2
$\begingroup$

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.

Thanks,

Richard

$\endgroup$
1
  • 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$ Mar 6, 2014 at 19:12

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2014 at 16:57

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.