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 heur.h 26 * @ingroup INTERNALAPI 27 * @brief internal methods 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_HEUR_H__ 34 #define __SCIP_HEUR_H__ 35 36 37 #include "scip/def.h" 38 #include "blockmemshell/memory.h" 39 #include "scip/type_retcode.h" 40 #include "scip/type_result.h" 41 #include "scip/type_set.h" 42 #include "scip/type_primal.h" 43 #include "scip/type_heur.h" 44 #include "scip/pub_heur.h" 45 #include "scip/stat.h" 46 47 #ifdef __cplusplus 48 extern "C" { 49 #endif 50 51 /** create a set of diving heuristic settings */ 52 SCIP_RETCODE SCIPdivesetCreate( 53 SCIP_DIVESET** divesetptr, /**< pointer to the freshly created diveset */ 54 SCIP_HEUR* heur, /**< the heuristic to which this dive setting belongs */ 55 const char* name, /**< name for the diveset, or NULL if the name of the heuristic should be used */ 56 SCIP_SET* set, /**< global SCIP settings */ 57 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 58 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */ 59 SCIP_Real minreldepth, /**< minimal relative depth to start diving */ 60 SCIP_Real maxreldepth, /**< maximal relative depth to start diving */ 61 SCIP_Real maxlpiterquot, /**< maximal fraction of diving LP iterations compared to node LP iterations */ 62 SCIP_Real maxdiveubquot, /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) 63 * where diving is performed (0.0: no limit) */ 64 SCIP_Real maxdiveavgquot, /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) 65 * where diving is performed (0.0: no limit) */ 66 SCIP_Real maxdiveubquotnosol, /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */ 67 SCIP_Real maxdiveavgquotnosol,/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */ 68 SCIP_Real lpresolvedomchgquot,/**< percentage of immediate domain changes during probing to trigger LP resolve */ 69 int lpsolvefreq, /**< LP solve frequency for (0: only if enough domain reductions are found by propagation)*/ 70 int maxlpiterofs, /**< additional number of allowed LP iterations */ 71 unsigned int initialseed, /**< initial seed for random number generation */ 72 SCIP_Bool backtrack, /**< use one level of backtracking if infeasibility is encountered? */ 73 SCIP_Bool onlylpbranchcands, /**< should only LP branching candidates be considered instead of the slower but 74 * more general constraint handler diving variable selection? */ 75 SCIP_Bool ispublic, /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */ 76 SCIP_DIVETYPE divetypemask, /**< bit mask that represents the supported dive types by this dive set */ 77 SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)), /**< method for candidate score and rounding direction */ 78 SCIP_DECL_DIVESETAVAILABLE((*divesetavailable)) /**< callback to check availability of dive set at the current stage, or NULL if always available */ 79 ); 80 81 /** resets diving settings counters */ 82 SCIP_RETCODE SCIPdivesetReset( 83 SCIP_DIVESET* diveset, /**< diveset to be reset */ 84 SCIP_SET* set /**< global SCIP settings */ 85 ); 86 87 /** update diveset statistics and global diveset statistics */ 88 void SCIPdivesetUpdateStats( 89 SCIP_DIVESET* diveset, /**< diveset to be reset */ 90 SCIP_STAT* stat, /**< global SCIP statistics */ 91 int depth, /**< the depth reached this time */ 92 int nprobingnodes, /**< the number of probing nodes explored this time */ 93 int nbacktracks, /**< the number of backtracks during probing this time */ 94 SCIP_Longint nsolsfound, /**< number of new solutions found this time */ 95 SCIP_Longint nbestsolsfound, /**< number of new best solutions found this time */ 96 SCIP_Longint nconflictsfound, /**< number of new conflicts found this time */ 97 SCIP_Bool leavesol, /**< has the diving heuristic reached a feasible leaf */ 98 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 99 ); 100 101 /** get the candidate score and preferred rounding direction for a candidate variable */ 102 SCIP_RETCODE SCIPdivesetGetScore( 103 SCIP_DIVESET* diveset, /**< general diving settings */ 104 SCIP_SET* set, /**< SCIP settings */ 105 SCIP_DIVETYPE divetype, /**< the type of diving that should be applied */ 106 SCIP_VAR* divecand, /**< the candidate for which the branching direction is requested */ 107 SCIP_Real divecandsol, /**< LP solution value of the candidate */ 108 SCIP_Real divecandfrac, /**< fractionality of the candidate */ 109 SCIP_Real* candscore, /**< pointer to store the candidate score */ 110 SCIP_Bool* roundup /**< pointer to store whether preferred direction for diving is upwards */ 111 ); 112 113 /** check specific preconditions for diving, e.g., if an incumbent solution is available */ 114 SCIP_RETCODE SCIPdivesetIsAvailable( 115 SCIP_DIVESET* diveset, /**< diving heuristic settings */ 116 SCIP_SET* set, /**< SCIP settings */ 117 SCIP_Bool* available /**< pointer to store if the diving can run at the current solving stage */ 118 ); 119 120 /** update diveset LP statistics, should be called after every LP solved by this diving heuristic */ 121 void SCIPdivesetUpdateLPStats( 122 SCIP_DIVESET* diveset, /**< diving settings */ 123 SCIP_STAT* stat, /**< global SCIP statistics */ 124 SCIP_Longint niterstoadd, /**< additional number of LP iterations to be added */ 125 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 126 ); 127 128 /** copies the given primal heuristic to a new scip */ 129 SCIP_RETCODE SCIPheurCopyInclude( 130 SCIP_HEUR* heur, /**< primal heuristic */ 131 SCIP_SET* set /**< SCIP_SET of SCIP to copy to */ 132 ); 133 134 /** creates a primal heuristic */ 135 SCIP_RETCODE SCIPheurCreate( 136 SCIP_HEUR** heur, /**< pointer to primal heuristic data structure */ 137 SCIP_SET* set, /**< global SCIP settings */ 138 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 139 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */ 140 const char* name, /**< name of primal heuristic */ 141 const char* desc, /**< description of primal heuristic */ 142 char dispchar, /**< display character of primal heuristic */ 143 int priority, /**< priority of the primal heuristic */ 144 int freq, /**< frequency for calling primal heuristic */ 145 int freqofs, /**< frequency offset for calling primal heuristic */ 146 int maxdepth, /**< maximal depth level to call heuristic at (-1: no limit) */ 147 SCIP_HEURTIMING timingmask, /**< positions in the node solving loop where heuristic should be executed */ 148 SCIP_Bool usessubscip, /**< does the heuristic use a secondary SCIP instance? */ 149 SCIP_DECL_HEURCOPY ((*heurcopy)), /**< copy method of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */ 150 SCIP_DECL_HEURFREE ((*heurfree)), /**< destructor of primal heuristic */ 151 SCIP_DECL_HEURINIT ((*heurinit)), /**< initialize primal heuristic */ 152 SCIP_DECL_HEUREXIT ((*heurexit)), /**< deinitialize primal heuristic */ 153 SCIP_DECL_HEURINITSOL ((*heurinitsol)), /**< solving process initialization method of primal heuristic */ 154 SCIP_DECL_HEUREXITSOL ((*heurexitsol)), /**< solving process deinitialization method of primal heuristic */ 155 SCIP_DECL_HEUREXEC ((*heurexec)), /**< execution method of primal heuristic */ 156 SCIP_HEURDATA* heurdata /**< primal heuristic data */ 157 ); 158 159 /** calls destructor and frees memory of primal heuristic */ 160 SCIP_RETCODE SCIPheurFree( 161 SCIP_HEUR** heur, /**< pointer to primal heuristic data structure */ 162 SCIP_SET* set, /**< global SCIP settings */ 163 BMS_BLKMEM* blkmem /**< block memory */ 164 ); 165 166 /** initializes primal heuristic */ 167 SCIP_RETCODE SCIPheurInit( 168 SCIP_HEUR* heur, /**< primal heuristic */ 169 SCIP_SET* set /**< global SCIP settings */ 170 ); 171 172 /** calls exit method of primal heuristic */ 173 SCIP_RETCODE SCIPheurExit( 174 SCIP_HEUR* heur, /**< primal heuristic */ 175 SCIP_SET* set /**< global SCIP settings */ 176 ); 177 178 /** informs primal heuristic that the branch and bound process is being started */ 179 SCIP_RETCODE SCIPheurInitsol( 180 SCIP_HEUR* heur, /**< primal heuristic */ 181 SCIP_SET* set /**< global SCIP settings */ 182 ); 183 184 /** informs primal heuristic that the branch and bound process data is being freed */ 185 SCIP_RETCODE SCIPheurExitsol( 186 SCIP_HEUR* heur, /**< primal heuristic */ 187 SCIP_SET* set /**< global SCIP settings */ 188 ); 189 190 /** should the heuristic be executed at the given depth, frequency, timing, ... */ 191 SCIP_Bool SCIPheurShouldBeExecuted( 192 SCIP_HEUR* heur, /**< primal heuristic */ 193 int depth, /**< depth of current node */ 194 int lpstateforkdepth, /**< depth of the last node with solved LP */ 195 SCIP_HEURTIMING heurtiming, /**< current point in the node solving process */ 196 SCIP_Bool* delayed /**< pointer to store whether the heuristic should be delayed */ 197 ); 198 199 /** calls execution method of primal heuristic */ 200 SCIP_RETCODE SCIPheurExec( 201 SCIP_HEUR* heur, /**< primal heuristic */ 202 SCIP_SET* set, /**< global SCIP settings */ 203 SCIP_PRIMAL* primal, /**< primal data */ 204 int depth, /**< depth of current node */ 205 int lpstateforkdepth, /**< depth of the last node with solved LP */ 206 SCIP_HEURTIMING heurtiming, /**< current point in the node solving process */ 207 SCIP_Bool nodeinfeasible, /**< was the current node already detected to be infeasible? */ 208 int* ndelayedheurs, /**< pointer to count the number of delayed heuristics */ 209 SCIP_RESULT* result /**< pointer to store the result of the callback method */ 210 ); 211 212 /** sets priority of primal heuristic */ 213 void SCIPheurSetPriority( 214 SCIP_HEUR* heur, /**< primal heuristic */ 215 SCIP_SET* set, /**< global SCIP settings */ 216 int priority /**< new priority of the primal heuristic */ 217 ); 218 219 /** sets copy callback of primal heuristic */ 220 void SCIPheurSetCopy( 221 SCIP_HEUR* heur, /**< primal heuristic */ 222 SCIP_DECL_HEURCOPY ((*heurcopy)) /**< copy callback of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */ 223 ); 224 225 /** sets destructor callback of primal heuristic */ 226 void SCIPheurSetFree( 227 SCIP_HEUR* heur, /**< primal heuristic */ 228 SCIP_DECL_HEURFREE ((*heurfree)) /**< destructor of primal heuristic */ 229 ); 230 231 /** sets initialization callback of primal heuristic */ 232 void SCIPheurSetInit( 233 SCIP_HEUR* heur, /**< primal heuristic */ 234 SCIP_DECL_HEURINIT ((*heurinit)) /**< initialize primal heuristic */ 235 ); 236 237 /** sets deinitialization callback of primal heuristic */ 238 void SCIPheurSetExit( 239 SCIP_HEUR* heur, /**< primal heuristic */ 240 SCIP_DECL_HEUREXIT ((*heurexit)) /**< deinitialize primal heuristic */ 241 ); 242 243 /** sets solving process initialization callback of primal heuristic */ 244 void SCIPheurSetInitsol( 245 SCIP_HEUR* heur, /**< primal heuristic */ 246 SCIP_DECL_HEURINITSOL ((*heurinitsol)) /**< solving process initialization callback of primal heuristic */ 247 ); 248 249 /** sets solving process deinitialization callback of primal heuristic */ 250 void SCIPheurSetExitsol( 251 SCIP_HEUR* heur, /**< primal heuristic */ 252 SCIP_DECL_HEUREXITSOL ((*heurexitsol)) /**< solving process deinitialization callback of primal heuristic */ 253 ); 254 255 /** enables or disables all clocks of \p heur, depending on the value of the flag */ 256 void SCIPheurEnableOrDisableClocks( 257 SCIP_HEUR* heur, /**< the heuristic for which all clocks should be enabled or disabled */ 258 SCIP_Bool enable /**< should the clocks of the heuristic be enabled? */ 259 ); 260 261 #ifdef __cplusplus 262 } 263 #endif 264 265 #endif 266