As far as I know, Integer Linear Programming(ILP) problem is NP-complete. According to the following paper, Binary Linear Programming problem(BLP) can be solved in Polynomial time. http://dx.doi.org/10.4236/ajor.2016.61001

I'm not familiar with the convex Quadratic Problem mentioned in the paper. However, I know that ILP can be converted to Binary Linear Programming problem in polynomial time, which means ILP will also be P, rather than NP-complete, if this paper is correct.

If the paper above is something rubbish, then for the following specific BLP problem, can it be solved in polynomial time of n? The very special point of this BLP is that the coefficients $A$ are also binary.

\begin{align} \min_{x} \quad & [c]_{1 \times n}[x]_{n \times 1} \\ \text{s.t.} \quad & [A]_{m \times n}[x]_{n \times 1} = [1]_{m \times 1} \\ \; & x\in\mathbb{B}\\ \; & A\in\mathbb{B}\\ \; & \forall j\in\{1,2,...,n\}, \sum\limits _{i=1} ^m A_{i,j} =k;k\in Int^+ \end{align}

I strongly believe this problem can be solved in Polynomial time, as I've tried "bintprog"(Tomlab/CPLEX) in Matlab on this problem of size up to n≈14000, and it can be solved in 5s on my laptop(intel i5-4210U). I've done some search in the IBM CPLEX document, but still haven't got a clue yet.

Right now I can only confirm the time complexity of this problem as $ O(n^m)$, but this is not a strong Polynomial Time notation as $ m $ can be as large as $ n $.

  • $\begingroup$ BLP is NP-complete, so I wouldn’t trust the paper. Your special case is NP-complete, by reduction from 1-in-3 SAT. $\endgroup$ – Yuval Filmus Jul 6 '19 at 22:05
  • $\begingroup$ is finding the intersection of two hyperplanes in $n$ dimension also NP-complete? According to pdfs.semanticscholar.org/f4a6/… $\endgroup$ – Six How Jul 6 '19 at 22:13
  • $\begingroup$ I’m not sure what that means. In any case, it sounds like a separate question. $\endgroup$ – Yuval Filmus Jul 6 '19 at 22:14
  • $\begingroup$ Thank you. If this specific BLP is not P, then finding the intersection of two hyperplanes in $n$ dimension should also be NP-complete... because each row in the constraint condition can be regarded as a hyperplane, and the solution is just just equivalent to finding the intersection. However, intuitively, it shouldn't be that hard@_@ $\endgroup$ – Six How Jul 6 '19 at 22:25

Your Answer

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

Browse other questions tagged or ask your own question.