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.c 26 * @ingroup OTHER_CFILES 27 * @brief methods for primal heuristics 28 * @author Tobias Achterberg 29 * @author Timo Berthold 30 */ 31 32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 33 34 #include <assert.h> 35 #include <string.h> 36 37 #include "scip/def.h" 38 #include "scip/set.h" 39 #include "scip/clock.h" 40 #include "scip/paramset.h" 41 #include "scip/primal.h" 42 #include "scip/scip.h" 43 #include "scip/heur.h" 44 #include "scip/pub_message.h" 45 #include "scip/pub_misc.h" 46 #include "scip/misc.h" 47 48 #include "scip/struct_heur.h" 49 50 /** compares two heuristics w.r.t. to their delay positions and priorities */ 51 SCIP_DECL_SORTPTRCOMP(SCIPheurComp) 52 { /*lint --e{715}*/ 53 SCIP_HEUR* heur1 = (SCIP_HEUR*)elem1; 54 SCIP_HEUR* heur2 = (SCIP_HEUR*)elem2; 55 56 assert(heur1 != NULL); 57 assert(heur2 != NULL); 58 59 if( heur1->delaypos == heur2->delaypos ) 60 if( heur1->priority != heur2->priority ) 61 return heur2->priority - heur1->priority; /* prefer higher priorities */ 62 else 63 return (strcmp(heur1->name, heur2->name)); /* tiebreaker */ 64 else if( heur1->delaypos == -1 ) 65 return +1; /* prefer delayed heuristics */ 66 else if( heur2->delaypos == -1 ) 67 return -1; /* prefer delayed heuristics */ 68 else if( heur1->ncalls * heur1->freq > heur2->ncalls * heur2->freq ) 69 return +1; 70 else if( heur1->ncalls * heur1->freq < heur2->ncalls * heur2->freq ) 71 return -1; 72 else 73 return heur1->delaypos - heur2->delaypos; /* prefer lower delay positions */ 74 } 75 76 /** compares two heuristics w.r.t. to their priority values */ 77 SCIP_DECL_SORTPTRCOMP(SCIPheurCompPriority) 78 { 79 return SCIPheurGetPriority((SCIP_HEUR*)elem2) - 80 SCIPheurGetPriority((SCIP_HEUR*)elem1); 81 } 82 83 /** comparison method for sorting heuristics w.r.t. to their name */ 84 SCIP_DECL_SORTPTRCOMP(SCIPheurCompName) 85 { 86 return strcmp(SCIPheurGetName((SCIP_HEUR*)elem1), SCIPheurGetName((SCIP_HEUR*)elem2)); 87 } 88 89 /** method to call, when the priority of a heuristic was changed */ 90 static 91 SCIP_DECL_PARAMCHGD(paramChgdHeurPriority) 92 { /*lint --e{715}*/ 93 SCIP_PARAMDATA* paramdata; 94 95 paramdata = SCIPparamGetData(param); 96 assert(paramdata != NULL); 97 98 /* use SCIPsetHeurPriority() to mark the heuristics unsorted */ 99 SCIP_CALL( SCIPsetHeurPriority(scip, (SCIP_HEUR*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/ 100 101 return SCIP_OKAY; 102 } 103 104 /** resets diving statistics */ 105 static 106 void resetDivesetStats( 107 SCIP_DIVESETSTATS* divesetstats /**< dive set statistics */ 108 ) 109 { 110 assert(divesetstats != NULL); 111 112 divesetstats->nlpiterations = 0L; 113 divesetstats->totaldepth = 0L; 114 divesetstats->totalsoldepth = 0L; 115 divesetstats->totalnnodes = 0L; 116 divesetstats->totalnbacktracks = 0L; 117 divesetstats->minsoldepth = INT_MAX; 118 divesetstats->maxsoldepth = -1; 119 divesetstats->mindepth = INT_MAX; 120 divesetstats->maxdepth = -1; 121 divesetstats->nlps = 0; 122 divesetstats->nsolsfound = 0; 123 divesetstats->nbestsolsfound = 0; 124 divesetstats->nconflictsfound = 0; 125 divesetstats->ncalls = 0; 126 divesetstats->nsolcalls = 0; 127 } 128 129 /* resets diving settings counters */ 130 SCIP_RETCODE SCIPdivesetReset( 131 SCIP_DIVESET* diveset, /**< diveset to be reset */ 132 SCIP_SET* set /**< global SCIP settings */ 133 ) 134 { 135 int d; 136 137 assert(diveset != NULL); 138 assert(diveset->randnumgen != NULL); 139 140 /* reset diveset statistics for all contexts */ 141 for( d = 0; d < 4; ++d ) 142 { 143 resetDivesetStats(diveset->divesetstats[d]); 144 } 145 146 /* reset the random number generator */ 147 SCIPrandomSetSeed(diveset->randnumgen, (unsigned int) SCIPsetInitializeRandomSeed(set, diveset->initialseed)); 148 149 return SCIP_OKAY; 150 } 151 152 /** update dive set statistics */ 153 static 154 void updateDivesetstats( 155 SCIP_DIVESETSTATS* divesetstats, /**< dive set statistics */ 156 int depth, /**< the depth reached this time */ 157 int nprobingnodes, /**< the number of probing nodes explored this time */ 158 int nbacktracks, /**< the number of backtracks during probing this time */ 159 SCIP_Longint nsolsfound, /**< number of new solutions found this time */ 160 SCIP_Longint nbestsolsfound, /**< number of new best solutions found this time */ 161 SCIP_Longint nconflictsfound, /**< number of new conflicts found this time */ 162 SCIP_Bool leavesol /**< has the diving heuristic reached a feasible leaf */ 163 ) 164 { 165 divesetstats->totaldepth += depth; 166 divesetstats->mindepth = MIN(divesetstats->mindepth, depth); 167 divesetstats->maxdepth = MAX(divesetstats->maxdepth, depth); 168 divesetstats->totalnnodes += nprobingnodes; 169 divesetstats->totalnbacktracks += nbacktracks; 170 divesetstats->ncalls++; 171 172 /* update solution statistics only if a solution was found */ 173 if( leavesol ) 174 { 175 divesetstats->totalsoldepth += depth; 176 divesetstats->minsoldepth = MIN(divesetstats->minsoldepth, depth); 177 divesetstats->maxsoldepth = MAX(divesetstats->maxsoldepth, depth); 178 divesetstats->nsolcalls++; 179 } 180 181 divesetstats->nsolsfound += nsolsfound; 182 divesetstats->nbestsolsfound += nbestsolsfound; 183 divesetstats->nconflictsfound += nconflictsfound; 184 } 185 186 /** returns the dive set statistics for the given context */ 187 static 188 SCIP_DIVESETSTATS* divesetGetStats( 189 SCIP_DIVESET* diveset, /**< diveset to be reset */ 190 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 191 ) 192 { 193 assert(diveset != NULL); 194 assert(divecontext == SCIP_DIVECONTEXT_ADAPTIVE || 195 divecontext == SCIP_DIVECONTEXT_SINGLE || 196 divecontext == SCIP_DIVECONTEXT_TOTAL || 197 divecontext == SCIP_DIVECONTEXT_SCHEDULER ); 198 199 return diveset->divesetstats[(int)divecontext]; 200 } 201 202 /** update diveset statistics and global diveset statistics */ 203 void SCIPdivesetUpdateStats( 204 SCIP_DIVESET* diveset, /**< diveset to be reset */ 205 SCIP_STAT* stat, /**< global SCIP statistics */ 206 int depth, /**< the depth reached this time */ 207 int nprobingnodes, /**< the number of probing nodes explored this time */ 208 int nbacktracks, /**< the number of backtracks during probing this time */ 209 SCIP_Longint nsolsfound, /**< number of new solutions found this time */ 210 SCIP_Longint nbestsolsfound, /**< number of new best solutions found this time */ 211 SCIP_Longint nconflictsfound, /**< number of new conflicts found this time */ 212 SCIP_Bool leavesol, /**< has the diving heuristic reached a feasible leaf */ 213 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 214 ) 215 { 216 int c; 217 SCIP_DIVECONTEXT updatecontexts[] = {SCIP_DIVECONTEXT_TOTAL, divecontext}; 218 219 assert(diveset != NULL); 220 assert(divecontext == SCIP_DIVECONTEXT_ADAPTIVE || divecontext == SCIP_DIVECONTEXT_SINGLE 221 || divecontext == SCIP_DIVECONTEXT_SCHEDULER); 222 223 /* update statistics for total context and given context */ 224 for( c = 0; c < 2; ++c ) 225 { 226 updateDivesetstats(divesetGetStats(diveset, updatecontexts[c]), depth, nprobingnodes, 227 nbacktracks, nsolsfound, nbestsolsfound, nconflictsfound, leavesol); 228 } 229 230 stat->totaldivesetdepth += depth; 231 stat->ndivesetcalls++; 232 } 233 234 /** append diveset to heuristic array of divesets */ 235 static 236 SCIP_RETCODE heurAddDiveset( 237 SCIP_HEUR* heur, /**< the heuristic to which this dive setting belongs */ 238 SCIP_DIVESET* diveset /**< pointer to the freshly created diveset */ 239 ) 240 { 241 assert(heur != NULL); 242 assert(diveset != NULL); 243 assert(diveset->heur == NULL); 244 245 diveset->heur = heur; 246 247 if( heur->divesets == NULL ) 248 { 249 assert(heur->ndivesets == 0); 250 SCIP_ALLOC( BMSallocMemoryArray(&heur->divesets, 1) ); 251 } 252 else 253 { 254 assert(heur->ndivesets > 0); 255 SCIP_ALLOC( BMSreallocMemoryArray(&heur->divesets, heur->ndivesets + 1) ); /*lint !e776 I expect no overflow here */ 256 } 257 258 /* append diveset to the end of the array */ 259 heur->divesets[heur->ndivesets] = diveset; 260 heur->ndivesets++; 261 262 return SCIP_OKAY; 263 } 264 265 /** create a set of diving heuristic settings */ 266 SCIP_RETCODE SCIPdivesetCreate( 267 SCIP_DIVESET** divesetptr, /**< pointer to the freshly created diveset */ 268 SCIP_HEUR* heur, /**< the heuristic to which this dive setting belongs */ 269 const char* name, /**< name for the diveset, or NULL if the name of the heuristic should be used */ 270 SCIP_SET* set, /**< global SCIP settings */ 271 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 272 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */ 273 SCIP_Real minreldepth, /**< minimal relative depth to start diving */ 274 SCIP_Real maxreldepth, /**< maximal relative depth to start diving */ 275 SCIP_Real maxlpiterquot, /**< maximal fraction of diving LP iterations compared to node LP iterations */ 276 SCIP_Real maxdiveubquot, /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) 277 * where diving is performed (0.0: no limit) */ 278 SCIP_Real maxdiveavgquot, /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) 279 * where diving is performed (0.0: no limit) */ 280 SCIP_Real maxdiveubquotnosol, /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */ 281 SCIP_Real maxdiveavgquotnosol,/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */ 282 SCIP_Real lpresolvedomchgquot,/**< percentage of immediate domain changes during probing to trigger LP resolve */ 283 int lpsolvefreq, /**< LP solve frequency for (0: only if enough domain reductions are found by propagation)*/ 284 int maxlpiterofs, /**< additional number of allowed LP iterations */ 285 unsigned int initialseed, /**< initial seed for random number generation */ 286 SCIP_Bool backtrack, /**< use one level of backtracking if infeasibility is encountered? */ 287 SCIP_Bool onlylpbranchcands, /**< should only LP branching candidates be considered instead of the slower but 288 * more general constraint handler diving variable selection? */ 289 SCIP_Bool ispublic, /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */ 290 SCIP_DIVETYPE divetypemask, /**< bit mask that represents the supported dive types by this dive set */ 291 SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)), /**< method for candidate score and rounding direction */ 292 SCIP_DECL_DIVESETAVAILABLE((*divesetavailable)) /**< callback to check availability of dive set at the current stage, or NULL if always available */ 293 ) 294 { 295 int c; 296 char paramname[SCIP_MAXSTRLEN]; 297 const char* divesetname; 298 SCIP_DIVESET* diveset; 299 300 assert(divesetptr != NULL); 301 assert(set != NULL); 302 assert(divesetgetscore != NULL); 303 assert(heur != NULL); 304 assert(blkmem != NULL); 305 306 SCIP_ALLOC( BMSallocBlockMemory(blkmem, divesetptr) ); 307 diveset = *divesetptr; 308 309 /* allocate random number generator. Note that we must make explicit use of random seed initialization because 310 * we create the random number generator directly, not through the public SCIP API 311 */ 312 diveset->initialseed = initialseed; 313 314 /* simply use 0 as initial seed, the seed is reset in SCIPdivesetReset, anyway */ 315 SCIP_CALL( SCIPrandomCreate(&diveset->randnumgen, blkmem, 0) ); 316 317 /* for convenience, the name gets inferred from the heuristic to which the diveset is added if no name is provided */ 318 divesetname = (name == NULL ? SCIPheurGetName(heur) : name); 319 SCIP_ALLOC( BMSduplicateMemoryArray(&diveset->name, divesetname, strlen(divesetname)+1) ); 320 diveset->heur = NULL; 321 322 /* scoring callbacks */ 323 diveset->divesetgetscore = divesetgetscore; 324 diveset->divesetavailable = divesetavailable; 325 326 SCIP_CALL( heurAddDiveset(heur, diveset) ); 327 diveset->sol = NULL; 328 diveset->divetypemask = divetypemask; 329 diveset->ispublic = ispublic; 330 331 /* allocate memory for diveset statistics */ 332 for( c = 0; c < 4; ++c ) 333 { 334 SCIP_DIVESETSTATS** divesetstatsptr = &diveset->divesetstats[c]; 335 SCIP_ALLOC( BMSallocBlockMemory(blkmem, divesetstatsptr) ); 336 } 337 338 SCIP_CALL( SCIPdivesetReset(diveset, set) ); 339 340 /* add collection of diving heuristic specific parameters */ 341 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/minreldepth", diveset->name); 342 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, 343 paramname, "minimal relative depth to start diving", 344 &diveset->minreldepth, TRUE, minreldepth, 0.0, 1.0, NULL, NULL) ); 345 346 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxreldepth", diveset->name); 347 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, paramname, 348 "maximal relative depth to start diving", 349 &diveset->maxreldepth, TRUE, maxreldepth, 0.0, 1.0, NULL, NULL) ); 350 351 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxlpiterquot", diveset->name); 352 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, 353 paramname, 354 "maximal fraction of diving LP iterations compared to node LP iterations", 355 &diveset->maxlpiterquot, FALSE, maxlpiterquot, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 356 357 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxlpiterofs", diveset->name); 358 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, 359 paramname, 360 "additional number of allowed LP iterations", 361 &diveset->maxlpiterofs, FALSE, maxlpiterofs, 0, INT_MAX, NULL, NULL) ); 362 363 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiveubquot", diveset->name); 364 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, 365 paramname, 366 "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)", 367 &diveset->maxdiveubquot, TRUE, maxdiveubquot, 0.0, 1.0, NULL, NULL) ); 368 369 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiveavgquot", diveset->name); 370 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, 371 paramname, 372 "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)", 373 &diveset->maxdiveavgquot, TRUE, maxdiveavgquot, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 374 375 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiveubquotnosol", diveset->name); 376 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, 377 paramname, 378 "maximal UBQUOT when no solution was found yet (0.0: no limit)", 379 &diveset->maxdiveubquotnosol, TRUE, maxdiveubquotnosol, 0.0, 1.0, NULL, NULL) ); 380 381 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiveavgquotnosol", diveset->name); 382 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, 383 paramname, 384 "maximal AVGQUOT when no solution was found yet (0.0: no limit)", 385 &diveset->maxdiveavgquotnosol, TRUE, maxdiveavgquotnosol, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 386 387 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/backtrack", diveset->name); 388 SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, 389 paramname, 390 "use one level of backtracking if infeasibility is encountered?", 391 &diveset->backtrack, FALSE, backtrack, NULL, NULL) ); 392 393 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/lpresolvedomchgquot", diveset->name); 394 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, paramname, 395 "percentage of immediate domain changes during probing to trigger LP resolve", 396 &diveset->lpresolvedomchgquot, FALSE, lpresolvedomchgquot, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 397 398 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/lpsolvefreq", diveset->name); 399 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, 400 paramname, 401 "LP solve frequency for diving heuristics (0: only after enough domain changes have been found)", 402 &diveset->lpsolvefreq, FALSE, lpsolvefreq, 0, INT_MAX, 403 NULL, NULL) ); 404 405 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/onlylpbranchcands", diveset->name); 406 SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, 407 paramname, 408 "should only LP branching candidates be considered instead of the slower but " 409 "more general constraint handler diving variable selection?", 410 &diveset->onlylpbranchcands, FALSE, onlylpbranchcands, NULL, NULL) ); 411 412 return SCIP_OKAY; 413 } 414 415 /** get the heuristic to which this diving setting belongs */ 416 SCIP_HEUR* SCIPdivesetGetHeur( 417 SCIP_DIVESET* diveset /**< diving settings */ 418 ) 419 { 420 return diveset->heur; 421 } 422 423 /** get the working solution of this dive set */ 424 SCIP_SOL* SCIPdivesetGetWorkSolution( 425 SCIP_DIVESET* diveset /**< diving settings */ 426 ) 427 { 428 assert(diveset != NULL); 429 430 return diveset->sol; 431 } 432 433 /** set the working solution for this dive set */ 434 void SCIPdivesetSetWorkSolution( 435 SCIP_DIVESET* diveset, /**< diving settings */ 436 SCIP_SOL* sol /**< new working solution for this dive set, or NULL */ 437 ) 438 { 439 assert(diveset != NULL); 440 441 diveset->sol = sol; 442 } 443 444 /** get the name of the dive set */ 445 const char* SCIPdivesetGetName( 446 SCIP_DIVESET* diveset /**< diving settings */ 447 ) 448 { 449 assert(diveset != NULL); 450 451 return diveset->name; 452 } 453 454 /** get the minimum relative depth of the diving settings */ 455 SCIP_Real SCIPdivesetGetMinRelDepth( 456 SCIP_DIVESET* diveset /**< diving settings */ 457 ) 458 { 459 return diveset->minreldepth; 460 } 461 462 /** get the maximum relative depth of the diving settings */ 463 SCIP_Real SCIPdivesetGetMaxRelDepth( 464 SCIP_DIVESET* diveset /**< diving settings */ 465 ) 466 { 467 return diveset->maxreldepth; 468 } 469 470 /** get the number of successful runs of the diving settings */ 471 SCIP_Longint SCIPdivesetGetSolSuccess( 472 SCIP_DIVESET* diveset, /**< diving settings */ 473 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 474 475 ) 476 { 477 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext); 478 479 assert(divesetstats != NULL); 480 481 return 10 * divesetstats->nbestsolsfound + divesetstats->nsolsfound; 482 } 483 484 /** get the number of calls to this dive set */ 485 int SCIPdivesetGetNCalls( 486 SCIP_DIVESET* diveset, /**< diving settings */ 487 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 488 ) 489 { 490 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext); 491 492 assert(divesetstats != NULL); 493 494 return divesetstats->ncalls; 495 } 496 497 /** get the number of calls successfully terminated at a feasible leaf node */ 498 int SCIPdivesetGetNSolutionCalls( 499 SCIP_DIVESET* diveset, /**< diving settings */ 500 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 501 ) 502 { 503 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext); 504 505 assert(diveset != NULL); 506 507 return divesetstats->nsolcalls; 508 } 509 510 /** get the minimum depth reached by this dive set */ 511 int SCIPdivesetGetMinDepth( 512 SCIP_DIVESET* diveset, /**< diving settings */ 513 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 514 ) 515 { 516 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext); 517 518 assert(divesetstats != NULL); 519 520 return divesetstats->mindepth; 521 } 522 523 /** get the maximum depth reached by this dive set */ 524 int SCIPdivesetGetMaxDepth( 525 SCIP_DIVESET* diveset, /**< diving settings */ 526 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 527 ) 528 { 529 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext); 530 531 assert(divesetstats != NULL); 532 533 return divesetstats->maxdepth; 534 } 535 536 /** get the average depth this dive set reached during execution */ 537 SCIP_Real SCIPdivesetGetAvgDepth( 538 SCIP_DIVESET* diveset, /**< diving settings */ 539 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 540 ) 541 { 542 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext); 543 544 assert(divesetstats != NULL); 545 546 return (divesetstats->ncalls == 0 ? 0.0 : divesetstats->totaldepth / (SCIP_Real)divesetstats->ncalls); 547 } 548 549 /** get the minimum depth at which this dive set found a solution */ 550 int SCIPdivesetGetMinSolutionDepth( 551 SCIP_DIVESET* diveset, /**< diving settings */ 552 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 553 ) 554 { 555 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext); 556 557 assert(divesetstats != NULL); 558 559 return divesetstats->minsoldepth; 560 } 561 562 /** get the maximum depth at which this dive set found a solution */ 563 int SCIPdivesetGetMaxSolutionDepth( 564 SCIP_DIVESET* diveset, /**< diving settings */ 565 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 566 ) 567 { 568 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext); 569 570 assert(divesetstats != NULL); 571 572 return divesetstats->maxsoldepth; 573 } 574 575 /** get the average depth at which this dive set found a solution */ 576 SCIP_Real SCIPdivesetGetAvgSolutionDepth( 577 SCIP_DIVESET* diveset, /**< diving settings */ 578 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 579 ) 580 { 581 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext); 582 583 assert(divesetstats != NULL); 584 585 return (divesetstats->nsolcalls == 0 ? 0.0 : divesetstats->totalsoldepth / (SCIP_Real)divesetstats->nsolcalls); 586 } 587 588 /** get the total number of LP iterations used by this dive set */ 589 SCIP_Longint SCIPdivesetGetNLPIterations( 590 SCIP_DIVESET* diveset, /**< diving settings */ 591 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 592 ) 593 { 594 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext); 595 596 assert(divesetstats != NULL); 597 598 return divesetstats->nlpiterations; 599 } 600 601 /** get the total number of probing nodes used by this dive set */ 602 SCIP_Longint SCIPdivesetGetNProbingNodes( 603 SCIP_DIVESET* diveset, /**< diving settings */ 604 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 605 ) 606 { 607 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext); 608 609 assert(divesetstats != NULL); 610 611 return divesetstats->totalnnodes; 612 } 613 614 /** get the total number of backtracks performed by this dive set */ 615 SCIP_Longint SCIPdivesetGetNBacktracks( 616 SCIP_DIVESET* diveset, /**< diving settings */ 617 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 618 ) 619 { 620 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext); 621 622 assert(divesetstats != NULL); 623 624 return divesetstats->totalnbacktracks; 625 } 626 627 /** get the total number of conflicts found by this dive set */ 628 SCIP_Longint SCIPdivesetGetNConflicts( 629 SCIP_DIVESET* diveset, /**< diving settings */ 630 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 631 ) 632 { 633 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext); 634 635 assert(divesetstats != NULL); 636 637 return divesetstats->nconflictsfound; 638 } 639 640 /** get the total number of solutions (leaf and rounded solutions) found by the dive set */ 641 SCIP_Longint SCIPdivesetGetNSols( 642 SCIP_DIVESET* diveset, /**< diving settings */ 643 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 644 ) 645 { 646 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext); 647 648 assert(divesetstats != NULL); 649 650 return divesetstats->nsolsfound; 651 } 652 653 654 /** get the maximum LP iterations quotient of the diving settings */ 655 SCIP_Real SCIPdivesetGetMaxLPIterQuot( 656 SCIP_DIVESET* diveset /**< diving settings */ 657 ) 658 { 659 return diveset->maxlpiterquot; 660 } 661 662 /** get the maximum LP iterations offset of the diving settings */ 663 int SCIPdivesetGetMaxLPIterOffset( 664 SCIP_DIVESET* diveset /**< diving settings */ 665 ) 666 { 667 return diveset->maxlpiterofs; 668 } 669 670 /** get the maximum upper bound quotient parameter of the diving settings if no solution is available */ 671 SCIP_Real SCIPdivesetGetUbQuotNoSol( 672 SCIP_DIVESET* diveset /**< diving settings */ 673 ) 674 { 675 return diveset->maxdiveubquotnosol; 676 } 677 678 /** get the average quotient parameter of the diving settings if no solution is available */ 679 SCIP_Real SCIPdivesetGetAvgQuotNoSol( 680 SCIP_DIVESET* diveset /**< diving settings */ 681 ) 682 { 683 return diveset->maxdiveavgquotnosol; 684 } 685 /** get the maximum upper bound quotient parameter of the diving settings if an incumbent solution exists */ 686 SCIP_Real SCIPdivesetGetUbQuot( 687 SCIP_DIVESET* diveset /**< diving settings */ 688 ) 689 { 690 return diveset->maxdiveubquot; 691 } 692 693 /** get the average upper bound quotient parameter of the diving settings if an incumbent solution exists */ 694 SCIP_Real SCIPdivesetGetAvgQuot( 695 SCIP_DIVESET* diveset /**< diving settings */ 696 ) 697 { 698 return diveset->maxdiveavgquot; 699 } 700 701 /** should backtracking be applied? */ 702 SCIP_Bool SCIPdivesetUseBacktrack( 703 SCIP_DIVESET* diveset /**< diving settings */ 704 ) 705 { 706 return diveset->backtrack; 707 } 708 709 /** returns the LP solve frequency for diving LPs (0: dynamically based on number of intermediate domain reductions) */ 710 int SCIPdivesetGetLPSolveFreq( 711 SCIP_DIVESET* diveset /**< diving settings */ 712 ) 713 { 714 assert(diveset != NULL); 715 716 return diveset->lpsolvefreq; 717 } 718 719 /** returns the random number generator of this \p diveset for tie-breaking */ 720 SCIP_RANDNUMGEN* SCIPdivesetGetRandnumgen( 721 SCIP_DIVESET* diveset /**< diving settings */ 722 ) 723 { 724 assert(diveset != NULL); 725 assert(diveset->randnumgen != NULL); 726 727 return diveset->randnumgen; 728 } 729 730 /** returns the domain reduction quotient for triggering an immediate resolve of the diving LP (0.0: always resolve)*/ 731 SCIP_Real SCIPdivesetGetLPResolveDomChgQuot( 732 SCIP_DIVESET* diveset /**< diving settings */ 733 ) 734 { 735 assert(diveset != NULL); 736 737 return diveset->lpresolvedomchgquot; 738 } 739 740 /** should only LP branching candidates be considered instead of the slower but 741 * more general constraint handler diving variable selection? 742 */ 743 SCIP_Bool SCIPdivesetUseOnlyLPBranchcands( 744 SCIP_DIVESET* diveset /**< diving settings */ 745 ) 746 { 747 assert(diveset != NULL); 748 749 return diveset->onlylpbranchcands; 750 } 751 752 /** returns TRUE if dive set supports diving of the specified type */ 753 SCIP_Bool SCIPdivesetSupportsType( 754 SCIP_DIVESET* diveset, /**< diving settings */ 755 SCIP_DIVETYPE divetype /**< bit mask that represents the supported dive types by this dive set */ 756 ) 757 { 758 assert(diveset != NULL); 759 760 return (divetype & diveset->divetypemask); 761 } 762 763 /** is this dive set publicly available (ie., can be used by other primal heuristics?) */ 764 SCIP_Bool SCIPdivesetIsPublic( 765 SCIP_DIVESET* diveset /**< diving settings */ 766 ) 767 { 768 assert(diveset != NULL); 769 770 return diveset->ispublic; 771 } 772 773 /** updates LP related diveset statistics */ 774 static 775 void updateDivesetstatsLP( 776 SCIP_DIVESETSTATS* divesetstats, /**< diving settings */ 777 SCIP_Longint niterstoadd /**< additional number of LP iterations to be added */ 778 ) 779 { 780 assert(divesetstats != NULL); 781 782 divesetstats->nlpiterations += niterstoadd; 783 divesetstats->nlps++; 784 } 785 786 /** update diveset LP statistics, should be called after every LP solved by this diving heuristic */ 787 void SCIPdivesetUpdateLPStats( 788 SCIP_DIVESET* diveset, /**< diving settings */ 789 SCIP_STAT* stat, /**< global SCIP statistics */ 790 SCIP_Longint niterstoadd, /**< additional number of LP iterations to be added */ 791 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 792 ) 793 { 794 assert(diveset != NULL); 795 assert(divecontext == SCIP_DIVECONTEXT_ADAPTIVE || divecontext == SCIP_DIVECONTEXT_SINGLE 796 || divecontext == SCIP_DIVECONTEXT_SCHEDULER); 797 798 /* update statistics for total context and given context */ 799 updateDivesetstatsLP(divesetGetStats(diveset, divecontext), niterstoadd); 800 updateDivesetstatsLP(divesetGetStats(diveset, SCIP_DIVECONTEXT_TOTAL), niterstoadd); 801 802 stat->ndivesetlpiterations += niterstoadd; 803 stat->ndivesetlps++; 804 } 805 806 /** frees memory of a diveset */ 807 static 808 void divesetFree( 809 SCIP_DIVESET** divesetptr, /**< general diving settings */ 810 BMS_BLKMEM* blkmem /**< block memory for parameter settings */ 811 ) 812 { 813 int c; 814 SCIP_DIVESET* diveset = *divesetptr; 815 816 assert(diveset != NULL); 817 assert(diveset->name != NULL); 818 assert(diveset->randnumgen != NULL); 819 820 SCIPrandomFree(&diveset->randnumgen, blkmem); 821 822 /* free all diveset statistics */ 823 for( c = 0; c < 4; ++c ) 824 { 825 SCIP_DIVESETSTATS** divesetstatsptr = &diveset->divesetstats[c]; 826 BMSfreeBlockMemory(blkmem, divesetstatsptr); 827 } 828 829 BMSfreeMemoryArray(&diveset->name); 830 BMSfreeBlockMemory(blkmem, divesetptr); 831 } 832 833 /** get the candidate score and preferred rounding direction for a candidate variable */ 834 SCIP_RETCODE SCIPdivesetGetScore( 835 SCIP_DIVESET* diveset, /**< general diving settings */ 836 SCIP_SET* set, /**< SCIP settings */ 837 SCIP_DIVETYPE divetype, /**< the type of diving that should be applied */ 838 SCIP_VAR* divecand, /**< the candidate for which the branching direction is requested */ 839 SCIP_Real divecandsol, /**< LP solution value of the candidate */ 840 SCIP_Real divecandfrac, /**< fractionality of the candidate */ 841 SCIP_Real* candscore, /**< pointer to store the candidate score */ 842 SCIP_Bool* roundup /**< pointer to store whether preferred direction for diving is upwards */ 843 ) 844 { 845 assert(diveset->divesetgetscore != NULL); 846 assert(candscore != NULL); 847 assert(roundup != NULL); 848 assert(divecand != NULL); 849 assert(divetype & diveset->divetypemask); 850 851 SCIP_CALL( diveset->divesetgetscore(set->scip, diveset, divetype, divecand, divecandsol, divecandfrac, 852 candscore, roundup) ); 853 854 return SCIP_OKAY; 855 } 856 857 /** check specific preconditions for diving, e.g., if an incumbent solution is available */ 858 SCIP_RETCODE SCIPdivesetIsAvailable( 859 SCIP_DIVESET* diveset, /**< diving heuristic settings */ 860 SCIP_SET* set, /**< SCIP settings */ 861 SCIP_Bool* available /**< pointer to store if the diving can run at the current solving stage */ 862 ) 863 { 864 assert(set != NULL); 865 assert(diveset != NULL); 866 assert(available != NULL); 867 868 if( diveset->divesetavailable == NULL ) 869 *available = TRUE; 870 else 871 { 872 *available = FALSE; 873 SCIP_CALL( diveset->divesetavailable(set->scip, diveset, available) ); 874 } 875 876 return SCIP_OKAY; 877 } 878 879 880 881 /** copies the given primal heuristic to a new scip */ 882 SCIP_RETCODE SCIPheurCopyInclude( 883 SCIP_HEUR* heur, /**< primal heuristic */ 884 SCIP_SET* set /**< SCIP_SET of SCIP to copy to */ 885 ) 886 { 887 assert(heur != NULL); 888 assert(set != NULL); 889 assert(set->scip != NULL); 890 891 if( heur->heurcopy != NULL ) 892 { 893 SCIPsetDebugMsg(set, "including heur %s in subscip %p\n", SCIPheurGetName(heur), (void*)set->scip); 894 SCIP_CALL( heur->heurcopy(set->scip, heur) ); 895 } 896 897 return SCIP_OKAY; 898 } 899 900 /** internal method for creating a primal heuristic */ 901 static 902 SCIP_RETCODE doHeurCreate( 903 SCIP_HEUR** heur, /**< pointer to primal heuristic data structure */ 904 SCIP_SET* set, /**< global SCIP settings */ 905 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 906 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */ 907 const char* name, /**< name of primal heuristic */ 908 const char* desc, /**< description of primal heuristic */ 909 char dispchar, /**< display character of primal heuristic */ 910 int priority, /**< priority of the primal heuristic */ 911 int freq, /**< frequency for calling primal heuristic */ 912 int freqofs, /**< frequency offset for calling primal heuristic */ 913 int maxdepth, /**< maximal depth level to call heuristic at (-1: no limit) */ 914 SCIP_HEURTIMING timingmask, /**< positions in the node solving loop where heuristic should be executed */ 915 SCIP_Bool usessubscip, /**< does the heuristic use a secondary SCIP instance? */ 916 SCIP_DECL_HEURCOPY ((*heurcopy)), /**< copy method of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */ 917 SCIP_DECL_HEURFREE ((*heurfree)), /**< destructor of primal heuristic */ 918 SCIP_DECL_HEURINIT ((*heurinit)), /**< initialize primal heuristic */ 919 SCIP_DECL_HEUREXIT ((*heurexit)), /**< deinitialize primal heuristic */ 920 SCIP_DECL_HEURINITSOL ((*heurinitsol)), /**< solving process initialization method of primal heuristic */ 921 SCIP_DECL_HEUREXITSOL ((*heurexitsol)), /**< solving process deinitialization method of primal heuristic */ 922 SCIP_DECL_HEUREXEC ((*heurexec)), /**< execution method of primal heuristic */ 923 SCIP_HEURDATA* heurdata /**< primal heuristic data */ 924 ) 925 { 926 char paramname[SCIP_MAXSTRLEN]; 927 char paramdesc[SCIP_MAXSTRLEN]; 928 929 assert(heur != NULL); 930 assert(name != NULL); 931 assert(desc != NULL); 932 assert(freq >= -1); 933 assert(freqofs >= 0); 934 assert(heurexec != NULL); 935 936 SCIP_ALLOC( BMSallocMemory(heur) ); 937 BMSclearMemory(*heur); 938 939 SCIP_ALLOC( BMSduplicateMemoryArray(&(*heur)->name, name, strlen(name)+1) ); 940 SCIP_ALLOC( BMSduplicateMemoryArray(&(*heur)->desc, desc, strlen(desc)+1) ); 941 (*heur)->dispchar = dispchar; 942 (*heur)->priority = priority; 943 (*heur)->freq = freq; 944 (*heur)->freqofs = freqofs; 945 (*heur)->maxdepth = maxdepth; 946 (*heur)->delaypos = -1; 947 (*heur)->timingmask = timingmask; 948 (*heur)->usessubscip = usessubscip; 949 (*heur)->heurcopy = heurcopy; 950 (*heur)->heurfree = heurfree; 951 (*heur)->heurinit = heurinit; 952 (*heur)->heurexit = heurexit; 953 (*heur)->heurinitsol = heurinitsol; 954 (*heur)->heurexitsol = heurexitsol; 955 (*heur)->heurexec = heurexec; 956 (*heur)->heurdata = heurdata; 957 SCIP_CALL( SCIPclockCreate(&(*heur)->setuptime, SCIP_CLOCKTYPE_DEFAULT) ); 958 SCIP_CALL( SCIPclockCreate(&(*heur)->heurclock, SCIP_CLOCKTYPE_DEFAULT) ); 959 (*heur)->ncalls = 0; 960 (*heur)->nsolsfound = 0; 961 (*heur)->nbestsolsfound = 0; 962 (*heur)->initialized = FALSE; 963 (*heur)->divesets = NULL; 964 (*heur)->ndivesets = 0; 965 966 /* add parameters */ 967 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/priority", name); 968 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of heuristic <%s>", name); 969 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc, 970 &(*heur)->priority, TRUE, priority, INT_MIN/4, INT_MAX/4, 971 paramChgdHeurPriority, (SCIP_PARAMDATA*)(*heur)) ); /*lint !e740*/ 972 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/freq", name); 973 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "frequency for calling primal heuristic <%s> (-1: never, 0: only at depth freqofs)", name); 974 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc, 975 &(*heur)->freq, FALSE, freq, -1, SCIP_MAXTREEDEPTH, NULL, NULL) ); 976 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/freqofs", name); 977 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "frequency offset for calling primal heuristic <%s>", name); 978 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc, 979 &(*heur)->freqofs, FALSE, freqofs, 0, SCIP_MAXTREEDEPTH, NULL, NULL) ); 980 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdepth", name); 981 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "maximal depth level to call primal heuristic <%s> (-1: no limit)", name); 982 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc, 983 &(*heur)->maxdepth, TRUE, maxdepth, -1, SCIP_MAXTREEDEPTH, NULL, NULL) ); 984 985 return SCIP_OKAY; 986 } 987 988 /** creates a primal heuristic */ 989 SCIP_RETCODE SCIPheurCreate( 990 SCIP_HEUR** heur, /**< pointer to primal heuristic data structure */ 991 SCIP_SET* set, /**< global SCIP settings */ 992 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 993 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */ 994 const char* name, /**< name of primal heuristic */ 995 const char* desc, /**< description of primal heuristic */ 996 char dispchar, /**< display character of primal heuristic */ 997 int priority, /**< priority of the primal heuristic */ 998 int freq, /**< frequency for calling primal heuristic */ 999 int freqofs, /**< frequency offset for calling primal heuristic */ 1000 int maxdepth, /**< maximal depth level to call heuristic at (-1: no limit) */ 1001 SCIP_HEURTIMING timingmask, /**< positions in the node solving loop where heuristic should be executed */ 1002 SCIP_Bool usessubscip, /**< does the heuristic use a secondary SCIP instance? */ 1003 SCIP_DECL_HEURCOPY ((*heurcopy)), /**< copy method of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */ 1004 SCIP_DECL_HEURFREE ((*heurfree)), /**< destructor of primal heuristic */ 1005 SCIP_DECL_HEURINIT ((*heurinit)), /**< initialize primal heuristic */ 1006 SCIP_DECL_HEUREXIT ((*heurexit)), /**< deinitialize primal heuristic */ 1007 SCIP_DECL_HEURINITSOL ((*heurinitsol)), /**< solving process initialization method of primal heuristic */ 1008 SCIP_DECL_HEUREXITSOL ((*heurexitsol)), /**< solving process deinitialization method of primal heuristic */ 1009 SCIP_DECL_HEUREXEC ((*heurexec)), /**< execution method of primal heuristic */ 1010 SCIP_HEURDATA* heurdata /**< primal heuristic data */ 1011 ) 1012 { 1013 assert(heur != NULL); 1014 assert(name != NULL); 1015 assert(desc != NULL); 1016 assert(freq >= -1); 1017 assert(freqofs >= 0); 1018 assert(heurexec != NULL); 1019 1020 SCIP_CALL_FINALLY( doHeurCreate(heur, set, messagehdlr, blkmem, name, desc, dispchar, priority, freq, freqofs, 1021 maxdepth, timingmask, usessubscip, heurcopy, heurfree, heurinit, heurexit, heurinitsol, heurexitsol, heurexec, 1022 heurdata), (void) SCIPheurFree(heur, set, blkmem) ); 1023 1024 return SCIP_OKAY; 1025 } 1026 1027 /** calls destructor and frees memory of primal heuristic */ 1028 SCIP_RETCODE SCIPheurFree( 1029 SCIP_HEUR** heur, /**< pointer to primal heuristic data structure */ 1030 SCIP_SET* set, /**< global SCIP settings */ 1031 BMS_BLKMEM* blkmem /**< block memory */ 1032 ) 1033 { 1034 int d; 1035 assert(heur != NULL); 1036 if( *heur == NULL ) 1037 return SCIP_OKAY; 1038 assert(!(*heur)->initialized); 1039 assert(set != NULL); 1040 assert((*heur)->divesets != NULL || (*heur)->ndivesets == 0); 1041 1042 /* call destructor of primal heuristic */ 1043 if( (*heur)->heurfree != NULL ) 1044 { 1045 SCIP_CALL( (*heur)->heurfree(set->scip, *heur) ); 1046 } 1047 1048 for( d = 0; d < (*heur)->ndivesets; ++d ) 1049 { 1050 assert((*heur)->divesets[d] != NULL); 1051 divesetFree(&((*heur)->divesets[d]), blkmem); 1052 } 1053 BMSfreeMemoryArrayNull(&(*heur)->divesets); 1054 SCIPclockFree(&(*heur)->heurclock); 1055 SCIPclockFree(&(*heur)->setuptime); 1056 BMSfreeMemoryArrayNull(&(*heur)->name); 1057 BMSfreeMemoryArrayNull(&(*heur)->desc); 1058 BMSfreeMemory(heur); 1059 1060 return SCIP_OKAY; 1061 } 1062 1063 /** initializes primal heuristic */ 1064 SCIP_RETCODE SCIPheurInit( 1065 SCIP_HEUR* heur, /**< primal heuristic */ 1066 SCIP_SET* set /**< global SCIP settings */ 1067 ) 1068 { 1069 int d; 1070 assert(heur != NULL); 1071 assert(set != NULL); 1072 1073 if( heur->initialized ) 1074 { 1075 SCIPerrorMessage("primal heuristic <%s> already initialized\n", heur->name); 1076 return SCIP_INVALIDCALL; 1077 } 1078 1079 if( set->misc_resetstat ) 1080 { 1081 SCIPclockReset(heur->setuptime); 1082 SCIPclockReset(heur->heurclock); 1083 1084 heur->delaypos = -1; 1085 heur->ncalls = 0; 1086 heur->nsolsfound = 0; 1087 heur->nbestsolsfound = 0; 1088 1089 set->heurssorted = FALSE; 1090 set->heursnamesorted = FALSE; 1091 } 1092 1093 if( heur->heurinit != NULL ) 1094 { 1095 /* start timing */ 1096 SCIPclockStart(heur->setuptime, set); 1097 1098 SCIP_CALL( heur->heurinit(set->scip, heur) ); 1099 1100 /* stop timing */ 1101 SCIPclockStop(heur->setuptime, set); 1102 } 1103 1104 /* reset dive sets */ 1105 for( d = 0; d < heur->ndivesets; ++d ) 1106 { 1107 assert(heur->divesets[d] != NULL); 1108 SCIP_CALL( SCIPdivesetReset(heur->divesets[d], set) ); 1109 } 1110 1111 heur->initialized = TRUE; 1112 1113 return SCIP_OKAY; 1114 } 1115 1116 /** calls exit method of primal heuristic */ 1117 SCIP_RETCODE SCIPheurExit( 1118 SCIP_HEUR* heur, /**< primal heuristic */ 1119 SCIP_SET* set /**< global SCIP settings */ 1120 ) 1121 { 1122 assert(heur != NULL); 1123 assert(set != NULL); 1124 1125 if( !heur->initialized ) 1126 { 1127 SCIPerrorMessage("primal heuristic <%s> not initialized\n", heur->name); 1128 return SCIP_INVALIDCALL; 1129 } 1130 1131 if( heur->heurexit != NULL ) 1132 { 1133 /* start timing */ 1134 SCIPclockStart(heur->setuptime, set); 1135 1136 SCIP_CALL( heur->heurexit(set->scip, heur) ); 1137 1138 /* stop timing */ 1139 SCIPclockStop(heur->setuptime, set); 1140 } 1141 heur->initialized = FALSE; 1142 1143 return SCIP_OKAY; 1144 } 1145 1146 /** informs primal heuristic that the branch and bound process is being started */ 1147 SCIP_RETCODE SCIPheurInitsol( 1148 SCIP_HEUR* heur, /**< primal heuristic */ 1149 SCIP_SET* set /**< global SCIP settings */ 1150 ) 1151 { 1152 assert(heur != NULL); 1153 assert(set != NULL); 1154 1155 if( heur->delaypos != -1 ) 1156 { 1157 heur->delaypos = -1; 1158 set->heurssorted = FALSE; 1159 } 1160 1161 /* call solving process initialization method of primal heuristic */ 1162 if( heur->heurinitsol != NULL ) 1163 { 1164 /* start timing */ 1165 SCIPclockStart(heur->setuptime, set); 1166 1167 SCIP_CALL( heur->heurinitsol(set->scip, heur) ); 1168 1169 /* stop timing */ 1170 SCIPclockStop(heur->setuptime, set); 1171 } 1172 1173 return SCIP_OKAY; 1174 } 1175 1176 /** informs primal heuristic that the branch and bound process data is being freed */ 1177 SCIP_RETCODE SCIPheurExitsol( 1178 SCIP_HEUR* heur, /**< primal heuristic */ 1179 SCIP_SET* set /**< global SCIP settings */ 1180 ) 1181 { 1182 assert(heur != NULL); 1183 assert(set != NULL); 1184 1185 /* call solving process deinitialization method of primal heuristic */ 1186 if( heur->heurexitsol != NULL ) 1187 { 1188 /* start timing */ 1189 SCIPclockStart(heur->setuptime, set); 1190 1191 SCIP_CALL( heur->heurexitsol(set->scip, heur) ); 1192 1193 /* stop timing */ 1194 SCIPclockStop(heur->setuptime, set); 1195 } 1196 1197 return SCIP_OKAY; 1198 } 1199 1200 /** should the heuristic be executed at the given depth, frequency, timing, ... */ 1201 SCIP_Bool SCIPheurShouldBeExecuted( 1202 SCIP_HEUR* heur, /**< primal heuristic */ 1203 int depth, /**< depth of current node */ 1204 int lpstateforkdepth, /**< depth of the last node with solved LP */ 1205 SCIP_HEURTIMING heurtiming, /**< current point in the node solving process */ 1206 SCIP_Bool* delayed /**< pointer to store whether the heuristic should be delayed */ 1207 ) 1208 { 1209 SCIP_Bool execute; 1210 1211 if( ((heur->timingmask & SCIP_HEURTIMING_BEFOREPRESOL) && heurtiming == SCIP_HEURTIMING_BEFOREPRESOL) 1212 || ((heur->timingmask & SCIP_HEURTIMING_DURINGPRESOLLOOP) && heurtiming == SCIP_HEURTIMING_DURINGPRESOLLOOP) ) 1213 { 1214 /* heuristic may be executed before/during presolving. Do so, if it was not disabled by setting the frequency to -1 */ 1215 execute = heur->freq >= 0; 1216 } 1217 else if( (heur->timingmask & SCIP_HEURTIMING_AFTERPSEUDONODE) == 0 1218 && (heurtiming == SCIP_HEURTIMING_AFTERLPNODE || heurtiming == SCIP_HEURTIMING_AFTERLPPLUNGE) ) 1219 { 1220 /* heuristic was skipped on intermediate pseudo nodes: check, if a node matching the execution frequency lies 1221 * between the current node and the last LP node of the path 1222 */ 1223 execute = (heur->freq > 0 && depth >= heur->freqofs 1224 && ((depth + heur->freq - heur->freqofs) / heur->freq 1225 != (lpstateforkdepth + heur->freq - heur->freqofs) / heur->freq)); 1226 } 1227 else 1228 { 1229 /* heuristic may be executed on every node: check, if the current depth matches the execution frequency and offset */ 1230 execute = (heur->freq > 0 && depth >= heur->freqofs && (depth - heur->freqofs) % heur->freq == 0); 1231 } 1232 1233 /* if frequency is zero, execute heuristic only at the depth level of the frequency offset */ 1234 execute = execute || (depth == heur->freqofs && heur->freq == 0); 1235 1236 /* compare current depth against heuristic's maximal depth level */ 1237 execute = execute && (heur->maxdepth == -1 || depth <= heur->maxdepth); 1238 1239 /* if the heuristic was delayed, execute it anyway */ 1240 execute = execute || (heur->delaypos >= 0); 1241 1242 /* if the heuristic should be called after plunging but not during plunging, delay it if we are in plunging */ 1243 if( execute 1244 && ((heurtiming == SCIP_HEURTIMING_AFTERLPNODE 1245 && (heur->timingmask & SCIP_HEURTIMING_AFTERLPNODE) == 0 1246 && (heur->timingmask & SCIP_HEURTIMING_AFTERLPPLUNGE) > 0) 1247 || (heurtiming == SCIP_HEURTIMING_AFTERPSEUDONODE 1248 && (heur->timingmask & SCIP_HEURTIMING_AFTERPSEUDONODE) == 0 1249 && (heur->timingmask & SCIP_HEURTIMING_AFTERPSEUDOPLUNGE) > 0)) ) 1250 { 1251 /* the heuristic should be delayed until plunging is finished */ 1252 execute = FALSE; 1253 *delayed = TRUE; 1254 } 1255 1256 /* execute heuristic only if its timing mask fits the current point in the node solving process */ 1257 execute = execute && (heur->timingmask & heurtiming) > 0; 1258 1259 return execute; 1260 } 1261 1262 /** calls execution method of primal heuristic */ 1263 SCIP_RETCODE SCIPheurExec( 1264 SCIP_HEUR* heur, /**< primal heuristic */ 1265 SCIP_SET* set, /**< global SCIP settings */ 1266 SCIP_PRIMAL* primal, /**< primal data */ 1267 int depth, /**< depth of current node */ 1268 int lpstateforkdepth, /**< depth of the last node with solved LP */ 1269 SCIP_HEURTIMING heurtiming, /**< current point in the node solving process */ 1270 SCIP_Bool nodeinfeasible, /**< was the current node already detected to be infeasible? */ 1271 int* ndelayedheurs, /**< pointer to count the number of delayed heuristics */ 1272 SCIP_RESULT* result /**< pointer to store the result of the callback method */ 1273 ) 1274 { 1275 SCIP_Bool execute; 1276 SCIP_Bool delayed; 1277 1278 assert(heur != NULL); 1279 assert(heur->heurexec != NULL); 1280 assert(heur->freq >= -1); 1281 assert(heur->freqofs >= 0); 1282 assert(heur->maxdepth >= -1); 1283 assert(set != NULL); 1284 assert(set->scip != NULL); 1285 assert(primal != NULL); 1286 assert(depth >= 0 || heurtiming == SCIP_HEURTIMING_BEFOREPRESOL || heurtiming == SCIP_HEURTIMING_DURINGPRESOLLOOP); 1287 assert(ndelayedheurs != NULL); 1288 assert(result != NULL); 1289 1290 *result = SCIP_DIDNOTRUN; 1291 1292 delayed = FALSE; 1293 execute = SCIPheurShouldBeExecuted(heur, depth, lpstateforkdepth, heurtiming, &delayed); 1294 1295 if( delayed ) 1296 { 1297 assert(!execute); 1298 *result = SCIP_DELAYED; 1299 } 1300 1301 if( execute ) 1302 { 1303 SCIP_Longint oldnsolsfound; 1304 SCIP_Longint oldnbestsolsfound; 1305 1306 SCIPsetDebugMsg(set, "executing primal heuristic <%s> in depth %d (delaypos: %d)\n", heur->name, depth, heur->delaypos); 1307 1308 oldnsolsfound = primal->nsolsfound; 1309 oldnbestsolsfound = primal->nbestsolsfound; 1310 1311 /* start timing */ 1312 SCIPclockStart(heur->heurclock, set); 1313 1314 /* call external method */ 1315 SCIP_CALL( heur->heurexec(set->scip, heur, heurtiming, nodeinfeasible, result) ); 1316 1317 /* stop timing */ 1318 SCIPclockStop(heur->heurclock, set); 1319 1320 /* evaluate result */ 1321 if( *result != SCIP_FOUNDSOL 1322 && *result != SCIP_DIDNOTFIND 1323 && *result != SCIP_DIDNOTRUN 1324 && *result != SCIP_DELAYED 1325 && *result != SCIP_UNBOUNDED ) 1326 { 1327 SCIPerrorMessage("execution method of primal heuristic <%s> returned invalid result <%d>\n", 1328 heur->name, *result); 1329 return SCIP_INVALIDRESULT; 1330 } 1331 if( *result != SCIP_DIDNOTRUN && *result != SCIP_DELAYED ) 1332 heur->ncalls++; 1333 heur->nsolsfound += primal->nsolsfound - oldnsolsfound; 1334 heur->nbestsolsfound += primal->nbestsolsfound - oldnbestsolsfound; 1335 1336 /* update delay position of heuristic */ 1337 if( *result != SCIP_DELAYED && heur->delaypos != -1 ) 1338 { 1339 heur->delaypos = -1; 1340 set->heurssorted = FALSE; 1341 } 1342 } 1343 assert(*result == SCIP_DIDNOTRUN || *result == SCIP_DELAYED || *result == SCIP_UNBOUNDED || heur->delaypos == -1); 1344 1345 /* check if the heuristic was (still) delayed */ 1346 if( *result == SCIP_DELAYED || heur->delaypos >= 0 ) 1347 { 1348 SCIPsetDebugMsg(set, "delaying execution of primal heuristic <%s> in depth %d (delaypos: %d), heur was%s delayed before, had delaypos %d\n", 1349 heur->name, depth, *ndelayedheurs, heur->delaypos >= 0 ? "" : " not", heur->delaypos); 1350 1351 /* mark the heuristic delayed */ 1352 if( heur->delaypos != *ndelayedheurs ) 1353 { 1354 heur->delaypos = *ndelayedheurs; 1355 set->heurssorted = FALSE; 1356 } 1357 (*ndelayedheurs)++; 1358 } 1359 1360 return SCIP_OKAY; 1361 } 1362 1363 /** gets user data of primal heuristic */ 1364 SCIP_HEURDATA* SCIPheurGetData( 1365 SCIP_HEUR* heur /**< primal heuristic */ 1366 ) 1367 { 1368 assert(heur != NULL); 1369 1370 return heur->heurdata; 1371 } 1372 1373 /** sets user data of primal heuristic; user has to free old data in advance! */ 1374 void SCIPheurSetData( 1375 SCIP_HEUR* heur, /**< primal heuristic */ 1376 SCIP_HEURDATA* heurdata /**< new primal heuristic user data */ 1377 ) 1378 { 1379 assert(heur != NULL); 1380 1381 heur->heurdata = heurdata; 1382 } 1383 1384 /* new callback setter methods */ 1385 1386 /** sets copy callback of primal heuristic */ 1387 void SCIPheurSetCopy( 1388 SCIP_HEUR* heur, /**< primal heuristic */ 1389 SCIP_DECL_HEURCOPY ((*heurcopy)) /**< copy callback of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */ 1390 ) 1391 { 1392 assert(heur != NULL); 1393 1394 heur->heurcopy = heurcopy; 1395 } 1396 1397 /** sets destructor callback of primal heuristic */ 1398 void SCIPheurSetFree( 1399 SCIP_HEUR* heur, /**< primal heuristic */ 1400 SCIP_DECL_HEURFREE ((*heurfree)) /**< destructor of primal heuristic */ 1401 ) 1402 { 1403 assert(heur != NULL); 1404 1405 heur->heurfree = heurfree; 1406 } 1407 1408 /** sets initialization callback of primal heuristic */ 1409 void SCIPheurSetInit( 1410 SCIP_HEUR* heur, /**< primal heuristic */ 1411 SCIP_DECL_HEURINIT ((*heurinit)) /**< initialize primal heuristic */ 1412 ) 1413 { 1414 assert(heur != NULL); 1415 1416 heur->heurinit = heurinit; 1417 } 1418 1419 /** sets deinitialization callback of primal heuristic */ 1420 void SCIPheurSetExit( 1421 SCIP_HEUR* heur, /**< primal heuristic */ 1422 SCIP_DECL_HEUREXIT ((*heurexit)) /**< deinitialize primal heuristic */ 1423 ) 1424 { 1425 assert(heur != NULL); 1426 1427 heur->heurexit = heurexit; 1428 } 1429 1430 /** sets solving process initialization callback of primal heuristic */ 1431 void SCIPheurSetInitsol( 1432 SCIP_HEUR* heur, /**< primal heuristic */ 1433 SCIP_DECL_HEURINITSOL ((*heurinitsol)) /**< solving process initialization callback of primal heuristic */ 1434 ) 1435 { 1436 assert(heur != NULL); 1437 1438 heur->heurinitsol = heurinitsol; 1439 } 1440 1441 /** sets solving process deinitialization callback of primal heuristic */ 1442 void SCIPheurSetExitsol( 1443 SCIP_HEUR* heur, /**< primal heuristic */ 1444 SCIP_DECL_HEUREXITSOL ((*heurexitsol)) /**< solving process deinitialization callback of primal heuristic */ 1445 ) 1446 { 1447 assert(heur != NULL); 1448 1449 heur->heurexitsol = heurexitsol; 1450 } 1451 1452 /** gets name of primal heuristic */ 1453 const char* SCIPheurGetName( 1454 SCIP_HEUR* heur /**< primal heuristic */ 1455 ) 1456 { 1457 assert(heur != NULL); 1458 1459 return heur->name; 1460 } 1461 1462 /** gets description of primal heuristic */ 1463 const char* SCIPheurGetDesc( 1464 SCIP_HEUR* heur /**< primal heuristic */ 1465 ) 1466 { 1467 assert(heur != NULL); 1468 1469 return heur->desc; 1470 } 1471 1472 /** gets display character of primal heuristic */ 1473 char SCIPheurGetDispchar( 1474 SCIP_HEUR* heur /**< primal heuristic */ 1475 ) 1476 { 1477 assert(heur != NULL); 1478 1479 return heur->dispchar; 1480 } 1481 1482 /** returns the timing mask of the heuristic */ 1483 SCIP_HEURTIMING SCIPheurGetTimingmask( 1484 SCIP_HEUR* heur /**< primal heuristic */ 1485 ) 1486 { 1487 assert(heur != NULL); 1488 1489 return heur->timingmask; 1490 } 1491 1492 /** sets new timing mask for heuristic */ 1493 void SCIPheurSetTimingmask( 1494 SCIP_HEUR* heur, /**< primal heuristic */ 1495 SCIP_HEURTIMING timingmask /**< new timing mask of heuristic */ 1496 ) 1497 { 1498 assert(heur != NULL); 1499 1500 heur->timingmask = timingmask; 1501 } 1502 1503 /** does the heuristic use a secondary SCIP instance? */ 1504 SCIP_Bool SCIPheurUsesSubscip( 1505 SCIP_HEUR* heur /**< primal heuristic */ 1506 ) 1507 { 1508 assert(heur != NULL); 1509 1510 return heur->usessubscip; 1511 } 1512 1513 /** gets priority of primal heuristic */ 1514 int SCIPheurGetPriority( 1515 SCIP_HEUR* heur /**< primal heuristic */ 1516 ) 1517 { 1518 assert(heur != NULL); 1519 1520 return heur->priority; 1521 } 1522 1523 /** sets priority of primal heuristic */ 1524 void SCIPheurSetPriority( 1525 SCIP_HEUR* heur, /**< primal heuristic */ 1526 SCIP_SET* set, /**< global SCIP settings */ 1527 int priority /**< new priority of the primal heuristic */ 1528 ) 1529 { 1530 assert(heur != NULL); 1531 assert(set != NULL); 1532 1533 heur->priority = priority; 1534 set->heurssorted = FALSE; 1535 } 1536 1537 /** gets frequency of primal heuristic */ 1538 int SCIPheurGetFreq( 1539 SCIP_HEUR* heur /**< primal heuristic */ 1540 ) 1541 { 1542 assert(heur != NULL); 1543 1544 return heur->freq; 1545 } 1546 1547 /** sets frequency of primal heuristic */ 1548 void SCIPheurSetFreq( 1549 SCIP_HEUR* heur, /**< primal heuristic */ 1550 int freq /**< new frequency of heuristic */ 1551 ) 1552 { 1553 assert(heur != NULL); 1554 1555 heur->freq = freq; 1556 } 1557 1558 /** gets frequency offset of primal heuristic */ 1559 int SCIPheurGetFreqofs( 1560 SCIP_HEUR* heur /**< primal heuristic */ 1561 ) 1562 { 1563 assert(heur != NULL); 1564 1565 return heur->freqofs; 1566 } 1567 1568 /** gets maximal depth level for calling primal heuristic (returns -1, if no depth limit exists) */ 1569 int SCIPheurGetMaxdepth( 1570 SCIP_HEUR* heur /**< primal heuristic */ 1571 ) 1572 { 1573 assert(heur != NULL); 1574 1575 return heur->maxdepth; 1576 } 1577 1578 /** gets the number of times, the heuristic was called and tried to find a solution */ 1579 SCIP_Longint SCIPheurGetNCalls( 1580 SCIP_HEUR* heur /**< primal heuristic */ 1581 ) 1582 { 1583 assert(heur != NULL); 1584 1585 return heur->ncalls; 1586 } 1587 1588 /** gets the number of primal feasible solutions found by this heuristic */ 1589 SCIP_Longint SCIPheurGetNSolsFound( 1590 SCIP_HEUR* heur /**< primal heuristic */ 1591 ) 1592 { 1593 assert(heur != NULL); 1594 1595 return heur->nsolsfound; 1596 } 1597 1598 /** gets the number of new best primal feasible solutions found by this heuristic */ 1599 SCIP_Longint SCIPheurGetNBestSolsFound( 1600 SCIP_HEUR* heur /**< primal heuristic */ 1601 ) 1602 { 1603 assert(heur != NULL); 1604 1605 return heur->nbestsolsfound; 1606 } 1607 1608 /** is primal heuristic initialized? */ 1609 SCIP_Bool SCIPheurIsInitialized( 1610 SCIP_HEUR* heur /**< primal heuristic */ 1611 ) 1612 { 1613 assert(heur != NULL); 1614 1615 return heur->initialized; 1616 } 1617 1618 /** enables or disables all clocks of \p heur, depending on the value of the flag */ 1619 void SCIPheurEnableOrDisableClocks( 1620 SCIP_HEUR* heur, /**< the heuristic for which all clocks should be enabled or disabled */ 1621 SCIP_Bool enable /**< should the clocks of the heuristic be enabled? */ 1622 ) 1623 { 1624 assert(heur != NULL); 1625 1626 SCIPclockEnableOrDisable(heur->setuptime, enable); 1627 SCIPclockEnableOrDisable(heur->heurclock, enable); 1628 } 1629 1630 /** gets time in seconds used in this heuristic for setting up for next stages */ 1631 SCIP_Real SCIPheurGetSetupTime( 1632 SCIP_HEUR* heur /**< primal heuristic */ 1633 ) 1634 { 1635 assert(heur != NULL); 1636 1637 return SCIPclockGetTime(heur->setuptime); 1638 } 1639 1640 /** gets time in seconds used in this heuristic */ 1641 SCIP_Real SCIPheurGetTime( 1642 SCIP_HEUR* heur /**< primal heuristic */ 1643 ) 1644 { 1645 assert(heur != NULL); 1646 1647 return SCIPclockGetTime(heur->heurclock); 1648 } 1649 1650 /** returns array of divesets of this primal heuristic, or NULL if it has no divesets */ 1651 SCIP_DIVESET** SCIPheurGetDivesets( 1652 SCIP_HEUR* heur /**< primal heuristic */ 1653 ) 1654 { 1655 assert(heur != NULL); 1656 1657 return heur->divesets; 1658 } 1659 1660 /** returns the number of divesets of this primal heuristic */ 1661 int SCIPheurGetNDivesets( 1662 SCIP_HEUR* heur /**< primal heuristic */ 1663 ) 1664 { 1665 assert(heur != NULL); 1666 1667 return heur->ndivesets; 1668 } 1669 1670 /** Perform breadth-first (BFS) search on the variable constraint graph. 1671 * 1672 * The result of the algorithm is that the \p distances array contains the correct distances for 1673 * every variable from the start variables. The distance of a variable can then be accessed through its 1674 * problem index (calling SCIPvarGetProbindex()). 1675 * Hence, The method assumes that the length of \p distances is at least 1676 * SCIPgetNVars(). 1677 * Variables that are not connected through constraints to the start variables have a distance of -1. 1678 * 1679 * Limits can be provided to further restrict the breadth-first search. If a distance limit is given, 1680 * the search will be performed until the first variable at this distance is popped from the queue, i.e., 1681 * all variables with a distance < maxdistance have been labeled by the search. 1682 * If a variable limit is given, the search stops after it completes the distance level at which 1683 * the limit was reached. Hence, more variables may be actually labeled. 1684 * The start variables are accounted for those variable limits. 1685 * 1686 * If no variable variable constraint graph is provided, the method will create one and free it at the end 1687 * This is useful for a single use of the variable constraint graph. For several consecutive uses, 1688 * it is advised to create a variable constraint graph via SCIPvariableGraphCreate(). 1689 */ 1690 SCIP_RETCODE SCIPvariablegraphBreadthFirst( 1691 SCIP* scip, /**< SCIP data structure */ 1692 SCIP_VGRAPH* vargraph, /**< pointer to the variable graph, or NULL to let the function create a local graph */ 1693 SCIP_VAR** startvars, /**< array of start variables to calculate distance from */ 1694 int nstartvars, /**< number of starting variables, at least 1 */ 1695 int* distances, /**< array to keep distance in vargraph from start variables for every variable */ 1696 int maxdistance, /**< maximum distance >= 0 from start variable (INT_MAX for complete BFS) */ 1697 int maxvars, /**< maximum number of variables to compute distance for */ 1698 int maxbinintvars /**< maximum number of binary or integer variables to compute distance for */ 1699 ) 1700 { 1701 SCIP_VAR** vars; 1702 1703 int* queue; 1704 int nvars; 1705 int i; 1706 int currlvlidx; 1707 int nextlvlidx; 1708 int increment = 1; 1709 int currentdistance; 1710 int nbinintvarshit; 1711 int nvarshit; 1712 int nbinvars; 1713 int nintvars; 1714 int nbinintvars; 1715 SCIP_VAR** varbuffer; 1716 SCIP_Bool localvargraph; 1717 1718 assert(scip != NULL); 1719 assert(startvars != NULL); 1720 assert(nstartvars >= 1); 1721 assert(distances != NULL); 1722 assert(maxdistance >= 0); 1723 1724 /* get variable data */ 1725 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) ); 1726 1727 if( nvars == 0 ) 1728 return SCIP_OKAY; 1729 1730 nbinintvars = nbinvars + nintvars; 1731 1732 SCIP_CALL( SCIPallocBufferArray(scip, &queue, nvars) ); 1733 SCIP_CALL( SCIPallocClearBufferArray(scip, &varbuffer, nvars) ); 1734 1735 /* create a variable graph locally for this method, if none is provided */ 1736 if( vargraph == NULL ) 1737 { 1738 SCIP_CALL( SCIPvariableGraphCreate(scip, &vargraph, FALSE, 1.0, NULL) ); 1739 localvargraph = TRUE; 1740 } 1741 else 1742 localvargraph = FALSE; 1743 1744 SCIPhashtableRemoveAll(vargraph->visitedconss); 1745 1746 /* initialize distances to -1 */ 1747 for( i = 0; i < nvars; ++i ) 1748 { 1749 queue[i] = -1; 1750 distances[i] = -1; 1751 } 1752 1753 nvarshit = 0; 1754 nbinintvarshit = 0; 1755 /* initialize distances for starting variables and add them to the queue */ 1756 for( i = 0; i < nstartvars; ++i ) 1757 { 1758 int probindex = SCIPvarGetProbindex(startvars[i]); 1759 assert(probindex >= 0); 1760 /* start variables have a distance of 0 */ 1761 distances[probindex] = 0; 1762 queue[i] = probindex; 1763 nvarshit++; 1764 1765 if( probindex < nbinintvars ) 1766 nbinintvarshit++; 1767 } 1768 currlvlidx = 0; 1769 nextlvlidx = nvars - 1; 1770 1771 /* loop over the queue and pop the next variable, starting with start variables */ 1772 do 1773 { 1774 SCIP_VAR* currvar; 1775 int c; 1776 int varpos; 1777 1778 currvar = vars[queue[currlvlidx]]; 1779 varpos = SCIPvarGetProbindex(currvar); 1780 currentdistance = distances[varpos]; 1781 assert(currentdistance >= 0); 1782 1783 /* distances must only be computed up to maxdistance */ 1784 assert(currentdistance <= maxdistance); 1785 1786 /* check for termination because maximum distance has been reached */ 1787 if( currentdistance == maxdistance ) 1788 break; 1789 1790 assert(varpos >= 0); 1791 1792 /* loop over variable constraints and enqueue variables that were not visited yet */ 1793 for( c = 0; c < vargraph->nvarconss[varpos]; ++c ) 1794 { 1795 int nconsvars; 1796 int v; 1797 SCIP_Bool success; 1798 SCIP_CONS* cons = vargraph->varconss[varpos][c]; 1799 1800 /* check first if this constraint has already been visited */ 1801 if( SCIPhashtableExists(vargraph->visitedconss, (void *)cons) ) 1802 continue; 1803 1804 /* request number of constraint variables */ 1805 SCIP_CALL( SCIPgetConsNVars(scip, cons, &nconsvars, &success) ); 1806 1807 if( !success ) 1808 continue; 1809 1810 /* collect constraint variables in buffer */ 1811 SCIP_CALL( SCIPgetConsVars(scip, cons, varbuffer, nvars, &success) ); 1812 1813 if( !success ) 1814 continue; 1815 1816 /* collect previously unvisited variables of the constraint and enqueue them for breadth-first search */ 1817 for( v = 0; v < nconsvars; ++v ) 1818 { 1819 SCIP_VAR* nextvar = varbuffer[v]; 1820 int nextvarpos; 1821 assert(nextvar != NULL); 1822 if( !SCIPvarIsActive(nextvar) ) 1823 continue; 1824 1825 nextvarpos = SCIPvarGetProbindex(nextvar); 1826 assert(nextvarpos >= 0); 1827 1828 /* insert variables that were not considered yet into the next level queue */ 1829 if( distances[nextvarpos] == -1 ) 1830 { 1831 distances[nextvarpos] = currentdistance + 1; 1832 queue[nextlvlidx] = nextvarpos; 1833 nextlvlidx -= increment; 1834 1835 nvarshit++; 1836 if( nextvarpos < nbinintvars ) 1837 ++nbinintvarshit; 1838 } 1839 } /* end constraint variables loop */ 1840 1841 /* mark the constraint as visited */ 1842 SCIP_CALL( SCIPhashtableInsert(vargraph->visitedconss, (void *)cons) ); 1843 } /* end constraint loop */ 1844 1845 queue[currlvlidx] = -1; 1846 currlvlidx += increment; 1847 1848 /* check if we need to swap current and next level index and reverse the increment */ 1849 if( currlvlidx == nvars || currlvlidx == 0 || queue[currlvlidx] == -1 || currlvlidx == nextlvlidx ) 1850 { 1851 /* break early if the distance has been determined for enough variables */ 1852 if( nvarshit >= maxvars || nbinintvarshit >= maxbinintvars ) 1853 break; 1854 1855 /* increment knows whether we are currently looping upwards (all variables with odd distance) or downwards the 1856 * queue 1857 */ 1858 if( increment == +1 ) 1859 { 1860 currlvlidx = nvars - 1; 1861 nextlvlidx = 0; 1862 increment = -1; 1863 } 1864 else 1865 { 1866 currlvlidx = 0; 1867 nextlvlidx = nvars - 1; 1868 increment = +1; 1869 } 1870 } 1871 } 1872 while( queue[currlvlidx] != -1 && distances[queue[currlvlidx]] >= currentdistance ); 1873 1874 SCIPfreeBufferArray(scip, &varbuffer); 1875 SCIPfreeBufferArray(scip, &queue); 1876 1877 /* free also the variable graph, if it wasn't provided by the caller */ 1878 if( localvargraph ) 1879 { 1880 SCIPvariableGraphFree(scip, &vargraph); 1881 } 1882 1883 return SCIP_OKAY; 1884 } 1885 1886 /* fills variable graph data structure 1887 * 1888 * loops over global problem constraints and creates a mapping from the variables to their respective constraints 1889 */ 1890 static 1891 SCIP_RETCODE fillVariableGraph( 1892 SCIP* scip, /**< SCIP data structure */ 1893 SCIP_VGRAPH* vargraph, /**< variable graph data structure for breadth-first-search neighborhoods */ 1894 SCIP_Bool relaxdenseconss, /**< should dense constraints (at least as dense as \p density) be 1895 * ignored by connectivity graph? */ 1896 SCIP_Real relaxdensity, /**< density (with respect to number of variables) to relax constraint from graph */ 1897 int* nrelaxedconstraints /**< pointer to store the number of constraints that were relaxed, or NULL if not needed */ 1898 ) 1899 { 1900 SCIP_CONS** conss; 1901 int nconss; 1902 int nvars; 1903 int c; 1904 int relaxlimit; 1905 SCIP_VAR** varbuffer; 1906 1907 assert(scip != NULL); 1908 assert(vargraph != NULL); 1909 1910 conss = SCIPgetConss(scip); 1911 nconss = SCIPgetNConss(scip); 1912 1913 nvars = SCIPgetNVars(scip); 1914 SCIP_CALL( SCIPallocBufferArray(scip, &varbuffer, nvars) ); 1915 1916 if( nrelaxedconstraints != NULL ) 1917 *nrelaxedconstraints = 0; 1918 1919 relaxlimit = (int)(relaxdensity * nvars); 1920 1921 for( c = 0; c < nconss; ++c ) 1922 { 1923 int nconsvars; 1924 int v; 1925 SCIP_Bool success; 1926 SCIP_CONS* cons = conss[c]; 1927 1928 /* we only consider constraints that are checkable */ 1929 if( !SCIPconsIsChecked(cons) ) 1930 continue; 1931 1932 /* request number of variables */ 1933 SCIP_CALL( SCIPgetConsNVars(scip, cons, &nconsvars, &success) ); 1934 1935 if( !success ) 1936 continue; 1937 1938 /* relax constraints with density above the allowed number of free variables */ 1939 if( relaxdenseconss && nconsvars >= relaxlimit ) 1940 { 1941 if( nrelaxedconstraints != NULL ) 1942 ++(*nrelaxedconstraints); 1943 1944 continue; 1945 } 1946 1947 /* collect constraint variables in buffer */ 1948 SCIP_CALL( SCIPgetConsVars(scip, cons, varbuffer, nvars, &success) ); 1949 1950 if( !success ) 1951 continue; 1952 1953 /* loop over constraint variables and add this constraint to them if they are active */ 1954 for( v = 0; v < nconsvars; ++v ) 1955 { 1956 int varpos = SCIPvarGetProbindex(varbuffer[v]); 1957 1958 /* skip inactive variables */ 1959 if( varpos == -1 ) 1960 continue; 1961 1962 /* ensure array size */ 1963 if( vargraph->varconssize[varpos] == vargraph->nvarconss[varpos] ) 1964 { 1965 int newmem = SCIPcalcMemGrowSize(scip, vargraph->nvarconss[varpos] + 1); 1966 1967 assert(newmem > vargraph->varconssize[varpos]); 1968 1969 if( vargraph->varconss[varpos] == NULL ) 1970 { 1971 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vargraph->varconss[varpos], newmem) ); 1972 } 1973 else 1974 { 1975 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &vargraph->varconss[varpos], vargraph->varconssize[varpos], newmem) ); /*lint !e866*/ 1976 } 1977 vargraph->varconssize[varpos] = newmem; 1978 } 1979 1980 assert(vargraph->nvarconss[varpos] < vargraph->varconssize[varpos]); 1981 1982 /* add constraint to constraint array for this variable */ 1983 vargraph->varconss[varpos][vargraph->nvarconss[varpos]] = cons; 1984 vargraph->nvarconss[varpos] += 1; 1985 } 1986 } 1987 1988 /* free the buffer */ 1989 SCIPfreeBufferArray(scip, &varbuffer); 1990 1991 return SCIP_OKAY; 1992 } 1993 1994 /** initialization method of variable graph data structure */ 1995 SCIP_RETCODE SCIPvariableGraphCreate( 1996 SCIP* scip, /**< SCIP data structure */ 1997 SCIP_VGRAPH** vargraph, /**< pointer to the variable graph */ 1998 SCIP_Bool relaxdenseconss, /**< should dense constraints (at least as dense as \p density) be 1999 * ignored by connectivity graph? */ 2000 SCIP_Real relaxdensity, /**< density (with respect to number of variables) to relax constraint from graph */ 2001 int* nrelaxedconstraints /**< pointer to store the number of constraints that were relaxed, or NULL if not needed */ 2002 ) 2003 { 2004 int nvars; 2005 int nconss; 2006 2007 assert(scip != NULL); 2008 assert(vargraph != NULL); 2009 2010 nvars = SCIPgetNVars(scip); 2011 nconss = SCIPgetNConss(scip); 2012 2013 if( nvars == 0 ) 2014 return SCIP_OKAY; 2015 2016 SCIP_CALL( SCIPallocBlockMemory(scip, vargraph) ); 2017 2018 SCIP_CALL( SCIPhashtableCreate(&(*vargraph)->visitedconss, SCIPblkmem(scip), 2 * nconss, SCIPhashGetKeyStandard, 2019 SCIPhashKeyEqPtr, SCIPhashKeyValPtr, NULL) ); 2020 2021 /* allocate and clear memory */ 2022 SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*vargraph)->varconss, nvars) ); 2023 SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*vargraph)->nvarconss, nvars) ); 2024 SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*vargraph)->varconssize, nvars) ); 2025 2026 /* fill the variable graph with variable-constraint mapping for breadth-first search*/ 2027 SCIP_CALL( fillVariableGraph(scip, *vargraph, relaxdenseconss, relaxdensity, nrelaxedconstraints) ); 2028 2029 return SCIP_OKAY; 2030 } 2031 2032 /** deinitialization method of variable graph data structure */ 2033 void SCIPvariableGraphFree( 2034 SCIP* scip, /**< SCIP data structure */ 2035 SCIP_VGRAPH** vargraph /**< pointer to the variable graph */ 2036 ) 2037 { 2038 int nvars; 2039 int v; 2040 assert(scip != NULL); 2041 assert(vargraph != NULL); 2042 2043 nvars = SCIPgetNVars(scip); 2044 2045 for( v = nvars - 1; v >= 0; --v ) 2046 { 2047 SCIPfreeBlockMemoryArrayNull(scip, &(*vargraph)->varconss[v], (*vargraph)->varconssize[v]); /*lint !e866*/ 2048 } 2049 2050 /* allocate and clear memory */ 2051 SCIPfreeBlockMemoryArray(scip, &(*vargraph)->varconssize, nvars); 2052 SCIPfreeBlockMemoryArray(scip, &(*vargraph)->nvarconss, nvars); 2053 SCIPfreeBlockMemoryArray(scip, &(*vargraph)->varconss, nvars); 2054 2055 SCIPhashtableFree(&(*vargraph)->visitedconss); 2056 2057 SCIPfreeBlockMemory(scip, vargraph); 2058 } 2059