Benders Optimality and Feasibility Cuts

Benders decomposition attacks the mixed-integer problem

$$\min_{x,y}\ c^T x + f^T y \quad \text{s.t.}\quad Ax + By \ge b,\ x \ge 0,\ y \in Y$$

by fixing the complicating variables $y$ and solving a linear subproblem in $x$:

$$\text{SP}(y):\ \min_x\ c^T x \quad \text{s.t.}\ Ax \ge b - By,\ x \ge 0.$$

Its LP dual is

$$\text{DSP}(y):\ \max_u\ u^T(b - By) \quad \text{s.t.}\ A^T u \le c,\ u \ge 0.$$

The dual feasible region $U=\{u : A^T u \le c,\ u \ge 0\}$ does not depend on $y$; only the dual objective does. Let its extreme points be $u^1,\dots,u^K$ and its extreme rays be $r^1,\dots,r^J$.

When $\text{SP}(y)$ is feasible and bounded, the optimum of DSP$(y)$ is attained at some extreme point $u^*$, and by strong duality the subproblem optimum equals $(u^*)^T(b - By)$.

Introducing a master variable $\eta$ to stand for the subproblem cost yields an optimality cut:

$$\eta \ge (u^*)^T(b - By).$$

This is a linear inequality in $(y, \eta)$ that the master problem must satisfy.

Tiny example. With $b = \begin{bmatrix}4\\2\end{bmatrix}$, $B = I$, and $u^* = \begin{bmatrix}3\\1\end{bmatrix}$,

$$(u^*)^T(b - By) = 3(4 - y_1) + 1(2 - y_2) = 14 - 3y_1 - y_2,$$

so the optimality cut is $\eta \ge 14 - 3y_1 - y_2$.