Benders for Mixed-Integer Problems

A mixed-integer program (MIP) often contains two distinct kinds of decisions: a small set of complicating integer variables $\mathbf{y}$ (e.g., facility-open decisions, design choices) and a larger set of continuous variables $\mathbf{x}$ (e.g., shipping quantities, flows). We write such a problem in 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},\ \mathbf{y} \in Y,\end{aligned}$$

where $Y \subseteq \mathbb{Z}^p$ is the set of admissible integer values for $\mathbf{y}$.

Benders decomposition exploits this structure. Once we fix $\mathbf{y} = \hat{\mathbf{y}}$, the residual problem in $\mathbf{x}$ is a linear program -- the subproblem:

$$Q(\hat{\mathbf{y}}) \;=\; \min\ \mathbf{c}^T\mathbf{x}\quad \text{s.t.}\ A\mathbf{x} \geq \mathbf{b} - B\hat{\mathbf{y}},\ \mathbf{x} \geq \mathbf{0}.$$

The choice of $\mathbf{y}$ is delegated to the master problem, an integer program that uses an auxiliary variable $\eta$ to stand in for $Q(\mathbf{y})$:

$$\min\ \mathbf{f}^T\mathbf{y} + \eta\quad \text{s.t.}\ \mathbf{y} \in Y,\ (\text{Benders cuts}).$$

Benders alternates: solve the integer master to obtain $\hat{\mathbf{y}}$, solve the LP subproblem at $\hat{\mathbf{y}}$, and append a cut that forces $\eta$ to better approximate $Q(\mathbf{y})$. The integer search is handled only in the master; the continuous variables are handled only in the subproblem.