MILP Formulation Patterns: Big-M, Linearization, and Tight Models

Two mathematically equivalent MILP formulations can differ in solve time by orders of magnitude. The craft of mixed-integer modeling is a set of reusable patterns — logical implications, linearized products, symmetry breaks — plus one governing principle: the tighter the LP relaxation, the faster branch-and-bound converges. This page collects the patterns practitioners actually use, in a form you can translate into Pyomo, PuLP, or any modeling layer.

Formulation tightness: why the LP relaxation decides solve time

Branch-and-bound prunes the search tree using the LP relaxation bound. A tight formulation — one whose relaxation polytope hugs the integer hull — gives strong bounds and small trees; a weak one forces the solver to enumerate. When comparing two correct formulations, prefer the one whose LP relaxation objective is closer to the integer optimum on sample instances; this single number predicts performance better than model size does. Fewer variables is not the goal — extended formulations with more variables are often tighter.

Big-M constraints: linking logic to arithmetic

The workhorse pattern activates a constraint only when a binary is set. "If facility y is closed (y=0), flow x must be zero; else x may be up to its bound":

x <= M * y        (x >= 0, y binary)

The entire art is choosing M as small as correctness allows. M is not "a big number" — it is the tightest valid upper bound on x when y = 1, derived from problem data (a capacity, a demand sum, a horizon length). Lazy choices like 1e9 cause two failures: a weak LP relaxation (y can sit at a tiny fractional value while satisfying the constraint) and numerical trouble, since solvers work with feasibility tolerances around 1e-6 and huge coefficient ranges break them. Compute a per-constraint M from the data; never share one global constant.

Indicator constraints: the big-M alternative

Modern solvers (Gurobi, CPLEX, SCIP; HiGHS support is partial) accept indicator constraints directly:

y = 1  ->  a'x <= b

No M appears, so there is nothing to mis-size and no numerical risk. The trade-off: the solver handles indicators via branching rather than the relaxation, so a well-sized big-M formulation often solves faster. A sound default: use indicators when a tight M is genuinely hard to derive, big-M when it is easy.

Linearizing a binary times a continuous variable

The product z = y · x (y binary, 0 <= x <= U) appears whenever a decision switches a quantity on. Replace it with three constraints:

z <= U * y
z <= x
z >= x - U * (1 - y)     (and z >= 0)

When y = 0 the first line forces z = 0; when y = 1 the second and third pin z = x. A binary-times-binary product z = y1 · y2 is the same idea: z <= y1, z <= y2, z >= y1 + y2 - 1. Products of two continuous variables cannot be linearized exactly — that is bilinear programming; discretize one variable or use a solver with bilinear support.

Absolute values, min/max, and piecewise-linear costs

|x| in the objective (minimizing): introduce t >= x, t >= -x, minimize t. No binaries needed because minimization pushes t down.
max(x1, x2) being minimized: t >= x1, t >= x2, minimize t. The mirror case (maximizing a max, or minimizing a min) does need binaries — convexity no longer helps.
Piecewise-linear convex costs (minimizing): model as the max of the segment lines, no binaries. Non-convex piecewise costs need SOS2 variables or a binary per segment; most solvers accept SOS2 natively and modeling layers expose it (pyo.Piecewise in Pyomo).

Either-or and logical implications

For "at least one of a'x <= b1 or c'x <= b2", introduce binary y:

a'x <= b1 + M1 * y
c'x <= b2 + M2 * (1 - y)

General Boolean logic over binaries compiles mechanically: y1 -> y2 becomes y1 <= y2; y = y1 AND y2 is the product pattern above; y = y1 OR y2 is y >= y1, y >= y2, y <= y1 + y2. Writing these five lines from memory is a large fraction of practical MILP fluency.

Symmetry breaking

If machines 1..K are identical, every solution has K! relabeled twins and the solver explores them all. Break the symmetry in the formulation:

Ordering: require machine k's total load >= machine k+1's, or that job j can only start machine k if machine k-1 is used.
Lexicographic assignment: item i may only go to bins 1..i (bin-packing convention).

Symmetry breaking can turn an unsolvable model into a seconds-long one. Solvers detect some symmetry automatically, but explicit constraints are more reliable. Take care to break each symmetry exactly once — over-constraining can cut off all optima.

Common weak-model smells

A single giant M shared across constraints of different scales.
Coefficients spanning more than ~6 orders of magnitude in one model (rescale units).
Large gap between LP relaxation and best integer solution from the first node (weak formulation — look for a tighter one or valid cuts).
Thousands of near-identical solutions in the log (unbroken symmetry).

When to reformulate vs when to switch solvers

Exhaust formulation improvements before shopping for solvers: tightening one family of constraints routinely beats a 5x-faster engine, and it is free. Switch tools when the problem class is wrong for MIP altogether — heavy disjunctive scheduling structure usually belongs in CP-SAT rather than a big-M-encoded MILP.