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_crossover.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief crossover primal heuristic 28 * @author Timo Berthold 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "blockmemshell/memory.h" 34 #include "scip/heur_crossover.h" 35 #include "scip/heuristics.h" 36 #include "scip/pub_event.h" 37 #include "scip/pub_heur.h" 38 #include "scip/pub_message.h" 39 #include "scip/pub_misc.h" 40 #include "scip/pub_sol.h" 41 #include "scip/pub_var.h" 42 #include "scip/scip_branch.h" 43 #include "scip/scip_cons.h" 44 #include "scip/scip_copy.h" 45 #include "scip/scip_event.h" 46 #include "scip/scip_general.h" 47 #include "scip/scip_heur.h" 48 #include "scip/scip_mem.h" 49 #include "scip/scip_message.h" 50 #include "scip/scip_nodesel.h" 51 #include "scip/scip_numerics.h" 52 #include "scip/scip_param.h" 53 #include "scip/scip_prob.h" 54 #include "scip/scip_randnumgen.h" 55 #include "scip/scip_sol.h" 56 #include "scip/scip_solve.h" 57 #include "scip/scip_solvingstats.h" 58 #include "scip/scip_tree.h" 59 #include "scip/scip_var.h" 60 #include <string.h> 61 62 #define HEUR_NAME "crossover" 63 #define HEUR_DESC "LNS heuristic that fixes all variables that are identic in a couple of solutions" 64 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS 65 #define HEUR_PRIORITY -1104000 66 #define HEUR_FREQ 30 67 #define HEUR_FREQOFS 0 68 #define HEUR_MAXDEPTH -1 69 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE 70 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */ 71 72 #define DEFAULT_MAXNODES 5000LL /* maximum number of nodes to regard in the subproblem */ 73 #define DEFAULT_MINIMPROVE 0.01 /* factor by which Crossover should at least improve the incumbent */ 74 #define DEFAULT_MINNODES 50LL /* minimum number of nodes to regard in the subproblem */ 75 #define DEFAULT_MINFIXINGRATE 0.666 /* minimum percentage of integer variables that have to be fixed */ 76 #define DEFAULT_NODESOFS 500LL /* number of nodes added to the contingent of the total nodes */ 77 #define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */ 78 #define DEFAULT_LPLIMFAC 2.0 /* factor by which the limit on the number of LP depends on the node limit */ 79 #define DEFAULT_NUSEDSOLS 3 /* number of solutions that will be taken into account */ 80 #define DEFAULT_NWAITINGNODES 200LL /* number of nodes without incumbent change heuristic should wait */ 81 #define DEFAULT_RANDOMIZATION TRUE /* should the choice which sols to take be randomized? */ 82 #define DEFAULT_DONTWAITATROOT FALSE /* should the nwaitingnodes parameter be ignored at the root node? */ 83 #define DEFAULT_USELPROWS FALSE /* should subproblem be created out of the rows in the LP rows, 84 * otherwise, the copy constructors of the constraints handlers are used */ 85 #define DEFAULT_COPYCUTS TRUE /* if DEFAULT_USELPROWS is FALSE, then should all active cuts from the 86 * cutpool of the original scip be copied to constraints of the subscip 87 */ 88 #define DEFAULT_PERMUTE FALSE /* should the subproblem be permuted to increase diversification? */ 89 #define HASHSIZE_SOLS 500 /* size of hash table for solution tuples in crossover heuristic */ 90 #define DEFAULT_BESTSOLLIMIT -1 /* limit on number of improving incumbent solutions in sub-CIP */ 91 #define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */ 92 #define DEFAULT_RANDSEED 7 /* initial random seed */ 93 94 /* event handler properties */ 95 #define EVENTHDLR_NAME "Crossover" 96 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" 97 98 /* 99 * Data structures 100 */ 101 102 typedef struct SolTuple SOLTUPLE; 103 104 /** primal heuristic data */ 105 struct SCIP_HeurData 106 { 107 SCIP_SOL* prevlastsol; /**< worst solution taken into account during the previous run */ 108 SCIP_SOL* prevbestsol; /**< best solution during the previous run */ 109 int prevnsols; /**< number of all solutions during the previous run */ 110 111 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */ 112 SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */ 113 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */ 114 SCIP_Longint usednodes; /**< nodes already used by crossover in earlier calls */ 115 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */ 116 117 int nusedsols; /**< number of solutions that will be taken into account */ 118 SCIP_Longint nwaitingnodes; /**< number of nodes without incumbent change heuristic should wait */ 119 unsigned int nfailures; /**< number of failures since last successful call */ 120 SCIP_Longint nextnodenumber; /**< number of nodes at which crossover should be called the next time */ 121 SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */ 122 SCIP_Real minimprove; /**< factor by which Crossover should at least improve the incumbent */ 123 SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/ 124 SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */ 125 SCIP_Bool randomization; /**< should the choice which sols to take be randomized? */ 126 SCIP_Bool dontwaitatroot; /**< should the nwaitingnodes parameter be ignored at the root node? */ 127 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */ 128 SCIP_HASHTABLE* hashtable; /**< hashtable used to store the solution tuples already used */ 129 SOLTUPLE* lasttuple; /**< last tuple of solutions created by crossover */ 130 SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */ 131 SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied 132 * to constraints in subproblem? */ 133 SCIP_Bool permute; /**< should the subproblem be permuted to increase diversification? */ 134 int bestsollimit; /**< limit on number of improving incumbent solutions in sub-CIP */ 135 SCIP_Bool useuct; /**< should uct node selection be used at the beginning of the search? */ 136 }; 137 138 /** n-tuple of solutions and their hashkey */ 139 struct SolTuple 140 { 141 int* indices; /**< sorted array of solution indices */ 142 int size; /**< size of the array (should be heurdata->nusedsols) */ 143 unsigned int key; /**< hashkey of the tuple */ 144 SOLTUPLE* prev; /**< previous solution tuple created */ 145 }; 146 147 148 /* 149 * Local methods 150 */ 151 152 /** gets the hash key of a solution tuple */ 153 static 154 SCIP_DECL_HASHGETKEY(hashGetKeySols) 155 { /*lint --e{715}*/ 156 return elem; 157 } 158 159 160 /** returns TRUE iff both solution tuples are identical */ 161 static 162 SCIP_DECL_HASHKEYEQ(hashKeyEqSols) 163 { /*lint --e{715}*/ 164 int i; 165 int size; 166 167 int* indices1; 168 int* indices2; 169 170 indices1 = ((SOLTUPLE*)key1)->indices; 171 indices2 = ((SOLTUPLE*)key2)->indices; 172 173 /* there should be two nonempty arrays of the same size */ 174 assert(indices1 != NULL); 175 assert(indices2 != NULL); 176 assert(((SOLTUPLE*)key1)->size == ((SOLTUPLE*)key2)->size); 177 178 size = ((SOLTUPLE*)key1)->size; 179 180 /* compare arrays by components, return TRUE, iff equal */ 181 for( i = 0; i < size; i++ ) 182 { 183 if( indices1[i] != indices2[i] ) 184 return FALSE; 185 } 186 187 return TRUE; 188 } 189 190 191 /** returns hashkey of a solution tuple */ 192 static 193 SCIP_DECL_HASHKEYVAL(hashKeyValSols) 194 { /*lint --e{715}*/ 195 return ((SOLTUPLE*)key)->key; 196 } 197 198 199 /** calculates a hash key for a given tuple of solution indices */ 200 static 201 unsigned int calculateHashKey( 202 int* indices, /**< indices of solutions */ 203 int size /**< number of solutions */ 204 ) 205 { 206 int i; 207 unsigned int hashkey; 208 209 /* hashkey should be (x1+1) * (x2+1) * ... * (xn+1) + x1 + x2 + ... + xn */ 210 hashkey = 1; 211 for( i = 0; i < size; i++ ) 212 hashkey *= (unsigned) indices[i] + 1; 213 for( i = 0; i < size; i++ ) 214 hashkey += (unsigned) indices[i]; 215 216 return hashkey; 217 } 218 219 220 /** insertion sort for a small int array */ 221 static void sortArray( 222 int* a, /**< array to be sorted */ 223 int size /**< size of array */ 224 ) 225 { 226 int i; 227 int j; 228 int tmp; 229 230 /* simple insertion sort algorithm */ 231 for( i = 1; i < size; i++ ) 232 { 233 tmp = a[i]; 234 j = i-1; 235 while( j >= 0 && a[j] > tmp ) 236 { 237 a[j+1] = a[j]; /*lint !e679*/ 238 j = j-1; 239 } 240 a[j+1] = tmp; /*lint !e679*/ 241 } 242 } 243 244 245 /** creates a new tuple of solutions */ 246 static 247 SCIP_RETCODE createSolTuple( 248 SCIP* scip, /**< original SCIP data structure */ 249 SOLTUPLE** elem, /**< tuple of solutions which should be created */ 250 int* indices, /**< indices of solutions */ 251 int size, /**< number of solutions */ 252 SCIP_HEURDATA* heurdata /**< primal heuristic data */ 253 ) 254 { 255 /* memory allocation */ 256 SCIP_CALL( SCIPallocBlockMemory(scip, elem) ); 257 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*elem)->indices, size) ); 258 BMScopyMemoryArray((*elem)->indices, indices, size); 259 260 /* data input */ 261 sortArray(indices,size); 262 (*elem)->size = size; 263 (*elem)->key = calculateHashKey((*elem)->indices, (*elem)->size); 264 (*elem)->prev = heurdata->lasttuple; 265 266 /* update heurdata */ 267 heurdata->lasttuple = *elem; 268 return SCIP_OKAY; 269 } 270 271 272 /** checks whether the new solution was found at the same node by the same heuristic as an already selected one */ 273 static 274 SCIP_Bool solHasNewSource( 275 SCIP_SOL** sols, /**< feasible SCIP solutions */ 276 int* selection, /**< pool of solutions crossover uses */ 277 int selectionsize, /**< size of solution pool */ 278 int newsol /**< candidate solution */ 279 ) 280 { 281 int i; 282 283 for( i = 0; i < selectionsize; i++ ) 284 { 285 if( SCIPsolGetHeur(sols[selection[i]]) == SCIPsolGetHeur(sols[newsol]) 286 && SCIPsolGetNodenum(sols[selection[i]]) == SCIPsolGetNodenum(sols[newsol]) ) 287 return FALSE; 288 } 289 290 return TRUE; 291 } 292 293 /** randomly selects the solutions crossover will use from the pool of all solutions found so far */ 294 static 295 SCIP_RETCODE selectSolsRandomized( 296 SCIP* scip, /**< original SCIP data structure */ 297 int* selection, /**< pool of solutions crossover uses */ 298 SCIP_HEURDATA* heurdata, /**< primal heuristic data */ 299 SCIP_Bool* success /**< pointer to store whether the process was successful */ 300 ) 301 { 302 int i; 303 int j; 304 int lastsol; /* the worst solution possible to choose */ 305 int nusedsols; /* number of solutions which will be chosen */ 306 307 SOLTUPLE* elem; 308 SCIP_SOL** sols; 309 310 assert( success != NULL ); 311 312 /* initialization */ 313 nusedsols = heurdata->nusedsols; 314 lastsol = SCIPgetNSols(scip); 315 sols = SCIPgetSols(scip); 316 assert(nusedsols < lastsol); 317 318 i = 0; 319 *success = FALSE; 320 321 /* perform at maximum 10 restarts and stop as soon as a new set of solutions is found */ 322 while( !*success && i < 10 ) 323 { 324 SCIP_Bool validtuple; 325 326 validtuple = TRUE; 327 for( j = 0; j < nusedsols && validtuple; j++ ) 328 { 329 int k; 330 k = SCIPrandomGetInt(heurdata->randnumgen, nusedsols-j-1, lastsol-1); 331 332 /* ensure that the solution does not have a similar source as the others */ 333 while( k >= nusedsols-j-1 && !solHasNewSource(sols, selection, j, k) ) 334 k--; 335 336 validtuple = (k >= nusedsols-j-1); 337 selection[j] = k; 338 lastsol = k; 339 } 340 341 if( validtuple ) 342 { 343 /* creates an object ready to be inserted into the hashtable */ 344 SCIP_CALL( createSolTuple(scip, &elem, selection, nusedsols, heurdata) ); 345 346 /* check whether the randomized set is already in the hashtable, if not, insert it */ 347 if( !SCIPhashtableExists(heurdata->hashtable, elem) ) 348 { 349 SCIP_CALL( SCIPhashtableInsert(heurdata->hashtable, elem) ); 350 *success = TRUE; 351 } 352 } 353 i++; 354 } 355 356 return SCIP_OKAY; 357 } 358 359 360 /** determines the fixings for the CROSSOVER subproblem and checks whether enough fixings were found */ 361 static 362 SCIP_RETCODE fixVariables( 363 SCIP* scip, /**< original SCIP data structure */ 364 SCIP_VAR** fixedvars, /**< array to store source SCIP variables whose copies should be fixed in the sub-SCIP */ 365 SCIP_Real* fixedvals, /**< array to store solution values for variable fixing */ 366 int* nfixedvars, /**< pointer to store the number of fixed variables */ 367 int fixedvarssize, /**< size of the arrays to store fixing variables */ 368 int* selection, /**< pool of solutions crossover will use */ 369 SCIP_HEURDATA* heurdata, /**< primal heuristic data */ 370 SCIP_Bool* success /**< pointer to store whether the problem was created successfully */ 371 ) 372 { 373 SCIP_VAR** vars; /* original scip variables */ 374 SCIP_SOL** sols; /* pool of solutions */ 375 SCIP_Real fixingrate; /* percentage of variables that are fixed */ 376 377 int nvars; 378 int nbinvars; 379 int nintvars; 380 381 int i; 382 int j; 383 384 sols = SCIPgetSols(scip); 385 assert(sols != NULL); 386 assert(fixedvars != NULL); 387 assert(fixedvals != NULL); 388 389 /* get required data of the original problem */ 390 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) ); 391 assert(fixedvarssize >= nbinvars + nintvars); 392 393 *nfixedvars = 0; 394 395 /* go through discrete variables and collect potential fixings */ 396 for( i = 0; i < nbinvars + nintvars; i++ ) 397 { 398 SCIP_Real solval; 399 SCIP_Bool fixable; 400 401 fixable = TRUE; 402 solval = SCIPgetSolVal(scip, sols[selection[0]], vars[i]); 403 404 /* check, whether variable's value is identical for each selected solution */ 405 for( j = 1; j < heurdata->nusedsols; j++ ) 406 { 407 SCIP_Real varsolval; 408 varsolval = SCIPgetSolVal(scip, sols[selection[j]], vars[i]); 409 if( REALABS(solval - varsolval) > 0.5 ) 410 { 411 fixable = FALSE; 412 break; 413 } 414 } 415 416 /* original solval can be outside transformed global bounds */ 417 fixable = fixable && SCIPvarGetLbGlobal(vars[i]) <= solval && solval <= SCIPvarGetUbGlobal(vars[i]); 418 419 /* if solutions' values are equal, variable should be fixed in the subproblem */ 420 if( fixable ) 421 { 422 fixedvars[(*nfixedvars)] = vars[i]; 423 fixedvals[(*nfixedvars)] = solval; 424 (*nfixedvars)++; 425 } 426 } 427 428 fixingrate = (SCIP_Real)(*nfixedvars) / (SCIP_Real)(MAX(nbinvars + nintvars, 1)); 429 430 /* if all variables would be fixed or amount of fixed variables is insufficient, 431 * skip subproblem creation and abort immediately 432 */ 433 *success = (*nfixedvars) < nbinvars + nintvars && fixingrate >= heurdata->minfixingrate; 434 435 return SCIP_OKAY; 436 } 437 438 /** creates a subproblem for subscip by fixing a number of variables */ 439 static 440 SCIP_RETCODE determineVariableFixings( 441 SCIP* scip, /**< original SCIP data structure */ 442 SCIP_VAR** fixedvars, /**< array to store source SCIP variables whose copies should be fixed in the sub-SCIP */ 443 SCIP_Real* fixedvals, /**< array to store solution values for variable fixing */ 444 int* nfixedvars, /**< pointer to store the number of fixed variables */ 445 int fixedvarssize, /**< size of the arrays to store fixing variables */ 446 int* selection, /**< pool of solutions crossover will use */ 447 SCIP_HEURDATA* heurdata, /**< primal heuristic data */ 448 SCIP_Bool* success /**< pointer to store whether the problem was created successfully */ 449 ) 450 { 451 SCIP_SOL** sols; /* array of all solutions found so far */ 452 int nsols; /* number of all solutions found so far */ 453 int nusedsols; /* number of solutions to use in crossover */ 454 int i; 455 456 /* get solutions' data */ 457 nsols = SCIPgetNSols(scip); 458 sols = SCIPgetSols(scip); 459 nusedsols = heurdata->nusedsols; 460 461 assert(nusedsols > 1); 462 assert(nsols >= nusedsols); 463 464 /* use nusedsols best solutions if randomization is deactivated or there are only nusedsols solutions at hand 465 * or a good new solution was found since last call */ 466 if( !heurdata->randomization || nsols == nusedsols || heurdata->prevlastsol != sols[nusedsols-1] ) 467 { 468 SOLTUPLE* elem; 469 SCIP_HEUR* solheur; 470 SCIP_Longint solnodenum; 471 SCIP_Bool allsame; 472 473 for( i = 0; i < nusedsols; i++ ) 474 selection[i] = i; 475 SCIP_CALL( createSolTuple(scip, &elem, selection, nusedsols, heurdata) ); 476 477 solheur = SCIPsolGetHeur(sols[0]); 478 solnodenum = SCIPsolGetNodenum(sols[0]); 479 allsame = TRUE; 480 481 /* check, whether all solutions have been found by the same heuristic at the same node; in this case we do not run 482 * crossover, since it would probably just optimize over the same space as the other heuristic 483 */ 484 for( i = 1; i < nusedsols; i++ ) 485 { 486 if( SCIPsolGetHeur(sols[i]) != solheur || SCIPsolGetNodenum(sols[i]) != solnodenum ) 487 allsame = FALSE; 488 } 489 *success = !allsame && !SCIPhashtableExists(heurdata->hashtable, elem); 490 491 /* check, whether solution tuple has already been tried */ 492 if( !SCIPhashtableExists(heurdata->hashtable, elem) ) 493 { 494 SCIP_CALL( SCIPhashtableInsert(heurdata->hashtable, elem) ); 495 } 496 497 /* if solution tuple has already been tried, randomization is allowed and enough solutions are at hand, try 498 * to randomize another tuple. E.g., this can happen if the last crossover solution was among the best ones */ 499 if( !(*success) && heurdata->randomization && nsols > nusedsols ) 500 { 501 SCIP_CALL( selectSolsRandomized(scip, selection, heurdata, success) ); 502 } 503 } 504 /* otherwise randomize the set of solutions */ 505 else 506 { 507 SCIP_CALL( selectSolsRandomized(scip, selection, heurdata, success) ); 508 } 509 510 /* no acceptable solution tuple could be created */ 511 if( !(*success) ) 512 return SCIP_OKAY; 513 514 /* set up the variables of the subproblem */ 515 SCIP_CALL( fixVariables(scip, fixedvars, fixedvals, nfixedvars, fixedvarssize, selection, heurdata, success) ); 516 517 return SCIP_OKAY; 518 } 519 520 /** updates heurdata after a run of crossover */ 521 static 522 void updateFailureStatistic( 523 SCIP* scip, /**< original SCIP data structure */ 524 SCIP_HEURDATA* heurdata /**< primal heuristic data */ 525 ) 526 { 527 /* increase number of failures, calculate next node at which crossover should be called and update actual solutions */ 528 heurdata->nfailures++; 529 heurdata->nextnodenumber = (heurdata->nfailures <= 25 530 ? SCIPgetNNodes(scip) + 100*(2LL << heurdata->nfailures) /*lint !e703*/ 531 : SCIP_LONGINT_MAX); 532 } 533 534 /* ---------------- Callback methods of event handler ---------------- */ 535 536 /* exec the event handler 537 * 538 * we interrupt the solution process 539 */ 540 static 541 SCIP_DECL_EVENTEXEC(eventExecCrossover) 542 { 543 SCIP_HEURDATA* heurdata; 544 545 assert(eventhdlr != NULL); 546 assert(eventdata != NULL); 547 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 548 assert(event != NULL); 549 assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED); 550 551 heurdata = (SCIP_HEURDATA*)eventdata; 552 assert(heurdata != NULL); 553 554 /* interrupt solution process of sub-SCIP */ 555 if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit ) 556 { 557 SCIPdebugMsg(scip, "interrupt after %" SCIP_LONGINT_FORMAT " LPs\n", SCIPgetNLPs(scip)); 558 SCIP_CALL( SCIPinterruptSolve(scip) ); 559 } 560 561 return SCIP_OKAY; 562 } 563 564 /* 565 * Callback methods of primal heuristic 566 */ 567 568 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 569 static 570 SCIP_DECL_HEURCOPY(heurCopyCrossover) 571 { /*lint --e{715}*/ 572 assert(scip != NULL); 573 assert(heur != NULL); 574 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 575 576 /* call inclusion method of primal heuristic */ 577 SCIP_CALL( SCIPincludeHeurCrossover(scip) ); 578 579 return SCIP_OKAY; 580 } 581 582 /** setup and solve the subproblem and catch the return code */ 583 static 584 SCIP_RETCODE setupAndSolveSubscipCrossover( 585 SCIP* scip, /**< SCIP data structure */ 586 SCIP* subscip, /**< sub-SCIP data structure */ 587 SCIP_HEUR* heur, /**< mutation heuristic */ 588 SCIP_HEURDATA* heurdata, /**< heuristics data */ 589 SCIP_VAR** vars, /**< SCIP variables */ 590 SCIP_VAR** fixedvars, /**< array to store the variables that should be fixed in the subproblem */ 591 SCIP_Real* fixedvals, /**< array to store the fixing values to fix variables in the subproblem */ 592 SCIP_Longint nstallnodes, /**< node limit for the subproblem */ 593 SCIP_RESULT* result, /**< pointer to store the result */ 594 int* selection, /**< pool of solutions crossover uses */ 595 int nvars, /**< number of original problem's variables */ 596 int nfixedvars, /**< the number of variables that should be fixed */ 597 int nusedsols /**< number of solutions which will be chosen */ 598 ) 599 { 600 SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */ 601 SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */ 602 SCIP_VAR** subvars; /* subproblem's variables */ 603 SCIP_Real cutoff; /* objective cutoff for the subproblem */ 604 SCIP_Real upperbound; 605 SCIP_Bool success; 606 int i; 607 608 assert(scip != NULL); 609 assert(subscip != NULL); 610 assert(heur != NULL); 611 assert(heurdata != NULL); 612 613 /* create the variable mapping hash map */ 614 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) ); 615 success = FALSE; 616 617 /* create a copy of the transformed problem to be used by the heuristic */ 618 SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "crossover", fixedvars, fixedvals, nfixedvars, 619 heurdata->uselprows, heurdata->copycuts, &success, NULL) ); 620 621 eventhdlr = NULL; 622 /* create event handler for LP events */ 623 SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecCrossover, NULL) ); 624 if( eventhdlr == NULL ) 625 { 626 SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n"); 627 return SCIP_PLUGINNOTFOUND; 628 } 629 630 /* store copied variables in the order in which they appear in the main SCIP */ 631 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) ); 632 for( i = 0; i < nvars; i++ ) 633 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]); 634 635 /* free hash map */ 636 SCIPhashmapFree(&varmapfw); 637 638 /* do not abort subproblem on CTRL-C */ 639 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) ); 640 641 #ifdef SCIP_DEBUG 642 /* for debugging, enable full output */ 643 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) ); 644 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) ); 645 #else 646 /* disable statistic timing inside sub SCIP and output to console */ 647 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) ); 648 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) ); 649 #endif 650 651 /* check whether there is enough time and memory left */ 652 SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsollimit) ); 653 654 /* set limits for the subproblem */ 655 SCIP_CALL( SCIPcopyLimits(scip, subscip) ); 656 heurdata->nodelimit = nstallnodes; 657 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nstallnodes) ); 658 659 /* forbid recursive call of heuristics and separators solving subMIPs */ 660 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) ); 661 662 /* disable cutting plane separation */ 663 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) ); 664 665 /* disable expensive presolving */ 666 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) ); 667 668 /* use best estimate node selection */ 669 if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") ) 670 { 671 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) ); 672 } 673 674 /* activate uct node selection at the top of the tree */ 675 if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") ) 676 { 677 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) ); 678 } 679 680 /* use inference branching */ 681 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") ) 682 { 683 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) ); 684 } 685 686 /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */ 687 if( !SCIPisParamFixed(subscip, "conflict/enable") ) 688 { 689 SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) ); 690 } 691 if( !SCIPisParamFixed(subscip, "conflict/useboundlp") ) 692 { 693 SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') ); 694 } 695 if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") ) 696 { 697 SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) ); 698 } 699 700 /* speed up sub-SCIP by not checking dual LP feasibility */ 701 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) ); 702 703 /* add an objective cutoff */ 704 assert(!SCIPisInfinity(scip, SCIPgetUpperbound(scip))); 705 706 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip); 707 if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) ) 708 { 709 cutoff = (1-heurdata->minimprove)*SCIPgetUpperbound(scip) + heurdata->minimprove*SCIPgetLowerbound(scip); 710 } 711 else 712 { 713 if( SCIPgetUpperbound ( scip ) >= 0 ) 714 cutoff = ( 1 - heurdata->minimprove ) * SCIPgetUpperbound ( scip ); 715 else 716 cutoff = ( 1 + heurdata->minimprove ) * SCIPgetUpperbound ( scip ); 717 } 718 cutoff = MIN(upperbound, cutoff ); 719 SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) ); 720 721 /* permute the subproblem to increase diversification */ 722 if( heurdata->permute ) 723 { 724 SCIP_CALL( SCIPpermuteProb(subscip, SCIPinitializeRandomSeed(scip, (unsigned) SCIPheurGetNCalls(heur)), TRUE, TRUE, TRUE, TRUE, TRUE) ); 725 } 726 727 /* catch LP events of sub-SCIP */ 728 SCIP_CALL( SCIPtransformProb(subscip) ); 729 SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) ); 730 731 /* this code can be enabled whenever the subproblem should be written out */ 732 #ifdef SCIP_DISABLED_CODE 733 SCIPdebug( SCIP_CALL( SCIPwriteOrigProblem(subscip, "crossoverprob.cip", "cip", FALSE) ) ); 734 #endif 735 /* solve the subproblem */ 736 SCIPdebugMsg(scip, "Solve Crossover subMIP\n"); 737 738 /* Errors in solving the subproblem should not kill the overall solving process. 739 * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */ 740 SCIP_CALL_ABORT( SCIPsolve(subscip) ); 741 742 /* drop LP events of sub-SCIP */ 743 SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) ); 744 745 /* print solving statistics of subproblem if we are in SCIP's debug mode */ 746 SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) ); 747 748 heurdata->usednodes += SCIPgetNNodes(subscip); 749 750 /* merge histories of the subscip-variables to the SCIP variables. */ 751 SCIP_CALL( SCIPmergeVariableStatistics(subscip, scip, subvars, vars, nvars) ); 752 SCIPdebugMsg(scip, "Transferring variable histories complete\n"); 753 754 /* check, whether a solution was found */ 755 if( SCIPgetNSols(subscip) > 0 ) 756 { 757 int solindex; /* index of the solution created by crossover */ 758 759 /* check, whether a solution was found; 760 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted */ 761 success = FALSE; 762 solindex = -1; 763 SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, &solindex) ); 764 765 if( success ) 766 { 767 int tmp; 768 769 assert(solindex != -1); 770 771 *result = SCIP_FOUNDSOL; 772 773 /* insert all crossings of the new solution and (nusedsols-1) of its parents into the hashtable 774 * in order to avoid incest ;) 775 */ 776 for( i = 0; i < nusedsols; i++ ) 777 { 778 SOLTUPLE* elem; 779 tmp = selection[i]; 780 selection[i] = solindex; 781 782 SCIP_CALL( createSolTuple(scip, &elem, selection, nusedsols, heurdata) ); 783 SCIP_CALL( SCIPhashtableInsert(heurdata->hashtable, elem) ); 784 selection[i] = tmp; 785 } 786 787 /* if solution was among the best ones, crossover should not be called until another good solution was found */ 788 if( !heurdata->randomization ) 789 { 790 heurdata->prevbestsol = SCIPgetBestSol(scip); 791 heurdata->prevlastsol = SCIPgetSols(scip)[heurdata->nusedsols-1]; 792 } 793 } 794 795 /* if solution is not better than incumbent or could not be added to problem => run is counted as a failure */ 796 if( !success || solindex != SCIPsolGetIndex(SCIPgetBestSol(scip)) ) 797 updateFailureStatistic(scip, heurdata); 798 } 799 else 800 { 801 /* if no new solution was found, run was a failure */ 802 updateFailureStatistic(scip, heurdata); 803 } 804 805 SCIPfreeBufferArray(scip, &subvars); 806 807 return SCIP_OKAY; 808 } 809 810 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 811 static 812 SCIP_DECL_HEURFREE(heurFreeCrossover) 813 { /*lint --e{715}*/ 814 SCIP_HEURDATA* heurdata; 815 816 assert(heur != NULL); 817 assert(scip != NULL); 818 819 /* get heuristic data */ 820 heurdata = SCIPheurGetData(heur); 821 assert(heurdata != NULL); 822 823 /* free heuristic data */ 824 SCIPfreeBlockMemory(scip, &heurdata); 825 SCIPheurSetData(heur, NULL); 826 827 return SCIP_OKAY; 828 } 829 830 /** initialization method of primal heuristic (called after problem was transformed) */ 831 static 832 SCIP_DECL_HEURINIT(heurInitCrossover) 833 { /*lint --e{715}*/ 834 SCIP_HEURDATA* heurdata; 835 836 assert(heur != NULL); 837 assert(scip != NULL); 838 839 /* get heuristic's data */ 840 heurdata = SCIPheurGetData(heur); 841 assert(heurdata != NULL); 842 843 /* initialize data */ 844 heurdata->usednodes = 0; 845 heurdata->prevlastsol = NULL; 846 heurdata->prevbestsol = NULL; 847 heurdata->lasttuple = NULL; 848 heurdata->nfailures = 0; 849 heurdata->prevnsols = 0; 850 heurdata->nextnodenumber = 0; 851 852 /* create random number generator */ 853 SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE) ); 854 855 /* initialize hash table */ 856 SCIP_CALL( SCIPhashtableCreate(&heurdata->hashtable, SCIPblkmem(scip), HASHSIZE_SOLS, 857 hashGetKeySols, hashKeyEqSols, hashKeyValSols, NULL) ); 858 assert(heurdata->hashtable != NULL); 859 860 return SCIP_OKAY; 861 } 862 863 /** deinitialization method of primal heuristic (called before transformed problem is freed) */ 864 static 865 SCIP_DECL_HEUREXIT(heurExitCrossover) 866 { /*lint --e{715}*/ 867 SCIP_HEURDATA* heurdata; 868 SOLTUPLE* soltuple; 869 870 assert(heur != NULL); 871 assert(scip != NULL); 872 873 /* get heuristic data */ 874 heurdata = SCIPheurGetData(heur); 875 assert(heurdata != NULL); 876 soltuple = heurdata->lasttuple; 877 878 /* free all soltuples iteratively */ 879 while( soltuple != NULL ) 880 { 881 SOLTUPLE* tmp; 882 tmp = soltuple->prev; 883 SCIPfreeBlockMemoryArray(scip, &soltuple->indices, soltuple->size); 884 SCIPfreeBlockMemory(scip, &soltuple); 885 soltuple = tmp; 886 } 887 888 /* free random number generator */ 889 SCIPfreeRandom(scip, &heurdata->randnumgen); 890 891 /* free hash table */ 892 assert(heurdata->hashtable != NULL); 893 SCIPhashtableFree(&heurdata->hashtable); 894 895 return SCIP_OKAY; 896 } 897 898 /** execution method of primal heuristic */ 899 static 900 SCIP_DECL_HEUREXEC(heurExecCrossover) 901 { /*lint --e{715}*/ 902 SCIP* subscip; /* the subproblem created by crossover */ 903 SCIP_HEURDATA* heurdata; /* primal heuristic data */ 904 SCIP_VAR** vars; /* original problem's variables */ 905 SCIP_VAR** fixedvars; 906 SCIP_SOL** sols; 907 SCIP_RETCODE retcode; 908 SCIP_Longint nstallnodes; /* node limit for the subproblem */ 909 SCIP_Bool success; 910 SCIP_Real* fixedvals; 911 int* selection; /* pool of solutions crossover uses */ 912 int nvars; /* number of original problem's variables */ 913 int nbinvars; 914 int nintvars; 915 int nusedsols; 916 int nfixedvars; 917 918 assert(heur != NULL); 919 assert(scip != NULL); 920 assert(result != NULL); 921 922 /* get heuristic's data */ 923 heurdata = SCIPheurGetData(heur); 924 assert(heurdata != NULL); 925 nusedsols = heurdata->nusedsols; 926 927 *result = SCIP_DELAYED; 928 929 /* only call heuristic, if enough solutions are at hand */ 930 if( SCIPgetNSols(scip) < nusedsols ) 931 return SCIP_OKAY; 932 933 sols = SCIPgetSols(scip); 934 assert(sols != NULL); 935 936 /* if one good solution was found, heuristic should not be delayed any longer */ 937 if( sols[nusedsols-1] != heurdata->prevlastsol ) 938 { 939 heurdata->nextnodenumber = SCIPgetNNodes(scip); 940 if( sols[0] != heurdata->prevbestsol ) 941 heurdata->nfailures = 0; 942 } 943 /* in nonrandomized mode: only recall heuristic, if at least one new good solution was found in the meantime */ 944 else if( !heurdata->randomization ) 945 return SCIP_OKAY; 946 947 /* if heuristic should be delayed, wait until certain number of nodes is reached */ 948 if( SCIPgetNNodes(scip) < heurdata->nextnodenumber ) 949 return SCIP_OKAY; 950 951 /* only call heuristic, if enough nodes were processed since last incumbent */ 952 if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip, SCIPgetBestSol(scip)) < heurdata->nwaitingnodes 953 && (SCIPgetDepth(scip) > 0 || !heurdata->dontwaitatroot) ) 954 return SCIP_OKAY; 955 956 *result = SCIP_DIDNOTRUN; 957 958 /* calculate the maximal number of branching nodes until heuristic is aborted */ 959 nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip)); 960 961 /* reward Crossover if it succeeded often */ 962 nstallnodes = (SCIP_Longint) 963 (nstallnodes * (1.0 + 2.0*(SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur)+1.0))); 964 965 /* count the setup costs for the sub-MIP as 100 nodes */ 966 nstallnodes -= 100 * SCIPheurGetNCalls(heur); 967 nstallnodes += heurdata->nodesofs; 968 969 /* determine the node limit for the current process */ 970 nstallnodes -= heurdata->usednodes; 971 nstallnodes = MIN(nstallnodes, heurdata->maxnodes); 972 973 /* check whether we have enough nodes left to call subproblem solving */ 974 if( nstallnodes < heurdata->minnodes ) 975 return SCIP_OKAY; 976 977 /* consider time and memory limits of the main SCIP */ 978 SCIP_CALL( SCIPcheckCopyLimits(scip, &success) ); 979 980 if( !success ) 981 return SCIP_OKAY; 982 983 if( SCIPisStopped(scip) ) 984 return SCIP_OKAY; 985 986 /* get variable information */ 987 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) ); 988 assert(nvars > 0); 989 990 /* check whether discrete variables are available */ 991 if( nbinvars == 0 && nintvars == 0 ) 992 return SCIP_OKAY; 993 994 /* allocate necessary buffer storage for selection of variable fixings */ 995 SCIP_CALL( SCIPallocBufferArray(scip, &selection, nusedsols) ); 996 SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, nbinvars + nintvars) ); 997 SCIP_CALL( SCIPallocBufferArray(scip, &fixedvals, nbinvars + nintvars) ); 998 999 success = FALSE; 1000 nfixedvars = 0; 1001 /* determine fixings of variables with same value in a certain set of solutions */ 1002 SCIP_CALL( determineVariableFixings(scip, fixedvars, fixedvals, &nfixedvars, nbinvars + nintvars, selection, heurdata, &success) ); 1003 1004 heurdata->prevbestsol = SCIPgetBestSol(scip); 1005 heurdata->prevlastsol = sols[heurdata->nusedsols-1]; 1006 1007 /* if creation of sub-SCIP was aborted (e.g. due to number of fixings), free sub-SCIP and abort */ 1008 if( !success ) 1009 { 1010 /* this run will be counted as a failure since no new solution tuple could be generated or the neighborhood of the 1011 * solution was not fruitful in the sense that it was too big 1012 */ 1013 updateFailureStatistic(scip, heurdata); 1014 1015 goto TERMINATE; 1016 } 1017 1018 *result = SCIP_DIDNOTFIND; 1019 /* initializing the subproblem */ 1020 SCIP_CALL( SCIPcreate(&subscip) ); 1021 1022 /* setup and solve the subproblem and catch the return code */ 1023 retcode = setupAndSolveSubscipCrossover(scip, subscip, heur, heurdata, vars, 1024 fixedvars, fixedvals, nstallnodes, result, selection, nvars, nfixedvars, nusedsols); 1025 1026 /* free the subscip in any case */ 1027 SCIP_CALL( SCIPfree(&subscip) ); 1028 SCIP_CALL( retcode ); 1029 1030 TERMINATE: 1031 /* free buffer storage for variable fixings */ 1032 SCIPfreeBufferArray(scip, &fixedvals); 1033 SCIPfreeBufferArray(scip, &fixedvars); 1034 SCIPfreeBufferArray(scip, &selection); 1035 1036 return SCIP_OKAY; 1037 } 1038 1039 /* 1040 * primal heuristic specific interface methods 1041 */ 1042 1043 /** creates the crossover primal heuristic and includes it in SCIP */ 1044 SCIP_RETCODE SCIPincludeHeurCrossover( 1045 SCIP* scip /**< SCIP data structure */ 1046 ) 1047 { 1048 SCIP_HEURDATA* heurdata; 1049 SCIP_HEUR* heur; 1050 1051 /* create Crossover primal heuristic data */ 1052 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 1053 1054 /* include primal heuristic */ 1055 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 1056 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 1057 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecCrossover, heurdata) ); 1058 1059 assert(heur != NULL); 1060 1061 /* set non-NULL pointers to callback methods */ 1062 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyCrossover) ); 1063 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeCrossover) ); 1064 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitCrossover) ); 1065 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitCrossover) ); 1066 1067 /* add crossover primal heuristic parameters */ 1068 1069 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs", 1070 "number of nodes added to the contingent of the total nodes", 1071 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1072 1073 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes", 1074 "maximum number of nodes to regard in the subproblem", 1075 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1076 1077 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes", 1078 "minimum number of nodes required to start the subproblem", 1079 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1080 1081 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nusedsols", 1082 "number of solutions to be taken into account", 1083 &heurdata->nusedsols, FALSE, DEFAULT_NUSEDSOLS, 2, INT_MAX, NULL, NULL) ); 1084 1085 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes", 1086 "number of nodes without incumbent change that heuristic should wait", 1087 &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1088 1089 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot", 1090 "contingent of sub problem nodes in relation to the number of nodes of the original problem", 1091 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) ); 1092 1093 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate", 1094 "minimum percentage of integer variables that have to be fixed", 1095 &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) ); 1096 1097 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove", 1098 "factor by which Crossover should at least improve the incumbent", 1099 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) ); 1100 1101 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac", 1102 "factor by which the limit on the number of LP depends on the node limit", 1103 &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) ); 1104 1105 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/randomization", 1106 "should the choice which sols to take be randomized?", 1107 &heurdata->randomization, TRUE, DEFAULT_RANDOMIZATION, NULL, NULL) ); 1108 1109 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/dontwaitatroot", 1110 "should the nwaitingnodes parameter be ignored at the root node?", 1111 &heurdata->dontwaitatroot, TRUE, DEFAULT_DONTWAITATROOT, NULL, NULL) ); 1112 1113 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows", 1114 "should subproblem be created out of the rows in the LP rows?", 1115 &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) ); 1116 1117 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts", 1118 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?", 1119 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) ); 1120 1121 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/permute", 1122 "should the subproblem be permuted to increase diversification?", 1123 &heurdata->permute, TRUE, DEFAULT_PERMUTE, NULL, NULL) ); 1124 1125 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/bestsollimit", 1126 "limit on number of improving incumbent solutions in sub-CIP", 1127 &heurdata->bestsollimit, FALSE, DEFAULT_BESTSOLLIMIT, -1, INT_MAX, NULL, NULL) ); 1128 1129 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct", 1130 "should uct node selection be used at the beginning of the search?", 1131 &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) ); 1132 return SCIP_OKAY; 1133 } 1134