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

Improve this question
$\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$
    – Suresh Venkat
    Commented Mar 6, 2014 at 19:12

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Mar 6, 2014 at 16:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .