I have a high-dimensional, non-empty polytope $Ax\geq b$ sitting inside the cube ($0\leq x_i \leq 1$). Is there any general theory or technique to show that this polytope contains an integer point, that is a point of the cube?

Unfortunately, $A$ is not totally unimodular.



  • 1
    $\begingroup$ This problem is NP-complete, so you're unlikely to find a good algorithm without more info about how the polytope is constructed. $\endgroup$ – Suresh Venkat Mar 6 '14 at 19:12

You could answer the question by trying all $2^n$ possible vectors with 0/1 entries (where $n$ is the dimension of the space), but let's assume you mean "is there an efficient algorithm to determine if an integer point exists?" The answer is basically "no"; the relevant area to look at is (binary) mixed integer linear programming.

| cite | improve this answer | |
  • $\begingroup$ Thanks for your answer. I know the algorithms for that problem, but the data is just too big for computations. I'm rather interested in a theoretical approach. $\endgroup$ – Richard Mar 6 '14 at 16:57

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.