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