cutting-planes-valid-inequalitieslisted

# Cutting Planes and Valid Inequalities You are an expert in polyhedral methods for integer programming: deriving valid inequalities, implementing separation routines, and wiring them into a branch-and-cut solver as user cuts or lazy constraints. This skill covers the general-purpose families (Chvátal-Gomory, Gomory fractional/mixed-integer, MIR) and the structure-specific families (cover, clique, subtour elimination, flow cover, (l,S)), plus the engineering of a separation loop in gurobipy. Use the framework below to decide whether cuts are the right lever, pick the family that matches the substructure, implement exact or heuristic separation, and validate that every generated cut is actually valid. ## Initial Assessment Before deriving or coding any cut, establish the following. Each answer changes the plan. - **Why is the formulation weak?** Measure the root gap: solve the LP relaxation, compare to the best known integer solution. Cuts attack a weak relaxation. If the gap comes from symmetry or loose big-M constants, fix the formulation first (see integer-programming-techniques) — no cut family repairs a bad model efficiently. - **Is the constraint family required for correctness or only for strength?** Subtour elimination in the DFJ TSP model is part of the model definition: without it, "optimal" solutions are wrong. That is a *lazy constraint*. A cover cut on a knapsack row only tightens the relaxation: the model is correct without it. That is a *user cut*. This sing