Classical Benders Decomposition

Original Problem

The Benders decomposition [1] is applied to MILPs or other problems that have a mix of “difficult” and “easy” variables. The difficult variable, namely “complicating variables”, are variables that, if their values were fixed, would make the rest of the problem much easier to solve. The canonical example is a problem with both integer variables and continuous variables. Consider the following MILP

\[\begin{split}\begin{aligned} \min_{x, y} \quad & c^T x + f^T y \\ \text{s.t.} \quad & Ax + By \geq b \\ & x \in X \\ & y \in Y \end{aligned}\end{split}\]

where \(x \geq 0\) are the complicating (e.g., integer) variables and \(y \geq 0\) are the easy (continuous) variables. The key insight is that if \(x\) is fixed to a specific value \(\bar{x}\), the remaining problem in becomes a simple pure LP, which is easy to solve. The Benders Decomposition method reformulates the problem into master problem and subproblem based on the complicating and easy variables. Benders cuts are then generated from the subproblem and added to the master problem to iteratively refine the solution.

Reformulation

The master problem works only with the complicating variables \(x\). Its goal is to find the best possible values for \(x\) by considering the overall objective function. It approximates the impact of the \(y\) variables using a single variable \(\eta\), which represents the optimal cost of the subproblem. The master problem with iteratively added constraints, known as Benders cuts (optimality cuts and feasibility cuts), is as follows.

\[\begin{split}\begin{aligned} \min_{x, \eta} \quad & c^T x + \eta \\ \text{s.t.} \quad & x \in X \\ & \eta \geq \dots (\text{optimality cuts}) \\ & 0 \geq \dots (\text{feasibility cuts}) \\ & -\infty < \eta < +\infty \end{aligned}\end{split}\]

Once the master problem proposes a candidate solution \(\bar{x}\), the subproblem is solved to find the optimal values of \(y\) for that fixed \(\bar{x}\). The primal subproblem for a given \(\bar{x}\) is as follows.

\[\begin{split}\begin{aligned} \min_{y} \quad & f^T y \\ \text{s.t.} \quad & By \geq b - A \bar{x} \\ & y \in Y \end{aligned}\end{split}\]

This is a pure LP. However, the information we need for the Benders cuts comes from its dual. The dual subproblem is as follows.

\[\begin{split}\begin{aligned} \max_{\pi} \quad & \pi^T (b - A \bar{x}) \\ \text{s.t.} \quad & B^T \pi \leq f \\ & \pi \geq 0 \end{aligned}\end{split}\]

Solving this dual subproblem has two possible outcomes that are crucial for the algorithm:

  1. Finite optimal: The dual problem has an optimal solution \(\bar{\pi}\). By strong duality, this means the primal subproblem is feasible and has an optimal solution. This outcome leads to a Benders Optimality Cut, formulated based on \(\bar{\pi}\).

  2. Unbounded: The dual problem is unbounded. By the weak duality theorem, this implies that the primal subproblem is infeasible. This outcome leads to a Benders Feasibility Cut, formulated based on an extreme ray of the dual feasible region.

Tip

One do not need to explicitly formulate the dual subproblem, since modern LP solvers can provide the dual values (for optimality cuts) or extreme rays (for feasibility cuts) directly when solving the primal subproblem.

Benders Cuts

Benders cuts are the constraints added back to the master problem to inform it about the consequences of choosing a particular .

Optimality Cut

  • When is it generated? When the subproblem is feasible for a given \(\bar{x}\), yielding an optimal dual solution \(\bar{\pi}\).

  • What is the logic? The optimal cost of the subproblem for \(\bar{x}\) is \(\bar{\pi}^T (b - A \bar{x})\). The master problem’s variable \(\eta\) must be at least this large. We can generalize this for any \((x, \eta)\) pair to create a valid cut that constrains \(\eta\).

  • The Cut: We add the following linear constraint to the master problem.

    \[\eta \geq \bar{\pi}^T (b - A x)\]

Note

  • This cut tells the master problem: “For any future choice of \(x\), the cost of the corresponding subproblem \(\eta\) will be at least \(\bar{\pi}^T (b - A x)\).”

  • It can also be seen as a first-order Taylor approximation (or linearization) of \(\eta\) around \(\bar{x}\), since the cut is equivalent to

    \[\eta \geq \bar{\pi}^T (b - A \bar{x}) - \bar{\pi}^T A (x - \bar{x})\]

    where \(\bar{\pi}^T (b - A \bar{x}) = f^T \bar{y}\) (strong duality) is the optimal value of the subproblem at \(\bar{x}\), and \(-\bar{\pi}^T A\) is the gradient of the optimal value function \(\eta\) with respect to \(x\).

  • The former form is more generally used in practice, as it does not require storing \(\bar{x}\).

Feasibility Cut

  • When is it generated? When the subproblem is infeasible for a given \(\bar{x}\). This corresponds to the dual subproblem being unbounded.

  • What is the logic? If the dual is unbounded, we can find an extreme ray \(\bar{r}\) of the dual feasible region. An extreme ray is a direction in which the dual objective can increase indefinitely. The condition for the dual being unbounded for \(\bar{x}\) is \(\bar{r}^T (b - A \bar{x}) > 0\). To prevent future choices of \(x\) from causing the same infeasibility, we must enforce the opposite.

  • The Cut: We add the following linear constraint to the master problem.

    \[0 \geq \bar{r}^T (b - A x)\]

Note

  • This cut tells the master problem: “The choice \(\bar{x}\) was invalid because it made the subproblem impossible to solve. This constraint cuts off solutions similar to \(\bar{x}\).”

  • An extreme ray is a certificate of infeasibility. Its existence is guaranteed by Farkas’ Lemma, and it can be obtained directly from LP solvers when they declare a problem to be infeasible.

  • Farkas’ Lemma: For the matrices \(A, B\) and vectors \(b, \bar{x}\), exactly one of the following statements is true:

    1. (feasible subproblem) There exists a \(y \geq 0\) such that \(B y = b - A\bar{x}\).

    2. (infeasible subproblem) There exists a \(r \in \mathbb{R}\) such that \(B^T r \leq 0\) and \(r^T(b - A\bar{x}) > 0\).

Algorithm

The algorithm is an iterative process that alternates between solving the master problem, solving the subproblem, and adding Benders cuts to the master problem based on the subproblem’s results.

  1. Initialization

    • Initialize a lower bound \(LB = -\infty\) and an upper bound \(UB = +\infty\).

    • Add any initial cuts to the master problem if available. Often, the algorithm starts with no cuts.

    • Set the iteration counter \(k = 1\).

  2. Step 1: Solve the master problem

    • Solve the current master problem to get a solution \((\bar{x}_k, \bar{\eta}_k)\).

    • The objective value of the master problem, \(c^T \bar{x}_k + \bar{\eta}_k\), is a valid lower bound on the optimal solution of the original problem. Update \(LB = \max(LB, c^T \bar{x}_k + \bar{\eta}_k)\).

  3. Step 2: Check for convergence

    • If \(UB - LB \leq \epsilon\) (where \(\epsilon\) is a small tolerance), then STOP. The optimal solution has been found within the desired tolerance. The best solution found so far that yielded a feasible subproblem is the optimal solution.

  4. Step 3: Solve the subproblem

    • Using the fixed value \(\bar{x}_k\) from the master problem, solve the (dual) subproblem.

  5. Step 4: Generate and add a cut

    • Case A: subproblem is feasible (dual is bounded).

      • The sub problem objective value is \(f^T \bar{y}_k = \bar{\pi}^T_k (b - A \bar{x}_k)\).

      • The objective value for this feasible solution is \(c^T \bar{x}_k + f^T \bar{y}_k\).

      • Update the upper bound by \(UB = \min(UB, c^T \bar{x}_k + f^T \bar{y}_k)\).

      • Add a Benders optimality cut to the master problem for lower bounding \(\eta\).

    Caution

    • For \(-\infty < \eta < +\infty\) introduced in the master problem for optimality cuts, \(\infty\) should be replaced with a sufficiently large number, that remains as small as possible to ensure validity, to avoid numerical issues in practice.

    • In BendersLib, \(-\infty\) is provided as a customizable parameter BendersParams.theta_lb; \(+\infty\) is set to solvers’ default upper bound for unbounded variables.

    • Case B: subproblem is infeasible (dual is unbounded).

      • Find an extreme ray and add a Benders feasibility cut to the master problem.

  6. Step 5: Loop

    • Increment \(k = k + 1\) and go back to Step 1.

Given the set of complicating variables, the classical Benders Decomposition method has a standard way to formulate the master problem, subproblem, and Benders cuts. Therefore, these procedures can be automated, and users only need to provide the original problem and specify which variables are complicating variables. We implemented the method in ClassicalBenders, and automated it in AnnotatedBenders.

See also

References