Assessing Whether a MIP Could Have Been an LP

Audit a mixed-integer program to decide whether its integrality constraints are redundant. When the constraint matrix is totally unimodular and the right-hand side is integer, the LP relaxation already returns integer-optimal vertices and the MIP could have been formulated as an LP.

Step 1 of 157%

Tutorial

Auditing a MIP: Could It Have Been an LP?

Declaring variables integer in a MIP can balloon solve time relative to an LP. Sometimes those integer declarations are doing nothing: the LP relaxation already returns an integer-optimal vertex, and the MIP could have been an LP all along.

For a MIP of the form

\max\; c^\top x \quad \text{s.t.}\;\; Ax \le b,\; x \ge 0,\; x \in \mathbb{Z}^n,

the integrality constraints are redundant whenever:

$A$ is totally unimodular (TU), and
$b$ is integer.

When both hold, every vertex of the LP-relaxation polyhedron $\{x : Ax \le b,\, x \ge 0\}$ has integer coordinates, so the simplex method returns an integer optimum directly. The MIP could have been written as

\max\; c^\top x \quad \text{s.t.}\;\; Ax \le b,\; x \ge 0,

with the integrality constraints dropped.

The audit is mechanical:

TU? (look at $A$ ) ${}+{}$ Integer $b$ ? (look at the RHS) ${}\implies{}$ Drop the integrality constraints.

If either condition fails, integrality may be essential. We will see both flavors of failure shortly.