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 pub_heur.h 17 * @ingroup PUBLICCOREAPI 18 * @brief public methods 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_PUB_HEUR_H__ 25 #define __SCIP_PUB_HEUR_H__ 26 27 #include "scip/def.h" 28 #include "scip/type_heur.h" 29 #include "scip/type_misc.h" 30 #include "scip/type_retcode.h" 31 #include "scip/type_scip.h" 32 #include "scip/type_sol.h" 33 #include "scip/type_timing.h" 34 #include "scip/type_var.h" 35 36 #ifdef __cplusplus 37 extern "C" { 38 #endif 39 40 /**@addtogroup PublicHeuristicMethods 41 * 42 * @{ 43 */ 44 45 46 47 /** compares two heuristics w. r. to their priority */ 48 SCIP_EXPORT 49 SCIP_DECL_SORTPTRCOMP(SCIPheurComp); 50 51 /** comparison method for sorting heuristics w.r.t. to their name */ 52 SCIP_EXPORT 53 SCIP_DECL_SORTPTRCOMP(SCIPheurCompName); 54 55 /** gets user data of primal heuristic */ 56 SCIP_EXPORT 57 SCIP_HEURDATA* SCIPheurGetData( 58 SCIP_HEUR* heur /**< primal heuristic */ 59 ); 60 61 /** sets user data of primal heuristic; user has to free old data in advance! */ 62 SCIP_EXPORT 63 void SCIPheurSetData( 64 SCIP_HEUR* heur, /**< primal heuristic */ 65 SCIP_HEURDATA* heurdata /**< new primal heuristic user data */ 66 ); 67 68 /** gets name of primal heuristic */ 69 SCIP_EXPORT 70 const char* SCIPheurGetName( 71 SCIP_HEUR* heur /**< primal heuristic */ 72 ); 73 74 /** gets description of primal heuristic */ 75 SCIP_EXPORT 76 const char* SCIPheurGetDesc( 77 SCIP_HEUR* heur /**< primal heuristic */ 78 ); 79 80 /** gets display character of primal heuristic */ 81 SCIP_EXPORT 82 char SCIPheurGetDispchar( 83 SCIP_HEUR* heur /**< primal heuristic */ 84 ); 85 86 /** returns the timing mask of the heuristic */ 87 SCIP_EXPORT 88 SCIP_HEURTIMING SCIPheurGetTimingmask( 89 SCIP_HEUR* heur /**< primal heuristic */ 90 ); 91 92 /** sets new timing mask for heuristic */ 93 SCIP_EXPORT 94 void SCIPheurSetTimingmask( 95 SCIP_HEUR* heur, /**< primal heuristic */ 96 SCIP_HEURTIMING timingmask /**< new timing mask of heuristic */ 97 ); 98 99 /** does the heuristic use a secondary SCIP instance? */ 100 SCIP_EXPORT 101 SCIP_Bool SCIPheurUsesSubscip( 102 SCIP_HEUR* heur /**< primal heuristic */ 103 ); 104 105 /** gets priority of primal heuristic */ 106 SCIP_EXPORT 107 int SCIPheurGetPriority( 108 SCIP_HEUR* heur /**< primal heuristic */ 109 ); 110 111 /** gets frequency of primal heuristic */ 112 SCIP_EXPORT 113 int SCIPheurGetFreq( 114 SCIP_HEUR* heur /**< primal heuristic */ 115 ); 116 117 /** sets frequency of primal heuristic */ 118 SCIP_EXPORT 119 void SCIPheurSetFreq( 120 SCIP_HEUR* heur, /**< primal heuristic */ 121 int freq /**< new frequency of heuristic */ 122 ); 123 124 /** gets frequency offset of primal heuristic */ 125 SCIP_EXPORT 126 int SCIPheurGetFreqofs( 127 SCIP_HEUR* heur /**< primal heuristic */ 128 ); 129 130 /** gets maximal depth level for calling primal heuristic (returns -1, if no depth limit exists) */ 131 SCIP_EXPORT 132 int SCIPheurGetMaxdepth( 133 SCIP_HEUR* heur /**< primal heuristic */ 134 ); 135 136 /** gets the number of times, the heuristic was called and tried to find a solution */ 137 SCIP_EXPORT 138 SCIP_Longint SCIPheurGetNCalls( 139 SCIP_HEUR* heur /**< primal heuristic */ 140 ); 141 142 /** gets the number of primal feasible solutions found by this heuristic */ 143 SCIP_EXPORT 144 SCIP_Longint SCIPheurGetNSolsFound( 145 SCIP_HEUR* heur /**< primal heuristic */ 146 ); 147 148 /** gets the number of new best primal feasible solutions found by this heuristic */ 149 SCIP_EXPORT 150 SCIP_Longint SCIPheurGetNBestSolsFound( 151 SCIP_HEUR* heur /**< primal heuristic */ 152 ); 153 154 /** is primal heuristic initialized? */ 155 SCIP_EXPORT 156 SCIP_Bool SCIPheurIsInitialized( 157 SCIP_HEUR* heur /**< primal heuristic */ 158 ); 159 160 /** gets time in seconds used in this heuristic for setting up for next stages */ 161 SCIP_EXPORT 162 SCIP_Real SCIPheurGetSetupTime( 163 SCIP_HEUR* heur /**< primal heuristic */ 164 ); 165 166 /** gets time in seconds used in this heuristic */ 167 SCIP_EXPORT 168 SCIP_Real SCIPheurGetTime( 169 SCIP_HEUR* heur /**< primal heuristic */ 170 ); 171 172 /** returns array of divesets of this primal heuristic, or NULL if it has no divesets */ 173 SCIP_EXPORT 174 SCIP_DIVESET** SCIPheurGetDivesets( 175 SCIP_HEUR* heur /**< primal heuristic */ 176 ); 177 178 /** returns the number of divesets of this primal heuristic */ 179 SCIP_EXPORT 180 int SCIPheurGetNDivesets( 181 SCIP_HEUR* heur /**< primal heuristic */ 182 ); 183 184 /** @} */ 185 186 /** get the heuristic to which this diving setting belongs */ 187 SCIP_EXPORT 188 SCIP_HEUR* SCIPdivesetGetHeur( 189 SCIP_DIVESET* diveset /**< diving settings */ 190 ); 191 192 /** get the working solution of this dive set */ 193 SCIP_EXPORT 194 SCIP_SOL* SCIPdivesetGetWorkSolution( 195 SCIP_DIVESET* diveset /**< diving settings */ 196 ); 197 198 /** set the working solution for this dive set */ 199 SCIP_EXPORT 200 void SCIPdivesetSetWorkSolution( 201 SCIP_DIVESET* diveset, /**< diving settings */ 202 SCIP_SOL* sol /**< new working solution for this dive set, or NULL */ 203 ); 204 205 /**@addtogroup PublicDivesetMethods 206 * 207 * @{ 208 */ 209 210 /** get the name of the dive set */ 211 SCIP_EXPORT 212 const char* SCIPdivesetGetName( 213 SCIP_DIVESET* diveset /**< diving settings */ 214 ); 215 216 /** get the minimum relative depth of the diving settings */ 217 SCIP_EXPORT 218 SCIP_Real SCIPdivesetGetMinRelDepth( 219 SCIP_DIVESET* diveset /**< diving settings */ 220 ); 221 222 /** get the maximum relative depth of the diving settings */ 223 SCIP_EXPORT 224 SCIP_Real SCIPdivesetGetMaxRelDepth( 225 SCIP_DIVESET* diveset /**< diving settings */ 226 ); 227 228 /** get the number of successful runs of the diving settings */ 229 SCIP_EXPORT 230 SCIP_Longint SCIPdivesetGetSolSuccess( 231 SCIP_DIVESET* diveset, /**< diving settings */ 232 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 233 ); 234 235 /** get the number of calls to this dive set */ 236 SCIP_EXPORT 237 int SCIPdivesetGetNCalls( 238 SCIP_DIVESET* diveset, /**< diving settings */ 239 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 240 ); 241 242 /** get the number of calls successfully terminated at a feasible leaf node */ 243 SCIP_EXPORT 244 int SCIPdivesetGetNSolutionCalls( 245 SCIP_DIVESET* diveset, /**< diving settings */ 246 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 247 ); 248 249 /** get the minimum depth reached by this dive set */ 250 SCIP_EXPORT 251 int SCIPdivesetGetMinDepth( 252 SCIP_DIVESET* diveset, /**< diving settings */ 253 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 254 ); 255 256 /** get the maximum depth reached by this dive set */ 257 SCIP_EXPORT 258 int SCIPdivesetGetMaxDepth( 259 SCIP_DIVESET* diveset, /**< diving settings */ 260 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 261 ); 262 263 /** get the average depth this dive set reached during execution */ 264 SCIP_EXPORT 265 SCIP_Real SCIPdivesetGetAvgDepth( 266 SCIP_DIVESET* diveset, /**< diving settings */ 267 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 268 ); 269 270 /** get the minimum depth at which this dive set found a solution */ 271 SCIP_EXPORT 272 int SCIPdivesetGetMinSolutionDepth( 273 SCIP_DIVESET* diveset, /**< diving settings */ 274 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 275 ); 276 277 /** get the maximum depth at which this dive set found a solution */ 278 SCIP_EXPORT 279 int SCIPdivesetGetMaxSolutionDepth( 280 SCIP_DIVESET* diveset, /**< diving settings */ 281 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 282 ); 283 284 /** get the average depth at which this dive set found a solution */ 285 SCIP_EXPORT 286 SCIP_Real SCIPdivesetGetAvgSolutionDepth( 287 SCIP_DIVESET* diveset, /**< diving settings */ 288 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 289 ); 290 291 /** get the total number of LP iterations used by this dive set */ 292 SCIP_EXPORT 293 SCIP_Longint SCIPdivesetGetNLPIterations( 294 SCIP_DIVESET* diveset, /**< diving settings */ 295 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 296 ); 297 298 /** get the total number of probing nodes used by this dive set */ 299 SCIP_EXPORT 300 SCIP_Longint SCIPdivesetGetNProbingNodes( 301 SCIP_DIVESET* diveset, /**< diving settings */ 302 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 303 ); 304 305 /** get the total number of backtracks performed by this dive set */ 306 SCIP_EXPORT 307 SCIP_Longint SCIPdivesetGetNBacktracks( 308 SCIP_DIVESET* diveset, /**< diving settings */ 309 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 310 ); 311 312 /** get the total number of conflicts found by this dive set */ 313 SCIP_EXPORT 314 SCIP_Longint SCIPdivesetGetNConflicts( 315 SCIP_DIVESET* diveset, /**< diving settings */ 316 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 317 ); 318 319 /** get the total number of solutions (leaf and rounded solutions) found by the dive set */ 320 SCIP_EXPORT 321 SCIP_Longint SCIPdivesetGetNSols( 322 SCIP_DIVESET* diveset, /**< diving settings */ 323 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 324 ); 325 326 /** get the maximum LP iterations quotient of the diving settings */ 327 SCIP_EXPORT 328 SCIP_Real SCIPdivesetGetMaxLPIterQuot( 329 SCIP_DIVESET* diveset /**< diving settings */ 330 ); 331 332 /** get the maximum LP iterations offset of the diving settings */ 333 SCIP_EXPORT 334 int SCIPdivesetGetMaxLPIterOffset( 335 SCIP_DIVESET* diveset /**< diving settings */ 336 ); 337 338 /** get the maximum upper bound quotient parameter of the diving settings if no solution is available */ 339 SCIP_EXPORT 340 SCIP_Real SCIPdivesetGetUbQuotNoSol( 341 SCIP_DIVESET* diveset /**< diving settings */ 342 ); 343 344 /** get the average quotient parameter of the diving settings if no solution is available */ 345 SCIP_EXPORT 346 SCIP_Real SCIPdivesetGetAvgQuotNoSol( 347 SCIP_DIVESET* diveset /**< diving settings */ 348 ); 349 350 /** get the maximum upper bound quotient parameter of the diving settings if an incumbent solution exists */ 351 SCIP_EXPORT 352 SCIP_Real SCIPdivesetGetUbQuot( 353 SCIP_DIVESET* diveset /**< diving settings */ 354 ); 355 356 /** get the average upper bound quotient parameter of the diving settings if an incumbent solution exists */ 357 SCIP_EXPORT 358 SCIP_Real SCIPdivesetGetAvgQuot( 359 SCIP_DIVESET* diveset /**< diving settings */ 360 ); 361 362 /** should backtracking be applied? */ 363 SCIP_EXPORT 364 SCIP_Bool SCIPdivesetUseBacktrack( 365 SCIP_DIVESET* diveset /**< diving settings */ 366 ); 367 368 /** returns the LP solve frequency for diving LPs (0: dynamically based on number of intermediate domain reductions) */ 369 SCIP_EXPORT 370 int SCIPdivesetGetLPSolveFreq( 371 SCIP_DIVESET* diveset /**< diving settings */ 372 ); 373 374 /** returns the domain reduction quotient for triggering an immediate resolve of the diving LP (0.0: always resolve)*/ 375 SCIP_EXPORT 376 SCIP_Real SCIPdivesetGetLPResolveDomChgQuot( 377 SCIP_DIVESET* diveset /**< diving settings */ 378 ); 379 380 /** should only LP branching candidates be considered instead of the slower but 381 * more general constraint handler diving variable selection? 382 */ 383 SCIP_EXPORT 384 SCIP_Bool SCIPdivesetUseOnlyLPBranchcands( 385 SCIP_DIVESET* diveset /**< diving settings */ 386 ); 387 388 /** returns TRUE if dive set supports diving of the specified type */ 389 SCIP_EXPORT 390 SCIP_Bool SCIPdivesetSupportsType( 391 SCIP_DIVESET* diveset, /**< diving settings */ 392 SCIP_DIVETYPE divetype /**< bit mask that represents the supported dive types by this dive set */ 393 ); 394 395 /** returns the random number generator of this \p diveset for tie-breaking */ 396 SCIP_EXPORT 397 SCIP_RANDNUMGEN* SCIPdivesetGetRandnumgen( 398 SCIP_DIVESET* diveset /**< diving settings */ 399 ); 400 401 /** is this dive set publicly available (ie., can be used by other primal heuristics?) */ 402 SCIP_EXPORT 403 SCIP_Bool SCIPdivesetIsPublic( 404 SCIP_DIVESET* diveset /**< diving settings */ 405 ); 406 407 /** @} */ 408 409 /**@defgroup PublicVariableGraphMethods Public Variable Graph Methods 410 * @ingroup MiscellaneousMethods 411 * 412 * @brief methods to create a variable graph and perform breadth-first search 413 * 414 * @{ 415 */ 416 417 /** Perform breadth-first (BFS) search on the variable constraint graph. 418 * 419 * The result of the algorithm is that the \p distances array contains the correct distances for 420 * every variable from the start variables. The distance of a variable can then be accessed through its 421 * problem index (calling SCIPvarGetProbindex()). 422 * Hence, The method assumes that the length of \p distances is at least 423 * SCIPgetNVars(). 424 * Variables that are not connected through constraints to the start variables have a distance of -1. 425 * 426 * Limits can be provided to further restrict the breadth-first search. If a distance limit is given, 427 * the search will be performed until the first variable at this distance is popped from the queue, i.e., 428 * all variables with a distance < maxdistance have been labeled by the search. 429 * If a variable limit is given, the search stops after it completes the distance level at which 430 * the limit was reached. Hence, more variables may be actually labeled. 431 * The start variables are accounted for those variable limits. 432 * 433 * If no variable variable constraint graph is provided, the method will create one and free it at the end 434 * This is useful for a single use of the variable constraint graph. For several consecutive uses, 435 * it is advised to create a variable constraint graph via SCIPvariableGraphCreate(). 436 */ 437 SCIP_EXPORT 438 SCIP_RETCODE SCIPvariablegraphBreadthFirst( 439 SCIP* scip, /**< SCIP data structure */ 440 SCIP_VGRAPH* vargraph, /**< pointer to the variable graph, or NULL to let the function create a local graph */ 441 SCIP_VAR** startvars, /**< array of start variables to calculate distance from */ 442 int nstartvars, /**< number of starting variables, at least 1 */ 443 int* distances, /**< array to keep distance in vargraph from start variables for every variable */ 444 int maxdistance, /**< maximum distance >= 0 from start variable (INT_MAX for complete BFS) */ 445 int maxvars, /**< maximum number of variables to compute distance for */ 446 int maxbinintvars /**< maximum number of binary or integer variables to compute distance for */ 447 ); 448 449 /** initialization method of variable graph data structure */ 450 SCIP_EXPORT 451 SCIP_RETCODE SCIPvariableGraphCreate( 452 SCIP* scip, /**< SCIP data structure */ 453 SCIP_VGRAPH** vargraph, /**< pointer to the variable graph */ 454 SCIP_Bool relaxdenseconss, /**< should dense constraints (at least as dense as \p density) be 455 * ignored by connectivity graph? */ 456 SCIP_Real relaxdensity, /**< density (with respect to number of variables) to relax constraint from graph */ 457 int* nrelaxedconstraints /**< pointer to store the number of constraints that were relaxed, or NULL if not needed */ 458 ); 459 460 /** deinitialization method of variable graph data structure */ 461 SCIP_EXPORT 462 void SCIPvariableGraphFree( 463 SCIP* scip, /**< SCIP data structure */ 464 SCIP_VGRAPH** vargraph /**< pointer to the variable graph */ 465 ); 466 467 /** @} */ 468 469 470 #ifdef __cplusplus 471 } 472 #endif 473 474 #endif 475