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:
src/CMakeLists.txt
and Makefile
files in the SCIP distribution.src/scipdefplugins.c
.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:
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.
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:
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.
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.
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 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).
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.
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.
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.
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).
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.
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.
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.