Can we have an integer polytope when $A$ is not totally unimodular and $b$ is an integer vector?

680 Views Asked by At

I am kind of confused. I know the theorem that: " Let $A$ be totally unimodular and b an integer vector. The polytope $P :$= {$x$ | $Ax$ ≤ $b$} is integer (all vertices are integer)."

So I'm wondering if $A$ is a {$-1,0,1$} matrix and b is an integer vector then the set {$Ax \leq b |$ R$^n$} is an integer polytope?

If this is true can you give me an example.

Thank you

1

There are 1 best solutions below

1
On BEST ANSWER

Total unimodularity is a sufficient, but not necessary condition for a constraint matrix (given integral $b$) to define an integer polytope (cp. Polyhedra with the Integer Carathéodory Property ). An example given by that paper:

\begin{bmatrix} 1&1&1&1&1&0&0&0&0&0\\1&1&0&0&0&0&0&1&0&1\\0&1&1&0&0&1&0&0&1&0\\0&0&1&1&0&0&1&0&0&1\\0&0&0&1&1&1&0&1&0&0 \end{bmatrix}