type definitions for Benders' decomposition methods
Definition in file type_benders.h.
Go to the source code of this file.
Macros | |
#define | SCIP_DECL_BENDERSCOPY(x) |
#define | SCIP_DECL_BENDERSFREE(x) |
#define | SCIP_DECL_BENDERSINIT(x) |
#define | SCIP_DECL_BENDERSEXIT(x) |
#define | SCIP_DECL_BENDERSINITPRE(x) |
#define | SCIP_DECL_BENDERSEXITPRE(x) |
#define | SCIP_DECL_BENDERSINITSOL(x) |
#define | SCIP_DECL_BENDERSEXITSOL(x) |
#define | SCIP_DECL_BENDERSCREATESUB(x) |
#define | SCIP_DECL_BENDERSPRESUBSOLVE(x) |
#define | SCIP_DECL_BENDERSSOLVESUBCONVEX(x) |
#define | SCIP_DECL_BENDERSSOLVESUB(x) |
#define | SCIP_DECL_BENDERSPOSTSOLVE(x) |
#define | SCIP_DECL_BENDERSFREESUB(x) |
#define | SCIP_DECL_BENDERSGETVAR(x) |
#define SCIP_DECL_BENDERSCOPY | ( | x | ) |
copy method for Benders' decomposition plugins (called when SCIP copies plugins). If there is an active Benders' decomposition, all copies are not valid. As such, there is no valid parameter that is passed to the callback function
input:
Definition at line 95 of file type_benders.h.
Referenced by doBendersCreate(), SCIPbendersCreate(), SCIPbendersSetCopy(), and SCIPincludeBenders().
#define SCIP_DECL_BENDERSFREE | ( | x | ) |
destructor of Benders' decomposition to free user data (called when SCIP is exiting)
input:
Definition at line 103 of file type_benders.h.
Referenced by doBendersCreate(), SCIPbendersCreate(), SCIPbendersSetFree(), and SCIPincludeBenders().
#define SCIP_DECL_BENDERSINIT | ( | x | ) |
initialization method of Benders' decomposition (called after problem was transformed and the Benders' decomposition is active)
input:
Definition at line 112 of file type_benders.h.
Referenced by doBendersCreate(), SCIPbendersCreate(), SCIPincludeBenders(), and SCIPsetBendersInit().
#define SCIP_DECL_BENDERSEXIT | ( | x | ) |
deinitialization method of Benders' decomposition (called before transformed problem is freed and the Benders' decomposition is active)
input:
Definition at line 121 of file type_benders.h.
Referenced by doBendersCreate(), SCIPbendersCreate(), SCIPincludeBenders(), and SCIPsetBendersExit().
#define SCIP_DECL_BENDERSINITPRE | ( | x | ) |
presolving initialization method of the Benders' decomposition (called when presolving is about to begin)
This function is called immediately after the auxiliary variables are created in the master problem. The callback provides the user an opportunity to add variable data to the auxiliary variables.
input:
Definition at line 132 of file type_benders.h.
#define SCIP_DECL_BENDERSEXITPRE | ( | x | ) |
presolving deinitialization method of the Benders' decomposition (called after presolving has been finished)
input:
Definition at line 140 of file type_benders.h.
#define SCIP_DECL_BENDERSINITSOL | ( | x | ) |
solving process initialization method of Benders' decomposition (called when branch and bound process is about to begin)
This method is called when the presolving was finished and the branch and bound process is about to begin. The Benders' decomposition may use this call to initialize its branch and bound specific data.
input:
Definition at line 151 of file type_benders.h.
#define SCIP_DECL_BENDERSEXITSOL | ( | x | ) |
solving process deinitialization method of Benders' decomposition (called before branch and bound process data is freed)
This method is called before the branch and bound process is freed. The Benders' decomposition should use this call to clean up its branch and bound data.
input:
Definition at line 162 of file type_benders.h.
#define SCIP_DECL_BENDERSCREATESUB | ( | x | ) |
the method for creating the Benders' decomposition subproblem. This method is called during the initialisation stage (after the master problem was transformed).
This method must register the SCIP instance for the subproblem with the Benders' decomposition core by calling SCIPaddBendersSubproblem. Typically, the user must create the SCIP instances for the subproblems. These can be created within a reader or probdata and then registered with the Benders' decomposition core during the call of this callback. If there are any settings required for solving the subproblems, then they should be set here. However, some settings will be overridden by the standard solving method included in the Benders' decomposition framework. If a special solving method is desired, the user can implement the bendersSolvesubXyz callback. In this latter case, it is possible to provide a NULL pointer to SCIPaddBendersSubproblem. This will ensure that no internal solving methods available within the Benders' decomposition core are invoked during the solving process.
If the user defines a subproblem solving method, then in BENDERSCREATESUB, the user must explicitly specify the subproblem type. This is necessary because the dual solutions from convex problems can be used to generate cuts. The classical Benders' optimality and feasibility cuts require that the subproblems are convex. The subproblem type is specified by calling SCIPbendersSetSubproblemType. The available subproblem types are defined in SCIP_BENDERSSUBTYPE.
If the user does NOT implement a subproblem solving method, then the convexity of the problem is determined internally.
input:
Definition at line 194 of file type_benders.h.
#define SCIP_DECL_BENDERSPRESUBSOLVE | ( | x | ) |
called before the subproblem solving loop for Benders' decomposition. The pre subproblem solve function gives the user an oppportunity to perform any global set up for the Benders' decomposition.
input:
possible return values for *result (if more than one applies, the first in the list should be used):
Definition at line 218 of file type_benders.h.
#define SCIP_DECL_BENDERSSOLVESUBCONVEX | ( | x | ) |
the solving method for a convex Benders' decomposition subproblem. This call back is provided to solve problems for which the dual soluitons are used to generate Benders' decomposition cuts. In the classical Benders' decomposition implementation, this would be an LP. However, it can be any convex problem where the dual solutions are given by a single vector of reals.
In the Benders' decomposition subproblem solving process, there are two solving loops. The first is where the convex subproblems, and the convex relaxations of subproblems, are solved. If no cuts are generated after this solving loop, then the second loop solves subproblems defined as CIPs. This callback is executed during the FIRST solving loop only.
In the classical Benders' decomposition implementation, if the subproblems are all LPs the only the BENDERSSOLVESUBCONVEX need to be implemented. If the subproblems are MIPs, then it is useful to only implement a single SCIP instance for the subproblem and then change the variable types of the appropriate variables to CONTINUOUS for the CONVEX subproblem solve and to INTEGER for the CIP subproblem solve.
The solving methods are separated so that they can be called in parallel.
NOTE: The solving methods must be thread safe.
This method is called from within the execution method.
input:
possible return values for *result (if more than one applies, the first in the list should be used):
Definition at line 259 of file type_benders.h.
#define SCIP_DECL_BENDERSSOLVESUB | ( | x | ) |
the solving method for a Benders' decomposition subproblem as a CIP. This call back is provided to solve problems for which the dual solutions are not well defined. In this case, the cuts are typically generated from the primal solution to the CIP. In the classical Benders' decomposition implementation, this would be a MIP. However, it can be any CIP.
In the Benders' decomposition subproblem solving process, there are two solving loops. The first is where the convex subproblems, and the convex relaxations of subproblems, are solved. If no cuts are generated after this solving loop, then the second loop solves subproblems defined as CIPs. This callback is executed during the SECOND solving loop only.
The solving methods are separated so that they can be called in parallel.
NOTE: The solving methods must be thread safe.
This method is called from within the execution method.
input:
possible return values for *result (if more than one applies, the first in the list should be used):
Definition at line 292 of file type_benders.h.
#define SCIP_DECL_BENDERSPOSTSOLVE | ( | x | ) |
the post-solve method for Benders' decomposition. The post-solve method is called after the subproblems have been solved but before they have been freed. After the solving of the Benders' decomposition subproblems, the subproblem solving data is freed in the SCIP_DECL_BENDERSFREESUB callback. However, it is not necessary to implement SCIP_DECL_BENDERSFREESUB.
If SCIP_DECL_BENDERSFREESUB is not implemented, then the Benders' decomposition framework will perform a default freeing of the subproblems. If a subproblem is an LP, then they will be in probing mode for the subproblem solve. So the freeing process involves ending the probing mode. If the subproblem is a MIP, then the subproblem is solved by calling SCIPsolve. As such, the transformed problem must be freed after each subproblem solve.
This callback provides the opportunity for the user to clean up any data structures that should not exist beyond the current iteration. The user has full access to the master and subproblems in this callback. So it is possible to construct solution for the master problem in the method. Additionally, if there are any subproblems that are infeasibility and this can not be resolved, then the it is possible to merge these subproblems into the master problem. The subproblem indices are given in the mergecands array. The merging can be perform by a user defined function or by calling SCIPmergeBendersSubproblemIntoMaster. If a subproblem was merged into the master problem, then the merged flag must be set to TRUE.
input:
Definition at line 328 of file type_benders.h.
#define SCIP_DECL_BENDERSFREESUB | ( | x | ) |
frees the subproblem so that it can be resolved in the next iteration. As stated above, it is not necessary to implement this callback. If the callback is implemented, the subproblems should be freed by calling SCIPfreeTransform(). However, if the subproblems are LPs, then it could be more efficient to put the subproblem into probing mode prior to solving and then exiting the probing mode during the callback. To put the subproblem into probing mode, the subproblem must be in SCIP_STAGE_SOLVING. This can be achieved by using eventhandlers.
If SCIP_DECL_BENDERSFREESUB is not implemented, then the Benders' decomposition framework will perform a default freeing of the subproblems. If a subproblem is an LP, then they will be in probing mode for the subproblem solve. So the freeing process involves ending the probing mode. If the subproblem is a MIP, then the subproblem is solved by calling SCIPsolve. As such, the transformed problem must be freed after each subproblem solve.
NOTE: The freeing methods must be thread safe.
input:
Definition at line 350 of file type_benders.h.
#define SCIP_DECL_BENDERSGETVAR | ( | x | ) |
the variable mapping from the subproblem to the master problem. It is neccessary to have a mapping between every master problem variable and its counterpart in the subproblem. This mapping must go both ways: from master to sub and sub to master.
This method is called when generating the cuts. The cuts are generated by using the solution to the subproblem to eliminate a solution to the master problem.
input:
Definition at line 366 of file type_benders.h.
typedef enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE |
indicates the callback in cons_benders and cons_benderslp that triggered the subproblem solve
Definition at line 51 of file type_benders.h.
typedef enum SCIP_BendersSolveLoop SCIP_BENDERSSOLVELOOP |
identifies the type of problem solved in each solve loop
Definition at line 60 of file type_benders.h.
typedef enum SCIP_BendersSubStatus SCIP_BENDERSSUBSTATUS |
Definition at line 69 of file type_benders.h.
typedef enum SCIP_BendersSubType SCIP_BENDERSSUBTYPE |
Definition at line 79 of file type_benders.h.
typedef struct SCIP_Benders SCIP_BENDERS |
Benders' decomposition data
Definition at line 81 of file type_benders.h.
typedef struct SCIP_BendersData SCIP_BENDERSDATA |
locally defined Benders' decomposition data
Definition at line 82 of file type_benders.h.
typedef struct SCIP_SubproblemSolveStat SCIP_SUBPROBLEMSOLVESTAT |
the solving statistics of the subproblems
Definition at line 83 of file type_benders.h.
enum SCIP_BendersEnfoType |
Definition at line 44 of file type_benders.h.
Definition at line 53 of file type_benders.h.
Definition at line 62 of file type_benders.h.
enum SCIP_BendersSubType |
Definition at line 71 of file type_benders.h.