58#define CONSHDLR_NAME "benders"
59#define CONSHDLR_DESC "constraint handler to execute Benders' Decomposition"
60#define CONSHDLR_ENFOPRIORITY -100
61#define CONSHDLR_CHECKPRIORITY -5000000
62#define CONSHDLR_EAGERFREQ 100
64#define CONSHDLR_MAXPREROUNDS 0
65#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST
66#define CONSHDLR_NEEDSCONS FALSE
69#define DEFAULT_CHECKEDSOLSSIZE 20
70#define DEFAULT_ACTIVE FALSE
77struct SCIP_ConshdlrData
107 SCIP_Bool success =
TRUE;
146 for(
i = 0;
i < nactivebenders;
i++ )
153 for( j = 0; j < nsubproblems; j++ )
179 assert(conshdlrdata->ncheckedsols <= conshdlrdata->checkedsolssize);
180 if( conshdlrdata->ncheckedsols + 1 > conshdlrdata->checkedsolssize )
186 conshdlrdata->checkedsolssize = newsize;
188 assert(conshdlrdata->ncheckedsols + 1 <= conshdlrdata->checkedsolssize);
191 conshdlrdata->checkedsols[conshdlrdata->ncheckedsols] =
SCIPsolGetIndex(newsol);
192 conshdlrdata->ncheckedsols++;
225 SCIP_Bool unbounded =
FALSE;
234 for(
i = 0;
i < nsubproblems;
i++ )
270 SCIP_Bool infeasible;
286 for(
i = 0;
i < nactivebenders;
i++ )
293 SCIP_Bool unbounded =
FALSE;
413 conshdlrdata->ncheckedsols = 0;
453 if( conshdlrdata->active )
476 if( conshdlrdata->active )
499 if( conshdlrdata->active )
524 SCIP_Bool performcheck;
525 SCIP_Bool infeasible;
540 if( conshdlrdata->active )
547 for(
i = 0;
i < conshdlrdata->ncheckedsols;
i++ )
549 if( conshdlrdata->checkedsols[
i] == solindex )
551 conshdlrdata->checkedsols[0] = conshdlrdata->checkedsols[conshdlrdata->ncheckedsols - 1];
552 conshdlrdata->ncheckedsols--;
554 performcheck =
FALSE;
560 if( performcheck && nactivebenders > 0 )
562 for(
i = 0;
i < nactivebenders;
i++ )
639 if( conshdlrdata->active )
645 for(
i = 0;
i < nactivebenders;
i++ )
649 for( j = 0; j < nsubproblems; j++ )
652 SCIP_Real lowerbound;
653 SCIP_Bool infeasible;
718 if( conshdlrdata->active )
727 for(
i = 0;
i < nactivebenders;
i++ )
736 for( j = 0; j < nsubproblems; j++ )
751 for( j = 0; j <
nvars; j++ )
754 (nlockspos + nlocksneg)*nsubproblems) );
785 consEnfolpBenders, consEnfopsBenders, consCheckBenders, consLockBenders,
799 "constraints/" CONSHDLR_NAME "/active",
"is the Benders' decomposition constraint handler active?",
static SCIP_RETCODE constructValidSolution(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_BENDERSENFOTYPE type)
#define CONSHDLR_NEEDSCONS
#define CONSHDLR_CHECKPRIORITY
#define CONSHDLR_MAXPREROUNDS
#define DEFAULT_CHECKEDSOLSSIZE
#define CONSHDLR_PRESOLTIMING
#define CONSHDLR_EAGERFREQ
#define CONSHDLR_ENFOPRIORITY
static SCIP_Bool unboundedAuxiliaryVariables(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol)
constraint handler for Benders' decomposition
SCIP_RETCODE SCIPconsBendersEnforceSolution(SCIP *scip, SCIP_SOL *sol, SCIP_CONSHDLR *conshdlr, SCIP_RESULT *result, SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint)
SCIP_RETCODE SCIPincludeConshdlrBenders(SCIP *scip)
int SCIPgetSubscipDepth(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
SCIP_RETCODE SCIPgetOrigVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPheurPassSolAddSol(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
int SCIPgetNActiveBenders(SCIP *scip)
SCIP_Bool SCIPbendersCutRelaxation(SCIP_BENDERS *benders)
SCIP_BENDERS ** SCIPgetBenders(SCIP *scip)
SCIP_RETCODE SCIPcomputeBendersSubproblemLowerbound(SCIP *scip, SCIP_BENDERS *benders, int probnumber, SCIP_Real *lowerbound, SCIP_Bool *infeasible)
SCIP_VAR * SCIPbendersGetAuxiliaryVar(SCIP_BENDERS *benders, int probnumber)
SCIP_Real SCIPgetBendersAuxiliaryVarVal(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, int probnumber)
SCIP_Bool SCIPbendersCutPseudo(SCIP_BENDERS *benders)
SCIP_VAR ** SCIPbendersGetAuxiliaryVars(SCIP_BENDERS *benders)
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
void SCIPbendersUpdateSubproblemLowerbound(SCIP_BENDERS *benders, int probnumber, SCIP_Real lowerbound)
SCIP_Bool SCIPbendersCutLP(SCIP_BENDERS *benders)
SCIP_RETCODE SCIPsolveBendersSubproblems(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool *infeasible, SCIP_Bool *auxviol, SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint)
SCIP_Real SCIPbendersGetSubproblemObjval(SCIP_BENDERS *benders, int probnumber)
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)),)
SCIP_RETCODE SCIPsetConshdlrInit(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPsetConshdlrExit(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocMemory(scip, ptr)
#define SCIPfreeMemory(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
SCIP_RETCODE SCIPcreateLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
SCIP_RETCODE SCIPunlinkSol(SCIP *scip, SCIP_SOL *sol)
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
SCIP_RETCODE SCIPcreateRelaxSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
int SCIPsolGetIndex(SCIP_SOL *sol)
SCIP_RETCODE SCIPcheckSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *feasible)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_RETCODE SCIPcreatePseudoSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIPfreeSol(scip, &heurdata->sol))
assert(minobj< SCIPgetCutoffbound(scip))
primal heuristic that tries a given solution
methods commonly used by primal heuristics
void SCIPmessagePrintInfo(SCIP_MESSAGEHDLR *messagehdlr, const char *formatstr,...)
@ SCIP_BENDERSENFOTYPE_RELAX
@ SCIP_BENDERSENFOTYPE_LP
@ SCIP_BENDERSENFOTYPE_CHECK
@ SCIP_BENDERSENFOTYPE_PSEUDO
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
#define SCIP_DECL_CONSENFOLP(x)
#define SCIP_DECL_CONSEXIT(x)
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
#define SCIP_DECL_CONSENFORELAX(x)
#define SCIP_DECL_CONSENFOPS(x)
#define SCIP_DECL_CONSPRESOL(x)
#define SCIP_DECL_CONSLOCK(x)
#define SCIP_DECL_CONSINIT(x)
#define SCIP_DECL_CONSCHECK(x)
#define SCIP_DECL_CONSHDLRCOPY(x)
#define SCIP_DECL_CONSFREE(x)
@ SCIP_LPSOLSTAT_UNBOUNDEDRAY
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_STAGE_INITPRESOLVE