cons_benderslp.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 greater than the integer constraint handler. This means
27 * that all LP solutions will be first checked for feasibility with respect to the Benders' decomposition second stage
28 * constraints before performing an integrality check. This is part of a multi-phase approach for solving mixed integer
31 * A parameter is available to control the depth at which the non-integer LP solution are enforced by solving the
32 * Benders' decomposition subproblems. This parameter is set to 0 by default, indicating that non-integer LP solutions
36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
48 #define CONSHDLR_ENFOPRIORITY 10000000 /**< priority of the constraint handler for constraint enforcing */
49 #define CONSHDLR_CHECKPRIORITY 10000000 /**< priority of the constraint handler for checking feasibility */
50 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
52 #define CONSHDLR_NEEDSCONS FALSE /**< should the constraint handler be skipped, if no constraints are available? */
55 #define DEFAULT_CONSBENDERSLP_MAXDEPTH 0/**< depth at which Benders' decomposition cuts are generated from the LP
57 #define DEFAULT_CONSBENDERSLP_FREQ 0/**< the depth frequency for generating LP cuts after the max depth is reached (0: never, 1: all nodes, ...) */
58 #define DEFAULT_CONSBENDERSLP_STALLLIMIT 100/**< the number of nodes processed without a dual bound improvement before enforcing the LP relaxation, 0: no stall count applied */
59 #define DEFAULT_CONSBENDERSLP_ITERLIMIT 100 /**< after the root node, only iterlimit fractional LP solutions are used at each node to generate Benders' decomposition cuts. */
78 int iterlimit; /**< the iteration limit for the first phase of the two-phase method at a node lower than the root. */
80 int stalllimit; /**< the number of nodes processed without bound improvement before enforcing the LP relaxation */
107 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
137 /* updating the stall count. If the bound has improved since the last call, then the stall count is set to zero */
152 /* the result is initially set to FEASIBLE. If the two-phase method is not executed, then the result will remain as
153 * FEASIBLE. The actual feasibility of the Benders' decomposition subproblems is checked in cons_benders.
157 /* only check the Benders' decomposition subproblems for fractional LP solutions if the two-phase method is activated */
181 SCIP_CALL( SCIPconsBendersEnforceSolution(scip, NULL, conshdlr, result, SCIP_BENDERSENFOTYPE_LP, FALSE) );
183 /* if the stalllimit is exceeded and the subproblem were checked, then the stall count is reset to zero */
201 if( !conshdlrdata->active || (conshdlrdata->maxdepth >= 0 && SCIPgetDepth(scip) > conshdlrdata->maxdepth) )
204 SCIP_CALL( SCIPconsBendersEnforceSolution(scip, sol, conshdlr, result, SCIP_BENDERSENFOTYPE_RELAX, FALSE) );
220 if( !conshdlrdata->active || (conshdlrdata->maxdepth >= 0 && SCIPgetDepth(scip) > conshdlrdata->maxdepth) )
223 SCIP_CALL( SCIPconsBendersEnforceSolution(scip, NULL, conshdlr, result, SCIP_BENDERSENFOTYPE_PSEUDO, FALSE) );
230 * The feasibility check for Benders' decomposition is performed in cons_benders. As such, it is redundant to perform
231 * the feasibility check here. As such, the solution is flagged as feasible, which will then be corrected in
256 /** creates the handler for executing the Benders' decomposition subproblem solve on fractional LP solution and
260 )
287 "depth at which Benders' decomposition cuts are generated from the LP solution (-1: always, 0: only at root)",
288 &conshdlrdata->maxdepth, TRUE, DEFAULT_CONSBENDERSLP_MAXDEPTH, -1, SCIP_MAXTREEDEPTH, NULL, NULL) );
292 "the depth frequency for generating LP cuts after the max depth is reached (0: never, 1: all nodes, ...)",
297 "the number of nodes processed without a dual bound improvement before enforcing the LP relaxation, 0: no stall count applied",
302 "after the root node, only iterlimit fractional LP solutions are used at each node to generate Benders' decomposition cuts.",
306 "constraints/" CONSHDLR_NAME "/active", "is the Benders' decomposition LP cut constraint handler active?",
constraint handler for Benders' decomposition
Definition: struct_scip.h:59
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:308
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 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
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBenderslp)
Definition: cons_benderslp.c:97
Definition: struct_tree.h:132
Definition: type_benders.h:37
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:357
Definition: type_benders.h:39
Definition: struct_cons.h:117
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
SCIP_RETCODE SCIPincludeConshdlrBenderslp(SCIP *scip)
Definition: cons_benderslp.c:260
static SCIP_DECL_CONSENFORELAX(consEnforelaxBenderslp)
Definition: cons_benderslp.c:195
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:332
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4187
Definition: type_benders.h:38
static SCIP_DECL_CONSENFOPS(consEnfopsBenderslp)
Definition: cons_benderslp.c:214
#define DEFAULT_CONSBENDERSLP_STALLLIMIT
Definition: cons_benderslp.c:60
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
constraint handler for benderslp decomposition
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
static SCIP_DECL_CONSENFOLP(consEnfolpBenderslp)
Definition: cons_benderslp.c:131
Definition: objbenders.h:33
#define DEFAULT_CONSBENDERSLP_ITERLIMIT
Definition: cons_benderslp.c:61
SCIP callable library.