MILP Idioms

285. MILP Idioms

285.1. MILP Modeling Idioms

Phrasebook of LP/MILP modeling idioms — small algebraic constructs that encode logic, products, piecewise terms, and other structure as linear constraints.

Network / flow
$\sum_{𝑗} 𝑥_{𝑖 𝑗} - \sum_{𝑗} 𝑥_{𝑗 𝑖} = 𝑏_{𝑖}$	conservation: $𝑏_{𝑖}$ source/sink/0
$𝑥_{𝑖 𝑗} - 𝑥_{𝑗 𝑖}$	net arc flow (single signed var)
$0 \leq 𝑥_{𝑖 𝑗} \leq 𝑢_{𝑖 𝑗}$	arc capacity
$\sum_{𝑖 \in 𝑆, 𝑗 \notin 𝑆} 𝑥_{𝑖 𝑗}$	flow across a cut
Conditional (Big-M)
$𝑎^{𝑇} 𝑥 \leq 𝑏 + 𝑀 (1 - 𝑦)$	active only if $𝑦 = 1$
$\begin{matrix} 𝑎^{𝑇} 𝑥 \leq 𝑏_{1} + 𝑀 𝑦 \\ 𝑎^{𝑇} 𝑥 \leq 𝑏_{2} + 𝑀 (1 - 𝑦) \end{matrix}$	either/or
tight $𝑀$	loose $𝑀$ ruins relaxation
Binary ↔ continuous
$𝑥 \leq 𝑀 𝑦$	fixed-charge on/off
$𝑙 𝑦 \leq 𝑥 \leq 𝑢 𝑦$	semi-continuous: 0 or $[𝑙, 𝑢]$
$𝑥 \geq 𝜀 𝑦$	force strictly positive
Binary logic
$\sum 𝑦_{𝑖} \leq 1$	at most one
$\sum 𝑦_{𝑖} = 1$	exactly one (SOS1)
$\sum 𝑦_{𝑖} \geq 1$	OR
$\begin{matrix} \sum 𝑦_{𝑖} \leq 𝑘 \\ \sum 𝑦_{𝑖} \geq 𝑘 \end{matrix}$	cardinality
$𝑦_{𝑎} \leq 𝑦_{𝑏}$	implication $𝑎 \Rightarrow 𝑏$
Products
$\begin{matrix} 𝑧 \leq 𝑦_{1} \\ 𝑧 \leq 𝑦_{2} \\ 𝑧 \geq 𝑦_{1} + 𝑦_{2} - 1 \end{matrix}$	bin × bin
$\begin{matrix} 𝑧 \leq 𝑢 𝑦 \\ 𝑧 \leq 𝑥 \\ 𝑧 \geq 𝑥 - 𝑢 (1 - 𝑦) \\ 𝑧 \geq 0 \end{matrix}$	bin × cont, $𝑥 \in [0, 𝑢]$
McCormick envelope	cont × cont relaxation
Abs / norms
$\begin{matrix} 𝑥 = 𝑥^{+} - 𝑥^{-} \\ 𝑥^{+}, 𝑥^{-} \geq 0 \end{matrix}$	$\| 𝑥 \| = 𝑥^{+} + 𝑥^{-}$ (L1)
$\begin{matrix} 𝑡 \geq 𝑥 \\ 𝑡 \geq - 𝑥 \end{matrix}$	$\| 𝑥 \|$ , epigraph
Min / max
$𝑡 \geq 𝑓_{𝑖} (𝑥) \forall 𝑖$	min $𝑡$ ⇒ minimax
$𝑡 \leq 𝑓_{𝑖} (𝑥) \forall 𝑖$	max $𝑡$ ⇒ maximin
Piecewise-linear
λ-method + SOS2	convex combo of breakpoints
δ-method	incremental encoding
Sequencing
$𝑢_{𝑖} - 𝑢_{𝑗} + 𝑛 𝑥_{𝑖 𝑗} \leq 𝑛 - 1$	MTZ subtour elim.
$𝑠_{𝑗} \geq 𝑠_{𝑖} + 𝑑_{𝑖}$	precedence
Covering family
$\sum 𝑎_{𝑖 𝑗} 𝑥_{𝑗} \geq 1$	set covering
$\sum 𝑎_{𝑖 𝑗} 𝑥_{𝑗} \leq 1$	set packing
$\sum 𝑎_{𝑖 𝑗} 𝑥_{𝑗} = 1$	partitioning
$\sum 𝑤_{𝑖} 𝑥_{𝑖} \leq 𝑊$	knapsack
Slack / deviation
$\begin{matrix} 𝑎^{𝑇} 𝑥 + 𝑠 = 𝑏 \\ 𝑠 \geq 0 \end{matrix}$	slack (≤ → =); surplus $- 𝑠$
$𝑓 (𝑥) + 𝑑^{-} - 𝑑^{+} = tgt$	goal prog. / soft
Temporal
$𝐼_{𝑡} = 𝐼_{𝑡 - 1} + 𝑝_{𝑡} - 𝑑_{𝑡}$	inventory balance
Transforms
$\sum 𝑥 = 1, 𝑥 \geq 0$	unit simplex
Charnes–Cooper	linear-fractional → LP
$𝑦_{𝑖} \geq 𝑦_{𝑖 + 1}$	symmetry breaking