cons_benders.c
Go to the documentation of this file.
21 * Two constraint handlers are implemented for the generation of Benders' decomposition cuts. When included in a
22 * problem, the Benders' decomposition constraint handlers generate cuts during the enforcement of LP and relaxation
23 * solutions. Additionally, Benders' decomposition cuts can be generated when checking the feasibility of solutions with
26 * This constraint handler has an enforcement priority that is less than the integer constraint handler. This means that
27 * only integer feasible solutions from the LP solver are enforced by this constraint handler. This is the traditional
28 * behaviour of the branch-and-check approach to Benders' decomposition. Additionally, the check priority is set low,
29 * such that this expensive constraint handler is only called as a final check on primal feasible solutions.
31 * This constraint handler in the standard constraint handler that should be added when using Benders' decomposition.
32 * Additionally, there is a flag in SCIPincludeConshdlrBenders that permits the addition of the LP constraint handler,
33 * cons_benderslp. The use of both cons_benders and cons_benderslp allows the user to perform a multiphase Benders'
37 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
51 #define CONSHDLR_ENFOPRIORITY -100 /**< priority of the constraint handler for constraint enforcing */
52 #define CONSHDLR_CHECKPRIORITY -5000000 /**< priority of the constraint handler for checking feasibility */
53 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
55 #define CONSHDLR_MAXPREROUNDS 0 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
56 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
57 #define CONSHDLR_NEEDSCONS FALSE /**< should the constraint handler be skipped, if no constraints are available? */
80 /** constructs a new solution based upon the solutions to the Benders' decomposition subproblems */
139 /* getting the auxiliary variables and the number of subproblems from the Benders' decomposition structure */
176 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->checkedsols, conshdlrdata->checkedsolssize, newsize) );
240 * This method is called from cons_benderslp and cons_benders. If the method is called from cons_benderslp, then the
241 * solutions are not guaranteed to be integer feasible. This is because the default priority is set greater than the
242 * integer constraint handler. If this method is called from cons_benders, then, because the default enforcement
243 * priority is set less than that of the integer constraint handler, then it can be assumed that the solutions are
246 * The checkint flag indicates whether integer feasibility can be assumed. If it is not assumed, i.e. checkint ==
247 * FALSE, then only the convex relaxations of the subproblems are solved. If integer feasibility is assumed, i.e.
248 * checkint == TRUE, then the convex relaxations and the full CIP are solved to generate Benders' cuts and check
286 /* if the solution is unbounded, then it may not be possible to generate any Benders' decomposition
287 * cuts. If the unboundedness is from the auxiliary variables, then cuts are required. Otherwise, if
288 * the unboundedness comes from original variables, then the unboundedness needs to be handled by other
303 SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], NULL, result, &infeasible, &auxviol, type, checkint) );
310 SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], sol, result, &infeasible, &auxviol, type, checkint) );
316 SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], NULL, result, &infeasible, &auxviol, type, checkint) );
326 /* The decompositions are checked until one is found that is not feasible. Not being feasible could mean that
327 * infeasibility of the original problem has been proven or a constraint has been added. If the result
333 /* if the constraint handler was called with an integer feasible solution, then a feasible solution can be proposed */
336 /* in the case that the problem is feasible, this means that all subproblems are feasible. The auxiliary variables
346 /* if no Benders' decomposition were run, then the result is returned as SCIP_FEASIBLE. The SCIP_DIDNOTRUN result
347 * indicates that no subproblems were checked or that cuts were disabled, so that it is not guaranteed that this
373 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
406 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->checkedsols, conshdlrdata->checkedsolssize) );
412 /** deinitialization method of constraint handler (called before transformed problem is freed) */
446 SCIP_CALL( SCIPconsBendersEnforceSolution(scip, NULL, conshdlr, result, SCIP_BENDERSENFOTYPE_LP, TRUE) );
469 SCIP_CALL( SCIPconsBendersEnforceSolution(scip, sol, conshdlr, result, SCIP_BENDERSENFOTYPE_RELAX, TRUE) );
492 SCIP_CALL( SCIPconsBendersEnforceSolution(scip, NULL, conshdlr, result, SCIP_BENDERSENFOTYPE_PSEUDO, TRUE) );
503 * This function checks the feasibility of the Benders' decomposition master problem. In the case that the problem is
504 * feasible, then the auxiliary variables must be updated with the subproblem objective function values. It is not
558 /* in the case of multiple Benders' decompositions, the subproblems are solved until a constriant is added or
564 /* in the case that the problem is feasible, this means that all subproblems are feasible. The auxiliary variables
576 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "all subproblems are feasible but there is a violation in the auxiliary variables\n");
582 /* if no Benders' decomposition were run, then the result is returned as SCIP_FEASIBLE. The SCIP_DIDNOTRUN result
583 * indicates that no subproblems were checked or that cuts were disabled, so that it is not guaranteed that this
597 * This method is used to update the lower bounds of the auxiliary problem and to identify infeasibility before the
598 * subproblems are solved. When SCIP is copied, the Benders' decomposition subproblems from the source SCIP are
599 * transferred to the target SCIP. So there is no need to perform this presolving step in the copied SCIP, since the
617 /* this presolving step is only valid for the main SCIP instance. If the SCIP instance is copied, then the presolving
629 /* it is only possible to compute the lower bound of the subproblems if the constraint handler is active */
649 SCIP_CALL( SCIPcomputeBendersSubproblemLowerbound(scip, benders[i], j, &lowerbound, &infeasible) );
663 SCIPdebugMsg(scip, "Tightened lower bound of <%s> to %g\n", SCIPvarGetName(auxiliaryvar), lowerbound);
684 * The auxiliary variables and the master problem variables need to lock added by the Benders' decomposition
685 * constraint. The auxiliary variables require a down lock. The master problem variable need both up and down lock.
686 * The master problem variables require locks in both directions because the coefficients in all potential Benders'
708 /* the locks should only be added if the Benders' decomposition constraint handler has been activated */
722 /* if the auxiliary variable exists, then we need to add a down lock. Initially, a down lock is added to all
723 * auxiliary variables during creating. This is because the creation of auxiliary variable occurs after
724 * CONS_LOCK is called. The inclusion of the auxiliary variables in this function is to cover the case if locks
739 /* adding up and down locks for all master problem variables. Since the locks for all constraint handlers
740 * without constraints, no auxiliary variables have been added. As such, all variables are master variables.
786 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolBenders, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
790 "constraints/" CONSHDLR_NAME "/active", "is the Benders' decomposition constraint handler active?",
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:86
Definition: type_result.h:33
SCIP_VAR * SCIPbendersGetAuxiliaryVar(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6132
Definition: type_result.h:37
constraint handler for Benders' decomposition
primal heuristic that tries a given solution
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1213
Definition: struct_scip.h:59
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:308
void SCIPbendersUpdateSubproblemLowerbound(SCIP_BENDERS *benders, int probnumber, SCIP_Real lowerbound)
Definition: benders.c:6685
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:166
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4263
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:123
Definition: type_result.h:49
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
Definition: struct_var.h:198
Definition: type_benders.h:40
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:5940
methods commonly used by primal heuristics
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:48
SCIP_Real SCIPbendersGetSubproblemObjval(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6171
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:525
SCIP_RETCODE SCIPsetConshdlrInit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINIT((*consinit)))
Definition: scip_cons.c:381
SCIP_Real SCIPgetBendersAuxiliaryVarVal(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, int probnumber)
Definition: scip_benders.c:922
SCIP_Bool SCIPbendersCutRelaxation(SCIP_BENDERS *benders)
Definition: benders.c:6074
Definition: type_benders.h:37
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:357
Definition: struct_benders.h:48
Definition: type_benders.h:39
Definition: struct_sol.h:64
SCIP_RETCODE SCIPcreateRelaxSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:425
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip_sol.c:610
SCIP_RETCODE SCIPheurPassSolAddSol(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol)
Definition: heur_trysol.c:284
SCIP_RETCODE SCIPsetConshdlrExit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXIT((*consexit)))
Definition: scip_cons.c:405
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4677
Definition: type_result.h:35
static SCIP_DECL_CONSENFORELAX(consEnforelaxBenders)
Definition: cons_benders.c:458
Definition: struct_cons.h:117
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:613
Definition: type_result.h:36
SCIP_RETCODE SCIPconsBendersEnforceSolution(SCIP *scip, SCIP_SOL *sol, SCIP_CONSHDLR *conshdlr, SCIP_RESULT *result, SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint)
Definition: cons_benders.c:252
Definition: type_retcode.h:33
void SCIPmessagePrintInfo(SCIP_MESSAGEHDLR *messagehdlr, const char *formatstr,...)
Definition: message.c:585
Definition: struct_heur.h:88
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:332
SCIP_RETCODE SCIPcreatePseudoSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:452
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4199
static SCIP_RETCODE constructValidSolution(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_BENDERSENFOTYPE type)
Definition: cons_benders.c:83
SCIP_RETCODE SCIPcreateLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:362
Definition: type_benders.h:38
Definition: type_set.h:45
SCIP_RETCODE SCIPcomputeBendersSubproblemLowerbound(SCIP *scip, SCIP_BENDERS *benders, int probnumber, SCIP_Real *lowerbound, SCIP_Bool *infeasible)
Definition: scip_benders.c:950
Definition: type_set.h:39
Definition: type_lp.h:36
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBenders)
Definition: cons_benders.c:363
Definition: type_var.h:84
SCIP_VAR ** SCIPbendersGetAuxiliaryVars(SCIP_BENDERS *benders)
Definition: benders.c:6144
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
Definition: objbenders.h:33
Definition: type_var.h:43
static SCIP_Bool unboundedAuxiliaryVariables(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol)
Definition: cons_benders.c:210
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:3440
SCIP_RETCODE SCIPgetOrigVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:2351
Definition: type_result.h:39
SCIP callable library.
SCIP_RETCODE SCIPincludeConshdlrBenders(SCIP *scip)
Definition: cons_benders.c:760