default Benders' decomposition plugin
- Stephen J. Maher
The default Benders' decomposition plugin is provided to simplify the interaction the Benders' decomposition framework within SCIP. This plugin is included in the SCIP package by default. Using the default Benders' decomposition plugin, a problem can be solved by Benders' decomposition by calling
SCIPcreateBendersDefault(master problem, array of subproblems, number of subproblems)
where "master problem" is a SCIP instance of the master problem, "array of subproblems" is an array of SCIP instances that are the Benders' decomposition subproblems and "number of subproblems" is an integer indicating the number of subproblems for this decomposition.
A key feature of the default Benders' decomposition plugin is the automatic generation of the variable mapping between the variables of the master problem and the subproblems.
In the traditional application of Benders' decomposition, master problem variables are fixed to a solution value and modify the RHS of the second stage constraints. The implementation within SCIP requires that a variable is created in the subproblem for every master problem variable that appears in the subproblem constraints. This variable MUST have the same name as the corresponding variable in the master problem. This name is used to automatically generate the mapping between the master problem and the corresponding subproblem variables.
Definition in file benders_default.c.
Creates the variable mappings between the master problem and the corresponding variable in the subproblem.
TODO: add the functionality to allow the user to provide an array of hashmaps for mapping between the master problem variables and the corresponding subproblem variables. TODO: check for uniqueness of names in this function.
|scip||SCIP data structure |
|benders||the Benders' decomposition structure |
Definition at line 130 of file benders_default.c.
References NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPbendersGetData(), SCIPblkmem(), SCIPcaptureVar(), SCIPfindVar(), SCIPgetNVars(), SCIPgetSubscipDepth(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapInsert(), SCIPhashmapInsertInt(), SCIPsnprintf(), SCIPvarGetName(), SCIPvarGetOrigvarSum(), and TRUE.
Referenced by SCIP_DECL_BENDERSINIT().
! [SnippetBendersGetvarDefault] the method for creating the Benders' decomposition subproblem. This method is called during the initialisation stage (after the master problem was transformed)
This method must create the SCIP instance for the subproblem and add the required variables and constraints. In addition, the settings required for the solving the problem must be set here. However, some settings will be overridden by the standard solving method included in the Benders' decomposition framework. If a special solving method is desired, the user can implement the bendersSolvesubDefault callback.
Definition at line 455 of file benders_default.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPaddBendersSubproblem(), and SCIPbendersGetData().