Welcome to MathOverflow

Question

2

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.

edited Oct 24 at 3:43

asked Oct 24 at 3:00

Steven Collazos
88●6

	Are you looking for a theoretical solution for a class of examples, or a computational solution for specific instances? – gordon-royle Oct 24 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 at 18:46

Michael Biro · Accepted Answer · 2012-10-24 03:50:36Z UTC

1

An incomplete solution:

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

answered Oct 24 at 3:50

Michael Biro
581●1●11

	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 at 4:52
	Obviously he doesn't (yet) have an answer for that case. $\:$ – Ricky Demer Oct 24 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 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 at 5:29

Thomas Kalinowski · Answer 2 · 2012-10-24 05:25:11Z UTC

5

This paper shows that testing integrality is coNP-complete.

answered Oct 24 at 5:25

Thomas Kalinowski
709●4●7

Is there a simple test to determine whether a polytope is integral?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.