Scippy

SCIP

Solving Constraint Integer Programs

type_benders.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2018 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file type_benders.h
17  * @ingroup TYPEDEFINITIONS
18  * @brief type definitions for Benders' decomposition methods
19  * @author Stephen J. Maher
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef __SCIP_TYPE_BENDERS_H__
25 #define __SCIP_TYPE_BENDERS_H__
26 
27 #include "scip/def.h"
28 #include "scip/type_retcode.h"
29 #include "scip/type_scip.h"
30 
31 #ifdef __cplusplus
32 extern "C" {
33 #endif
34 
36 {
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 */
41 };
42 typedef enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE; /**< indicates the callback in cons_benders and cons_benderslp that triggered the subproblem solve */
43 
45 {
46  SCIP_BENDERSSOLVELOOP_CONVEX = 0, /**< the relaxation is solved in this iteration of the loop */
47  SCIP_BENDERSSOLVELOOP_CIP = 1, /**< the CIP is solved in this iteration of the loop */
48  SCIP_BENDERSSOLVELOOP_USERCONVEX = 2, /**< the user defined solve function is called */
49  SCIP_BENDERSSOLVELOOP_USERCIP = 3 /**< the user defined solve function is called */
50 };
51 typedef enum SCIP_BendersSolveLoop SCIP_BENDERSSOLVELOOP; /**< identifies the type of problem solved in each solve loop */
52 
54 {
55  SCIP_BENDERSSUBSTATUS_UNKNOWN = 0, /**< the subsystem status is unknown */
56  SCIP_BENDERSSUBSTATUS_OPTIMAL = 1, /**< the subsystem is solved to be optimal */
57  SCIP_BENDERSSUBSTATUS_AUXVIOL = 2, /**< the subproblem is optimal, but the auxiliary variable is violated */
58  SCIP_BENDERSSUBSTATUS_INFEAS = 3 /**< the subproblem is solved to be infeasible */
59 };
61 
62 typedef struct SCIP_Benders SCIP_BENDERS; /**< Benders' decomposition data */
63 typedef struct SCIP_BendersData SCIP_BENDERSDATA; /**< locally defined Benders' decomposition data */
64 
65 
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
68  * function
69  *
70  * input:
71  * - scip : SCIP main data structure
72  * - benders : the Benders' decomposition itself
73  */
74 #define SCIP_DECL_BENDERSCOPY(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
75 
76 /** destructor of Benders' decomposition to free user data (called when SCIP is exiting)
77  *
78  * input:
79  * - scip : SCIP main data structure
80  * - benders : the Benders' decomposition itself
81  */
82 #define SCIP_DECL_BENDERSFREE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
83 
84 /** initialization method of Benders' decomposition (called after problem was transformed and the Benders' decomposition
85  * is active)
86  *
87  * input:
88  * - scip : SCIP main data structure
89  * - benders : the Benders' decomposition itself
90  */
91 #define SCIP_DECL_BENDERSINIT(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
92 
93 /** deinitialization method of Benders' decomposition (called before transformed problem is freed and the Benders'
94  * decomposition is active)
95  *
96  * input:
97  * - scip : SCIP main data structure
98  * - benders : the Benders' decomposition itself
99  */
100 #define SCIP_DECL_BENDERSEXIT(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
101 
102 /** presolving initialization method of the Benders' decomposition (called when presolving is about to begin)
103  *
104  * This function is called immediately after the auxiliary variables are created in the master problem. The callback
105  * provides the user an opportunity to add variable data to the auxiliary variables.
106  *
107  * input:
108  * - scip : SCIP main data structure
109  * - benders : the Benders' decomposition itself
110  */
111 #define SCIP_DECL_BENDERSINITPRE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
112 
113 /** presolving deinitialization method of the Benders' decomposition (called after presolving has been finished)
114  *
115  * input:
116  * - scip : SCIP main data structure
117  * - benders : the Benders' decomposition itself
118  */
119 #define SCIP_DECL_BENDERSEXITPRE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
120 
121 /** solving process initialization method of Benders' decomposition (called when branch and bound process is about to begin)
122  *
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.
125  *
126  * input:
127  * - scip : SCIP main data structure
128  * - benders : the Benders' decomposition itself
129  */
130 #define SCIP_DECL_BENDERSINITSOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
131 
132 /** solving process deinitialization method of Benders' decomposition (called before branch and bound process data is freed)
133  *
134  * This method is called before the branch and bound process is freed.
135  * The Benders' decomposition should use this call to clean up its branch and bound data.
136  *
137  * input:
138  * - scip : SCIP main data structure
139  * - benders : the Benders' decomposition itself
140  */
141 #define SCIP_DECL_BENDERSEXITSOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
142 
143 /** the method for creating the Benders' decomposition subproblem. This method is called during the initialisation stage
144  * (after the master problem was transformed).
145  *
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
148  * possible to construct the variable mapping within the BENDERSINIT callback.
149  *
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.
156  *
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
160  * convex, then the user must call SCIPbendersSetSubproblemIsConvex()
161  *
162  * If the user does NOT implement a subproblem solving method, then the convexity of the problem is determined
163  * internally.
164  *
165  * input:
166  * - scip : SCIP main data structure
167  * - benders : the Benders' decomposition data structure
168  * - probnumber : the subproblem problem number
169  */
170 #define SCIP_DECL_BENDERSCREATESUB(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, int probnumber)
171 
172 /** called before the subproblem solving loop for Benders' decomposition. The pre subproblem solve function gives the
173  * user an oppportunity to perform any global set up for the Benders' decomposition.
174  *
175  * input:
176  * - scip : SCIP main data structure
177  * - benders : the Benders' decomposition data structure
178  * - sol : the solution that will be checked in the subproblem. Can be NULL.
179  * - type : the enforcement type that called the Benders' decomposition solve.
180  * - checkint : should the integer subproblems be checked.
181  * - skipsolve : flag to return whether the current subproblem solving loop should be skipped
182  * - result : a result to be returned to the Benders' constraint handler if the solve is skipped. If the
183  * solve is not skipped, then the returned result is ignored.
184  *
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.
191  */
192 #define SCIP_DECL_BENDERSPRESUBSOLVE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_SOL* sol,\
193  SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint, SCIP_Bool* skipsolve, SCIP_RESULT* result)
194 
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
198  * are given by a single vector of reals.
199  *
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
203  * loop only.
204  *
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
208  * CONTINUOUS for the CONVEX subproblem solve and to INTEGER for the CIP subproblem solve.
209  *
210  * The solving methods are separated so that they can be called in parallel.
211  *
212  * NOTE: The solving methods must be thread safe.
213  *
214  * This method is called from within the execution method.
215  *
216  * input:
217  * - scip : SCIP main data structure
218  * - benders : the Benders' decomposition data structure
219  * - sol : the solution that will be checked in the subproblem. Can be NULL.
220  * - probnumber : the subproblem problem number
221  * - onlyconvexcheck : flag to indicate that only the convex relaxations will be checked in this solving loop. This is
222  * a feature of the Large Neighbourhood Benders' Search
223  * - objective : variable to return the objective function value of the subproblem
224  * - result : the result from solving the subproblem
225  *
226  * possible return values for *result (if more than one applies, the first in the list should be used):
227  * - SCIP_DIDNOTRUN : the subproblem was not solved in this iteration
228  * - SCIP_FEASIBLE : the subproblem is solved and is feasible
229  * - SCIP_INFEASIBLE : the subproblem is solved and is infeasible
230  * - SCIP_UNBOUNDED : the subproblem is solved and is unbounded
231  */
232 #define SCIP_DECL_BENDERSSOLVESUBCONVEX(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_SOL* sol,\
233  int probnumber, SCIP_Bool onlyconvexcheck, SCIP_Real* objective, SCIP_RESULT* result)
234 
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
238  * be any CIP.
239  *
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
243  * loop only.
244  *
245  * The solving methods are separated so that they can be called in parallel.
246  *
247  * NOTE: The solving methods must be thread safe.
248  *
249  * This method is called from within the execution method.
250  *
251  * input:
252  * - scip : SCIP main data structure
253  * - benders : the Benders' decomposition data structure
254  * - sol : the solution that will be checked in the subproblem. Can be NULL.
255  * - probnumber : the subproblem problem number
256  * - objective : variable to return the objective function value of the subproblem
257  * - result : the result from solving the subproblem
258  *
259  * possible return values for *result (if more than one applies, the first in the list should be used):
260  * - SCIP_DIDNOTRUN : the subproblem was not solved in this iteration
261  * - SCIP_FEASIBLE : the subproblem is solved and is feasible
262  * - SCIP_INFEASIBLE : the subproblem is solved and is infeasible
263  * - SCIP_UNBOUNDED : the subproblem is solved and is unbounded
264  */
265 #define SCIP_DECL_BENDERSSOLVESUB(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_SOL* sol, int probnumber,\
266  SCIP_Real* objective, SCIP_RESULT* result)
267 
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
271  * SCIP_DECL_BENDERSFREESUB.
272  *
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.
277  *
278  * This callback provides the opportunity for the user to clean up any data structures that should not exist beyond the current
279  * iteration.
280  * The user has full access to the master and subproblems in this callback. So it is possible to construct solution for
281  * the master problem in the method.
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
285  * subproblem was merged into the master problem, then the merged flag must be set to TRUE.
286  *
287  * input:
288  * - scip : SCIP main data structure
289  * - benders : the Benders' decomposition data structure
290  * - sol : the solution that was checked by solving the subproblems. Can be NULL.
291  * - type : the enforcement type that called the Benders' decomposition solve.
292  * - mergecands : the subproblems that are candidates for merging into the master problem, the first
293  * npriomergecands are the priority candidates (they should be merged). The remaining
294  * (nmergecands - npriomergecands) are subproblems that could be merged if desired.
295  * - npriomergecands : the number of priority merge candidates.
296  * - nmergecands : the total number of subproblems that are candidates for merging into the master problem
297  * - checkint : should the integer subproblems be checked.
298  * - infeasible : indicates whether at least one subproblem is infeasible
299  * - merged : flag to indicate whether a subproblem was merged into the master problem.
300  */
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,\
303  SCIP_Bool infeasible, SCIP_Bool* merged)
304 
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.
310  *
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.
315  *
316  * NOTE: The freeing methods must be thread safe.
317  *
318  * input:
319  * - scip : SCIP main data structure
320  * - benders : the Benders' decomposition data structure
321  * - probnumber : the subproblem problem number
322  */
323 #define SCIP_DECL_BENDERSFREESUB(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, int probnumber)
324 
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
327  * and sub to master.
328  *
329  * This method is called when generating the cuts. The cuts are generated by using the solution to the subproblem to
330  * eliminate a solution to the master problem.
331  *
332  * input:
333  * - scip : SCIP main data structure
334  * - benders : the Benders' decomposition structure
335  * - var : the variable for which the corresponding variable in the master or subproblem is required
336  * - mappedvar : pointer to store the variable that is mapped to var
337  * - probnumber : the number of the subproblem that the desired variable belongs to, -1 for the master problem
338  */
339 #define SCIP_DECL_BENDERSGETVAR(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_VAR* var,\
340  SCIP_VAR** mappedvar, int probnumber)
341 
342 #ifdef __cplusplus
343 }
344 #endif
345 
346 #endif
SCIP_BendersEnfoType
Definition: type_benders.h:35
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
Definition: type_benders.h:42
type definitions for return codes for SCIP methods
SCIP_BendersSolveLoop
Definition: type_benders.h:44
type definitions for SCIP&#39;s main datastructure
struct SCIP_BendersData SCIP_BENDERSDATA
Definition: type_benders.h:63
enum SCIP_BendersSolveLoop SCIP_BENDERSSOLVELOOP
Definition: type_benders.h:51
SCIP_BendersSubStatus
Definition: type_benders.h:53
common defines and data types used in all packages of SCIP
enum SCIP_BendersSubStatus SCIP_BENDERSSUBSTATUS
Definition: type_benders.h:60