Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

constraint handler for benderslp decomposition

Author
Stephen J. Maher

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 46 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 47 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 48 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 49 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 50 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 53 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 56 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 59 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 60 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 61 of file cons_benderslp.c.

Referenced by SCIPincludeConshdlrBenderslp().

◆ DEFAULT_ACTIVE

#define DEFAULT_ACTIVE   FALSE

is the constraint handler active?

Definition at line 62 of file cons_benderslp.c.

Referenced by SCIPincludeConshdlrBenderslp().

Function Documentation

◆ SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyBenderslp  )
static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 97 of file cons_benderslp.c.

◆ SCIP_DECL_CONSFREE()

static SCIP_DECL_CONSFREE ( consFreeBenderslp  )
static

destructor of constraint handler to free constraint handler data (called when SCIP is exiting)

Definition at line 111 of file cons_benderslp.c.

◆ SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpBenderslp  )
static

constraint enforcing method of constraint handler for LP solutions

Definition at line 131 of file cons_benderslp.c.

◆ SCIP_DECL_CONSENFORELAX()

static SCIP_DECL_CONSENFORELAX ( consEnforelaxBenderslp  )
static

constraint enforcing method of constraint handler for relaxation solutions

Definition at line 195 of file cons_benderslp.c.

◆ SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsBenderslp  )
static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 214 of file cons_benderslp.c.

◆ SCIP_DECL_CONSCHECK()

static SCIP_DECL_CONSCHECK ( consCheckBenderslp  )
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 237 of file cons_benderslp.c.

◆ SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockBenderslp  )
static

variable rounding lock method of constraint handler

Definition at line 247 of file cons_benderslp.c.