Lazy constraint generation

We saw in the previous part how we can solve \begin{align*} \min \ & \mathbf{c}^\mathsf{T} \mathbf{x} + \mathbf{d}^\mathsf{T} \mathbf{y} \\ (P)~~~~\text{s.t.} \ & \mathbf{A}\mathbf{x} + \mathbf{B}\mathbf{y} \geq \mathbf{b} \\ & \mathbf{x} \in \mathcal{X}, \mathbf{y} \geq \mathbf{0} \end{align*} where \(\mathbf{A} \in \mathbb{R}^{m\times n_x}\), \(\mathbf{B} \in \mathbb{R}^{m\times n_y}\), \(\mathbf{c} \in \mathbb{R}^{n_x}\), \(\mathbf{d} \in \mathbb{R}^{n_y}\), and \(\mathcal{X} \subseteq \mathbb{R}^{n_x}\) by solving \begin{align*} \min \ & \mathbf{c}^\mathsf{T} \mathbf{x} + z \\ (BP)~~~~\text{s.t.} \ & {\mathbf{r}^{i}}^\mathsf{T}\left(\mathbf{b} - \mathbf{A}\mathbf{x}\right) \leq 0, & \forall i \in \{1,\ldots,k\},\\ & {\mathbf{p}^{i}}^\mathsf{T} \left(\mathbf{b}-\mathbf{A}\mathbf{x}\right) \leq z & \forall i \in \{1,\ldots,\ell\}, \\ & \mathbf{x} \in \mathcal{X} \end{align*} where \(\mathbf{r}^{1},\ldots,\mathbf{r}^{k}\) form a complete set of extreme rays of \(\left\{\mathbf{u} : \mathbf{u}^\mathsf{T}\mathbf{B} \leq \mathbf{0},~ \mathbf{u} \geq \mathbf{0} \right\}\) and \(\mathbf{p}^{1},\ldots,\mathbf{p}^{\ell}\) are the extreme points of \(\left\{\mathbf{u} : \mathbf{u}^\mathsf{T}\mathbf{B} \leq \mathbf{d}^\mathsf{T}, ~\mathbf{u} \geq \mathbf{0} \right\}\).

We now give an iterative algorithm that solves \((BP)\) by generating the inequalities “lazily”.

Benders decomposition algorithm

Input: The problem \((P)\) with at least one optimal solution and \(\mathcal{X}\) bounded.
Steps:

1. Initialize \((M)\) to the problem \(\min \left\{ \mathbf{c}^\mathsf{T} \mathbf{x} + z : \mathbf{x} \in \mathcal{X} \right\}\).

2. Obtain an optimal solution \(\mathbf{x}^*, z^*\) to \((M)\). If the problem is unbounded, set \(z^* = -\infty\) and choose a feasible \(\mathbf{x}^*\) that minimizes \(\mathbf{c}^\mathsf{T} \mathbf{x}\).

3. Solve \begin{align*} \max \ & \mathbf{u}^\mathsf{T}\left(\mathbf{b}-\mathbf{A}\mathbf{x}^*\right) \\ \text{s.t.} \ & \mathbf{u}^\mathsf{T} \mathbf{B} \leq \mathbf{d}^\mathsf{T} \\ & \mathbf{u} \geq \mathbf{0}. \end{align*}

4. If the problem is unbounded, set \(\mathbf{u}^*\) to an extreme ray so that \({\mathbf{u}^*}^\mathsf{T} \left(\mathbf{b}-\mathbf{A}\mathbf{x}^*\right) \gt 0\), add \({\mathbf{u}^*}^\mathsf{T} \left(\mathbf{b}-\mathbf{A}\mathbf{x}\right) \leq 0 \) to \((M)\) and go to Step 2. Otherwise, if the optimal value is greater than \(z^*\), set \(\mathbf{u}^*\) to an optimal solution that is an extreme point, add \({\mathbf{u}^*}^\mathsf{T} \left(\mathbf{b}-\mathbf{A}\mathbf{x}\right) \leq z\) to \((M)\) and go to Step 2.

5. Let \(\mathbf{y}^*\) be a solution to \begin{align*} \mathbf{d}^\mathsf{T}\mathbf{y} & = z^* \\ \mathbf{B}\mathbf{y} & \geq \mathbf{b} - \mathbf{A}\mathbf{x}^* \\ \mathbf{y} & \geq \mathbf{0} \end{align*} and return \(\mathbf{x}^*,\mathbf{y}^*\) as an optimal solution to \((P)\).

Remark. In step 2, there is an implicit assumption that the problem is unbounded only if there is no constraint on \(z\). This assumption certainly holds when the set \(\mathcal{X}\) is bounded. For details on relaxing the assumption on \((P)\), see p. 372 of the book Theory of Linear and Integer programming by Alexander Schrijver.

Worked example

1. Solve the problem \begin{align*} \min\quad & x_1 + 2x_2 + 3y_1 + y_2 \\ (P)~~~~\text{s.t}\quad & x_1 + x_2 + 2y_1 - y_2 \geq 3 \\ & 3x_1 - x_2 + y_1 + 2y_2 \geq 4 \\ & 0 \leq x_1, x_2 \leq 1 \\ & y_1, y_2 \geq 0. \end{align*} using Benders decomposition algorithm.

   Iteration 1:

   1. The problem \((M)\) is \(\min \left\{ x_1 + 2x_2 + z : 0 \leq x_1, x_2 \leq 1.\right\}\).

   2. The problem \((M)\) is unbounded. We set \(x^*_1 = x^*_2 = 0\) and \(z^* = -\infty\).

   3. Solve \(\max \left\{ 3u_1 + 4u_2 :~ \begin{array}{r} 2u_1 + u_2 \leq 3 \\ -u_1 +2u_2 \leq 1 \\ u_1, u_2 \geq 0\end{array} \right\}\).

   4. The problem has an extreme point optimal solution at \(\mathbf{u}^* = \begin{bmatrix} 1 \\ 1 \end{bmatrix}\). Add the cut \(\begin{bmatrix} 1 & 1 \end{bmatrix} \begin{bmatrix} 3- (x_1 + x_2)\\ 4-(3x_1-x_2)\end{bmatrix} \leq z\), or more simply, \(4x_1+z \geq 7\) to \((M)\).

   Iteration 2:

   2. The problem \((M)\) has an optimal solution at \(x^*_1 = 1\), \(x^*_2 = 0\) and \(z^* = 3\).

   3. Solve \(\max \left\{ 2u_1 + u_2 :~ \begin{array}{r} 2u_1 + u_2 \leq 3 \\ -u_1 +2u_2 \leq 1 \\ u_1, u_2 \geq 0\end{array} \right\}\).

   4. The problem has an extreme point optimal solution at \(\mathbf{u}^* = \begin{bmatrix} \frac{3}{2} \\ 0\end{bmatrix}\). Add the cut \(\begin{bmatrix} \frac{3}{2} & 0 \end{bmatrix} \begin{bmatrix} 3- (x_1 + x_2)\\ 4-(3x_1-x_2)\end{bmatrix} \leq z\), or more simply, \(3x_1+3x_2 + 2z \geq 9\) to \((M)\).

   Iteration 3:

   2. The problem \((M)\) has an optimal solution at \(x^*_1 = 1\), \(x^*_2 = 0\) and \(z^* = 3\).

   3. Solve \(\max \left\{ 2u_1 + u_2 :~ \begin{array}{r} 2u_1 + u_2 \leq 3 \\ -u_1 +2u_2 \leq 1 \\ u_1, u_2 \geq 0\end{array} \right\}\).

   4. The problem has an extreme point optimal solution at \(\mathbf{u}^* = \begin{bmatrix} \frac{3}{2} \\ 0\end{bmatrix}\) with optimal value equal to \(z^*\).

   5. Solving \begin{align*} 3 y_1 + y_2 & = 3 \\ 2y_1 - y_2 & \geq 2 \\ y_1 + 2y_2 & \geq 1 \\ y_1, y_2 & \geq 0 \end{align*} gives the solution \(\mathbf{y}^* = \begin{bmatrix} 1 \\ 0\end{bmatrix}\). Hence, \(\mathbf{x}^* = \begin{bmatrix} 1 \\ 0\end{bmatrix}\) and \(\mathbf{y}^* = \begin{bmatrix} 1 \\ 0\end{bmatrix}\) give an optimal solution to \((P)\).