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”.
Input: The problem \((P)\) with at least one optimal solution
and \(\mathcal{X}\) bounded.
Steps:
Initialize \((M)\) to the problem \(\min \left\{ \mathbf{c}^\mathsf{T} \mathbf{x} + z : \mathbf{x} \in \mathcal{X} \right\}\).
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}\).
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*}
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.
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.
Example. Consider the problem \begin{align*} \min\quad & x_1 - 5x_2 + 3y \\ (P)~~~~\text{s.t}\quad & 2x_1 + x_2 + y \geq 5 \\ & 3x_1 - x_2 - y \geq 3 \\ & 1 \leq x_1 \leq 2 \\ & 0 \leq x_2 \leq 1 \\ & y \geq 0. \end{align*} We apply the above algorithm with \(\mathbf{A} = \begin{bmatrix} 2 & 1 \\ 3 & -1 \end{bmatrix}\), \(\mathbf{B} = \begin{bmatrix} 1 \\ -1 \end{bmatrix}\), \(\mathbf{b} = \begin{bmatrix} 5 \\ 3 \end{bmatrix}\), \(\mathbf{c} = \begin{bmatrix} 1 \\ 5 \end{bmatrix}\), \(\mathbf{d} = \begin{bmatrix} 3 \end{bmatrix}\), and \(\mathcal{X} = \left\{ \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} : 1 \leq x_1 \leq 2,\ 0 \leq x_2 \leq 1 \right\}\).
Iteration 1:
The problem \((M)\) is \(\min \left\{ x_1 - 5x_2 + z : 1 \leq x_1 \leq 2,\ 0 \leq x_2 \leq 1.\right\}\).
The problem \((M)\) is unbounded. We set \(z^* = -\infty\) and \(x^*_1 = x^*_2 = 1\).
Solve \(\max \left\{ 2u_1 + u_2 : u_1 - u_2 \leq 3, \ u_1, u_2 \geq 0 \right\}\).
The problem is unbounded. With the extreme ray \(\mathbf{u}^* = \begin{bmatrix} 0 \\ 1 \end{bmatrix}\), we add the cut \(\begin{bmatrix} 0 & 1 \end{bmatrix} \begin{bmatrix} 5- (2x_1 + x_2)\\ 3-(3x_1-x_2)\end{bmatrix} \leq 0\), or more simply, \(3x_1 -x_2 \geq 3\) to \((M)\).
The problem \((M)\) is unbounded. We set \(z^* = -\infty\), \(x^*_1 = \frac{4}{3}\), and \(x^*_2 = 1\).
Solve \(\max \left\{ \frac{4}{3}u_1 : u_1 - u_2 \leq 3, \ u_1, u_2 \geq 0 \right\}\).
The problem is unbounded. With the extreme ray \(\mathbf{u}^* = \begin{bmatrix} 1 \\ 1 \end{bmatrix}\), we add the cut \(\begin{bmatrix} 1 & 1 \end{bmatrix} \begin{bmatrix} 5- (2x_1 + x_2)\\ 3-(3x_1-x_2)\end{bmatrix} \leq 0\), or more simply, \(5x_1 \geq 8\) to \((M)\).
The problem \((M)\) is unbounded. We set \(z^* = -\infty\), \(x^*_1 = \frac{8}{5}\), and \(x^*_2 = 1\).
Solve \(\max \left\{ \frac{4}{5}u_1 - \frac{4}{5}u_2 : u_1 - u_2 \leq 3, \ u_1, u_2 \geq 0 \right\}\).
The problem \((M)\) has an extreme point optimal solution at \(\mathbf{u}^* = \begin{bmatrix} 3 \\ 0\end{bmatrix}\). We add the cut \(\begin{bmatrix} 3 & 0 \end{bmatrix} \begin{bmatrix} 5- (2x_1 + x_2)\\ 3-(3x_1-x_2)\end{bmatrix} \leq z\), or more simply, \(6x_1 + 3x_2 + z \geq 15\) to \((M)\).
The problem \((M)\) has an optimal solution at \(x^*_1 = 2\), \(x^*_2 = 1\) and \(z^* = 0\).
Solve \(\max \left\{ - 2u_2 : u_1 - u_2 \leq 3, \ u_1, u_2 \geq 0 \right\}\).
The problem has optimal value equal to \(z^*\).
Solving \begin{align*} 3 y & = 0 \\ y & \geq 0 \\ -y & \geq -2 \\ y & \geq 0 \end{align*} gives the solution \(y^* = 0\). Hence, \(\begin{bmatrix} x^*_1 \\ x^*_2 \\ y^* \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \\ 0\end{bmatrix}\) is an optimal solution to \((P)\).
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.