Detailed Description

Generates a standard Benders' decomposition optimality cut.

Author: Stephen J. Maher

#include "scip/pub_expr.h"
#include "scip/benderscut_opt.h"
#include "scip/cons_linear.h"
#include "scip/pub_benderscut.h"
#include "scip/pub_benders.h"
#include "scip/pub_lp.h"
#include "scip/pub_nlp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_linear.h"
#include "scip/pub_var.h"
#include "scip/scip.h"
#include <string.h>

Go to the source code of this file.

Macros
#define	BENDERSCUT_NAME "optimality"

#define	BENDERSCUT_DESC "Standard Benders' decomposition optimality cut"

#define	BENDERSCUT_PRIORITY 5000

#define	BENDERSCUT_LPCUT TRUE

#define	SCIP_DEFAULT_ADDCUTS FALSE /** Should cuts be generated, instead of constraints */

#define	SCIP_DEFAULT_CALCMIR TRUE /** Should the mixed integer rounding procedure be used for the cut */

Functions
static SCIP_RETCODE	polishSolution (SCIP subproblem, SCIP_Bool success)

static SCIP_RETCODE	checkSetupTolerances (SCIP masterprob, SCIP_SOL sol, SCIP_VAR *vars, SCIP_Real vals, SCIP_Real lhs, SCIP_Real checkobj, int nvars, SCIP_Bool *valid)

static SCIP_RETCODE	resolveNLPWithTighterFeastol (SCIP subproblem, SCIP_BENDERS benders, SCIP_Real multiplier, SCIP_Bool *success)

static SCIP_RETCODE	addVariableToArray (SCIP masterprob, SCIP_VAR vars, SCIP_Real vals, SCIP_VAR addvar, SCIP_Real addval, int nvars, int *varssize)

static SCIP_Real	getNlpVarSol (SCIP_VAR var, SCIP_Real primalvals, SCIP_HASHMAP *var2idx)

static SCIP_RETCODE	computeMIRForOptimalityCut (SCIP masterprob, SCIP_SOL sol, SCIP_VAR *vars, SCIP_Real vals, SCIP_Real lhs, SCIP_Real rhs, int nvars, SCIP_Real cutcoefs, int cutinds, SCIP_Real cutrhs, int cutnnz, SCIP_Bool *success)

static SCIP_RETCODE	computeStandardLPOptimalityCut (SCIP masterprob, SCIP subproblem, SCIP_BENDERS benders, SCIP_VAR vars, SCIP_Real vals, SCIP_Real lhs, SCIP_Real rhs, int nvars, int varssize, SCIP_Real checkobj, SCIP_Bool success)

static SCIP_RETCODE	computeStandardNLPOptimalityCut (SCIP masterprob, SCIP subproblem, SCIP_BENDERS benders, SCIP_VAR vars, SCIP_Real vals, SCIP_Real lhs, SCIP_Real rhs, int nvars, int varssize, SCIP_Real objective, SCIP_Real primalvals, SCIP_Real consdualvals, SCIP_Real varlbdualvals, SCIP_Real varubdualvals, SCIP_HASHMAP row2idx, SCIP_HASHMAP var2idx, SCIP_Real checkobj, SCIP_Bool success)

static SCIP_RETCODE	addAuxiliaryVariableToCut (SCIP masterprob, SCIP_BENDERS benders, SCIP_VAR *vars, SCIP_Real vals, int *nvars, int probnumber)

static	SCIP_DECL_BENDERSCUTFREE (benderscutFreeOpt)

static	SCIP_DECL_BENDERSCUTEXEC (benderscutExecOpt)

SCIP_RETCODE	SCIPincludeBenderscutOpt (SCIP scip, SCIP_BENDERS benders)

SCIP_RETCODE	SCIPgenerateAndApplyBendersOptCut (SCIP masterprob, SCIP subproblem, SCIP_BENDERS benders, SCIP_BENDERSCUT benderscut, SCIP_SOL sol, int probnumber, char cutname, SCIP_Real objective, SCIP_Real primalvals, SCIP_Real consdualvals, SCIP_Real varlbdualvals, SCIP_Real varubdualvals, SCIP_HASHMAP row2idx, SCIP_HASHMAP var2idx, SCIP_BENDERSENFOTYPE type, SCIP_Bool addcut, SCIP_Bool feasibilitycut, SCIP_RESULT *result)

SCIP_RETCODE	SCIPaddNlRowGradientBenderscutOpt (SCIP masterprob, SCIP subproblem, SCIP_BENDERS benders, SCIP_NLROW nlrow, SCIP_Real mult, SCIP_Real primalvals, SCIP_HASHMAP var2idx, SCIP_Real dirderiv, SCIP_VAR vars, SCIP_Real vals, int nvars, int varssize)

Macro Definition Documentation

◆ BENDERSCUT_NAME

#define BENDERSCUT_NAME "optimality"

Definition at line 47 of file benderscut_opt.c.

◆ BENDERSCUT_DESC

#define BENDERSCUT_DESC "Standard Benders' decomposition optimality cut"

Definition at line 48 of file benderscut_opt.c.

◆ BENDERSCUT_PRIORITY

#define BENDERSCUT_PRIORITY 5000

Definition at line 49 of file benderscut_opt.c.

◆ BENDERSCUT_LPCUT

#define BENDERSCUT_LPCUT TRUE

Definition at line 50 of file benderscut_opt.c.

◆ SCIP_DEFAULT_ADDCUTS

#define SCIP_DEFAULT_ADDCUTS FALSE /** Should cuts be generated, instead of constraints */

Definition at line 52 of file benderscut_opt.c.

◆ SCIP_DEFAULT_CALCMIR

#define SCIP_DEFAULT_CALCMIR TRUE /** Should the mixed integer rounding procedure be used for the cut */

Definition at line 53 of file benderscut_opt.c.

Function Documentation

◆ polishSolution()

static SCIP_RETCODE polishSolution	(	SCIP *	subproblem,
		SCIP_Bool *	success
	)

static

in the case of numerical troubles, the LP is resolved with solution polishing activated

Parameters

subproblem	the SCIP data structure
success	TRUE is the resolving of the LP was successful

Definition at line 73 of file benderscut_opt.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPgetIntParam(), SCIPgetLPSolstat(), SCIPinProbing(), SCIPsetIntParam(), SCIPsolveProbingLP(), and TRUE.

Referenced by SCIP_DECL_BENDERSCUTEXEC().

◆ checkSetupTolerances()

static SCIP_RETCODE checkSetupTolerances	(	SCIP *	masterprob,
		SCIP_SOL *	sol,
		SCIP_VAR **	vars,
		SCIP_Real *	vals,
		SCIP_Real	lhs,
		SCIP_Real	checkobj,
		int	nvars,
		SCIP_Bool *	valid
	)

static

verifying the activity of the cut when master variables are within epsilon of their upper or lower bounds

When setting up the Benders' decomposition subproblem, master variables taking values that are within epsilon greater than their upper bound or less than their lower bound are set to their upper and lower bounds respectively. As such, there can be a difference between the subproblem dual solution objective and the optimality cut activity, when computed using the master problem solution directly. This check is to verify whether this difference is an actual error or due to the violation of the upper and lower bounds when setting up the Benders' decomposition subproblem.

Parameters

masterprob	the SCIP data structure
sol	the master problem solution
vars	pointer to array of variables in the generated cut with non-zero coefficient
vals	pointer to array of coefficients of the variables in the generated cut
lhs	the left hand side of the cut
checkobj	the objective of the subproblem computed from the dual solution
nvars	the number of variables in the cut
valid	returns true is the cut is valid

Definition at line 113 of file benderscut_opt.c.

References NULL, SCIP_OKAY, SCIP_Real, SCIPgetSolVal(), SCIPisFeasEQ(), SCIPisGT(), SCIPisLT(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by SCIPgenerateAndApplyBendersOptCut().

◆ resolveNLPWithTighterFeastol()

static SCIP_RETCODE resolveNLPWithTighterFeastol	(	SCIP *	subproblem,
		SCIP_BENDERS *	benders,
		SCIP_Real	multiplier,
		SCIP_Bool *	success
	)

static

when solving NLP subproblems, numerical issues are addressed by tightening the feasibility tolerance

Parameters

subproblem	the SCIP data structure
benders	the benders' decomposition structure
multiplier	the amount by which to decrease the tolerance
success	TRUE is the resolving of the LP was successful

Definition at line 157 of file benderscut_opt.c.

References FALSE, SCIP_NlpParam::feastol, NULL, SCIP_NlpParam::opttol, SCIP_CALL, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_NLPSOLSTAT_GLOBOPT, SCIP_NLPSOLSTAT_LOCOPT, SCIP_OKAY, SCIPbendersGetNLPParam(), SCIPcreateNLPSol(), SCIPdebugMsg, SCIPfreeSol(), SCIPgetNLPSolstat(), SCIPgetNLPTermstat(), SCIPinProbing(), SCIPprintSol(), SCIPsolveNLPParam(), and TRUE.

Referenced by SCIP_DECL_BENDERSCUTEXEC().

◆ addVariableToArray()

static SCIP_RETCODE addVariableToArray	(	SCIP *	masterprob,
		SCIP_VAR ***	vars,
		SCIP_Real **	vals,
		SCIP_VAR *	addvar,
		SCIP_Real	addval,
		int *	nvars,
		int *	varssize
	)

static

adds a variable and value to the constraint/row arrays

Parameters

masterprob	the SCIP instance of the master problem
vars	pointer to the array of variables in the generated cut with non-zero coefficient
vals	pointer to the array of coefficients of the variables in the generated cut
addvar	the variable that will be added to the array
addval	the value that will be added to the array
nvars	the number of variables in the variable array
varssize	the length of the variable size

Definition at line 207 of file benderscut_opt.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBufferArray.

Referenced by computeStandardLPOptimalityCut(), and SCIPaddNlRowGradientBenderscutOpt().

◆ getNlpVarSol()

static SCIP_Real getNlpVarSol	(	SCIP_VAR *	var,
		SCIP_Real *	primalvals,
		SCIP_HASHMAP *	var2idx
	)

static

returns the variable solution either from the NLP or from the primal vals array

Parameters

var	the variable for which the solution is requested
primalvals	the primal solutions for the NLP, can be NULL
var2idx	mapping from variable of the subproblem to the index in the dual arrays, can be NULL

Definition at line 243 of file benderscut_opt.c.

References NULL, SCIP_Real, SCIPhashmapExists(), SCIPhashmapGetImageInt(), and SCIPvarGetNLPSol().

Referenced by computeStandardNLPOptimalityCut(), and SCIPaddNlRowGradientBenderscutOpt().

◆ computeMIRForOptimalityCut()

static SCIP_RETCODE computeMIRForOptimalityCut	(	SCIP *	masterprob,
		SCIP_SOL *	sol,
		SCIP_VAR **	vars,
		SCIP_Real *	vals,
		SCIP_Real	lhs,
		SCIP_Real	rhs,
		int	nvars,
		SCIP_Real *	cutcoefs,
		int *	cutinds,
		SCIP_Real *	cutrhs,
		int *	cutnnz,
		SCIP_Bool *	success
	)

static

calculates a MIR cut from the coefficients of the standard optimality cut

Parameters

masterprob	the SCIP instance of the master problem
sol	primal CIP solution
vars	pointer to array of variables in the generated cut with non-zero coefficient
vals	pointer to array of coefficients of the variables in the generated cut
lhs	the left hand side of the cut
rhs	the right hand side of the cut
nvars	the number of variables in the cut
cutcoefs	the coefficients of the MIR cut
cutinds	the variable indices of the MIR cut
cutrhs	the RHS of the MIR cut
cutnnz	the number of non-zeros in the cut
success	was the MIR cut successfully computed?

Definition at line 269 of file benderscut_opt.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaggrRowAddCustomCons(), SCIPaggrRowCreate(), SCIPaggrRowFree(), SCIPallocBufferArray, SCIPcalcFlowCover(), SCIPcalcMIR(), SCIPcutsTightenCoefficients(), SCIPfreeBufferArray, SCIPisEfficacious(), SCIPisInfinity(), SCIPvarGetProbindex(), and TRUE.

Referenced by SCIPgenerateAndApplyBendersOptCut().

◆ computeStandardLPOptimalityCut()

static SCIP_RETCODE computeStandardLPOptimalityCut	(	SCIP *	masterprob,
		SCIP *	subproblem,
		SCIP_BENDERS *	benders,
		SCIP_VAR ***	vars,
		SCIP_Real **	vals,
		SCIP_Real *	lhs,
		SCIP_Real *	rhs,
		int *	nvars,
		int *	varssize,
		SCIP_Real *	checkobj,
		SCIP_Bool *	success
	)

static

computes a standard Benders' optimality cut from the dual solutions of the LP

Parameters

masterprob	the SCIP instance of the master problem
subproblem	the SCIP instance of the subproblem
benders	the benders' decomposition structure
vars	pointer to array of variables in the generated cut with non-zero coefficient
vals	pointer to array of coefficients of the variables in the generated cut
lhs	the left hand side of the cut
rhs	the right hand side of the cut
nvars	the number of variables in the cut
varssize	the number of variables in the array
checkobj	stores the objective function computed from the dual solution
success	was the cut generation successful?

Definition at line 354 of file benderscut_opt.c.

References addVariableToArray(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetBendersMasterVar(), SCIPgetFixedVars(), SCIPgetLPRows(), SCIPgetNFixedVars(), SCIPgetNLPRows(), SCIPgetNVars(), SCIPgetVarRedcost(), SCIPgetVars(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIProwGetDualsol(), SCIProwGetLhs(), SCIProwGetRhs(), SCIPvarGetLbLocal(), SCIPvarGetObj(), SCIPvarGetSol(), SCIPvarGetUbLocal(), SCIPvarGetUnchangedObj(), and TRUE.

Referenced by SCIPgenerateAndApplyBendersOptCut().

◆ computeStandardNLPOptimalityCut()

static SCIP_RETCODE computeStandardNLPOptimalityCut	(	SCIP *	masterprob,
		SCIP *	subproblem,
		SCIP_BENDERS *	benders,
		SCIP_VAR ***	vars,
		SCIP_Real **	vals,
		SCIP_Real *	lhs,
		SCIP_Real *	rhs,
		int *	nvars,
		int *	varssize,
		SCIP_Real	objective,
		SCIP_Real *	primalvals,
		SCIP_Real *	consdualvals,
		SCIP_Real *	varlbdualvals,
		SCIP_Real *	varubdualvals,
		SCIP_HASHMAP *	row2idx,
		SCIP_HASHMAP *	var2idx,
		SCIP_Real *	checkobj,
		SCIP_Bool *	success
	)

static

computes a standard Benders' optimality cut from the dual solutions of the NLP

Parameters

masterprob	the SCIP instance of the master problem
subproblem	the SCIP instance of the subproblem
benders	the benders' decomposition structure
vars	pointer to array of variables in the generated cut with non-zero coefficient
vals	pointer to array of coefficients of the variables in the generated cut
lhs	the left hand side of the cut
rhs	the right hand side of the cut
nvars	the number of variables in the cut
varssize	the number of variables in the array
objective	the objective function of the subproblem
primalvals	the primal solutions for the NLP, can be NULL
consdualvals	dual variables for the constraints, can be NULL
varlbdualvals	the dual variables for the variable lower bounds, can be NULL
varubdualvals	the dual variables for the variable upper bounds, can be NULL
row2idx	mapping between the row in the subproblem to the index in the dual array, can be NULL
var2idx	mapping from variable of the subproblem to the index in the dual arrays, can be NULL
checkobj	stores the objective function computed from the dual solution
success	was the cut generation successful?

Definition at line 499 of file benderscut_opt.c.

References FALSE, getNlpVarSol(), NULL, REALABS, SCIP_CALL, SCIP_ERROR, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_OBJSENSE_MINIMIZE, SCIP_OKAY, SCIP_Real, SCIPaddNlRowGradientBenderscutOpt(), SCIPdebugMsg, SCIPerrorMessage, SCIPgetFixedVars(), SCIPgetNFixedVars(), SCIPgetNLPNlRows(), SCIPgetNLPSolstat(), SCIPgetNLPVars(), SCIPgetNNLPNlRows(), SCIPgetNNLPVars(), SCIPgetObjsense(), SCIPgetTransObjoffset(), SCIPgetTransObjscale(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPhasNLPSolution(), SCIPinfinity(), SCIPisInfinity(), SCIPisNLPConstructed(), SCIPisZero(), SCIPnlrowGetDualsol(), SCIPvarGetObj(), SCIPvarGetUnchangedObj(), and TRUE.

Referenced by SCIPgenerateAndApplyBendersOptCut().

◆ addAuxiliaryVariableToCut()

static SCIP_RETCODE addAuxiliaryVariableToCut	(	SCIP *	masterprob,
		SCIP_BENDERS *	benders,
		SCIP_VAR **	vars,
		SCIP_Real *	vals,
		int *	nvars,
		int	probnumber
	)

static

Adds the auxiliary variable to the generated cut. If this is the first optimality cut for the subproblem, then the auxiliary variable is first created and added to the master problem.

Parameters

masterprob	the SCIP instance of the master problem
benders	the benders' decomposition structure
vars	the variables in the generated cut with non-zero coefficient
vals	the coefficients of the variables in the generated cut
nvars	the number of variables in the cut
probnumber	the number of the pricing problem

Definition at line 625 of file benderscut_opt.c.

References NULL, SCIP_OKAY, and SCIPbendersGetAuxiliaryVar().

Referenced by SCIPgenerateAndApplyBendersOptCut().

◆ SCIP_DECL_BENDERSCUTFREE()

static SCIP_DECL_BENDERSCUTFREE ( benderscutFreeOpt )

static

destructor of Benders' decomposition cuts to free user data (called when SCIP is exiting)

Definition at line 657 of file benderscut_opt.c.

References BENDERSCUT_NAME, NULL, SCIP_OKAY, SCIPbenderscutGetData(), SCIPbenderscutGetName(), SCIPbenderscutSetData(), and SCIPfreeBlockMemory.

◆ SCIP_DECL_BENDERSCUTEXEC()

static SCIP_DECL_BENDERSCUTEXEC ( benderscutExecOpt )

static

execution method of Benders' decomposition cuts

Definition at line 678 of file benderscut_opt.c.

References BENDERSCUT_NAME, FALSE, NULL, polishSolution(), resolveNLPWithTighterFeastol(), SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_LONGINT_FORMAT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_MAXSTRLEN, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_STAGE_INITSOLVE, SCIP_STAGE_SOLVING, SCIPbenderscutGetData(), SCIPbenderscutGetNFound(), SCIPbendersGetNSubproblems(), SCIPbendersGetSubproblemObjval(), SCIPbendersSubproblem(), SCIPdebugMsg, SCIPgenerateAndApplyBendersOptCut(), SCIPgetLPSolstat(), SCIPgetNLPSolstat(), SCIPgetNNlpis(), SCIPgetStage(), SCIPisNLPConstructed(), and SCIPsnprintf().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ BENDERSCUT_NAME

◆ BENDERSCUT_DESC

◆ BENDERSCUT_PRIORITY

◆ BENDERSCUT_LPCUT

◆ SCIP_DEFAULT_ADDCUTS

◆ SCIP_DEFAULT_CALCMIR

Function Documentation

◆ polishSolution()

◆ checkSetupTolerances()

◆ resolveNLPWithTighterFeastol()

◆ addVariableToArray()

◆ getNlpVarSol()

◆ computeMIRForOptimalityCut()

◆ computeStandardLPOptimalityCut()

◆ computeStandardNLPOptimalityCut()

◆ addAuxiliaryVariableToCut()

◆ SCIP_DECL_BENDERSCUTFREE()

◆ SCIP_DECL_BENDERSCUTEXEC()