47#define BENDERSCUT_NAME "optimality"
48#define BENDERSCUT_DESC "Standard Benders' decomposition optimality cut"
49#define BENDERSCUT_PRIORITY 5000
50#define BENDERSCUT_LPCUT TRUE
52#define SCIP_DEFAULT_ADDCUTS FALSE
53#define SCIP_DEFAULT_CALCMIR TRUE
60struct SCIP_BenderscutData
225 if( *
nvars >= *varssize )
318 SCIP_CALL(
SCIPcalcFlowCover(
masterprob,
sol,
TRUE, 0.9999,
FALSE, aggrrow,
cutcoefs,
cutrhs,
cutinds,
cutnnz,
323 SCIP_CALL(
SCIPcalcMIR(
masterprob,
sol,
TRUE, 0.9999,
TRUE,
FALSE,
FALSE,
NULL,
NULL, 0.001, 0.999, 1.0, aggrrow,
338 (*success) = !redundant;
388 for(
i = 0;
i < nrows;
i++ )
424 for(
i = 0;
i < nsubvars + nfixedvars;
i++ )
433 var = fixedvars[
i - nsubvars];
509 SCIP_Real* varlbdualvals,
510 SCIP_Real* varubdualvals,
541 SCIPerrorMessage(
"The optimality cut must generated from either a SCIP instance or all of the dual solutions and indices must be supplied");
570 for(
i = 0;
i < nrows;
i++ )
595 for(
i = 0;
i < nsubvars;
i++ )
598 for(
i = 0;
i < nfixedvars;
i++ )
641 vals[(*nvars)] = 1.0;
698 addcut = benderscutdata->addcuts;
708 SCIPdebugMsg(
scip,
"The subproblem %d is set to NULL. The <%s> Benders' decomposition cut can not be executed.\n",
727 SCIPbendersGetSubproblemObjval(benders,
probnumber),
NULL,
NULL,
NULL,
NULL,
NULL,
NULL, type,
addcut,
741 SCIPdebugMsg(
scip,
"Attempting to polish the LP solution to find an alternative dual extreme point.\n");
749 SCIPbendersGetSubproblemObjval(benders,
probnumber),
NULL,
NULL,
NULL,
NULL,
NULL,
NULL, type,
addcut,
757 SCIPdebugMsg(
scip,
"Attempting to resolve the NLP with a tighter feasibility tolerance to find an "
758 "alternative dual extreme point.\n");
767 SCIPbendersGetSubproblemObjval(benders,
probnumber),
NULL,
NULL,
NULL,
NULL,
NULL,
NULL, type,
addcut,
815 "should cuts be generated and added to the cutpool instead of global constraints directly added to the problem.",
821 "should the mixed integer rounding procedure be applied to cuts",
847 SCIP_Real* varlbdualvals,
848 SCIP_Real* varubdualvals,
881 && row2idx ==
NULL && var2idx ==
NULL)
883 && row2idx !=
NULL && var2idx !=
NULL));
918 varssize = nmastervars;
925 var2idx, &checkobj, &
success) );
931 &varssize, &checkobj, &
success) );
1002#ifdef SCIP_MOREDEBUG
1090 SCIP_Bool infeasible;
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)
#define SCIP_DEFAULT_ADDCUTS
static SCIP_RETCODE addVariableToArray(SCIP *masterprob, SCIP_VAR ***vars, SCIP_Real **vals, SCIP_VAR *addvar, SCIP_Real addval, int *nvars, int *varssize)
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 resolveNLPWithTighterFeastol(SCIP *subproblem, SCIP_Real multiplier, SCIP_Bool *success)
static SCIP_RETCODE addAuxiliaryVariableToCut(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_VAR **vars, SCIP_Real *vals, int *nvars, int probnumber)
#define SCIP_DEFAULT_CALCMIR
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_Real getNlpVarSol(SCIP_VAR *var, SCIP_Real *primalvals, SCIP_HASHMAP *var2idx)
#define BENDERSCUT_PRIORITY
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 polishSolution(SCIP *subproblem, SCIP_Bool *success)
Generates a standard Benders' decomposition optimality cut.
Constraint handler for linear constraints in their most general form, .
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)
SCIP_RETCODE SCIPincludeBenderscutOpt(SCIP *scip, SCIP_BENDERS *benders)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
SCIP_Real SCIPgetActivityLinear(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
int SCIPgetSubscipDepth(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
SCIP_Real SCIPgetTransObjoffset(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
SCIP_OBJSENSE SCIPgetObjsense(SCIP *scip)
int SCIPgetNFixedVars(SCIP *scip)
SCIP_VAR ** SCIPgetFixedVars(SCIP *scip)
SCIP_Real SCIPgetTransObjscale(SCIP *scip)
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
int SCIPhashmapEntryGetImageInt(SCIP_HASHMAPENTRY *entry)
int SCIPhashmapGetNEntries(SCIP_HASHMAP *hashmap)
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
void * SCIPhashmapEntryGetOrigin(SCIP_HASHMAPENTRY *entry)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
SCIP_VAR * SCIPbendersGetAuxiliaryVar(SCIP_BENDERS *benders, int probnumber)
SCIP_RETCODE SCIPgetBendersMasterVar(SCIP *scip, SCIP_BENDERS *benders, SCIP_VAR *var, SCIP_VAR **mappedvar)
const char * SCIPbendersGetName(SCIP_BENDERS *benders)
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
SCIP * SCIPbendersSubproblem(SCIP_BENDERS *benders, int probnumber)
SCIP_RETCODE SCIPcheckBendersSubproblemOptimality(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, int probnumber, SCIP_Bool *optimal)
SCIP_Real SCIPbendersGetSubproblemObjval(SCIP_BENDERS *benders, int probnumber)
SCIP_Bool SCIPbendersInStrengthenRound(SCIP_BENDERS *benders)
SCIP_RETCODE SCIPincludeBenderscutBasic(SCIP *scip, SCIP_BENDERS *benders, SCIP_BENDERSCUT **benderscutptr, const char *name, const char *desc, int priority, SCIP_Bool islpcut, SCIP_DECL_BENDERSCUTEXEC((*benderscutexec)), SCIP_BENDERSCUTDATA *benderscutdata)
SCIP_RETCODE SCIPsetBenderscutFree(SCIP *scip, SCIP_BENDERSCUT *benderscut,)
void SCIPbenderscutSetData(SCIP_BENDERSCUT *benderscut, SCIP_BENDERSCUTDATA *benderscutdata)
const char * SCIPbenderscutGetName(SCIP_BENDERSCUT *benderscut)
SCIP_BENDERSCUTDATA * SCIPbenderscutGetData(SCIP_BENDERSCUT *benderscut)
SCIP_RETCODE SCIPstoreBendersCut(SCIP *scip, SCIP_BENDERS *benders, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, int nvars)
SCIP_Longint SCIPbenderscutGetNFound(SCIP_BENDERSCUT *benderscut)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_RETCODE SCIPsetConsDynamic(SCIP *scip, SCIP_CONS *cons, SCIP_Bool dynamic)
SCIP_RETCODE SCIPsetConsRemovable(SCIP *scip, SCIP_CONS *cons, SCIP_Bool removable)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
SCIP_Bool SCIPcutsTightenCoefficients(SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, int *nchgcoefs)
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
SCIP_RETCODE SCIPaggrRowAddCustomCons(SCIP *scip, SCIP_AGGRROW *aggrrow, int *inds, SCIP_Real *vals, int len, SCIP_Real rhs, SCIP_Real weight, int rank, SCIP_Bool local)
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
SCIP_RETCODE SCIPcalcFlowCover(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool allowlocal, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
SCIP_RETCODE SCIPcalcMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
SCIP_RETCODE SCIPevalExprGradient(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
SCIP_Bool SCIPexpriterIsEnd(SCIP_EXPRITER *iterator)
SCIP_Real SCIPexprGetDerivative(SCIP_EXPR *expr)
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
void SCIPfreeExpriter(SCIP_EXPRITER **iterator)
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
int SCIPgetNLPRows(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
#define SCIPallocClearBufferArray(scip, ptr, num)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPreallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
int SCIPgetNNlpis(SCIP *scip)
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
SCIP_NLPSOLSTAT SCIPgetNLPSolstat(SCIP *scip)
SCIP_RETCODE SCIPsolveNLPParam(SCIP *scip, SCIP_NLPPARAM param)
int SCIPgetNNLPVars(SCIP *scip)
int SCIPgetNNLPNlRows(SCIP *scip)
SCIP_VAR ** SCIPgetNLPVars(SCIP *scip)
SCIP_Bool SCIPhasNLPSolution(SCIP *scip)
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
SCIP_NLPTERMSTAT SCIPgetNLPTermstat(SCIP *scip)
int SCIPnlrowGetNLinearVars(SCIP_NLROW *nlrow)
SCIP_VAR ** SCIPnlrowGetLinearVars(SCIP_NLROW *nlrow)
SCIP_Real SCIPnlrowGetDualsol(SCIP_NLROW *nlrow)
SCIP_EXPR * SCIPnlrowGetExpr(SCIP_NLROW *nlrow)
SCIP_Real * SCIPnlrowGetLinearCoefs(SCIP_NLROW *nlrow)
SCIP_Bool SCIPinProbing(SCIP *scip)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
SCIP_RETCODE SCIPcreateEmptyRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
SCIP_RETCODE SCIPcreateNLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPvarGetSol(SCIP_VAR *var, SCIP_Bool getlpval)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
int SCIPvarGetProbindex(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
SCIP_Real SCIPvarGetNLPSol(SCIP_VAR *var)
SCIP_Real SCIPvarGetUnchangedObj(SCIP_VAR *var)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
assert(minobj< SCIPgetCutoffbound(scip))
static const char * paramname[]
public methods for Benders' decomposition
public methods for Benders' decomposition cuts
public functions to work with algebraic expressions
public methods for LP management
public methods for message output
#define SCIPdebugPrintCons(x, y, z)
public data structures and miscellaneous methods
internal miscellaneous methods for linear constraints
public methods for NLP management
public methods for problem variables
@ SCIP_BENDERSENFOTYPE_RELAX
@ SCIP_BENDERSENFOTYPE_LP
@ SCIP_BENDERSENFOTYPE_CHECK
@ SCIP_BENDERSENFOTYPE_PSEUDO
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
#define SCIP_DECL_BENDERSCUTEXEC(x)
struct SCIP_BenderscutData SCIP_BENDERSCUTDATA
#define SCIP_DECL_BENDERSCUTFREE(x)
#define SCIP_NLPPARAM_DEFAULT(scip)
enum SCIP_NlpSolStat SCIP_NLPSOLSTAT
@ SCIP_NLPSOLSTAT_FEASIBLE
@ SCIP_NLPSOLSTAT_GLOBOPT
enum SCIP_NlpTermStat SCIP_NLPTERMSTAT
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE