LP Relaxation and Optimality Gaps

An integer program (IP) requires some or all variables to take integer values, which generally makes it much harder to solve than an ordinary linear program. The LP relaxation of an integer program is the linear program obtained by dropping every integrality constraint while keeping the objective and all other constraints unchanged.

Consider the IP for assigning aircraft to two routes, where $x_1, x_2$ are integer counts of aircraft:

$$\begin{aligned}\text{maximize}\quad & 6x_1 + 4x_2\\ \text{subject to}\quad & 2x_1 + x_2 \le 7\\ & x_1 + 2x_2 \le 8\\ & x_1,\ x_2 \ge 0,\ \text{integer.}\end{aligned}$$

Its LP relaxation is

$$\begin{aligned}\text{maximize}\quad & 6x_1 + 4x_2\\ \text{subject to}\quad & 2x_1 + x_2 \le 7\\ & x_1 + 2x_2 \le 8\\ & x_1,\ x_2 \ge 0.\end{aligned}$$

For binary variables $x_i \in \{0,1\}$, the relaxation replaces the binary requirement with the bounds $0 \le x_i \le 1$.

The LP relaxation is much easier to solve than the original IP because LPs are solvable in polynomial time (e.g., by the simplex method), whereas IPs are generally NP-hard.