CUTTING PLANE METHOD

Progressively tightening the feasible region with valid inequalities

3
60°
The cutting plane method (Gomory, 1958) solves integer programs by iteratively solving LP relaxations and adding valid cuts that exclude the fractional LP optimum without removing any integer feasible point. Each Gomory cut is derived from a tableau row: if a basic variable has fractional value f, the cut {fractional parts} ≥ f is a valid inequality satisfied by all integer points. After enough cuts, the LP relaxation's optimum coincides with the integer optimum. Combined with Branch & Bound (the B&B+cutting framework), cutting planes are the basis of modern MIP solvers like CPLEX and Gurobi, reducing tree sizes by orders of magnitude.