Linearization techniques

What problem does this solve?

Real decision models are full of things that are not linear: “if we open the plant, pay the fixed cost,” “use at most one of these suppliers,” “the cost per unit drops after 1,000 units,” “minimize the worst-case lateness,” “the product of two yes/no decisions.” Mixed-integer linear programming (MILP) solvers are extraordinarily good, but they only accept linear objectives and constraints over continuous and integer variables.

Linearization is the set of exact reformulations that bridge the gap. Each pattern introduces auxiliary variables and linear constraints whose feasible solutions correspond one-to-one with the original nonlinear logic.

When should you use it?

• The nonlinearity involves binary or integer decisions: products, logic, fixed costs, either-or conditions. These linearize exactly.
• The nonlinear function is convex in a minimization (or concave in a maximization) and piecewise linear: maxima, absolute values, increasing marginal costs. These linearize exactly with no extra binaries.
• The function is nonlinear and non-convex but can be approximated by pieces to acceptable accuracy, at the price of extra binaries.

Prefer a native solver feature when one exists (indicator constraints, SOS2, general constraints like max or abs in modern solvers). They often presolve better than a hand-written big-M.

Mathematical formulation

The core patterns, with $x, y \in \{0,1\}$ binary and $z$ continuous with known bounds $0 \le z \le U$:

Product of two binaries, $w = x\,y$:

Binary times bounded continuous, $w = x\,z$ (exact McCormick envelope):

Fixed charge (pay $f$ if any quantity $q \le U$ is produced):

Conditional constraint (big-M: enforce $a^\top q \le b$ only when $y = 1$):

Absolute value in a minimization, $t = |u|$:

Min-max (minimize the worst of several linear terms):

Logic over binaries. “At most one”: $\sum_i y_i \le 1$. “If A then B”: $y_A \le y_B$. “A or B”: $y_A + y_B \ge 1$. “Exactly $k$”: $\sum_i y_i = k$.

Piecewise linear cost with breakpoints $(a_j, f(a_j))$: write $q = \sum_j \lambda_j a_j$, cost $= \sum_j \lambda_j f(a_j)$, $\sum_j \lambda_j = 1$, $\lambda \ge 0$, with at most two adjacent $\lambda_j$ nonzero (an SOS2 condition, or binaries per segment). If $f$ is convex in a minimization, the adjacency condition can be dropped.

Intuition

Every linearization is the same move: name the nonlinear quantity as a new variable, then fence it in with linear constraints that are tight exactly where the logic says it should be.

For $w = xy$ with binaries, the four constraints describe the convex hull of the four points $(x, y, w) \in \{(0,0,0), (0,1,0), (1,0,0), (1,1,1)\}$. The LP relaxation is as tight as it can be, which is why this linearization is “free.”

Big-M is different. It is exact for integer solutions but weak in the LP relaxation when $M$ is large, because fractional $y$ can switch the constraint mostly off. That is why the size of $M$ is a modeling decision, not a constant: use the smallest valid bound you can derive from the data.

The convex cases (absolute value, max in a minimization) need no binaries at all, because the solver is pushing $t$ down onto the largest of the terms anyway.

Worked example

A plant can run a product line or not. Running costs a fixed $5,000 and $12 per unit, capacity is 800 units, and if it runs it must produce at least 200 units (a minimum batch). Demand $d$ must be met from this line or bought from a supplier at $20 per unit.

Let $y \in \{0,1\}$ be “run the line,” $q$ the units produced, $s$ the units bought:

The single constraint pair $200y \le q \le 800y$ encodes three rules at once: no production unless the line runs, at least the minimum batch if it does, and never more than capacity. Producing $q$ saves $8 per unit against buying, so running pays when $8q > 5000$, that is, above 625 units of demand. For $d = 500$ the model buys all 500 ($10,000 against $11,000 for running); for $d = 700$ it runs and makes 700 ($13,400 against $14,000).

Python implementation

Written with scipy.optimize.milp, which ships with SciPy and needs no separate solver install:

import numpy as np
from scipy.optimize import milp, LinearConstraint, Bounds

def plan(d):
    # variables: [y, q, s]
    c = np.array([5000.0, 12.0, 20.0])
    A = np.array([
        [0.0, 1.0, 1.0],     # q + s >= d
        [-800.0, 1.0, 0.0],  # q - 800 y <= 0    (no production unless running; capacity)
        [200.0, -1.0, 0.0],  # 200 y - q <= 0    (minimum batch if running)
    ])
    cons = LinearConstraint(A, lb=[d, -np.inf, -np.inf], ub=[np.inf, 0.0, 0.0])
    res = milp(c, constraints=cons, integrality=[1, 0, 0],
               bounds=Bounds([0, 0, 0], [1, np.inf, np.inf]))
    y, q, s = res.x
    return round(y), round(q), round(s), res.fun

for d in (500, 700):
    print(d, plan(d))   # 500 -> (0, 0, 500, 10000.0); 700 -> (1, 700, 0, 13400.0)

The same model in Pyomo, PuLP, gurobipy, or OR-Tools differs only in syntax; the linearization is identical.

Interactive demonstration

A MILP Formulation Explorer that lets you toggle constraints and watch the LP relaxation and integer optimum move is planned for the playground. The Optimization page has a one-page guide to deciding whether linear or integer programming fits your problem at all.

Computational complexity and trade-offs

• Every binary can double the search space. Branch and bound explores far fewer nodes than $2^n$ in practice, but tight formulations matter enormously.
• Tightness beats compactness. A formulation with more constraints but a tighter LP relaxation usually solves faster than a compact one with big-M constraints.
• Big-M size drives both relaxation weakness and numerical trouble. Values like $10^6$ against coefficients near 1 invite tolerance errors where $y = 10^{-6}$ quietly activates a constraint.
• Piecewise approximations trade accuracy for binaries: more breakpoints, more accurate, slower.

Common mistakes

• One giant M for every constraint. Derive a separate, tight bound per constraint from the data.
• Linearizing a convex term with binaries when the plain epigraph constraints would do.
• Linearizing a non-convex maximum in a minimization with only $t \ge g_k$; that models the maximum correctly only when the objective pushes $t$ down.
• Forgetting the lower fence. $w \le x$ and $w \le y$ alone let the solver set $w = 0$ even when both are 1, if it has a reason to.
• Hand-coding what the solver already supports. Indicator constraints and SOS2 sets are often handled better natively.

The individual techniques have their own notes: big-M, absolute value, min-max, indicator constraints, logical constraints, and piecewise-linear approximation.

Related patterns