Short note. A compact reference, correct as far as it goes. It will be expanded into a full guide with a worked example and an interactive demonstration.
Problem
Real cost curves are rarely straight lines — bulk discounts, economies of scale, and diminishing returns all bend. But MILP solvers want linear (or at worst convex quadratic) terms.
When to use it
Any nonlinear function of a single variable that you’re willing to approximate with straight segments: production cost curves, fuel consumption vs. speed, warehouse cost vs. utilization.
Formulation
Break the domain of x into breakpoints x_0 < x_1 < ... < x_k with known
function values f(x_i). Using the SOS2 (special-ordered-set) formulation,
introduce weights w_i >= 0 such that at most two adjacent weights are
nonzero:
x = sum(w_i * x_i for i in breakpoints)
f = sum(w_i * f(x_i) for i in breakpoints)
sum(w_i) = 1
at most 2 consecutive w_i nonzero # SOS2 constraintCode sketch
import gurobipy as gp
model = gp.Model()
x = model.addVar(name="x")
f = model.addVar(name="f")
breakpoints = [0, 100, 300, 600, 1000]
values = [0, 800, 1900, 3000, 3800] # f(x) at each breakpoint
model.addGenConstrPWL(x, f, breakpoints, values)Most commercial solvers (Gurobi’s addGenConstrPWL, CPLEX’s piecewise
helpers) wrap the SOS2 machinery for you — reach for those before
hand-rolling weights.
Pitfalls
- More breakpoints = better accuracy but more binary/SOS overhead and a slower solve. Start coarse, add breakpoints only where curvature is sharp.
- If the curve is convex and you’re minimizing cost (or concave and maximizing), you often don’t need SOS2 at all — a simple set of linear segments taken as an upper envelope works because the LP will naturally pick the right one. Try that first; it’s much cheaper.
- Approximation error compounds if this variable feeds into other nonlinear relationships downstream.