Benders' decomposition is a very popular mathematical programming technique that is applied to solve structured problems. Problems that display a block diagonal structure are particularly amenable to the application of Benders' decomposition. In a purely mixed-integer linear setting, such problems are given by

\[ \begin{array}[t]{rllclcl} \min & \displaystyle & c^{T}x & + & d^{T}y \\ & \\ \text{subject to} & \displaystyle & Ax & & & = & b \\ & \\ & \displaystyle & Tx & + & Hy & = & h \\ & \\ & & x & & & \in & \mathbb{Z}^{p}\times\mathbb{R}^{n - p} \\ & & & & y & \in & \mathbb{R}^{m} \\ \end{array} \]

The variables \(x\) and \(y\) are described as the first and second stage variables respectively. In the classical use of Benders' decomposition, it is a requirement that the all second stage variables are continuous. Extensions to the classical Benders' decomposition approach have permitted the use of more general second stage problems.

The application of Benders' decomposition to the above problem results in a subproblem, given by

\[ \begin{array}[t]{rll} \min & \displaystyle & d^{T}y \\ & \\ \text{subject to} & \displaystyle & Hy = h - T\bar{x} \\ & \\ & & y \in \mathbb{R}^{m} \\ \end{array} \]

where \(\bar{x}\) is a solution vector of the first stage variables. As such, the subproblem is a problem only in \(y\). The dual solution to the subproblem, either an extreme point or extreme ray, is used to generate cuts that are added to the master problem. Let \(\lambda\) be the vector of dual variables associated with the set of constraints from the subproblem. If, for a given \(\bar{x}\), the subproblem is infeasible, then \(\lambda\) corresponds to a dual ray and is used to produce the cut

\[ 0 \geq \lambda(h - Tx) \]

which eliminates \(\bar{x}\) from the master problem. If, for a given \(\bar{x}\), the subproblem is feasible, then \(\lambda\) corresponds to a dual extreme point and is used to produce the cut

\[ \varphi \geq \lambda(h - Tx) \]

where \(\varphi\) is an auxiliary variable added to the master problem as an underestimator of the optimal subproblem objective function value.

Given \(\Omega^{p}\) and \(\Omega^{r}\) as the sets of dual extreme points and rays of the subproblem, respectively, the Benders' decomposition master problem is given by

\[ \begin{array}[t]{rll} \min & \displaystyle & c^{T}x + \varphi \\ & \\ \text{subject to} & \displaystyle & Ax = b \\ & \\ & \displaystyle & \varphi \geq \lambda(h - Tx) \quad \forall \lambda \in \Omega^{r}\\ & \\ & \displaystyle & 0 \geq \lambda(h - Tx) \quad \forall \lambda \in \Omega^{r} \\ & \\ & & x \in \mathbb{Z}^{p}\times\mathbb{R}^{n - p} \\ & & \varphi \in \mathbb{R} \\ \end{array} \]

Overview

In SCIP 6.0 a Benders' decomposition framework has been implemented.

The current framework can be used to handle a Benders Decomposition of CIPs of the form

\[ \begin{array}[t]{rllclcl} \min & \displaystyle & c^{T}x & + & d^{T}y \\ \text{subject to} & \displaystyle & g(x & , & y) & \in & [\ell,u] \\ & & x & & & \in & X \\ & & & & y & \in & Y \\ \end{array} \]

when either

the subproblem is convex: \(g_i(x,y)\) convex on \(X\times Y\) if \(u_i<\infty\), \(g_i(x,y)\) concave on \(X\times Y\) if \(\ell_i>-\infty\), and \(Y=\mathbb{R}^m\), or
the first stage variables are of binary type: \( X \subseteq \{0,1\}^n \).

This framework can be used in four different ways: inputting an instance in the SMPS file format, using the default Benders' decomposition implementation (see src/scip/benders_default.c), implementing a custom Benders' decomposition plugin (see How to add custom Benders' decomposition implementations), or by using the Benders' decomposition mode of GCG. An overview of how to use each of these methods will be provided in this section.

Inputting an instance in the SMPS file format.

As part of the Benders' decomposition framework development, a reader for instances in the SMPS file format has been implemented (see src/scip/reader_smps.c). The details regarding the SMPS file format can be found at:

Birge, J. R.; Dempster, M. A.; Gassmann, H. I.; Gunn, E.; King, A. J. & Wallace, S. W. A standard input format for multiperiod stochastic linear programs IIASA, Laxenburg, Austria, WP-87-118, 1987

In brief, the SMPS file format involves three different files:

A core file (.cor): a problem instance in MPS format that is the core problem of a stochastic program.
A time file (.tim): partitions the variables and constraints into the different stages of the stochastic program
A stochastic file (.sto): describes the scenarios for each stage.

The STO reader (see src/scip/reader_sto.c) constructs the stochastic program using the information from the core and time files. By default, the STO reader will construct the deterministic equivalent of the stochastic program. A parameter is provided "reading/sto/usebenders" that will inform the STO reader to apply Benders' decomposition to the input stochastic program.

Inputting a user-defined decomposition structure

Benders' decomposition can be applied from a user-provided decomposition structure. Details about the decomposition structure and how to provide it to SCIP can be found at How to provide a problem decomposition. Prior to reading the decomposition structure into SCIP, it is necessary to inform SCIP that the variables and constraints must be labelled for Benders' decomposition. This is achieved by setting the parameter "decomposition/benderslabels" to "TRUE". Following this, Benders' decomposition will be applied if the parameter "decomposition/applybenders" is set to "TRUE".

When Benders' decomposition is applied using the decomposition structure, the Benders' decomposition algorithm is executed within a relaxator (see How to add relaxation handlers). The relaxator is called when processing the root node of the original SCIP instance, before the first LP solve. Within the relaxator, a sub-SCIP is created, upon which the Benders' decomposition is applied. The default Benders' decomposition plugin (see Using the default Benders' decomposition plugin.) is used for applying the decomposition. The master problem sub-SCIP is solved and then the solution from the Benders' decomposition algorithm is returned.

If the problem is solved to optimality by the Benders' decomposition algorithm, then the original SCIP instance terminates. There are cases where the Benders' decomposition algorithm terminates without an optimal solution. As a result, the original SCIP instance would continue solving. These cases are: reaching node, memory or solution limits, or numerical issues meaning that the Benders' solution is not optimal for the original problem. The parameter "relaxing/benders/continueorig" is provided to inform SCIP whether the original SCIP instance should continue solving following the completion of the Benders' algorithm. By default, solving in the original SCIP instance is interrupted when the relaxator finishes.

The parameter setting and limits from the original SCIP instance are copied across to the master problem sub-SCIP in the Benders' decomposition relaxator. It is possible to set a separate node limit for the Benders' algorithm within the relaxator. This is achieved by using the parameter "relaxing/benders/nodelimit". A possible use case for a separate Benders' node limit is that the Benders' algorithm could be used as an initial heuristics for the original SCIP instance.

An advantage over using the decomposition structure compared to an instance in the SMPS format is that the solution to the original problem is easily accessible. At the completion of the Benders' decomposition algorithm, the best know solution is copied back to the original SCIP instance. Note that using a decomposition structure is not the only way to get the original problem solution from the Benders' decomposition algorithm. Whichever method you use, it is possible to solve the Benders' decomposition subproblems by calling SCIPsetupBendersSubproblem() and then SCIPsolveBendersSubproblem() for each subproblem using the best solution from the master problem. An example of this can be found in solveBendersSubproblems() of src/scip/relax_benders.c.

Using the default Benders' decomposition plugin.

A default implementation of a Benders' decomposition plugin has been included in SCIP 6.0 (see src/scip/benders_default.c). In order to use the default plugin, the user must create SCIP instances of the master problem and subproblems. The subproblems must also contain a copy of the master problem variables, since these are fixed to the master problem solution values during the subproblem solving loop. These SCIP instances for the master and subproblems are passed to the default plugin by calling SCIPcreateBendersDefault().

The mapping between the master and subproblem variables is performed automatically. The default solving and cut generation methods are applied to solve the input problem. It is important to note that the mapping between the master and subproblem variables relies on the variable names. The variables of the subproblem corresponding to master problem variables must have the same name in both problems.

The CAP (stochastic capacitated facility location problem) example demonstrates the use of the default Benders' decomposition implementation within a project.

Implementing a custom Benders' decomposition implementation.

A custom Benders' decomposition requires the implementation of a Benders' decomposition plugin. The key aspects for implementing a custom Benders' decomposition plugin are explained in How to add custom Benders' decomposition implementations.

Using the Benders' decomposition mode of GCG

In GCG 3.0, a Benders' decomposition mode has been implemented. This mode takes the decomposition found by the detection schemes of GCG and applies Benders' decomposition. Using GCG it is possible to apply Benders' decomposition to general problem without having to manually construct the decompositions.

Objective type options for the Benders' decomposition

Classically, the application of Benders' decomposition results in the inclusion of an auxiliary variable to provide an underestimation of the subproblem objective value. If the subproblem can be separated into disjoint problems, then this auxiliary variable can be substituted with the sum of auxiliary variables (one for each subproblem).

While the summation of auxiliary variables is theoretically possible for all applications of Benders' decomposition, there are problems where an alternative objective may be beneficial. An example is a multiple machine scheduling problem with a makespan objective. To accommodate different objective types, the Benders' decomposition framework allows for the objective types of summation (the classical method) or the minimum of the maximum subproblem auxiliary variables. The objective type can be set using the method SCIPsetBendersObjectiveType(). Note that the different objective types only have an impact if more than one subproblem is used in the Benders' decomposition.