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 46 struct SCIP_BenderscutCut 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 }; 54 typedef struct SCIP_BenderscutCut SCIP_BENDERSCUTCUT; 55 56 /** Benders' decomposition data */ 57 struct SCIP_Benders 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 SCIP_NLPPARAM nlpparam; /**< parameters for NLP solves */ 111 112 /* information for heuristics */ 113 SCIP* sourcescip; /**< the source scip from when the Benders' was copied */ 114 SCIP_Bool iscopy; /**< is the Benders' decomposition struct a copy */ 115 SCIP_HASHMAP* mastervarsmap; /**< hash map for the master variables from the subscip to the master */ 116 117 /* the subproblem information */ 118 SCIP** subproblems; /**< the Benders' decomposition subproblems */ 119 SCIP_VAR** auxiliaryvars; /**< the auxiliary variables for the Benders' optimality cuts */ 120 SCIP_PQUEUE* subprobqueue; /**< the priority queue for the subproblems */ 121 SCIP_SUBPROBLEMSOLVESTAT** solvestat; /**< storing the solving statistics of all the subproblems */ 122 SCIP_Real* subprobobjval; /**< the objective value of the subproblem in the current iteration */ 123 SCIP_Real* bestsubprobobjval; /**< the best objective value of the subproblem */ 124 SCIP_Real* subproblowerbound; /**< a lower bound on the subproblem - used for the integer cuts */ 125 int naddedsubprobs; /**< subproblems added to the Benders' decomposition data */ 126 int nsubproblems; /**< number of subproblems */ 127 SCIP_BENDERSSUBTYPE* subprobtype; /**< the convexity type of the subproblem */ 128 SCIP_Bool* subprobisconvex; /**< is the subproblem convex? This implies that the dual sol can be used for cuts */ 129 SCIP_Bool* subprobisnonlinear; /**< does the subproblem contain non-linear constraints */ 130 int nconvexsubprobs; /**< the number of subproblems that are convex */ 131 int nnonlinearsubprobs; /**< the number of subproblems that are non-linear */ 132 SCIP_Bool subprobscreated; /**< have the subproblems been created for this Benders' decomposition. 133 This flag is used when retransforming the problem.*/ 134 SCIP_Bool* mastervarscont; /**< flag to indicate that the master problem variable have been converted 135 to continuous variables. */ 136 SCIP_Bool* subprobsetup; /**< flag to indicate whether the subproblem has been set up. */ 137 SCIP_Bool* indepsubprob; /**< flag to indicate if a subproblem is independent of the master prob */ 138 SCIP_Bool* subprobenabled; /**< flag to indicate whether the subproblem is enabled */ 139 int nactivesubprobs; /**< the number of active subproblems */ 140 SCIP_Bool freesubprobs; /**< do the subproblems need to be freed by the Benders' decomposition core? */ 141 SCIP_Bool masterisnonlinear; /**< flag to indicate whether the master problem contains non-linear constraints */ 142 143 /* cut strengthening details */ 144 SCIP_SOL* corepoint; /**< the point that is separated for stabilisation */ 145 SCIP_SOL* initcorepoint; /**< the point that was used to initialise the core point */ 146 SCIP_Real convexmult; /**< the multiplier for the convex comb of the LP and sepa point */ 147 SCIP_Real perturbeps; /**< epsilon value to perturb the LP solution */ 148 int noimprovecount; /**< count of the iterations without improvement */ 149 int noimprovelimit; /**< limit used to change behaviour of stabilitation */ 150 SCIP_NODE* prevnode; /**< the previous node where the cut strengthening was performed */ 151 SCIP_Longint prevnlpiter; /**< number of LP iters at the previous call of the cut strengthening */ 152 SCIP_Real prevlowerbound; /**< the lowerbound from the previous LP enforcement iteration */ 153 SCIP_Bool strengthenenabled; /**< is the core point cut strengthening enabled */ 154 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) */ 155 SCIP_Bool strengthenround; /**< flag to indicate whether a cut strengthening round is being performed */ 156 int nstrengthencuts; /**< the number of strengthened cuts found */ 157 int nstrengthencalls; /**< the number of calls to the strengthening round */ 158 int nstrengthenfails; /**< the number of calls to the strengthening round that fail to find cuts */ 159 160 /* solving process information */ 161 int npseudosols; /**< the number of pseudo solutions checked since the last generated cut */ 162 SCIP_Bool feasibilityphase; /**< is the Benders' decomposition in a feasibility phase, i.e. using slack variables */ 163 164 /* Bender's cut information */ 165 SCIP_BENDERSCUT** benderscuts; /**< the available Benders' cut algorithms */ 166 int nbenderscuts; /**< the number of Benders' cut algorithms */ 167 int benderscutssize; /**< the size of the Benders' cuts algorithms array */ 168 SCIP_Bool benderscutssorted; /**< are the Benders' cuts algorithms sorted by priority */ 169 SCIP_Bool benderscutsnamessorted;/**< are the Benders' cuts algorithms sorted by name */ 170 171 /* cut storage information */ 172 SCIP_BENDERSCUTCUT** storedcuts; /**< array to store the data required to form a cut/constraint */ 173 int storedcutssize; /**< the size of the added cuts array */ 174 int nstoredcuts; /**< the number of the added cuts */ 175 176 }; 177 178 /** statistics for solving the subproblems. Used for prioritising the solving of the subproblem */ 179 struct SCIP_SubproblemSolveStat 180 { 181 int idx; /**< the index of the subproblem */ 182 int ncalls; /**< the number of times this subproblems has been solved */ 183 SCIP_Real avgiter; /**< the average number of LP/NLP iterations performed */ 184 }; 185 186 /** parameters that are set to solve the subproblem. This will be changed from what the user inputs, so they are stored 187 * and reset after the solving loop. */ 188 struct SCIP_SubproblemParams 189 { 190 SCIP_Real limits_memory; 191 SCIP_Real limits_time; 192 int cons_linear_propfreq; 193 int lp_disablecutoff; 194 int lp_scaling; 195 int prop_maxrounds; 196 int prop_maxroundsroot; 197 char lp_initalg; 198 char lp_resolvealg; 199 SCIP_Bool conflict_enable; 200 SCIP_Bool lp_alwaysgetduals; 201 SCIP_Bool misc_catchctrlc; 202 SCIP_Bool misc_scaleobj; 203 }; 204 typedef struct SCIP_SubproblemParams SCIP_SUBPROBPARAMS; 205 206 #ifdef __cplusplus 207 } 208 #endif 209 210 #endif 211