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 37 struct SCIP_BenderscutCut 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 }; 45 typedef struct SCIP_BenderscutCut SCIP_BENDERSCUTCUT; 46 47 /** Benders' decomposition data */ 48 struct SCIP_Benders 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 */ 168 struct SCIP_SubproblemSolveStat 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. */ 177 struct SCIP_SubproblemParams 178 { 179 SCIP_Real limits_memory; 180 SCIP_Real limits_time; 181 int cons_linear_propfreq; 182 int lp_disablecutoff; 183 int lp_scaling; 184 int prop_maxrounds; 185 int prop_maxroundsroot; 186 char lp_initalg; 187 char lp_resolvealg; 188 SCIP_Bool conflict_enable; 189 SCIP_Bool lp_alwaysgetduals; 190 SCIP_Bool misc_catchctrlc; 191 SCIP_Bool misc_scaleobj; 192 }; 193 typedef struct SCIP_SubproblemParams SCIP_SUBPROBPARAMS; 194 195 #ifdef __cplusplus 196 } 197 #endif 198 199 #endif 200