scip_benders.h
Go to the documentation of this file.
38 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
67 * To use the Benders' decomposition for solving a problem, it first has to be activated with a call to SCIPactivateBenders().
70 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
77 * @note method has all Benders' decomposition callbacks as arguments and is thus changed every time a new callback is
91 SCIP_DECL_BENDERSCOPY ((*benderscopy)), /**< copy method of Benders' decomposition or NULL if you don't want to copy your plugin into sub-SCIPs */
95 SCIP_DECL_BENDERSINITPRE((*bendersinitpre)),/**< presolving initialization method for Benders' decomposition */
96 SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)),/**< presolving deinitialization method for Benders' decomposition */
97 SCIP_DECL_BENDERSINITSOL((*bendersinitsol)),/**< solving process initialization method of Benders' decomposition */
98 SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)),/**< solving process deinitialization method of Benders' decomposition */
99 SCIP_DECL_BENDERSGETVAR((*bendersgetvar)),/**< returns the master variable for a given subproblem variable */
100 SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)),/**< creates a Benders' decomposition subproblem */
101 SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)),/**< the execution method of the Benders' decomposition algorithm */
102 SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)),/**< the solving method for convex Benders' decomposition subproblems */
103 SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)),/**< the solving method for the Benders' decomposition subproblems */
104 SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)),/**< called after the subproblems are solved. */
105 SCIP_DECL_BENDERSFREESUB((*bendersfreesub)),/**< the freeing method for the Benders' decomposition subproblems */
109 /** creates a Benders' decomposition and includes it in SCIP with all non-fundamental callbacks set to NULL
111 * If needed, the non-fundamental callbacks can be added afterwards via setter functions SCIPsetBendersCopy(),
112 * SCIPsetBendersFree(), SCIPsetBendersInity(), SCIPsetBendersExit(), SCIPsetBendersInitsol(), SCIPsetBendersExitsol(),
115 * To use the Benders' decomposition for solving a problem, it first has to be activated with a call to SCIPactivateBenders().
118 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
125 * @note if you want to set all callbacks with a single method call, consider using SCIPincludeBenders() instead
138 SCIP_DECL_BENDERSGETVAR((*bendersgetvar)),/**< returns the master variable for a given subproblem variable */
139 SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)),/**< creates a Benders' decomposition subproblem */
145 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
156 SCIP_DECL_BENDERSCOPY((*benderscopy)) /**< copy method of Benders' decomposition or NULL if you don't want to copy your plugin into sub-SCIPs */
161 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
177 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
193 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
209 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
220 SCIP_DECL_BENDERSINITPRE((*bendersinitpre))/**< presolving initialization method of Benders' decomposition */
225 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
236 SCIP_DECL_BENDERSEXITPRE((*bendersexitpre))/**< presolving deinitialization method of Benders' decomposition */
241 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
252 SCIP_DECL_BENDERSINITSOL((*bendersinitsol))/**< solving process initialization method of Benders' decomposition */
257 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
268 SCIP_DECL_BENDERSEXITSOL((*bendersexitsol))/**< solving process deinitialization method of Benders' decomposition */
273 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
284 SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve))/**< method called prior to solving the subproblems */
289 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
300 SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)),/**< the solving method for convex Benders' decomposition subproblems */
301 SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)),/**< solving method for a Benders' decomposition subproblem */
302 SCIP_DECL_BENDERSFREESUB((*bendersfreesub))/**< the subproblem freeing method for Benders' decomposition */
307 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
318 SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve))/**< solving process deinitialization method of Benders' decomposition */
321 /** sets the subproblem comparison method for determining the solving order in Benders' decomposition
323 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
334 SCIP_DECL_SORTPTRCOMP((*benderssubcomp)) /**< a comparator for defining the solving order of the subproblems */
344 /** returns the array of currently available Benders' decomposition; active Benders' decomposition are in the first
366 * This method should be called during the problem creation stage for all pricers that are necessary to solve
371 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
386 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
409 * The checkint flag indicates whether integer feasibility can be assumed. If it is not assumed, i.e. checkint ==
410 * FALSE, then only the convex relaxations of the subproblems are solved. If integer feasibility is assumed, i.e.
411 * checkint == TRUE, then the convex relaxations and the full CIP are solved to generate Benders' cuts and check
414 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
432 SCIP_Bool* infeasible, /**< is the master problem infeasible with respect to the Benders' cuts? */
433 SCIP_Bool* auxviol, /**< set to TRUE only if the solution is feasible but the aux vars are violated */
442 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
466 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
499 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
515 * This is called if the user requires to solve the Benders' decomposition subproblem separately from the main Benders'
518 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
541 * The method either calls the users solve subproblem method or calls the generic method. In the case of the generic
544 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
570 * subproblem callback for Benders' decomposition or the default freeing methods. In the default case, if the
571 * subproblem is an LP, then SCIPendProbing is called. If the subproblem is a MIP, then SCIPfreeTransform is called.
573 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
594 /** checks the optimality of a Benders' decomposition subproblem by comparing the objective function value against the
597 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
615 SCIP_Bool* optimal /**< flag to indicate whether the current subproblem is optimal for the master */
627 /** solves an independent subproblem to identify its lower bound and updates the lower bound of the corresponding
638 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
652 * This process just adds a copy of the subproblem variables and constraints to the master problem, but keeps the
653 * subproblem stored in the Benders' decomposition data structure. The reason for keeping the subproblem available is
656 * Once the subproblem is merged into the master problem, then the subproblem is flagged as disabled. This means that
659 * The associated auxiliary variables are kept in the master problem. The objective function of the merged subproblem
670 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
695 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
713 * This should be called from the SCIPincludeBendersXyz for the associated Benders' decomposition. It is only possible
717 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
724 * @note method has all Benders' decomposition callbacks as arguments and is thus changed every time a new callback is
736 SCIP_DECL_BENDERSCUTCOPY((*benderscutcopy)),/**< copy method of Benders' decomposition cuts or NULL if you don't want to copy your plugin into sub-SCIPs */
740 SCIP_DECL_BENDERSCUTINITSOL((*benderscutinitsol)),/**< solving process initialization method of Benders' decomposition cuts */
741 SCIP_DECL_BENDERSCUTEXITSOL((*benderscutexitsol)),/**< solving process deinitialization method of Benders' decomposition cuts */
742 SCIP_DECL_BENDERSCUTEXEC((*benderscutexec)),/**< execution method of Benders' decomposition cuts */
746 /** creates a Benders' cut and includes it an associated Benders' decomposition with all non-fundamental callbacks set to NULL
748 * If needed, the non-fundamental callbacks can be added afterwards via setter functions SCIPsetBenderscutCopy(),
749 * SCIPsetBenderscutFree(), SCIPsetBenderscutInit(), SCIPsetBenderscutExit(), SCIPsetBenderscutInitsol(),
754 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
761 * @note if you want to set all callbacks with a single method call, consider using SCIPincludeBenders() instead
772 SCIP_DECL_BENDERSCUTEXEC((*benderscutexec)),/**< the execution method of the Benders' cut algorithm */
778 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
789 SCIP_DECL_BENDERSCUTCOPY((*benderscutcopy))/**< copy method of benderscut or NULL if you don't want to copy your plugin into sub-SCIPs */
794 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
810 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
826 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
842 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
853 SCIP_DECL_BENDERSCUTINITSOL((*benderscutinitsol))/**< solving process initialization method of benderscut */
858 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
869 SCIP_DECL_BENDERSCUTEXITSOL((*benderscutexitsol))/**< solving process deinitialization method of benderscut */
874 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
890 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
914 * When calling the function, the user must be sure that the variables are associated with the input SCIP instance.
917 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
SCIP_RETCODE SCIPsetBendersPresubsolve(SCIP *scip, SCIP_BENDERS *benders, SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)))
Definition: scip_benders.c:389
SCIP_RETCODE SCIPsetBendersSolveAndFreesub(SCIP *scip, SCIP_BENDERS *benders, SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)), SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)), SCIP_DECL_BENDERSFREESUB((*bendersfreesub)))
Definition: scip_benders.c:413
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_RETCODE SCIPmergeBendersSubproblemIntoMaster(SCIP *scip, SCIP_BENDERS *benders, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, int probnumber)
Definition: scip_benders.c:999
SCIP_RETCODE SCIPfreeBendersSubproblem(SCIP *scip, SCIP_BENDERS *benders, int probnumber)
Definition: scip_benders.c:861
void SCIPsetBendersPriority(SCIP *scip, SCIP_BENDERS *benders, int priority)
Definition: scip_benders.c:590
type definitions for miscellaneous datastructures
Definition: struct_scip.h:68
Definition: struct_benderscut.h:46
SCIP_RETCODE SCIPgetBendersMasterVar(SCIP *scip, SCIP_BENDERS *benders, SCIP_VAR *var, SCIP_VAR **mappedvar)
Definition: scip_benders.c:660
SCIP_RETCODE SCIPsetBendersSubproblemComp(SCIP *scip, SCIP_BENDERS *benders, SCIP_DECL_SORTPTRCOMP((*benderssubcomp)))
Definition: scip_benders.c:477
SCIP_RETCODE SCIPsetBendersExitsol(SCIP *scip, SCIP_BENDERS *benders, SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)))
Definition: scip_benders.c:365
Definition: struct_var.h:207
SCIP_RETCODE SCIPsetBendersInit(SCIP *scip, SCIP_BENDERS *benders, SCIP_DECL_BENDERSINIT((*bendersinit)))
Definition: scip_benders.c:245
SCIP_RETCODE SCIPincludeBenderscut(SCIP *scip, SCIP_BENDERS *benders, const char *name, const char *desc, int priority, SCIP_Bool islpcut, SCIP_DECL_BENDERSCUTCOPY((*benderscutcopy)), SCIP_DECL_BENDERSCUTFREE((*benderscutfree)), SCIP_DECL_BENDERSCUTINIT((*benderscutinit)), SCIP_DECL_BENDERSCUTEXIT((*benderscutexit)), SCIP_DECL_BENDERSCUTINITSOL((*benderscutinitsol)), SCIP_DECL_BENDERSCUTEXITSOL((*benderscutexitsol)), SCIP_DECL_BENDERSCUTEXEC((*benderscutexec)), SCIP_BENDERSCUTDATA *benderscutdata)
Definition: scip_benders.c:1085
SCIP_Real SCIPgetBendersAuxiliaryVarVal(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, int probnumber)
Definition: scip_benders.c:931
type definitions for return codes for SCIP methods
SCIP_RETCODE SCIPgetBendersSubproblemVar(SCIP *scip, SCIP_BENDERS *benders, SCIP_VAR *var, SCIP_VAR **mappedvar, int probnumber)
Definition: scip_benders.c:696
Definition: struct_benders.h:57
type definitions for LP management
Definition: struct_sol.h:73
SCIP_RETCODE SCIPsetBendersExit(SCIP *scip, SCIP_BENDERS *benders, SCIP_DECL_BENDERSEXIT((*bendersexit)))
Definition: scip_benders.c:269
SCIP_RETCODE SCIPcomputeBendersSubproblemLowerbound(SCIP *scip, SCIP_BENDERS *benders, int probnumber, SCIP_Real *lowerbound, SCIP_Bool *infeasible)
Definition: scip_benders.c:959
Definition: struct_misc.h:137
SCIP_RETCODE SCIPincludeBenders(SCIP *scip, const char *name, const char *desc, int priority, SCIP_Bool cutlp, SCIP_Bool cutpseudo, SCIP_Bool cutrelax, SCIP_Bool shareauxvars, SCIP_DECL_BENDERSCOPY((*benderscopy)), SCIP_DECL_BENDERSFREE((*bendersfree)), SCIP_DECL_BENDERSINIT((*bendersinit)), SCIP_DECL_BENDERSEXIT((*bendersexit)), SCIP_DECL_BENDERSINITPRE((*bendersinitpre)), SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)), SCIP_DECL_BENDERSINITSOL((*bendersinitsol)), SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)), SCIP_DECL_BENDERSGETVAR((*bendersgetvar)), SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)), SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)), SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)), SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)), SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)), SCIP_DECL_BENDERSFREESUB((*bendersfreesub)), SCIP_BENDERSDATA *bendersdata)
Definition: scip_benders.c:76
SCIP_RETCODE SCIPsetupBendersSubproblem(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, int probnumber, SCIP_BENDERSENFOTYPE type)
Definition: scip_benders.c:780
type definitions for SCIP's main datastructure
SCIP_RETCODE SCIPincludeBendersBasic(SCIP *scip, SCIP_BENDERS **bendersptr, const char *name, const char *desc, int priority, SCIP_Bool cutlp, SCIP_Bool cutpseudo, SCIP_Bool cutrelax, SCIP_Bool shareauxvars, SCIP_DECL_BENDERSGETVAR((*bendersgetvar)), SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)), SCIP_BENDERSDATA *bendersdata)
Definition: scip_benders.c:151
SCIP_RETCODE SCIPsetBenderscutExit(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTEXIT((*benderscutexit)))
Definition: scip_benders.c:1252
#define SCIP_DECL_BENDERSSOLVESUBCONVEX(x)
Definition: type_benders.h:259
type definitions for problem variables
SCIP_RETCODE SCIPsetBenderscutPriority(SCIP *scip, SCIP_BENDERSCUT *benderscut, int priority)
Definition: scip_benders.c:1324
SCIP_RETCODE SCIPstoreBendersCut(SCIP *scip, SCIP_BENDERS *benders, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, int nvars)
Definition: scip_benders.c:1366
SCIP_BENDERS * SCIPfindBenders(SCIP *scip, const char *name)
Definition: scip_benders.c:493
SCIP_RETCODE SCIPapplyBendersStoredCuts(SCIP *scip, SCIP_BENDERS *benders)
Definition: scip_benders.c:1434
SCIP_RETCODE SCIPapplyBendersDecomposition(SCIP *scip, int decompindex)
Definition: scip_benders.c:1028
SCIP_RETCODE SCIPsetBendersCopy(SCIP *scip, SCIP_BENDERS *benders, SCIP_DECL_BENDERSCOPY((*benderscopy)))
Definition: scip_benders.c:197
SCIP_RETCODE SCIPdeactivateBenders(SCIP *scip, SCIP_BENDERS *benders)
Definition: scip_benders.c:577
SCIP_RETCODE SCIPaddBendersSubproblem(SCIP *scip, SCIP_BENDERS *benders, SCIP *subproblem)
Definition: scip_benders.c:746
type definitions for Benders' decomposition methods
SCIP_RETCODE SCIPcheckBendersSubproblemOptimality(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, int probnumber, SCIP_Bool *optimal)
Definition: scip_benders.c:892
type definitions for storing primal CIP solutions
type definitions for Benders' decomposition cut
SCIP_RETCODE SCIPsetBendersPostsolve(SCIP *scip, SCIP_BENDERS *benders, SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)))
Definition: scip_benders.c:453
SCIP_RETCODE SCIPsetBenderscutInit(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTINIT((*benderscutinit)))
Definition: scip_benders.c:1228
SCIP_RETCODE SCIPsetBendersInitsol(SCIP *scip, SCIP_BENDERS *benders, SCIP_DECL_BENDERSINITSOL((*bendersinitsol)))
Definition: scip_benders.c:341
SCIP_RETCODE SCIPsetBenderscutInitsol(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTINITSOL((*benderscutinitsol)))
Definition: scip_benders.c:1276
SCIP_RETCODE SCIPsetBenderscutCopy(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTCOPY((*benderscutcopy)))
Definition: scip_benders.c:1180
SCIP_RETCODE SCIPsetBenderscutExitsol(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTEXITSOL((*benderscutexitsol)))
Definition: scip_benders.c:1300
SCIP_RETCODE SCIPsetBendersFree(SCIP *scip, SCIP_BENDERS *benders, SCIP_DECL_BENDERSFREE((*bendersfree)))
Definition: scip_benders.c:221
result codes for SCIP callback methods
SCIP_RETCODE SCIPsolveBendersSubproblem(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, int probnumber, SCIP_Bool *infeasible, SCIP_Bool solvecip, SCIP_Real *objective)
Definition: scip_benders.c:818
SCIP_RETCODE SCIPsetBenderscutFree(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTFREE((*benderscutfree)))
Definition: scip_benders.c:1204
int SCIPgetBendersNSubproblems(SCIP *scip, SCIP_BENDERS *benders)
Definition: scip_benders.c:722
common defines and data types used in all packages of SCIP
SCIP_RETCODE SCIPactivateBenders(SCIP *scip, SCIP_BENDERS *benders, int nsubproblems)
Definition: scip_benders.c:555
Definition: objbenders.h:43
SCIP_RETCODE SCIPsetBendersExitpre(SCIP *scip, SCIP_BENDERS *benders, SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)))
Definition: scip_benders.c:317
SCIP_RETCODE SCIPsolveBendersSubproblems(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool *infeasible, SCIP_Bool *auxviol, SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint)
Definition: scip_benders.c:622
SCIP_RETCODE SCIPsetBendersInitpre(SCIP *scip, SCIP_BENDERS *benders, SCIP_DECL_BENDERSINITPRE((*bendersinitpre)))
Definition: scip_benders.c:293
type definitions for constraints and constraint handlers