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?",
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
Definition: type_result.h:42
Definition: type_result.h:46
constraint handler for Benders' decomposition
primal heuristic that tries a given solution
SCIP_Real SCIPbendersGetSubproblemObjval(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6179
Definition: struct_scip.h:68
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:317
Definition: type_result.h:58
Definition: struct_var.h:207
Definition: type_benders.h:49
SCIP_RETCODE SCIPconsBendersEnforceSolution(SCIP *scip, SCIP_SOL *sol, SCIP_CONSHDLR *conshdlr, SCIP_RESULT *result, SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint)
Definition: cons_benders.c:261
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:175
SCIP_VAR ** SCIPbendersGetAuxiliaryVars(SCIP_BENDERS *benders)
Definition: benders.c:6152
methods commonly used by primal heuristics
SCIP_Real SCIPgetBendersAuxiliaryVarVal(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, int probnumber)
Definition: scip_benders.c:931
SCIP_RETCODE SCIPheurPassSolAddSol(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol)
Definition: heur_trysol.c:293
SCIP_RETCODE SCIPgetOrigVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:2365
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4676
SCIP_RETCODE SCIPincludeConshdlrBenders(SCIP *scip)
Definition: cons_benders.c:769
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
SCIP_RETCODE SCIPcreateLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:370
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
Definition: type_benders.h:46
Definition: struct_benders.h:57
Definition: type_benders.h:48
Definition: struct_sol.h:73
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4259
SCIP_RETCODE SCIPcomputeBendersSubproblemLowerbound(SCIP *scip, SCIP_BENDERS *benders, int probnumber, SCIP_Real *lowerbound, SCIP_Bool *infeasible)
Definition: scip_benders.c:959
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip_sol.c:618
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:341
Definition: type_result.h:44
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:458
static SCIP_DECL_CONSENFORELAX(consEnforelaxBenders)
Definition: cons_benders.c:467
Definition: struct_cons.h:126
Definition: type_result.h:45
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:366
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4202
Definition: type_retcode.h:42
void SCIPmessagePrintInfo(SCIP_MESSAGEHDLR *messagehdlr, const char *formatstr,...)
Definition: message.c:594
Definition: struct_heur.h:97
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1221
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:3450
static SCIP_RETCODE constructValidSolution(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_BENDERSENFOTYPE type)
Definition: cons_benders.c:92
Definition: type_benders.h:47
Definition: type_set.h:54
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:5948
SCIP_RETCODE SCIPcreateRelaxSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:433
SCIP_RETCODE SCIPcreatePseudoSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:460
Definition: type_set.h:48
Definition: type_lp.h:45
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:484
void SCIPbendersUpdateSubproblemLowerbound(SCIP_BENDERS *benders, int probnumber, SCIP_Real lowerbound)
Definition: benders.c:6693
SCIP_RETCODE SCIPsetConshdlrInit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINIT((*consinit)))
Definition: scip_cons.c:390
SCIP_RETCODE SCIPsetConshdlrExit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXIT((*consexit)))
Definition: scip_cons.c:414
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:534
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBenders)
Definition: cons_benders.c:372
Definition: type_var.h:93
SCIP_Bool SCIPbendersCutRelaxation(SCIP_BENDERS *benders)
Definition: benders.c:6082
SCIP_VAR * SCIPbendersGetAuxiliaryVar(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6140
Definition: objbenders.h:43
Definition: type_var.h:52
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 SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1361
static SCIP_Bool unboundedAuxiliaryVariables(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol)
Definition: cons_benders.c:219
Definition: type_result.h:48
SCIP callable library.
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