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_rins.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief LNS heuristic that combines the incumbent with the LP optimum 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_rins.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_lp.h" 49 #include "scip/scip_mem.h" 50 #include "scip/scip_message.h" 51 #include "scip/scip_nodesel.h" 52 #include "scip/scip_numerics.h" 53 #include "scip/scip_param.h" 54 #include "scip/scip_prob.h" 55 #include "scip/scip_sol.h" 56 #include "scip/scip_solve.h" 57 #include "scip/scip_solvingstats.h" 58 #include <string.h> 59 60 #define HEUR_NAME "rins" 61 #define HEUR_DESC "relaxation induced neighborhood search by Danna, Rothberg, and Le Pape" 62 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS 63 #define HEUR_PRIORITY -1101000 64 #define HEUR_FREQ 25 65 #define HEUR_FREQOFS 0 66 #define HEUR_MAXDEPTH -1 67 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE 68 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */ 69 70 #define DEFAULT_NODESOFS 500 /* number of nodes added to the contingent of the total nodes */ 71 #define DEFAULT_MAXNODES 5000 /* maximum number of nodes to regard in the subproblem */ 72 #define DEFAULT_MINNODES 50 /* minimum number of nodes to regard in the subproblem */ 73 #define DEFAULT_MINIMPROVE 0.01 /* factor by which RINS should at least improve the incumbent */ 74 #define DEFAULT_MINFIXINGRATE 0.3 /* minimum percentage of integer variables that have to be fixed */ 75 #define DEFAULT_NODESQUOT 0.3 /* subproblem nodes in relation to nodes of the original problem */ 76 #define DEFAULT_LPLIMFAC 2.0 /* factor by which the limit on the number of LP depends on the node limit */ 77 #define DEFAULT_NWAITINGNODES 200 /* number of nodes without incumbent change that heuristic should wait */ 78 #define DEFAULT_USELPROWS FALSE /* should subproblem be created out of the rows in the LP rows, 79 * otherwise, the copy constructors of the constraints handlers are used */ 80 #define DEFAULT_COPYCUTS TRUE /* if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool 81 * of the original scip be copied to constraints of the subscip 82 */ 83 #define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */ 84 85 /* event handler properties */ 86 #define EVENTHDLR_NAME "Rins" 87 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" 88 89 /* 90 * Data structures 91 */ 92 93 /** primal heuristic data */ 94 struct SCIP_HeurData 95 { 96 int nodesofs; /**< number of nodes added to the contingent of the total nodes */ 97 int maxnodes; /**< maximum number of nodes to regard in the subproblem */ 98 int minnodes; /**< minimum number of nodes to regard in the subproblem */ 99 SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */ 100 int nwaitingnodes; /**< number of nodes without incumbent change that heuristic should wait */ 101 SCIP_Real minimprove; /**< factor by which RINS should at least improve the incumbent */ 102 SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/ 103 SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */ 104 SCIP_Longint usednodes; /**< nodes already used by RINS in earlier calls */ 105 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */ 106 SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */ 107 SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied 108 * to constraints in subproblem? 109 */ 110 SCIP_Bool useuct; /**< should uct node selection be used at the beginning of the search? */ 111 }; 112 113 /* 114 * Local methods 115 */ 116 117 118 119 120 /** determines variable fixings for RINS 121 * 122 * RINS fixes variables with matching solution values in the current LP and the 123 * incumbent solution 124 */ 125 static 126 SCIP_RETCODE determineFixings( 127 SCIP* scip, /**< original SCIP data structure */ 128 SCIP_VAR** fixedvars, /**< array to store source SCIP variables that should be fixed in the copy */ 129 SCIP_Real* fixedvals, /**< array to store fixing values for variables that should be fixed in the copy */ 130 int* nfixedvars, /**< pointer to store the number of variables that RINS can fix */ 131 int fixedvarssize, /**< size of the buffer arrays to store potential fixings */ 132 SCIP_Real minfixingrate, /**< percentage of integer variables that have to be fixed */ 133 SCIP_Bool* success /**< pointer to store whether sufficiently many variable fixings were found */ 134 ) 135 { 136 SCIP_SOL* bestsol; /* incumbent solution of the original problem */ 137 SCIP_VAR** vars; /* original scip variables */ 138 SCIP_Real fixingrate; 139 140 int nvars; 141 int nbinvars; 142 int nintvars; 143 int i; 144 int fixingcounter; 145 146 assert(fixedvals != NULL); 147 assert(fixedvars != NULL); 148 assert(nfixedvars != NULL); 149 150 /* get required data of the original problem */ 151 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) ); 152 bestsol = SCIPgetBestSol(scip); 153 assert(bestsol != NULL); 154 155 fixingcounter = 0; 156 assert(fixedvarssize >= nbinvars + nintvars); 157 158 /* determine variables to fix in the subproblem */ 159 for( i = 0; i < nbinvars + nintvars; i++ ) 160 { 161 SCIP_Real lpsolval; 162 SCIP_Real solval; 163 164 /* get the current LP solution and the incumbent solution for each variable */ 165 lpsolval = SCIPvarGetLPSol(vars[i]); 166 solval = SCIPgetSolVal(scip, bestsol, vars[i]); 167 168 /* iff both solutions are equal, variable is stored to be fixed */ 169 if( SCIPisFeasEQ(scip, lpsolval, solval) ) 170 { 171 /* store the fixing and increase the number of fixed variables */ 172 fixedvars[fixingcounter] = vars[i]; 173 fixedvals[fixingcounter] = solval; 174 fixingcounter++; 175 } 176 } 177 178 /* store the number of fixings */ 179 *nfixedvars = fixingcounter; 180 181 /* abort, if all variables should be fixed */ 182 if( fixingcounter == nbinvars + nintvars ) 183 { 184 *success = FALSE; 185 return SCIP_OKAY; 186 } 187 else 188 fixingrate = (SCIP_Real)fixingcounter / (SCIP_Real)(MAX(nbinvars + nintvars, 1)); 189 190 /* abort, if the amount of fixed variables is insufficient */ 191 if( fixingrate < minfixingrate ) 192 { 193 *success = FALSE; 194 return SCIP_OKAY; 195 } 196 197 *success = TRUE; 198 return SCIP_OKAY; 199 } 200 201 static 202 SCIP_DECL_EVENTEXEC(eventExecRins); 203 204 /** wrapper for the part of heuristic that runs a subscip. Wrapper is needed to avoid possible ressource leaks */ 205 static 206 SCIP_RETCODE wrapperRins( 207 SCIP* scip, /**< original SCIP data structure */ 208 SCIP* subscip, /**< SCIP structure of the subproblem */ 209 SCIP_HEUR* heur, /**< Heuristic pointer */ 210 SCIP_HEURDATA* heurdata, /**< Heuristic's data */ 211 SCIP_VAR** vars, /**< original problem's variables */ 212 SCIP_VAR** fixedvars, /**< Fixed variables of original SCIP */ 213 SCIP_Real* fixedvals, /**< Fixed values of original SCIP */ 214 SCIP_RESULT* result, /**< Result pointer */ 215 int nvars, /**< Number of variables */ 216 int nfixedvars, /**< Number of fixed variables */ 217 SCIP_Longint nnodes /**< Number of nodes in the b&b tree */ 218 ) 219 { 220 SCIP_VAR** subvars; /* variables of the subscip */ 221 SCIP_HASHMAP* varmapfw; /* hashmap for mapping between vars of scip and subscip */ 222 SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */ 223 SCIP_Real upperbound; /* upperbound of the original SCIP */ 224 SCIP_Real cutoff; /* objective cutoff for the subproblem */ 225 226 SCIP_Bool success; 227 228 int i; 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, "rins", fixedvars, fixedvals, nfixedvars, 235 heurdata->uselprows, heurdata->copycuts, &success, NULL) ); 236 237 eventhdlr = NULL; 238 /* create event handler for LP events */ 239 SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecRins, NULL) ); 240 if( eventhdlr == NULL ) 241 { 242 SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n"); 243 return SCIP_PLUGINNOTFOUND; 244 } 245 246 /* copy subproblem variables from map to obtain the same order */ 247 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) ); 248 for( i = 0; i < nvars; i++ ) 249 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]); 250 251 /* free hash map */ 252 SCIPhashmapFree(&varmapfw); 253 254 /* do not abort subproblem on CTRL-C */ 255 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) ); 256 257 #ifdef SCIP_DEBUG 258 /* for debugging, enable full output */ 259 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", SCIP_VERBLEVEL_FULL) ); 260 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) ); 261 #else 262 /* disable statistic timing inside sub SCIP and output to console */ 263 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", (int) SCIP_VERBLEVEL_NONE) ); 264 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) ); 265 #endif 266 267 /* set limits for the subproblem */ 268 SCIP_CALL( SCIPcopyLimits(scip, subscip) ); 269 heurdata->nodelimit = nnodes; 270 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nnodes) ); 271 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", MAX(10, nnodes/10)) ); 272 SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", 3) ); 273 274 /* forbid recursive call of heuristics and separators solving subMIPs */ 275 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) ); 276 277 /* disable cutting plane separation */ 278 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) ); 279 280 /* disable expensive presolving */ 281 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) ); 282 283 /* use best estimate node selection */ 284 if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") ) 285 { 286 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) ); 287 } 288 289 /* activate uct node selection at the top of the tree */ 290 if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") ) 291 { 292 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) ); 293 } 294 295 /* use inference branching */ 296 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") ) 297 { 298 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) ); 299 } 300 301 /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */ 302 if( !SCIPisParamFixed(subscip, "conflict/enable") ) 303 { 304 SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) ); 305 } 306 if( !SCIPisParamFixed(subscip, "conflict/useboundlp") ) 307 { 308 SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') ); 309 } 310 if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") ) 311 { 312 SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) ); 313 } 314 315 /* speed up sub-SCIP by not checking dual LP feasibility */ 316 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) ); 317 318 /* add an objective cutoff */ 319 assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) ); 320 321 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip); 322 if( !SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) ) 323 { 324 cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip) + heurdata->minimprove * SCIPgetLowerbound(scip); 325 } 326 else 327 { 328 if( SCIPgetUpperbound(scip) >= 0 ) 329 cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip); 330 else 331 cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip); 332 } 333 cutoff = MIN(upperbound, cutoff); 334 SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) ); 335 336 /* catch LP events of sub-SCIP */ 337 SCIP_CALL( SCIPtransformProb(subscip) ); 338 SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) ); 339 340 /* Errors in solving the subproblem should not kill the overall solving process 341 * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 342 */ 343 /* solve the subproblem */ 344 SCIP_CALL_ABORT( SCIPsolve(subscip) ); 345 346 /* drop LP events of sub-SCIP */ 347 SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) ); 348 349 /* we try to merge variable statistics with those of our main SCIP */ 350 SCIP_CALL( SCIPmergeVariableStatistics(subscip, scip, subvars, vars, nvars) ); 351 352 /* print solving statistics of subproblem if we are in SCIP's debug mode */ 353 SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) ); 354 355 heurdata->usednodes += SCIPgetNNodes(subscip); 356 357 SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, NULL) ); 358 if( success ) 359 *result = SCIP_FOUNDSOL; 360 361 /* free subproblem */ 362 SCIPfreeBufferArray(scip, &subvars); 363 364 return SCIP_OKAY; 365 } 366 367 /* ---------------- Callback methods of event handler ---------------- */ 368 369 /* exec the event handler 370 * 371 * we interrupt the solution process 372 */ 373 static 374 SCIP_DECL_EVENTEXEC(eventExecRins) 375 { 376 SCIP_HEURDATA* heurdata; 377 378 assert(eventhdlr != NULL); 379 assert(eventdata != NULL); 380 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 381 assert(event != NULL); 382 assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED); 383 384 heurdata = (SCIP_HEURDATA*)eventdata; 385 assert(heurdata != NULL); 386 387 /* interrupt solution process of sub-SCIP */ 388 if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit ) 389 { 390 SCIPdebugMsg(scip, "interrupt after %" SCIP_LONGINT_FORMAT " LPs\n",SCIPgetNLPs(scip)); 391 SCIP_CALL( SCIPinterruptSolve(scip) ); 392 } 393 394 return SCIP_OKAY; 395 } 396 397 398 /* 399 * Callback methods of primal heuristic 400 */ 401 402 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 403 static 404 SCIP_DECL_HEURCOPY(heurCopyRins) 405 { /*lint --e{715}*/ 406 assert(scip != NULL); 407 assert(heur != NULL); 408 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 409 410 /* call inclusion method of primal heuristic */ 411 SCIP_CALL( SCIPincludeHeurRins(scip) ); 412 413 return SCIP_OKAY; 414 } 415 416 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 417 static 418 SCIP_DECL_HEURFREE(heurFreeRins) 419 { /*lint --e{715}*/ 420 SCIP_HEURDATA* heurdata; 421 422 assert( heur != NULL ); 423 assert( scip != NULL ); 424 425 /* get heuristic data */ 426 heurdata = SCIPheurGetData(heur); 427 assert( heurdata != NULL ); 428 429 /* free heuristic data */ 430 SCIPfreeBlockMemory(scip, &heurdata); 431 SCIPheurSetData(heur, NULL); 432 433 return SCIP_OKAY; 434 } 435 436 437 /** initialization method of primal heuristic (called after problem was transformed) */ 438 static 439 SCIP_DECL_HEURINIT(heurInitRins) 440 { /*lint --e{715}*/ 441 SCIP_HEURDATA* heurdata; 442 443 assert( heur != NULL ); 444 assert( scip != NULL ); 445 446 /* get heuristic's data */ 447 heurdata = SCIPheurGetData(heur); 448 assert( heurdata != NULL ); 449 450 /* initialize data */ 451 heurdata->usednodes = 0; 452 453 return SCIP_OKAY; 454 } 455 456 457 /** execution method of primal heuristic */ 458 static 459 SCIP_DECL_HEUREXEC(heurExecRins) 460 { /*lint --e{715}*/ 461 SCIP_Longint nnodes; 462 463 SCIP_HEURDATA* heurdata; /* heuristic's data */ 464 SCIP* subscip; /* the subproblem created by RINS */ 465 SCIP_VAR** vars; /* original problem's variables */ 466 SCIP_VAR** fixedvars; 467 SCIP_Real* fixedvals; 468 469 SCIP_RETCODE retcode; /* retcode needed for wrapper method */ 470 471 int nvars; 472 int nbinvars; 473 int nintvars; 474 int nfixedvars; 475 476 SCIP_Bool success; 477 478 assert( heur != NULL ); 479 assert( scip != NULL ); 480 assert( result != NULL ); 481 assert( SCIPhasCurrentNodeLP(scip) ); 482 483 *result = SCIP_DELAYED; 484 485 /* do not call heuristic of node was already detected to be infeasible */ 486 if( nodeinfeasible ) 487 return SCIP_OKAY; 488 489 /* get heuristic's data */ 490 heurdata = SCIPheurGetData(heur); 491 assert( heurdata != NULL ); 492 493 /* only call heuristic, if an optimal LP solution and a feasible solution are at hand */ 494 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL || SCIPgetNSols(scip) <= 0 ) 495 return SCIP_OKAY; 496 497 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */ 498 if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) ) 499 return SCIP_OKAY; 500 501 /* only call heuristic, if the best solution comes from transformed problem */ 502 assert( SCIPgetBestSol(scip) != NULL ); 503 if( SCIPsolIsOriginal(SCIPgetBestSol(scip)) ) 504 return SCIP_OKAY; 505 506 /* only call heuristic, if enough nodes were processed since last incumbent */ 507 if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip,SCIPgetBestSol(scip)) < heurdata->nwaitingnodes) 508 return SCIP_OKAY; 509 510 *result = SCIP_DIDNOTRUN; 511 512 /* calculate the maximal number of branching nodes until heuristic is aborted */ 513 nnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip)); 514 515 /* reward RINS if it succeeded often */ 516 nnodes = (SCIP_Longint)(nnodes * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0)); 517 nnodes -= (SCIP_Longint)(100.0 * SCIPheurGetNCalls(heur)); /* count the setup costs for the sub-MIP as 100 nodes */ 518 nnodes += heurdata->nodesofs; 519 520 /* determine the node limit for the current process */ 521 nnodes -= heurdata->usednodes; 522 nnodes = MIN(nnodes, heurdata->maxnodes); 523 524 /* check whether we have enough nodes left to call subproblem solving */ 525 if( nnodes < heurdata->minnodes ) 526 return SCIP_OKAY; 527 528 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) ); 529 530 /* check whether discrete variables are available */ 531 if( nbinvars == 0 && nintvars == 0 ) 532 return SCIP_OKAY; 533 534 if( SCIPisStopped(scip) ) 535 return SCIP_OKAY; 536 537 /* allocate buffer storage to hold the RINS fixings */ 538 SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, nbinvars + nintvars) ); 539 SCIP_CALL( SCIPallocBufferArray(scip, &fixedvals, nbinvars + nintvars) ); 540 541 success = FALSE; 542 543 nfixedvars = 0; 544 /* determine possible fixings for RINS: variables with same value in bestsol and LP relaxation */ 545 SCIP_CALL( determineFixings(scip, fixedvars, fixedvals, &nfixedvars, nbinvars + nintvars, heurdata->minfixingrate, &success) ); 546 547 /* too few variables could be fixed by the RINS scheme */ 548 if( !success ) 549 goto TERMINATE; 550 551 /* check whether there is enough time and memory left */ 552 SCIP_CALL( SCIPcheckCopyLimits(scip, &success) ); 553 554 /* abort if no time is left or not enough memory to create a copy of SCIP */ 555 if( !success ) 556 goto TERMINATE; 557 558 assert(nfixedvars > 0 && nfixedvars < nbinvars + nintvars); 559 560 *result = SCIP_DIDNOTFIND; 561 562 SCIPdebugMsg(scip, "RINS heuristic fixes %d out of %d binary+integer variables\n", nfixedvars, nbinvars + nintvars); 563 SCIP_CALL( SCIPcreate(&subscip) ); 564 565 retcode = wrapperRins(scip, subscip, heur, heurdata, vars, fixedvars, fixedvals, result, nvars, nfixedvars, nnodes); 566 567 SCIP_CALL( SCIPfree(&subscip) ); 568 569 SCIP_CALL( retcode ); 570 571 TERMINATE: 572 SCIPfreeBufferArray(scip, &fixedvals); 573 SCIPfreeBufferArray(scip, &fixedvars); 574 575 return SCIP_OKAY; 576 } 577 578 /* 579 * primal heuristic specific interface methods 580 */ 581 582 /** creates the RINS primal heuristic and includes it in SCIP */ 583 SCIP_RETCODE SCIPincludeHeurRins( 584 SCIP* scip /**< SCIP data structure */ 585 ) 586 { 587 SCIP_HEURDATA* heurdata; 588 SCIP_HEUR* heur; 589 590 /* create Rins primal heuristic data */ 591 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 592 593 /* include primal heuristic */ 594 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 595 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 596 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecRins, heurdata) ); 597 598 assert(heur != NULL); 599 600 /* set non-NULL pointers to callback methods */ 601 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyRins) ); 602 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeRins) ); 603 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitRins) ); 604 605 /* add RINS primal heuristic parameters */ 606 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nodesofs", 607 "number of nodes added to the contingent of the total nodes", 608 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0, INT_MAX, NULL, NULL) ); 609 610 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxnodes", 611 "maximum number of nodes to regard in the subproblem", 612 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) ); 613 614 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minnodes", 615 "minimum number of nodes required to start the subproblem", 616 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) ); 617 618 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot", 619 "contingent of sub problem nodes in relation to the number of nodes of the original problem", 620 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) ); 621 622 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes", 623 "number of nodes without incumbent change that heuristic should wait", 624 &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0, INT_MAX, NULL, NULL) ); 625 626 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove", 627 "factor by which " HEUR_NAME " should at least improve the incumbent", 628 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) ); 629 630 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate", 631 "minimum percentage of integer variables that have to be fixed", 632 &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) ); 633 634 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac", 635 "factor by which the limit on the number of LP depends on the node limit", 636 &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) ); 637 638 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows", 639 "should subproblem be created out of the rows in the LP rows?", 640 &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) ); 641 642 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts", 643 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?", 644 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) ); 645 646 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct", 647 "should uct node selection be used at the beginning of the search?", 648 &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) ); 649 650 return SCIP_OKAY; 651 } 652