HLPL / VerTeX Modelling Language Documentation

← lessons

The LP relaxation as a bound

Drop the integers, solve fast, get a bound for free.

Chapter: 0b — MIP theory · lesson id mip-relaxation · theory lesson

---

Almost every algorithm for integer programming starts the same way: throw out the integrality constraints, solve the resulting LP, and use what you learn. The LP $relaxation$ is cheap, mature, and — most importantly — its optimum is a $bound$ on the integer optimum.

Notes

Definition (LP relaxation). Given an MIP $\min\ c^{\top} x$ s.t. $A x \leq b$, $x_{j} \in \mathbb{Z}$ for $j \in I$, $x \geq 0$, the $LP\ relaxation$ is the LP obtained by $dropping$ the integrality constraints: $\min\ c^{\top} x$ s.t. $A x \leq b$, $x \geq 0$. The relaxation has a strictly larger (or equal) feasible set than the MIP.

Theorem (LP relaxation gives a bound). Let $v_{\text{LP}}$ be the optimal value of the LP relaxation and $v_{\text{MIP}}$ the optimal value of the MIP. For a minimisation, $v_{\text{LP}} \leq v_{\text{MIP}}$. For a maximisation, $v_{\text{LP}} \geq v_{\text{MIP}}$.

Proof, step by step (Why the relaxation gives a bound (min case)).

1. What is the relationship between the feasible sets? Every MIP-feasible point is also LP-relaxation-feasible (it satisfies the linear constraints; the integrality constraints we dropped only excluded points, never added any). So $F_{\text{MIP}} \subseteq F_{\text{LP}}$.
2. How does the optimal value of a minimisation respond when the feasible set grows? Minimising over a larger set can only decrease (or hold) the optimum. Formally, if $F \subseteq G$ then $\min_{F} f \geq \min_{G} f$.
3. Combine. Therefore $v_{\text{LP}} = \min_{F_{\text{LP}}} c^{\top} x \leq \min_{F_{\text{MIP}}} c^{\top} x = v_{\text{MIP}}$. The relaxation underestimates the integer optimum. $\blacksquare$

This is the foundation of every practical MIP algorithm. A bound is useful in three ways:

• $Stopping\ early$. If the LP relaxation already gives $v_{\text{LP}} = 100$ for a min problem and you find a feasible integer solution with value $100$, you are done: the integer solution is provably optimal.
• $Pruning\ search$. In branch-and-bound, a subproblem whose LP relaxation is worse than the best known integer solution can be pruned without searching further. The bound is the basis of the "bound" in the name.
• $Sensitivity\ analysis$. The LP dual variables (from the relaxation) tell you which constraints are economically binding even when integrality bites.

Definition (Integrality gap). For a minimisation MIP instance, the $absolute\ integrality\ gap$ is $v_{\text{MIP}} - v_{\text{LP}} \geq 0$; the $relative\ integrality\ gap$ is the ratio $v_{\text{MIP}} / v_{\text{LP}}$ (which is $\geq 1$). For a maximisation MIP, swap roles: gap is $v_{\text{LP}} - v_{\text{MIP}}$ or the ratio $v_{\text{LP}} / v_{\text{MIP}}$. The integrality gap of a $formulation$ is the worst-case relative gap across all instances. A formulation with gap close to $1$ is called $tight$ or $strong$; a loose formulation has a large gap and produces weak relaxations.

Example (Tight vs. weak formulations). Two ways to say "$x \leq M y$ for binary $y$": (a) write $x \leq M y$ literally with a large $M$; (b) write $x \leq u y$ where $u$ is the tightest upper bound on $x$. Both are correct, but (b) yields a tighter LP relaxation and faster solver runtimes. Choosing constants well — picking the smallest valid $M$ — is one of the main skills of an OR practitioner.

Quick check. A minimisation MIP has LP relaxation value $42.7$. The solver finds an integer feasible solution with value $44$. What can you say?

• The integer optimum is exactly $43$.
• The integer optimum is in the interval $[42.7, 44]$. ← correct
• There is no integer optimum because $42.7$ is not an integer.

Recap.

• The LP relaxation drops integrality. Its optimum is a bound on the MIP optimum (under-estimate for min, over-estimate for max).
• Bounds drive every branch-and-bound search, prune large subtrees, and certify optimality.
• Tighter formulations have smaller integrality gaps and faster solves.

Read this through MCP: read with path: "lessons/mip-relaxation", or resource hlpl://lessons/mip-relaxation.