SCIP Doxygen Documentation
Loading...
Searching...
No Matches
Benders' decomposition cut method

Detailed Description

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.

Function Documentation

◆ SCIPgenerateAndApplyBendersOptCut()

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

Parameters
masterprobthe SCIP instance of the master problem
subproblemthe SCIP instance of the pricing problem
bendersthe benders' decomposition
benderscutthe benders' decomposition cut method
solprimal CIP solution
probnumberthe number of the pricing problem
cutnamethe name for the cut to be generated
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
typethe enforcement type calling this function
addcutshould the Benders' cut be added as a cut or constraint
feasibilitycutis this called for the generation of a feasibility cut
resultthe 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().

◆ SCIPaddNlRowGradientBenderscutOpt()

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.

Parameters
masterprobthe SCIP instance of the master problem
subproblemthe SCIP instance of the subproblem
bendersthe benders' decomposition structure
nlrownonlinear row
multmultiplier
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
dirderivstorage to add directional derivative
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
nvarsthe number of variables in the cut
varssizethe 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().