A Big-M Formulation is a modelling technique in Mixed-Integer Programming (MIP) that uses a large finite constant M to encode logical disjunctions as linear constraints. When a binary decision variable y equals 1, the constraint of the form x ≤ M·y is made loose, allowing x to take any value up to M. When y equals 0, the constraint forces x to zero, effectively activating or deactivating a variable or constraint based on a binary choice. Big-M formulations are the dominant technique for encoding on/off decisions, precedence relationships, and piecewise-linear functions in mixed-integer models.
The relationship is mechanical but critical: x ≤ M·y creates a coupling where the binary y controls the upper bound on x. If y=1, the constraint becomes x ≤ M (non-restrictive if M is set correctly). If y=0, the constraint becomes x ≤ 0, forcing x to zero. This pattern repeats across crew scheduling (only include a flight-crew pairing if a binary assignment variable equals 1), facility location (only allow demand to be served from a facility if that facility is open), and cutting patterns (only use a cut pattern if a binary pattern-selection variable is activated).
Decision variables: y_i = 1 if warehouse i is open, 0 otherwise. d_ij = demand assigned from warehouse i to customer j.
Big-M constraint: d_ij ≤ M·y_i ensures that demand can only be assigned from warehouse i if warehouse i is open (y_i = 1). If y_i = 0, the constraint forces d_ij ≤ 0, which combined with non-negativity forces d_ij = 0.
Choosing M: M must be at least as large as the maximum possible demand that could be assigned from any single warehouse. A too-small M cuts off feasible solutions. A too-large M (e.g., M = 999,999) makes the LP relaxation weak: the continuous solver can set y_i = 0.0001 and d_ij ≈ 99,999, nearly ignoring the binary requirement.
The payoff of correct M: A tight M keeps the LP relaxation strong, reducing the integrality gap and allowing solvers to prove optimality faster.
Mistake 1: "Set M as large as possible for safety." The intuitive approach is to set M "as large as possible" to guarantee feasibility regardless of the data. This is wrong in practice. A large M makes the LP relaxation very weak: the continuous solution can ignore the binary constraint almost entirely, because M·y allows x to be nearly anything even before branching. This inflates the integrality gap, forces the solver to explore far more branch-and-bound nodes, and introduces numerical instability when M is set to extreme values such as 10^6 or 10^9. The correct M is the tightest value that does not cut off any feasible solution: derived from problem-specific bounds, not from an arbitrary large number. A good Big-M is a formulation quality decision, not a safety parameter.
Mistake 2: Ignoring indicator constraints in modern solvers. A second common confusion is treating Big-M as equivalent to indicator constraints. Modern solvers (Gurobi 12, HiGHS 1.14) handle indicator constraints natively (e.g., "if y=1 then constraint c holds") and internally generate tighter reformulations than a manually specified M. Where the solver supports indicator constraints, they are almost always preferable to a manually chosen M.
The correct M is the tightest value that does not exclude any feasible solution. Setting M arbitrarily large (e.g. 1,000,000) weakens the LP relaxation and makes the solver dramatically slower — the solver must explore many more branches to prove optimality.