Benders Decomposition: The Idea

Consider a mixed-integer linear program of the form

$$\begin{aligned}\min\quad & \mathbf{c}^T \mathbf{x} + \mathbf{f}^T \mathbf{y} \\ \text{s.t.}\quad & A\mathbf{x} + B\mathbf{y} \geq \mathbf{b} \\ & \mathbf{x} \geq \mathbf{0},\quad \mathbf{y} \in Y, \end{aligned}$$

where $Y$ encodes restrictions on $\mathbf{y}$ that make the joint problem hard (e.g. integrality). The variables $\mathbf{y}$ are called the complicating variables: once we fix them to a specific value $\bar{\mathbf{y}},$ what remains in $\mathbf{x}$ is just a linear program.

Benders decomposition exploits this structure by alternating between two pieces:

• A master problem that proposes a value $\bar{\mathbf{y}}$ for the complicating variables.
• A subproblem that, given $\bar{\mathbf{y}},$ solves the LP

$$SP(\bar{\mathbf{y}}):\quad \min_{\mathbf{x} \geq \mathbf{0}}\ \mathbf{c}^T \mathbf{x} \quad \text{s.t.}\quad A\mathbf{x} \geq \mathbf{b} - B\bar{\mathbf{y}}$$

and sends information back to the master in the form of a cut — a linear inequality in $\mathbf{y}$ (and one auxiliary variable).

The key idea: rather than optimizing $\mathbf{x}$ and $\mathbf{y}$ jointly, we drive $\bar{\mathbf{y}}$ through a sequence of master solutions, each refined by the cut produced from the previous subproblem. The master sees a progressively better approximation of the subproblem's value as a function of $\mathbf{y}.$