Scippy

SCIP

Solving Constraint Integer Programs

pub_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-2020 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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file pub_benders.h
17  * @ingroup PUBLICCOREAPI
18  * @brief public methods for Benders' decomposition
19  * @author Stephen J. Maher
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef __SCIP_PUB_BENDERS_H__
25 #define __SCIP_PUB_BENDERS_H__
26 
27 #include "scip/def.h"
28 #include "scip/type_benders.h"
29 #include "scip/type_benderscut.h"
30 #include "scip/type_misc.h"
31 #include "scip/type_retcode.h"
32 #include "scip/type_scip.h"
33 #include "scip/type_var.h"
34 #include "scip/type_stat.h"
35 
36 #ifdef __cplusplus
37 extern "C" {
38 #endif
39 
40 /**@addtogroup PublicBendersMethods
41  *
42  * @{
43  */
44 
45 /** compares two benderss w. r. to their priority */
47 SCIP_DECL_SORTPTRCOMP(SCIPbendersComp);
48 
49 /** comparison method for sorting benderss w.r.t. to their name */
51 SCIP_DECL_SORTPTRCOMP(SCIPbendersCompName);
52 
53 /** gets user data of Benders' decomposition */
56  SCIP_BENDERS* benders /**< Benders' decomposition */
57  );
58 
59 /** sets user data of Benders' decomposition; user has to free old data in advance! */
62  SCIP_BENDERS* benders, /**< Benders' decomposition */
63  SCIP_BENDERSDATA* bendersdata /**< new Benders' decomposition user data */
64  );
65 
66 /** gets name of Benders' decomposition */
68 const char* SCIPbendersGetName(
69  SCIP_BENDERS* benders /**< Benders' decomposition */
70  );
71 
72 /** gets description of Benders' decomposition */
74 const char* SCIPbendersGetDesc(
75  SCIP_BENDERS* benders /**< Benders' decomposition */
76  );
77 
78 /** gets priority of Benders' decomposition */
81  SCIP_BENDERS* benders /**< Benders' decomposition */
82  );
83 
84 /** gets the number of subproblems for the Benders' decomposition */
87  SCIP_BENDERS* benders /**< the Benders' decomposition data structure */
88  );
89 
90 /** returns the SCIP instance for a given subproblem */
93  SCIP_BENDERS* benders, /**< the Benders' decomposition data structure */
94  int probnumber /**< the subproblem number */
95  );
96 
97 /** gets the number of times, the Bender' decomposition was called and tried to find a violated second stage constraint */
100  SCIP_BENDERS* benders /**< Benders' decomposition */
101  );
102 
103 /** gets the number of optimality cuts found by the collection of Benders' decomposition subproblems */
106  SCIP_BENDERS* benders /**< Benders' decomposition */
107  );
108 
109 /** gets the number of cuts found from the strengthening round */
112  SCIP_BENDERS* benders /**< Benders' decomposition */
113  );
114 
115 /** gets the number of calls to the strengthening round */
118  SCIP_BENDERS* benders /**< Benders' decomposition */
119  );
120 
121 /** gets the number of calls to the strengthening round that fail */
124  SCIP_BENDERS* benders /**< Benders' decomposition */
125  );
126 
127 /** gets time in seconds used in this Benders' decomposition for setting up for next stages */
130  SCIP_BENDERS* benders /**< Benders' decomposition */
131  );
132 
133 /** gets execution time in seconds used in this Benders' decomposition */
136  SCIP_BENDERS* benders /**< Benders' decomposition */
137  );
138 
139 /** Is Benders' decomposition initialized? */
142  SCIP_BENDERS* benders /**< Benders' decomposition */
143  );
144 
145 /** returns whether the given Benders' decomposition is in use in the current problem */
148  SCIP_BENDERS* benders /**< the Benders' decomposition structure */
149  );
150 
151 /** Returns whether only the convex relaxations will be checked in this solve loop
152  * when Benders' is used in the LNS heuristics, only the convex relaxations of the master/subproblems are checked,
153  * i.e. no integer cuts are generated. In this case, then Benders' decomposition is performed under the assumption
154  * that all subproblems are convex relaxations.
155  */
158  SCIP_BENDERS* benders, /**< Benders' decomposition */
159  SCIP_Bool subscipsoff /**< flag indicating whether plugins using sub-SCIPs are deactivated */
160  );
161 
162 /** Are Benders' cuts generated from the LP solutions? */
165  SCIP_BENDERS* benders /**< Benders' decomposition */
166  );
167 
168 /** Are Benders' cuts generated from the pseudo solutions? */
171  SCIP_BENDERS* benders /**< Benders' decomposition */
172  );
173 
174 /** Are Benders' cuts generated from the relaxation solutions? */
177  SCIP_BENDERS* benders /**< Benders' decomposition */
178  );
179 
180 /** Should this Benders' use the auxiliary variables from the highest priority Benders'? */
183  SCIP_BENDERS* benders /**< Benders' decomposition */
184  );
185 
186 /** sets the subproblem setup flag */
189  SCIP_BENDERS* benders, /**< Benders' decomposition */
190  int probnumber, /**< the subproblem number */
191  SCIP_Bool issetup /**< flag to indicate whether the subproblem has been setup */
192  );
193 
194 /** returns the subproblem setup flag */
197  SCIP_BENDERS* benders, /**< Benders' decomposition */
198  int probnumber /**< the subproblem number */
199  );
200 
201 /** returns the auxiliary variable for the given subproblem */
204  SCIP_BENDERS* benders, /**< Benders' decomposition */
205  int probnumber /**< the subproblem number */
206  );
207 
208 /** returns all auxiliary variables */
211  SCIP_BENDERS* benders /**< Benders' decomposition */
212  );
213 
214 /** stores the objective function value of the subproblem for use in cut generation */
217  SCIP_BENDERS* benders, /**< Benders' decomposition */
218  int probnumber, /**< the subproblem number */
219  SCIP_Real objval /**< the objective function value for the subproblem */
220  );
221 
222 /** returns the objective function value of the subproblem for use in cut generation */
225  SCIP_BENDERS* benders, /**< Benders' decomposition */
226  int probnumber /**< the subproblem number */
227  );
228 
229 /** returns the number of cuts that have been added for storage */
232  SCIP_BENDERS* benders /**< Benders' decomposition cut */
233  );
234 
235 /** returns the data for the cuts that have been added by the Benders' cut plugin */
238  SCIP_BENDERS* benders, /**< Benders' decomposition cut */
239  int cutidx, /**< the index for the cut data that is requested */
240  SCIP_VAR*** vars, /**< the variables that have non-zero coefficients in the cut */
241  SCIP_Real** vals, /**< the coefficients of the variables in the cut */
242  SCIP_Real* lhs, /**< the left hand side of the cut */
243  SCIP_Real* rhs, /**< the right hand side of the cut */
244  int* nvars /**< the number of variables with non-zero coefficients in the cut */
245  );
246 
247 /** returns the original problem data for the cuts that have been added by the Benders' cut plugin. The stored
248  * variables and values will populate the input vars and vals arrays. Thus, memory must be allocated for the vars and
249  * vals arrays
250  */
253  SCIP_BENDERS* benders, /**< Benders' decomposition cut */
254  int cutidx, /**< the index for the cut data that is requested */
255  SCIP_VAR*** vars, /**< the variables that have non-zero coefficients in the cut */
256  SCIP_Real** vals, /**< the coefficients of the variables in the cut */
257  SCIP_Real* lhs, /**< the left hand side of the cut */
258  SCIP_Real* rhs, /**< the right hand side of the cut */
259  int* nvars, /**< the number of variables with non-zero coefficients in the cut */
260  int varssize /**< the available slots in the array */
261  );
262 
263 /*
264  * Public functions associated with Benders' cuts
265  */
266 
267 /** returns the Benders' cut of the given name, or NULL if not existing */
270  SCIP_BENDERS* benders, /**< Benders' decomposition */
271  const char* name /**< name of Benderscut' decomposition */
272  );
273 
274 
275 /** returns the array of currently available Benders' cuts; active Benders' decomposition are in the first slots of
276  * the array
277  */
280  SCIP_BENDERS* benders /**< Benders' decomposition */
281  );
282 
283 
284 /** returns the number of currently available Benders' cuts */
287  SCIP_BENDERS* benders /**< Benders' decomposition */
288  );
289 
290 /** sets the priority of a Benders' decomposition */
293  SCIP_BENDERS* benders, /**< Benders' decomposition */
294  SCIP_BENDERSCUT* benderscut, /**< Benders' cut */
295  int priority /**< new priority of the Benders' decomposition */
296  );
297 
298 /** returns whether the solution has non-zero slack variables */
301  SCIP_BENDERS* benders, /**< Benders' decomposition */
302  SCIP_Bool* activeslack /**< flag to indicate whether a slack variable is active */
303  );
304 
305 /** sets the subproblem type
306  *
307  * The subproblem types are:
308  * - Convex constraints with continuous variables
309  * - Convex constraints with discrete variables
310  * - Non-convex constraints with continuous variables
311  * - Non-convex constraints with discrete variables
312  */
315  SCIP_BENDERS* benders, /**< Benders' decomposition */
316  int probnumber, /**< the subproblem number */
317  SCIP_BENDERSSUBTYPE subprobtype /**< the subproblem type */
318  );
319 
320 /** returns the type of the subproblem
321  *
322  * This type is used to determine whether the duals of the problem can be used to generate cuts
323  */
326  SCIP_BENDERS* benders, /**< Benders' decomposition */
327  int probnumber /**< the subproblem number */
328  );
329 
330 /** sets the flag indicating whether a subproblem is convex
331  *
332  * It is possible that this can change during the solving process. One example is when the three-phase method is
333  * employed, where the first phase solves the convex relaxation of both the master and subproblems, the second phase
334  * reintroduces the integrality constraints to the master problem and the third phase then reintroduces integrality
335  * constraints to the subproblems.
336  */
339  SCIP_BENDERS* benders, /**< Benders' decomposition */
340  int probnumber, /**< the subproblem number */
341  SCIP_Bool isconvex /**< flag to indicate whether the subproblem is convex */
342  );
343 
344 /** returns whether the subproblem is convex
345  *
346  * This means that the dual solution can be used to generate cuts.
347  */
350  SCIP_BENDERS* benders, /**< Benders' decomposition */
351  int probnumber /**< the subproblem number */
352  );
353 
354 /** returns the number of subproblems that are convex */
357  SCIP_BENDERS* benders /**< Benders' decomposition */
358  );
359 
360 /** sets the flag indicating whether a subproblem contains non-linear constraints */
363  SCIP_BENDERS* benders, /**< Benders' decomposition */
364  int probnumber, /**< the subproblem number */
365  SCIP_Bool isnonlinear /**< flag to indicate whether the subproblem contains non-linear constraints */
366  );
367 
368 /** returns whether the subproblem contains non-linear constraints. */
371  SCIP_BENDERS* benders, /**< Benders' decomposition */
372  int probnumber /**< the subproblem number */
373  );
374 
375 /** returns the number of subproblems that contain non-linear constraints */
378  SCIP_BENDERS* benders /**< Benders' decomposition */
379  );
380 
381 /** sets the flag indicating whether the master problem contains non-linear constraints */
384  SCIP_BENDERS* benders, /**< Benders' decomposition */
385  SCIP_Bool isnonlinear /**< flag to indicate whether the subproblem contains non-linear constraints */
386  );
387 
388 /** returns whether the master problem contains non-linear constraints. */
391  SCIP_BENDERS* benders /**< Benders' decomposition */
392  );
393 
394 /** returns the flag indicating that Benders' decomposition is in a cut strengthening round */
397  SCIP_BENDERS* benders /**< Benders' decomposition */
398  );
399 
400 /** solves the LP of the Benders' decomposition subproblem
401  *
402  * This requires that the subproblem is in probing mode.
403  */
406  SCIP* scip, /**< the SCIP data structure */
407  SCIP_BENDERS* benders, /**< the Benders' decomposition data structure */
408  int probnumber, /**< the subproblem number */
409  SCIP_STATUS* solvestatus, /**< status of subproblem solve */
410  SCIP_Real* objective /**< optimal value of subproblem, if solved to optimality */
411  );
412 
413 /** solves the Benders' decomposition subproblem */
416  SCIP* scip, /**< the SCIP data structure */
417  SCIP_BENDERS* benders, /**< the Benders' decomposition data structure */
418  int probnumber, /**< the subproblem number */
419  SCIP_STATUS* solvestatus, /**< status of subproblem solve */
420  SCIP_Bool solvecip /**< directly solve the CIP subproblem */
421  );
422 
423 /** returns the number of cuts that have been transferred from sub SCIPs to the master SCIP */
426  SCIP_BENDERS* benders /**< the Benders' decomposition data structure */
427  );
428 
429 /** updates the lower bound for the subproblem. If the lower bound is not greater than the previously stored lowerbound,
430  * then no update occurs.
431  */
434  SCIP_BENDERS* benders, /**< Benders' decomposition */
435  int probnumber, /**< the subproblem number */
436  SCIP_Real lowerbound /**< the lower bound */
437  );
438 
439 /** returns the stored lower bound for the given subproblem */
442  SCIP_BENDERS* benders, /**< Benders' decomposition */
443  int probnumber /**< the subproblem number */
444  );
445 
446 /** sets the independent subproblem flag */
449  SCIP_BENDERS* benders, /**< Benders' decomposition */
450  int probnumber, /**< the subproblem number */
451  SCIP_Bool isindep /**< flag to indicate whether the subproblem is independent */
452  );
453 
454 /** returns whether the subproblem is independent */
457  SCIP_BENDERS* benders, /**< Benders' decomposition */
458  int probnumber /**< the subproblem number */
459  );
460 
461 /** returns whether the subproblem is enabled, i.e. the subproblem is still solved in the solving loop. */
464  SCIP_BENDERS* benders, /**< Benders' decomposition */
465  int probnumber /**< the subproblem number */
466  );
467 
468 /** @} */
469 
470 #ifdef __cplusplus
471 }
472 #endif
473 
474 #endif
SCIP_EXPORT SCIP_Bool SCIPbendersMasterIsNonlinear(SCIP_BENDERS *benders)
Definition: benders.c:6418
SCIP_EXPORT SCIP_RETCODE SCIPbendersSolveSubproblemCIP(SCIP *scip, SCIP_BENDERS *benders, int probnumber, SCIP_STATUS *solvestatus, SCIP_Bool solvecip)
Definition: benders.c:4913
SCIP_EXPORT void SCIPbendersSetData(SCIP_BENDERS *benders, SCIP_BENDERSDATA *bendersdata)
Definition: benders.c:5740
SCIP_EXPORT int SCIPbendersGetNConvexSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:6355
SCIP_EXPORT SCIP_VAR * SCIPbendersGetAuxiliaryVar(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6141
SCIP_EXPORT SCIP_Bool SCIPbendersShareAuxVars(SCIP_BENDERS *benders)
Definition: benders.c:6093
SCIP_EXPORT SCIP_RETCODE SCIPbendersSolSlackVarsActive(SCIP_BENDERS *benders, SCIP_Bool *activeslack)
Definition: benders.c:6192
type definitions for miscellaneous datastructures
SCIP_EXPORT SCIP_Bool SCIPbendersSubproblemIsIndependent(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6583
SCIP_EXPORT void SCIPbendersUpdateSubproblemLowerbound(SCIP_BENDERS *benders, int probnumber, SCIP_Real lowerbound)
Definition: benders.c:6694
SCIP_EXPORT SCIP_Bool SCIPbendersCutPseudo(SCIP_BENDERS *benders)
Definition: benders.c:6073
SCIP_EXPORT SCIP_Bool SCIPbendersOnlyCheckConvexRelax(SCIP_BENDERS *benders, SCIP_Bool subscipsoff)
Definition: benders.c:2995
SCIP_EXPORT int SCIPbendersGetNNonlinearSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:6397
#define SCIP_EXPORT
Definition: def.h:100
SCIP_EXPORT SCIP_Bool SCIPbendersSubproblemIsEnabled(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6623
SCIP_EXPORT SCIP_DECL_SORTPTRCOMP(SCIPbendersComp)
Definition: benders.c:853
SCIP_EXPORT void SCIPbendersSetSubproblemIsNonlinear(SCIP_BENDERS *benders, int probnumber, SCIP_Bool isnonlinear)
Definition: benders.c:6365
SCIP_EXPORT int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:5949
SCIP_EXPORT void SCIPbendersSetSubproblemType(SCIP_BENDERS *benders, int probnumber, SCIP_BENDERSSUBTYPE subprobtype)
Definition: benders.c:6277
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_EXPORT int SCIPbendersGetNStrengthenCalls(SCIP_BENDERS *benders)
Definition: benders.c:6001
SCIP_EXPORT SCIP_Real SCIPbendersGetSubproblemObjval(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6180
type definitions for return codes for SCIP methods
SCIP_EXPORT SCIP_Real SCIPbendersGetSubproblemLowerbound(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6713
SCIP_EXPORT SCIP_RETCODE SCIPbendersGetStoredCutData(SCIP_BENDERS *benders, int cutidx, SCIP_VAR ***vars, SCIP_Real **vals, SCIP_Real *lhs, SCIP_Real *rhs, int *nvars)
Definition: benders.c:6735
SCIP_EXPORT SCIP_Bool SCIPbendersCutRelaxation(SCIP_BENDERS *benders)
Definition: benders.c:6083
type definitions for problem statistics
SCIP_EXPORT SCIP_Real SCIPbendersGetTime(SCIP_BENDERS *benders)
Definition: benders.c:6031
SCIP_EXPORT SCIP * SCIPbendersSubproblem(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:5959
enum SCIP_BendersSubType SCIP_BENDERSSUBTYPE
Definition: type_benders.h:70
SCIP_EXPORT SCIP_BENDERSDATA * SCIPbendersGetData(SCIP_BENDERS *benders)
Definition: benders.c:5730
SCIP_EXPORT SCIP_Bool SCIPbendersCutLP(SCIP_BENDERS *benders)
Definition: benders.c:6063
SCIP_EXPORT int SCIPbendersGetNTransferredCuts(SCIP_BENDERS *benders)
Definition: benders.c:6682
SCIP_EXPORT int SCIPbendersGetNStrengthenFails(SCIP_BENDERS *benders)
Definition: benders.c:6011
type definitions for SCIP&#39;s main datastructure
SCIP_EXPORT int SCIPbendersGetNCutsFound(SCIP_BENDERS *benders)
Definition: benders.c:5981
SCIP_EXPORT SCIP_Bool SCIPbendersSubproblemIsNonlinear(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6385
struct SCIP_BendersData SCIP_BENDERSDATA
Definition: type_benders.h:73
SCIP_EXPORT SCIP_BENDERSCUT * SCIPfindBenderscut(SCIP_BENDERS *benders, const char *name)
Definition: benders.c:6898
SCIP_EXPORT SCIP_Bool SCIPbendersSubproblemIsSetup(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6531
SCIP_EXPORT void SCIPbendersSetMasterIsNonlinear(SCIP_BENDERS *benders, SCIP_Bool isnonlinear)
Definition: benders.c:6407
type definitions for problem variables
SCIP_EXPORT void SCIPbendersSetSubproblemIsConvex(SCIP_BENDERS *benders, int probnumber, SCIP_Bool isconvex)
Definition: benders.c:6320
SCIP_EXPORT SCIP_Real SCIPbendersGetSetupTime(SCIP_BENDERS *benders)
Definition: benders.c:6021
SCIP_EXPORT void SCIPbendersSetSubproblemIsIndependent(SCIP_BENDERS *benders, int probnumber, SCIP_Bool isindep)
Definition: benders.c:6543
SCIP_EXPORT SCIP_BENDERSSUBTYPE SCIPbendersGetSubproblemType(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6302
#define SCIP_Bool
Definition: def.h:70
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:58
SCIP_EXPORT SCIP_Bool SCIPbendersIsActive(SCIP_BENDERS *benders)
Definition: benders.c:2683
type definitions for Benders&#39; decomposition methods
SCIP_EXPORT void SCIPbendersSetSubproblemIsSetup(SCIP_BENDERS *benders, int probnumber, SCIP_Bool issetup)
Definition: benders.c:6518
type definitions for Benders&#39; decomposition cut
SCIP_EXPORT int SCIPbendersGetNStrengthenCutsFound(SCIP_BENDERS *benders)
Definition: benders.c:5991
SCIP_EXPORT int SCIPbendersGetNBenderscuts(SCIP_BENDERS *benders)
Definition: benders.c:6937
SCIP_EXPORT const char * SCIPbendersGetDesc(SCIP_BENDERS *benders)
Definition: benders.c:5915
#define SCIP_Real
Definition: def.h:163
SCIP_EXPORT SCIP_VAR ** SCIPbendersGetAuxiliaryVars(SCIP_BENDERS *benders)
Definition: benders.c:6153
SCIP_EXPORT SCIP_Bool SCIPbendersIsInitialized(SCIP_BENDERS *benders)
Definition: benders.c:6053
SCIP_EXPORT SCIP_RETCODE SCIPbendersSolveSubproblemLP(SCIP *scip, SCIP_BENDERS *benders, int probnumber, SCIP_STATUS *solvestatus, SCIP_Real *objective)
Definition: benders.c:4749
SCIP_EXPORT int SCIPbendersGetNStoredCuts(SCIP_BENDERS *benders)
Definition: benders.c:6725
SCIP_EXPORT SCIP_Bool SCIPbendersInStrengthenRound(SCIP_BENDERS *benders)
Definition: benders.c:6428
SCIP_EXPORT const char * SCIPbendersGetName(SCIP_BENDERS *benders)
Definition: benders.c:5905
common defines and data types used in all packages of SCIP
SCIP_EXPORT SCIP_RETCODE SCIPbendersSetBenderscutPriority(SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, int priority)
Definition: benders.c:6947
SCIP_EXPORT SCIP_BENDERSCUT ** SCIPbendersGetBenderscuts(SCIP_BENDERS *benders)
Definition: benders.c:6920
SCIP_EXPORT int SCIPbendersGetNCalls(SCIP_BENDERS *benders)
Definition: benders.c:5971
SCIP_EXPORT int SCIPbendersGetPriority(SCIP_BENDERS *benders)
Definition: benders.c:5925
SCIP_EXPORT SCIP_RETCODE SCIPbendersGetStoredCutOrigData(SCIP_BENDERS *benders, int cutidx, SCIP_VAR ***vars, SCIP_Real **vals, SCIP_Real *lhs, SCIP_Real *rhs, int *nvars, int varssize)
Definition: benders.c:6766
SCIP_EXPORT void SCIPbendersSetSubproblemObjval(SCIP_BENDERS *benders, int probnumber, SCIP_Real objval)
Definition: benders.c:6163
SCIP_EXPORT SCIP_Bool SCIPbendersSubproblemIsConvex(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6343