Cutting Plane Method

The cutting plane method is a classical technique for integer programming (IP) and mixed-integer programming (MIP) that iteratively tightens the LP relaxation with **valid inequalities** that cut off the fractional LP optimum without excluding any integer-feasible solution. The method was introduced by Gomory (1958) for integer programming (Gomory fractional cut) and Gomory (1960) for the mixed-integer variant (Gomory mixed-integer cut). The algorithm proceeds as follows: solve the LP relaxation; if the solution is integer the optimum is found; otherwise generate a cut that excludes the fractional point but preserves all integer-feasible points, add it to the model, and re-solve the LP; iterate until integrality. Cut families are problem-specific: knapsack cover cuts, flow cover cuts, clique cuts (graph coloring/IP), mixed-integer rounding (MIR), Chvátal-Gomory cuts, lift-and-project cuts (Balas, Ceria and Cornuéjols 1993), and subtour and comb inequalities for TSP (Padberg-Rinaldi 1991). Because pure Gomory cuts converge slowly in practice, modern implementations combine cuts with branch and bound (branch-and-cut, Padberg and Rinaldi 1991) — the foundational architecture of modern MIP solvers. Cut generation is automatic and largely invisible to the user. Nemhauser and Wolsey (1988), Wolsey (1998), and Cornuéjols (2008) are reference readings.