type_benders.h
Go to the documentation of this file.
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37 SCIP_BENDERSENFOTYPE_LP = 1, /**< the Benders' subproblems are solved during the enforcement of an LP solution */
38 SCIP_BENDERSENFOTYPE_RELAX = 2, /**< the Benders' subproblems are solved during the enforcement of a relaxation solution */
39 SCIP_BENDERSENFOTYPE_PSEUDO = 3, /**< the Benders' subproblems are solved during the enforcement of a pseudo solution */
40 SCIP_BENDERSENFOTYPE_CHECK = 4 /**< the Benders' subproblems are solved during the checking of a solution for feasibility */
42 typedef enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE; /**< indicates the callback in cons_benders and cons_benderslp that triggered the subproblem solve */
51 typedef enum SCIP_BendersSolveLoop SCIP_BENDERSSOLVELOOP; /**< identifies the type of problem solved in each solve loop */
57 SCIP_BENDERSSUBSTATUS_AUXVIOL = 2, /**< the subproblem is optimal, but the auxiliary variable is violated */
63 typedef struct SCIP_BendersData SCIP_BENDERSDATA; /**< locally defined Benders' decomposition data */
66 /** copy method for Benders' decomposition plugins (called when SCIP copies plugins). If there is an active Benders'
67 * decomposition, all copies are not valid. As such, there is no valid parameter that is passed to the callback
84 /** initialization method of Benders' decomposition (called after problem was transformed and the Benders' decomposition
93 /** deinitialization method of Benders' decomposition (called before transformed problem is freed and the Benders'
102 /** presolving initialization method of the Benders' decomposition (called when presolving is about to begin)
104 * This function is called immediately after the auxiliary variables are created in the master problem. The callback
113 /** presolving deinitialization method of the Benders' decomposition (called after presolving has been finished)
121 /** solving process initialization method of Benders' decomposition (called when branch and bound process is about to begin)
123 * This method is called when the presolving was finished and the branch and bound process is about to begin.
124 * The Benders' decomposition may use this call to initialize its branch and bound specific data.
132 /** solving process deinitialization method of Benders' decomposition (called before branch and bound process data is freed)
143 /** the method for creating the Benders' decomposition subproblem. This method is called during the initialisation stage
146 * @note When the create subproblem callback is invoked, the mapping between the master problem and subproblem
147 * variables must be available. The create subproblem callback is invoked immediately after BENDERSINIT. So, it is
150 * This method must register the SCIP instance for the subproblem with the Benders' decomposition core by calling
151 * SCIPaddBendersSubproblem. Typically, the user must create the SCIP instances for the subproblems. These can be
152 * created within a reader or probdata and then registered with the Benders' decomposition core during the call of this
153 * callback. If there are any settings required for solving the subproblems, then they should be set here. However,
154 * some settings will be overridden by the standard solving method included in the Benders' decomposition framework.
155 * If a special solving method is desired, the user can implement the bendersSolvesubXyz callback.
157 * If the user defines a subproblem solving method, then in BENDERSCREATESUB, the user must specify whether the
158 * subproblem is convex. This is necessary because the dual solutions from convex problems can be used to generate cuts.
159 * The classical Benders' optimality and feasibility cuts require that the subproblems are convex. If the subproblem is
162 * If the user does NOT implement a subproblem solving method, then the convexity of the problem is determined
170 #define SCIP_DECL_BENDERSCREATESUB(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, int probnumber)
172 /** called before the subproblem solving loop for Benders' decomposition. The pre subproblem solve function gives the
182 * - result : a result to be returned to the Benders' constraint handler if the solve is skipped. If the
185 * possible return values for *result (if more than one applies, the first in the list should be used):
186 * - SCIP_DIDNOTRUN : the subproblem was not solved in this iteration. Other decompositions will be checked.
187 * - SCIP_CONSADDED : a constraint has been added to the master problem. No other decompositions will be checked.
188 * - SCIP_SEPARATED : a cut has been added to the master problem. No other decompositions will be checked.
189 * - SCIP_FEASIBLE : feasibility of the solution is reported to SCIP. Other decompositions will be checked.
190 * - SCIP_INFEASIBLE : infeasibility of the solution is reported to SCIP. No other decompositions will be checked.
192 #define SCIP_DECL_BENDERSPRESUBSOLVE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_SOL* sol,\
195 /** the solving method for a convex Benders' decomposition subproblem. This call back is provided to solve problems
196 * for which the dual soluitons are used to generate Benders' decomposition cuts. In the classical Benders'
197 * decomposition implementation, this would be an LP. However, it can be any convex problem where the dual solutions
200 * In the Benders' decomposition subproblem solving process, there are two solving loops. The first is where the convex
201 * subproblems, and the convex relaxations of subproblems, are solved. If no cuts are generated after this solving
202 * loop, then the second loop solves subproblems defined as CIPs. This callback is executed during the FIRST solving
205 * In the classical Benders' decomposition implementation, if the subproblems are all LPs the only the
206 * BENDERSSOLVESUBCONVEX need to be implemented. If the subproblems are MIPs, then it is useful to only implement a
207 * single SCIP instance for the subproblem and then change the variable types of the appropriate variables to
221 * - onlyconvexcheck : flag to indicate that only the convex relaxations will be checked in this solving loop. This is
226 * possible return values for *result (if more than one applies, the first in the list should be used):
232 #define SCIP_DECL_BENDERSSOLVESUBCONVEX(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_SOL* sol,\
235 /** the solving method for a Benders' decomposition subproblem as a CIP. This call back is provided to solve problems
236 * for which the dual solutions are not well defined. In this case, the cuts are typically generated from the primal
237 * solution to the CIP. In the classical Benders' decomposition implementation, this would be a MIP. However, it can
240 * In the Benders' decomposition subproblem solving process, there are two solving loops. The first is where the convex
241 * subproblems, and the convex relaxations of subproblems, are solved. If no cuts are generated after this solving
242 * loop, then the second loop solves subproblems defined as CIPs. This callback is executed during the SECOND solving
259 * possible return values for *result (if more than one applies, the first in the list should be used):
265 #define SCIP_DECL_BENDERSSOLVESUB(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_SOL* sol, int probnumber,\
268 /** the post-solve method for Benders' decomposition. The post-solve method is called after the subproblems have
269 * been solved but before they have been freed. After the solving of the Benders' decomposition subproblems, the
270 * subproblem solving data is freed in the SCIP_DECL_BENDERSFREESUB callback. However, it is not necessary to implement
273 * If SCIP_DECL_BENDERSFREESUB is not implemented, then the Benders' decomposition framework will perform a default
274 * freeing of the subproblems. If a subproblem is an LP, then they will be in probing mode for the subproblem
275 * solve. So the freeing process involves ending the probing mode. If the subproblem is a MIP, then the subproblem is
276 * solved by calling SCIPsolve. As such, the transformed problem must be freed after each subproblem solve.
278 * This callback provides the opportunity for the user to clean up any data structures that should not exist beyond the current
280 * The user has full access to the master and subproblems in this callback. So it is possible to construct solution for
282 * Additionally, if there are any subproblems that are infeasibility and this can not be resolved, then the it is
283 * possible to merge these subproblems into the master problem. The subproblem indices are given in the mergecands
284 * array. The merging can be perform by a user defined function or by calling SCIPmergeBendersSubproblemIntoMaster. If a
292 * - mergecands : the subproblems that are candidates for merging into the master problem, the first
296 * - nmergecands : the total number of subproblems that are candidates for merging into the master problem
301 #define SCIP_DECL_BENDERSPOSTSOLVE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_SOL* sol,\
302 SCIP_BENDERSENFOTYPE type, int* mergecands, int npriomergecands, int nmergecands, SCIP_Bool checkint,\
305 /** frees the subproblem so that it can be resolved in the next iteration. As stated above, it is not necessary to
306 * implement this callback. If the callback is implemented, the subproblems should be freed by calling
307 * SCIPfreeTransform(). However, if the subproblems are LPs, then it could be more efficient to put the subproblem
308 * into probing mode prior to solving and then exiting the probing mode during the callback. To put the subproblem into
309 * probing mode, the subproblem must be in SCIP_STAGE_SOLVING. This can be achieved by using eventhandlers.
311 * If SCIP_DECL_BENDERSFREESUB is not implemented, then the Benders' decomposition framework will perform a default
312 * freeing of the subproblems. If a subproblem is an LP, then they will be in probing mode for the subproblem
313 * solve. So the freeing process involves ending the probing mode. If the subproblem is a MIP, then the subproblem is
314 * solved by calling SCIPsolve. As such, the transformed problem must be freed after each subproblem solve.
323 #define SCIP_DECL_BENDERSFREESUB(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, int probnumber)
325 /** the variable mapping from the subproblem to the master problem. It is neccessary to have a mapping between every
326 * master problem variable and its counterpart in the subproblem. This mapping must go both ways: from master to sub
329 * This method is called when generating the cuts. The cuts are generated by using the solution to the subproblem to
335 * - var : the variable for which the corresponding variable in the master or subproblem is required
337 * - probnumber : the number of the subproblem that the desired variable belongs to, -1 for the master problem
339 #define SCIP_DECL_BENDERSGETVAR(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_VAR* var,\
Definition: type_benders.h:58
Definition: type_benders.h:40
Definition: type_benders.h:46
type definitions for return codes for SCIP methods
Definition: type_benders.h:37
Definition: struct_benders.h:38
Definition: type_benders.h:39
Definition: type_benders.h:55
Definition: type_benders.h:47
type definitions for SCIP's main datastructure
Definition: type_benders.h:38
Definition: type_benders.h:57
Definition: type_benders.h:56
Definition: type_benders.h:49
common defines and data types used in all packages of SCIP