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,574 Downloads   10,443 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.

Copyright © 2024 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.