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_heur.h 26 * @ingroup INTERNALAPI 27 * @brief datastructures for primal heuristics 28 * @author Tobias Achterberg 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #ifndef __SCIP_STRUCT_HEUR_H__ 34 #define __SCIP_STRUCT_HEUR_H__ 35 36 37 #include "scip/def.h" 38 #include "scip/type_clock.h" 39 #include "scip/type_heur.h" 40 41 #ifdef __cplusplus 42 extern "C" { 43 #endif 44 45 46 struct SCIP_DivesetStats 47 { 48 SCIP_Longint nlpiterations; /**< LP iterations used in this dive set */ 49 SCIP_Longint nlps; /**< the number of LPs solved by this dive set */ 50 SCIP_Longint totaldepth; /**< the total depth used in this dive set */ 51 SCIP_Longint totalsoldepth; /**< the sum of depths at which this dive set found solutions */ 52 SCIP_Longint totalnnodes; /**< the total number of probing nodes explored by this dive set */ 53 SCIP_Longint totalnbacktracks; /**< the total number of backtracks during the execution of this dive set */ 54 SCIP_Longint nsolsfound; /**< the total number of solutions found */ 55 SCIP_Longint nbestsolsfound; /**< the total number of best solutions found */ 56 SCIP_Longint nconflictsfound; /**< the total number of added conflicts during the execution of this dive set */ 57 int mindepth; /**< the minimum depth reached by all executions of the dive set */ 58 int maxdepth; /**< the maximum depth reached by an execution of the dive set */ 59 int minsoldepth; /**< the minimum depth at which this dive set found a solution */ 60 int maxsoldepth; /**< the maximum depth at which this dive set found a solution */ 61 int ncalls; /**< the total number of calls of this dive set */ 62 int nsolcalls; /**< number of calls with a leaf solution */ 63 }; 64 typedef struct SCIP_DivesetStats SCIP_DIVESETSTATS; 65 66 /** common settings for diving heuristics */ 67 struct SCIP_Diveset 68 { 69 SCIP_HEUR* heur; /**< the heuristic to which this dive set belongs */ 70 char* name; /**< name of dive controller, in case that a heuristic has several */ 71 SCIP_SOL* sol; /**< working solution of this dive set */ 72 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */ 73 SCIP_DIVESETSTATS* divesetstats[4]; /**< statistics for individual contexts */ 74 SCIP_Real minreldepth; /**< minimal relative depth to start diving */ 75 SCIP_Real maxreldepth; /**< maximal relative depth to start diving */ 76 SCIP_Real maxlpiterquot; /**< maximal fraction of diving LP iterations compared to node LP iterations */ 77 SCIP_Real maxdiveubquot; /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) 78 * where diving is performed (0.0: no limit) */ 79 SCIP_Real maxdiveavgquot; /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) 80 * where diving is performed (0.0: no limit) */ 81 SCIP_Real maxdiveubquotnosol; /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */ 82 SCIP_Real maxdiveavgquotnosol;/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */ 83 SCIP_Real lpresolvedomchgquot;/**< percentage of immediate domain changes during probing to trigger LP resolve */ 84 int lpsolvefreq; /**< LP solve frequency for diving heuristics */ 85 int maxlpiterofs; /**< additional number of allowed LP iterations */ 86 unsigned int initialseed; /**< initial seed for the random number generator */ 87 SCIP_Bool backtrack; /**< use one level of backtracking if infeasibility is encountered? */ 88 SCIP_Bool onlylpbranchcands; /**< should only LP branching candidates be considered instead of the slower but 89 * more general constraint handler diving variable selection? */ 90 SCIP_Bool ispublic; /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */ 91 SCIP_DIVETYPE divetypemask; /**< bit mask that represents the supported dive types by this dive set */ 92 SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)); /**< method for candidate score and rounding direction */ 93 SCIP_DECL_DIVESETAVAILABLE((*divesetavailable)); /**< callback to check availability of dive set at the current stage, or NULL if always available */ 94 }; 95 96 /** primal heuristics data */ 97 struct SCIP_Heur 98 { 99 SCIP_Longint ncalls; /**< number of times, this heuristic was called */ 100 SCIP_Longint nsolsfound; /**< number of feasible primal solutions found so far by this heuristic */ 101 SCIP_Longint nbestsolsfound; /**< number of new best primal CIP solutions found so far by this heuristic */ 102 char* name; /**< name of primal heuristic */ 103 char* desc; /**< description of primal heuristic */ 104 SCIP_DECL_HEURCOPY ((*heurcopy)); /**< copy method of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */ 105 SCIP_DECL_HEURFREE ((*heurfree)); /**< destructor of primal heuristic */ 106 SCIP_DECL_HEURINIT ((*heurinit)); /**< initialize primal heuristic */ 107 SCIP_DECL_HEUREXIT ((*heurexit)); /**< deinitialize primal heuristic */ 108 SCIP_DECL_HEURINITSOL ((*heurinitsol)); /**< solving process initialization method of primal heuristic */ 109 SCIP_DECL_HEUREXITSOL ((*heurexitsol)); /**< solving process deinitialization method of primal heuristic */ 110 SCIP_DECL_HEUREXEC ((*heurexec)); /**< execution method of primal heuristic */ 111 SCIP_HEURDATA* heurdata; /**< primal heuristics local data */ 112 SCIP_DIVESET** divesets; /**< array of diving controllers of this heuristic */ 113 SCIP_CLOCK* setuptime; /**< time spend for setting up this heuristic for the next stages */ 114 SCIP_CLOCK* heurclock; /**< heuristic execution time */ 115 int priority; /**< priority of the primal heuristic */ 116 int freq; /**< frequency for calling primal heuristic */ 117 int freqofs; /**< frequency offset for calling primal heuristic */ 118 int maxdepth; /**< maximal depth level to call heuristic at (-1: no limit) */ 119 int delaypos; /**< position in the delayed heuristics queue, or -1 if not delayed */ 120 int ndivesets; /**< number of diving controllers of this heuristic */ 121 SCIP_HEURTIMING timingmask; /**< positions in the node solving loop where heuristic should be executed */ 122 SCIP_Bool usessubscip; /**< does the heuristic use a secondary SCIP instance? */ 123 SCIP_Bool initialized; /**< is primal heuristic initialized? */ 124 char dispchar; /**< display character of primal heuristic */ 125 }; 126 127 /** variable graph data structure to determine breadth-first distances between variables 128 * 129 * the variable graph internally stores a mapping from the variables to the constraints in which they appear. 130 * 131 * @see PublicVariableGraphMethods for available methods 132 */ 133 struct SCIP_VGraph 134 { 135 SCIP_CONS*** varconss; /**< constraints of each variable */ 136 SCIP_HASHTABLE* visitedconss; /**< hash table that keeps a record of visited constraints during breadth-first search */ 137 int* nvarconss; /**< number of constraints for each variable */ 138 int* varconssize; /**< size array for every varconss entry */ 139 }; 140 141 #ifdef __cplusplus 142 } 143 #endif 144 145 #endif 146