Detailed Description
constraint handler for benderslp decomposition
Two constraint handlers are implemented for the generation of Benders' decomposition cuts. When included in a problem, the Benders' decomposition constraint handlers generate cuts during the enforcement of LP and relaxation solutions. Additionally, Benders' decomposition cuts can be generated when checking the feasibility of solutions with respect to the subproblem constraints.
This constraint handler has an enforcement priority that is greater than the integer constraint handler. This means that all LP solutions will be first checked for feasibility with respect to the Benders' decomposition second stage constraints before performing an integrality check. This is part of a multi-phase approach for solving mixed integer programs by Benders' decomposition.
A parameter is available to control the depth at which the non-integer LP solution are enforced by solving the Benders' decomposition subproblems. This parameter is set to 0 by default, indicating that non-integer LP solutions are enforced only at the root node.
Definition in file cons_benderslp.c.
#include <assert.h>
#include "scip/scip.h"
#include "scip/cons_benderslp.h"
#include "scip/cons_benders.h"
Go to the source code of this file.
Macros | |
#define | CONSHDLR_NAME "benderslp" |
#define | CONSHDLR_DESC "constraint handler for Benders' Decomposition to separate LP solutions" |
#define | CONSHDLR_ENFOPRIORITY 10000000 |
#define | CONSHDLR_CHECKPRIORITY 10000000 |
#define | CONSHDLR_EAGERFREQ 100 |
#define | CONSHDLR_NEEDSCONS FALSE |
#define | DEFAULT_CONSBENDERSLP_MAXDEPTH 0 |
#define | DEFAULT_CONSBENDERSLP_FREQ 0 |
#define | DEFAULT_CONSBENDERSLP_STALLLIMIT 100 |
#define | DEFAULT_CONSBENDERSLP_ITERLIMIT 100 |
#define | DEFAULT_ACTIVE FALSE |
Functions | |
static | SCIP_DECL_CONSHDLRCOPY (conshdlrCopyBenderslp) |
static | SCIP_DECL_CONSFREE (consFreeBenderslp) |
static | SCIP_DECL_CONSENFOLP (consEnfolpBenderslp) |
static | SCIP_DECL_CONSENFORELAX (consEnforelaxBenderslp) |
static | SCIP_DECL_CONSENFOPS (consEnfopsBenderslp) |
static | SCIP_DECL_CONSCHECK (consCheckBenderslp) |
static | SCIP_DECL_CONSLOCK (consLockBenderslp) |
SCIP_RETCODE | SCIPincludeConshdlrBenderslp (SCIP *scip) |
Macro Definition Documentation
◆ CONSHDLR_NAME
#define CONSHDLR_NAME "benderslp" |
Definition at line 55 of file cons_benderslp.c.
Referenced by SCIPincludeConshdlrBenderslp().
◆ CONSHDLR_DESC
#define CONSHDLR_DESC "constraint handler for Benders' Decomposition to separate LP solutions" |
Definition at line 56 of file cons_benderslp.c.
Referenced by SCIPincludeConshdlrBenderslp().
◆ CONSHDLR_ENFOPRIORITY
#define CONSHDLR_ENFOPRIORITY 10000000 |
priority of the constraint handler for constraint enforcing
Definition at line 57 of file cons_benderslp.c.
Referenced by SCIPincludeConshdlrBenderslp().
◆ CONSHDLR_CHECKPRIORITY
#define CONSHDLR_CHECKPRIORITY 10000000 |
priority of the constraint handler for checking feasibility
Definition at line 58 of file cons_benderslp.c.
Referenced by SCIPincludeConshdlrBenderslp().
◆ CONSHDLR_EAGERFREQ
#define CONSHDLR_EAGERFREQ 100 |
frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only
Definition at line 59 of file cons_benderslp.c.
Referenced by SCIPincludeConshdlrBenderslp().
◆ CONSHDLR_NEEDSCONS
#define CONSHDLR_NEEDSCONS FALSE |
should the constraint handler be skipped, if no constraints are available?
Definition at line 62 of file cons_benderslp.c.
Referenced by SCIPincludeConshdlrBenderslp().
◆ DEFAULT_CONSBENDERSLP_MAXDEPTH
#define DEFAULT_CONSBENDERSLP_MAXDEPTH 0 |
depth at which Benders' decomposition cuts are generated from the LP solution (-1: always, 0: only at root)
Definition at line 65 of file cons_benderslp.c.
Referenced by SCIPincludeConshdlrBenderslp().
◆ DEFAULT_CONSBENDERSLP_FREQ
#define DEFAULT_CONSBENDERSLP_FREQ 0 |
the depth frequency for generating LP cuts after the max depth is reached (0: never, 1: all nodes, ...)
Definition at line 68 of file cons_benderslp.c.
Referenced by SCIPincludeConshdlrBenderslp().
◆ DEFAULT_CONSBENDERSLP_STALLLIMIT
#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
Definition at line 69 of file cons_benderslp.c.
Referenced by SCIPincludeConshdlrBenderslp().
◆ DEFAULT_CONSBENDERSLP_ITERLIMIT
#define DEFAULT_CONSBENDERSLP_ITERLIMIT 100 |
after the root node, only iterlimit fractional LP solutions are used at each node to generate Benders' decomposition cuts.
Definition at line 70 of file cons_benderslp.c.
Referenced by SCIPincludeConshdlrBenderslp().
◆ DEFAULT_ACTIVE
#define DEFAULT_ACTIVE FALSE |
is the constraint handler active?
Definition at line 71 of file cons_benderslp.c.
Referenced by SCIPincludeConshdlrBenderslp().
Function Documentation
◆ SCIP_DECL_CONSHDLRCOPY()
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 106 of file cons_benderslp.c.
◆ SCIP_DECL_CONSFREE()
|
static |
destructor of constraint handler to free constraint handler data (called when SCIP is exiting)
Definition at line 120 of file cons_benderslp.c.
◆ SCIP_DECL_CONSENFOLP()
|
static |
constraint enforcing method of constraint handler for LP solutions
Definition at line 140 of file cons_benderslp.c.
◆ SCIP_DECL_CONSENFORELAX()
|
static |
constraint enforcing method of constraint handler for relaxation solutions
Definition at line 204 of file cons_benderslp.c.
◆ SCIP_DECL_CONSENFOPS()
|
static |
constraint enforcing method of constraint handler for pseudo solutions
Definition at line 223 of file cons_benderslp.c.
◆ SCIP_DECL_CONSCHECK()
|
static |
feasibility check method of constraint handler for integral solutions. The feasibility check for Benders' decomposition is performed in cons_benders. As such, it is redundant to perform the feasibility check here. As such, the solution is flagged as feasible, which will then be corrected in cons_benders if the solution is infeasible with respect to the second stage constraints
Definition at line 246 of file cons_benderslp.c.
◆ SCIP_DECL_CONSLOCK()
|
static |
variable rounding lock method of constraint handler
Definition at line 256 of file cons_benderslp.c.