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 */ |
#define BENDERSCUT_NAME "optimality" |
Definition at line 47 of file benderscut_opt.c.
#define BENDERSCUT_DESC "Standard Benders' decomposition optimality cut" |
Definition at line 48 of file benderscut_opt.c.
#define BENDERSCUT_PRIORITY 5000 |
Definition at line 49 of file benderscut_opt.c.
#define BENDERSCUT_LPCUT TRUE |
Definition at line 50 of file benderscut_opt.c.
#define SCIP_DEFAULT_ADDCUTS FALSE /** Should cuts be generated, instead of constraints */ |
Definition at line 52 of file benderscut_opt.c.
#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().
|
static |
in the case of numerical troubles, the LP is resolved with solution polishing activated
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 assert(), cutoff, FALSE, lperror, NULL, SCIP_Bool, SCIP_CALL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPgetIntParam(), SCIPgetLPSolstat(), SCIPinProbing(), SCIPsetIntParam(), SCIPsolveProbingLP(), and TRUE.
Referenced by SCIP_DECL_BENDERSCUTEXEC().
|
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.
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 assert(), i, NULL, nvars, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPgetSolVal(), SCIPisFeasEQ(), SCIPisGT(), SCIPisLT(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), sol, valid, and vars.
Referenced by SCIPgenerateAndApplyBendersOptCut().
|
static |
when solving NLP subproblems, numerical issues are addressed by tightening the feasibility tolerance
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 assert(), FALSE, SCIP_NlpParam::feastol, NULL, SCIP_NlpParam::opttol, SCIP_Bool, SCIP_CALL, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_NLPSOLSTAT_GLOBOPT, SCIP_NLPSOLSTAT_LOCOPT, SCIP_OKAY, SCIP_Real, SCIPbendersGetNLPParam(), SCIPcreateNLPSol(), SCIPdebugMsg, SCIPfreeSol(), SCIPgetNLPSolstat(), SCIPgetNLPTermstat(), SCIPinProbing(), SCIPprintSol(), SCIPsolveNLPParam(), and TRUE.
Referenced by SCIP_DECL_BENDERSCUTEXEC().
|
static |
adds a variable and value to the constraint/row arrays
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 assert(), NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcalcMemGrowSize(), SCIPreallocBufferArray, and vars.
Referenced by computeStandardLPOptimalityCut(), and SCIPaddNlRowGradientBenderscutOpt().
|
static |
returns the variable solution either from the NLP or from the primal vals array
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 assert(), NULL, SCIP_Real, SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPvarGetNLPSol(), and var.
Referenced by computeStandardNLPOptimalityCut(), and SCIPaddNlRowGradientBenderscutOpt().
|
static |
calculates a MIR cut from the coefficients of the standard optimality cut
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 assert(), FALSE, i, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaggrRowAddCustomCons(), SCIPaggrRowCreate(), SCIPaggrRowFree(), SCIPallocBufferArray, SCIPcalcFlowCover(), SCIPcalcMIR(), SCIPcutsTightenCoefficients(), SCIPfreeBufferArray, SCIPisEfficacious(), SCIPisInfinity(), SCIPvarGetProbindex(), sol, TRUE, and vars.
Referenced by SCIPgenerateAndApplyBendersOptCut().
|
static |
computes a standard Benders' optimality cut from the dual solutions of the LP
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 352 of file benderscut_opt.c.
References addVariableToArray(), assert(), FALSE, i, NULL, nvars, SCIP_Bool, 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(), TRUE, var, and vars.
Referenced by SCIPgenerateAndApplyBendersOptCut().
|
static |
computes a standard Benders' optimality cut from the dual solutions of the NLP
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 497 of file benderscut_opt.c.
References assert(), FALSE, getNlpVarSol(), i, NULL, nvars, REALABS, SCIP_Bool, 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(), TRUE, and vars.
Referenced by SCIPgenerateAndApplyBendersOptCut().
|
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.
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 623 of file benderscut_opt.c.
References assert(), NULL, nvars, SCIP_OKAY, SCIP_Real, SCIPbendersGetAuxiliaryVar(), and vars.
Referenced by SCIPgenerateAndApplyBendersOptCut().
|
static |
destructor of Benders' decomposition cuts to free user data (called when SCIP is exiting)
Definition at line 655 of file benderscut_opt.c.
References assert(), BENDERSCUT_NAME, NULL, SCIP_OKAY, SCIPbenderscutGetData(), SCIPbenderscutGetName(), SCIPbenderscutSetData(), and SCIPfreeBlockMemory.
|
static |
execution method of Benders' decomposition cuts
Definition at line 676 of file benderscut_opt.c.
References assert(), BENDERSCUT_NAME, FALSE, NULL, polishSolution(), resolveNLPWithTighterFeastol(), result, 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(), SCIPsnprintf(), and sol.