How to add custom Benders' decomposition cut generation methods

The Benders' decomposition framework of SCIP allows the user to provide a custom implementation of cut generation methods. The Benders' decomposition cut methods are linked to the Benders' decomposition implementations, not the master problem SCIP instance. As such, you are able to have different Benders' decomposition cut methods for each included Benders' decomposition. The current list of all Benders' decomposition cut generation methods available in this release can be found here.

We now explain how users can add their own Benders' decomposition cut methods. Take the default Benders' decomposition cut method (src/scip/benderscut_opt.c) as an example. This Benders' decomposition cut method generates a classical optimality cut from the optimal dual solution to the convex relaxation of the Benders' decomposition subproblem. Same as all other default plugins, it is written in C. C++ users can easily adapt the code by using the scip::ObjBenderscut wrapper base class and implement the scip_...() virtual methods instead of the SCIP_DECL_BENDERSCUT... callback methods.

Additional documentation for the callback methods of a Benders' decomposition cut methods, in particular for the input parameters, can be found in the file type_benderscut.h.

Here is what you have to do to implement a custom Benders' decomposition cut method:

1. Copy the template files src/scip/benderscut_xyz.c and src/scip/benderscut_xyz.h into files "benderscut_mybenderscut.c" and "benderscut_mybenderscut.h".
   Make sure to adjust your build system such that these files are compiled and linked to your project.
   If you are adding a new default plugin, this means updating the src/CMakeLists.txt and Makefile files in the SCIP distribution.
2. Use SCIPincludeBenderscutMybenderscut() in order to include the Benders' decomposition cut method into your SCIP instance, e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example).
   If you are adding a new default plugin, this include function must be added to src/scipdefplugins.c.
3. Open the new files with a text editor and replace all occurrences of "xyz" by "mybenderscut".
4. Adjust the properties of the Benders' decomposition (see Properties of a Benders' decomposition).
5. Define the Benders' decomposition data (see Benders' decomposition Data). This is optional.
6. Implement the interface methods (see Interface Methods).
7. Implement the fundamental callback methods (see Fundamental Callback Methods of a Benders' decomposition cut method).
8. Implement the additional callback methods (see Additional Callback Methods of a Separator). This is optional.

Properties of a Benders' decomposition

At the top of the new file "benderscut_mybenderscut.c", you can find the Benders' decomposition cut methods 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::ObjBenderscut from within your constructor. The properties you have to set have the following meaning:

BENDERSCUT_NAME: the name of the Benders' decomposition cut method.

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

BENDERSCUT_DESC: the description of the Benders' decomposition cut method.

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

BENDERSCUT_PRIORITY: the priority of the Benders' decomposition cut method.

In each of the Benders' decomposition subproblem solving loops, the included Benders' decomposition cut methods are called in order of priority. The priority is important because once a cut is generated for a subproblem, no other cuts are generated for that subproblem for that solving loop.
The priority of the Benders' decomposition should be set according to the order in which the cut should be generated. For example, the priority of the included cuts attempt to generation feasibility cuts (src/scip/benderscut_feas.c and src/scip/benderscut_nogood.c) prior to attempting to generate optimality cuts.

BENDERSCUT_LPCUT: Can this cut be applied to convex subproblems and convex relaxations of CIP subproblems?

Since the Benders' decomposition framework executes two different solving loops, one for convex subproblems and the other for CIP subproblems, the Benders' decomposition cut methods must be partitioned by their suitability for each subproblem type. If BENDERSCUT_LPCUT is set to TRUE, then this cut is only applied to convex subproblems and convex relaxations of CIP subproblems.

Benders' decomposition Data

Below the header "Data structures" you can find a struct which is called "struct SCIP_BenderscutData". 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 "benderscut_mybenderscut.c", you can find the interface method SCIPincludeBenderscutMybenderscut(), which also appears in "benderscut_mybenderscut.h" SCIPincludeBenderscutMybenderscut() 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 SCIPincludeBenderscut(), or SCIPincludeBenderscutBasic() since SCIP version 3.0. In the latter variant, additional callbacks must be added via setter functions as, e.g., SCIPsetBenderscutCopy(). 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 cut data, you have to allocate the memory for the data at this point. You can do this by calling:

SCIP_CALL( SCIPallocBlockMemory(scip, &benderscutdata) );

You also have to initialize the fields in "struct SCIP_BenderscutData" afterwards. For freeing the Benders' decomposition cut data, see BENDERSCUTFREE.

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 SCIPincludeBenderscutOpt() in src/scip/benderscut_opt.c for an example.

Fundamental Callback Methods of a Benders' decomposition cut method

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 SCIPincludeBenderscut() or SCIPincludeBenderscutBasic(), see Interface Methods.

Benders' decomposition cut methods only one callback, BENDERSCUTEXEC, that must be implemented.

Additional documentation for the callback methods, in particular to their input parameters, can be found in type_benderscut.h.

BENDERSCUTEXEC

The BENDERSCUTEXEC callback is called during the cut generation process within the Benders' decomposition subproblem solving loop. This method must generate a cut for the given subproblem if the associated subsystem is not optimal with respect to the checked master problem solution.

When generating cuts, it is possible to store these within the SCIP_BendersData of the associated Benders' decomposition. This is achieved by calling SCIPstoreBenderscutCons() (SCIPstoreBenderscutCut() if the Benders' decomposition cut is added as a cutting plane instead as a constraint). The storing of cuts can be useful when using the large neighbourhood Benders' search, where the cut generated in the sub-SCIP solve are transferred to the main SCIP instance.

The BENDERSCUTEXEC callback must return the result of the cut generation. The permissable results are:

• if the Benders' cut was not run (SCIP_DIDNOTRUN).
• if the Benders' cut was run, but there was an error in generating the cut (SCIP_DIDNOTFIND).
• if the Benders' decomposition cut algorithm has not generated a constraint or cut (SCIP_FEASIBLE).
• an additional constraint for the Benders' decomposition cut was generated (SCIP_CONSADDED).
• a cutting plane representing the Benders' decomposition cut was generated (SCIP_SEPARATED).

If the BENDERSCUTEXEC callback returns SCIP_DIDNOTFIND due to an error in the cut generation, if no other subproblems generate a cut during the same iteration of the Benders' decomposition algorithm, then this could result in an error. It is possible to avoid the error by merging the subproblem into the master problem (see BENDERSPOSTSOLVE).

Additional Callback Methods of a Separator

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 SCIPincludeBenderscut() to SCIP or via specific setter functions after a call of SCIPincludeBenderscutBasic(), see also Interface Methods.

BENDERSCUTFREE

If you are using Benders' decomposition cut data (see Benders' decomposition Data and Interface Methods), you have to implement this method in order to free the Benders' decomposition cut data.

If you have allocated memory for fields in your Benders' decomposition cut 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.

BENDERSCUTCOPY

The BENDERSCUTCOPY 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 the Benders' decomposition cuts are included by calling SCIPincludeBendersDefaultCuts() in the include method of the Benders' decomposition implementation, such as SCIPincludeBendersDefault(), then it is not necessary to implement BENDERSCUTCOPY. The copy method could be implemented to copy Benders' decomposition cut data from the original SCIP instance to the sub-SCIP.

BENDERSCUTINIT

The BENDERSCUTINIT callback is executed after the problem is transformed The Benders' decomposition cut method may, e.g., use this call to initialize its Benders' decomposition cut data. 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).

BENDERSCUTEXIT

The BENDERSCUTEXIT callback is executed before the transformed problem is freed. In this method, the Benders' decomposition cut method should free all resources that have been allocated for the solving process in BENDERSCUTINIT.

BENDERSCUTINITSOL

The BENDERSCUTINITSOL 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.

BENDERSCUTEXITSOL

The BENDERSCUTEXITSOL 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.