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.

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.