5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Are you looking for a theoretical solution for a class of examples, or a computational solution for specific instances? $\endgroup$ Oct 24, 2012 at 5:28
  • $\begingroup$ 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 ... $\endgroup$
    – John Doe
    Oct 27, 2012 at 18:46

2 Answers 2

1
$\begingroup$

An incomplete solution:

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

$\endgroup$
4
  • $\begingroup$ 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}$? $\endgroup$
    – J.C. Ottem
    Oct 24, 2012 at 4:52
  • $\begingroup$ Obviously he doesn't (yet) have an answer for that case. $\:$ $\endgroup$
    – user5810
    Oct 24, 2012 at 4:53
  • $\begingroup$ (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}$.) $\endgroup$
    – J.C. Ottem
    Oct 24, 2012 at 4:56
  • $\begingroup$ 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! $\endgroup$ Oct 24, 2012 at 5:29
7
$\begingroup$

In the paper The complexity of recognizing linear systems with certain integrality properties, Guoli Ding, Li Feng & Wenan Zang, Mathematical Programming 114, pages 321–334 (2008) the authors prove that testing integrality is coNP-complete.

$\endgroup$
0

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.