The paper Solving the Binary Linear Programming Model in Polynomial Time claims that Binary Integer Linear Programming is in P. However, it seems that no subsequent literature in the mainstream has done any further study on this. I am a bit doubtful regarding the correctness of the claim made in that paper. Therefore, I have put this question here.


Often called Binary Integer Programming (BIP). Wikipedia:

Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems.

Here is a list of those 21 Karp problems.

You can also find the claim that BIP $\in$ NPC in many class notes, e.g., this set.

  • 6
    $\begingroup$ The cited paper actually acknowledges that BIP is NP-complete. In fact the paper explicitly claims to have proven that P = NP. That by itself is plenty reason to be "doubtful regarding the correctness of the claim" in the paper. $\endgroup$ – Timothy Chow Aug 14 '19 at 21:52
  • 1
    $\begingroup$ Thanks, @Joseph O'Rourke for your reply! However, I did check Wiki before posting the question. Please let me know if you are aware of any recent development on this. $\endgroup$ – aroyc Aug 16 '19 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.