SCIP
Solving Constraint Integer Programs
benders_default.c File Reference
Detailed Description
default Benders' decomposition plugin
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.
#include "scip/benders_default.h"#include "scip/bendersdefcuts.h"#include "scip/pub_benders.h"#include "scip/pub_message.h"#include "scip/pub_misc.h"#include "scip/pub_var.h"#include "scip/scip.h"Go to the source code of this file.
Macros | |
| #define | BENDERS_NAME "default" |
| #define | BENDERS_DESC "default implementation of Benders' decomposition" |
| #define | BENDERS_PRIORITY 0 |
| #define | BENDERS_CUTLP TRUE |
| #define | BENDERS_CUTPSEUDO TRUE |
| #define | BENDERS_CUTRELAX TRUE |
| #define | BENDERS_SHAREAUXVARS FALSE |
Functions | |
| static SCIP_RETCODE | createBendersData (SCIP *scip, SCIP **subproblems, SCIP_BENDERSDATA **bendersdata, int nsubproblems) |
| static SCIP_RETCODE | createVariableMappings (SCIP *scip, SCIP_BENDERS *benders) |
| static | SCIP_DECL_BENDERSCOPY (bendersCopyDefault) |
| static | SCIP_DECL_BENDERSFREE (bendersFreeDefault) |
| static | SCIP_DECL_BENDERSINIT (bendersInitDefault) |
| static | SCIP_DECL_BENDERSEXIT (bendersExitDefault) |
| static | SCIP_DECL_BENDERSGETVAR (bendersGetvarDefault) |
| static | SCIP_DECL_BENDERSCREATESUB (bendersCreatesubDefault) |
| SCIP_RETCODE | SCIPcreateBendersDefault (SCIP *scip, SCIP **subproblems, int nsubproblems) |
| SCIP_RETCODE | SCIPincludeBendersDefault (SCIP *scip) |
Macro Definition Documentation
◆ BENDERS_NAME
| #define BENDERS_NAME "default" |
Definition at line 61 of file benders_default.c.
Referenced by SCIP_DECL_BENDERSCOPY(), SCIPcreateBendersDefault(), and SCIPincludeBendersDefault().
◆ BENDERS_DESC
| #define BENDERS_DESC "default implementation of Benders' decomposition" |
Definition at line 62 of file benders_default.c.
Referenced by SCIPincludeBendersDefault().
◆ BENDERS_PRIORITY
| #define BENDERS_PRIORITY 0 |
Definition at line 63 of file benders_default.c.
Referenced by SCIPincludeBendersDefault().
◆ BENDERS_CUTLP
| #define BENDERS_CUTLP TRUE |
should Benders' cut be generated for LP solutions
Definition at line 64 of file benders_default.c.
Referenced by SCIPincludeBendersDefault().
◆ BENDERS_CUTPSEUDO
| #define BENDERS_CUTPSEUDO TRUE |
should Benders' cut be generated for pseudo solutions
Definition at line 65 of file benders_default.c.
Referenced by SCIPincludeBendersDefault().
◆ BENDERS_CUTRELAX
| #define BENDERS_CUTRELAX TRUE |
should Benders' cut be generated for relaxation solutions
Definition at line 66 of file benders_default.c.
Referenced by SCIPincludeBendersDefault().
◆ BENDERS_SHAREAUXVARS
| #define BENDERS_SHAREAUXVARS FALSE |
should this Benders' share the highest priority Benders' aux vars
Definition at line 67 of file benders_default.c.
Referenced by SCIPincludeBendersDefault().
Function Documentation
◆ createBendersData()
|
static |
creates the Benders' decomposition data
- Parameters
-
scip SCIP data structure subproblems the Benders' decomposition subproblems bendersdata the Benders' decomposition data nsubproblems the number of subproblems in the Benders' decomposition
Definition at line 97 of file benders_default.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, and TRUE.
Referenced by SCIPcreateBendersDefault().
◆ createVariableMappings()
|
static |
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.
- Parameters
-
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().
◆ SCIP_DECL_BENDERSCOPY()
|
static |
copy method for Benders' decomposition plugins (called when SCIP copies plugins)
Definition at line 232 of file benders_default.c.
References BENDERS_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPbendersGetData(), SCIPbendersIsActive(), SCIPcopyOrig(), SCIPcreate(), SCIPcreateBendersDefault(), SCIPfindBenders(), SCIPfreeBufferArray, SCIPincludeBendersDefault(), and TRUE.
◆ SCIP_DECL_BENDERSFREE()
|
static |
destructor of Benders' decomposition to free user data (called when SCIP is exiting) ! [SnippetBendersFreeDefault]
Definition at line 303 of file benders_default.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPbendersGetData(), SCIPfree(), SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.
◆ SCIP_DECL_BENDERSINIT()
|
static |
! [SnippetBendersFreeDefault] initialization method of Benders' decomposition (called after problem was transformed)
Definition at line 342 of file benders_default.c.
References createVariableMappings(), NULL, SCIP_CALL, and SCIP_OKAY.
◆ SCIP_DECL_BENDERSEXIT()
|
static |
deinitialization method of Benders' decomposition (called before transformed problem is freed and the Benders' decomposition is active)
Definition at line 357 of file benders_default.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPbendersGetData(), SCIPfreeBlockMemoryArray, SCIPhashmapFree(), and SCIPreleaseVar().
◆ SCIP_DECL_BENDERSGETVAR()
|
static |
mapping method between the master problem variables and the subproblem variables of Benders' decomposition ! [SnippetBendersGetvarDefault]
Definition at line 396 of file benders_default.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbendersGetData(), SCIPhashmapGetImage(), SCIPhashmapGetImageInt(), and SCIPvarGetOrigvarSum().
◆ SCIP_DECL_BENDERSCREATESUB()
|
static |
! [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().