methods and files provided by the default Benders' decomposition cut method of SCIP
A detailed description what a Benders' decomposition cut method does and how to add a Benders' decomposition cut method to SCIP can be found here.
Topics | |
Inclusion methods | |
methods to include specific Benders' decomposition cut methods into SCIP |
Functions | |
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) |
Files | |
file | benderscut_feas.h |
Standard feasibility cuts for Benders' decomposition. | |
file | benderscut_feasalt.h |
Alternative feasibility cuts for Benders' decomposition. | |
file | benderscut_int.h |
Generates a Laporte and Louveaux Benders' decomposition integer cut. | |
file | benderscut_nogood.h |
Generates a no-good cut for solutions that are integer infeasible. | |
file | benderscut_opt.h |
Generates a standard Benders' decomposition optimality cut. |
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 ) |
Generates a classical Benders' optimality cut using the dual solutions from the subproblem or the input arrays. If the dual solutions are input as arrays, then a mapping between the array indices and the rows/variables is required. This method can also be used to generate a feasiblity, is a problem to minimise the infeasibilities has been solved to generate the dual solutions
Generates a classical Benders' optimality cut using the dual solutions from the subproblem or the input arrays. If the dual solutions are input as arrays, then a mapping between the array indices and the rows/variables is required. As a cut strengthening approach, when an optimality cut is being generated (i.e. not for feasibility cuts) a MIR procedure is performed on the row. This procedure attempts to find a stronger constraint, if this doesn't happen, then the original constraint is added to SCIP.
This method can also be used to generate a feasibility cut, if a problem to minimise the infeasibilities has been solved to generate the dual solutions
masterprob | the SCIP instance of the master problem |
subproblem | the SCIP instance of the pricing problem |
benders | the benders' decomposition |
benderscut | the benders' decomposition cut method |
sol | primal CIP solution |
probnumber | the number of the pricing problem |
cutname | the name for the cut to be generated |
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 |
type | the enforcement type calling this function |
addcut | should the Benders' cut be added as a cut or constraint |
feasibilitycut | is this called for the generation of a feasibility cut |
result | the result from solving the subproblems |
Definition at line 837 of file benderscut_opt.c.
References addAuxiliaryVariableToCut(), assert(), checkSetupTolerances(), computeMIRForOptimalityCut(), computeStandardLPOptimalityCut(), computeStandardNLPOptimalityCut(), FALSE, i, NULL, nvars, result, SCIP_BENDERSENFOTYPE_CHECK, SCIP_BENDERSENFOTYPE_LP, SCIP_BENDERSENFOTYPE_PSEUDO, SCIP_BENDERSENFOTYPE_RELAX, SCIP_Bool, SCIP_CALL, SCIP_CONSADDED, SCIP_DIDNOTFIND, SCIP_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIP_STAGE_INITSOLVE, SCIPABORT, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarsToRow(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPbenderscutGetData(), SCIPbendersInStrengthenRound(), SCIPcheckBendersSubproblemOptimality(), SCIPcreateConsBasicLinear(), SCIPcreateEmptyRowConshdlr(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPfeastol(), SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetActivityLinear(), SCIPgetLhsLinear(), SCIPgetNFixedVars(), SCIPgetNNlpis(), SCIPgetNVars(), SCIPgetRowSolActivity(), SCIPgetSolVal(), SCIPgetStage(), SCIPgetSubscipDepth(), SCIPgetVars(), SCIPinfinity(), SCIPisFeasEQ(), SCIPisNLPConstructed(), SCIPreleaseCons(), SCIPreleaseRow(), SCIProwGetLhs(), SCIPsetConsDynamic(), SCIPsetConsRemovable(), SCIPstoreBendersCut(), SCIPvarGetName(), sol, TRUE, valid, and vars.
Referenced by generateAndApplyBendersCuts(), and SCIP_DECL_BENDERSCUTEXEC().
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 ) |
adds the gradient of a nonlinear row in the current NLP solution of a subproblem to a linear row or constraint in the master problem
Only computes gradient w.r.t. master problem variables. Computes also the directional derivative, that is, mult times gradient times solution.
masterprob | the SCIP instance of the master problem |
subproblem | the SCIP instance of the subproblem |
benders | the benders' decomposition structure |
nlrow | nonlinear row |
mult | multiplier |
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 |
dirderiv | storage to add directional derivative |
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 |
nvars | the number of variables in the cut |
varssize | the number of variables in the array |
Definition at line 1167 of file benderscut_opt.c.
References addVariableToArray(), assert(), FALSE, getNlpVarSol(), i, NULL, nvars, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPcreateExpriter(), SCIPcreateNLPSol(), SCIPcreateSol(), SCIPevalExprGradient(), SCIPexprGetDerivative(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPfreeExpriter(), SCIPfreeSol(), SCIPgetBendersMasterVar(), SCIPgetVarExprVar(), SCIPhashmapEntryGetImageInt(), SCIPhashmapEntryGetOrigin(), SCIPhashmapGetEntry(), SCIPhashmapGetNEntries(), SCIPisExprVar(), SCIPnlrowGetExpr(), SCIPnlrowGetLinearCoefs(), SCIPnlrowGetLinearVars(), SCIPnlrowGetNLinearVars(), SCIPsetSolVal(), var, and vars.
Referenced by computeStandardNLPFeasibilityCut(), and computeStandardNLPOptimalityCut().