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