cutting-planes-valid-inequalities

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 single distinction drives the callback type, the parameters, and the failure modes.
• What substructure does the model contain? Knapsack rows (sums of bounded variables against a capacity) suggest cover and lifted cover cuts. Pairwise conflicts between binaries suggest clique cuts. Single mixed rows suggest MIR. Connectivity requirements suggest cut-set inequalities. No recognizable structure suggests letting Gomory/MIR machinery inside the solver do the work.
• Has the solver's own cut engine been given a chance? Gurobi separates Gomory, MIR, cover, clique, flow-cover, zero-half, and more by default. Try Params.Cuts = 2 (aggressive) and read the cut summary in the log before writing custom separation. Custom cuts pay off when you know structure the solver cannot see.
• Exact or heuristic separation? Exact separation for covers and cliques is itself NP-hard (a knapsack and a max-weight clique, respectively), but pseudo-polynomial DP or greedy heuristics are standard. Subtour separation is polynomial (min cut). Decide what the time budget per node allows.
• Problem size and cut volume. Estimate how many cuts a round can produce. Thousands of dense cuts can slow each LP reoptimization more than the bound improvement is worth.
• Solver and license. The callback recipes here use gurobipy (cbCut, cbLazy). PySCIPOpt and python-mip/CBC offer equivalents; CP-SAT does not expose user cuts.
• Data integrality. Cover-cut DP separation and pure Gomory arguments assume integer row data. Scale or round the data, or switch to MIR, when coefficients are fractional.
• Validation plan. Every separation bug produces a cut that slices off the optimum, and the solver will not warn you. Keep at least one known feasible (ideally optimal) solution of a small instance and assert that every generated cut is satisfied by it.
• Reporting needs. For research output, record bound-versus-round traces and percentage of root gap closed per cut family, not just final runtimes.