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-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file type_benders.h
26 * @ingroup TYPEDEFINITIONS
27 * @brief type definitions for Benders' decomposition methods
28 * @author Stephen J. Maher
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
33#ifndef __SCIP_TYPE_BENDERS_H__
34#define __SCIP_TYPE_BENDERS_H__
35
36#include "scip/def.h"
37#include "scip/type_retcode.h"
38#include "scip/type_scip.h"
39
40#ifdef __cplusplus
41extern "C" {
42#endif
43
45{
46 SCIP_BENDERSENFOTYPE_LP = 1, /**< the Benders' subproblems are solved during the enforcement of an LP solution */
47 SCIP_BENDERSENFOTYPE_RELAX = 2, /**< the Benders' subproblems are solved during the enforcement of a relaxation solution */
48 SCIP_BENDERSENFOTYPE_PSEUDO = 3, /**< the Benders' subproblems are solved during the enforcement of a pseudo solution */
49 SCIP_BENDERSENFOTYPE_CHECK = 4 /**< the Benders' subproblems are solved during the checking of a solution for feasibility */
50};
51typedef enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE; /**< indicates the callback in cons_benders and cons_benderslp that triggered the subproblem solve */
52
54{
55 SCIP_BENDERSSOLVELOOP_CONVEX = 0, /**< the relaxation is solved in this iteration of the loop */
56 SCIP_BENDERSSOLVELOOP_CIP = 1, /**< the CIP is solved in this iteration of the loop */
57 SCIP_BENDERSSOLVELOOP_USERCONVEX = 2, /**< the user defined solve function is called */
58 SCIP_BENDERSSOLVELOOP_USERCIP = 3 /**< the user defined solve function is called */
59};
60typedef enum SCIP_BendersSolveLoop SCIP_BENDERSSOLVELOOP; /**< identifies the type of problem solved in each solve loop */
61
63{
64 SCIP_BENDERSSUBSTATUS_UNKNOWN = 0, /**< the subsystem status is unknown */
65 SCIP_BENDERSSUBSTATUS_OPTIMAL = 1, /**< the subsystem is solved to be optimal */
66 SCIP_BENDERSSUBSTATUS_AUXVIOL = 2, /**< the subproblem is optimal, but the auxiliary variable is violated */
67 SCIP_BENDERSSUBSTATUS_INFEAS = 3 /**< the subproblem is solved to be infeasible */
68};
70
72{
73 SCIP_BENDERSSUBTYPE_CONVEXCONT = 0, /**< the subproblem has convex constraints and continuous variables */
74 SCIP_BENDERSSUBTYPE_CONVEXDIS = 1, /**< the subproblem has convex constraints and discrete variables */
75 SCIP_BENDERSSUBTYPE_NONCONVEXCONT = 2, /**< the subproblem has non-convex constraints and continuous variables */
76 SCIP_BENDERSSUBTYPE_NONCONVEXDIS = 3, /**< the subproblem has non-convex constraints and discrete variables */
77 SCIP_BENDERSSUBTYPE_UNKNOWN = 4, /**< the default type before the type is known */
78};
80
81typedef struct SCIP_Benders SCIP_BENDERS; /**< Benders' decomposition data */
82typedef struct SCIP_BendersData SCIP_BENDERSDATA; /**< locally defined Benders' decomposition data */
83typedef struct SCIP_SubproblemSolveStat SCIP_SUBPROBLEMSOLVESTAT; /**< the solving statistics of the subproblems */
84
85
86/** copy method for Benders' decomposition plugins (called when SCIP copies plugins). If there is an active Benders'
87 * decomposition, all copies are not valid. As such, there is no valid parameter that is passed to the callback
88 * function
89 *
90 * input:
91 * - scip : SCIP main data structure
92 * - benders : the Benders' decomposition itself
93 * - threadsafe : must the Benders' decomposition copy be thread safe
94 */
95#define SCIP_DECL_BENDERSCOPY(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_Bool threadsafe)
96
97/** destructor of Benders' decomposition to free user data (called when SCIP is exiting)
98 *
99 * input:
100 * - scip : SCIP main data structure
101 * - benders : the Benders' decomposition itself
102 */
103#define SCIP_DECL_BENDERSFREE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
104
105/** initialization method of Benders' decomposition (called after problem was transformed and the Benders' decomposition
106 * is active)
107 *
108 * input:
109 * - scip : SCIP main data structure
110 * - benders : the Benders' decomposition itself
111 */
112#define SCIP_DECL_BENDERSINIT(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
113
114/** deinitialization method of Benders' decomposition (called before transformed problem is freed and the Benders'
115 * decomposition is active)
116 *
117 * input:
118 * - scip : SCIP main data structure
119 * - benders : the Benders' decomposition itself
120 */
121#define SCIP_DECL_BENDERSEXIT(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
122
123/** presolving initialization method of the Benders' decomposition (called when presolving is about to begin)
124 *
125 * This function is called immediately after the auxiliary variables are created in the master problem. The callback
126 * provides the user an opportunity to add variable data to the auxiliary variables.
127 *
128 * input:
129 * - scip : SCIP main data structure
130 * - benders : the Benders' decomposition itself
131 */
132#define SCIP_DECL_BENDERSINITPRE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
133
134/** presolving deinitialization method of the Benders' decomposition (called after presolving has been finished)
135 *
136 * input:
137 * - scip : SCIP main data structure
138 * - benders : the Benders' decomposition itself
139 */
140#define SCIP_DECL_BENDERSEXITPRE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
141
142/** solving process initialization method of Benders' decomposition (called when branch and bound process is about to begin)
143 *
144 * This method is called when the presolving was finished and the branch and bound process is about to begin.
145 * The Benders' decomposition may use this call to initialize its branch and bound specific data.
146 *
147 * input:
148 * - scip : SCIP main data structure
149 * - benders : the Benders' decomposition itself
150 */
151#define SCIP_DECL_BENDERSINITSOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
152
153/** solving process deinitialization method of Benders' decomposition (called before branch and bound process data is freed)
154 *
155 * This method is called before the branch and bound process is freed.
156 * The Benders' decomposition should use this call to clean up its branch and bound data.
157 *
158 * input:
159 * - scip : SCIP main data structure
160 * - benders : the Benders' decomposition itself
161 */
162#define SCIP_DECL_BENDERSEXITSOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
163
164/** the method for creating the Benders' decomposition subproblem. This method is called during the initialisation stage
165 * (after the master problem was transformed).
166 *
167 * @note When the create subproblem callback is invoked, the mapping between the master problem and subproblem
168 * variables must be available. The create subproblem callback is invoked immediately after BENDERSINIT. So, it is
169 * possible to construct the variable mapping within the BENDERSINIT callback.
170 *
171 * This method must register the SCIP instance for the subproblem with the Benders' decomposition core by calling
172 * SCIPaddBendersSubproblem. Typically, the user must create the SCIP instances for the subproblems. These can be
173 * created within a reader or probdata and then registered with the Benders' decomposition core during the call of this
174 * callback. If there are any settings required for solving the subproblems, then they should be set here. However,
175 * some settings will be overridden by the standard solving method included in the Benders' decomposition framework.
176 * If a special solving method is desired, the user can implement the bendersSolvesubXyz callback. In this latter case,
177 * it is possible to provide a NULL pointer to SCIPaddBendersSubproblem. This will ensure that no internal solving
178 * methods available within the Benders' decomposition core are invoked during the solving process.
179 *
180 * If the user defines a subproblem solving method, then in BENDERSCREATESUB, the user must explicitly specify the
181 * subproblem type. This is necessary because the dual solutions from convex problems can be used to generate cuts.
182 * The classical Benders' optimality and feasibility cuts require that the subproblems are convex. The subproblem type
183 * is specified by calling SCIPbendersSetSubproblemType. The available subproblem types are defined in
184 * SCIP_BENDERSSUBTYPE.
185 *
186 * If the user does NOT implement a subproblem solving method, then the convexity of the problem is determined
187 * internally.
188 *
189 * input:
190 * - scip : SCIP main data structure
191 * - benders : the Benders' decomposition data structure
192 * - probnumber : the subproblem problem number
193 */
194#define SCIP_DECL_BENDERSCREATESUB(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, int probnumber)
195
196/** called before the subproblem solving loop for Benders' decomposition. The pre subproblem solve function gives the
197 * user an oppportunity to perform any global set up for the Benders' decomposition.
198 *
199 * input:
200 * - scip : SCIP main data structure
201 * - benders : the Benders' decomposition data structure
202 * - sol : the solution that will be checked in the subproblem. Can be NULL.
203 * - type : the enforcement type that called the Benders' decomposition solve.
204 * - checkint : should the integer subproblems be checked.
205 * - infeasible : flag to return whether the master problem in infeasible with respect to the added cuts
206 * - auxviol : set to TRUE only if the solution is feasible but the aux vars are violated
207 * - skipsolve : flag to return whether the current subproblem solving loop should be skipped
208 * - result : a result to be returned to the Benders' constraint handler if the solve is skipped. If the
209 * solve is not skipped, then the returned result is ignored.
210 *
211 * possible return values for *result (if more than one applies, the first in the list should be used):
212 * - SCIP_DIDNOTRUN : the subproblem was not solved in this iteration. Other decompositions will be checked.
213 * - SCIP_CONSADDED : a constraint has been added to the master problem. No other decompositions will be checked.
214 * - SCIP_SEPARATED : a cut has been added to the master problem. No other decompositions will be checked.
215 * - SCIP_FEASIBLE : feasibility of the solution is reported to SCIP. Other decompositions will be checked.
216 * - SCIP_INFEASIBLE : infeasibility of the solution is reported to SCIP. No other decompositions will be checked.
217 */
218#define SCIP_DECL_BENDERSPRESUBSOLVE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_SOL* sol,\
219 SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint, SCIP_Bool* infeasible, SCIP_Bool* auxviol, SCIP_Bool* skipsolve,\
220 SCIP_RESULT* result)
221
222/** the solving method for a convex Benders' decomposition subproblem. This call back is provided to solve problems
223 * for which the dual soluitons are used to generate Benders' decomposition cuts. In the classical Benders'
224 * decomposition implementation, this would be an LP. However, it can be any convex problem where the dual solutions
225 * are given by a single vector of reals.
226 *
227 * In the Benders' decomposition subproblem solving process, there are two solving loops. The first is where the convex
228 * subproblems, and the convex relaxations of subproblems, are solved. If no cuts are generated after this solving
229 * loop, then the second loop solves subproblems defined as CIPs. This callback is executed during the FIRST solving
230 * loop only.
231 *
232 * In the classical Benders' decomposition implementation, if the subproblems are all LPs the only the
233 * BENDERSSOLVESUBCONVEX need to be implemented. If the subproblems are MIPs, then it is useful to only implement a
234 * single SCIP instance for the subproblem and then change the variable types of the appropriate variables to
235 * CONTINUOUS for the CONVEX subproblem solve and to INTEGER for the CIP subproblem solve.
236 *
237 * The solving methods are separated so that they can be called in parallel.
238 *
239 * NOTE: The solving methods must be thread safe.
240 *
241 * This method is called from within the execution method.
242 *
243 * input:
244 * - scip : SCIP main data structure
245 * - benders : the Benders' decomposition data structure
246 * - sol : the solution that will be checked in the subproblem. Can be NULL.
247 * - probnumber : the subproblem problem number
248 * - onlyconvexcheck : flag to indicate that only the convex relaxations will be checked in this solving loop. This is
249 * a feature of the Large Neighbourhood Benders' Search
250 * - objective : variable to return the objective function value of the subproblem
251 * - result : the result from solving the subproblem
252 *
253 * possible return values for *result (if more than one applies, the first in the list should be used):
254 * - SCIP_DIDNOTRUN : the subproblem was not solved in this iteration
255 * - SCIP_FEASIBLE : the subproblem is solved and is feasible
256 * - SCIP_INFEASIBLE : the subproblem is solved and is infeasible
257 * - SCIP_UNBOUNDED : the subproblem is solved and is unbounded
258 */
259#define SCIP_DECL_BENDERSSOLVESUBCONVEX(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_SOL* sol,\
260 int probnumber, SCIP_Bool onlyconvexcheck, SCIP_Real* objective, SCIP_RESULT* result)
261
262/** the solving method for a Benders' decomposition subproblem as a CIP. This call back is provided to solve problems
263 * for which the dual solutions are not well defined. In this case, the cuts are typically generated from the primal
264 * solution to the CIP. In the classical Benders' decomposition implementation, this would be a MIP. However, it can
265 * be any CIP.
266 *
267 * In the Benders' decomposition subproblem solving process, there are two solving loops. The first is where the convex
268 * subproblems, and the convex relaxations of subproblems, are solved. If no cuts are generated after this solving
269 * loop, then the second loop solves subproblems defined as CIPs. This callback is executed during the SECOND solving
270 * loop only.
271 *
272 * The solving methods are separated so that they can be called in parallel.
273 *
274 * NOTE: The solving methods must be thread safe.
275 *
276 * This method is called from within the execution method.
277 *
278 * input:
279 * - scip : SCIP main data structure
280 * - benders : the Benders' decomposition data structure
281 * - sol : the solution that will be checked in the subproblem. Can be NULL.
282 * - probnumber : the subproblem problem number
283 * - objective : variable to return the objective function value of the subproblem
284 * - result : the result from solving the subproblem
285 *
286 * possible return values for *result (if more than one applies, the first in the list should be used):
287 * - SCIP_DIDNOTRUN : the subproblem was not solved in this iteration
288 * - SCIP_FEASIBLE : the subproblem is solved and is feasible
289 * - SCIP_INFEASIBLE : the subproblem is solved and is infeasible
290 * - SCIP_UNBOUNDED : the subproblem is solved and is unbounded
291 */
292#define SCIP_DECL_BENDERSSOLVESUB(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_SOL* sol, int probnumber,\
293 SCIP_Real* objective, SCIP_RESULT* result)
294
295/** the post-solve method for Benders' decomposition. The post-solve method is called after the subproblems have
296 * been solved but before they have been freed. After the solving of the Benders' decomposition subproblems, the
297 * subproblem solving data is freed in the SCIP_DECL_BENDERSFREESUB callback. However, it is not necessary to implement
298 * SCIP_DECL_BENDERSFREESUB.
299 *
300 * If SCIP_DECL_BENDERSFREESUB is not implemented, then the Benders' decomposition framework will perform a default
301 * freeing of the subproblems. If a subproblem is an LP, then they will be in probing mode for the subproblem
302 * solve. So the freeing process involves ending the probing mode. If the subproblem is a MIP, then the subproblem is
303 * solved by calling SCIPsolve. As such, the transformed problem must be freed after each subproblem solve.
304 *
305 * This callback provides the opportunity for the user to clean up any data structures that should not exist beyond the current
306 * iteration.
307 * The user has full access to the master and subproblems in this callback. So it is possible to construct solution for
308 * the master problem in the method.
309 * Additionally, if there are any subproblems that are infeasibility and this can not be resolved, then the it is
310 * possible to merge these subproblems into the master problem. The subproblem indices are given in the mergecands
311 * array. The merging can be perform by a user defined function or by calling SCIPmergeBendersSubproblemIntoMaster. If a
312 * subproblem was merged into the master problem, then the merged flag must be set to TRUE.
313 *
314 * input:
315 * - scip : SCIP main data structure
316 * - benders : the Benders' decomposition data structure
317 * - sol : the solution that was checked by solving the subproblems. Can be NULL.
318 * - type : the enforcement type that called the Benders' decomposition solve.
319 * - mergecands : the subproblems that are candidates for merging into the master problem, the first
320 * npriomergecands are the priority candidates (they should be merged). The remaining
321 * (nmergecands - npriomergecands) are subproblems that could be merged if desired.
322 * - npriomergecands : the number of priority merge candidates.
323 * - nmergecands : the total number of subproblems that are candidates for merging into the master problem
324 * - checkint : should the integer subproblems be checked.
325 * - infeasible : indicates whether at least one subproblem is infeasible
326 * - merged : flag to indicate whether a subproblem was merged into the master problem.
327 */
328#define SCIP_DECL_BENDERSPOSTSOLVE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_SOL* sol,\
329 SCIP_BENDERSENFOTYPE type, int* mergecands, int npriomergecands, int nmergecands, SCIP_Bool checkint,\
330 SCIP_Bool infeasible, SCIP_Bool* merged)
331
332/** frees the subproblem so that it can be resolved in the next iteration. As stated above, it is not necessary to
333 * implement this callback. If the callback is implemented, the subproblems should be freed by calling
334 * SCIPfreeTransform(). However, if the subproblems are LPs, then it could be more efficient to put the subproblem
335 * into probing mode prior to solving and then exiting the probing mode during the callback. To put the subproblem into
336 * probing mode, the subproblem must be in SCIP_STAGE_SOLVING. This can be achieved by using eventhandlers.
337 *
338 * If SCIP_DECL_BENDERSFREESUB is not implemented, then the Benders' decomposition framework will perform a default
339 * freeing of the subproblems. If a subproblem is an LP, then they will be in probing mode for the subproblem
340 * solve. So the freeing process involves ending the probing mode. If the subproblem is a MIP, then the subproblem is
341 * solved by calling SCIPsolve. As such, the transformed problem must be freed after each subproblem solve.
342 *
343 * NOTE: The freeing methods must be thread safe.
344 *
345 * input:
346 * - scip : SCIP main data structure
347 * - benders : the Benders' decomposition data structure
348 * - probnumber : the subproblem problem number
349 */
350#define SCIP_DECL_BENDERSFREESUB(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, int probnumber)
351
352/** the variable mapping from the subproblem to the master problem. It is neccessary to have a mapping between every
353 * master problem variable and its counterpart in the subproblem. This mapping must go both ways: from master to sub
354 * and sub to master.
355 *
356 * This method is called when generating the cuts. The cuts are generated by using the solution to the subproblem to
357 * eliminate a solution to the master problem.
358 *
359 * input:
360 * - scip : SCIP main data structure
361 * - benders : the Benders' decomposition structure
362 * - var : the variable for which the corresponding variable in the master or subproblem is required
363 * - mappedvar : pointer to store the variable that is mapped to var
364 * - probnumber : the number of the subproblem that the desired variable belongs to, -1 for the master problem
365 */
366#define SCIP_DECL_BENDERSGETVAR(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_VAR* var,\
367 SCIP_VAR** mappedvar, int probnumber)
368
369#ifdef __cplusplus
370}
371#endif
372
373#endif
common defines and data types used in all packages of SCIP
SCIP_BendersEnfoType
Definition: type_benders.h:45
@ SCIP_BENDERSENFOTYPE_RELAX
Definition: type_benders.h:47
@ SCIP_BENDERSENFOTYPE_LP
Definition: type_benders.h:46
@ SCIP_BENDERSENFOTYPE_CHECK
Definition: type_benders.h:49
@ SCIP_BENDERSENFOTYPE_PSEUDO
Definition: type_benders.h:48
SCIP_BendersSubStatus
Definition: type_benders.h:63
@ SCIP_BENDERSSUBSTATUS_AUXVIOL
Definition: type_benders.h:66
@ SCIP_BENDERSSUBSTATUS_UNKNOWN
Definition: type_benders.h:64
@ SCIP_BENDERSSUBSTATUS_INFEAS
Definition: type_benders.h:67
@ SCIP_BENDERSSUBSTATUS_OPTIMAL
Definition: type_benders.h:65
SCIP_BendersSubType
Definition: type_benders.h:72
@ SCIP_BENDERSSUBTYPE_NONCONVEXDIS
Definition: type_benders.h:76
@ SCIP_BENDERSSUBTYPE_CONVEXCONT
Definition: type_benders.h:73
@ SCIP_BENDERSSUBTYPE_NONCONVEXCONT
Definition: type_benders.h:75
@ SCIP_BENDERSSUBTYPE_CONVEXDIS
Definition: type_benders.h:74
@ SCIP_BENDERSSUBTYPE_UNKNOWN
Definition: type_benders.h:77
enum SCIP_BendersSubType SCIP_BENDERSSUBTYPE
Definition: type_benders.h:79
SCIP_BendersSolveLoop
Definition: type_benders.h:54
@ SCIP_BENDERSSOLVELOOP_CIP
Definition: type_benders.h:56
@ SCIP_BENDERSSOLVELOOP_CONVEX
Definition: type_benders.h:55
@ SCIP_BENDERSSOLVELOOP_USERCONVEX
Definition: type_benders.h:57
@ SCIP_BENDERSSOLVELOOP_USERCIP
Definition: type_benders.h:58
enum SCIP_BendersSolveLoop SCIP_BENDERSSOLVELOOP
Definition: type_benders.h:60
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
Definition: type_benders.h:51
enum SCIP_BendersSubStatus SCIP_BENDERSSUBSTATUS
Definition: type_benders.h:69
struct SCIP_BendersData SCIP_BENDERSDATA
Definition: type_benders.h:82
type definitions for return codes for SCIP methods
type definitions for SCIP's main datastructure