Benders’ Decomposition - Textbook Algorithm

Master problem

The basic Benders’ decomposition algorithm as explained in several textbooks (e.g., [NW88], [Mar99]) works as follows. After introducing an artificial variable \(\eta = d^Ty\), the master problem relaxation becomes:

\[\begin{split}\begin{align} & \text{minimize} & & c^Tx + \eta \\ & \text{subject to} & & A x \leq b & & \\ &&& \eta \geq \overline{\eta} & & \\ &&& x \in \mathbb{Z}^n_+ & & \\ \end{align}\end{split}\]

Here \(\overline{\eta}\) is a lower bound on the variable \(\eta\) that AIMMS will automatically derive. For example, if the vector \(d\) is nonnegative then we know that 0 is a lower bound on \(d^Ty\) since we assumed that the variable \(y\) is nonnegative, and therefore we can take \(\overline{\eta} = 0\). We assume that the master problem is bounded.

Subproblem

After solving the master problem we obtain an optimal solution, denoted by \((x^*,\eta^*)\) with \(x^*\) integer. This solution is fixed in the subproblem which we denote by \(PS(x^*)\):

\[\begin{split}\begin{align} & \text{minimize} & & d^Ty \\ & \text{subject to} & & Q y \leq r - Tx^* & & \\ &&& y \in \mathbb{R}^m_+ & & \\ \end{align}\end{split}\]

Note that this subproblem is a linear programming problem in which the continuous variable \(y\) is the only variable.

Dual subproblem

Textbooks that explain Benders’ decomposition often use the dual of this subproblem because duality theory plays an important role, and the Benders’ optimality and feasibility cuts can be expressed using the variables of the dual problem. The dual of the subproblem \(PS(x^*)\) is given by:

\[\begin{split}\begin{align} & \text{maximize} & & r - \pi^T(Tx^*) \\ & \text{subject to} & & \pi^TQ \geq d^T & & \\ &&& \pi \geq 0 & & \\ \end{align}\end{split}\]

We denote this problem by \(DS(x^*)\).

Optimality cut

If this subproblem is feasible, let \(z^*\) denote the optimal objective value and \(\overline{\pi}\) an optimal solution of \(DS(x^*)\). If \(z^* \leq \eta^*\) then the current solution \((x^*,\eta^*)\) is a feasible and optimal solution of our original problem, and the Benders’ decomposition algorithm only needs to solve \(PS(x^*)\) to obtain optimal values for variable \(y\). If \(z^* > \eta^*\) then the Benders’ optimality cut \(\eta \geq \overline{\pi}^T (r - Tx)\) is added to the master problem and the algorithm continues by solving the master problem again.

Feasibility cut

If the dual subproblem is unbounded, implying that the primal subproblem is infeasible, then an unbounded extreme ray \(\overline{\pi}\) is selected and the Benders’ feasibility cut \(\overline{\pi}^T (r - Tx) \leq 0\) is added to the master problem. Modern solvers like CPLEX, Gurobi and COPT can provide an unbounded extreme ray in case a LP problem is unbounded. After adding the feasibility cut the Benders’ decomposition algorithm continues by solving the master problem.