Big-M, indicators, logical "or" — the patterns that turn intent into MILP.
Chapter: 0b — MIP theory · lesson id mip-modelling · theory lesson
A linear program can only directly express linear constraints. But real problems come with "if $y = 0$ then $x = 0$", "at most three of these binaries can be 1", "either A or B but not both". The MIP modelling toolkit is how those non-linear-looking requirements get translated into clean linear inequalities. Pick the right pattern and your solver flies; pick the wrong one and a problem that should solve in seconds takes hours.
You want: $y = 0 \Rightarrow x = 0$, where $y \in {0, 1}$ and $x \geq 0$. Equivalently, $x$ can only be non-zero when the switch $y$ is on. Pick an upper bound $M$ that you know $x$ never exceeds, and write:
$$ x ;\leq; M \cdot y $$
When $y = 0$, the constraint forces $x \leq 0$, and combined with $x \geq 0$ this pins $x = 0$. When $y = 1$, the constraint says $x \leq M$, which is the default upper bound and lets $x$ float anywhere up to it.
Choose $M$ as $small$ as possible. A loose $M$ is harmless for feasibility but ruins the LP relaxation: a continuous $y = 0.001$ allows $x = 0.001 M$, which is large when $M$ is large. Loose $M$s mean loose relaxations mean long solves. If you know $x$ never exceeds $50$, write $x \leq 50 y$, not $x \leq 10{,}000 y$.
You want $at\ least\ one$ of two constraints to hold: $a^{\top} x \geq \beta_{1}$ $or$ $a^{\top} x \geq \beta_{2}$ (a "logical or" — both can hold at the same time, but at least one must). Introduce a binary $z \in {0, 1}$ and large $M_{1}, M_{2}$:
$$ a^{\top} x + M_{1} z ;\geq; \beta_{1} \qquad a^{\top} x + M_{2} (1 - z) ;\geq; \beta_{2} $$
When $z = 0$ the first constraint is forced active, the second is relaxed (the $M_{2}$ term swallows any deficit). When $z = 1$, the opposite. So whichever value of $z$ the solver picks, at least one of the two original constraints is enforced. The solver picks whichever branch costs less.
If you really want $exclusive$ or (exactly one of the two, never both), the big-M trick alone is not enough. You need an extra constraint that forbids the unselected branch from holding, which is in general non-linear. The "exactly one" case shows up rarely in practice; "at least one" is what most disjunctive constraints actually mean.
Major commercial solvers (CPLEX, Gurobi) support $native$ indicator constraints: write $y = 1 \Rightarrow a^{\top} x \leq \beta$ directly, no $M$ required. Open-source solvers vary — some have partial support, others none — so check yours before relying on them. Indicators are tighter than big-M because the solver can use specialised propagation. When your solver supports them, prefer indicators over big-M; when it does not, fall back to big-M and pick the tightest $M$ you can prove.
For a set $S$ of binaries, "at most $k$ are 1" is $\sum_{i \in S} y_{i} \leq k$, and "exactly one is 1" is $\sum_{i \in S} y_{i} = 1$. A related but distinct construct is the $special$-$ordered$-$set\ of\ type\ 1$ (SOS1): a set of variables — not necessarily binary — of which $at\ most\ one$ may be non-zero. A solver enforces an SOS1 by branching on the set directly rather than through a $\sum = 1$ constraint, so the two are not interchangeable. SOS2 — at most two $adjacent$ variables non-zero — encodes piecewise-linear functions and is supported natively in most solvers.
Quick check. You need: "if $y = 1$ then $x \geq -3$", where $y \in {0, 1}$, $x$ is free, and $x$ has known bounds $[-100, 100]$. Which big-M formulation is correct?
A shortcut that only works for $non$-$negative$ thresholds with $x \geq 0$ variables: "$x \geq L \cdot y$" enforces "$y = 1 \Rightarrow x \geq L$" without an extra $M$, because $y = 0$ just gives $x \geq 0$ which is already part of the model. For any other case — negative thresholds, variables that can go negative — the general $L + M(y - 1)$ pattern is the safe choice.
$\min |x|$ is not linear. But if you can split $x$ into a non-negative part $x^{+}$ and a non-positive part $x^{-}$ — say $x = x^{+} - x^{-}$ with both $\geq 0$ — and minimise $x^{+} + x^{-}$, you get the same thing. This works because at the optimum at most one of $x^{+}, x^{-}$ is non-zero (otherwise you could reduce both by a constant and lower the objective).
A similar trick handles $\min \max_{i} f_{i}(x)$: introduce $t$ and rewrite as $\min t$ s.t. $t \geq f_{i}(x)$ for each $i$. The reformulation is linear if each $f_{i}$ is.
Recap.
Read this through MCP: read with path: "lessons/mip-modelling", or resource hlpl://lessons/mip-modelling.