Data Pattern Pro

Mathematical programming / Linearization

Min/Max Linearization

Represent max(a, b) or min(a, b) as auxiliary variables and linear constraints so they can appear in a MILP.

Note Intermediate

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

You need a variable that equals the worst-case (or best-case) of several quantities — e.g. the makespan of a schedule is the max completion time across all jobs. max() and min() aren’t linear operators.

When to use it

Anytime a “bottleneck” or “worst-of” quantity drives your objective or a constraint: makespan, peak load, latest arrival time.

Formulation

For z = max(a_1, ..., a_n), it’s enough to bound z from above by each term and let the objective push it down to the tightest one — only when you’re minimizing z:

z >= a_i   for all i
minimize z

For z = min(a_1, ..., a_n) when maximizing z, the mirror image:

z <= a_i   for all i
maximize z

If you need the max/min as an input to further constraints (not just the objective), you need binaries to select which term is active — that’s the same complementarity issue as in absolute value linearization.

Code sketch

import pulp

prob = pulp.LpProblem("minimize_makespan", pulp.LpMinimize)
completion = {j: pulp.LpVariable(f"c_{j}", lowBound=0) for j in jobs}
makespan = pulp.LpVariable("makespan", lowBound=0)

for j in jobs:
    prob += makespan >= completion[j]

prob += makespan  # objective

Pitfalls

  • This “bound and let the objective do the work” trick only holds in one direction (min of a max, or max of a min). Get the direction backwards and the solver has no incentive to tighten z — it’ll sit at whatever bound you gave it.
  • If z also needs to feed into other constraints elsewhere in the model, you generally need to know which a_i achieved the max, which brings back binaries and Big-M/indicator constraints.