1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* */
/* This file is part of the program and library */
/* SCIP --- Solving Constraint Integer Programs */
/* */
/* Copyright 2002-2022 Zuse Institute Berlin */
/* */
/* Licensed under the Apache License, Version 2.0 (the "License"); */
/* you may not use this file except in compliance with the License. */
/* You may obtain a copy of the License at */
/* */
/* http://www.apache.org/licenses/LICENSE-2.0 */
/* */
/* Unless required by applicable law or agreed to in writing, software */
/* distributed under the License is distributed on an "AS IS" BASIS, */
/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
/* See the License for the specific language governing permissions and */
/* limitations under the License. */
/* */
/* You should have received a copy of the Apache-2.0 license */
/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
/* */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/**@file benders.h
* @ingroup INTERNALAPI
* @brief internal methods for Benders' decomposition
* @author Stephen J. Maher
*/
/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
#ifndef __SCIP_BENDERS_H__
#define __SCIP_BENDERS_H__
#include "blockmemshell/memory.h"
#include "scip/def.h"
#include "scip/type_benders.h"
#include "scip/type_benderscut.h"
#include "scip/type_dcmp.h"
#include "scip/type_message.h"
#include "scip/type_misc.h"
#include "scip/type_result.h"
#include "scip/type_retcode.h"
#include "scip/type_scip.h"
#include "scip/type_set.h"
#include "scip/type_sol.h"
#include "scip/type_stat.h"
#include "scip/type_var.h"
#ifdef __cplusplus
extern "C" {
#endif
/** copies the given Benders' decomposition to a new scip */
SCIP_RETCODE SCIPbendersCopyInclude(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_SET* sourceset, /**< SCIP_SET of SCIP to copy from */
SCIP_SET* targetset, /**< SCIP_SET of SCIP to copy to */
SCIP_HASHMAP* varmap, /**< a hashmap to store the mapping of source variables corresponding
* target variables; must not be NULL */
SCIP_Bool copysubproblems, /**< must the subproblems be copied with the Benders' decomposition copy */
SCIP_Bool* valid /**< was the copying process valid? */
);
/** creates a Benders' decomposition */
SCIP_RETCODE SCIPbendersCreate(
SCIP_BENDERS** benders, /**< pointer to Benders' decomposition data structure */
SCIP_SET* set, /**< global SCIP settings */
SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
const char* name, /**< name of Benders' decomposition */
const char* desc, /**< description of Benders' decomposition */
int priority, /**< priority of the Benders' decomposition */
SCIP_Bool cutlp, /**< should Benders' cuts be generated for LP solutions */
SCIP_Bool cutpseudo, /**< should Benders' cuts be generated for pseudo solutions */
SCIP_Bool cutrelax, /**< should Benders' cuts be generated for relaxation solutions */
SCIP_Bool shareauxvars, /**< should this Benders' use the highest priority Benders aux vars */
SCIP_DECL_BENDERSCOPY ((*benderscopy)), /**< copy method of Benders' decomposition or NULL if you don't want to copy your plugin into sub-SCIPs */
SCIP_DECL_BENDERSFREE ((*bendersfree)), /**< destructor of Benders' decomposition */
SCIP_DECL_BENDERSINIT ((*bendersinit)), /**< initialize Benders' decomposition */
SCIP_DECL_BENDERSEXIT ((*bendersexit)), /**< deinitialize Benders' decomposition */
SCIP_DECL_BENDERSINITPRE((*bendersinitpre)),/**< presolving initialization method for Benders' decomposition */
SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)),/**< presolving deinitialization method for Benders' decomposition */
SCIP_DECL_BENDERSINITSOL((*bendersinitsol)),/**< solving process initialization method of Benders' decomposition */
SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)),/**< solving process deinitialization method of Benders' decomposition */
SCIP_DECL_BENDERSGETVAR((*bendersgetvar)),/**< returns the master variable for a given subproblem variable */
SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)),/**< creates a Benders' decomposition subproblem */
SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)),/**< called prior to the subproblem solving loop */
SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)),/**< the solving method for convex Benders' decomposition subproblems */
SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)),/**< the solving method for the Benders' decomposition subproblems */
SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)),/**< called after the subproblems are solved. */
SCIP_DECL_BENDERSFREESUB((*bendersfreesub)),/**< the freeing method for the Benders' decomposition subproblems */
SCIP_BENDERSDATA* bendersdata /**< Benders' decomposition data */
);
/** calls destructor and frees memory of Benders' decomposition */
SCIP_RETCODE SCIPbendersFree(
SCIP_BENDERS** benders, /**< pointer to Benders' decomposition data structure */
SCIP_SET* set /**< global SCIP settings */
);
/** initializes Benders' decomposition */
SCIP_RETCODE SCIPbendersInit(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_SET* set /**< global SCIP settings */
);
/** calls exit method of Benders' decomposition */
SCIP_RETCODE SCIPbendersExit(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_SET* set /**< global SCIP settings */
);
/** informs the Benders' decomposition that the presolving process is being started */
SCIP_RETCODE SCIPbendersInitpre(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_SET* set, /**< global SCIP settings */
SCIP_STAT* stat /**< dynamic problem statistics */
);
/** informs the Benders' decomposition that the presolving process has completed */
SCIP_RETCODE SCIPbendersExitpre(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_SET* set, /**< global SCIP settings */
SCIP_STAT* stat /**< dynamic problem statistics */
);
/** informs Benders' decomposition that the branch and bound process is being started */
SCIP_RETCODE SCIPbendersInitsol(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_SET* set /**< global SCIP settings */
);
/** informs Benders' decomposition that the branch and bound process data is being freed */
SCIP_RETCODE SCIPbendersExitsol(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_SET* set /**< global SCIP settings */
);
/** activates Benders' decomposition such that it is called in LP solving loop */
SCIP_RETCODE SCIPbendersActivate(
SCIP_BENDERS* benders, /**< the Benders' decomposition structure */
SCIP_SET* set, /**< global SCIP settings */
int nsubproblems /**< the number subproblems used in this decomposition */
);
/** deactivates Benders' decomposition such that it is no longer called in LP solving loop */
SCIP_RETCODE SCIPbendersDeactivate(
SCIP_BENDERS* benders, /**< the Benders' decomposition structure */
SCIP_SET* set /**< global SCIP settings */
);
/** enables or disables all clocks of Benders' decomposition depending on the value of the flag */
void SCIPbendersEnableOrDisableClocks(
SCIP_BENDERS* benders, /**< the Benders' decomposition for which all clocks should be enabled or disabled */
SCIP_Bool enable /**< should the clocks of the Benders' decomposition be enabled? */
);
/** solves the subproblem using the current master problem solution.
*
* The checkint flag indicates whether integer feasibility can be assumed. If it is not assumed, i.e. checkint ==
* FALSE, then only the convex relaxations of the subproblems are solved. If integer feasibility is assumed, i.e.
* checkint == TRUE, then the convex relaxations and the full CIP are solved to generate Benders' cuts and check
* solution feasibility.
*/
SCIP_RETCODE SCIPbendersExec(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_SET* set, /**< global SCIP settings */
SCIP_SOL* sol, /**< primal CIP solution */
SCIP_RESULT* result, /**< result of the pricing process */
SCIP_Bool* infeasible, /**< is the master problem infeasible with respect to the Benders' cuts? */
SCIP_Bool* auxviol, /**< set to TRUE only if the solution is feasible but the aux vars are violated */
SCIP_BENDERSENFOTYPE type, /**< the type of solution being enforced */
SCIP_Bool checkint /**< should the integer solution be checked by the subproblems */
);
/** Executes the subproblem solving process. */
SCIP_RETCODE SCIPbendersExecSubproblemSolve(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_SET* set, /**< global SCIP settings */
SCIP_SOL* sol, /**< primal CIP solution */
int probnum, /**< the subproblem number */
SCIP_BENDERSSOLVELOOP solveloop, /**< the solve loop iteration. The first iter is for LP, the second for IP */
SCIP_Bool enhancement, /**< is the solve performed as part of an enhancement? */
SCIP_Bool* solved, /**< flag to indicate whether the subproblem was solved */
SCIP_Bool* infeasible, /**< returns whether the current subproblem is infeasible */
SCIP_BENDERSENFOTYPE type /**< the enforcement type calling this function */
);
/** sets up the subproblem using the solution to the master problem */
SCIP_RETCODE SCIPbendersSetupSubproblem(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_SET* set, /**< global SCIP settings */
SCIP_SOL* sol, /**< primal CIP solution */
int probnumber, /**< the subproblem number */
SCIP_BENDERSENFOTYPE type /**< the enforcement type calling this function */
);
/** Solve a Benders' decomposition subproblems. This will either call the user defined method or the generic solving
* methods. If the generic method is called, then the subproblem must be set up before calling this method. */
SCIP_RETCODE SCIPbendersSolveSubproblem(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_SET* set, /**< global SCIP settings */
SCIP_SOL* sol, /**< primal CIP solution, can be NULL */
int probnumber, /**< the subproblem number */
SCIP_Bool* infeasible, /**< returns whether the current subproblem is infeasible */
SCIP_Bool solvecip, /**< directly solve the CIP subproblem */
SCIP_Real* objective /**< the objective function value of the subproblem, can be NULL */
);
/** frees the subproblems */
SCIP_RETCODE SCIPbendersFreeSubproblem(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_SET* set, /**< global SCIP settings */
int probnumber /**< the subproblem number */
);
/** compares the subproblem objective value with the auxiliary variable value for optimality */
SCIP_Bool SCIPbendersSubproblemIsOptimal(
SCIP_BENDERS* benders, /**< the benders' decomposition structure */
SCIP_SET* set, /**< global SCIP settings */
SCIP_SOL* sol, /**< primal CIP solution */
int probnumber /**< the subproblem number */
);
/** returns the value of the auxiliary variable value in a master problem solution */
SCIP_Real SCIPbendersGetAuxiliaryVarVal(
SCIP_BENDERS* benders, /**< the benders' decomposition structure */
SCIP_SET* set, /**< global SCIP settings */
SCIP_SOL* sol, /**< primal CIP solution */
int probnumber /**< the subproblem number */
);
/** Solves an independent subproblem to identify its lower bound. The lower bound is then used to update the bound on
* the auxiliary variable.
*/
SCIP_RETCODE SCIPbendersComputeSubproblemLowerbound(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_SET* set, /**< global SCIP settings */
int probnumber, /**< the subproblem to be evaluated */
SCIP_Real* lowerbound, /**< the lowerbound for the subproblem */
SCIP_Bool* infeasible /**< was the subproblem found to be infeasible? */
);
/** merges a subproblem into the master problem. This process just adds a copy of the subproblem variables and
* constraints to the master problem, but keeps the subproblem stored in the Benders' decomposition data structure.
* The reason for keeping the subproblem available is for when it is queried for solutions after the problem is solved.
*
* Once the subproblem is merged into the master problem, then the subproblem is flagged as disabled. This means that
* it will not be solved in the subsequent subproblem solving loops.
*
* The associated auxiliary variables are kept in the master problem. The objective function of the merged subproblem
* is added as an underestimator constraint.
*/
SCIP_RETCODE SCIPbendersMergeSubproblemIntoMaster(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_SET* set, /**< global SCIP settings */
SCIP_HASHMAP* varmap, /**< a hashmap to store the mapping of subproblem variables corresponding
* to the newly created master variables, or NULL */
SCIP_HASHMAP* consmap, /**< a hashmap to store the mapping of subproblem constraints to the
corresponding newly created constraints, or NULL */
int probnumber /**< the number of the subproblem that will be merged into the master problem*/
);
/** Applies a Benders' decomposition to the problem based upon the decomposition selected from the storage */
extern
SCIP_RETCODE SCIPbendersApplyDecomposition(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_SET* set, /**< global SCIP settings */
SCIP_DECOMP* decomp /**< the decomposition to apply to the problem */
);
/** sets priority of Benders' decomposition */
void SCIPbendersSetPriority(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_SET* set, /**< global SCIP settings */
int priority /**< new priority of the Benders' decomposition */
);
/** sets copy callback of Benders' decomposition */
void SCIPbendersSetCopy(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_DECL_BENDERSCOPY ((*benderscopy)) /**< copy callback of Benders' decomposition */
);
/** sets destructor callback of Benders' decomposition */
void SCIPbendersSetFree(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_DECL_BENDERSFREE ((*bendersfree)) /**< destructor of Benders' decomposition */
);
/** sets initialization callback of Benders' decomposition */
void SCIPbendersSetInit(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_DECL_BENDERSINIT((*bendersinit)) /**< initialize Benders' decomposition */
);
/** sets deinitialization callback of Benders' decomposition */
void SCIPbendersSetExit(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_DECL_BENDERSEXIT((*bendersexit)) /**< deinitialize Benders' decomposition */
);
/** sets presolving initialization callback of Benders' decomposition */
void SCIPbendersSetInitpre(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_DECL_BENDERSINITPRE((*bendersinitpre))/**< initialize presolving for Benders' decomposition */
);
/** sets presolving deinitialization callback of Benders' decomposition */
void SCIPbendersSetExitpre(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_DECL_BENDERSEXITPRE((*bendersexitpre))/**< deinitialize presolving for Benders' decomposition */
);
/** sets solving process initialization callback of Benders' decomposition */
void SCIPbendersSetInitsol(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_DECL_BENDERSINITSOL((*bendersinitsol))/**< solving process initialization callback of Benders' decomposition */
);
/** sets solving process deinitialization callback of Benders' decomposition */
void SCIPbendersSetExitsol(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_DECL_BENDERSEXITSOL((*bendersexitsol))/**< solving process deinitialization callback of Benders' decomposition */
);
/** sets the pre subproblem solve callback of Benders' decomposition */
void SCIPbendersSetPresubsolve(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve))/**< called prior to the subproblem solving loop */
);
/** sets convex solve callback of Benders' decomposition */
void SCIPbendersSetSolvesubconvex(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex))/**< solving method for the convex Benders' decomposition subproblem */
);
/** sets solve callback of Benders' decomposition */
void SCIPbendersSetSolvesub(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub))/**< solving method for a Benders' decomposition subproblem */
);
/** sets post-solve callback of Benders' decomposition */
void SCIPbendersSetPostsolve(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve))/**< solving process deinitialization callback of Benders' decomposition */
);
/** sets post-solve callback of Benders' decomposition */
void SCIPbendersSetSubproblemComp(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_DECL_SORTPTRCOMP((*benderssubcomp)) /**< a comparator for defining the solving order of the subproblems */
);
/** sets free subproblem callback of Benders' decomposition */
void SCIPbendersSetFreesub(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_DECL_BENDERSFREESUB((*bendersfreesub))/**< the freeing callback for the subproblem */
);
/** Returns the corresponding master or subproblem variable for the given variable.
* This provides a call back for the variable mapping between the master and subproblems. */
SCIP_RETCODE SCIPbendersGetVar(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_SET* set, /**< global SCIP settings */
SCIP_VAR* var, /**< the variable for which the corresponding variable is desired */
SCIP_VAR** mappedvar, /**< the variable that is mapped to var */
int probnumber /**< the problem number for the desired variable, -1 for the master problem */
);
/** adds a subproblem to the Benders' decomposition data */
SCIP_RETCODE SCIPbendersAddSubproblem(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP* subproblem /**< subproblem to be added to the data storage */
);
/** removes the subproblems from the Benders' decomposition data */
void SCIPbendersRemoveSubproblems(
SCIP_BENDERS* benders /**< Benders' decomposition */
);
/** Sets whether the subproblem is enabled or disabled. A subproblem is disabled if it has been merged into the master
* problem.
*/
void SCIPbendersSetSubproblemEnabled(
SCIP_BENDERS* benders, /**< Benders' decomposition */
int probnumber, /**< the subproblem number */
SCIP_Bool enabled /**< flag to indicate whether the subproblem is enabled */
);
/** changes all of the master problem variables in the given subproblem to continuous */
SCIP_RETCODE SCIPbendersChgMastervarsToCont(
SCIP_BENDERS* benders, /**< Benders' decomposition */
SCIP_SET* set, /**< global SCIP settings */
int probnumber /**< the subproblem number */
);
/** sets a flag to indicate whether the master variables are all set to continuous */
SCIP_RETCODE SCIPbendersSetMastervarsCont(
SCIP_BENDERS* benders, /**< Benders' decomposition */
int probnumber, /**< the subproblem number */
SCIP_Bool arecont /**< flag to indicate whether the master problem variables are continuous */
);
/** returns whether the master variables are all set to continuous */
SCIP_Bool SCIPbendersGetMastervarsCont(
SCIP_BENDERS* benders, /**< Benders' decomposition */
int probnumber /**< the subproblem number */
);
/** adds the data for the generated cuts to the Benders' cut storage */
SCIP_RETCODE SCIPbendersStoreCut(
SCIP_BENDERS* benders, /**< Benders' decomposition cut */
SCIP_SET* set, /**< global SCIP settings */
SCIP_VAR** vars, /**< the variables that have non-zero coefficients in the cut */
SCIP_Real* vals, /**< the coefficients of the variables in the cut */
SCIP_Real lhs, /**< the left hand side of the cut */
SCIP_Real rhs, /**< the right hand side of the cut */
int nvars /**< the number of variables with non-zero coefficients in the cut */
);
/** inserts a Benders' cut algorithm plugin into the Benders' cuts plugin list */
SCIP_RETCODE SCIPbendersIncludeBenderscut(
SCIP_BENDERS* benders, /**< Benders' decomposition structure */
SCIP_SET* set, /**< global SCIP settings */
SCIP_BENDERSCUT* benderscut /**< Benders' cut */
);
/** sets the Benders' cuts sorted flags in the Benders' decomposition */
void SCIPbendersSetBenderscutsSorted(
SCIP_BENDERS* benders, /**< Benders' decomposition structure */
SCIP_Bool sorted /**< the value to set the sorted flag to */
);
/** sorts Benders' decomposition cuts by priorities */
void SCIPbendersSortBenderscuts(
SCIP_BENDERS* benders /**< Benders' decomposition */
);
/** sorts Benders' decomposition cuts by name */
void SCIPbendersSortBenderscutsName(
SCIP_BENDERS* benders /**< Benders' decomposition */
);
#ifdef __cplusplus
}
#endif
#endif