When LP Solutions are Automatically Integer

Uses the Hoffman–Kruskal theorem to identify integer programs whose LP relaxations are guaranteed to have integer optimal solutions, eliminating the need for branch-and-bound.

Step 1 of 157%

Tutorial

The Hoffman–Kruskal Theorem

A square matrix is totally unimodular (TU) if every square submatrix has determinant in $\{-1, 0, 1\}$ . The reason we care about TU matrices is the following result, which links them directly to linear programming.

Hoffman–Kruskal Theorem. If $A$ is totally unimodular and $\mathbf{b}$ is an integer vector, then every basic feasible solution of

\{\,\mathbf{x} : A\mathbf{x} \le \mathbf{b},\ \mathbf{x} \ge \mathbf{0}\,\}

has integer coordinates.

Because every LP attains its optimum at a basic feasible solution, this gives an immediate corollary:

Corollary. If $A$ is TU and $\mathbf{b}$ is integer, then

\max\ \mathbf{c}^T\mathbf{x}\quad\text{s.t.}\quad A\mathbf{x}\le \mathbf{b},\ \mathbf{x}\ge \mathbf{0}

has an integer optimal solution — for any objective $\mathbf{c}$ .

The same conclusion holds with $A\mathbf{x} = \mathbf{b}$ , $A\mathbf{x} \ge \mathbf{b}$ , or any combination.

In other words, when $A$ is TU and $\mathbf{b}$ is integer, the LP relaxation automatically solves the integer program — no branch-and-bound, no cutting planes.

Two hypotheses must hold:

$A$ is totally unimodular.
$\mathbf{b}$ has all integer entries.

The objective $\mathbf{c}$ plays no role.