3.1 Benders for Standard MILP

According to wikipedia:

Benders decomposition (or Benders’ decomposition) is a technique in mathematical programming that allows the solution of very large linear programming problems that have a special block structure. This block structure often occurs in applications such as stochastic programming as the uncertainty is usually represented with scenarios. The technique is named after Jacques F. Benders.

For standard MILP, get rid of \(\mathbf{x}\), we get:

\[ \begin{align} \min \quad & \mathbf{f} ^ { T } \mathbf{y} + g ( y ) \\ \text{s.t.} \quad& \mathbf{y} \in Y \end{align} \]

and

\[ \begin{align} g(y) = \min \quad& \mathbf{c}^{T} \mathbf{x} \\ \text{s.t.} \quad& \mathbf{A} \mathbf{x} \geq \mathbf{b} - \mathbf{B} \overline{\mathbf{y}} \\ & \mathbf{x} \geq 0 \end{align} \]

The dual function of \(g(y)\):

\[ \begin{align} g_d(y) = \max \quad & (\mathbf{b} - \mathbf{B}\overline{\mathbf{y}})^{T} \mathbf{u} \\ \text{s.t.} \quad& \mathbf{A}^{T} \mathbf{u} \leq \mathbf{c} \\ & \mathbf{u} \geq 0 \end{align} \]

where the constraints of the dual \(g(y)\) does not contain any \(\mathbf{y}\) values. Hence we can now analyze the feasibility of the model without considering the value of \(\mathbf{y}\).

Given the Minkovsky Fication theorem, we can hence reformulate the dual \(g(y)\) LP program as extreme points \(u^p\) and extreme rays \(u^r\). Assume that we enumerate all the extreme points and extreme rays, we can reformulate: \[ \begin{align} u & = \sum _ { i } \lambda _ { i } ^ { p } \cdot u _ { i } ^ { P } + \sum _ { j } \lambda _ { j } ^ { r } \cdot u _ { j } ^ { r } \\ \sum _ { i } \lambda _ { i } ^ { p } &= 1 \\ \lambda _ { i } ^ { p } , \lambda _ { j } ^ { r } & \geq 0 \end{align} \]

\(g_d(y)\) can be expressed to: \[ \begin{align} g_{\text{dual}}(y) = \max \quad& (\mathbf{b} - \mathbf{B}\overline{\mathbf{y}})^{T} \mathbf{u} \\ \text{s.t.} \quad& u = \sum _ { i } \lambda _ { i } ^ { p } \cdot u _ { i } ^ { p } + \sum _ { j } \lambda _ { j } ^ { r } \cdot u _ { j } ^ { r } \\ & \sum _ { i } \lambda _ { i } ^ { p } = 1 \\ & \lambda _ { i } ^ { p } , \lambda _ { j } ^ { r } \geq 0 \\ & \mathbf{u} \geq 0 \end{align} \]

Substitute the \(u\) variables with the extreme points and extreme rays (and multiply \((b − By)\) into the sum’s): \[ \begin{align} g_{\text{dual}}(y) = \max \quad& ( b - B \overline { y } ) ^ { T } \times \sum _ { i } \lambda _ { i } ^ { p } \cdot u _ { i } ^ { p } + ( b - B \overline { y } ) ^ { T } \times \sum _ { j } \lambda _ { j } ^ { r } \cdot u _ { j } ^ { r } \\ \text{s.t.} \quad& \sum _ { i } \lambda _ { i } ^ { p } = 1 \\ & \lambda _ { i } ^ { p } , \lambda _ { j } ^ { r } \geq 0 \end{align} \]

If we select a \(y\) such that just one term \((b - B\overline{y})^T u_j^r\) becomes positive, i.e. \((b - B\overline{y})^T u_j^r > 0\) then the LP is unbounded because there are no limits on the \(\lambda_j^r\). Hence in order not to get an unbounded dual \(g(y)\) function corresponding to not getting an infeasible \(g(y)\) we have to ensure that this does not happen for any extreme ray.

If an optimal solution exists (i.e. the polyhedron is not un-bounded or infeasible), at least one optimal solution to the dual \(g(y)\) function is a corner point \(u_i^p\). Hence the dual \(g(y)\) function has the value of the maximal point. We need to find the corner point

Let’s ensure feasibility and add the value of the maximal point: \[ \begin{align} \min \quad& q \\ \text{s.t.} \quad& \overline { u _ { j } ^ { r } } \cdot ( b - B y ) \leq 0 \quad \forall j \\ & \overline { u _ { i } ^ { p } } \cdot ( b - B y ) \leq q \quad \forall i \\ & y \in Y , q \in R \end{align} \]

The above problem becomes the so-called Benders Master Problem (BMP): \[ \begin{align} \min \quad& \mathbf{f}^{T} \mathbf{y} + q \\ \text{s.t.} \quad& \mathbf{\overline {u_{j}^{r}}} (\mathbf{b} - \mathbf{B} \mathbf{y} ) \leq 0 \quad \forall j \\ & \mathbf{\overline {u_{i}^{p}}} (\mathbf{b} - \mathbf{B} \mathbf{y} ) \leq q \quad \forall i \\ & y \in Y \\ & q \in R \end{align} \]

3.1.1 Cutting Planes

We can consider the Bender’s algorithm as a cutting plane algorithm: We know there is an exponential amount of cuts, but we only generate them when needed … by solving the Benders Sub Problem (BSP): \[ \begin{align} \max \quad& (\mathbf{b} - \mathbf{B} \mathbf{\overline{y}})^{T} \mathbf{u} \\ \text{s.t.} \quad& \mathbf{A}^{T} \mathbf{u} \leq \mathbf{c} \\ & \mathbf{u} \geq \mathbf{0} \end{align} \] We use the BSP problem to find the extreme points \(\overline{u_i^p}\). These we use to generate the so-called optimality cuts.

To generate the so-called feasibility cuts, we need to be able to find extreme rays, i.e. if the BSP is un-bounded when we try to solve it, we need to find one extreme ray of that problem. This we will deal with next week. For now (in the exercises) we will assume that the BSP is NOT un-bounded.

3.1.2 Benders Algorithm

Write up the MASTER-PROBLEM, without any constraints: \[ \begin{align} \min \quad& z_{MAS} = q + f ^ { T } y \\ \text{s.t.} \quad& y \in Y \\ & q , z_{MAS} \in R \end{align} \] Actually, if there are constraints in the original problem with only \(y\) variables, then these constraints can and should stay.

Assume the \(y\) variables are fixed. Move the (now) \(y\) constants to the right hand side and dualize the problem. This is the SUB-PROBLEM: \[ \begin{align} \max \quad & z_{SUB} = ( b - B \overline { y } ) ^ { T } u \\ \text{s.t.} \quad & A ^ { T } u \leq c \\ & u \geq 0 \\ & z_{SUB} \in R \end{align} \]

The BSP is the dual of the following model: \[ \begin{align} \min \quad& c^T x \\ \text{s.t.} \quad& A x \geq b - B \overline{y} \\ & x \geq 0 \end{align} \] But this model is the original problem and if we add \(f^T \overline{y}\) to the value, then it is a feasible solution to the original problem, hence a legal upper bound.

The \(z_{LOW}\) bound is the optimal value of the BMP: \[ \begin{align} \min \quad& z_{LOW} = z_{MAS} = q + f ^ { T } y \\ \quad& \overline { u _ { j } ^ { r } } \cdot ( b - B y ) \leq 0 \quad \forall j \\ & \overline { u _ { i } ^ { p } } \cdot ( b - B y ) \leq q \quad \forall i \\ & y \in Y , q \in R \end{align} \] Notice that during the Benders algorithm the relaxed problem is solved (not all constraints are there). Hence a feasible lower bound.

If the Benders sub-problem is un-bounded, then the original problem, changed by the chosen y variables, is in-feasible. Hence we add a constraint to the Benders master problem, the feasibility constraint, which makes such a choice of y variable values impossible.

To find the extreme rays, we first insert 0 on the right-hand side.

Benders’ Sub Problem

\[ \begin{align} g_d(y) = \max \quad& (\mathbf{b} - \mathbf{B}\overline{\mathbf{y}})^{T} \mathbf{u} \\ \text{s.t.} \quad& \mathbf{A}^{T} \mathbf{u} \leq \mathbf{c} \\ & \mathbf{u} \geq 0 \end{align} \]

Then, we set dummy:

\[ \begin{align} g_d(y) = \max \quad & dummy \\ \text{s.t.} \quad & dummy = 1 \\ & (\mathbf{b} - \mathbf{B}\overline{\mathbf{y}})^{T} \mathbf{u} = 1\\ & \mathbf{A}^{T} \mathbf{u} \leq 0 \\ & \mathbf{u} \geq 0 \end{align} \]

3.1.3 Simple Illustration

\[ \begin{align} \min \quad& z_0 = 5 x - 3 y \\ \text{s.t.} \quad& x + 2 y \geq 4 \\ & 2 x - y \geq 0 \\ & x - 3 y \geq - 13 \\ & x \geq 0 \\ & y \in \{ 0,1 , \ldots , 10 \} \end{align} \]

In standard form:

\[ \begin{align} \min \quad& \mathbf{c}^{T} \mathbf{x} + \mathbf{f} ^ { T } \mathbf{y} \\ \text{s.t.} \quad& \mathbf{A} \mathbf{x} + \mathbf{B} \mathbf{y} \geq \mathbf{b} \\ & \mathbf{y} \in Y \\ & \mathbf{x} \geq 0 \end{align} \]

where

\[ \begin{align} \mathbf{c} &= (5)^T \\ \mathbf{f} &= (-3)^T \\ \mathbf{b} &= (4, 0, -13)^T \\ \mathbf{x} &= (x)^T \\ \mathbf{y} &= (y)^T \\ \mathbf{A} &= \left(\begin{array}{c} 1 \\ 2 \\ 1 \end{array} \right) \\ \mathbf{B} &= \left(\begin{array}{c} 2 \\ -1 \\ -3 \end{array} \right) \end{align} \]

Move the \(y\) constants to the right hand side of the constraints. \[ \begin{align} \min \quad & 5 x - 3 \overline{y} \\ \text{s.t.} \quad & x \geq 4 - 2 \overline{y} \\ & 2 x \geq \overline{y} \\ & x \geq 3 \overline{y} - 13 \\ & x \geq 0 \end{align} \]

Dualize the model (we need to find the u values, keeping the \(y\) constants in the in the objective. This is the Benders Sub Problem: \[ \begin{align} OBJ_{SUB} = \max \quad& (4 - 2 \overline{y}) u_1 + \overline{y} u_2 + (3 \overline{y} - 13) u_3 \\ \text{s.t.} \quad& u_1 + 2 u_2 + u_3 \leq 5 \\ & u_1, u_2, u_3 \geq 0 \end{align} \]

\[ \begin{align} UB = \min \left(OBJ_{SUB} - 3 \overline{y}, UB \right) \end{align} \]

\[ \begin{align} OBJ_{MAS} = \min \quad& - 3 y + q \\ \text{s.t.} \quad& (4 - 2 y) \overline{u_1} + y \overline{u_2} + (3 y - 13) \overline{u_3} \leq q \quad \forall p \\ & y \in T \\ & q \in R \end{align} \]

\[ \begin{align} LB = \max(OBJ_{MAS}, LB) \end{align} \]

Now we are ready to execute the algorithm:

• Assign initial bounds \(UB = +\infty\), \(LB = -\infty\) and \(\epsilon = a\) small number
• Assign inital \(\overline{y}\) value (possibly randomly)
• Set in the fixed \(\overline{y}\) into the Benders sub-problem and solve the Benders sub-problem to get the extreme point \(\overline{u}\) and \(OBJ_{SUB}\).
• Calculate the upper-bound: \(UB = \min \left(OBJ_{SUB} - 3 \overline{y}\right)\)
• Add new constraint \(\sum _ { i } \left( b _ { i } - \sum _ { k } B _ { k } ^ { i } \cdot y _ { k } \right) \overline { u _ { i } } \leq q\) to the Benders master-problem.
• Solve the Benders master-problem to get new y values.
• Calculate the lower-bound: \(LB = OBJ_{MAS}\).
• Terminate if \(U B - L B \leq \epsilon\)
• Go to 3 (with the new value for \(y\))

3.1.4 Simple Illustration 2

\[ \begin{align} \min \quad & 5 x_1 + 3 x_2 - 3 y_1 + y_2 \\ \text{s.t.} \quad & x_1 + 3 x_2 + 2 y_1 - 4 y_2 \geq 4 \\ & 2 x_1 + x_2 - y_1 + 2 y_2 \geq 0 \\ & x_1 - 5 x_2 - 3 y_1 + y_2 \geq-13 \\ & x_1, x_2 \geq 0 \\ & y_1, y_2 \in \{0, 1, 2, ..., 10 \} \end{align} \]

which can be transformed into standard form:

\[ \begin{align} \mathbf{c} &= (5, 3)^T \\ \mathbf{f} &= (-3, 1)^T \\ \mathbf{b} &= (4, 0, -13)^T \\ \mathbf{x} &= (x_1, x_2)^T \\ \mathbf{y} &= (y_1, y_2)^T \\ \mathbf{A} &= \left(\begin{array}{c} 1 & 3\\ 2 & 1 \\ 1 & -5 \end{array} \right) \\ \mathbf{B} &= \left(\begin{array}{c} 2 & -4 \\ -1 & 2 \\ -3 & 1 \end{array} \right) \end{align} \]

3.1.5 Benders Algorithm for Problems with Extreme Rays

\[ \begin{align} \min \quad & 2 x_{1} + 6 x_{2} + 2 y_{1} + 3 y_{2} \\ \text{s.t.} \quad & - x_{1} + 2 x_{2} + 3 y_{1} - y_{2} \geq 5 \\ & x_{1} - 3 x_{2} + 2 y_{1} + 2 y_{2} \geq 4 \\ & x_{1}, x_{2} \geq 0 \\ & y_{1}, y_{2} \in \{0, 1, 2 \} \end{align} \] which can be transformed into standard form:

\[ \begin{align} \mathbf{c} &= (2, 6)^T \\ \mathbf{f} &= (2, 3)^T \\ \mathbf{b} &= (5, 4)^T \\ \mathbf{x} &= (x_1, x_2)^T \\ \mathbf{y} &= (y_1, y_2)^T \\ \mathbf{A} &= \left(\begin{array}{c} -1 & 2 \\ 1 & -3 \end{array} \right) \\ \mathbf{B} &= \left(\begin{array}{c} 3 & -1 \\ 2 & 2 \end{array} \right) \end{align} \]