American Journal of Operations Research

Volume 6, Issue 1 (January 2016)

ISSN Print: 2160-8830   ISSN Online: 2160-8849

Google-based Impact Factor: 1.72  Citations  

Solving the Binary Linear Programming Model in Polynomial Time

HTML  XML Download Download as PDF (Size: 253KB)  PP. 1-7  
DOI: 10.4236/ajor.2016.61001    6,789 Downloads   10,634 Views  Citations
Author(s)

ABSTRACT

The paper presents a technique for solving the binary linear programming model in polynomial time. The general binary linear programming problem is transformed into a convex quadratic programming problem. The convex quadratic programming problem is then solved by interior point algorithms. This settles one of the open problems of whether P = NP or not. The worst case complexity of interior point algorithms for the convex quadratic problem is polynomial. It can also be shown that every liner integer problem can be converted into binary linear problem.

Share and Cite:

Munapo, E. (2016) Solving the Binary Linear Programming Model in Polynomial Time. American Journal of Operations Research, 6, 1-7. doi: 10.4236/ajor.2016.61001.

Cited by

[1] Exact Vertex Migration Model of Graph Partitioning Based on Mixed 0–1 Linear Programming and Iteration Algorithm
Journal of the Operations …, 2024
[2] Model-Predictive Control in Communication Networks
2023
[3] Optimal placement of sensors to enhance degrees of freedom in monostatic collocated MIMO radar
Hashemi, E Yazdian - Digital Signal Processing, 2023
[4] Energy-Efficient and Security-Aware Task Offloading for Multi-Tier Edge-Cloud Computing Systems
IEEE Access, 2023
[5] Two dimensional Minimum Sensor Array: A new perspective to array design
IEEE Sensors Journal, 2023
[6] Priority‐based resource allocation in wireless powered UAV‐assisted networks
IET Networks, 2022
[7] Simplified Shelf Problem as a Binary Linear Integer Programming Problem
2022
[8] Optimization of Oil Well Production Using Binary Programming Method: Case Study Offshore Platform
Proceedings of the International Conference on Industrial Engineering and Operations Management, 2021
[9] Reducing the complexity of the knapsack linear integer problem by reformulation techniques
… Journal of System Assurance Engineering and …, 2021
[10] Linear Integer Programming
Linear Integer Programming, 2021
[11] The Traveling Salesman Problem: Network Properties, Convex Quadratic Formulation, and Solution
2021
[12] An Efficient Method for Sparse Linear Array Sensor Placement to Achieve Maximum Degrees of Freedom
Hashemi… - IEEE Sensors …, 2021
[13] Optimization of unmanned aerial vehicle augmented ultra-dense networks
2020
[14] Route Optimization for Residential Solid Waste Collection: Mmabatho Case Study
2019
[15] The equal tendency algorithm: a new heuristic for the reliability model
International Journal of System Assurance Engineering and Management, 2019
[16] The Controversial Millennium Problem–Proof that NP= P
2019
[17] Joint Beamforming, User Association, and Power Control for Cellular-Enabled UAV Communications
2019
[18] Joint Beamforming, User Association, and Height Control for Cellular-Enabled UAV Communications
2019
[19] A linear algorithm for reliable predictive network control
2018
[20] Second Proof That P= NP
2016
[21] De Gruyter Series on the Applications of Mathematics in Engineering and Information Sciences

Copyright © 2025 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.