cons_benderslp.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 greater than the integer constraint handler. This means
36 * that all LP solutions will be first checked for feasibility with respect to the Benders' decomposition second stage
37 * constraints before performing an integrality check. This is part of a multi-phase approach for solving mixed integer
40 * A parameter is available to control the depth at which the non-integer LP solution are enforced by solving the
41 * Benders' decomposition subproblems. This parameter is set to 0 by default, indicating that non-integer LP solutions
45/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
57#define CONSHDLR_ENFOPRIORITY 10000000 /**< priority of the constraint handler for constraint enforcing */
58#define CONSHDLR_CHECKPRIORITY 10000000 /**< priority of the constraint handler for checking feasibility */
59#define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
61#define CONSHDLR_NEEDSCONS FALSE /**< should the constraint handler be skipped, if no constraints are available? */
64#define DEFAULT_CONSBENDERSLP_MAXDEPTH 0/**< depth at which Benders' decomposition cuts are generated from the LP
66#define DEFAULT_CONSBENDERSLP_FREQ 0/**< the depth frequency for generating LP cuts after the max depth is reached (0: never, 1: all nodes, ...) */
67#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 */
68#define DEFAULT_CONSBENDERSLP_ITERLIMIT 100 /**< after the root node, only iterlimit fractional LP solutions are used at each node to generate Benders' decomposition cuts. */
87 int iterlimit; /**< the iteration limit for the first phase of the two-phase method at a node lower than the root. */
89 int stalllimit; /**< the number of nodes processed without bound improvement before enforcing the LP relaxation */
116/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
146 /* updating the stall count. If the bound has improved since the last call, then the stall count is set to zero */
161 /* the result is initially set to FEASIBLE. If the two-phase method is not executed, then the result will remain as
162 * FEASIBLE. The actual feasibility of the Benders' decomposition subproblems is checked in cons_benders.
166 /* only check the Benders' decomposition subproblems for fractional LP solutions if the two-phase method is activated */
190 SCIP_CALL( SCIPconsBendersEnforceSolution(scip, NULL, conshdlr, result, SCIP_BENDERSENFOTYPE_LP, FALSE) );
192 /* if the stalllimit is exceeded and the subproblem were checked, then the stall count is reset to zero */
210 if( !conshdlrdata->active || (conshdlrdata->maxdepth >= 0 && SCIPgetDepth(scip) > conshdlrdata->maxdepth) )
213 SCIP_CALL( SCIPconsBendersEnforceSolution(scip, sol, conshdlr, result, SCIP_BENDERSENFOTYPE_RELAX, FALSE) );
229 if( !conshdlrdata->active || (conshdlrdata->maxdepth >= 0 && SCIPgetDepth(scip) > conshdlrdata->maxdepth) )
232 SCIP_CALL( SCIPconsBendersEnforceSolution(scip, NULL, conshdlr, result, SCIP_BENDERSENFOTYPE_PSEUDO, FALSE) );
239 * The feasibility check for Benders' decomposition is performed in cons_benders. As such, it is redundant to perform
240 * the feasibility check here. As such, the solution is flagged as feasible, which will then be corrected in
265/** creates the handler for executing the Benders' decomposition subproblem solve on fractional LP solution and
296 "depth at which Benders' decomposition cuts are generated from the LP solution (-1: always, 0: only at root)",
297 &conshdlrdata->maxdepth, TRUE, DEFAULT_CONSBENDERSLP_MAXDEPTH, -1, SCIP_MAXTREEDEPTH, NULL, NULL) );
301 "the depth frequency for generating LP cuts after the max depth is reached (0: never, 1: all nodes, ...)",
306 "the number of nodes processed without a dual bound improvement before enforcing the LP relaxation, 0: no stall count applied",
311 "after the root node, only iterlimit fractional LP solutions are used at each node to generate Benders' decomposition cuts.",
315 "constraints/" CONSHDLR_NAME "/active", "is the Benders' decomposition LP cut constraint handler active?",
constraint handler for Benders' decomposition
static SCIP_DECL_CONSENFOPS(consEnfopsBenderslp)
Definition: cons_benderslp.c:221
static SCIP_DECL_CONSENFOLP(consEnfolpBenderslp)
Definition: cons_benderslp.c:138
#define DEFAULT_CONSBENDERSLP_ITERLIMIT
Definition: cons_benderslp.c:68
#define DEFAULT_CONSBENDERSLP_STALLLIMIT
Definition: cons_benderslp.c:67
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBenderslp)
Definition: cons_benderslp.c:104
static SCIP_DECL_CONSENFORELAX(consEnforelaxBenderslp)
Definition: cons_benderslp.c:202
constraint handler for benderslp 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 SCIPincludeConshdlrBenderslp(SCIP *scip)
Definition: cons_benderslp.c:267
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:83
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_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 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
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:458
Definition: objbenders.h:44
SCIP callable library.
Definition: struct_cons.h:127
Definition: struct_tree.h:142
Definition: struct_scip.h:70