Detailed Description
Generates a standard Benders' decomposition optimality cut.
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" |
Definition at line 47 of file benderscut_opt.c.
Referenced by SCIP_DECL_BENDERSCUTEXEC(), SCIP_DECL_BENDERSCUTFREE(), and SCIPincludeBenderscutOpt().
◆ 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 |
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 |
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 |
when solving NLP subproblems, numerical issues are addressed by tightening the feasibility tolerance
- Parameters
-
subproblem the SCIP data 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_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 |
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 206 of file benderscut_opt.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBufferArray.
Referenced by computeStandardLPOptimalityCut(), and SCIPaddNlRowGradientBenderscutOpt().
◆ getNlpVarSol()
|
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 242 of file benderscut_opt.c.
References NULL, SCIP_Real, SCIPhashmapExists(), SCIPhashmapGetImageInt(), and SCIPvarGetNLPSol().
Referenced by computeStandardNLPOptimalityCut(), and SCIPaddNlRowGradientBenderscutOpt().
◆ computeMIRForOptimalityCut()
|
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 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 |
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 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 |
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 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 |
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 622 of file benderscut_opt.c.
References NULL, SCIP_OKAY, and SCIPbendersGetAuxiliaryVar().
Referenced by SCIPgenerateAndApplyBendersOptCut().
◆ SCIP_DECL_BENDERSCUTFREE()
|
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()
|
static |
execution method of Benders' decomposition cuts
Definition at line 675 of file benderscut_opt.c.
References BENDERSCUT_NAME, FALSE, NULL, polishSolution(), resolveNLPWithTighterFeastol(), SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, 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().