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:

Copy the template files src/scip/benders_xyz.c and src/scip/benders_xyz.h into files "benders_mybenders.c" and "benders_mybenders.h".
Make sure to adjust your Makefile such that these files are compiled and linked to your project.
Use SCIPincludeBendersMybenders() in order to include the Benders' decomposition into your SCIP instance, e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example).
Open the new files with a text editor and replace all occurrences of "xyz" by "mybenders".
Adjust the properties of the Benders' decomposition (see Properties of a Benders' decomposition).
Define the Benders' decomposition data (see Benders' decomposition Data). This is optional.
Implement the interface methods (see Interface Methods).
Implement the fundamental callback methods (see Fundamental Callback Methods of a Benders' decomposition).
Implement the additional callback methods (see Additional Callback Methods of a Benders' decomposition implementation). This is optional.

Properties of a Benders' decomposition

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:

BENDERS_NAME: the name of the Benders' decomposition.: This name is used in the interactive shell to address the Benders' decomposition. Additionally, if you are searching for a Benders' decomposition with SCIPfindBenders(), this name is looked up. Names have to be unique: no two Benders' decompositions may have the same name.

BENDERS_DESC: the description of the Benders' decomposition.: This string is printed as a description of the Benders' decomposition in the interactive shell.

BENDERS_PRIORITY: the priority of the Benders' decomposition.: During the enforcement and checking of solutions in src/scip/cons_benders.c and src/scip/cons_benderslp.c, every active Benders' decompositions are called. The execution method of the Benders' decomposition calls each of the subproblems and generates cuts from their solutions. So the active Benders' decompositions are called in order of priority until a cut is generated or feasibility is proven.
The priority of the Benders' decomposition should be set according to the difficulty of solving the subproblems and the generation of cuts. However, it is possible to prioritise the Benders' decompositions with respect to the strength of the subproblem formulation and the resulting cuts.

BENDERS_CUTLP: should Benders' decomposition cuts be generated during the enforcement of LP solutions.: This is a flag that is used by src/scip/cons_benders.c and src/scip/cons_benderslp.c to idicate whether the enforcement of LP solutions should involve solving the Benders' decomposition subproblems. This should be set to TRUE to have an exact solution algorithm. In the presence of multiple Benders' decomposition, it may be desired to enforce the LP solutions for only a subset of those implemented.

BENDERS_CUTRELAX: should Benders' decomposition cuts be generated during the enforcement of relaxation solutions.: This is a flag that is used by src/scip/cons_benders.c and src/scip/cons_benderslp.c to idicate whether the enforcement of relaxation solutions should involve solving the Benders' decomposition subproblems. This should be set to TRUE to have an exact solution algorithm. In the presence of multiple Benders' decomposition, it may be desired to enforce the relaxation solutions for only a subset of those implemented. This parameter will only take effect if external relaxation have been implemented.

BENDERS_CUTPSEUDO: should Benders' decomposition subproblems be solved during the enforcement of pseudo solutions.: This is a flag that is used by src/scip/cons_benders.c and src/scip/cons_benderslp.c to indicate whether the enforcement of pseudo solutions should involve solving the Benders' decomposition subproblems. This should be set to TRUE, since not enforcing pseudo solutions could result in an error or suboptimal result. During the enforcement of pseudo solutions, no cuts are generated. Only a flag to indicate whether the solution is feasible or if the LP should be solved again is returned.

BENDERS_SHAREAUXVARS: should this Benders' decomposition use the auxiliary variables from the highest priority: Benders' decomposition. This parameter only takes effect if multiple Benders' decompositions are implemented. Consider the case that two Benders' decompositions are implemented with different formulations of the subproblem. Since the subproblems in each of the decomposition will have the same optimal solution, then it is useful to only have a single auxiliary variable for the two different subproblems. This means that when an optimality cut is generated in the lower priority Benders' decomposition, the auxiliary variable from the highest priority Benders' decomposition will be added to the right hand side.

Benders' decomposition Data

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.

Interface Methods

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:

SCIP_CALL( SCIPallocBlockMemory(scip, &bendersdata) );

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.

Fundamental Callback Methods of a Benders' decomposition

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.

BENDERSGETVAR

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

static
SCIP_DECL_BENDERSGETVAR(bendersGetvarDefault)
{  /*lint --e{715}*/
   SCIP_BENDERSDATA* bendersdata;
   SCIP_VAR* origvar;
   SCIP_Real scalar;
   SCIP_Real constant;
   assert(scip != NULL);
   assert(benders != NULL);
   assert(var != NULL);
   assert(mappedvar != NULL);
   bendersdata = SCIPbendersGetData(benders);
   if( probnumber == -1 )
   {
      origvar = var;
      /* The variable needs to be transformed back into an original variable. If the variable is already original, then
       * this function just returns the same variable
       */
      scalar = 1.0;
      constant = 0.0;
      SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) );
      /* using the original variable, the master variable can be retrieved from the hash map */
      (*mappedvar) = (SCIP_VAR*) SCIPhashmapGetImage(bendersdata->subvartomastervar, origvar);
      if( (*mappedvar) == NULL )
         (*mappedvar) = (SCIP_VAR*) SCIPhashmapGetImage(bendersdata->subvartomastervar, var);
   }
   else
   {
      int masterindex;
      /* The variable needs to be transformed back into an original variable. If the variable is already original, then
       * this function just returns the same variable
       */
      /* we are requesting the subproblem variable for a master problem variable
       * The master problem variable is a transformed variable. The original variable is not required.
       * NOTE: Currently the original variable is being used. This may not be correct and should be the transformed
       * variable.
       */
      masterindex = SCIPhashmapGetImageInt(bendersdata->mastervartosubindex, var);
      (*mappedvar) = bendersdata->subproblemvars[probnumber][masterindex];
   }
   return SCIP_OKAY;
}

(Source: src/scip/benders_default.c)

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.

BENDERSCREATESUB

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.

Additional Callback Methods of a Benders' decomposition implementation

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.

BENDERSFREE

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:

static
SCIP_DECL_BENDERSFREE(bendersFreeDefault)
{  /*lint --e{715}*/
   SCIP_BENDERSDATA* bendersdata;
   int i;
   assert(scip != NULL);
   assert(benders != NULL);
   bendersdata = SCIPbendersGetData(benders);
   assert(bendersdata != NULL);
   /* should have been freed in bendersExitDefault (if mappingcreated), or not been created at the first place */
   assert(bendersdata->subproblemvars == NULL);
   assert(bendersdata->subvartomastervar == NULL);
   assert(bendersdata->mastervartosubindex == NULL);
   if( bendersdata->created )
   {
      /* if the subproblems were copied, then the copy needs to be freed */
      if( bendersdata->subprobscopied )
      {
         for( i = bendersdata->nsubproblems - 1; i >= 0; i-- )
         {
            SCIP_CALL( SCIPfree(&bendersdata->subproblems[i]) );
         }
      }
      SCIPfreeBlockMemoryArray(scip, &bendersdata->subproblems, bendersdata->nsubproblems);
   }
   SCIPfreeBlockMemory(scip, &bendersdata);
   return SCIP_OKAY;
}

(Source: src/scip/benders_default.c)

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.

BENDERSCOPY

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.

BENDERSINIT

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).

BENDERSEXIT

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.

BENDERSINITPRE

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.

BENDERSEXITPRE

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.

BENDERSINITSOL

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.

BENDERSEXITSOL

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.

BENDERSPRESUBSOLVE

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

the subproblem was not solved in this iteration. Other decompositions will be checked (SCIP_DIDNOTRUN).
a constraint has been added to the master problem. No other decompositions will be checked (SCIP_CONSADDED).
a cut has been added to the master problem. No other decompositions will be checked (SCIP_SEPARATED).
feasibility of the solution is reported to SCIP. Other decompositions will be checked (SCIP_FEASIBLE).
infeasibility of the solution is reported to SCIP. No other decompositions will be checked (SCIP_INFEASIBLE).

BENDERSSOLVESUBCONVEX

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 subproblem was not solved in this iteration (SCIP_DIDNOTRUN)
the subproblem is solved and is feasible (SCIP_FEASIBLE)
the subproblem is solved and is infeasible (SCIP_INFEASIBLE)
the subproblem is solved and is unbounded (SCIP_UNBOUNDED)

BENDERSSOLVESUB

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 subproblem was not solved in this iteration (SCIP_DIDNOTRUN)
the subproblem is solved and is feasible (SCIP_FEASIBLE)
the subproblem is solved and is infeasible (SCIP_INFEASIBLE)
the subproblem is solved and is unbounded (SCIP_UNBOUNDED)

BENDERSPOSTSOLVE

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.

BENDERSFREESUB

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.