Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

constraint handler for Benders' 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 less than the integer constraint handler. This means that only integer feasible solutions from the LP solver are enforced by this constraint handler. This is the traditional behaviour of the branch-and-check approach to Benders' decomposition. Additionally, the check priority is set low, such that this expensive constraint handler is only called as a final check on primal feasible solutions.

This constraint handler in the standard constraint handler that should be added when using Benders' decomposition. Additionally, there is a flag in SCIPincludeConshdlrBenders that permits the addition of the LP constraint handler, cons_benderslp. The use of both cons_benders and cons_benderslp allows the user to perform a multiphase Benders' decomposition algorithm.

Definition in file cons_benders.c.

#include <assert.h>
#include <string.h>
#include "scip/scip.h"
#include "scip/cons_benders.h"
#include "scip/heur_trysol.h"
#include "scip/heuristics.h"

Go to the source code of this file.

Macros

#define CONSHDLR_NAME   "benders"
 
#define CONSHDLR_DESC   "constraint handler to execute Benders' Decomposition"
 
#define CONSHDLR_ENFOPRIORITY   -100
 
#define CONSHDLR_CHECKPRIORITY   -5000000
 
#define CONSHDLR_EAGERFREQ   100
 
#define CONSHDLR_MAXPREROUNDS   0
 
#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_FAST
 
#define CONSHDLR_NEEDSCONS   FALSE
 
#define DEFAULT_CHECKEDSOLSSIZE   20
 
#define DEFAULT_ACTIVE   FALSE
 

Functions

static SCIP_RETCODE constructValidSolution (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_BENDERSENFOTYPE type)
 
static SCIP_Bool unboundedAuxiliaryVariables (SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol)
 
SCIP_RETCODE SCIPconsBendersEnforceSolution (SCIP *scip, SCIP_SOL *sol, SCIP_CONSHDLR *conshdlr, SCIP_RESULT *result, SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint)
 
static SCIP_DECL_CONSHDLRCOPY (conshdlrCopyBenders)
 
static SCIP_DECL_CONSFREE (consFreeBenders)
 
static SCIP_DECL_CONSINIT (consInitBenders)
 
static SCIP_DECL_CONSEXIT (consExitBenders)
 
static SCIP_DECL_CONSENFOLP (consEnfolpBenders)
 
static SCIP_DECL_CONSENFORELAX (consEnforelaxBenders)
 
static SCIP_DECL_CONSENFOPS (consEnfopsBenders)
 
static SCIP_DECL_CONSCHECK (consCheckBenders)
 
static SCIP_DECL_CONSPRESOL (consPresolBenders)
 
static SCIP_DECL_CONSLOCK (consLockBenders)
 
SCIP_RETCODE SCIPincludeConshdlrBenders (SCIP *scip)
 

Macro Definition Documentation

◆ CONSHDLR_NAME

#define CONSHDLR_NAME   "benders"

Definition at line 58 of file cons_benders.c.

Referenced by SCIPincludeConshdlrBenders().

◆ CONSHDLR_DESC

#define CONSHDLR_DESC   "constraint handler to execute Benders' Decomposition"

Definition at line 59 of file cons_benders.c.

Referenced by SCIPincludeConshdlrBenders().

◆ CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY   -100

priority of the constraint handler for constraint enforcing

Definition at line 60 of file cons_benders.c.

Referenced by SCIPincludeConshdlrBenders().

◆ CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY   -5000000

priority of the constraint handler for checking feasibility

Definition at line 61 of file cons_benders.c.

Referenced by SCIPincludeConshdlrBenders().

◆ 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 62 of file cons_benders.c.

Referenced by SCIPincludeConshdlrBenders().

◆ CONSHDLR_MAXPREROUNDS

#define CONSHDLR_MAXPREROUNDS   0

maximal number of presolving rounds the constraint handler participates in (-1: no limit)

Definition at line 65 of file cons_benders.c.

Referenced by SCIPincludeConshdlrBenders().

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_FAST

presolving timing of the constraint handler (fast, medium, or exhaustive)

Definition at line 66 of file cons_benders.c.

Referenced by SCIPincludeConshdlrBenders().

◆ CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS   FALSE

should the constraint handler be skipped, if no constraints are available?

Definition at line 67 of file cons_benders.c.

Referenced by SCIPincludeConshdlrBenders().

◆ DEFAULT_CHECKEDSOLSSIZE

#define DEFAULT_CHECKEDSOLSSIZE   20

initial size of the checked sols array

Definition at line 70 of file cons_benders.c.

Referenced by SCIP_DECL_CONSINIT().

◆ DEFAULT_ACTIVE

#define DEFAULT_ACTIVE   FALSE

is the constraint handler active?

Definition at line 71 of file cons_benders.c.

Referenced by SCIPincludeConshdlrBenders().

Function Documentation

◆ constructValidSolution()

◆ unboundedAuxiliaryVariables()

static SCIP_Bool unboundedAuxiliaryVariables ( SCIP scip,
SCIP_BENDERS benders,
SCIP_SOL sol 
)
static

checks the Benders' decomposition auxiliary variables for unboundedness.

Parameters
scipthe SCIP data structure
bendersthe Benders' decomposition data structure
solthe primal solution to enforce, or NULL for the current LP/pseudo sol

Definition at line 219 of file cons_benders.c.

References FALSE, NULL, SCIP_Bool, SCIPbendersGetNSubproblems(), SCIPconsBendersEnforceSolution(), SCIPgetBendersAuxiliaryVarVal(), SCIPisInfinity(), and TRUE.

Referenced by constructValidSolution(), and SCIPconsBendersEnforceSolution().

◆ SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyBenders  )
static

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

Definition at line 372 of file cons_benders.c.

References NULL, SCIP_CALL, SCIP_DECL_CONSFREE(), SCIP_OKAY, SCIPincludeConshdlrBenders(), and TRUE.

Referenced by SCIPconsBendersEnforceSolution().

◆ SCIP_DECL_CONSFREE()

static SCIP_DECL_CONSFREE ( consFreeBenders  )
static

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

Definition at line 385 of file cons_benders.c.

References NULL, SCIP_DECL_CONSINIT(), SCIP_OKAY, SCIPconshdlrGetData(), and SCIPfreeMemory.

Referenced by SCIP_DECL_CONSHDLRCOPY().

◆ SCIP_DECL_CONSINIT()

static SCIP_DECL_CONSINIT ( consInitBenders  )
static

initialization method of constraint handler (called after problem was transformed)

Definition at line 404 of file cons_benders.c.

References DEFAULT_CHECKEDSOLSSIZE, NULL, SCIP_CALL, SCIP_DECL_CONSEXIT(), SCIP_OKAY, SCIPallocBlockMemoryArray, and SCIPconshdlrGetData().

Referenced by SCIP_DECL_CONSFREE().

◆ SCIP_DECL_CONSEXIT()

static SCIP_DECL_CONSEXIT ( consExitBenders  )
static

deinitialization method of constraint handler (called before transformed problem is freed)

Definition at line 424 of file cons_benders.c.

References NULL, SCIP_DECL_CONSENFOLP(), SCIP_OKAY, SCIPconshdlrGetData(), and SCIPfreeBlockMemoryArray.

Referenced by SCIP_DECL_CONSINIT().

◆ SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpBenders  )
static

constraint enforcing method of constraint handler for LP solutions

Definition at line 444 of file cons_benders.c.

References NULL, SCIP_BENDERSENFOTYPE_LP, SCIP_CALL, SCIP_DECL_CONSENFORELAX(), SCIP_FEASIBLE, SCIP_OKAY, SCIPconsBendersEnforceSolution(), SCIPconshdlrGetData(), and TRUE.

Referenced by SCIP_DECL_CONSEXIT().

◆ SCIP_DECL_CONSENFORELAX()

static SCIP_DECL_CONSENFORELAX ( consEnforelaxBenders  )
static

constraint enforcing method of constraint handler for relaxation solutions

Definition at line 467 of file cons_benders.c.

References NULL, SCIP_BENDERSENFOTYPE_RELAX, SCIP_CALL, SCIP_DECL_CONSENFOPS(), SCIP_FEASIBLE, SCIP_OKAY, SCIPconsBendersEnforceSolution(), SCIPconshdlrGetData(), and TRUE.

Referenced by SCIP_DECL_CONSENFOLP().

◆ SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsBenders  )
static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 490 of file cons_benders.c.

References NULL, SCIP_BENDERSENFOTYPE_PSEUDO, SCIP_CALL, SCIP_DECL_CONSCHECK(), SCIP_FEASIBLE, SCIP_OKAY, SCIPconsBendersEnforceSolution(), SCIPconshdlrGetData(), and TRUE.

Referenced by SCIP_DECL_CONSENFORELAX().

◆ SCIP_DECL_CONSCHECK()

static SCIP_DECL_CONSCHECK ( consCheckBenders  )
static

feasibility check method of constraint handler for integral solutions

This function checks the feasibility of the Benders' decomposition master problem. In the case that the problem is feasible, then the auxiliary variables must be updated with the subproblem objective function values. It is not possible to simply update the auxiliary variable values, so a new solution is created.

Definition at line 518 of file cons_benders.c.

References constructValidSolution(), FALSE, NULL, SCIP_BENDERSENFOTYPE_CHECK, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSPRESOL(), SCIP_DIDNOTRUN, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconshdlrGetData(), SCIPgetBenders(), SCIPgetMessagehdlr(), SCIPgetNActiveBenders(), SCIPmessagePrintInfo(), SCIPsolGetIndex(), SCIPsolIsOriginal(), SCIPsolveBendersSubproblems(), and TRUE.

Referenced by SCIP_DECL_CONSENFOPS().

◆ SCIP_DECL_CONSPRESOL()

static SCIP_DECL_CONSPRESOL ( consPresolBenders  )
static

the presolving method for the Benders' decomposition constraint handler

This method is used to update the lower bounds of the auxiliary problem and to identify infeasibility before the subproblems are solved. When SCIP is copied, the Benders' decomposition subproblems from the source SCIP are transferred to the target SCIP. So there is no need to perform this presolving step in the copied SCIP, since the computed bounds would be identical.

Definition at line 613 of file cons_benders.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSLOCK(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPbendersGetAuxiliaryVar(), SCIPbendersGetNSubproblems(), SCIPbendersUpdateSubproblemLowerbound(), SCIPchgVarLb(), SCIPcomputeBendersSubproblemLowerbound(), SCIPconshdlrGetData(), SCIPdebugMsg, SCIPgetBenders(), SCIPgetNActiveBenders(), SCIPgetSubscipDepth(), SCIPisGT(), SCIPvarGetLbLocal(), and SCIPvarGetName().

Referenced by SCIP_DECL_CONSCHECK().

◆ SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockBenders  )
static

variable rounding lock method of constraint handler The auxiliary variables and the master problem variables need to lock added by the Benders' decomposition constraint. The auxiliary variables require a down lock. The master problem variable need both up and down lock. The master problem variables require locks in both directions because the coefficients in all potential Benders' cuts are not known in general.

Definition at line 700 of file cons_benders.c.

References NULL, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPaddVarLocksType(), SCIPbendersGetAuxiliaryVar(), SCIPbendersGetNSubproblems(), SCIPconshdlrGetData(), SCIPgetBenders(), SCIPgetNActiveBenders(), SCIPgetOrigVarsData(), and SCIPincludeConshdlrBenders().

Referenced by SCIP_DECL_CONSPRESOL().