methods for Benders' decomposition
Definition in file benders.c.
#include <assert.h>
#include <string.h>
#include "scip/def.h"
#include "scip/set.h"
#include "scip/clock.h"
#include "scip/dcmp.h"
#include "scip/paramset.h"
#include "scip/lp.h"
#include "scip/prob.h"
#include "scip/pricestore.h"
#include "scip/scip.h"
#include "scip/scipdefplugins.h"
#include "scip/benders.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/cons_linear.h"
#include "scip/cons_nonlinear.h"
#include "scip/struct_benders.h"
#include "scip/struct_benderscut.h"
#include "scip/benderscut.h"
Go to the source code of this file.
Macros | |
#define | SCIP_DEFAULT_TRANSFERCUTS FALSE /** should Benders' cuts generated in LNS heuristics be transferred to the main SCIP instance? */ |
#define | SCIP_DEFAULT_CUTSASCONSS TRUE /** should the transferred cuts be added as constraints? */ |
#define | SCIP_DEFAULT_LNSCHECK TRUE /** should the Benders' decomposition be used in LNS heuristics */ |
#define | SCIP_DEFAULT_LNSMAXDEPTH -1 /** maximum depth at which the LNS check is performed */ |
#define | SCIP_DEFAULT_LNSMAXCALLS 10 /** the maximum number of Benders' decomposition calls in LNS heuristics */ |
#define | SCIP_DEFAULT_LNSMAXCALLSROOT 0 /** the maximum number of root node Benders' decomposition calls in LNS heuristics */ |
#define | SCIP_DEFAULT_SUBPROBFRAC 1.0 /** fraction of subproblems that are solved in each iteration */ |
#define | SCIP_DEFAULT_UPDATEAUXVARBOUND FALSE /** should the auxiliary variable lower bound be updated by solving the subproblem */ |
#define | SCIP_DEFAULT_AUXVARSIMPLINT FALSE /** set the auxiliary variables as implint if the subproblem objective is integer */ |
#define | SCIP_DEFAULT_CUTCHECK TRUE /** should cuts be generated during the checking of solutions? */ |
#define | SCIP_DEFAULT_STRENGTHENMULT 0.5 /** the convex combination multiplier for the cut strengthening */ |
#define | SCIP_DEFAULT_NOIMPROVELIMIT 5 /** the maximum number of cut strengthening without improvement */ |
#define | SCIP_DEFAULT_STRENGTHENPERTURB 1e-06 /** the amount by which the cut strengthening solution is perturbed */ |
#define | SCIP_DEFAULT_STRENGTHENENABLED FALSE /** enable the core point cut strengthening approach */ |
#define | SCIP_DEFAULT_STRENGTHENINTPOINT 'r' /** where should the strengthening interior point be sourced from ('l'p relaxation, 'f'irst solution, 'i'ncumbent solution, 'r'elative interior point, vector of 'o'nes, vector of 'z'eros) */ |
#define | SCIP_DEFAULT_NUMTHREADS 1 /** the number of parallel threads to use when solving the subproblems */ |
#define | SCIP_DEFAULT_EXECFEASPHASE FALSE /** should a feasibility phase be executed during the root node processing */ |
#define | SCIP_DEFAULT_SLACKVARCOEF 1e+6 /** the initial objective coefficient of the slack variables in the subproblem */ |
#define | SCIP_DEFAULT_MAXSLACKVARCOEF 1e+9 /** the maximal objective coefficient of the slack variables in the subproblem */ |
#define | SCIP_DEFAULT_CHECKCONSCONVEXITY TRUE /** should the constraints of the subproblem be checked for convexity? */ |
#define | SCIP_DEFAULT_NLPITERLIMIT 10000 /** iteration limit for NLP solver */ |
#define | BENDERS_MAXPSEUDOSOLS |
#define | BENDERS_ARRAYSIZE 1000 |
#define | AUXILIARYVAR_NAME "##bendersauxiliaryvar" /** the name for the Benders' auxiliary variables in the master problem */ |
#define | SLACKVAR_NAME |
#define | NLINEARCONSHDLRS 5 |
#define | NODEFOCUS_EVENTHDLR_NAME "bendersnodefocus" |
#define | NODEFOCUS_EVENTHDLR_DESC "node focus event handler for Benders' decomposition" |
#define | MIPNODEFOCUS_EVENTHDLR_NAME "bendersmipsolvenodefocus" |
#define | MIPNODEFOCUS_EVENTHDLR_DESC "node focus event handler for the MIP solve method for Benders' decomposition" |
#define | UPPERBOUND_EVENTHDLR_NAME "bendersupperbound" |
#define | UPPERBOUND_EVENTHDLR_DESC "found solution event handler to terminate subproblem solve for a given upper bound" |
#define | NODESOLVED_EVENTHDLR_NAME "bendersnodesolved" |
#define | NODESOLVED_EVENTHDLR_DESC "node solved event handler for the Benders' integer cuts" |
#define SCIP_DEFAULT_TRANSFERCUTS FALSE /** should Benders' cuts generated in LNS heuristics be transferred to the main SCIP instance? */ |
Definition at line 58 of file benders.c.
Referenced by doBendersCreate().
#define SCIP_DEFAULT_CUTSASCONSS TRUE /** should the transferred cuts be added as constraints? */ |
Definition at line 59 of file benders.c.
Referenced by doBendersCreate().
#define SCIP_DEFAULT_LNSCHECK TRUE /** should the Benders' decomposition be used in LNS heuristics */ |
Definition at line 60 of file benders.c.
Referenced by doBendersCreate().
#define SCIP_DEFAULT_LNSMAXDEPTH -1 /** maximum depth at which the LNS check is performed */ |
Definition at line 61 of file benders.c.
Referenced by doBendersCreate().
#define SCIP_DEFAULT_LNSMAXCALLS 10 /** the maximum number of Benders' decomposition calls in LNS heuristics */ |
Definition at line 62 of file benders.c.
Referenced by doBendersCreate().
#define SCIP_DEFAULT_LNSMAXCALLSROOT 0 /** the maximum number of root node Benders' decomposition calls in LNS heuristics */ |
Definition at line 63 of file benders.c.
Referenced by doBendersCreate().
#define SCIP_DEFAULT_SUBPROBFRAC 1.0 /** fraction of subproblems that are solved in each iteration */ |
Definition at line 64 of file benders.c.
Referenced by doBendersCreate().
#define SCIP_DEFAULT_UPDATEAUXVARBOUND FALSE /** should the auxiliary variable lower bound be updated by solving the subproblem */ |
Definition at line 65 of file benders.c.
Referenced by doBendersCreate().
#define SCIP_DEFAULT_AUXVARSIMPLINT FALSE /** set the auxiliary variables as implint if the subproblem objective is integer */ |
Definition at line 66 of file benders.c.
Referenced by doBendersCreate().
#define SCIP_DEFAULT_CUTCHECK TRUE /** should cuts be generated during the checking of solutions? */ |
Definition at line 67 of file benders.c.
Referenced by doBendersCreate().
#define SCIP_DEFAULT_STRENGTHENMULT 0.5 /** the convex combination multiplier for the cut strengthening */ |
Definition at line 68 of file benders.c.
Referenced by doBendersCreate().
#define SCIP_DEFAULT_NOIMPROVELIMIT 5 /** the maximum number of cut strengthening without improvement */ |
Definition at line 69 of file benders.c.
Referenced by doBendersCreate().
#define SCIP_DEFAULT_STRENGTHENPERTURB 1e-06 /** the amount by which the cut strengthening solution is perturbed */ |
Definition at line 70 of file benders.c.
Referenced by doBendersCreate().
#define SCIP_DEFAULT_STRENGTHENENABLED FALSE /** enable the core point cut strengthening approach */ |
Definition at line 71 of file benders.c.
Referenced by doBendersCreate().
#define SCIP_DEFAULT_STRENGTHENINTPOINT 'r' /** where should the strengthening interior point be sourced from ('l'p relaxation, 'f'irst solution, 'i'ncumbent solution, 'r'elative interior point, vector of 'o'nes, vector of 'z'eros) */ |
Definition at line 72 of file benders.c.
Referenced by doBendersCreate().
#define SCIP_DEFAULT_NUMTHREADS 1 /** the number of parallel threads to use when solving the subproblems */ |
Definition at line 73 of file benders.c.
Referenced by doBendersCreate().
#define SCIP_DEFAULT_EXECFEASPHASE FALSE /** should a feasibility phase be executed during the root node processing */ |
Definition at line 74 of file benders.c.
Referenced by doBendersCreate().
#define SCIP_DEFAULT_SLACKVARCOEF 1e+6 /** the initial objective coefficient of the slack variables in the subproblem */ |
Definition at line 75 of file benders.c.
Referenced by doBendersCreate().
#define SCIP_DEFAULT_MAXSLACKVARCOEF 1e+9 /** the maximal objective coefficient of the slack variables in the subproblem */ |
Definition at line 76 of file benders.c.
Referenced by doBendersCreate().
#define SCIP_DEFAULT_CHECKCONSCONVEXITY TRUE /** should the constraints of the subproblem be checked for convexity? */ |
Definition at line 77 of file benders.c.
Referenced by doBendersCreate().
#define SCIP_DEFAULT_NLPITERLIMIT 10000 /** iteration limit for NLP solver */ |
Definition at line 78 of file benders.c.
Referenced by doBendersCreate().
#define BENDERS_MAXPSEUDOSOLS |
Definition at line 80 of file benders.c.
Referenced by SCIPbendersExec().
#define BENDERS_ARRAYSIZE 1000 |
the initial size of the added constraints/cuts arrays
Definition at line 82 of file benders.c.
Referenced by SCIPbendersInit().
#define AUXILIARYVAR_NAME "##bendersauxiliaryvar" /** the name for the Benders' auxiliary variables in the master problem */ |
Definition at line 84 of file benders.c.
Referenced by addAuxiliaryVariablesToMaster(), assignAuxiliaryVariables(), and SCIPbendersGetVar().
#define SLACKVAR_NAME |
Definition at line 85 of file benders.c.
Referenced by addSlackVars(), createAuxiliaryNonlinearSubproblem(), SCIPbendersSetupSubproblem(), and SCIPbendersSolSlackVarsActive().
#define NLINEARCONSHDLRS 5 |
Definition at line 86 of file benders.c.
Referenced by addSlackVarsToConstraints(), and checkSubproblemConvexity().
#define NODEFOCUS_EVENTHDLR_NAME "bendersnodefocus" |
Definition at line 89 of file benders.c.
Referenced by initialiseLPSubproblem(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXIT(), SCIP_DECL_EVENTEXITSOL(), SCIP_DECL_EVENTFREE(), and SCIP_DECL_EVENTINITSOL().
#define NODEFOCUS_EVENTHDLR_DESC "node focus event handler for Benders' decomposition" |
Definition at line 90 of file benders.c.
Referenced by initialiseLPSubproblem().
#define MIPNODEFOCUS_EVENTHDLR_NAME "bendersmipsolvenodefocus" |
Definition at line 92 of file benders.c.
Referenced by createSubproblems(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXIT(), SCIP_DECL_EVENTEXITSOL(), SCIP_DECL_EVENTFREE(), SCIP_DECL_EVENTINITSOL(), SCIPbendersComputeSubproblemLowerbound(), and SCIPbendersSolveSubproblemCIP().
#define MIPNODEFOCUS_EVENTHDLR_DESC "node focus event handler for the MIP solve method for Benders' decomposition" |
Definition at line 93 of file benders.c.
Referenced by createSubproblems().
#define UPPERBOUND_EVENTHDLR_NAME "bendersupperbound" |
Definition at line 95 of file benders.c.
Referenced by createSubproblems(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXIT(), SCIP_DECL_EVENTEXITSOL(), SCIP_DECL_EVENTFREE(), SCIP_DECL_EVENTINITSOL(), and updateEventhdlrUpperbound().
#define UPPERBOUND_EVENTHDLR_DESC "found solution event handler to terminate subproblem solve for a given upper bound" |
Definition at line 96 of file benders.c.
Referenced by createSubproblems().
#define NODESOLVED_EVENTHDLR_NAME "bendersnodesolved" |
Definition at line 98 of file benders.c.
Referenced by SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTINITSOL(), and SCIPbendersActivate().
#define NODESOLVED_EVENTHDLR_DESC "node solved event handler for the Benders' integer cuts" |
Definition at line 99 of file benders.c.
Referenced by SCIPbendersActivate().
|
static |
initialises the members of the eventhandler data
scip | the SCIP data structure |
eventhdlrdata | the event handler data |
Definition at line 116 of file benders.c.
References assert(), FALSE, NULL, SCIP_OKAY, and SCIPinfinity().
Referenced by createSubproblems(), exitEventhandler(), and initialiseLPSubproblem().
|
static |
initsol method for the event handlers
scip | the SCIP data structure |
eventhdlr | the event handlers data structure |
eventtype | event type mask to select events to catch |
Definition at line 134 of file benders.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcatchEvent(), and SCIPeventhdlrGetData().
Referenced by SCIP_DECL_EVENTINITSOL(), SCIP_DECL_EVENTINITSOL(), and SCIP_DECL_EVENTINITSOL().
|
static |
the exit sol method for the event handlers
scip | the SCIP data structure |
eventhdlr | the event handlers data structure |
eventtype | event type mask to select events to catch |
Definition at line 154 of file benders.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPdropEvent(), and SCIPeventhdlrGetData().
Referenced by SCIP_DECL_EVENTEXITSOL(), SCIP_DECL_EVENTEXITSOL(), and SCIP_DECL_EVENTEXITSOL().
|
static |
the exit method for the event handlers
scip | the SCIP data structure |
eventhdlr | the event handlers data structure |
Definition at line 178 of file benders.c.
References assert(), initEventhandlerData(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPeventhdlrGetData().
Referenced by SCIP_DECL_EVENTEXIT(), SCIP_DECL_EVENTEXIT(), and SCIP_DECL_EVENTEXIT().
|
static |
free method for the event handler
scip | the SCIP data structure |
eventhdlr | the event handlers data structure |
Definition at line 198 of file benders.c.
References assert(), NULL, SCIP_OKAY, SCIPeventhdlrGetData(), SCIPeventhdlrSetData(), and SCIPfreeBlockMemory.
Referenced by SCIP_DECL_EVENTFREE(), SCIP_DECL_EVENTFREE(), and SCIP_DECL_EVENTFREE().
|
static |
exec the event handler
Definition at line 224 of file benders.c.
References assert(), NODEFOCUS_EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_NODEFOCUSED, SCIP_OKAY, SCIPdropEvent(), SCIPeventhdlrGetData(), SCIPeventhdlrGetName(), and SCIPinterruptSolve().
|
static |
solving process initialization method of event handler (called when branch and bound process is about to begin)
Definition at line 246 of file benders.c.
References assert(), initsolEventhandler(), NODEFOCUS_EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_NODEFOCUSED, SCIP_OKAY, and SCIPeventhdlrGetName().
|
static |
solving process deinitialization method of event handler (called before branch and bound process data is freed)
Definition at line 259 of file benders.c.
References assert(), exitsolEventhandler(), NODEFOCUS_EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_NODEFOCUSED, SCIP_OKAY, and SCIPeventhdlrGetName().
|
static |
deinitialization method of event handler (called before transformed problem is freed)
Definition at line 272 of file benders.c.
References assert(), exitEventhandler(), NODEFOCUS_EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, and SCIPeventhdlrGetName().
|
static |
deinitialization method of event handler (called before transformed problem is freed)
Definition at line 285 of file benders.c.
References assert(), freeEventhandler(), NODEFOCUS_EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, and SCIPeventhdlrGetName().
|
static |
exec the event handler
Definition at line 301 of file benders.c.
References assert(), MIPNODEFOCUS_EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_NODEFOCUSED, SCIP_OKAY, SCIPdropEvent(), SCIPeventhdlrGetData(), SCIPeventhdlrGetName(), and SCIPinterruptSolve().
|
static |
solving process initialization method of event handler (called when branch and bound process is about to begin)
Definition at line 327 of file benders.c.
References assert(), initsolEventhandler(), MIPNODEFOCUS_EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_NODEFOCUSED, SCIP_OKAY, and SCIPeventhdlrGetName().
|
static |
solving process deinitialization method of event handler (called before branch and bound process data is freed)
Definition at line 340 of file benders.c.
References assert(), exitsolEventhandler(), MIPNODEFOCUS_EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_NODEFOCUSED, SCIP_OKAY, and SCIPeventhdlrGetName().
|
static |
deinitialization method of event handler (called before transformed problem is freed)
Definition at line 353 of file benders.c.
References assert(), exitEventhandler(), MIPNODEFOCUS_EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, and SCIPeventhdlrGetName().
|
static |
deinitialization method of event handler (called before transformed problem is freed)
Definition at line 366 of file benders.c.
References assert(), freeEventhandler(), MIPNODEFOCUS_EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, and SCIPeventhdlrGetName().
|
static |
exec the event handler
Definition at line 381 of file benders.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPeventhdlrGetData(), SCIPeventhdlrGetName(), SCIPgetBestSol(), SCIPgetObjsense(), SCIPgetSolOrigObj(), SCIPinterruptSolve(), SCIPisLT(), and UPPERBOUND_EVENTHDLR_NAME.
|
static |
solving process initialization method of event handler (called when branch and bound process is about to begin)
Definition at line 405 of file benders.c.
References assert(), initsolEventhandler(), NULL, SCIP_CALL, SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_OKAY, SCIPeventhdlrGetName(), and UPPERBOUND_EVENTHDLR_NAME.
|
static |
solving process deinitialization method of event handler (called before branch and bound process data is freed)
Definition at line 418 of file benders.c.
References assert(), exitsolEventhandler(), NULL, SCIP_CALL, SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_OKAY, SCIPeventhdlrGetName(), and UPPERBOUND_EVENTHDLR_NAME.
|
static |
deinitialization method of event handler (called before transformed problem is freed)
Definition at line 431 of file benders.c.
References assert(), exitEventhandler(), NULL, SCIP_CALL, SCIP_OKAY, SCIPeventhdlrGetName(), and UPPERBOUND_EVENTHDLR_NAME.
|
static |
deinitialization method of event handler (called before transformed problem is freed)
Definition at line 444 of file benders.c.
References assert(), freeEventhandler(), NULL, SCIP_CALL, SCIP_OKAY, SCIPeventhdlrGetName(), and UPPERBOUND_EVENTHDLR_NAME.
|
static |
updates the upper bound in the event handler data
benders | Benders' decomposition |
probnumber | the subproblem number |
upperbound | the upper bound value |
Definition at line 457 of file benders.c.
References assert(), NULL, SCIP_OKAY, SCIP_Real, SCIPbendersSubproblem(), SCIPeventhdlrGetData(), SCIPfindEventhdlr(), and UPPERBOUND_EVENTHDLR_NAME.
Referenced by SCIPbendersExecSubproblemSolve().
|
static |
Updates the cut constant of the Benders' cuts data. This function solves the master problem with only the auxiliary variables in the objective function.
masterprob | the SCIP instance of the master problem |
benders | Benders' decomposition |
Definition at line 486 of file benders.c.
References assert(), cutoff, i, lperror, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_COLUMN, SCIPbendersGetAuxiliaryVar(), SCIPbendersGetNSubproblems(), SCIPbendersGetSubproblemLowerbound(), SCIPbendersUpdateSubproblemLowerbound(), SCIPchgVarObjProbing(), SCIPdebugMsg, SCIPendProbing(), SCIPgetNVars(), SCIPgetSolTransObj(), SCIPgetVars(), SCIPinDive(), SCIPinProbing(), SCIPinRepropagation(), SCIPisInfinity(), SCIPsolveProbingLP(), SCIPstartProbing(), SCIPvarGetStatus(), and vars.
Referenced by SCIP_DECL_EVENTEXEC().
|
static |
exec the event handler
Definition at line 553 of file benders.c.
References assert(), NODESOLVED_EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_NODESOLVED, SCIP_OKAY, SCIPbendersGetNConvexSubproblems(), SCIPbendersGetNSubproblems(), SCIPdropEvent(), SCIPeventhdlrGetData(), SCIPeventhdlrGetName(), and updateSubproblemLowerbound().
|
static |
solving process initialization method of event handler (called when branch and bound process is about to begin)
Definition at line 576 of file benders.c.
References assert(), NODESOLVED_EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_NODESOLVED, SCIP_OKAY, SCIPbendersIsActive(), SCIPbendersOnlyCheckConvexRelax(), SCIPcatchEvent(), SCIPeventhdlrGetData(), SCIPeventhdlrGetName(), SCIPgetSubscipsOff(), and SCIP_Benders::threadsafe.
|
static |
comparison method for sorting the subproblems. The subproblem that has been called the least is prioritised
Definition at line 606 of file benders.c.
References assert(), SCIP_SubproblemSolveStat::avgiter, SCIP_SubproblemSolveStat::idx, MAX, SCIP_SubproblemSolveStat::ncalls, and NULL.
|
static |
adds the auxiliary variables to the Benders' decomposition master problem
scip | SCIP data structure |
benders | Benders' decomposition structure |
Definition at line 674 of file benders.c.
References AUXILIARYVAR_NAME, SCIP_Benders::auxiliaryvars, SCIP_Benders::auxvarsimplint, FALSE, i, NULL, SCIP_Bool, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIPaddVar(), SCIPaddVarLocksType(), SCIPallocBlockMemory, SCIPbendersGetAuxiliaryVar(), SCIPbendersGetName(), SCIPbendersGetNSubproblems(), SCIPbendersShareAuxVars(), SCIPbendersSubproblem(), SCIPcaptureVar(), SCIPcreateVarBasic(), SCIPfreeBlockMemory, SCIPgetBenders(), SCIPinfinity(), SCIPisObjIntegral(), SCIPsnprintf(), SCIPvarSetData(), SCIP_Benders::subproblowerbound, and TRUE.
Referenced by SCIPbendersInitpre().
|
static |
assigns the copied auxiliary variables in the target SCIP to the target Benders' decomposition data
scip | SCIP data structure, the target scip |
benders | Benders' decomposition |
Definition at line 747 of file benders.c.
References assert(), AUXILIARYVAR_NAME, SCIP_Benders::auxiliaryvars, FALSE, i, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPABORT, SCIPallocBlockMemory, SCIPbendersGetName(), SCIPbendersGetNSubproblems(), SCIPbendersShareAuxVars(), SCIPcaptureVar(), SCIPfindVar(), SCIPfreeBlockMemory, SCIPgetBenders(), SCIPgetSubscipDepth(), SCIPsnprintf(), SCIPvarGetTransVar(), SCIPvarSetData(), and TRUE.
Referenced by SCIPbendersInit().
|
static |
sets the subproblem objective value array to -infinity
benders | the Benders' decomposition structure |
set | global SCIP settings |
Definition at line 831 of file benders.c.
References assert(), i, NULL, SCIP_Real, SCIPbendersGetNSubproblems(), SCIPbendersSetSubproblemObjval(), SCIPbendersSubproblem(), SCIPinfinity(), and SCIPsetInfinity().
Referenced by SCIPbendersExec().
|
static |
method to call, when the priority of a Benders' decomposition was changed
Definition at line 871 of file benders.c.
References assert(), NULL, SCIP_OKAY, SCIPparamGetData(), SCIPparamGetInt(), and SCIPsetBendersPriority().
|
static |
creates a variable mapping between the master problem variables of the source scip and the sub scip
benders | Benders' decomposition of the target SCIP instance |
sourceset | global SCIP settings from the source SCIP |
varmap | a hashmap to store the mapping of source variables corresponding target variables; must not be NULL |
Definition at line 886 of file benders.c.
References assert(), i, SCIP_Benders::iscopy, SCIP_Benders::mastervarsmap, NULL, nvars, SCIP_Set::scip, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPcaptureVar(), SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapGetImage(), SCIPhashmapInsert(), and vars.
Referenced by SCIPbendersCopyInclude().
SCIP_RETCODE SCIPbendersCopyInclude | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | sourceset, | ||
SCIP_SET * | targetset, | ||
SCIP_HASHMAP * | varmap, | ||
SCIP_Bool | threadsafe, | ||
SCIP_Bool * | valid ) |
copies the given Benders' decomposition to a new SCIP
benders | Benders' decomposition |
sourceset | SCIP_SET of SCIP to copy from |
targetset | SCIP_SET of SCIP to copy to |
varmap | a hashmap to store the mapping of source variables corresponding target variables; if NULL, then the transfer of cuts is not possible |
threadsafe | must the Benders' decomposition copy be thread safe |
valid | was the copying process valid? |
Definition at line 926 of file benders.c.
References assert(), SCIP_Set::benders_copybenders, SCIP_Benders::benderscuts, createMasterVarMapping(), FALSE, i, SCIP_Benders::iscopy, SCIP_Benders::lnscheck, SCIP_Benders::lnsmaxcalls, SCIP_Benders::lnsmaxcallsroot, SCIP_Benders::lnsmaxdepth, SCIP_Benders::mastervarsmap, SCIP_Benders::nbenderscuts, NULL, SCIP_Set::scip, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPbenderscutCopyInclude(), SCIPbendersGetName(), SCIPbendersIsActive(), SCIPbendersSortBenderscuts(), SCIPsetDebugMsg, SCIPsetFindBenders(), SCIP_Benders::sourcescip, SCIP_Benders::threadsafe, TRUE, and valid.
Referenced by SCIPcopyBenders().
|
static |
internal method for creating a Benders' decomposition structure
benders | pointer to Benders' decomposition data structure |
set | global SCIP settings |
messagehdlr | message handler |
blkmem | block memory for parameter settings |
name | name of Benders' decomposition |
desc | description of Benders' decomposition |
priority | priority of the Benders' decomposition |
cutlp | should Benders' cuts be generated for LP solutions |
cutpseudo | should Benders' cuts be generated for pseudo solutions |
cutrelax | should Benders' cuts be generated for relaxation solutions |
shareauxvars | should this Benders' use the highest priority Benders aux vars |
bendersdata | Benders' decomposition data |
Definition at line 997 of file benders.c.
References assert(), BMSallocMemory, BMSclearMemory, BMSduplicateMemoryArray, FALSE, NULL, paramname, SCIP_ALLOC, SCIP_Bool, SCIP_CALL, SCIP_CLOCKTYPE_DEFAULT, SCIP_DECL_BENDERSCOPY, SCIP_DECL_BENDERSEXIT, SCIP_DECL_BENDERSFREE, SCIP_DECL_BENDERSINIT, SCIP_DEFAULT_AUXVARSIMPLINT, SCIP_DEFAULT_CHECKCONSCONVEXITY, SCIP_DEFAULT_CUTCHECK, SCIP_DEFAULT_CUTSASCONSS, SCIP_DEFAULT_EXECFEASPHASE, SCIP_DEFAULT_LNSCHECK, SCIP_DEFAULT_LNSMAXCALLS, SCIP_DEFAULT_LNSMAXCALLSROOT, SCIP_DEFAULT_LNSMAXDEPTH, SCIP_DEFAULT_MAXSLACKVARCOEF, SCIP_DEFAULT_NLPITERLIMIT, SCIP_DEFAULT_NOIMPROVELIMIT, SCIP_DEFAULT_NUMTHREADS, SCIP_DEFAULT_SLACKVARCOEF, SCIP_DEFAULT_STRENGTHENENABLED, SCIP_DEFAULT_STRENGTHENINTPOINT, SCIP_DEFAULT_STRENGTHENMULT, SCIP_DEFAULT_STRENGTHENPERTURB, SCIP_DEFAULT_SUBPROBFRAC, SCIP_DEFAULT_TRANSFERCUTS, SCIP_DEFAULT_UPDATEAUXVARBOUND, SCIP_INVALIDCALL, SCIP_MAXSTRLEN, SCIP_MAXTREEDEPTH, SCIP_NLPPARAM_DEFAULT, SCIP_OKAY, SCIPclockCreate(), SCIPerrorMessage, SCIPsetAddBoolParam(), SCIPsetAddCharParam(), SCIPsetAddIntParam(), SCIPsetAddRealParam(), SCIPsetInfinity(), SCIPsnprintf(), and TRUE.
Referenced by SCIPbendersCreate().
SCIP_RETCODE SCIPbendersCreate | ( | SCIP_BENDERS ** | benders, |
SCIP_SET * | set, | ||
SCIP_MESSAGEHDLR * | messagehdlr, | ||
BMS_BLKMEM * | blkmem, | ||
const char * | name, | ||
const char * | desc, | ||
int | priority, | ||
SCIP_Bool | cutlp, | ||
SCIP_Bool | cutpseudo, | ||
SCIP_Bool | cutrelax, | ||
SCIP_Bool | shareauxvars, | ||
SCIP_DECL_BENDERSCOPY((*benderscopy)) | , | ||
SCIP_DECL_BENDERSFREE((*bendersfree)) | , | ||
SCIP_DECL_BENDERSINIT((*bendersinit)) | , | ||
SCIP_DECL_BENDERSEXIT((*bendersexit)) | , | ||
SCIP_DECL_BENDERSINITPRE((*bendersinitpre)) | , | ||
SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)) | , | ||
SCIP_DECL_BENDERSINITSOL((*bendersinitsol)) | , | ||
SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)) | , | ||
SCIP_DECL_BENDERSGETVAR((*bendersgetvar)) | , | ||
SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)) | , | ||
SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)) | , | ||
SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)) | , | ||
SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)) | , | ||
SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)) | , | ||
SCIP_DECL_BENDERSFREESUB((*bendersfreesub)) | , | ||
SCIP_BENDERSDATA * | bendersdata ) |
creates a Benders' decomposition structure
To use the Benders' decomposition for solving a problem, it first has to be activated with a call to SCIPactivateBenders().
benders | pointer to Benders' decomposition data structure |
set | global SCIP settings |
messagehdlr | message handler |
blkmem | block memory for parameter settings |
name | name of Benders' decomposition |
desc | description of Benders' decomposition |
priority | priority of the Benders' decomposition |
cutlp | should Benders' cuts be generated for LP solutions |
cutpseudo | should Benders' cuts be generated for pseudo solutions |
cutrelax | should Benders' cuts be generated for relaxation solutions |
shareauxvars | should this Benders' use the highest priority Benders aux vars |
bendersdata | Benders' decomposition data |
Definition at line 1206 of file benders.c.
References assert(), doBendersCreate(), NULL, SCIP_Bool, SCIP_CALL_FINALLY, SCIP_DECL_BENDERSCOPY, SCIP_DECL_BENDERSEXIT, SCIP_DECL_BENDERSFREE, SCIP_DECL_BENDERSINIT, SCIP_OKAY, and SCIPbendersFree().
Referenced by SCIPincludeBenders(), and SCIPincludeBendersBasic().
|
static |
releases the variables that have been captured in the hashmap
scip | the SCIP data structure |
benders | Benders' decomposition |
Definition at line 1251 of file benders.c.
References assert(), i, SCIP_Benders::mastervarsmap, NULL, SCIP_CALL, SCIP_OKAY, SCIPhashmapEntryGetImage(), SCIPhashmapGetEntry(), SCIPhashmapGetNEntries(), SCIPreleaseVar(), and var.
Referenced by SCIPbendersFree().
SCIP_RETCODE SCIPbendersFree | ( | SCIP_BENDERS ** | benders, |
SCIP_SET * | set ) |
calls destructor and frees memory of Benders' decomposition
benders | pointer to Benders' decomposition data structure |
set | global SCIP settings |
Definition at line 1285 of file benders.c.
References assert(), BMSfreeMemory, BMSfreeMemoryArray, BMSfreeMemoryArrayNull, i, NULL, releaseVarMappingHashmapVars(), SCIP_CALL, SCIP_OKAY, SCIPbenderscutFree(), SCIPclockFree(), and SCIPhashmapFree().
Referenced by SCIPbendersCreate().
|
static |
scip | the SCIP data structure |
benders | Benders' decomposition |
cons | constraint to which the slack variable(s) is added to |
linearconshdlrs | an array storing the linear constraint handlers |
nlconshdlr | pointer to the nonlinear constraint handler |
nlinearconshdlrs | the number of linear constraint handlers |
Definition at line 1330 of file benders.c.
References assert(), FALSE, i, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPaddLinearVarNonlinear(), SCIPaddVar(), SCIPconsAddCoef(), SCIPconsGetHdlr(), SCIPconsGetLhs(), SCIPconsGetName(), SCIPconsGetRhs(), SCIPconshdlrGetName(), SCIPcreateVarBasic(), SCIPgetLhsNonlinear(), SCIPgetRhsNonlinear(), SCIPinfinity(), SCIPisInfinity(), SCIPreleaseVar(), SCIPsnprintf(), SCIPwarningMessage(), SLACKVAR_NAME, SCIP_Benders::slackvarcoef, TRUE, and var.
Referenced by addSlackVarsToConstraints().
|
static |
adds the slack variables to each of the constraints for the generation of feasibility cuts for the given non-linear subproblem
benders | Benders' decomposition |
set | global SCIP settings |
probnumber | the subproblem number |
Definition at line 1442 of file benders.c.
References addSlackVars(), assert(), i, NLINEARCONSHDLRS, NULL, SCIP_CALL, SCIP_OKAY, SCIPbendersGetNSubproblems(), SCIPbendersSubproblem(), SCIPfindConshdlr(), SCIPgetNOrigConss(), and SCIPgetOrigConss().
Referenced by createSubproblems().
|
static |
initialises a MIP subproblem by putting the problem into SCIP_STAGE_SOLVING. This is achieved by calling SCIPsolve and then interrupting the solve in a node focus event handler. The LP subproblem is also initialised using this method; however, a different event handler is added. This event handler will put the LP subproblem into probing mode. The MIP solving function is called to initialise the subproblem because this function calls SCIPsolve with the appropriate parameter settings for Benders' decomposition.
benders | Benders' decomposition |
set | global SCIP settings |
probnumber | the subproblem number |
infeasible | pointer to store whether the lp is detected as infeasible |
success | was the initialisation process successful |
Definition at line 1488 of file benders.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_MEMLIMIT, SCIP_STATUS_TIMELIMIT, SCIPbendersGetNSubproblems(), SCIPbendersSolveSubproblemCIP(), SCIPbendersSubproblem(), SCIPconstructLP(), and SCIPgetStage().
Referenced by initialiseLPSubproblem(), SCIPbendersSetupSubproblem(), and SCIPbendersSolveSubproblem().
|
static |
initialises an LP subproblem by putting the problem into probing mode. The probing mode is invoked in a node focus event handler. This event handler is added just prior to calling the initialise subproblem function.
benders | Benders' decomposition |
set | global SCIP settings |
probnumber | the subproblem number |
infeasible | pointer to store whether the lp is detected as infeasible |
Definition at line 1531 of file benders.c.
References assert(), initEventhandlerData(), initialiseSubproblem(), NODEFOCUS_EVENTHDLR_DESC, NODEFOCUS_EVENTHDLR_NAME, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPbendersGetNSubproblems(), SCIPbendersSubproblem(), SCIPincludeEventhdlrBasic(), SCIPsetEventhdlrExit(), SCIPsetEventhdlrExitsol(), SCIPsetEventhdlrFree(), and SCIPsetEventhdlrInitsol().
Referenced by createSubproblems(), and SCIPbendersChgMastervarsToCont().
|
static |
checks whether the convex relaxation of the subproblem is sufficient to solve the original problem to optimality
We check whether we can conclude that the CIP is actually an LP or a convex NLP. To do this, we check that all variables are of continuous type and that every constraint is either handled by known linear constraint handler (knapsack, linear, logicor, setppc, varbound) or the nonlinear constraint handler. In the latter case, we also check whether the nonlinear constraint is convex. Further, nonlinear constraints are only considered if an NLP solver interface is available, i.e., and NLP could be solved. If constraints are present that cannot be identified as linear or convex nonlinear, then we assume that the problem is not convex, thus solving its LP or NLP relaxation will not be sufficient.
benders | Benders' decomposition |
set | global SCIP settings |
probnumber | the subproblem number, or -1 for the master problem |
Definition at line 1581 of file benders.c.
References assert(), SCIP_Benders::checkconsconvexity, FALSE, i, nbinvars, nintvars, NLINEARCONSHDLRS, NULL, nvars, SCIP_BENDERSSUBTYPE_CONVEXCONT, SCIP_BENDERSSUBTYPE_CONVEXDIS, SCIP_BENDERSSUBTYPE_NONCONVEXCONT, SCIP_BENDERSSUBTYPE_NONCONVEXDIS, SCIP_Bool, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_OKAY, SCIPABORT, SCIPbendersGetNSubproblems(), SCIPbendersGetSubproblemType(), SCIPbendersGetVar(), SCIPbendersSetMasterIsNonlinear(), SCIPbendersSetSubproblemIsNonlinear(), SCIPbendersSetSubproblemType(), SCIPbendersSubproblem(), SCIPblkmem(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPdebugMsg, SCIPevalExprActivity(), SCIPfindConshdlr(), SCIPgetCurvatureNonlinear(), SCIPgetExprNonlinear(), SCIPgetLhsNonlinear(), SCIPgetNNlpis(), SCIPgetNOrigConss(), SCIPgetNVars(), SCIPgetOrigConss(), SCIPgetProbName(), SCIPgetRhsNonlinear(), SCIPgetVarsData(), SCIPhasExprCurvature(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapInsert(), SCIPisInfinity(), SCIPsetDebugMsg, TRUE, and vars.
Referenced by createSubproblems(), and SCIPbendersChgMastervarsToCont().
|
static |
creates the subproblems and registers it with the Benders' decomposition struct
benders | Benders' decomposition |
set | global SCIP settings |
Definition at line 1791 of file benders.c.
References addSlackVarsToConstraints(), assert(), checkSubproblemConvexity(), SCIP_Benders::execfeasphase, FALSE, SCIP_Benders::feasibilityphase, i, initEventhandlerData(), initialiseLPSubproblem(), SCIP_Benders::iscopy, MIPNODEFOCUS_EVENTHDLR_DESC, MIPNODEFOCUS_EVENTHDLR_NAME, NULL, nvars, SCIP_BENDERSSUBTYPE_CONVEXCONT, SCIP_BENDERSSUBTYPE_CONVEXDIS, SCIP_BENDERSSUBTYPE_UNKNOWN, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_STAGE_PROBLEM, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, SCIPallocBlockMemory, SCIPbendersChgMastervarsToCont(), SCIPbendersGetNSubproblems(), SCIPbendersGetSubproblemType(), SCIPbendersGetVar(), SCIPbendersSetSubproblemsAreInfeasible(), SCIPbendersSubproblem(), SCIPbendersSubproblemIsNonlinear(), SCIPchgVarObj(), SCIPerrorMessage, SCIPgetStage(), SCIPgetVarsData(), SCIPincludeEventhdlrBasic(), SCIPsetEventhdlrExit(), SCIPsetEventhdlrExitsol(), SCIPsetEventhdlrFree(), SCIPsetEventhdlrInitsol(), SCIPsetIntParam(), SCIPvarGetName(), SCIPvarGetObj(), SCIPverbMessage(), SCIP_Benders::subprobscreated, SCIP_Benders::threadsafe, TRUE, UPPERBOUND_EVENTHDLR_DESC, UPPERBOUND_EVENTHDLR_NAME, and vars.
Referenced by SCIPbendersInit().
SCIP_RETCODE SCIPbendersInit | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set ) |
initializes Benders' decomposition
benders | Benders' decomposition |
set | global SCIP settings |
Definition at line 1993 of file benders.c.
References assert(), assignAuxiliaryVariables(), BENDERS_ARRAYSIZE, SCIP_Benders::bendersclock, SCIP_Benders::benderscuts, BMSallocBlockMemoryArray, createSubproblems(), i, SCIP_Benders::initialized, SCIP_Benders::iscopy, SCIP_Benders::name, SCIP_Benders::nbenderscuts, SCIP_Benders::ncalls, SCIP_Benders::ncutsfound, SCIP_Benders::nstoredcuts, SCIP_Benders::ntransferred, NULL, SCIP_ALLOC, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPbenderscutInit(), SCIPbendersSortBenderscuts(), SCIPblkmem(), SCIPclockReset(), SCIPclockStart(), SCIPclockStop(), SCIPerrorMessage, SCIPsetGetRealParam(), SCIP_Benders::setuptime, SCIP_Benders::solutiontol, SCIP_Benders::storedcuts, SCIP_Benders::storedcutssize, and TRUE.
|
static |
Transfers Benders' cuts that were generated while solving a sub-SCIP to the original SCIP instance. This involves creating a constraint/cut that is equivalent to the generated cut in the sub-SCIP. This new constraint/cut is then added to the original SCIP instance.
sourcescip | the source SCIP from when the Benders' decomposition was copied |
benders | the Benders' decomposition structure of the sub SCIP |
vars | the variables from the source constraint |
vals | the coefficients of the variables in the source constriant |
lhs | the LHS of the source constraint |
rhs | the RHS of the source constraint |
nvars | the number of variables in the source constraint |
Definition at line 2073 of file benders.c.
References assert(), SCIP_Benders::cutsasconss, FALSE, i, SCIP_Benders::mastervarsmap, SCIP_Benders::ntransferred, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddPoolCut(), SCIPaddVarToRow(), SCIPbendersGetName(), SCIPbendersGetNTransferredCuts(), SCIPcreateConsBasicLinear(), SCIPcreateEmptyRowConshdlr(), SCIPfindBenders(), SCIPfindConshdlr(), SCIPhashmapGetImage(), SCIPreleaseCons(), SCIPreleaseRow(), SCIPsetConsRemovable(), SCIPsnprintf(), SCIPvarGetOrigvarSum(), TRUE, and vars.
Referenced by transferBendersCuts().
|
static |
transfers the cuts generated in a subscip to the source scip
sourcescip | the source SCIP from when the Benders' decomposition was copied |
subscip | the sub SCIP where the Benders' cuts were generated |
benders | the Benders' decomposition structure of the sub SCIP |
Definition at line 2191 of file benders.c.
References assert(), createAndAddTransferredCut(), i, SCIP_Benders::mastervarsmap, NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbendersGetName(), SCIPbendersGetNStoredCuts(), SCIPbendersGetStoredCutData(), SCIPfindBenders(), SCIP_Benders::transfercuts, and vars.
Referenced by SCIPbendersExit().
SCIP_RETCODE SCIPbendersExit | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set ) |
calls exit method of Benders' decomposition
benders | Benders' decomposition |
set | global SCIP settings |
Definition at line 2237 of file benders.c.
References assert(), SCIP_Benders::auxiliaryvars, SCIP_Benders::benderscuts, BMSfreeBlockMemoryArray, SCIP_Benders::corepoint, FALSE, i, SCIP_Benders::initialized, SCIP_Benders::iscopy, SCIP_Benders::mastervarsmap, SCIP_Benders::name, SCIP_Benders::nbenderscuts, SCIP_Benders::nstoredcuts, NULL, SCIP_BenderscutCut::nvars, SCIP_CALL, SCIP_INVALIDCALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPaddVarLocksType(), SCIPbenderscutExit(), SCIPbendersGetNSubproblems(), SCIPbendersSortBenderscuts(), SCIPblkmem(), SCIPclockStart(), SCIPclockStop(), SCIPerrorMessage, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeSol(), SCIPreleaseVar(), SCIPvarGetNLocksDown(), SCIP_Benders::setuptime, SCIP_Benders::sourcescip, SCIP_Benders::storedcuts, SCIP_Benders::storedcutssize, transferBendersCuts(), SCIP_BenderscutCut::vals, and SCIP_BenderscutCut::vars.
|
static |
Checks whether a subproblem is independent.
scip | the SCIP data structure |
benders | Benders' decomposition |
Definition at line 2324 of file benders.c.
References assert(), FALSE, i, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPbendersGetNSubproblems(), SCIPbendersSetSubproblemIsIndependent(), SCIPgetBendersSubproblemVar(), SCIPgetVarsData(), TRUE, and vars.
Referenced by SCIPbendersInitpre().
SCIP_RETCODE SCIPbendersInitpre | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set, | ||
SCIP_STAT * | stat ) |
informs the Benders' decomposition that the presolving process is being started
benders | Benders' decomposition |
set | global SCIP settings |
stat | dynamic problem statistics |
Definition at line 2380 of file benders.c.
References addAuxiliaryVariablesToMaster(), assert(), checkSubproblemIndependence(), SCIP_Benders::iscopy, NULL, SCIP_CALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), and SCIP_Benders::setuptime.
SCIP_RETCODE SCIPbendersExitpre | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set, | ||
SCIP_STAT * | stat ) |
informs the Benders' decomposition that the presolving process has completed
benders | Benders' decomposition |
set | global SCIP settings |
stat | dynamic problem statistics |
Definition at line 2423 of file benders.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), and SCIP_Benders::setuptime.
SCIP_RETCODE SCIPbendersInitsol | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set ) |
informs Benders' decomposition that the branch and bound process is being started
benders | Benders' decomposition |
set | global SCIP settings |
Definition at line 2449 of file benders.c.
References assert(), SCIP_Benders::benderscuts, i, SCIP_Benders::nbenderscuts, NULL, SCIP_CALL, SCIP_OKAY, SCIPbenderscutInitsol(), SCIPbendersSortBenderscuts(), SCIPclockStart(), SCIPclockStop(), and SCIP_Benders::setuptime.
SCIP_RETCODE SCIPbendersExitsol | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set ) |
informs Benders' decomposition that the branch and bound process data is being freed
benders | Benders' decomposition |
set | global SCIP settings |
Definition at line 2482 of file benders.c.
References assert(), SCIP_Benders::benderscuts, FALSE, i, SCIP_Benders::nbenderscuts, NULL, SCIP_CALL, SCIP_OKAY, SCIPbenderscutExitsol(), SCIPbendersFreeSubproblem(), SCIPbendersGetNSubproblems(), SCIPbendersSetSubproblemIsIndependent(), SCIPbendersSortBenderscuts(), SCIPbendersSubproblemIsIndependent(), SCIPclockStart(), SCIPclockStop(), and SCIP_Benders::setuptime.
SCIP_RETCODE SCIPbendersActivate | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set, | ||
int | nsubproblems ) |
activates Benders' decomposition such that it is called in LP solving loop
benders | the Benders' decomposition structure |
set | global SCIP settings |
nsubproblems | the number subproblems used in this decomposition |
Definition at line 2538 of file benders.c.
References SCIP_Benders::active, assert(), SCIP_Benders::auxiliaryvars, SCIP_SubproblemSolveStat::avgiter, SCIP_Benders::bestsubprobobjval, BMSallocMemory, BMSallocMemoryArray, FALSE, i, SCIP_SubproblemSolveStat::idx, SCIP_Benders::indepsubprob, SCIP_Benders::mastervarscont, SCIP_Benders::nactivesubprobs, SCIP_SubproblemSolveStat::ncalls, NODESOLVED_EVENTHDLR_DESC, NODESOLVED_EVENTHDLR_NAME, SCIP_Benders::nsubproblems, NULL, SCIP_Benders::prevlowerbound, SCIP_ALLOC, SCIP_BENDERSSUBTYPE_UNKNOWN, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_INIT, SCIP_STAGE_PROBLEM, SCIPincludeEventhdlrBasic(), SCIPpqueueCreate(), SCIPpqueueInsert(), SCIPsetEventhdlrInitsol(), SCIPsetInfinity(), SCIP_Benders::solvestat, SCIP_Benders::strengthenround, SCIP_Benders::subprobenabled, SCIP_Benders::subprobisconvex, SCIP_Benders::subprobisnonlinear, SCIP_Benders::subproblems, SCIP_Benders::subproblowerbound, SCIP_Benders::subprobobjval, SCIP_Benders::subprobqueue, SCIP_Benders::subprobsetup, SCIP_Benders::subprobtype, and TRUE.
Referenced by SCIPactivateBenders().
SCIP_RETCODE SCIPbendersDeactivate | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set ) |
deactivates Benders' decomposition such that it is no longer called in LP solving loop
benders | the Benders' decomposition structure |
set | global SCIP settings |
Definition at line 2624 of file benders.c.
References SCIP_Benders::active, assert(), SCIP_Benders::auxiliaryvars, SCIP_Benders::bestsubprobobjval, BMSfreeMemory, BMSfreeMemoryArray, FALSE, SCIP_Benders::freesubprobs, i, SCIP_Benders::indepsubprob, SCIP_Benders::mastervarscont, NULL, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_INIT, SCIP_STAGE_PROBLEM, SCIPbendersGetNSubproblems(), SCIPbendersSubproblem(), SCIPfree(), SCIPpqueueFree(), SCIP_Benders::solvestat, SCIP_Benders::subprobenabled, SCIP_Benders::subprobisconvex, SCIP_Benders::subprobisnonlinear, SCIP_Benders::subproblems, SCIP_Benders::subproblowerbound, SCIP_Benders::subprobobjval, SCIP_Benders::subprobqueue, SCIP_Benders::subprobsetup, and SCIP_Benders::subprobtype.
Referenced by SCIPdeactivateBenders(), and SCIPfreeProb().
|
static |
updates the lower bound for all auxiliary variables. This is called if the first LP enforced is unbounded.
benders | Benders' decomposition |
set | global SCIP settings |
result | the result from updating the auxiliary variable lower bound |
Definition at line 2698 of file benders.c.
References assert(), FALSE, i, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_INFEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIPbendersComputeSubproblemLowerbound(), SCIPbendersGetAuxiliaryVar(), SCIPbendersGetNSubproblems(), SCIPbendersUpdateSubproblemLowerbound(), SCIPchgVarLb(), SCIPsetDebugMsg, SCIPsetIsGT(), SCIPvarGetLbGlobal(), and SCIPvarGetName().
Referenced by SCIPbendersExec().
|
static |
sets the core point used for cut strengthening. If the strenghtenintpoint is set to 'i', then the core point is reinitialised each time the incumbent is updated
scip | the SCIP data structure |
benders | Benders' decomposition |
Definition at line 2755 of file benders.c.
References assert(), SCIP_Benders::corepoint, FALSE, i, SCIP_Benders::initcorepoint, NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_MINIMAL, SCIPcomputeLPRelIntPoint(), SCIPcreateLPSol(), SCIPcreateSol(), SCIPcreateSolCopy(), SCIPfreeSol(), SCIPgetBestSol(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPgetVarsData(), SCIPisInfinity(), SCIPsetSolVal(), SCIPunlinkSol(), SCIPverbMessage(), SCIP_Benders::strengthenintpoint, TRUE, and vars.
Referenced by performInteriorSolCutStrengthening().
|
static |
performs cut strengthening by using an interior solution to generate cuts
benders | Benders' decomposition |
set | global SCIP settings |
sol | primal CIP solution |
type | the type of solution being enforced |
checkint | are the subproblems called during a check/enforce of integer sols? |
perturbsol | should the solution be perturbed to escape infeasibility? |
auxviol | set to TRUE only if the solution is feasible but the aux vars are violated |
infeasible | is the master problem infeasible with respect to the Benders' cuts? |
skipsolve | should the main solve be skipped as a result of this strengthening? |
result | result of the pricing process |
Definition at line 2841 of file benders.c.
References assert(), SCIP_Benders::convexmult, SCIP_Benders::corepoint, FALSE, i, SCIP_Benders::noimprovecount, SCIP_Benders::noimprovelimit, SCIP_Benders::nstrengthencalls, SCIP_Benders::nstrengthencuts, SCIP_Benders::nstrengthenfails, NULL, nvars, SCIP_Benders::perturbeps, SCIP_Benders::prevlowerbound, SCIP_Benders::prevnlpiter, SCIP_Benders::prevnode, result, SCIP_BENDERSENFOTYPE_LP, SCIP_Bool, SCIP_CALL, SCIP_CONSADDED, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIP_VARSTATUS_FIXED, SCIPbendersGetNCutsFound(), SCIPcreateLPSol(), SCIPfreeSol(), SCIPgetBendersNSubproblems(), SCIPgetBendersSubproblemVar(), SCIPgetBestSol(), SCIPgetCurrentNode(), SCIPgetLowerbound(), SCIPgetNLPIterations(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPsetDebugMsg, SCIPsetIsGT(), SCIPsetSolVal(), SCIPsolveBendersSubproblems(), SCIPunlinkSol(), SCIPvarGetStatus(), setAndUpdateCorePoint(), sol, TRUE, and vars.
Referenced by SCIPbendersExec().
|
static |
returns the number of subproblems that will be checked in this iteration
benders | Benders' decomposition |
set | global SCIP settings |
type | the type of solution being enforced |
Definition at line 3010 of file benders.c.
References SCIP_Benders::ncalls, SCIP_BENDERSENFOTYPE_CHECK, SCIP_Real, SCIPbendersGetNSubproblems(), SCIPbendersOnlyCheckConvexRelax(), SCIPsetCeil(), SCIPsetGetSubscipsOff(), and SCIP_Benders::subprobfrac.
Referenced by createSolveSubproblemIndexList().
|
static |
returns whether the solving of the given subproblem needs to be executed
benders | Benders' decomposition |
probnumber | the subproblem index |
Definition at line 3025 of file benders.c.
References SCIP_Bool, SCIPbendersSubproblemIsEnabled(), and SCIPbendersSubproblemIsIndependent().
Referenced by generateBendersCuts(), SCIPbendersExec(), SCIPbendersFreeSubproblem(), SCIPbendersSetSubproblemEnabled(), SCIPbendersSetSubproblemIsIndependent(), and solveBendersSubproblems().
|
static |
creates an ordered list of subproblem indices to be solved
benders | Benders' decomposition |
set | global SCIP settings |
type | the type of solution being enforced |
solveidx | a list of subproblem indices to the solved in the current iteration |
nsolveidx | the number of subproblem indices in the list |
Definition at line 3036 of file benders.c.
References assert(), SCIP_SubproblemSolveStat::idx, NULL, numSubproblemsToCheck(), SCIPbendersGetNSubproblems(), SCIPpqueueNElems(), SCIPpqueueRemove(), and SCIP_Benders::subprobqueue.
Referenced by SCIPbendersExec().
|
static |
updates the subproblem solving statistics and inserts the indices into the queue
benders | Benders' decomposition |
solveidx | the list of indices of subproblems that were solved |
nsolveidx | the number of subproblem indices |
updatestat | should the statistics be updated |
Definition at line 3076 of file benders.c.
References assert(), SCIP_SubproblemSolveStat::avgiter, i, SCIP_SubproblemSolveStat::idx, SCIP_SubproblemSolveStat::ncalls, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbendersGetNSubproblems(), SCIPbendersSubproblem(), SCIPgetNLPIterations(), SCIPpqueueInsert(), SCIPpqueueNElems(), SCIP_Benders::solvestat, and SCIP_Benders::subprobqueue.
Referenced by SCIPbendersExec().
|
static |
Solves each of the Benders' decomposition subproblems for the given solution. All, or a fraction, of subproblems are solved before the Benders' decomposition cuts are generated. Since a convex relaxation of the subproblem could be solved to generate cuts, a parameter nverified is used to identified the number of subproblems that have been solved in their "original" form. For example, if the subproblem is a MIP, then if the LP is solved to generate cuts, this does not constitute a verification. The verification is only performed when the MIP is solved.
benders | Benders' decomposition |
set | global SCIP settings |
sol | primal CIP solution |
type | the type of solution being enforced |
solveloop | the current solve loop |
checkint | are the subproblems called during a check/enforce of integer sols? |
nverified | the number of subproblems verified in the current loop |
solveidx | the indices of subproblems to be solved in this loop |
nsolveidx | the number of subproblems to be solved in this loop |
subprobsolved | an array indicating the subproblems that were solved in this loop. |
substatus | array to store the status of the subsystem |
infeasible | is the master problem infeasible with respect to the Benders' cuts? |
optimal | is the current solution optimal? |
stopped | was the solving process stopped? |
Definition at line 3125 of file benders.c.
References assert(), FALSE, i, MIN, NULL, SCIP_Benders::numthreads, SCIP_BENDERSENFOTYPE_CHECK, SCIP_BENDERSENFOTYPE_LP, SCIP_BENDERSSOLVELOOP_CIP, SCIP_BENDERSSOLVELOOP_CONVEX, SCIP_BENDERSSOLVELOOP_USERCIP, SCIP_BENDERSSOLVELOOP_USERCONVEX, SCIP_BENDERSSUBSTATUS_AUXVIOL, SCIP_BENDERSSUBSTATUS_INFEAS, SCIP_BENDERSSUBSTATUS_OPTIMAL, SCIP_BENDERSSUBSTATUS_UNKNOWN, SCIP_BENDERSSUBTYPE_CONVEXCONT, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPbendersExecSubproblemSolve(), SCIPbendersGetAuxiliaryVarVal(), SCIPbendersGetSubproblemLowerbound(), SCIPbendersGetSubproblemObjval(), SCIPbendersGetSubproblemType(), SCIPbendersOnlyCheckConvexRelax(), SCIPbendersSetSubproblemObjval(), SCIPbendersSubproblem(), SCIPbendersSubproblemIsOptimal(), SCIPinfinity(), SCIPisStopped(), SCIPrelDiff(), SCIPsetDebugMsg, SCIPsetGetIntParam(), SCIPsetGetSubscipsOff(), SCIPsetInfinity(), SCIPsetIsInfinity(), sol, SCIP_Benders::solutiontol, subproblemIsActive(), and TRUE.
Referenced by SCIPbendersExec().
|
static |
Calls the Benders' decompsition cuts for the given solve loop. There are four cases: i) solveloop == SCIP_BENDERSSOLVELOOP_CONVEX - only the LP Benders' cuts are called ii) solveloop == SCIP_BENDERSSOLVELOOP_CIP - only the CIP Benders' cuts are called iii) solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX - only the LP Benders' cuts are called iv) solveloop == SCIP_BENDERSSOLVELOOP_USERCIP - only the CIP Benders' cuts are called
The priority of the results are: SCIP_CONSADDED (SCIP_SEPARATED), SCIP_DIDNOTFIND, SCIP_FEASIBLE, SCIP_DIDNOTRUN. In this function, there are four levels of results that need to be assessed. These are: i) The result from the individual cut for the subproblem ii) The overall result for the subproblem from all cuts iii) the overall result for the solve loop from all cuts iv) the over all result from all solve loops. In each level, the priority of results must be adhered to.
benders | Benders' decomposition |
set | global SCIP settings |
sol | primal CIP solution |
result | result of the pricing process |
type | the type of solution being enforced |
solveloop | the current solve loop |
checkint | are the subproblems called during a check/enforce of integer sols? |
subprobsolved | an array indicating the subproblems that were solved in this loop. |
substatus | array to store the status of the subsystem |
solveidx | the indices of subproblems to be solved in this loop |
nsolveidx | the number of subproblems to be solved in this loop |
mergecands | the subproblems that are merge candidates |
npriomergecands | the number of priority merge candidates. |
nmergecands | the number of merge candidates. |
nsolveloops | the number of solve loops, is updated w.r.t added cuts |
Definition at line 3396 of file benders.c.
References assert(), SCIP_Benders::cutcheck, i, SCIP_Benders::ncutsfound, NULL, result, SCIP_BENDERSENFOTYPE_CHECK, SCIP_BENDERSSOLVELOOP_CIP, SCIP_BENDERSSOLVELOOP_CONVEX, SCIP_BENDERSSOLVELOOP_USERCIP, SCIP_BENDERSSOLVELOOP_USERCONVEX, SCIP_BENDERSSUBSTATUS_INFEAS, SCIP_BENDERSSUBSTATUS_OPTIMAL, SCIP_BENDERSSUBTYPE_CONVEXCONT, SCIP_Bool, SCIP_CALL, SCIP_CONSADDED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FEASIBLE, SCIP_Longint, SCIP_OKAY, SCIP_SEPARATED, SCIP_STAGE_PRESOLVED, SCIP_STAGE_SOLVED, SCIP_STAGE_TRANSFORMED, SCIPbenderscutExec(), SCIPbenderscutGetNFound(), SCIPbenderscutIsLPCut(), SCIPbendersGetBenderscuts(), SCIPbendersGetNBenderscuts(), SCIPbendersGetNConvexSubproblems(), SCIPbendersGetNSubproblems(), SCIPbendersGetSubproblemType(), SCIPbendersOnlyCheckConvexRelax(), SCIPsetGetStage(), SCIPsetGetSubscipsOff(), sol, SCIP_Benders::strengthenround, and subproblemIsActive().
Referenced by SCIPbendersExec().
SCIP_RETCODE SCIPbendersExec | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set, | ||
SCIP_SOL * | sol, | ||
SCIP_RESULT * | result, | ||
SCIP_Bool * | infeasible, | ||
SCIP_Bool * | auxviol, | ||
SCIP_BENDERSENFOTYPE | type, | ||
SCIP_Bool | checkint ) |
Solves the subproblem using the current master problem solution.
The checkint flag indicates whether integer feasibility can be assumed. If it is not assumed, i.e. checkint == FALSE, then only the convex relaxations of the subproblems are solved. If integer feasibility is assumed, i.e. checkint == TRUE, then the convex relaxations and the full CIP are solved to generate Benders' cuts and check solution feasibility.
TODO: consider allowing the possibility to pass solution information back from the subproblems instead of the scip instance. This would allow the use of different solvers for the subproblems, more importantly allowing the use of an LP solver for LP subproblems.
benders | Benders' decomposition |
set | global SCIP settings |
sol | primal CIP solution |
result | result of the pricing process |
infeasible | is the master problem infeasible with respect to the Benders' cuts? |
auxviol | set to TRUE only if the solution is feasible but the aux vars are violated |
type | the type of solution being enforced |
checkint | should the integer solution be checked by the subproblems |
Definition at line 3594 of file benders.c.
References assert(), BENDERS_MAXPSEUDOSOLS, SCIP_Benders::bendersclock, createSolveSubproblemIndexList(), FALSE, SCIP_Benders::feasibilityphase, generateBendersCuts(), i, SCIP_Benders::iscopy, SCIP_Benders::lnscheck, SCIP_Benders::lnsmaxcalls, SCIP_Benders::lnsmaxcallsroot, SCIP_Benders::lnsmaxdepth, SCIP_Benders::maxslackvarcoef, SCIP_Benders::name, SCIP_Benders::ncalls, SCIP_Benders::npseudosols, NULL, performInteriorSolCutStrengthening(), resetSubproblemObjectiveValue(), result, SCIP_BENDERSENFOTYPE_CHECK, SCIP_BENDERSENFOTYPE_LP, SCIP_BENDERSENFOTYPE_PSEUDO, SCIP_BENDERSSOLVELOOP_USERCIP, SCIP_BENDERSSOLVELOOP_USERCONVEX, SCIP_Bool, SCIP_CALL, SCIP_CONSADDED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_ERROR, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_INVALIDRESULT, SCIP_LPSOLSTAT_UNBOUNDEDRAY, SCIP_OKAY, SCIP_SEPARATED, SCIP_SOLVELP, SCIP_STAGE_TRANSFORMED, SCIP_VERBLEVEL_HIGH, SCIPallocClearBlockMemoryArray, SCIPbendersFreeSubproblem(), SCIPbendersGetName(), SCIPbendersGetNCalls(), SCIPbendersGetNConvexSubproblems(), SCIPbendersGetNSubproblems(), SCIPbendersOnlyCheckConvexRelax(), SCIPbendersSolSlackVarsActive(), SCIPbendersSubproblem(), SCIPclockStart(), SCIPclockStop(), SCIPerrorMessage, SCIPfreeBlockMemoryArray, SCIPgetDepth(), SCIPgetLPSolstat(), SCIPgetMessagehdlr(), SCIPgetObjsense(), SCIPgetPrimalbound(), SCIPgetSolOrigObj(), SCIPgetStage(), SCIPinProbing(), SCIPmessagePrintVerbInfo(), SCIPprintSol(), SCIPsetDebugMsg, SCIPsetGetSubscipsOff(), SCIPsetIsLE(), SCIPsolveBendersSubproblems(), SCIPverbMessage(), SCIP_Benders::slackvarcoef, sol, solveBendersSubproblems(), SCIP_Benders::sourcescip, SCIP_Benders::strengthenenabled, SCIP_Benders::strengthenround, subproblemIsActive(), TRUE, updateAuxiliaryVarLowerbound(), SCIP_Benders::updateauxvarbound, and updateSubproblemStatQueue().
Referenced by SCIPsolveBendersSubproblems().
|
static |
solves the user-defined subproblem solving function
benders | Benders' decomposition |
set | global SCIP settings |
sol | primal CIP solution |
probnumber | the subproblem number |
solveloop | the solve loop iteration. The first iter is for LP, the second for IP |
infeasible | returns whether the current subproblem is infeasible |
objective | the objective function value of the subproblem |
result | the result from solving the subproblem |
Definition at line 4131 of file benders.c.
References assert(), SCIP_Benders::name, NULL, result, SCIP_BENDERSSOLVELOOP_USERCIP, SCIP_BENDERSSOLVELOOP_USERCONVEX, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_ERROR, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_INVALIDRESULT, SCIP_OKAY, SCIP_Real, SCIP_UNBOUNDED, SCIPbendersOnlyCheckConvexRelax(), SCIPerrorMessage, SCIPsetGetSubscipsOff(), SCIPsetInfinity(), SCIPsetIsInfinity(), sol, and TRUE.
Referenced by SCIPbendersExecSubproblemSolve(), and SCIPbendersSolveSubproblem().
SCIP_RETCODE SCIPbendersExecSubproblemSolve | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set, | ||
SCIP_SOL * | sol, | ||
int | probnumber, | ||
SCIP_BENDERSSOLVELOOP | solveloop, | ||
SCIP_Bool | enhancement, | ||
SCIP_Bool * | solved, | ||
SCIP_Bool * | infeasible, | ||
SCIP_BENDERSENFOTYPE | type ) |
executes the subproblem solving process
benders | Benders' decomposition |
set | global SCIP settings |
sol | primal CIP solution |
probnumber | the subproblem number |
solveloop | the solve loop iteration. The first iter is for LP, the second for IP |
enhancement | is the solve performed as part of and enhancement? |
solved | flag to indicate whether the subproblem was solved |
infeasible | returns whether the current subproblem is infeasible |
type | the enforcement type calling this function |
Definition at line 4202 of file benders.c.
References assert(), executeUserDefinedSolvesub(), FALSE, SCIP_Benders::name, NULL, result, SCIP_BENDERSSOLVELOOP_CIP, SCIP_BENDERSSOLVELOOP_CONVEX, SCIP_BENDERSSOLVELOOP_USERCIP, SCIP_BENDERSSOLVELOOP_USERCONVEX, SCIP_BENDERSSUBTYPE_CONVEXCONT, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_ERROR, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_MEMLIMIT, SCIP_STATUS_OPTIMAL, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_UNBOUNDED, SCIP_STATUS_UNKNOWN, SCIP_STATUS_USERINTERRUPT, SCIP_UNBOUNDED, SCIP_VERBLEVEL_FULL, SCIPABORT, SCIPbendersGetAuxiliaryVarVal(), SCIPbendersGetSubproblemType(), SCIPbendersSetSubproblemObjval(), SCIPbendersSetupSubproblem(), SCIPbendersSolveSubproblemCIP(), SCIPbendersSolveSubproblemLP(), SCIPbendersSubproblem(), SCIPbendersSubproblemIsSetup(), SCIPerrorMessage, SCIPgetBestSol(), SCIPgetObjsense(), SCIPgetSolOrigObj(), SCIPsetDebugMsg, SCIPsetInfinity(), SCIPverbMessage(), sol, TRUE, and updateEventhdlrUpperbound().
Referenced by solveBendersSubproblems().
SCIP_RETCODE SCIPbendersSetupSubproblem | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set, | ||
SCIP_SOL * | sol, | ||
int | probnumber, | ||
SCIP_BENDERSENFOTYPE | type ) |
sets up the subproblem using the solution to the master problem
benders | Benders' decomposition |
set | global SCIP settings |
sol | primal CIP solution |
probnumber | the subproblem number |
type | the enforcement type calling this function |
Definition at line 4371 of file benders.c.
References assert(), FALSE, SCIP_Benders::feasibilityphase, i, initialiseSubproblem(), SCIP_Benders::maxslackvarcoef, SCIP_Benders::name, NULL, nvars, SCIP_BENDERSENFOTYPE_CHECK, SCIP_BENDERSSUBTYPE_CONVEXCONT, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPbendersChgMastervarsToCont(), SCIPbendersGetNSubproblems(), SCIPbendersGetSubproblemType(), SCIPbendersGetVar(), SCIPbendersSetSubproblemIsSetup(), SCIPbendersSetSubproblemsAreInfeasible(), SCIPbendersSubproblem(), SCIPchgVarLb(), SCIPchgVarObjProbing(), SCIPchgVarUb(), SCIPchgVarUbProbing(), SCIPerrorMessage, SCIPgetDepth(), SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPinProbing(), SCIPisEQ(), SCIPisGT(), SCIPisLT(), SCIPisZero(), SCIPstartProbing(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SLACKVAR_NAME, SCIP_Benders::slackvarcoef, sol, TRUE, and vars.
Referenced by SCIPbendersExecSubproblemSolve(), and SCIPsetupBendersSubproblem().
SCIP_RETCODE SCIPbendersSolveSubproblem | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set, | ||
SCIP_SOL * | sol, | ||
int | probnumber, | ||
SCIP_Bool * | infeasible, | ||
SCIP_Bool | solvecip, | ||
SCIP_Real * | objective ) |
Solve a Benders' decomposition subproblems. This will either call the user defined method or the generic solving methods. If the generic method is called, then the subproblem must be set up before calling this method.
benders | Benders' decomposition |
set | global SCIP settings |
sol | primal CIP solution, can be NULL |
probnumber | the subproblem number |
infeasible | returns whether the current subproblem is infeasible |
solvecip | directly solve the CIP subproblem |
objective | the objective function value of the subproblem, can be NULL |
Definition at line 4531 of file benders.c.
References assert(), executeUserDefinedSolvesub(), FALSE, initialiseSubproblem(), NULL, result, SCIP_BENDERSSOLVELOOP_USERCIP, SCIP_BENDERSSOLVELOOP_USERCONVEX, SCIP_BENDERSSUBTYPE_CONVEXCONT, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIP_STATUS_INFEASIBLE, SCIPbendersGetNSubproblems(), SCIPbendersGetSubproblemType(), SCIPbendersSolveSubproblemCIP(), SCIPbendersSolveSubproblemLP(), SCIPbendersSubproblem(), SCIPbendersSubproblemIsIndependent(), SCIPbendersSubproblemIsSetup(), SCIPerrorMessage, SCIPgetBestSol(), SCIPgetObjsense(), SCIPgetSolOrigObj(), SCIPinfinity(), SCIPinProbing(), SCIPstartProbing(), sol, and TRUE.
Referenced by SCIPsolveBendersSubproblem().
|
static |
copies the time and memory limit from the master problem to the subproblem
scip | the SCIP data structure |
subproblem | the Benders' decomposition subproblem |
Definition at line 4640 of file benders.c.
References assert(), MAX, MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetParam(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPparamGetRealMax(), and SCIPsetRealParam().
Referenced by SCIPbendersComputeSubproblemLowerbound(), and setSubproblemParams().
|
static |
stores the original parameters from the subproblem
subproblem | the SCIP data structure |
origparams | the original subproblem parameters |
Definition at line 4673 of file benders.c.
References assert(), SCIP_SubproblemParams::conflict_enable, SCIP_SubproblemParams::cons_linear_propfreq, SCIP_SubproblemParams::limits_memory, SCIP_SubproblemParams::limits_time, SCIP_SubproblemParams::lp_alwaysgetduals, SCIP_SubproblemParams::lp_disablecutoff, SCIP_SubproblemParams::lp_initalg, SCIP_SubproblemParams::lp_resolvealg, SCIP_SubproblemParams::lp_scaling, SCIP_SubproblemParams::misc_catchctrlc, SCIP_SubproblemParams::misc_scaleobj, NULL, SCIP_SubproblemParams::prop_maxrounds, SCIP_SubproblemParams::prop_maxroundsroot, SCIP_CALL, SCIP_OKAY, SCIPgetBoolParam(), SCIPgetCharParam(), SCIPgetIntParam(), and SCIPgetRealParam().
Referenced by SCIPbendersSolveSubproblemCIP(), and SCIPbendersSolveSubproblemLP().
|
static |
sets the parameters for the subproblem
Definition at line 4700 of file benders.c.
References assert(), copyMemoryAndTimeLimits(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_OFF, SCIP_VERBLEVEL_NONE, SCIPsetBoolParam(), SCIPsetCharParam(), SCIPsetHeuristics(), SCIPsetIntParam(), SCIPsetPresolving(), and TRUE.
Referenced by SCIPbendersSolveSubproblemCIP(), and SCIPbendersSolveSubproblemLP().
|
static |
resets the original parameters from the subproblem
subproblem | the SCIP data structure |
origparams | the original subproblem parameters |
Definition at line 4751 of file benders.c.
References assert(), SCIP_SubproblemParams::conflict_enable, SCIP_SubproblemParams::cons_linear_propfreq, SCIP_SubproblemParams::limits_memory, SCIP_SubproblemParams::limits_time, SCIP_SubproblemParams::lp_alwaysgetduals, SCIP_SubproblemParams::lp_disablecutoff, SCIP_SubproblemParams::lp_initalg, SCIP_SubproblemParams::lp_resolvealg, SCIP_SubproblemParams::lp_scaling, SCIP_SubproblemParams::misc_catchctrlc, SCIP_SubproblemParams::misc_scaleobj, NULL, SCIP_SubproblemParams::prop_maxrounds, SCIP_SubproblemParams::prop_maxroundsroot, SCIP_CALL, SCIP_OKAY, SCIPsetBoolParam(), SCIPsetCharParam(), SCIPsetIntParam(), and SCIPsetRealParam().
Referenced by SCIPbendersSolveSubproblemCIP(), and SCIPbendersSolveSubproblemLP().
SCIP_RETCODE SCIPbendersFreeSubproblem | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set, | ||
int | probnumber ) |
frees the subproblems
benders | Benders' decomposition |
set | global SCIP settings |
probnumber | the subproblem number |
Definition at line 5051 of file benders.c.
References assert(), FALSE, NULL, SCIP_BENDERSSUBTYPE_CONVEXCONT, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_TRANSFORMED, SCIPbendersGetSubproblemType(), SCIPbendersSetSubproblemIsSetup(), SCIPbendersSubproblem(), SCIPendProbing(), SCIPfreeTransform(), SCIPgetStage(), SCIPinProbing(), and subproblemIsActive().
Referenced by SCIPbendersComputeSubproblemLowerbound(), SCIPbendersExec(), SCIPbendersExitsol(), SCIPbendersMergeSubproblemIntoMaster(), and SCIPfreeBendersSubproblem().
SCIP_Bool SCIPbendersSubproblemIsOptimal | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set, | ||
SCIP_SOL * | sol, | ||
int | probnumber ) |
compares the subproblem objective value with the auxiliary variable value for optimality
benders | the benders' decomposition structure |
set | global SCIP settings |
sol | primal CIP solution |
probnumber | the subproblem number |
Definition at line 5101 of file benders.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIP_Real, SCIPbendersGetAuxiliaryVarVal(), SCIPbendersGetSubproblemObjval(), SCIPrelDiff(), SCIPsetDebugMsg, sol, SCIP_Benders::solutiontol, and TRUE.
Referenced by SCIPcheckBendersSubproblemOptimality(), and solveBendersSubproblems().
SCIP_Real SCIPbendersGetAuxiliaryVarVal | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set, | ||
SCIP_SOL * | sol, | ||
int | probnumber ) |
returns the value of the auxiliary variable value in a master problem solution
benders | the benders' decomposition structure |
set | global SCIP settings |
sol | primal CIP solution |
probnumber | the subproblem number |
Definition at line 5130 of file benders.c.
References assert(), NULL, SCIP_Real, SCIPbendersGetAuxiliaryVar(), SCIPgetSolVal(), and sol.
Referenced by SCIPbendersExecSubproblemSolve(), SCIPbendersSubproblemIsOptimal(), SCIPgetBendersAuxiliaryVarVal(), and solveBendersSubproblems().
SCIP_RETCODE SCIPbendersComputeSubproblemLowerbound | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set, | ||
int | probnumber, | ||
SCIP_Real * | lowerbound, | ||
SCIP_Bool * | infeasible ) |
Solves an independent subproblem to identify its lower bound. The lower bound is then used to update the bound on the auxiliary variable.
benders | Benders' decomposition |
set | global SCIP settings |
probnumber | the subproblem to be evaluated |
lowerbound | the lowerbound for the subproblem |
infeasible | was the subproblem found to be infeasible? |
Definition at line 5151 of file benders.c.
References assert(), copyMemoryAndTimeLimits(), cutoff, FALSE, lperror, MIPNODEFOCUS_EVENTHDLR_NAME, SCIP_Benders::nlpparam, NULL, SCIP_BENDERSSUBTYPE_CONVEXCONT, SCIP_BENDERSSUBTYPE_CONVEXDIS, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_LPSOLSTAT_INFEASIBLE, SCIP_LPSOLSTAT_OPTIMAL, SCIP_NLPSOLSTAT_GLOBINFEASIBLE, SCIP_NLPSOLSTAT_GLOBOPT, SCIP_NLPSOLSTAT_LOCINFEASIBLE, SCIP_NLPSOLSTAT_LOCOPT, SCIP_NLPTERMSTAT_OKAY, SCIP_OKAY, SCIP_Real, SCIP_STATUS_INFEASIBLE, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, SCIP_VERBLEVEL_NONE, SCIPbendersFreeSubproblem(), SCIPbendersGetAuxiliaryVar(), SCIPbendersGetSubproblemType(), SCIPbendersSubproblem(), SCIPbendersSubproblemIsIndependent(), SCIPdebugMsg, SCIPeventhdlrGetData(), SCIPfindEventhdlr(), SCIPgetDualbound(), SCIPgetIntParam(), SCIPgetLongintParam(), SCIPgetLPSolstat(), SCIPgetNLPObjval(), SCIPgetNLPSolstat(), SCIPgetNLPTermstat(), SCIPgetNNlpis(), SCIPgetObjsense(), SCIPgetRealParam(), SCIPgetSolOrigObj(), SCIPgetStatus(), SCIPinfinity(), SCIPinfoMessage(), SCIPisLPConstructed(), SCIPisNLPConstructed(), SCIPretransformObj(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetRealParam(), SCIPsolve(), SCIPsolveNLPParam(), SCIPsolveProbingLP(), SCIPstartProbing(), SCIPvarGetLbGlobal(), SCIPverbMessage(), and TRUE.
Referenced by SCIPcomputeBendersSubproblemLowerbound(), and updateAuxiliaryVarLowerbound().
SCIP_RETCODE SCIPbendersMergeSubproblemIntoMaster | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set, | ||
SCIP_HASHMAP * | varmap, | ||
SCIP_HASHMAP * | consmap, | ||
int | probnumber ) |
Merges a subproblem into the master problem. This process just adds a copy of the subproblem variables and constraints to the master problem, but keeps the subproblem stored in the Benders' decomposition data structure. The reason for keeping the subproblem available is for when it is queried for solutions after the problem is solved.
Once the subproblem is merged into the master problem, then the subproblem is flagged as disabled. This means that it will not be solved in the subsequent subproblem solving loops.
The associated auxiliary variables are kept in the master problem. The objective function of the merged subproblem is added as an underestimator constraint.
benders | Benders' decomposition |
set | global SCIP settings |
varmap | a hashmap to store the mapping of subproblem variables corresponding to the newly created master variables, or NULL |
consmap | a hashmap to store the mapping of subproblem constraints to the corresponding newly created constraints, or NULL |
probnumber | the number of the subproblem that will be merged into the master problem |
Definition at line 5313 of file benders.c.
References assert(), FALSE, i, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddVar(), SCIPbendersFreeSubproblem(), SCIPbendersGetAuxiliaryVar(), SCIPbendersSetSubproblemEnabled(), SCIPbendersSubproblem(), SCIPblkmem(), SCIPconsGetHdlr(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPcreateConsBasicLinear(), SCIPcreateVarBasic(), SCIPgetBendersMasterVar(), SCIPgetConsCopy(), SCIPgetConss(), SCIPgetNConss(), SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapInsert(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsetConsRemovable(), SCIPsetInfinity(), SCIPsnprintf(), SCIPvarGetLbOriginal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetOrigvarSum(), SCIPvarGetType(), SCIPvarGetUbOriginal(), SCIPverbMessage(), TRUE, valid, and vars.
Referenced by SCIPmergeBendersSubproblemIntoMaster().
|
static |
when applying a decomposition from a supplied format, constraints must be transferred from the master problem to the subproblem. This is achieved by adding new constraints to the subproblem
set | global SCIP settings |
subproblem | the SCIP instance for the subproblem |
varmap | the variable hash map mapping the source variables to the target variables |
sourcecons | the constraint that being added to the subproblem |
Definition at line 5498 of file benders.c.
References assert(), i, NULL, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsMarkedPropagate(), SCIPconsIsModifiable(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateVar(), SCIPdebugMessage, SCIPerrorMessage, SCIPfreeBufferArray, SCIPgetConsCopy(), SCIPgetConsNVars(), SCIPgetConsVars(), SCIPhashmapExists(), SCIPhashmapInsert(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsInitial(), SCIPvarIsRemovable(), TRUE, and var.
Referenced by SCIPbendersApplyDecomposition().
|
static |
removes the variables and constraints from the master problem that have been transferred to a subproblem when the decomposition was applied.
scip | the SCIP data structure |
conss | the master problem constraints |
vars | the master problem variables, can be NULL |
conslabels | the labels indicating the block for each constraint |
varslabels | the labels indicating the block for each variable, can be NULL |
nconss | the number of constraints |
nvars | the number of variables |
Definition at line 5582 of file benders.c.
References assert(), i, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_PROBLEM, SCIPconsIsDeleted(), SCIPdelCons(), SCIPdelVar(), SCIPgetStage(), SCIPvarIsDeleted(), and vars.
Referenced by SCIPbendersApplyDecomposition().
SCIP_RETCODE SCIPbendersApplyDecomposition | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set, | ||
SCIP_DECOMP * | decomp ) |
Applies a Benders' decomposition to the problem based upon the decomposition selected from the storage
benders | Benders' decomposition |
set | global SCIP settings |
decomp | the decomposition to apply to the problem |
Definition at line 5625 of file benders.c.
References addConstraintToBendersSubproblem(), assert(), SCIP_Benders::freesubprobs, i, NULL, nvars, removeVariablesAndConstraintsFromMaster(), SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_PARAMSETTING_OFF, SCIPallocBufferArray, SCIPblkmem(), SCIPcopyPlugins(), SCIPcreate(), SCIPcreateBendersDefault(), SCIPcreateProbBasic(), SCIPdebugMessage, SCIPdecompGetConsLabels(), SCIPdecompGetNBlocks(), SCIPdecompGetVarsLabels(), SCIPfreeBufferArray, SCIPgetConss(), SCIPgetNConss(), SCIPgetProbName(), SCIPgetVarsData(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetPresolving(), SCIPsnprintf(), TRUE, valid, and vars.
Referenced by SCIPapplyBendersDecomposition().
SCIP_RETCODE SCIPbendersGetVar | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set, | ||
SCIP_VAR * | var, | ||
SCIP_VAR ** | mappedvar, | ||
int | probnumber ) |
Returns the corresponding master or subproblem variable for the given variable. This provides a call back for the variable mapping between the master and subproblems.
benders | Benders' decomposition |
set | global SCIP settings |
var | the variable for which the corresponding variable is desired |
mappedvar | the variable that is mapped to var |
probnumber | the problem number for the desired variable, -1 for the master problem |
Definition at line 5745 of file benders.c.
References assert(), AUXILIARYVAR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPvarGetName(), and var.
Referenced by checkSubproblemConvexity(), createSubproblems(), SCIPbendersChgMastervarsToCont(), SCIPbendersSetupSubproblem(), SCIPgetBendersMasterVar(), and SCIPgetBendersSubproblemVar().
void SCIPbendersSetCopy | ( | SCIP_BENDERS * | benders | ) |
sets copy callback of Benders' decomposition
benders | Benders' decomposition copy callback of Benders' decomposition |
Definition at line 5792 of file benders.c.
References assert(), NULL, and SCIP_DECL_BENDERSCOPY.
Referenced by SCIPsetBendersCopy().
void SCIPbendersSetFree | ( | SCIP_BENDERS * | benders | ) |
sets destructor callback of Benders' decomposition
benders | Benders' decomposition destructor of Benders' decomposition |
Definition at line 5803 of file benders.c.
References assert(), NULL, and SCIP_DECL_BENDERSFREE.
Referenced by SCIPsetBendersFree().
void SCIPbendersSetInit | ( | SCIP_BENDERS * | benders | ) |
sets initialization callback of Benders' decomposition
benders | Benders' decomposition initialize the Benders' decomposition |
Definition at line 5814 of file benders.c.
References assert(), and NULL.
Referenced by SCIPsetBendersInit().
void SCIPbendersSetExit | ( | SCIP_BENDERS * | benders | ) |
sets deinitialization callback of Benders' decomposition
benders | Benders' decomposition deinitialize the Benders' decomposition |
Definition at line 5825 of file benders.c.
References assert(), and NULL.
Referenced by SCIPsetBendersExit().
void SCIPbendersSetInitpre | ( | SCIP_BENDERS * | benders | ) |
sets presolving initialization callback of Benders' decomposition
benders | Benders' decomposition initialize presolving for Benders' decomposition |
Definition at line 5836 of file benders.c.
References assert(), and NULL.
Referenced by SCIPsetBendersInitpre().
void SCIPbendersSetExitpre | ( | SCIP_BENDERS * | benders | ) |
sets presolving deinitialization callback of Benders' decomposition
benders | Benders' decomposition deinitialize presolving for Benders' decomposition |
Definition at line 5847 of file benders.c.
References assert(), and NULL.
Referenced by SCIPsetBendersExitpre().
void SCIPbendersSetInitsol | ( | SCIP_BENDERS * | benders | ) |
sets solving process initialization callback of Benders' decomposition
benders | Benders' decomposition solving process initialization callback of Benders' decomposition |
Definition at line 5858 of file benders.c.
References assert(), and NULL.
Referenced by SCIPsetBendersInitsol().
void SCIPbendersSetExitsol | ( | SCIP_BENDERS * | benders | ) |
sets solving process deinitialization callback of Benders' decomposition
benders | Benders' decomposition solving process deinitialization callback of Benders' decomposition |
Definition at line 5869 of file benders.c.
References assert(), and NULL.
Referenced by SCIPsetBendersExitsol().
void SCIPbendersSetPresubsolve | ( | SCIP_BENDERS * | benders | ) |
sets the pre subproblem solve callback of Benders' decomposition
benders | Benders' decomposition called prior to the subproblem solving loop |
Definition at line 5880 of file benders.c.
References assert(), and NULL.
Referenced by SCIPsetBendersPresubsolve().
void SCIPbendersSetSolvesubconvex | ( | SCIP_BENDERS * | benders | ) |
sets convex solve callback of Benders' decomposition
benders | Benders' decomposition solving method for the convex Benders' decomposition subproblem |
Definition at line 5891 of file benders.c.
References assert(), and NULL.
Referenced by SCIPsetBendersSolveAndFreesub().
void SCIPbendersSetSolvesub | ( | SCIP_BENDERS * | benders | ) |
sets solve callback of Benders' decomposition
benders | Benders' decomposition solving method for a Benders' decomposition subproblem |
Definition at line 5902 of file benders.c.
References assert(), and NULL.
Referenced by SCIPsetBendersSolveAndFreesub().
void SCIPbendersSetPostsolve | ( | SCIP_BENDERS * | benders | ) |
sets post-solve callback of Benders' decomposition
benders | Benders' decomposition solving process deinitialization callback of Benders' decomposition |
Definition at line 5913 of file benders.c.
References assert(), and NULL.
Referenced by SCIPsetBendersPostsolve().
void SCIPbendersSetSubproblemComp | ( | SCIP_BENDERS * | benders | ) |
sets post-solve callback of Benders' decomposition
benders | Benders' decomposition a comparator for defining the solving order of the subproblems |
Definition at line 5924 of file benders.c.
References assert(), and NULL.
Referenced by SCIPsetBendersSubproblemComp().
void SCIPbendersSetFreesub | ( | SCIP_BENDERS * | benders | ) |
sets free subproblem callback of Benders' decomposition
benders | Benders' decomposition the freeing callback for the subproblem |
Definition at line 5935 of file benders.c.
References assert(), and NULL.
Referenced by SCIPsetBendersSolveAndFreesub().
void SCIPbendersSetPriority | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set, | ||
int | priority ) |
sets priority of Benders' decomposition
benders | Benders' decomposition |
set | global SCIP settings |
priority | new priority of the Benders' decomposition |
Definition at line 5976 of file benders.c.
References assert(), FALSE, NULL, and SCIP_Benders::priority.
Referenced by SCIPsetBendersPriority().
void SCIPbendersEnableOrDisableClocks | ( | SCIP_BENDERS * | benders, |
SCIP_Bool | enable ) |
enables or disables all clocks of the Benders' decomposition, depending on the value of the flag
benders | the Benders' decomposition for which all clocks should be enabled or disabled |
enable | should the clocks of the Benders' decomposition be enabled? |
Definition at line 6082 of file benders.c.
References assert(), SCIP_Benders::bendersclock, NULL, SCIP_Bool, SCIPclockEnableOrDisable(), and SCIP_Benders::setuptime.
SCIP_RETCODE SCIPbendersAddSubproblem | ( | SCIP_BENDERS * | benders, |
SCIP * | subproblem ) |
adds a subproblem to the Benders' decomposition data. If a custom subproblem solving method is used, then the subproblem pointer can be set to NULL
benders | Benders' decomposition |
subproblem | subproblem to be added to the data storage, can be NULL |
Definition at line 6146 of file benders.c.
References assert(), SCIP_Benders::naddedsubprobs, SCIP_Benders::name, SCIP_Benders::nsubproblems, NULL, SCIP_ERROR, SCIP_OKAY, SCIPerrorMessage, and SCIP_Benders::subproblems.
Referenced by SCIPaddBendersSubproblem().
void SCIPbendersRemoveSubproblems | ( | SCIP_BENDERS * | benders | ) |
removes the subproblems from the Benders' decomposition data
benders | Benders' decomposition |
Definition at line 6170 of file benders.c.
References assert(), BMSclearMemoryArray, SCIP_Benders::naddedsubprobs, NULL, and SCIP_Benders::subproblems.
void SCIPbendersSetSubproblemsAreInfeasible | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set ) |
sets the flag to indicate that at least one subproblem is always infeasible NOTE: this is without any variable fixing being performed
benders | Benders' decomposition |
set | global SCIP settings |
Definition at line 6481 of file benders.c.
References assert(), NULL, SCIPgetDepth(), SCIP_Benders::subprobsinfeasible, and TRUE.
Referenced by createSubproblems(), SCIPbendersChgMastervarsToCont(), and SCIPbendersSetupSubproblem().
SCIP_RETCODE SCIPbendersChgMastervarsToCont | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set, | ||
int | probnumber ) |
changes all of the master problem variables in the given subproblem to continuous.
benders | Benders' decomposition |
set | global SCIP settings |
probnumber | the subproblem number |
Definition at line 6506 of file benders.c.
References assert(), checkSubproblemConvexity(), i, initialiseLPSubproblem(), nbinvars, nintvars, NULL, SCIP_BENDERSSUBTYPE_CONVEXCONT, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_CONTINUOUS, SCIPbendersGetMastervarsCont(), SCIPbendersGetNSubproblems(), SCIPbendersGetSubproblemType(), SCIPbendersGetVar(), SCIPbendersSetMastervarsCont(), SCIPbendersSetSubproblemsAreInfeasible(), SCIPbendersSubproblem(), SCIPchgVarType(), SCIPgetVarsData(), SCIPvarGetType(), TRUE, and vars.
Referenced by createSubproblems(), and SCIPbendersSetupSubproblem().
void SCIPbendersSetSubproblemEnabled | ( | SCIP_BENDERS * | benders, |
int | probnumber, | ||
SCIP_Bool | enabled ) |
Sets whether the subproblem is enabled or disabled. A subproblem is disabled if it has been merged into the master problem.
benders | Benders' decomposition |
probnumber | the subproblem number |
enabled | flag to indicate whether the subproblem is enabled |
Definition at line 6672 of file benders.c.
References assert(), SCIP_Benders::nactivesubprobs, NULL, SCIP_Bool, SCIPbendersGetNSubproblems(), SCIP_Benders::subprobenabled, and subproblemIsActive().
Referenced by SCIPbendersMergeSubproblemIntoMaster().
SCIP_RETCODE SCIPbendersSetMastervarsCont | ( | SCIP_BENDERS * | benders, |
int | probnumber, | ||
SCIP_Bool | arecont ) |
sets a flag to indicate whether the master variables are all set to continuous
benders | Benders' decomposition |
probnumber | the subproblem number |
arecont | flag to indicate whether the master problem variables are continuous |
Definition at line 6710 of file benders.c.
References assert(), SCIP_Benders::mastervarscont, NULL, SCIP_BENDERSSUBTYPE_CONVEXCONT, SCIP_BENDERSSUBTYPE_CONVEXDIS, SCIP_BENDERSSUBTYPE_NONCONVEXCONT, SCIP_BENDERSSUBTYPE_NONCONVEXDIS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPbendersGetNSubproblems(), SCIPbendersGetSubproblemType(), SCIPbendersSetSubproblemType(), SCIPbendersSubproblem(), SCIPendProbing(), and SCIPinProbing().
Referenced by SCIPbendersChgMastervarsToCont().
SCIP_Bool SCIPbendersGetMastervarsCont | ( | SCIP_BENDERS * | benders, |
int | probnumber ) |
returns whether the master variables are all set to continuous
benders | Benders' decomposition |
probnumber | the subproblem number |
Definition at line 6745 of file benders.c.
References assert(), SCIP_Benders::mastervarscont, NULL, SCIP_Bool, and SCIPbendersGetNSubproblems().
Referenced by SCIPbendersChgMastervarsToCont().
SCIP_RETCODE SCIPbendersStoreCut | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set, | ||
SCIP_VAR ** | vars, | ||
SCIP_Real * | vals, | ||
SCIP_Real | lhs, | ||
SCIP_Real | rhs, | ||
int | nvars ) |
adds the data for the generated cuts to the Benders' cut storage
benders | Benders' decomposition cut |
set | global SCIP settings |
vars | the variables that have non-zero coefficients in the cut |
vals | the coefficients of the variables in the cut |
lhs | the left hand side of the cut |
rhs | the right hand side of the cut |
nvars | the number of variables with non-zero coefficients in the cut |
Definition at line 6889 of file benders.c.
References assert(), BMSreallocBlockMemoryArray, SCIP_BenderscutCut::lhs, SCIP_Benders::nstoredcuts, NULL, nvars, SCIP_BenderscutCut::nvars, SCIP_BenderscutCut::rhs, SCIP_ALLOC, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPblkmem(), SCIPduplicateBlockMemoryArray, SCIPsetCalcMemGrowSize(), SCIP_Benders::storedcuts, SCIP_Benders::storedcutssize, SCIP_BenderscutCut::vals, SCIP_BenderscutCut::vars, and vars.
Referenced by SCIPstoreBendersCut().
void SCIPbendersSetBenderscutsSorted | ( | SCIP_BENDERS * | benders, |
SCIP_Bool | sorted ) |
sets the sorted flags in the Benders' decomposition
benders | Benders' decomposition structure |
sorted | the value to set the sorted flag to |
Definition at line 6937 of file benders.c.
References assert(), SCIP_Benders::benderscutsnamessorted, SCIP_Benders::benderscutssorted, NULL, and SCIP_Bool.
Referenced by SCIPsetBenderscutPriority().
SCIP_RETCODE SCIPbendersIncludeBenderscut | ( | SCIP_BENDERS * | benders, |
SCIP_SET * | set, | ||
SCIP_BENDERSCUT * | benderscut ) |
inserts a Benders' cut into the Benders' cuts list
benders | Benders' decomposition structure |
set | global SCIP settings |
benderscut | Benders' cut |
Definition at line 6949 of file benders.c.
References assert(), SCIP_Benders::benderscuts, SCIP_Benders::benderscutssize, SCIP_Benders::benderscutssorted, BMSreallocMemoryArray, FALSE, SCIP_Benders::nbenderscuts, NULL, SCIP_ALLOC, SCIP_OKAY, and SCIPsetCalcMemGrowSize().
Referenced by SCIPincludeBenderscut(), and SCIPincludeBenderscutBasic().
void SCIPbendersSortBenderscuts | ( | SCIP_BENDERS * | benders | ) |
sorts Benders' decomposition cuts by priorities
benders | Benders' decomposition |
Definition at line 7038 of file benders.c.
References assert(), SCIP_Benders::benderscuts, SCIP_Benders::benderscutsnamessorted, SCIP_Benders::benderscutssorted, FALSE, SCIP_Benders::nbenderscuts, NULL, SCIPsortPtr(), and TRUE.
Referenced by SCIPbendersCopyInclude(), SCIPbendersExit(), SCIPbendersExitsol(), SCIPbendersInit(), and SCIPbendersInitsol().
void SCIPbendersSortBenderscutsName | ( | SCIP_BENDERS * | benders | ) |
sorts Benders' decomposition cuts by name
benders | Benders' decomposition |
Definition at line 7053 of file benders.c.
References assert(), SCIP_Benders::benderscuts, SCIP_Benders::benderscutsnamessorted, SCIP_Benders::benderscutssorted, FALSE, SCIP_Benders::nbenderscuts, NULL, SCIPsortPtr(), and TRUE.