benders_default.c
Go to the documentation of this file.
20 * The default Benders' decomposition plugin is provided to simplify the interaction the Benders' decomposition
21 * framework within SCIP. This plugin is included in the SCIP package by default. Using the default Benders'
26 * where "master problem" is a SCIP instance of the master problem, "array of subproblems" is an array of SCIP instances
27 * that are the Benders' decomposition subproblems and "number of subproblems" is an integer indicating the number of
30 * A key feature of the default Benders' decomposition plugin is the automatic generation of the variable mapping
33 * In the traditional application of Benders' decomposition, master problem variables are fixed to a solution value and
34 * modify the RHS of the second stage constraints. The implementation within SCIP requires that a variable is created
35 * in the subproblem for every master problem variable that appears in the subproblem constraints. This variable MUST
36 * have the same name as the corresponding variable in the master problem. This name is used to automatically generate
41 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
61 #define BENDERS_SHAREAUXVARS FALSE /**< should this Benders' share the highest priority Benders' aux vars */
72 SCIP_HASHMAP* mastervartosubindex;/**< hash map from the master variable to an index for the subproblemn variables */
73 SCIP_HASHMAP* subvartomastervar; /**< hashmap from the subproblem variable to the master variable */
74 SCIP_VAR*** subproblemvars; /**< the subproblem variables corresponding to master problem variables */
115 /** Creates the variable mappings between the master problem and the corresponding variable in the subproblem.
117 * TODO: add the functionality to allow the user to provide an array of hashmaps for mapping between the master problem
151 SCIP_CALL( SCIPhashmapCreate(&bendersdata->subvartomastervar, SCIPblkmem(scip), nvars*nsubproblems) );
158 /* this loop stores a mapping between the master problem variables and their counterpart in the subproblems. For each
159 * master problem variable, the variable name is used to search for any corresponding variables in each of the
160 * subproblems. If a corresponding variable exists, then a mapping is inserted into subvartomastervar and
173 * NOTE: This retrieved variable is the original variable. It may be a bug in regards to other parts of the code.
174 * The process maps the subproblem variable to the original master variable. It was original supposed to be a
189 /* find the corresponding subproblem variable for a given master problem variable using the variable name. */
227 * NOTE: this method uses the same subproblems as the main SCIP. In a parallel setting, this will not be thread safe.
235 SCIP_CALL( SCIPcreateBendersDefault(scip, bendersdata->subproblems, bendersdata->nsubproblems) );
290 /** mapping method between the master problem variables and the subproblem variables of Benders' decomposition */
310 /* The variable needs to be transformed back into an original variable. If the variable is already original, then
324 /* The variable needs to be transformed back into an original variable. If the variable is already original, then
330 * NOTE: Currently the original variable is being used. This may not be correct and should be the transformed
341 /** the method for creating the Benders' decomposition subproblem. This method is called during the initialisation stage
344 * This method must create the SCIP instance for the subproblem and add the required variables and constraints. In
345 * addition, the settings required for the solving the problem must be set here. However, some settings will be
346 * overridden by the standard solving method included in the Benders' decomposition framework. If a special solving
374 * @note Every variable that appears in the subproblem constraints must be created in the corresponding subproblem with
377 * @note The default Benders' decomposition implementation relies on unique variable names in the master problem and in
378 * each of the subproblems. This is required because a variable mapping is made between the master problem variables and
402 SCIPerrorMessage("The number of restarts is fixed to %d. The default Benders' decomposition requires the number"
436 SCIP_CALL( SCIPincludeBendersBasic(scip, &benders, BENDERS_NAME, BENDERS_DESC, BENDERS_PRIORITY, BENDERS_CUTLP,
437 BENDERS_CUTPSEUDO, BENDERS_CUTRELAX, BENDERS_SHAREAUXVARS, bendersGetvarDefault, bendersCreatesubDefault,
public methods for SCIP parameter handling
Definition: struct_scip.h:58
public methods for memory management
static SCIP_DECL_BENDERSINIT(bendersInitDefault)
Definition: benders_default.c:278
Definition: struct_var.h:198
SCIP_RETCODE SCIPsetBendersInit(SCIP *scip, SCIP_BENDERS *benders, SCIP_DECL_BENDERSINIT((*bendersinit)))
Definition: scip_benders.c:312
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
public methods for Benders' decomposition
SCIP_RETCODE SCIPcreateBendersDefault(SCIP *scip, SCIP **subproblems, int nsubproblems)
Definition: benders_default.c:381
public methods for problem variables
SCIP_RETCODE SCIPincludeBendersDefault(SCIP *scip)
Definition: benders_default.c:420
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
static SCIP_DECL_BENDERSFREE(bendersFreeDefault)
Definition: benders_default.c:244
Definition: struct_benders.h:38
Definition: struct_misc.h:121
public methods for Benders decomposition
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:291
static SCIP_RETCODE createVariableMappings(SCIP *scip, SCIP_BENDERS *benders)
Definition: benders_default.c:122
static SCIP_DECL_BENDERSCREATESUB(bendersCreatesubDefault)
Definition: benders_default.c:350
SCIP_RETCODE SCIPincludeBendersDefaultCuts(SCIP *scip, SCIP_BENDERS *benders)
Definition: bendersdefcuts.c:27
SCIP_BENDERSDATA * SCIPbendersGetData(SCIP_BENDERS *benders)
Definition: benders.c:4030
SCIP_RETCODE SCIPincludeBendersBasic(SCIP *scip, SCIP_BENDERS **bendersptr, const char *name, const char *desc, int priority, SCIP_Bool cutlp, SCIP_Bool cutpseudo, SCIP_Bool cutrelax, SCIP_Bool shareauxvars, SCIP_DECL_BENDERSGETVAR((*bendersgetvar)), SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)), SCIP_BENDERSDATA *bendersdata)
Definition: scip_benders.c:218
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:341
Definition: type_retcode.h:33
public methods for problem copies
Definition: type_retcode.h:34
static SCIP_DECL_BENDERSCOPY(bendersCopyDefault)
Definition: benders_default.c:217
SCIP_BENDERS * SCIPfindBenders(SCIP *scip, const char *name)
Definition: scip_benders.c:536
public data structures and miscellaneous methods
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:578
SCIP_RETCODE SCIPsetBendersCopy(SCIP *scip, SCIP_BENDERS *benders, SCIP_DECL_BENDERSCOPY((*benderscopy)))
Definition: scip_benders.c:264
SCIP_RETCODE SCIPaddBendersSubproblem(SCIP *scip, SCIP_BENDERS *benders, SCIP *subproblem)
Definition: scip_benders.c:784
SCIP_RETCODE SCIPvarGetOrigvarSum(SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: var.c:12253
public methods for message output
SCIP_RETCODE SCIPsetBendersFree(SCIP *scip, SCIP_BENDERS *benders, SCIP_DECL_BENDERSFREE((*bendersfree)))
Definition: scip_benders.c:288
default Benders' decomposition plugin
static SCIP_RETCODE createBendersData(SCIP *scip, SCIP **subproblems, SCIP_BENDERSDATA **bendersdata, int nsubproblems)
Definition: benders_default.c:89
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:2874
SCIP_RETCODE SCIPactivateBenders(SCIP *scip, SCIP_BENDERS *benders, int nsubproblems)
Definition: scip_benders.c:598
Definition: objbenders.h:33
public methods for global and local (sub)problems
static SCIP_DECL_BENDERSGETVAR(bendersGetvarDefault)
Definition: benders_default.c:293