Decomposition Methods for Mixed-Integer Linear Programs
Lagrangian relaxation, Dantzig–Wolfe decomposition, and Benders decomposition, developed side by side on one activation-and-assignment model. Published technical note.
Abstract
Many hard mixed-integer linear programs are hard not because every local decision is difficult, but because a relatively small number of global constraints force those local decisions to coordinate. This note introduces the three classical decomposition techniques that exploit that structure — Lagrangian relaxation, Dantzig–Wolfe decomposition, and Benders decomposition — developing each one on the same activation-and-assignment model so their mechanics and trade-offs can be compared directly.