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_adaptivediving.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief diving heuristic that selects adaptively between the existing, public dive sets 28 * @author Gregor Hendel 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include <assert.h> 34 #include <string.h> 35 36 #include "scip/heur_adaptivediving.h" 37 #include "scip/heuristics.h" 38 #include "scip/scipdefplugins.h" 39 40 #define HEUR_NAME "adaptivediving" 41 #define HEUR_DESC "diving heuristic that selects adaptively between the existing, public divesets" 42 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING 43 #define HEUR_PRIORITY -70000 44 #define HEUR_FREQ 5 45 #define HEUR_FREQOFS 3 46 #define HEUR_MAXDEPTH -1 47 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE 48 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */ 49 50 #define DIVESETS_INITIALSIZE 10 51 #define DEFAULT_INITIALSEED 13 52 53 /* 54 * Default parameter settings 55 */ 56 #define DEFAULT_SELTYPE 'w' 57 #define DEFAULT_SCORETYPE 'c' /**< score parameter for selection: minimize either average 'n'odes, LP 'i'terations, 58 * backtrack/'c'onflict ratio, 'd'epth, 1 / 's'olutions, or 59 * 1 / solutions'u'ccess */ 60 #define DEFAULT_USEADAPTIVECONTEXT FALSE 61 #define DEFAULT_SELCONFIDENCECOEFF 10.0 /**< coefficient c to decrease initial confidence (calls + 1.0) / (calls + c) in scores */ 62 #define DEFAULT_EPSILON 1.0 /**< parameter that increases probability of exploration among divesets (only active if seltype is 'e') */ 63 #define DEFAULT_MAXLPITERQUOT 0.1 /**< maximal fraction of diving LP iterations compared to node LP iterations */ 64 #define DEFAULT_MAXLPITEROFS 1500L /**< additional number of allowed LP iterations */ 65 #define DEFAULT_BESTSOLWEIGHT 10.0 /**< weight of incumbent solutions compared to other solutions in computation of LP iteration limit */ 66 67 /* locally defined heuristic data */ 68 struct SCIP_HeurData 69 { 70 /* data structures used internally */ 71 SCIP_SOL* sol; /**< working solution */ 72 SCIP_RANDNUMGEN* randnumgen; /**< random number generator for selection */ 73 SCIP_DIVESET** divesets; /**< publicly available divesets from diving heuristics */ 74 int ndivesets; /**< number of publicly available divesets from diving heuristics */ 75 int divesetssize; /**< array size for divesets array */ 76 int lastselection; /**< stores the last selected diveset when the heuristics was run */ 77 /* user parameters */ 78 SCIP_Real epsilon; /**< parameter that increases probability of exploration among divesets (only active if seltype is 'e') */ 79 SCIP_Real selconfidencecoeff; /**< coefficient c to decrease initial confidence (calls + 1.0) / (calls + c) in scores */ 80 SCIP_Real maxlpiterquot; /**< maximal fraction of diving LP iterations compared to node LP iterations */ 81 SCIP_Longint maxlpiterofs; /**< additional number of allowed LP iterations */ 82 SCIP_Real bestsolweight; /**< weight of incumbent solutions compared to other solutions in computation of LP iteration limit */ 83 char seltype; /**< selection strategy: (e)psilon-greedy, (w)eighted distribution, (n)ext diving */ 84 char scoretype; /**< score parameter for selection: minimize either average 'n'odes, LP 'i'terations, 85 * backtrack/'c'onflict ratio, 'd'epth, 1 / 's'olutions, or 86 * 1 / solutions'u'ccess */ 87 SCIP_Bool useadaptivecontext; /**< should the heuristic use its own statistics, or shared statistics? */ 88 }; 89 90 /* 91 * local methods 92 */ 93 94 95 /** get the selection score for this dive set */ 96 static 97 SCIP_RETCODE divesetGetSelectionScore( 98 SCIP_DIVESET* diveset, /**< diving settings data structure */ 99 SCIP_HEURDATA* heurdata, /**< heuristic data */ 100 SCIP_DIVECONTEXT divecontext, /**< context for diving statistics */ 101 SCIP_Real* scoreptr /**< pointer to store the score */ 102 ) 103 { 104 SCIP_Real confidence; 105 106 assert(scoreptr != NULL); 107 108 /* compute confidence scalar (converges towards 1 with increasing number of calls) */ 109 confidence = (SCIPdivesetGetNCalls(diveset, divecontext) + 1.0) / 110 (SCIPdivesetGetNCalls(diveset, divecontext) + heurdata->selconfidencecoeff); 111 112 switch (heurdata->scoretype) { 113 case 'n': /* min average nodes */ 114 *scoreptr = confidence * SCIPdivesetGetNProbingNodes(diveset, divecontext) / (SCIPdivesetGetNCalls(diveset, divecontext) + 1.0); 115 break; 116 case 'i': /* min avg LP iterations */ 117 *scoreptr = confidence * SCIPdivesetGetNLPIterations(diveset, divecontext) / (SCIPdivesetGetNCalls(diveset, divecontext) + 1.0); 118 break; 119 case 'c': /* min backtrack / conflict ratio (the current default) */ 120 *scoreptr = confidence * (SCIPdivesetGetNBacktracks(diveset, divecontext)) / (SCIPdivesetGetNConflicts(diveset, divecontext) + 10.0); 121 break; 122 case 'd': /* minimum average depth */ 123 *scoreptr = SCIPdivesetGetAvgDepth(diveset, divecontext) * confidence; 124 break; 125 case 's': /* maximum number of solutions */ 126 *scoreptr = confidence / (SCIPdivesetGetNSols(diveset, divecontext) + 1.0); 127 break; 128 case 'u': /* maximum solution success (which weighs best solutions higher) */ 129 *scoreptr = confidence / (SCIPdivesetGetSolSuccess(diveset, divecontext) + 1.0); 130 break; 131 default: 132 SCIPerrorMessage("Unsupported scoring parameter '%c'\n", heurdata->scoretype); 133 SCIPABORT(); 134 *scoreptr = SCIP_INVALID; 135 return SCIP_PARAMETERWRONGVAL; 136 } 137 138 return SCIP_OKAY; 139 } 140 141 /* 142 * Callback methods 143 */ 144 145 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 146 static 147 SCIP_DECL_HEURCOPY(heurCopyAdaptivediving) 148 { /*lint --e{715}*/ 149 assert(scip != NULL); 150 assert(heur != NULL); 151 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 152 153 /* call inclusion method of primal heuristic */ 154 SCIP_CALL( SCIPincludeHeurAdaptivediving(scip) ); 155 156 return SCIP_OKAY; 157 } 158 159 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 160 static 161 SCIP_DECL_HEURFREE(heurFreeAdaptivediving) /*lint --e{715}*/ 162 { /*lint --e{715}*/ 163 SCIP_HEURDATA* heurdata; 164 165 assert(heur != NULL); 166 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 167 assert(scip != NULL); 168 169 /* free heuristic data */ 170 heurdata = SCIPheurGetData(heur); 171 assert(heurdata != NULL); 172 173 if( heurdata->divesets != NULL ) 174 { 175 SCIPfreeBlockMemoryArray(scip, &heurdata->divesets, heurdata->divesetssize); 176 } 177 178 SCIPfreeRandom(scip, &heurdata->randnumgen); 179 180 SCIPfreeMemory(scip, &heurdata); 181 SCIPheurSetData(heur, NULL); 182 183 return SCIP_OKAY; 184 } 185 186 /** find publicly available divesets and store them */ 187 static 188 SCIP_RETCODE findAndStoreDivesets( 189 SCIP* scip, /**< SCIP data structure */ 190 SCIP_HEUR* heur, /**< the heuristic */ 191 SCIP_HEURDATA* heurdata /**< heuristic data */ 192 ) 193 { 194 int h; 195 SCIP_HEUR** heurs; 196 197 assert(scip != NULL); 198 assert(heur != NULL); 199 assert(heurdata != NULL); 200 201 heurs = SCIPgetHeurs(scip); 202 203 heurdata->divesetssize = DIVESETS_INITIALSIZE; 204 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->divesets, heurdata->divesetssize) ); 205 heurdata->ndivesets = 0; 206 207 for( h = 0; h < SCIPgetNHeurs(scip); ++h ) 208 { 209 int d; 210 assert(heurs[h] != NULL); 211 212 /* loop over divesets of this heuristic and check whether they are public */ 213 for( d = 0; d < SCIPheurGetNDivesets(heurs[h]); ++d ) 214 { 215 SCIP_DIVESET* diveset = SCIPheurGetDivesets(heurs[h])[d]; 216 if( SCIPdivesetIsPublic(diveset) ) 217 { 218 SCIPdebugMsg(scip, "Found publicly available diveset %s\n", SCIPdivesetGetName(diveset)); 219 220 if( heurdata->ndivesets == heurdata->divesetssize ) 221 { 222 int newsize = 2 * heurdata->divesetssize; 223 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &heurdata->divesets, heurdata->divesetssize, newsize) ); 224 heurdata->divesetssize = newsize; 225 } 226 heurdata->divesets[heurdata->ndivesets++] = diveset; 227 } 228 else 229 { 230 SCIPdebugMsg(scip, "Skipping private diveset %s\n", SCIPdivesetGetName(diveset)); 231 } 232 } 233 } 234 return SCIP_OKAY; 235 } 236 237 /** initialization method of primal heuristic (called after problem was transformed) */ 238 static 239 SCIP_DECL_HEURINIT(heurInitAdaptivediving) /*lint --e{715}*/ 240 { /*lint --e{715}*/ 241 SCIP_HEURDATA* heurdata; 242 243 assert(heur != NULL); 244 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 245 246 /* get and reset heuristic data */ 247 heurdata = SCIPheurGetData(heur); 248 heurdata->lastselection = -1; 249 if( heurdata->divesets != NULL ) 250 { 251 /* we clear the list of collected divesets to ensure reproducability and consistent state across multiple runs 252 * within the same SCIP data structure */ 253 SCIPfreeBlockMemoryArray(scip, &heurdata->divesets, heurdata->divesetssize); 254 assert(heurdata->divesets == NULL); 255 } 256 257 assert(heurdata != NULL); 258 259 /* create working solution */ 260 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) ); 261 262 /* initialize random seed; use problem dimensions to vary initial order between different instances */ 263 SCIPsetRandomSeed(scip, heurdata->randnumgen, 264 (unsigned int)(DEFAULT_INITIALSEED + SCIPgetNOrigVars(scip) + SCIPgetNOrigConss(scip))); 265 266 return SCIP_OKAY; 267 } 268 269 270 /** deinitialization method of primal heuristic (called before transformed problem is freed) */ 271 static 272 SCIP_DECL_HEUREXIT(heurExitAdaptivediving) /*lint --e{715}*/ 273 { /*lint --e{715}*/ 274 SCIP_HEURDATA* heurdata; 275 276 assert(heur != NULL); 277 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 278 279 /* get heuristic data */ 280 heurdata = SCIPheurGetData(heur); 281 assert(heurdata != NULL); 282 283 /* free working solution */ 284 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) ); 285 286 return SCIP_OKAY; 287 } 288 289 /* 290 * heuristic specific interface methods 291 */ 292 293 /** get LP iteration limit for diving */ 294 static 295 SCIP_Longint getLPIterlimit( 296 SCIP* scip, /**< SCIP data structure */ 297 SCIP_HEUR* heur, /**< the heuristic */ 298 SCIP_HEURDATA* heurdata /**< heuristic data */ 299 ) 300 { 301 SCIP_Real nsolsfound = SCIPheurGetNSolsFound(heur) + heurdata->bestsolweight * SCIPheurGetNBestSolsFound(heur); 302 SCIP_Longint nlpiterations = SCIPgetNNodeLPIterations(scip); 303 SCIP_Longint ncalls = SCIPheurGetNCalls(heur); 304 305 SCIP_Longint nlpiterationsdive = 0; 306 SCIP_Longint lpiterlimit; 307 int i; 308 309 assert(scip != NULL); 310 assert(heur != NULL); 311 assert(heurdata != NULL); 312 313 /* loop over the divesets and collect their individual iterations */ 314 for( i = 0; i < heurdata->ndivesets; ++i ) 315 { 316 nlpiterationsdive += SCIPdivesetGetNLPIterations(heurdata->divesets[i], SCIP_DIVECONTEXT_ADAPTIVE); 317 } 318 319 /* compute the iteration limit */ 320 lpiterlimit = (SCIP_Longint)(heurdata->maxlpiterquot * (nsolsfound+1.0)/(ncalls+1.0) * nlpiterations); 321 lpiterlimit += heurdata->maxlpiterofs; 322 lpiterlimit -= nlpiterationsdive; 323 324 return lpiterlimit; 325 } 326 327 #ifdef SCIP_DEBUG 328 /** print array for debug purpose */ 329 static 330 char* printRealArray( 331 char* strbuf, /**< string buffer array */ 332 SCIP_Real* elems, /**< array elements */ 333 int nelems /**< number of elements */ 334 ) 335 { 336 int c; 337 char* pos = strbuf; 338 339 for( c = 0; c < nelems; ++c ) 340 { 341 pos += sprintf(pos, "%.4f ", elems[c]); 342 } 343 344 return strbuf; 345 } 346 #endif 347 348 /** sample from a distribution defined by weights */ /*lint -e715*/ 349 static 350 int sampleWeighted( 351 SCIP* scip, /**< SCIP data structure */ 352 SCIP_RANDNUMGEN* rng, /**< random number generator */ 353 SCIP_Real* weights, /**< weights of a ground set that define the sampling distribution */ 354 int nweights /**< number of elements in the ground set */ 355 ) 356 { 357 SCIP_Real weightsum; 358 SCIP_Real randomnr; 359 int w; 360 #ifdef SCIP_DEBUG 361 char strbuf[SCIP_MAXSTRLEN]; 362 SCIPdebugMsg(scip, "Weights: %s\n", printRealArray(strbuf, weights, nweights)); 363 #endif 364 365 weightsum = 0.0; 366 /* collect sum of weights */ 367 for( w = 0; w < nweights; ++w ) 368 { 369 weightsum += weights[w]; 370 } 371 assert(weightsum > 0); 372 373 randomnr = SCIPrandomGetReal(rng, 0.0, weightsum); 374 375 weightsum = 0.0; 376 /* choose first element i such that the weight sum exceeds the random number */ 377 for( w = 0; w < nweights - 1; ++w ) 378 { 379 weightsum += weights[w]; 380 381 if( weightsum >= randomnr ) 382 break; 383 } 384 assert(w < nweights); 385 assert(weights[w] > 0.0); 386 387 return w; 388 } 389 390 /** select the diving method to apply */ 391 static 392 SCIP_RETCODE selectDiving( 393 SCIP* scip, /**< SCIP data structure */ 394 SCIP_HEUR* heur, /**< the heuristic */ 395 SCIP_HEURDATA* heurdata, /**< heuristic data */ 396 int* selection /**< selection made */ 397 ) 398 { 399 SCIP_Bool* methodunavailable; 400 SCIP_DIVESET** divesets; 401 int ndivesets; 402 int d; 403 SCIP_RANDNUMGEN* rng; 404 SCIP_DIVECONTEXT divecontext; 405 SCIP_Real* weights; 406 SCIP_Real epsilon_t; 407 408 divesets = heurdata->divesets; 409 ndivesets = heurdata->ndivesets; 410 assert(ndivesets > 0); 411 assert(divesets != NULL); 412 413 SCIP_CALL( SCIPallocClearBufferArray(scip, &methodunavailable, ndivesets) ); 414 415 divecontext = heurdata->useadaptivecontext ? SCIP_DIVECONTEXT_ADAPTIVE : SCIP_DIVECONTEXT_TOTAL; 416 417 /* check availability of divesets */ 418 for( d = 0; d < heurdata->ndivesets; ++d ) 419 { 420 SCIP_Bool available; 421 SCIP_CALL( SCIPisDivesetAvailable(scip, heurdata->divesets[d], &available) ); 422 methodunavailable[d] = ! available; 423 } 424 425 *selection = -1; 426 427 rng = heurdata->randnumgen; 428 assert(rng != NULL); 429 430 switch (heurdata->seltype) { 431 case 'e': 432 epsilon_t = heurdata->epsilon * sqrt(ndivesets / (SCIPheurGetNCalls(heur) + 1.0)); 433 epsilon_t = MAX(epsilon_t, 0.05); 434 435 /* select one of the available methods at random */ 436 if( epsilon_t >= 1.0 || SCIPrandomGetReal(rng, 0.0, 1.0) < epsilon_t ) 437 { 438 do 439 { 440 *selection = SCIPrandomGetInt(rng, 0, ndivesets - 1); 441 } 442 while( methodunavailable[*selection] ); 443 } 444 else 445 { 446 SCIP_Real bestscore = SCIP_REAL_MAX; 447 for( d = 0; d < heurdata->ndivesets; ++d ) 448 { 449 SCIP_Real score; 450 451 if( methodunavailable[d] ) 452 continue; 453 454 SCIP_CALL( divesetGetSelectionScore(divesets[d], heurdata, divecontext, &score) ); 455 456 if( score < bestscore ) 457 { 458 bestscore = score; 459 *selection = d; 460 } 461 } 462 } 463 break; 464 case 'w': 465 SCIP_CALL( SCIPallocBufferArray(scip, &weights, ndivesets) ); 466 467 /* initialize weights as inverse of the score + a small positive epsilon */ 468 for( d = 0; d < ndivesets; ++d ) 469 { 470 SCIP_Real score; 471 472 SCIP_CALL( divesetGetSelectionScore(divesets[d], heurdata, divecontext, &score) ); 473 474 weights[d] = methodunavailable[d] ? 0.0 : 1 / (score + 1e-4); 475 } 476 477 *selection = sampleWeighted(scip, rng, weights, ndivesets); 478 479 SCIPfreeBufferArray(scip, &weights); 480 break; 481 case 'n': 482 /* continue from last selection and stop at the next available method */ 483 *selection = heurdata->lastselection; 484 485 do 486 { 487 *selection = (*selection + 1) % ndivesets; 488 } 489 while( methodunavailable[*selection] ); 490 heurdata->lastselection = *selection; 491 break; 492 default: 493 SCIPerrorMessage("Error: Unknown selection method %c\n", heurdata->seltype); 494 495 return SCIP_INVALIDDATA; 496 } 497 498 assert(*selection >= 0 && *selection < ndivesets); 499 SCIPfreeBufferArray(scip, &methodunavailable); 500 501 return SCIP_OKAY; 502 } 503 504 /** execution method of primal heuristic */ 505 static 506 SCIP_DECL_HEUREXEC(heurExecAdaptivediving) /*lint --e{715}*/ 507 { /*lint --e{715}*/ 508 SCIP_HEURDATA* heurdata; 509 SCIP_DIVESET* diveset; 510 SCIP_DIVESET** divesets; 511 SCIP_Longint lpiterlimit; 512 int selection; 513 514 515 assert(heur != NULL); 516 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 517 assert(scip != NULL); 518 assert(result != NULL); 519 assert(SCIPhasCurrentNodeLP(scip)); 520 521 heurdata = SCIPheurGetData(heur); 522 if( heurdata->divesets == NULL ) 523 { 524 SCIP_CALL( findAndStoreDivesets(scip, heur, heurdata) ); 525 } 526 527 divesets = heurdata->divesets; 528 assert(divesets != NULL); 529 assert(heurdata->ndivesets > 0); 530 531 SCIPdebugMsg(scip, "heurExecAdaptivediving: depth %d sols %d inf %u node %lld (last dive at %lld)\n", 532 SCIPgetDepth(scip), 533 SCIPgetNSols(scip), 534 nodeinfeasible, 535 SCIPgetNNodes(scip), 536 SCIPgetLastDivenode(scip) 537 ); 538 539 *result = SCIP_DELAYED; 540 541 /* do not call heuristic in node that was already detected to be infeasible */ 542 if( nodeinfeasible ) 543 return SCIP_OKAY; 544 545 /* only call heuristic, if an optimal LP solution is at hand */ 546 if( !SCIPhasCurrentNodeLP(scip) || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 547 return SCIP_OKAY; 548 549 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */ 550 if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) ) 551 return SCIP_OKAY; 552 553 /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */ 554 if( !SCIPisLPSolBasic(scip) ) 555 return SCIP_OKAY; 556 557 /* don't dive two times at the same node */ 558 if( SCIPgetLastDivenode(scip) == SCIPgetNNodes(scip) && SCIPgetDepth(scip) > 0 ) 559 { 560 SCIPdebugMsg(scip, "already dived at node here\n"); 561 562 return SCIP_OKAY; 563 } 564 565 *result = SCIP_DIDNOTRUN; 566 567 lpiterlimit = getLPIterlimit(scip, heur, heurdata); 568 569 if( lpiterlimit <= 0 ) 570 return SCIP_OKAY; 571 572 /* select the next diving strategy based on previous success */ 573 SCIP_CALL( selectDiving(scip, heur, heurdata, &selection) ); 574 assert(selection >= 0 && selection < heurdata->ndivesets); 575 576 diveset = divesets[selection]; 577 assert(diveset != NULL); 578 579 SCIPdebugMsg(scip, "Selected diveset %s\n", SCIPdivesetGetName(diveset)); 580 581 SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, 582 lpiterlimit, -1, -1.0, SCIP_DIVECONTEXT_ADAPTIVE) ); 583 584 if( *result == SCIP_FOUNDSOL ) 585 { 586 SCIPdebugMsg(scip, "Solution found by diveset %s\n", SCIPdivesetGetName(diveset)); 587 } 588 589 return SCIP_OKAY; 590 } 591 592 /** creates the adaptivediving heuristic and includes it in SCIP */ 593 SCIP_RETCODE SCIPincludeHeurAdaptivediving( 594 SCIP* scip /**< SCIP data structure */ 595 ) 596 { 597 SCIP_RETCODE retcode; 598 SCIP_HEURDATA* heurdata; 599 SCIP_HEUR* heur; 600 601 /* create adaptivediving data */ 602 heurdata = NULL; 603 SCIP_CALL( SCIPallocMemory(scip, &heurdata) ); 604 605 heurdata->divesets = NULL; 606 heurdata->ndivesets = 0; 607 heurdata->divesetssize = -1; 608 609 SCIP_CALL_TERMINATE( retcode, SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_INITIALSEED, TRUE), TERMINATE ); 610 611 /* include adaptive diving primal heuristic */ 612 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 613 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 614 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecAdaptivediving, heurdata) ); 615 616 assert(heur != NULL); 617 618 /* set non-NULL pointers to callback methods */ 619 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyAdaptivediving) ); 620 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeAdaptivediving) ); 621 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitAdaptivediving) ); 622 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitAdaptivediving) ); 623 624 /* add parameters */ 625 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/epsilon", 626 "parameter that increases probability of exploration among divesets (only active if seltype is 'e')", 627 &heurdata->epsilon, FALSE, DEFAULT_EPSILON, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 628 629 SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/scoretype", 630 "score parameter for selection: minimize either average 'n'odes, LP 'i'terations," 631 "backtrack/'c'onflict ratio, 'd'epth, 1 / 's'olutions, or 1 / solutions'u'ccess", 632 &heurdata->scoretype, FALSE, DEFAULT_SCORETYPE, "cdinsu", NULL, NULL) ); 633 634 SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/seltype", 635 "selection strategy: (e)psilon-greedy, (w)eighted distribution, (n)ext diving", 636 &heurdata->seltype, FALSE, DEFAULT_SELTYPE, "enw", NULL, NULL) ); 637 638 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useadaptivecontext", 639 "should the heuristic use its own statistics, or shared statistics?", &heurdata->useadaptivecontext, TRUE, 640 DEFAULT_USEADAPTIVECONTEXT, NULL, NULL) ); 641 642 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/selconfidencecoeff", 643 "coefficient c to decrease initial confidence (calls + 1.0) / (calls + c) in scores", 644 &heurdata->selconfidencecoeff, FALSE, DEFAULT_SELCONFIDENCECOEFF, 1.0, (SCIP_Real)INT_MAX, NULL, NULL) ); 645 646 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxlpiterquot", 647 "maximal fraction of diving LP iterations compared to node LP iterations", 648 &heurdata->maxlpiterquot, FALSE, DEFAULT_MAXLPITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 649 650 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxlpiterofs", 651 "additional number of allowed LP iterations", 652 &heurdata->maxlpiterofs, FALSE, DEFAULT_MAXLPITEROFS, 0L, (SCIP_Longint)INT_MAX, NULL, NULL) ); 653 654 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/bestsolweight", 655 "weight of incumbent solutions compared to other solutions in computation of LP iteration limit", 656 &heurdata->bestsolweight, FALSE, DEFAULT_BESTSOLWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 657 658 /* cppcheck-suppress unusedLabel */ 659 TERMINATE: 660 if( retcode != SCIP_OKAY ) 661 { 662 SCIPfreeMemory(scip, &heurdata); 663 return retcode; 664 } 665 666 return SCIP_OKAY; 667 } 668