benderscut_int.c
Go to the documentation of this file.
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
72 SCIP_Real* subprobconstant; /**< the constant for each subproblem used for computing the integer cuts */
108 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &benderscutdata->subprobconstant, benderscutdata->nsubproblems) );
109 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &benderscutdata->firstcut, benderscutdata->nsubproblems) );
124 /** updates the cut constant for the given subproblem based upon the global bounds of the associated auxiliary variable */
141 /* checking if the subproblem lower bound has been updated. If it is has changed, then firstcut is set to TRUE.
147 benderscutdata->subprobconstant[probnumber] = SCIPbendersGetSubproblemLowerbound(benders, probnumber);
151 /* updating the cut constant if the auxiliary variable global lower bound is greater than the current constant */
152 if( SCIPisGT(masterprob, SCIPvarGetLbGlobal(auxiliaryvar), benderscutdata->subprobconstant[probnumber]) )
193 SCIPdebug( SCIPdebugMsg(masterprob, "Subproblem %d - Objective Value: Stored - %g Orig Obj - %g Cut constant - %g\n",
194 probnumber, SCIPbendersGetSubproblemObjval(benders, probnumber), SCIPgetSolOrigObj(subproblem, SCIPgetBestSol(subproblem))*(int)SCIPgetObjsense(subproblem),
212 SCIP_CALL( SCIPgetBendersSubproblemVar(masterprob, benders, vars[i], &subprobvar, probnumber) );
217 /* if the variable is on its upper bound, then the subproblem objective value is added to the cut */
279 /** adds the auxiliary variable to the generated cut. If this is the first optimality cut for the subproblem, then the
350 /* if the cuts are generated prior to the solving stage, then rows can not be generated. So constraints must be added
361 /* checking the optimality of the original problem with a comparison between the auxiliary variable and the
365 SCIP_CALL( SCIPcheckBendersSubproblemOptimality(masterprob, benders, sol, probnumber, &optimal) );
370 SCIPdebugMsg(masterprob, "No <%s> cut added. Current Master Problem Obj: %g\n", BENDERSCUT_NAME,
375 /* checking whether the subproblem constant is less than the auxiliary variable global lower bound */
378 /* if no integer cuts have been previously generated and the bound on the auxiliary variable is -infinity,
382 && SCIPisInfinity(masterprob, -SCIPvarGetLbGlobal(SCIPbendersGetAuxiliaryVar(benders, probnumber))) )
385 SCIP_CALL( generateAndApplyBendersIntegerCuts(masterprob, benders, benderscut, sol, probnumber, type, result,
390 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "integeroptcut_%d_%" SCIP_LONGINT_FORMAT, probnumber,
396 SCIP_CALL( SCIPcreateEmptyRowConshdlr(masterprob, &row, consbenders, cutname, 0.0, SCIPinfinity(masterprob), FALSE,
401 SCIP_CALL( SCIPcreateConsBasicLinear(masterprob, &cons, cutname, 0, NULL, NULL, 0.0, SCIPinfinity(masterprob)) );
442 /* if success is FALSE, then there was an error in generating the integer optimality cut. No cut will be added to
448 SCIPdebugMsg(masterprob, "Error in generating Benders' integer optimality cut for problem %d.\n", probnumber);
506 /** destructor of Benders' decomposition cuts to free user data (called when SCIP is exiting) */
527 /** initialization method of Benders' decomposition cuts (called after problem was transformed) */
546 /** deinitialization method of Benders' decomposition cuts (called before transformed problem is freed) */
580 SCIPdebugMsg(scip, "The subproblem %d is set to NULL. The <%s> Benders' decomposition cut can not be executed.\n",
587 /* it is only possible to generate the Laporte and Louveaux cuts for pure binary master problems */
592 SCIPinfoMessage(scip, NULL, "The integer optimality cuts can only be applied to problems with a "
600 /* the integer subproblem could terminate early if the auxiliary variable value is much greater than the optimal
605 SCIP_CALL( generateAndApplyBendersIntegerCuts(scip, benders, benderscut, sol, probnumber, type, result, FALSE) );
635 SCIP_CALL( SCIPincludeBenderscutBasic(scip, benders, &benderscut, BENDERSCUT_NAME, BENDERSCUT_DESC,
650 &benderscutdata->cutconstant, FALSE, SCIP_DEFAULT_CUTCONSTANT, -SCIPinfinity(scip), SCIPinfinity(scip),
656 "should cuts be generated and added to the cutpool instead of global constraints directly added to the problem.",
Generates a Laporte and Louveaux Benders' decomposition integer cut.
SCIP_RETCODE SCIPincludeBenderscutInt(SCIP *scip, SCIP_BENDERS *benders)
Definition: benderscut_int.c:617
SCIP_Real SCIPgetActivityLinear(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
Definition: cons_linear.c:18600
Definition: type_result.h:42
const char * SCIPbenderscutGetName(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:492
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)
Definition: scip_benders.c:1138
SCIP_Real SCIPbendersGetSubproblemObjval(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6179
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:782
public methods for SCIP parameter handling
static SCIP_RETCODE generateAndApplyBendersIntegerCuts(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SOL *sol, int probnumber, SCIP_BENDERSENFOTYPE type, SCIP_RESULT *result, SCIP_Bool initcons)
Definition: benderscut_int.c:317
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)
Definition: cons_linear.c:18040
Definition: struct_scip.h:68
public methods for memory management
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:886
static SCIP_DECL_BENDERSCUTFREE(benderscutFreeInt)
Definition: benderscut_int.c:508
SCIP_BENDERSCUTDATA * SCIPbenderscutGetData(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:403
Definition: struct_benderscut.h:46
static SCIP_DECL_PARAMCHGD(paramChgdBenderscutintConstant)
Definition: benderscut_int.c:80
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1695
Definition: struct_var.h:207
void SCIPbenderscutSetData(SCIP_BENDERSCUT *benderscut, SCIP_BENDERSCUTDATA *benderscutdata)
Definition: benderscut.c:413
Definition: type_benders.h:49
static SCIP_RETCODE createBenderscutData(SCIP *scip, SCIP_BENDERSCUTDATA *benderscutdata)
Definition: benderscut_int.c:97
public methods for Benders' decomposition
static void updateSubproblemCutConstant(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_BENDERSCUTDATA *benderscutdata, int probnumber)
Definition: benderscut_int.c:126
static SCIP_RETCODE addAuxiliaryVariableToCut(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_CONS *cons, SCIP_ROW *row, int probnumber, SCIP_Bool addcut)
Definition: benderscut_int.c:283
public methods for problem variables
Definition: type_result.h:49
SCIP_RETCODE SCIPgetBendersSubproblemVar(SCIP *scip, SCIP_BENDERS *benders, SCIP_VAR *var, SCIP_VAR **mappedvar, int probnumber)
Definition: scip_benders.c:696
SCIP_Bool SCIPbendersMasterIsNonlinear(SCIP_BENDERS *benders)
Definition: benders.c:6417
SCIP_Longint SCIPbenderscutGetNFound(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:543
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
Definition: cons_linear.c:18192
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
Definition: type_benders.h:46
public methods for numerical tolerances
Definition: struct_benders.h:57
Definition: type_benders.h:48
Definition: struct_sol.h:73
public methods for handling parameter settings
SCIP_RETCODE SCIPsetConsRemovable(SCIP *scip, SCIP_CONS *cons, SCIP_Bool removable)
Definition: scip_cons.c:1420
void SCIPbenderscutSetEnabled(SCIP_BENDERSCUT *benderscut, SCIP_Bool enabled)
Definition: benderscut.c:593
Definition: type_result.h:44
public methods for Benders decomposition
Definition: struct_cons.h:46
Definition: struct_cons.h:126
Definition: type_stat.h:61
Definition: type_result.h:45
static SCIP_RETCODE computeStandardIntegerOptCut(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_SOL *sol, SCIP_CONS *cons, SCIP_ROW *row, SCIP_Real cutconstant, int probnumber, SCIP_Bool addcut, SCIP_Bool *success)
Definition: benderscut_int.c:158
SCIP_RETCODE SCIPsetConsDynamic(SCIP *scip, SCIP_CONS *cons, SCIP_Bool dynamic)
Definition: scip_cons.c:1395
Definition: type_set.h:52
Definition: type_retcode.h:42
SCIP_RETCODE SCIPsetBenderscutExit(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTEXIT((*benderscutexit)))
Definition: scip_benders.c:1252
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
public methods for constraint handler plugins and constraints
static SCIP_DECL_BENDERSCUTEXEC(benderscutExecInt)
Definition: benderscut_int.c:567
public data structures and miscellaneous methods
static SCIP_DECL_BENDERSCUTINIT(benderscutInitInt)
Definition: benderscut_int.c:529
Definition: struct_lp.h:201
Definition: type_benders.h:47
public methods for LP management
SCIP_RETCODE SCIPchgRowLhs(SCIP *scip, SCIP_ROW *row, SCIP_Real lhs)
Definition: scip_lp.c:1583
public methods for cuts and aggregation rows
SCIP * SCIPbendersSubproblem(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:5958
Constraint handler for linear constraints in their most general form, .
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip_lp.c:2138
SCIP_RETCODE SCIPcheckBendersSubproblemOptimality(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, int probnumber, SCIP_Bool *optimal)
Definition: scip_benders.c:892
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:5948
public methods for the LP relaxation, rows and columns
public methods for Benders' decomposition cuts
SCIP_RETCODE SCIPsetBenderscutInit(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTINIT((*benderscutinit)))
Definition: scip_benders.c:1228
general public methods
SCIP_Real SCIPbendersGetSubproblemLowerbound(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6712
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:486
public methods for solutions
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1119
public methods for message output
Definition: type_result.h:52
public methods for message handling
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2206
SCIP_RETCODE SCIPsetBenderscutFree(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTFREE((*benderscutfree)))
Definition: scip_benders.c:1204
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
Definition: cons_linear.c:18485
static SCIP_DECL_BENDERSCUTEXIT(benderscutExitInt)
Definition: benderscut_int.c:548
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)
Definition: scip_lp.c:1391
SCIP_VAR * SCIPbendersGetAuxiliaryVar(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6140
Definition: objbenders.h:43
public methods for global and local (sub)problems
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1361
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18437
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
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)
Definition: scip_param.c:57