Is there a theorem that states that Integer Linear Problems with a Totally Unimodular constraint matrix are solvable in polynomial time?

186 Views Asked by At

Is there a theorem that states that Integer Linear Problems with a Totally Unimodular constraint matrix are solvable in polynomial time?

If the answer is positive, is it also valid for Mixed-Integer Linear Problems? And in which books can I find such theorem?

1

There are 1 best solutions below

1
On

Alexander Schrijver's Theory of Linear and Integer Programming has the following (Theorem 19.1), which is attributed to Hoffman and Kruskal,1956, Integral Boundary Points of Convex Polyhedra

"Let $A$ be a totally unimodular matrix and let $b$ be an integer vector. Then the polyhedron $P=\{Ax\leq b\}$ is integral."

This implies that any vertex solution to P will be integral. Since we can optimize over $P$ in polynomial time using linear programming to obtain such a vertex solution, we can solve problems with a Totally Unimodular constraint matrix AND an integer right hand side b in polynomial time. Note that the right hand side $b$ must be integer; I currently see that none of the other answers has mentioned this.

Since $P$ would be integral regardless of any integrality requirements on $x$, the theorem is valid for both Mixed-Integer Programs and Integer Programs.