cons_benders.c
Go to the documentation of this file.
30 * Two constraint handlers are implemented for the generation of Benders' decomposition cuts. When included in a
31 * problem, the Benders' decomposition constraint handlers generate cuts during the enforcement of LP and relaxation
32 * solutions. Additionally, Benders' decomposition cuts can be generated when checking the feasibility of solutions with
35 * This constraint handler has an enforcement priority that is less than the integer constraint handler. This means that
36 * only integer feasible solutions from the LP solver are enforced by this constraint handler. This is the traditional
37 * behaviour of the branch-and-check approach to Benders' decomposition. Additionally, the check priority is set low,
38 * such that this expensive constraint handler is only called as a final check on primal feasible solutions.
40 * This constraint handler in the standard constraint handler that should be added when using Benders' decomposition.
41 * Additionally, there is a flag in SCIPincludeConshdlrBenders that permits the addition of the LP constraint handler,
42 * cons_benderslp. The use of both cons_benders and cons_benderslp allows the user to perform a multiphase Benders'
46/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
60#define CONSHDLR_ENFOPRIORITY -100 /**< priority of the constraint handler for constraint enforcing */
61#define CONSHDLR_CHECKPRIORITY -5000000 /**< priority of the constraint handler for checking feasibility */
62#define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
64#define CONSHDLR_MAXPREROUNDS 0 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
65#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
66#define CONSHDLR_NEEDSCONS FALSE /**< should the constraint handler be skipped, if no constraints are available? */
89/** constructs a new solution based upon the solutions to the Benders' decomposition subproblems */
148 /* getting the auxiliary variables and the number of subproblems from the Benders' decomposition structure */
185 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->checkedsols, conshdlrdata->checkedsolssize, newsize) );
249 * This method is called from cons_benderslp and cons_benders. If the method is called from cons_benderslp, then the
250 * solutions are not guaranteed to be integer feasible. This is because the default priority is set greater than the
251 * integer constraint handler. If this method is called from cons_benders, then, because the default enforcement
252 * priority is set less than that of the integer constraint handler, then it can be assumed that the solutions are
255 * The checkint flag indicates whether integer feasibility can be assumed. If it is not assumed, i.e. checkint ==
256 * FALSE, then only the convex relaxations of the subproblems are solved. If integer feasibility is assumed, i.e.
257 * checkint == TRUE, then the convex relaxations and the full CIP are solved to generate Benders' cuts and check
295 /* if the solution is unbounded, then it may not be possible to generate any Benders' decomposition
296 * cuts. If the unboundedness is from the auxiliary variables, then cuts are required. Otherwise, if
297 * the unboundedness comes from original variables, then the unboundedness needs to be handled by other
312 SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], NULL, result, &infeasible, &auxviol, type, checkint) );
319 SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], sol, result, &infeasible, &auxviol, type, checkint) );
325 SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], NULL, result, &infeasible, &auxviol, type, checkint) );
335 /* The decompositions are checked until one is found that is not feasible. Not being feasible could mean that
336 * infeasibility of the original problem has been proven or a constraint has been added. If the result
342 /* if the constraint handler was called with an integer feasible solution, then a feasible solution can be proposed */
345 /* in the case that the problem is feasible, this means that all subproblems are feasible. The auxiliary variables
355 /* if no Benders' decomposition were run, then the result is returned as SCIP_FEASIBLE. The SCIP_DIDNOTRUN result
356 * indicates that no subproblems were checked or that cuts were disabled, so that it is not guaranteed that this
382/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
415 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->checkedsols, conshdlrdata->checkedsolssize) );
421/** deinitialization method of constraint handler (called before transformed problem is freed) */
455 SCIP_CALL( SCIPconsBendersEnforceSolution(scip, NULL, conshdlr, result, SCIP_BENDERSENFOTYPE_LP, TRUE) );
478 SCIP_CALL( SCIPconsBendersEnforceSolution(scip, sol, conshdlr, result, SCIP_BENDERSENFOTYPE_RELAX, TRUE) );
501 SCIP_CALL( SCIPconsBendersEnforceSolution(scip, NULL, conshdlr, result, SCIP_BENDERSENFOTYPE_PSEUDO, TRUE) );
512 * This function checks the feasibility of the Benders' decomposition master problem. In the case that the problem is
513 * feasible, then the auxiliary variables must be updated with the subproblem objective function values. It is not
567 /* in the case of multiple Benders' decompositions, the subproblems are solved until a constriant is added or
573 /* in the case that the problem is feasible, this means that all subproblems are feasible. The auxiliary variables
585 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "all subproblems are feasible but there is a violation in the auxiliary variables\n");
591 /* if no Benders' decomposition were run, then the result is returned as SCIP_FEASIBLE. The SCIP_DIDNOTRUN result
592 * indicates that no subproblems were checked or that cuts were disabled, so that it is not guaranteed that this
606 * This method is used to update the lower bounds of the auxiliary problem and to identify infeasibility before the
607 * subproblems are solved. When SCIP is copied, the Benders' decomposition subproblems from the source SCIP are
608 * transferred to the target SCIP. So there is no need to perform this presolving step in the copied SCIP, since the
626 /* this presolving step is only valid for the main SCIP instance. If the SCIP instance is copied, then the presolving
638 /* it is only possible to compute the lower bound of the subproblems if the constraint handler is active */
658 SCIP_CALL( SCIPcomputeBendersSubproblemLowerbound(scip, benders[i], j, &lowerbound, &infeasible) );
672 SCIPdebugMsg(scip, "Tightened lower bound of <%s> to %g\n", SCIPvarGetName(auxiliaryvar), lowerbound);
693 * The auxiliary variables and the master problem variables need to lock added by the Benders' decomposition
694 * constraint. The auxiliary variables require a down lock. The master problem variable need both up and down lock.
695 * The master problem variables require locks in both directions because the coefficients in all potential Benders'
717 /* the locks should only be added if the Benders' decomposition constraint handler has been activated */
731 /* if the auxiliary variable exists, then we need to add a down lock. Initially, a down lock is added to all
732 * auxiliary variables during creating. This is because the creation of auxiliary variable occurs after
733 * CONS_LOCK is called. The inclusion of the auxiliary variables in this function is to cover the case if locks
748 /* adding up and down locks for all master problem variables. Since the locks for all constraint handlers
749 * without constraints, no auxiliary variables have been added. As such, all variables are master variables.
795 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolBenders, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
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)
Definition: cons_benders.c:91
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBenders)
Definition: cons_benders.c:371
static SCIP_DECL_CONSENFORELAX(consEnforelaxBenders)
Definition: cons_benders.c:466
static SCIP_Bool unboundedAuxiliaryVariables(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol)
Definition: cons_benders.c:218
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)
Definition: cons_benders.c:260
SCIP_RETCODE SCIPincludeConshdlrBenders(SCIP *scip)
Definition: cons_benders.c:768
SCIP_RETCODE SCIPgetOrigVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:2357
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
SCIP_RETCODE SCIPheurPassSolAddSol(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol)
Definition: heur_trysol.c:293
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)
Definition: scip_param.c:57
SCIP_Bool SCIPbendersCutRelaxation(SCIP_BENDERS *benders)
Definition: benders.c:6102
SCIP_RETCODE SCIPcomputeBendersSubproblemLowerbound(SCIP *scip, SCIP_BENDERS *benders, int probnumber, SCIP_Real *lowerbound, SCIP_Bool *infeasible)
Definition: scip_benders.c:959
SCIP_VAR * SCIPbendersGetAuxiliaryVar(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6160
SCIP_Real SCIPgetBendersAuxiliaryVarVal(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, int probnumber)
Definition: scip_benders.c:931
SCIP_VAR ** SCIPbendersGetAuxiliaryVars(SCIP_BENDERS *benders)
Definition: benders.c:6172
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:5968
void SCIPbendersUpdateSubproblemLowerbound(SCIP_BENDERS *benders, int probnumber, SCIP_Real lowerbound)
Definition: benders.c:6713
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)
Definition: scip_benders.c:622
SCIP_Real SCIPbendersGetSubproblemObjval(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6199
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:540
SCIP_RETCODE SCIPsetConshdlrInit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINIT((*consinit)))
Definition: scip_cons.c:396
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)
Definition: scip_cons.c:181
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:323
SCIP_RETCODE SCIPsetConshdlrExit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXIT((*consexit)))
Definition: scip_cons.c:420
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:347
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4217
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip_sol.c:474
SCIP_RETCODE SCIPcreateLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:226
SCIP_RETCODE SCIPcreateRelaxSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:289
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)
Definition: scip_sol.c:3251
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1077
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_RETCODE SCIPcreatePseudoSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:316
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:484
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:458
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4676
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4259
primal heuristic that tries a given solution
methods commonly used by primal heuristics
void SCIPmessagePrintInfo(SCIP_MESSAGEHDLR *messagehdlr, const char *formatstr,...)
Definition: message.c:594
Definition: objbenders.h:44
SCIP callable library.
Definition: struct_benders.h:58
Definition: struct_cons.h:127
Definition: struct_heur.h:98
Definition: struct_sol.h:74
Definition: struct_var.h:208
Definition: struct_scip.h:70