Decomposition Methods for Mixed-Integer Linear Programs

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 article gives an approachable introduction to three classic decomposition methods for exploiting that structure: Lagrangian relaxation, Dantzig–Wolfe decomposition, and Benders decomposition. The article uses a small activation-and-assignment model as a running example and examines it through three lenses. Lagrangian relaxation coordinates with prices by relaxing global coupling constraints and moving them into the objective. Dantzig–Wolfe decomposition coordinates with columns by packaging local feasible plans into patterns and letting a master linear program choose among them. Benders decomposition coordinates with cuts by separating strategic integer decisions from operational subproblem responses. The goal is to make the relationships among these methods concrete: why they exist, how they work, what kinds of bounds they provide, and when each method feels natural. The article is intended for readers with some background in linear or integer programming who want a more intuitive structural understanding of decomposition methods.