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()

static SCIP_RETCODE constructValidSolution	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		SCIP_SOL *	sol,
		SCIP_BENDERSENFOTYPE	type
	)

static

constructs a new solution based upon the solutions to the Benders' decomposition subproblems

Parameters

scip	the SCIP instance
conshdlr	constraint handler
sol	primal CIP solution
type	the type of solution being enforced

Definition at line 92 of file cons_benders.c.

References FALSE, NULL, SCIP_BENDERSENFOTYPE_CHECK, SCIP_BENDERSENFOTYPE_LP, SCIP_BENDERSENFOTYPE_PSEUDO, SCIP_BENDERSENFOTYPE_RELAX, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_INITPRESOLVE, SCIP_STAGE_SOLVED, SCIP_VARSTATUS_FIXED, SCIPbendersGetAuxiliaryVars(), SCIPbendersGetNSubproblems(), SCIPbendersGetSubproblemObjval(), SCIPcalcMemGrowSize(), SCIPcheckSol(), SCIPconshdlrGetData(), SCIPcreateLPSol(), SCIPcreatePseudoSol(), SCIPcreateRelaxSol(), SCIPcreateSolCopy(), SCIPdebugMsg, SCIPfindHeur(), SCIPfreeSol(), SCIPgetBenders(), SCIPgetNActiveBenders(), SCIPgetSolVal(), SCIPgetStage(), SCIPheurPassSolAddSol(), SCIPisEQ(), SCIPisLT(), SCIPreallocBlockMemoryArray, SCIPsetSolVal(), SCIPsolGetIndex(), SCIPunlinkSol(), SCIPvarGetStatus(), TRUE, and unboundedAuxiliaryVariables().

Referenced by SCIP_DECL_CONSCHECK(), and SCIPconsBendersEnforceSolution().

◆ unboundedAuxiliaryVariables()

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

static

checks the Benders' decomposition auxiliary variables for unboundedness.

Parameters

scip	the SCIP data structure
benders	the Benders' decomposition data structure
sol	the 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().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

◆ CONSHDLR_ENFOPRIORITY

◆ CONSHDLR_CHECKPRIORITY

◆ CONSHDLR_EAGERFREQ

◆ CONSHDLR_MAXPREROUNDS

◆ CONSHDLR_PRESOLTIMING

◆ CONSHDLR_NEEDSCONS

◆ DEFAULT_CHECKEDSOLSSIZE

◆ DEFAULT_ACTIVE

Function Documentation

◆ constructValidSolution()

◆ unboundedAuxiliaryVariables()

◆ SCIP_DECL_CONSHDLRCOPY()

◆ SCIP_DECL_CONSFREE()

◆ SCIP_DECL_CONSINIT()

◆ SCIP_DECL_CONSEXIT()

◆ SCIP_DECL_CONSENFOLP()

◆ SCIP_DECL_CONSENFORELAX()

◆ SCIP_DECL_CONSENFOPS()

◆ SCIP_DECL_CONSCHECK()

◆ SCIP_DECL_CONSPRESOL()

◆ SCIP_DECL_CONSLOCK()