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. Such problems are given by
\[ \begin{array}[t]{rllclcl} \min & \displaystyle & c^{T}x & + & d^{T}y \\ & \\ 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 \\ & \\ 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 \\ & \\ 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} \]
The Benders' decomposition framework of SCIP allows the user to provide a custom implementation of many aspects of the Benders' decomposition algorithm. It is possible to implement multiple Benders' decompositions that work in conjunction with each other. Such a situation is where you may have different formulations of the Benders' decomposition subproblem.
The current list of all Benders' decomposition implementations available in this release can be found here.
We now explain how users can add their own Benders' decomposition implementations. Take the default Benders' decomposition implementation (src/scip/benders_default.c) as an example. Same as all other default plugins, it is written in C. C++ users can easily adapt the code by using the scip::ObjBenders wrapper base class and implement the scip_...() virtual methods instead of the SCIP_DECL_BENDERS... callback methods.
Additional documentation for the callback methods of a Benders' decomposition implementation, in particular for the input parameters, can be found in the file type_benders.h.
Here is what you have to do to implement a custom Benders' decomposition:
src/CMakeLists.txt
and Makefile
files in the SCIP distribution.src/scipdefplugins.c
.At the top of the new file "benders_mybenders.c", you can find the Benders' decomposition properties. These are given as compiler defines. In the C++ wrapper class, you have to provide the Benders' decomposition properties by calling the constructor of the abstract base class scip::ObjBenders from within your constructor. The properties you have to set have the following meaning:
Below the header "Data structures" you can find a struct which is called "struct SCIP_BendersData". In this data structure, you can store the data of your Benders' decomposition. For example, you should store the adjustable parameters of the Benders' decomposition in this data structure. In a Benders' decomposition, user parameters for the number of subproblems and an array to store the subproblem SCIP instances could be useful.
Defining Benders' decomposition data is optional. You can leave the struct empty.
At the bottom of "benders_mybenders.c", you can find the interface method SCIPincludeBendersMybenders(), which also appears in "benders_mybenders.h" SCIPincludeBendersMybenders() is called by the user, if (s)he wants to include the Benders' decomposition, i.e., if (s)he wants to use the Benders' decomposition in his/her application.
This method only has to be adjusted slightly. It is responsible for notifying SCIP of the presence of the Benders' decomposition. For this, you can either call SCIPincludeBenders(), or SCIPincludeBendersBasic() since SCIP version 3.0. In the latter variant, additional callbacks must be added via setter functions as, e.g., SCIPsetBendersCopy(). We recommend this latter variant because it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first variant must be manually adjusted with every SCIP release containing new callbacks for Benders' decompositions in order to compile.
If you are using Benders' decomposition data, you have to allocate the memory for the data at this point. You can do this by calling:
You also have to initialize the fields in "struct SCIP_BendersData" afterwards. For freeing the Benders' decomposition data, see BENDERSFREE.
You may also add user parameters for your Benders' decomposition, see How to add additional user parameters for how to add user parameters and the method SCIPincludeBendersDefault() in src/scip/benders_default.c for an example.
It is advised to disable presolving for the Benders' decomposition master problem by calling SCIPsetPresolving() with the parameter SCIP_PARAMSETTING_OFF. Presolving should be disabled because reductions on the master problem could be invalid since constraints have been transferred to the subproblems. It is not necessary to disable all presolving, but care must be taken when it is used for the Benders' decomposition master problem.
The Benders' decomposition constraint handler, see src/scip/cons_benders.c, includes a presolver for tightening the bound on the auxiliary variables. This presolver can be enabled with by setting "presolving/maxround" to 1 and "constraints/benders/maxprerounds" to 1. This presolver solves the Benders' decomposition subproblems without fixing the master problem variables to find a lower bound for the auxiliary variable.
The fundamental callback methods of the plugins are the ones that have to be implemented in order to obtain an operational algorithm. They are passed together with the Benders' decomposition itself to SCIP using SCIPincludeBenders() or SCIPincludeBendersBasic(), see Interface Methods.
Benders' decomposition plugins have two callbacks, BENDERSGETVAR and BENDERSCREATESUB that must be implemented.
Additional documentation for the callback methods, in particular to their input parameters, can be found in type_benders.h.
The BENDERSGETVAR callback provides a mapping between the master problem variables and their corresponding subproblem variables, and vice versa. The parameters of this function include the variable for which the mapped variable is desired and the problem number for the mapped variable. When requesting a subproblem variable for a given master problem variable, the master variable is input with the appropriate subproblem index. If a master problem variable is requested for a given subproblem variable, then the subproblem variable is input with the subproblem index given as -1.
An example of how to implement the mapping between the master and subproblem variables is shown by
In the above code snippet, the hashmaps providing the mapping between the master and subproblem variables are constructed in the SCIP_STAGE_INIT
stage (see BENDERSINIT).
The requested variable is returned via the mappedvar parameter. There may not exist a corresponding master (subproblem) variable for every input subproblem (master) variable. In such cases were no corresponding variable exists, mappedvar must be returned as NULL.
The mapped variables are retrieved by calling SCIPgetBendersMasterVar() and SCIPgetBendersSubproblemVar().
The variable mapping must be created before SCIP_STAGE_PRESOLVE
stage. This is because the variable mapping is required for checking solutions found by heuristics during presolving.
The BENDERSCREATESUB callback is executed during the SCIP_STAGE_INIT
stage. In this function, the user must register the SCIP instances for each subproblem. The BENDERSCREATESUB callback is executed once for each subproblem. The user registers a subproblem by calling SCIPbendersAddSubproblem().
It is possible to build the SCIP instance for the subproblem during the execution of this callback. However, it may be more convenient to build the subproblem instances during the problem creation stage of the master problem and store the subproblem SCIP instances in SCIP_BendersData. This approach is used in src/scip/benders_default.c.
The additional callback methods do not need to be implemented in every case. However, some of them have to be implemented for most applications, they can be used, for example, to initialize and free private data. Additional callbacks can either be passed directly with SCIPincludeBenders() to SCIP or via specific setter functions after a call of SCIPincludeBendersBasic(), see also Interface Methods.
If you are using Benders' decomposition data (see Benders' decomposition Data and Interface Methods), you have to implement this method in order to free the Benders' decomposition data. This can be done by the following procedure:
If you have allocated memory for fields in your Benders' decomposition data, remember to free this memory before freeing the Benders' decomposition data itself. If you are using the C++ wrapper class, this method is not available. Instead, just use the destructor of your class to free the member variables of your class.
The BENDERSCOPY callback is executed when a SCIP instance is copied, e.g. to solve a sub-SCIP. By defining this callback as NULL
the user disables the execution of the specified separator for all copied SCIP instances. This may deteriorate the performance of primal heuristics using sub-SCIPs.
If a user wishes to employ the Large Neighbourhood Benders' Search, it is necessary for the BENDERSCOPY callback to be implemented. This is required because the sub-SCIP instances of large neighbourhood search heuristics can only access the implemented Benders' decomposition if it is copied via the BENDERSCOPY callback.
The BENDERSINIT callback is executed after the problem is transformed. The Benders' decomposition implementation may, e.g., use this call to initialize its Benders' decomposition data. In src/scip/benders_default.c BENDERSINIT is used to create the mapping between the master and subproblem variables. The difference between the original and the transformed problem is explained in "What is this thing with the original and the transformed problem about?" on Frequently Asked Questions (FAQ).
The BENDERSEXIT callback is executed before the transformed problem is freed. In this method, the Benders' decomposition implementation should free all resources that have been allocated for the solving process in BENDERSINIT.
The BENDERSINITPRE callback is executed before the preprocessing is started, even if presolving is turned off. The Benders' decomposition may use this call to initialize its presolving data before the presolving process begins.
The BENDERSEXITPRE callback is executed after the preprocessing has been finished, even if presolving is turned off. The Benders' decomposition implementation may use this call, e.g., to clean up its presolving data. Besides clean up, no time consuming operations should be done.
The BENDERSINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to begin. The Benders' decomposition implementation may use this call to initialize its branch-and-bound specific data.
The BENDERSEXITSOL callback is executed before the branch-and-bound process is freed. The Benders' decomposition implementation should use this call to clean up its branch-and-bound data.
The BENDERSPRESUBSOLVE callback is provided to give the user an opportunity in each iteration to perform any setup operations prior to solving the subproblems. This callback also allows the user to skip the subproblem solve for the current iteration. In this case, the user must set the result parameter appropriately
Two different subproblem solving functions are provide in the Benders' decomposition framework, BENDERSSOLVESUBCONVEX and BENDERSSOLVESUB. These two solving functions are used in the two solving loops of the Benders' decomposition framework. The first solving loop solves convex subproblems and convex relaxations of CIPs. The BENDERSSOLVESUBCONVEX callback is executed only during the FIRST solving loop. Benders' cut generating methods suitable for convex subproblems are executed during this solving loop. If a cut is found, then the second solve loop is not executed. If your decomposition does not have any convex subproblems, then it is not necessary to implement the BENDERSSOLVESUBCONVEX callback. However, it may be computationally beneficial to solve the convex relaxation of CIP subproblems, such as the LP relaxation of a MIP subproblem.
The second solve loop expects that the CIP subproblems are solved to optimality.
If you implement the BENDERSSOLVESUBCONVEX callback, it is necessary to implement the BENDERSFREESUB callback.
The objective function value after the subproblem solve and the result must be returned. The permissible results are:
The BENDERSSOLVESUB is executed only during the SECOND solve loop. This callback function is used to solve CIP subproblems. If your decomposition does not have any CIP subproblems, then it is not necessary to implement the BENDERSSOLVESUB callback.
If you implement the BENDERSSOLVESUB callback, it is necessary to implement the BENDERSFREESUB callback.
The objective function value after the subproblem solve and the result must be returned. The permissible results are:
The BENDERSPOSTSOLVE callback is executed after the subproblems have been solved and any required cuts have been generated, but before the subproblems are freed. This callback provides the user an opportunity to interact the subproblems at a global level. For example, the user is able to construct a solution to the original problem by combining the solutions from the master problem and all subproblems.
Additionally, the user is able to merge subproblems into the master problem during the execution of this callback. The merging of subproblems into the master problem could be desired if it is too time consuming to satisfy the feasibility of a subproblem or the appropriate cutting methods are not available for the provided subproblem. A list of indicies of subproblems suitable for merging are given in the mergecands array. The first npriomergecands are the merge candidates that must be merged into the master problem. If they are not, then the solution process will terminate with an error. These merge candidates arise if a cut could not be generated due to numerical difficulties. The remaining nmergecands - npriomergecands are subproblems that could be merged into the master problem if desired by the user.
The BENDERSFREESUB callback is executed to clean up the subproblems after the solving process and prepare them for the next iteration. Typically, SCIPfreeTransform() is called for each subproblem to free the transformed problem.