Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

It is known that any rational convex polytope expressed as $\{ x\in\mathbb{R}^d : Ax \ge b \}$, where $A\in\mathbb{Z}^{k\times d}$ and $b\in\mathbb{Z}^k$, can be written as the convex hull of finitely many points.

My question is, given the above representation in terms of hyperplanes, one can determine (easily) whether the polytope is integral ---that is, whether the polytope can be written as the convex hull of points in the integer lattice.

share|improve this question
    
Are you looking for a theoretical solution for a class of examples, or a computational solution for specific instances? –  Gordon Royle Oct 24 '12 at 5:28
    
I am currently interested in figuring out whether, under some reasonable conditions, certain polytopes I am studying are integral. The class of polytopes I am looking at must satisfy some specific symmetry conditions. If for certain parameters I could argue that the polytope must be totally unimodular (as someone pointed out below), then that would be nice ... –  Steven Collazos Oct 27 '12 at 18:46
add comment

2 Answers 2

up vote 1 down vote accepted

An incomplete solution:

There is a polynomial-time test for total unimodularity, and if $A$ is totally unimodular, then the polytope is integral.

share|improve this answer
    
What if $A$ is not unimodular? E.g., $A=\begin{pmatrix}1 & 0\\ 0 & 1\\ 2 & 1 \end{pmatrix}$ and $b=\begin{pmatrix}0 \\ 0 \\ 2\end{pmatrix}$? –  J.C. Ottem Oct 24 '12 at 4:52
    
Obviously he doesn't (yet) have an answer for that case. $\:$ –  Ricky Demer Oct 24 '12 at 4:53
    
(the example should have been $A=\begin{pmatrix}1 & 0\\ 0 &1\\ 2 & -1\end{pmatrix}$ and $b=\begin{pmatrix}0 \\ 0 \\ -2\end{pmatrix}$.) –  J.C. Ottem Oct 24 '12 at 4:56
    
Right, if $A$ is not totally unimodular then this test is inconclusive. I'm not aware of an efficient test that works for all $A,b$, though I'd certainly be interested to see one! –  Michael Biro Oct 24 '12 at 5:29
add comment

This paper shows that testing integrality is coNP-complete.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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