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