Integer Programming & LP Relaxation

Relax integrality for a bound, then measure the integrality gap.

The idea

An integer program is a linear program whose variables must take whole-number values: maximize $c^{\top}x$ over $x \ge 0$ with $Ax \le b$ and $x \in \mathbb{Z}^{n}$. Many decisions are only meaningful in whole numbers — how many machines to buy, whether an edge is used — and the integrality requirement is what makes the problem hard: without it we would have an ordinary linear program, which we can solve efficiently.

The LP relaxation drops that requirement. It keeps the same objective and the same constraints but lets $x$ range over all real vectors with $x \ge 0$ and $Ax \le b$. Every point the integer program may choose remains feasible for the relaxation, so the relaxation optimizes over a larger region, and for a maximization its optimum cannot come out lower:

$\mathrm{OPT}_{\mathrm{LP}} \ge \mathrm{OPT}_{\mathrm{IP}}.$

The relaxation is therefore an upper bound on the integer optimum that we can actually compute, and the difference between the two values, the integrality gap, measures what integrality costs. In two variables the picture is a polygon dotted with integer points: the relaxation's optimum sits where a level line of $c^{\top}x$ last touches the polygon — a vertex, in general fractional — while the integer program must settle for the best integer point inside. When the gap is zero, the relaxation's solution already answers the integer question. When it is not, the fractional solution must still be converted into an integer one, and not merely by rounding: the nearest integer point can violate the constraints.

Ways to work on it

• Walkthrough. Relax an integer program to a linear program and see what the relaxed optimum tells you.
• Practice. Round a fractional LP optimum to the integer optimum.
• Hardest. Solve a 2-D LP relaxation at its vertex and reason about the integrality gap.

Not sure where to start? Take the ten-question placement test.