Cutting Plane Methods

Optimization · Axiom Academy

Tightening LP relaxations to solve integer programs more efficiently 1. The LP Relaxation and Cutting Planes When we relax the integer constraints of an integer program (IP), we obtain an LP relaxation that is easier to solve but may yield fractional solutions. The feasible region of the LP (blue) is larger than the convex hull of integer points (green). A cutting plane is a linear inequality that: Is valid for all integer feasible points Cuts off part of the LP relaxation (specifically, fractional solutions) Tightens the formulation, bringing the LP relaxation closer to the integer hull A valid inequality for an integer program is any constraint satisfied by all integer feasible solutions . Not all valid inequalities are useful as cuts, but strong cuts satisfy two properties: When we add a cutting plane to the LP relaxation, we eliminate fractional vertices without removing any integer solutions. The animation shows how adding multiple cuts progressively tightens the relaxation. 3. Gomory Cuts from the Simplex Tableau The Gomory fractional cut is a systematic way to derive cutting planes from an optimal simplex tableau of the LP relaxation. If we have a basic variable x i with a fractional value, we can generate a cut from its row. Consider a row from the simplex tableau where x i is basic: The Gomory cut takes the form of collecting the fractional parts. This cut is guaranteed to: Be valid for all integer feasible points Cut off the current fractional LP solution

This is the written version of the interactive lesson above. See the full Optimization course.