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_mutation.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief LNS heuristic that tries to randomly mutate the incumbent solution 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/heuristics.h" 35 #include "scip/heur_mutation.h" 36 #include "scip/pub_heur.h" 37 #include "scip/pub_message.h" 38 #include "scip/pub_misc.h" 39 #include "scip/pub_sol.h" 40 #include "scip/pub_var.h" 41 #include "scip/scip_branch.h" 42 #include "scip/scip_cons.h" 43 #include "scip/scip_copy.h" 44 #include "scip/scip_general.h" 45 #include "scip/scip_heur.h" 46 #include "scip/scip_mem.h" 47 #include "scip/scip_message.h" 48 #include "scip/scip_nodesel.h" 49 #include "scip/scip_numerics.h" 50 #include "scip/scip_param.h" 51 #include "scip/scip_prob.h" 52 #include "scip/scip_randnumgen.h" 53 #include "scip/scip_sol.h" 54 #include "scip/scip_solve.h" 55 #include "scip/scip_solvingstats.h" 56 #include <string.h> 57 58 #define HEUR_NAME "mutation" 59 #define HEUR_DESC "mutation heuristic randomly fixing variables" 60 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS 61 #define HEUR_PRIORITY -1103010 62 #define HEUR_FREQ -1 63 #define HEUR_FREQOFS 8 64 #define HEUR_MAXDEPTH -1 65 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE 66 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */ 67 68 #define DEFAULT_NODESOFS 500 /**< number of nodes added to the contingent of the total nodes */ 69 #define DEFAULT_MAXNODES 5000 /**< maximum number of nodes to regard in the subproblem */ 70 #define DEFAULT_MINIMPROVE 0.01 /**< factor by which Mutation should at least improve the incumbent */ 71 #define DEFAULT_MINNODES 500 /**< minimum number of nodes to regard in the subproblem */ 72 #define DEFAULT_MINFIXINGRATE 0.8 /**< minimum percentage of integer variables that have to be fixed */ 73 #define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */ 74 #define DEFAULT_NWAITINGNODES 200 /**< number of nodes without incumbent change that heuristic should wait */ 75 #define DEFAULT_USELPROWS FALSE /**< should subproblem be created out of the rows in the LP rows, 76 * otherwise, the copy constructors of the constraints handlers are used */ 77 #define DEFAULT_COPYCUTS TRUE /**< if DEFAULT_USELPROWS is FALSE, then should all active cuts from the 78 * cutpool of the original scip be copied to constraints of the subscip */ 79 #define DEFAULT_BESTSOLLIMIT -1 /**< limit on number of improving incumbent solutions in sub-CIP */ 80 #define DEFAULT_USEUCT FALSE /**< should uct node selection be used at the beginning of the search? */ 81 #define DEFAULT_RANDSEED 19 /**< initial random seed */ 82 /* 83 * Data structures 84 */ 85 86 /** primal heuristic data */ 87 struct SCIP_HeurData 88 { 89 int nodesofs; /**< number of nodes added to the contingent of the total nodes */ 90 int maxnodes; /**< maximum number of nodes to regard in the subproblem */ 91 int minnodes; /**< minimum number of nodes to regard in the subproblem */ 92 SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */ 93 int nwaitingnodes; /**< number of nodes without incumbent change that heuristic should wait */ 94 SCIP_Real minimprove; /**< factor by which Mutation should at least improve the incumbent */ 95 SCIP_Longint usednodes; /**< nodes already used by Mutation in earlier calls */ 96 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */ 97 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */ 98 SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */ 99 SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied 100 * to constraints in subproblem? 101 */ 102 int bestsollimit; /**< limit on number of improving incumbent solutions in sub-CIP */ 103 SCIP_Bool useuct; /**< should uct node selection be used at the beginning of the search? */ 104 }; 105 106 107 /* 108 * Local methods 109 */ 110 111 /** determine variables and values which should be fixed in the mutation subproblem */ 112 static 113 SCIP_RETCODE determineVariableFixings( 114 SCIP* scip, /**< original SCIP data structure */ 115 SCIP_VAR** fixedvars, /**< array to store the variables that should be fixed in the subproblem */ 116 SCIP_Real* fixedvals, /**< array to store the fixing values to fix variables in the subproblem */ 117 int* nfixedvars, /**< pointer to store the number of variables that should be fixed */ 118 SCIP_Real minfixingrate, /**< percentage of integer variables that have to be fixed */ 119 SCIP_RANDNUMGEN* randnumgen, /**< random number generator */ 120 SCIP_Bool* success /**< used to store whether the creation of the subproblem worked */ 121 ) 122 { 123 SCIP_VAR** vars; /* original scip variables */ 124 SCIP_SOL* sol; /* pool of solutions */ 125 126 int nvars; 127 int nbinvars; 128 int nintvars; 129 int ndiscretevars; 130 int i; 131 132 assert(fixedvars != NULL); 133 assert(fixedvals != NULL); 134 135 /* get required data of the original problem */ 136 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) ); 137 sol = SCIPgetBestSol(scip); 138 assert(sol != NULL); 139 140 /* compute the number of variables that should be fixed in the subproblem */ 141 *nfixedvars = (int)(minfixingrate * (nbinvars + nintvars)); 142 143 /* avoid the two corner cases that no or all discrete variables should be fixed */ 144 if( *nfixedvars == 0 || *nfixedvars == nbinvars + nintvars ) 145 { 146 *success = FALSE; 147 return SCIP_OKAY; 148 } 149 assert(*nfixedvars < nbinvars + nintvars); 150 151 ndiscretevars = nbinvars + nintvars; 152 /* copy the binary and integer variables into fixedvars */ 153 BMScopyMemoryArray(fixedvars, vars, ndiscretevars); 154 155 /* shuffle the array randomly */ 156 SCIPrandomPermuteArray(randnumgen, (void **)fixedvars, 0, nbinvars + nintvars); 157 158 *success = TRUE; 159 /* store the fixing values for the subset of variables that should be fixed */ 160 for( i = 0; i < *nfixedvars; ++i ) 161 { 162 /* fix all randomly marked variables */ 163 SCIP_Real solval; 164 SCIP_Real lb; 165 SCIP_Real ub; 166 167 solval = SCIPgetSolVal(scip, sol, fixedvars[i]); 168 lb = SCIPvarGetLbGlobal(fixedvars[i]); 169 ub = SCIPvarGetUbGlobal(fixedvars[i]); 170 assert(SCIPisLE(scip, lb, ub)); 171 172 /* due to dual reductions, it may happen that the solution value is not in 173 the variable's domain anymore */ 174 if( SCIPisLT(scip, solval, lb) ) 175 solval = lb; 176 else if( SCIPisGT(scip, solval, ub) ) 177 solval = ub; 178 179 /* we cannot fix to infinite solution values, better break in this case */ 180 if( SCIPisInfinity(scip, REALABS(solval)) ) 181 { 182 *success = FALSE; 183 break; 184 } 185 186 /* store the possibly adjusted solution value as fixing value */ 187 fixedvals[i] = solval; 188 } 189 190 return SCIP_OKAY; 191 } 192 193 /** setup and solve mutation sub-SCIP */ 194 static 195 SCIP_RETCODE setupAndSolveSubscipMutation( 196 SCIP* scip, /**< SCIP data structure */ 197 SCIP* subscip, /**< sub-SCIP data structure */ 198 SCIP_HEUR* heur, /**< mutation heuristic */ 199 SCIP_VAR** fixedvars, /**< array to store the variables that should be fixed in the subproblem */ 200 SCIP_Real* fixedvals, /**< array to store the fixing values to fix variables in the subproblem */ 201 int nfixedvars, /**< the number of variables that should be fixed */ 202 SCIP_Longint nsubnodes, /**< node limit for the subproblem */ 203 SCIP_RESULT* result /**< pointer to store the result */ 204 ) 205 { 206 SCIP_VAR** subvars; /* subproblem's variables */ 207 SCIP_VAR** vars; /* original problem's variables */ 208 SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */ 209 SCIP_HEURDATA* heurdata; 210 SCIP_Real cutoff; /* objective cutoff for the subproblem */ 211 SCIP_Real upperbound; 212 int nvars; /* number of original problem's variables */ 213 int i; 214 SCIP_Bool success; 215 216 assert(scip != NULL); 217 assert(subscip != NULL); 218 assert(heur != NULL); 219 assert(fixedvars != NULL); 220 assert(fixedvals != NULL); 221 222 heurdata = SCIPheurGetData(heur); 223 assert(heurdata != NULL); 224 225 vars = SCIPgetVars(scip); 226 nvars = SCIPgetNVars(scip); 227 228 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) ); 229 230 /* create the variable mapping hash map */ 231 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) ); 232 233 /* create a problem copy as sub SCIP */ 234 SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "mutation", fixedvars, fixedvals, nfixedvars, 235 heurdata->uselprows, heurdata->copycuts, &success, NULL) ); 236 237 for( i = 0; i < nvars; i++ ) 238 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]); 239 240 /* free hash map */ 241 SCIPhashmapFree(&varmapfw); 242 243 /* do not abort subproblem on CTRL-C */ 244 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) ); 245 246 #ifdef SCIP_DEBUG 247 /* for debugging, enable full output */ 248 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) ); 249 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) ); 250 #else 251 /* disable statistic timing inside sub SCIP and output to console */ 252 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) ); 253 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) ); 254 #endif 255 256 /* set limits for the subproblem */ 257 SCIP_CALL( SCIPcopyLimits(scip, subscip) ); 258 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nsubnodes) ); 259 SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsollimit) ); 260 261 /* forbid recursive call of heuristics and separators solving subMIPs */ 262 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) ); 263 264 /* disable cutting plane separation */ 265 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) ); 266 267 /* disable expensive presolving */ 268 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) ); 269 270 /* use best estimate node selection */ 271 if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") ) 272 { 273 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) ); 274 } 275 276 /* activate uct node selection at the top of the tree */ 277 if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") ) 278 { 279 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) ); 280 } 281 282 /* use inference branching */ 283 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") ) 284 { 285 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) ); 286 } 287 288 /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */ 289 if( !SCIPisParamFixed(subscip, "conflict/enable") ) 290 { 291 SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) ); 292 } 293 if( !SCIPisParamFixed(subscip, "conflict/useboundlp") ) 294 { 295 SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') ); 296 } 297 if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") ) 298 { 299 SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) ); 300 } 301 302 /* speed up sub-SCIP by not checking dual LP feasibility */ 303 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) ); 304 305 /* add an objective cutoff */ 306 assert( !SCIPisInfinity(scip, SCIPgetUpperbound(scip)) ); 307 308 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip); 309 if( !SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) ) 310 { 311 cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip) 312 + heurdata->minimprove * SCIPgetLowerbound(scip); 313 } 314 else 315 { 316 if( SCIPgetUpperbound(scip) >= 0 ) 317 cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip); 318 else 319 cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip); 320 } 321 cutoff = MIN(upperbound, cutoff); 322 SCIP_CALL(SCIPsetObjlimit(subscip, cutoff)); 323 324 /* solve the subproblem 325 * 326 * Errors in solving the subproblem should not kill the overall solving process 327 * Hence, the return code is caught but only in debug mode, SCIP will stop. 328 */ 329 SCIPdebugMsg(scip, "Solve Mutation subMIP\n"); 330 SCIP_CALL_ABORT( SCIPsolve(subscip) ); 331 332 /* transfer variable statistics from sub-SCIP */ 333 SCIP_CALL( SCIPmergeVariableStatistics(subscip, scip, subvars, vars, nvars) ); 334 335 /* print solving statistics of subproblem if we are in SCIP's debug mode */ 336 SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) ); 337 338 heurdata->usednodes += SCIPgetNNodes(subscip); 339 340 /* check, whether a solution was found; 341 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted 342 */ 343 SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, NULL) ); 344 if( success ) 345 *result = SCIP_FOUNDSOL; 346 347 /* free subproblem */ 348 SCIPfreeBufferArray(scip, &subvars); 349 350 return SCIP_OKAY; 351 } 352 353 354 /* 355 * Callback methods of primal heuristic 356 */ 357 358 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 359 static 360 SCIP_DECL_HEURCOPY(heurCopyMutation) 361 { /*lint --e{715}*/ 362 assert(scip != NULL); 363 assert(heur != NULL); 364 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 365 366 /* call inclusion method of primal heuristic */ 367 SCIP_CALL( SCIPincludeHeurMutation(scip) ); 368 369 return SCIP_OKAY; 370 } 371 372 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 373 static 374 SCIP_DECL_HEURFREE(heurFreeMutation) 375 { /*lint --e{715}*/ 376 SCIP_HEURDATA* heurdata; 377 378 assert(heur != NULL); 379 assert(scip != NULL); 380 381 /* get heuristic data */ 382 heurdata = SCIPheurGetData(heur); 383 assert(heurdata != NULL); 384 385 /* free heuristic data */ 386 SCIPfreeBlockMemory(scip, &heurdata); 387 SCIPheurSetData(heur, NULL); 388 389 return SCIP_OKAY; 390 } 391 392 /** initialization method of primal heuristic (called after problem was transformed) */ 393 static 394 SCIP_DECL_HEURINIT(heurInitMutation) 395 { /*lint --e{715}*/ 396 SCIP_HEURDATA* heurdata; 397 398 assert(heur != NULL); 399 assert(scip != NULL); 400 401 /* get heuristic's data */ 402 heurdata = SCIPheurGetData(heur); 403 assert(heurdata != NULL); 404 405 /* initialize data */ 406 heurdata->usednodes = 0; 407 408 /* create random number generator */ 409 SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen, 410 DEFAULT_RANDSEED, TRUE) ); 411 412 return SCIP_OKAY; 413 } 414 415 /** deinitialization method of primal heuristic */ 416 static 417 SCIP_DECL_HEUREXIT(heurExitMutation) 418 { /*lint --e{715}*/ 419 SCIP_HEURDATA* heurdata; 420 421 assert(heur != NULL); 422 assert(scip != NULL); 423 424 /* get heuristic data */ 425 heurdata = SCIPheurGetData(heur); 426 assert(heurdata != NULL); 427 428 /* free random number generator */ 429 SCIPfreeRandom(scip, &heurdata->randnumgen); 430 431 return SCIP_OKAY; 432 } 433 434 /** execution method of primal heuristic */ 435 static 436 SCIP_DECL_HEUREXEC(heurExecMutation) 437 { /*lint --e{715}*/ 438 SCIP_Longint maxnnodes; 439 SCIP_Longint nsubnodes; /* node limit for the subproblem */ 440 441 SCIP_HEURDATA* heurdata; /* heuristic's data */ 442 SCIP* subscip; /* the subproblem created by mutation */ 443 SCIP_VAR** fixedvars; /* array to store variables that should be fixed in the subproblem */ 444 SCIP_Real* fixedvals; /* array to store fixing values for the variables */ 445 446 SCIP_Real maxnnodesr; 447 448 int nfixedvars; 449 int nbinvars; 450 int nintvars; 451 452 SCIP_Bool success; 453 454 SCIP_RETCODE retcode; 455 456 assert( heur != NULL ); 457 assert( scip != NULL ); 458 assert( result != NULL ); 459 460 /* get heuristic's data */ 461 heurdata = SCIPheurGetData(heur); 462 assert(heurdata != NULL); 463 464 *result = SCIP_DELAYED; 465 466 /* only call heuristic, if feasible solution is available */ 467 if( SCIPgetNSols(scip) <= 0 ) 468 return SCIP_OKAY; 469 470 /* only call heuristic, if the best solution comes from transformed problem */ 471 assert(SCIPgetBestSol(scip) != NULL); 472 if( SCIPsolIsOriginal(SCIPgetBestSol(scip)) ) 473 return SCIP_OKAY; 474 475 /* only call heuristic, if enough nodes were processed since last incumbent */ 476 if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip,SCIPgetBestSol(scip)) < heurdata->nwaitingnodes) 477 return SCIP_OKAY; 478 479 *result = SCIP_DIDNOTRUN; 480 481 SCIP_CALL( SCIPgetVarsData(scip, NULL, NULL, &nbinvars, &nintvars, NULL, NULL) ); 482 483 /* only call heuristic, if discrete variables are present */ 484 if( nbinvars + nintvars == 0 ) 485 return SCIP_OKAY; 486 487 /* calculate the maximal number of branching nodes until heuristic is aborted */ 488 maxnnodesr = heurdata->nodesquot * SCIPgetNNodes(scip); 489 490 /* reward mutation if it succeeded often, count the setup costs for the sub-MIP as 100 nodes */ 491 maxnnodesr *= 1.0 + 2.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0); 492 maxnnodes = (SCIP_Longint) maxnnodesr - 100 * SCIPheurGetNCalls(heur); 493 maxnnodes += heurdata->nodesofs; 494 495 /* determine the node limit for the current process */ 496 nsubnodes = maxnnodes - heurdata->usednodes; 497 nsubnodes = MIN(nsubnodes, heurdata->maxnodes); 498 499 /* check whether we have enough nodes left to call subproblem solving */ 500 if( nsubnodes < heurdata->minnodes ) 501 return SCIP_OKAY; 502 503 if( SCIPisStopped(scip) ) 504 return SCIP_OKAY; 505 506 /* check whether there is enough time and memory left */ 507 SCIP_CALL( SCIPcheckCopyLimits(scip, &success) ); 508 509 if( !success ) 510 return SCIP_OKAY; 511 512 SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, nbinvars + nintvars) ); 513 SCIP_CALL( SCIPallocBufferArray(scip, &fixedvals, nbinvars + nintvars) ); 514 515 /* determine variables that should be fixed in the mutation subproblem */ 516 SCIP_CALL( determineVariableFixings(scip, fixedvars, fixedvals, &nfixedvars, heurdata->minfixingrate, heurdata->randnumgen, &success) ); 517 518 /* terminate if it is not possible to create the subproblem */ 519 if( !success ) 520 { 521 SCIPdebugMsg(scip, "Could not create the subproblem -> skip call\n"); 522 goto TERMINATE; 523 } 524 525 *result = SCIP_DIDNOTFIND; 526 527 /* initializing the subproblem */ 528 SCIP_CALL( SCIPcreate(&subscip) ); 529 530 /* setup and solve the subproblem and catch the return code */ 531 retcode = setupAndSolveSubscipMutation(scip, subscip, heur, fixedvars, fixedvals, nfixedvars, nsubnodes, result); 532 533 /* free the subscip in any case */ 534 SCIP_CALL( SCIPfree(&subscip) ); 535 SCIP_CALL( retcode ); 536 537 /* free storage for subproblem fixings */ 538 TERMINATE: 539 SCIPfreeBufferArray(scip, &fixedvals); 540 SCIPfreeBufferArray(scip, &fixedvars); 541 542 return SCIP_OKAY; 543 } 544 545 /* 546 * primal heuristic specific interface methods 547 */ 548 549 /** creates the mutation primal heuristic and includes it in SCIP */ 550 SCIP_RETCODE SCIPincludeHeurMutation( 551 SCIP* scip /**< SCIP data structure */ 552 ) 553 { 554 SCIP_HEURDATA* heurdata; 555 SCIP_HEUR* heur; 556 557 /* create Mutation primal heuristic data */ 558 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 559 560 /* include primal heuristic */ 561 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 562 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 563 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecMutation, heurdata) ); 564 565 assert(heur != NULL); 566 567 /* set non-NULL pointers to callback methods */ 568 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyMutation) ); 569 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeMutation) ); 570 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitMutation) ); 571 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitMutation) ); 572 573 /* add mutation primal heuristic parameters */ 574 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nodesofs", 575 "number of nodes added to the contingent of the total nodes", 576 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0, INT_MAX, NULL, NULL) ); 577 578 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxnodes", 579 "maximum number of nodes to regard in the subproblem", 580 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) ); 581 582 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minnodes", 583 "minimum number of nodes required to start the subproblem", 584 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) ); 585 586 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes", 587 "number of nodes without incumbent change that heuristic should wait", 588 &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0, INT_MAX, NULL, NULL) ); 589 590 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot", 591 "contingent of sub problem nodes in relation to the number of nodes of the original problem", 592 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) ); 593 594 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate", 595 "percentage of integer variables that have to be fixed", 596 &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, SCIPsumepsilon(scip), 1.0-SCIPsumepsilon(scip), NULL, NULL) ); 597 598 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove", 599 "factor by which " HEUR_NAME " should at least improve the incumbent", 600 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) ); 601 602 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows", 603 "should subproblem be created out of the rows in the LP rows?", 604 &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) ); 605 606 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts", 607 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?", 608 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) ); 609 610 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/bestsollimit", 611 "limit on number of improving incumbent solutions in sub-CIP", 612 &heurdata->bestsollimit, FALSE, DEFAULT_BESTSOLLIMIT, -1, INT_MAX, NULL, NULL) ); 613 614 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct", 615 "should uct node selection be used at the beginning of the search?", 616 &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) ); 617 618 return SCIP_OKAY; 619 } 620