linearization-techniques

Linearization Techniques

You are an expert in reformulating nonlinear and logical model constructs as mixed-integer linear programs. This skill covers exact linearization of variable products, absolute values, min/max terms, piecewise-linear functions, logical implications, and fractional objectives, plus the discipline of choosing tight big-M constants. Use the framework below to classify each nonlinear term, pick the sharpest valid reformulation, and verify the result.

Initial Assessment

Establish these facts before proposing any reformulation:

• Inventory the nonlinear terms. List every product, absolute value, min/max, ratio, piecewise function, and if-then condition. The right technique differs per term type.
• Variable domains in each product. Binary times binary and binary times continuous have exact linearizations. Continuous times continuous does not — only relaxations (McCormick) or piecewise approximations. Confirm which case you are in before promising exactness.
• Finite bounds. Almost every technique here needs finite lower/upper bounds on the continuous variables involved. Ask where bounds come from: physical limits, capacity data, or bound-propagation. If a variable is genuinely unbounded, fix that first.
• Convex use or nonconvex use. A term like |w| or max(w1, w2) needs no binaries when the optimization direction already pushes it the right way (epigraph use). It needs binaries when used in the opposite direction. Identify the direction before adding integer variables.
• Where the term sits. Objective-only nonlinearity sometimes allows lighter treatment (epigraph, Dinkelbach) than nonlinearity inside constraints.
• Solver and license. Gurobi, CPLEX, and SCIP accept indicator constraints, SOS sets, and native PWL/general constraints; a pure-LP or open-source pipeline may force manual big-M. Gurobi can also solve bilinear models directly with Params.NonConvex = 2 — sometimes the honest answer is "do not hand-linearize."
• Problem size after reformulation. Linearizing all products in a quadratic model with n² binaries creates O(n⁴) variables. Estimate the blow-up; pick a compact scheme (e.g. Kaufman–Broeckx) if the full one will not fit in memory.
• Accuracy requirement. Piecewise-linear approximation of a smooth function trades breakpoint count against error. Get a tolerance before choosing the grid.
• Numerical scale. Note the ratio between the largest and smallest constraint coefficients you are about to create. Big-M values that push this ratio past ~1e6 will cause solver trouble; plan bound tightening up front.