6
$\begingroup$

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.

$\endgroup$

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
3
  • 7
    $\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$ Aug 14, 2019 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, 2019 at 15:16
  • 1
    $\begingroup$ The paper converts BIP to convex quadratic programming... whose minimization is solvable in polynomial time. but the author wants his readers to maximize a convex quadratic program which is very very hard. unless he came up with methods of maximizing convex quadratic program. $\endgroup$
    – D. Sikilai
    Jul 8, 2022 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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