bigM

Big-M is a modeling technique used in linear and mixed-integer programming to handle conditional constraints and disjunctive logic by introducing a sufficiently large constant M and binary variables. It allows constraints to be activated or deactivated depending on the value of a binary variable, enabling the representation of logical choices within a linear framework.

A common construction uses binary y in {0,1} and a pair of inequalities such as:

x ≤ b + M(1 − y)

x ≥ a − M(1 − y)

When y = 1, these inequalities enforce a ≤ x ≤ b; when y = 0, the right-hand sides become large enough (assuming M is large) to relax the constraint and effectively remove it from consideration. Similar patterns can deactivate or activate other bounds or linear relations.

Big-M is also used to model disjunctive constraints, where one of several condition sets must hold. By coupling each set with a binary indicator and suitable M terms, the problem can be expressed entirely with linear inequalities and binaries.

Numerical considerations are important: M should be as small as possible while remaining feasible, because overly large M can lead to weak linear programming relaxations and numerical instability. If bounds are known, they should be used to derive tight M values. Modern solvers sometimes offer indicator constraints or disjunctive programming formulations that can achieve similar effects with better numerical properties.

See also: linearization of products with binaries, disjunctive programming, indicator constraints, MILP.