Scippy

SCIP

Solving Constraint Integer Programs

struct_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-2021 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 struct_benders.h
17  * @ingroup INTERNALAPI
18  * @brief data structures required 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_STRUCT_BENDERS_H__
25 #define __SCIP_STRUCT_BENDERS_H__
26 
27 
28 #include "scip/def.h"
29 #include "scip/type_clock.h"
30 #include "scip/type_benders.h"
31 #include "scip/type_benderscut.h"
32 
33 #ifdef __cplusplus
34 extern "C" {
35 #endif
36 
38 {
39  SCIP_VAR** vars; /**< the variables forming the cut */
40  SCIP_Real* vals; /**< the coefficients of the variables in the cut */
41  SCIP_Real lhs; /**< the left hand side of the cut */
42  SCIP_Real rhs; /**< the right hand side of the cut */
43  int nvars; /**< the number of variables in the cut */
44 };
46 
47 /** Benders' decomposition data */
49 {
50  char* name; /**< name of Benders' decomposition */
51  char* desc; /**< description of Benders' decomposition */
52  SCIP_DECL_BENDERSCOPY ((*benderscopy)); /**< copy method of Benders' decomposition or NULL if you don't want to copy your plugin into sub-SCIPs */
53  SCIP_DECL_BENDERSFREE ((*bendersfree)); /**< destructor of Benders' decomposition */
54  SCIP_DECL_BENDERSINIT ((*bendersinit)); /**< initialize Benders' decomposition */
55  SCIP_DECL_BENDERSEXIT ((*bendersexit)); /**< deinitialize Benders' decomposition */
56  SCIP_DECL_BENDERSINITPRE((*bendersinitpre));/**< presolving initialization method for Benders' decomposition */
57  SCIP_DECL_BENDERSEXITPRE((*bendersexitpre));/**< presolving deinitialization method for Benders' decomposition */
58  SCIP_DECL_BENDERSINITSOL((*bendersinitsol));/**< solving process initialization method of Benders' decomposition */
59  SCIP_DECL_BENDERSEXITSOL((*bendersexitsol));/**< solving process deinitialization method of Benders' decomposition */
60  SCIP_DECL_BENDERSGETVAR((*bendersgetvar)); /**< returns the corresponding variable from the master or subproblem */
61  SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve));/**< called prior to the subproblem solving loop */
62  SCIP_DECL_BENDERSCREATESUB((*benderscreatesub));/**< creates the Benders' decomposition subproblems */
63  SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex));/**< the solving method for convex Benders' decomposition subproblems */
64  SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub));/**< the solving method for the Benders' decomposition subproblems */
65  SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve));/**< called after the subproblems are solved. */
66  SCIP_DECL_BENDERSFREESUB((*bendersfreesub));/**< the freeing method for the Benders' decomposition subproblems */
67  SCIP_DECL_SORTPTRCOMP((*benderssubcomp)); /**< a comparator for defining the solving order of the subproblems */
68  SCIP_BENDERSDATA* bendersdata; /**< Benders' decomposition local data */
69  SCIP_CLOCK* setuptime; /**< time spend for setting up this Benders' decomposition for the next stages */
70  SCIP_CLOCK* bendersclock; /**< Benders' decomposition execution time */
71  int priority; /**< priority of the Benders' decomposition */
72  int ncalls; /**< number of times, this Benders' decomposition was called */
73  int ncutsfound; /**< number of cuts found by the Benders' decomposition */
74  int ntransferred; /**< number of cuts transferred from sub SCIP to the master SCIP */
75  SCIP_Bool active; /**< is the Benders' decomposition active? */
76  SCIP_Bool initialized; /**< is Benders' decomposition initialized? */
77  SCIP_Bool cutlp; /**< should Benders' cuts be generated for LP solutions? */
78  SCIP_Bool cutpseudo; /**< should Benders' cuts be generated for pseudo solutions? */
79  SCIP_Bool cutrelax; /**< should Benders' cuts be generated for relaxation solutions? */
80  SCIP_Bool shareauxvars; /**< should this Benders' share the highest priority Benders' auxiliary vars */
81 
82  /* additional Benders' decomposition parameters */
83  SCIP_Bool transfercuts; /**< should Benders' cuts generated in LNS heuristics be transferred to the main SCIP instance? */
84  SCIP_Bool lnscheck; /**< should Benders' decomposition be used in LNS heuristics? */
85  int lnsmaxdepth; /**< maximum depth at which the LNS check is performed */
86  int lnsmaxcalls; /**< maximum number of Benders' decomposition call in LNS heuristics */
87  int lnsmaxcallsroot; /**< maximum number of root node Benders' decomposition call in LNS heuristics */
88  SCIP_Bool cutsasconss; /**< should the transferred cuts be added as constraints? */
89  SCIP_Real subprobfrac; /**< fraction of subproblems that are solved in each iteration */
90  SCIP_Bool updateauxvarbound; /**< should the auxiliary variable lower bound be updated by solving the subproblem? */
91  SCIP_Bool auxvarsimplint; /**< if subproblem objective is integer, then set the auxiliary variables as implint */
92  SCIP_Bool cutcheck; /**< should cuts be generated while checking solutions? */
93  SCIP_Bool threadsafe; /**< has the copy been created requiring thread safety */
94  SCIP_Real solutiontol; /**< storing the tolerance for optimality in Benders' decomposition */
95  int numthreads; /**< the number of threads to use when solving the subproblem */
96  SCIP_Bool execfeasphase; /**< should a feasibility phase be executed during the root node, i.e.
97  adding slack variables to constraints to ensure feasibility */
98  SCIP_Real slackvarcoef; /**< the objective coefficient of the slack variables in the subproblem */
99  SCIP_Bool checkconsconvexity; /**< should the constraints of the subproblems be checked for convexity? */
100 
101  /* information for heuristics */
102  SCIP* sourcescip; /**< the source scip from when the Benders' was copied */
103  SCIP_Bool iscopy; /**< is the Benders' decomposition struct a copy */
104  SCIP_HASHMAP* mastervarsmap; /**< hash map for the master variables from the subscip to the master */
105 
106  /* the subproblem information */
107  SCIP** subproblems; /**< the Benders' decomposition subproblems */
108  SCIP_VAR** auxiliaryvars; /**< the auxiliary variables for the Benders' optimality cuts */
109  SCIP_PQUEUE* subprobqueue; /**< the priority queue for the subproblems */
110  SCIP_SUBPROBLEMSOLVESTAT** solvestat; /**< storing the solving statistics of all the subproblems */
111  SCIP_Real* subprobobjval; /**< the objective value of the subproblem in the current iteration */
112  SCIP_Real* bestsubprobobjval; /**< the best objective value of the subproblem */
113  SCIP_Real* subproblowerbound; /**< a lower bound on the subproblem - used for the integer cuts */
114  int naddedsubprobs; /**< subproblems added to the Benders' decomposition data */
115  int nsubproblems; /**< number of subproblems */
116  SCIP_BENDERSSUBTYPE* subprobtype; /**< the convexity type of the subproblem */
117  SCIP_Bool* subprobisconvex; /**< is the subproblem convex? This implies that the dual sol can be used for cuts */
118  SCIP_Bool* subprobisnonlinear; /**< does the subproblem contain non-linear constraints */
119  int nconvexsubprobs; /**< the number of subproblems that are convex */
120  int nnonlinearsubprobs; /**< the number of subproblems that are non-linear */
121  SCIP_Bool subprobscreated; /**< have the subproblems been created for this Benders' decomposition.
122  This flag is used when retransforming the problem.*/
123  SCIP_Bool* mastervarscont; /**< flag to indicate that the master problem variable have been converted
124  to continuous variables. */
125  SCIP_Bool* subprobsetup; /**< flag to indicate whether the subproblem has been set up. */
126  SCIP_Bool* indepsubprob; /**< flag to indicate if a subproblem is independent of the master prob */
127  SCIP_Bool* subprobenabled; /**< flag to indicate whether the subproblem is enabled */
128  int nactivesubprobs; /**< the number of active subproblems */
129  SCIP_Bool freesubprobs; /**< do the subproblems need to be freed by the Benders' decomposition core? */
130  SCIP_Bool masterisnonlinear; /**< flag to indicate whether the master problem contains non-linear constraints */
131 
132  /* cut strengthening details */
133  SCIP_SOL* corepoint; /**< the point that is separated for stabilisation */
134  SCIP_SOL* initcorepoint; /**< the point that was used to initialise the core point */
135  SCIP_Real convexmult; /**< the multiplier for the convex comb of the LP and sepa point */
136  SCIP_Real perturbeps; /**< epsilon value to perturb the LP solution */
137  int noimprovecount; /**< count of the iterations without improvement */
138  int noimprovelimit; /**< limit used to change behaviour of stabilitation */
139  SCIP_NODE* prevnode; /**< the previous node where the cut strengthening was performed */
140  SCIP_Longint prevnlpiter; /**< number of LP iters at the previous call of the cut strengthening */
141  SCIP_Real prevlowerbound; /**< the lowerbound from the previous LP enforcement iteration */
142  SCIP_Bool strengthenenabled; /**< is the core point cut strengthening enabled */
143  char strengthenintpoint; /**< where should the strengthening interior point be sourced from ('l'p relaxation, 'f'irst solution, 'i'ncumbent solution, 'r'elative interior point, vector of 'o'nes, vector of 'z'eros) */
144  SCIP_Bool strengthenround; /**< flag to indicate whether a cut strengthening round is being performed */
145  int nstrengthencuts; /**< the number of strengthened cuts found */
146  int nstrengthencalls; /**< the number of calls to the strengthening round */
147  int nstrengthenfails; /**< the number of calls to the strengthening round that fail to find cuts */
148 
149  /* solving process information */
150  int npseudosols; /**< the number of pseudo solutions checked since the last generated cut */
151  SCIP_Bool feasibilityphase; /**< is the Benders' decomposition in a feasibility phase, i.e. using slack variables */
152 
153  /* Bender's cut information */
154  SCIP_BENDERSCUT** benderscuts; /**< the available Benders' cut algorithms */
155  int nbenderscuts; /**< the number of Benders' cut algorithms */
156  int benderscutssize; /**< the size of the Benders' cuts algorithms array */
157  SCIP_Bool benderscutssorted; /**< are the Benders' cuts algorithms sorted by priority */
158  SCIP_Bool benderscutsnamessorted;/**< are the Benders' cuts algorithms sorted by name */
159 
160  /* cut storage information */
161  SCIP_BENDERSCUTCUT** storedcuts; /**< array to store the data required to form a cut/constraint */
162  int storedcutssize; /**< the size of the added cuts array */
163  int nstoredcuts; /**< the number of the added cuts */
164 
165 };
166 
167 /** statistics for solving the subproblems. Used for prioritising the solving of the subproblem */
169 {
170  int idx; /**< the index of the subproblem */
171  int ncalls; /**< the number of times this subproblems has been solved */
172  SCIP_Real avgiter; /**< the average number of LP/NLP iterations performed */
173 };
174 
175 /** parameters that are set to solve the subproblem. This will be changed from what the user inputs, so they are stored
176  * and reset after the solving loop. */
178 {
192 };
194 
195 #ifdef __cplusplus
196 }
197 #endif
198 
199 #endif
#define SCIP_DECL_BENDERSCREATESUB(x)
Definition: type_benders.h:184
SCIP_Bool strengthenround
SCIP_SOL * corepoint
SCIP_SOL * initcorepoint
SCIP_BENDERSDATA * bendersdata
SCIP_HASHMAP * mastervarsmap
#define SCIP_DECL_BENDERSINITSOL(x)
Definition: type_benders.h:142
SCIP_Bool freesubprobs
#define SCIP_DECL_BENDERSFREE(x)
Definition: type_benders.h:94
SCIP_Real prevlowerbound
SCIP_Bool strengthenenabled
#define SCIP_DECL_BENDERSINITPRE(x)
Definition: type_benders.h:123
#define SCIP_DECL_BENDERSGETVAR(x)
Definition: type_benders.h:356
SCIP_Bool cutsasconss
SCIP_CLOCK * bendersclock
SCIP_Real * bestsubprobobjval
SCIP_Bool * subprobenabled
SCIP_Bool benderscutssorted
SCIP_Bool * subprobisnonlinear
#define SCIP_DECL_BENDERSINIT(x)
Definition: type_benders.h:103
SCIP_Bool threadsafe
SCIP_Bool * indepsubprob
SCIP_Bool updateauxvarbound
SCIP_BENDERSSUBTYPE * subprobtype
SCIP_SUBPROBLEMSOLVESTAT ** solvestat
SCIP_NODE * prevnode
SCIP_Bool subprobscreated
SCIP ** subproblems
SCIP_Bool feasibilityphase
SCIP_Real * subprobobjval
enum SCIP_BendersSubType SCIP_BENDERSSUBTYPE
Definition: type_benders.h:70
SCIP_Bool checkconsconvexity
#define SCIP_DECL_BENDERSFREESUB(x)
Definition: type_benders.h:340
SCIP_Bool lnscheck
#define SCIP_DECL_BENDERSEXIT(x)
Definition: type_benders.h:112
#define SCIP_DECL_BENDERSSOLVESUB(x)
Definition: type_benders.h:282
SCIP_Bool * subprobisconvex
SCIP_BENDERSCUTCUT ** storedcuts
SCIP_Bool transfercuts
SCIP_Bool benderscutsnamessorted
SCIP_Bool masterisnonlinear
SCIP_Real solutiontol
struct SCIP_BendersData SCIP_BENDERSDATA
Definition: type_benders.h:73
#define SCIP_DECL_BENDERSSOLVESUBCONVEX(x)
Definition: type_benders.h:249
SCIP_Bool shareauxvars
#define SCIP_DECL_BENDERSCOPY(x)
Definition: type_benders.h:86
SCIP_Bool cutrelax
#define SCIP_Bool
Definition: def.h:70
char strengthenintpoint
SCIP_Bool execfeasphase
SCIP_Real slackvarcoef
SCIP_PQUEUE * subprobqueue
type definitions for Benders&#39; decomposition methods
type definitions for clocks and timing issues
SCIP_Bool cutpseudo
type definitions for Benders&#39; decomposition cut
SCIP_Longint prevnlpiter
SCIP_Bool * mastervarscont
#define SCIP_DECL_SORTPTRCOMP(x)
Definition: type_misc.h:172
#define SCIP_DECL_BENDERSEXITSOL(x)
Definition: type_benders.h:153
SCIP_Bool active
SCIP_Bool * subprobsetup
#define SCIP_Real
Definition: def.h:163
#define SCIP_Longint
Definition: def.h:148
SCIP_Bool iscopy
SCIP_Bool cutlp
#define SCIP_DECL_BENDERSPOSTSOLVE(x)
Definition: type_benders.h:318
#define SCIP_DECL_BENDERSEXITPRE(x)
Definition: type_benders.h:131
common defines and data types used in all packages of SCIP
SCIP_Bool cutcheck
SCIP_VAR ** auxiliaryvars
SCIP_Real perturbeps
SCIP_Bool initialized
SCIP_Real convexmult
SCIP_Bool auxvarsimplint
SCIP_Real * subproblowerbound
SCIP_BENDERSCUT ** benderscuts
#define SCIP_DECL_BENDERSPRESUBSOLVE(x)
Definition: type_benders.h:208
SCIP_Real subprobfrac
SCIP_CLOCK * setuptime