Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

Generates a standard Benders' decomposition optimality cut.

Author
Stephen J. Maher

Definition in file benderscut_opt.c.

#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_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"

◆ BENDERSCUT_DESC

#define BENDERSCUT_DESC   "Standard Benders' decomposition optimality cut"

Definition at line 48 of file benderscut_opt.c.

Referenced by SCIPincludeBenderscutOpt().

◆ BENDERSCUT_PRIORITY

#define BENDERSCUT_PRIORITY   5000

Definition at line 49 of file benderscut_opt.c.

Referenced by SCIPincludeBenderscutOpt().

◆ BENDERSCUT_LPCUT

#define BENDERSCUT_LPCUT   TRUE

Definition at line 50 of file benderscut_opt.c.

Referenced by SCIPincludeBenderscutOpt().

◆ SCIP_DEFAULT_ADDCUTS

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

Definition at line 52 of file benderscut_opt.c.

Referenced by SCIPincludeBenderscutOpt().

◆ 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.

Referenced by SCIPincludeBenderscutOpt().

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
subproblemthe SCIP data structure
successTRUE 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
masterprobthe SCIP data structure
solthe master problem solution
varspointer to array of variables in the generated cut with non-zero coefficient
valspointer to array of coefficients of the variables in the generated cut
lhsthe left hand side of the cut
checkobjthe objective of the subproblem computed from the dual solution
nvarsthe number of variables in the cut
validreturns 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_Real  multiplier,
SCIP_Bool success 
)
static

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

Parameters
subproblemthe SCIP data structure
multiplierthe amount by which to decrease the tolerance
successTRUE 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_NLPPARAM_DEFAULT, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_NLPSOLSTAT_GLOBOPT, SCIP_NLPSOLSTAT_LOCOPT, SCIP_OKAY, 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
masterprobthe SCIP instance of the master problem
varspointer to the array of variables in the generated cut with non-zero coefficient
valspointer to the array of coefficients of the variables in the generated cut
addvarthe variable that will be added to the array
addvalthe value that will be added to the array
nvarsthe number of variables in the variable array
varssizethe length of the variable size

Definition at line 206 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
varthe variable for which the solution is requested
primalvalsthe primal solutions for the NLP, can be NULL
var2idxmapping from variable of the subproblem to the index in the dual arrays, can be NULL

Definition at line 242 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
masterprobthe SCIP instance of the master problem
solprimal CIP solution
varspointer to array of variables in the generated cut with non-zero coefficient
valspointer to array of coefficients of the variables in the generated cut
lhsthe left hand side of the cut
rhsthe right hand side of the cut
nvarsthe number of variables in the cut
cutcoefsthe coefficients of the MIR cut
cutindsthe variable indices of the MIR cut
cutrhsthe RHS of the MIR cut
cutnnzthe number of non-zeros in the cut
successwas the MIR cut successfully computed?

Definition at line 268 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
masterprobthe SCIP instance of the master problem
subproblemthe SCIP instance of the subproblem
bendersthe benders' decomposition structure
varspointer to array of variables in the generated cut with non-zero coefficient
valspointer to array of coefficients of the variables in the generated cut
lhsthe left hand side of the cut
rhsthe right hand side of the cut
nvarsthe number of variables in the cut
varssizethe number of variables in the array
checkobjstores the objective function computed from the dual solution
successwas the cut generation successful?

Definition at line 351 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
masterprobthe SCIP instance of the master problem
subproblemthe SCIP instance of the subproblem
bendersthe benders' decomposition structure
varspointer to array of variables in the generated cut with non-zero coefficient
valspointer to array of coefficients of the variables in the generated cut
lhsthe left hand side of the cut
rhsthe right hand side of the cut
nvarsthe number of variables in the cut
varssizethe number of variables in the array
objectivethe objective function of the subproblem
primalvalsthe primal solutions for the NLP, can be NULL
consdualvalsdual variables for the constraints, can be NULL
varlbdualvalsthe dual variables for the variable lower bounds, can be NULL
varubdualvalsthe dual variables for the variable upper bounds, can be NULL
row2idxmapping between the row in the subproblem to the index in the dual array, can be NULL
var2idxmapping from variable of the subproblem to the index in the dual arrays, can be NULL
checkobjstores the objective function computed from the dual solution
successwas the cut generation successful?

Definition at line 496 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
masterprobthe SCIP instance of the master problem
bendersthe benders' decomposition structure
varsthe variables in the generated cut with non-zero coefficient
valsthe coefficients of the variables in the generated cut
nvarsthe number of variables in the cut
probnumberthe number of the pricing problem

Definition at line 622 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 654 of file benderscut_opt.c.

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

◆ SCIP_DECL_BENDERSCUTEXEC()