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_localbranching.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief Local branching heuristic according to Fischetti and Lodi 28 * @author Timo Berthold 29 * @author Marc Pfetsch 30 */ 31 32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 33 34 #include "blockmemshell/memory.h" 35 #include "scip/cons_linear.h" 36 #include "scip/heuristics.h" 37 #include "scip/heur_localbranching.h" 38 #include "scip/pub_event.h" 39 #include "scip/pub_heur.h" 40 #include "scip/pub_message.h" 41 #include "scip/pub_misc.h" 42 #include "scip/pub_sol.h" 43 #include "scip/pub_var.h" 44 #include "scip/scip_branch.h" 45 #include "scip/scip_cons.h" 46 #include "scip/scip_copy.h" 47 #include "scip/scip_event.h" 48 #include "scip/scip_general.h" 49 #include "scip/scip_heur.h" 50 #include "scip/scip_mem.h" 51 #include "scip/scip_message.h" 52 #include "scip/scip_nodesel.h" 53 #include "scip/scip_numerics.h" 54 #include "scip/scip_param.h" 55 #include "scip/scip_prob.h" 56 #include "scip/scip_sol.h" 57 #include "scip/scip_solve.h" 58 #include "scip/scip_solvingstats.h" 59 #include <string.h> 60 61 #define HEUR_NAME "localbranching" 62 #define HEUR_DESC "local branching heuristic by Fischetti and Lodi" 63 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS 64 #define HEUR_PRIORITY -1102000 65 #define HEUR_FREQ -1 66 #define HEUR_FREQOFS 0 67 #define HEUR_MAXDEPTH -1 68 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE 69 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */ 70 71 #define DEFAULT_NEIGHBORHOODSIZE 18 /* radius of the incumbents neighborhood to be searched */ 72 #define DEFAULT_NODESOFS 1000 /* number of nodes added to the contingent of the total nodes */ 73 #define DEFAULT_MAXNODES 10000 /* maximum number of nodes to regard in the subproblem */ 74 #define DEFAULT_MINIMPROVE 0.01 /* factor by which localbranching should at least improve the incumbent */ 75 #define DEFAULT_MINNODES 1000 /* minimum number of nodes required to start the subproblem */ 76 #define DEFAULT_NODESQUOT 0.05 /* contingent of sub problem nodes in relation to original nodes */ 77 #define DEFAULT_LPLIMFAC 1.5 /* factor by which the limit on the number of LP depends on the node limit */ 78 #define DEFAULT_NWAITINGNODES 200 /* number of nodes without incumbent change that heuristic should wait */ 79 #define DEFAULT_USELPROWS FALSE /* should subproblem be created out of the rows in the LP rows, 80 * otherwise, the copy constructors of the constraints handlers are used */ 81 #define DEFAULT_COPYCUTS TRUE /* if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool 82 * of the original scip be copied to constraints of the subscip 83 */ 84 #define DEFAULT_BESTSOLLIMIT 3 /* limit on number of improving incumbent solutions in sub-CIP */ 85 86 /* event handler properties */ 87 #define EVENTHDLR_NAME "Localbranching" 88 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" 89 90 91 #define EXECUTE 0 92 #define WAITFORNEWSOL 1 93 94 95 /* 96 * Data structures 97 */ 98 99 /** primal heuristic data */ 100 struct SCIP_HeurData 101 { 102 int nwaitingnodes; /**< number of nodes without incumbent change that heuristic should wait */ 103 int nodesofs; /**< number of nodes added to the contingent of the total nodes */ 104 int minnodes; /**< minimum number of nodes required to start the subproblem */ 105 int maxnodes; /**< maximum number of nodes to regard in the subproblem */ 106 SCIP_Longint usednodes; /**< amount of nodes local branching used during all calls */ 107 SCIP_Real nodesquot; /**< contingent of sub problem nodes in relation to original nodes */ 108 SCIP_Real minimprove; /**< factor by which localbranching should at least improve the incumbent */ 109 SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/ 110 SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */ 111 int neighborhoodsize; /**< radius of the incumbent's neighborhood to be searched */ 112 int callstatus; /**< current status of localbranching heuristic */ 113 SCIP_SOL* lastsol; /**< the last incumbent localbranching used as reference point */ 114 int curneighborhoodsize;/**< current neighborhoodsize */ 115 int curminnodes; /**< current minimal number of nodes required to start the subproblem */ 116 int emptyneighborhoodsize;/**< size of neighborhood that was proven to be empty */ 117 SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */ 118 SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied 119 * to constraints in subproblem? 120 */ 121 int bestsollimit; /**< limit on number of improving incumbent solutions in sub-CIP */ 122 }; 123 124 125 /* 126 * Local methods 127 */ 128 129 /** create the extra constraint of local branching and add it to subscip */ 130 static 131 SCIP_RETCODE addLocalbranchingConstraintAndObjcutoff( 132 SCIP* scip, /**< SCIP data structure */ 133 SCIP* subscip, /**< the subproblem created by localbranching */ 134 SCIP_HEUR* heur, /**< the local branching heuristic */ 135 SCIP_VAR** subvars /**< the subproblem variables */ 136 ) 137 { 138 SCIP_HEURDATA* heurdata; 139 SCIP_CONS* cons; /* local branching constraint to create */ 140 SCIP_VAR** consvars; 141 SCIP_VAR** vars; 142 SCIP_SOL* bestsol; 143 144 int nbinvars; 145 int nconsvars; 146 int i; 147 SCIP_Real lhs; 148 SCIP_Real rhs; 149 SCIP_Real* consvals; 150 char consname[SCIP_MAXSTRLEN]; 151 152 SCIP_Real cutoff; 153 SCIP_Real upperbound; 154 155 assert(scip != NULL); 156 assert(subscip != NULL); 157 assert(heur != NULL); 158 159 heurdata = SCIPheurGetData(heur); 160 assert(heurdata != NULL); 161 162 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_localbranchcons", SCIPgetProbName(scip)); 163 164 /* get the data of the variables and the best solution */ 165 SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, NULL, NULL, NULL) ); 166 bestsol = SCIPgetBestSol(scip); 167 assert( bestsol != NULL ); 168 169 /* memory allocation */ 170 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nbinvars) ); 171 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nbinvars) ); 172 nconsvars = 0; 173 174 /* set initial left and right hand sides of local branching constraint */ 175 lhs = (SCIP_Real)heurdata->emptyneighborhoodsize + 1.0; 176 rhs = (SCIP_Real)heurdata->curneighborhoodsize; 177 178 /* create the distance (to incumbent) function of the binary variables */ 179 for( i = 0; i < nbinvars; i++ ) 180 { 181 SCIP_Real solval; 182 183 if( subvars[i] == NULL ) 184 continue; 185 186 solval = SCIPgetSolVal(scip, bestsol, vars[i]); 187 assert( SCIPisFeasIntegral(scip, solval) ); 188 189 /* is variable i part of the binary support of bestsol? */ 190 if( SCIPisFeasEQ(scip, solval, 1.0) ) 191 { 192 consvals[nconsvars] = -1.0; 193 rhs -= 1.0; 194 lhs -= 1.0; 195 } 196 else 197 consvals[nconsvars] = 1.0; 198 199 consvars[nconsvars] = subvars[i]; 200 assert( SCIPvarGetType(consvars[nconsvars]) == SCIP_VARTYPE_BINARY ); 201 202 ++nconsvars; 203 } 204 205 /* creates localbranching constraint and adds it to subscip */ 206 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, consname, nconsvars, consvars, consvals, 207 lhs, rhs, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) ); 208 SCIP_CALL( SCIPaddCons(subscip, cons) ); 209 SCIP_CALL( SCIPreleaseCons(subscip, &cons) ); 210 211 /* add an objective cutoff */ 212 assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) ); 213 214 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip); 215 if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) ) 216 { 217 cutoff = (1-heurdata->minimprove)*SCIPgetUpperbound(scip) + heurdata->minimprove*SCIPgetLowerbound(scip); 218 } 219 else 220 { 221 if( SCIPgetUpperbound ( scip ) >= 0 ) 222 cutoff = ( 1 - heurdata->minimprove ) * SCIPgetUpperbound ( scip ); 223 else 224 cutoff = ( 1 + heurdata->minimprove ) * SCIPgetUpperbound ( scip ); 225 } 226 cutoff = MIN(upperbound, cutoff ); 227 SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) ); 228 229 /* free local memory */ 230 SCIPfreeBufferArray(scip, &consvals); 231 SCIPfreeBufferArray(scip, &consvars); 232 233 return SCIP_OKAY; 234 } 235 236 237 /* ---------------- Callback methods of event handler ---------------- */ 238 239 /** event handler execution callback to interrupt the solution process */ 240 static 241 SCIP_DECL_EVENTEXEC(eventExecLocalbranching) 242 { 243 SCIP_HEURDATA* heurdata; 244 245 assert(eventhdlr != NULL); 246 assert(eventdata != NULL); 247 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 248 assert(event != NULL); 249 assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED); 250 251 heurdata = (SCIP_HEURDATA*)eventdata; 252 assert(heurdata != NULL); 253 254 /* interrupt solution process of sub-SCIP */ 255 if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit ) 256 { 257 SCIPdebugMsg(scip, "interrupt after %" SCIP_LONGINT_FORMAT " LPs\n",SCIPgetNLPs(scip)); 258 SCIP_CALL( SCIPinterruptSolve(scip) ); 259 } 260 261 return SCIP_OKAY; 262 } 263 264 265 /* 266 * Callback methods of primal heuristic 267 */ 268 269 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 270 static 271 SCIP_DECL_HEURCOPY(heurCopyLocalbranching) 272 { /*lint --e{715}*/ 273 assert(scip != NULL); 274 assert(heur != NULL); 275 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 276 277 /* call inclusion method of primal heuristic */ 278 SCIP_CALL( SCIPincludeHeurLocalbranching(scip) ); 279 280 return SCIP_OKAY; 281 } 282 283 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 284 static 285 SCIP_DECL_HEURFREE(heurFreeLocalbranching) 286 { /*lint --e{715}*/ 287 SCIP_HEURDATA* heurdata; 288 289 assert( heur != NULL ); 290 assert( scip != NULL ); 291 292 /* get heuristic data */ 293 heurdata = SCIPheurGetData(heur); 294 assert( heurdata != NULL ); 295 296 /* free heuristic data */ 297 SCIPfreeBlockMemory(scip, &heurdata); 298 SCIPheurSetData(heur, NULL); 299 300 return SCIP_OKAY; 301 } 302 303 304 /** initialization method of primal heuristic (called after problem was transformed) */ 305 static 306 SCIP_DECL_HEURINIT(heurInitLocalbranching) 307 { /*lint --e{715}*/ 308 SCIP_HEURDATA* heurdata; 309 310 assert( heur != NULL ); 311 assert( scip != NULL ); 312 313 /* get heuristic's data */ 314 heurdata = SCIPheurGetData(heur); 315 assert( heurdata != NULL ); 316 317 /* with a little abuse we initialize the heurdata as if localbranching would have finished its last step regularly */ 318 heurdata->callstatus = WAITFORNEWSOL; 319 heurdata->lastsol = NULL; 320 heurdata->usednodes = 0; 321 heurdata->curneighborhoodsize = heurdata->neighborhoodsize; 322 heurdata->curminnodes = heurdata->minnodes; 323 heurdata->emptyneighborhoodsize = 0; 324 325 return SCIP_OKAY; 326 } 327 328 /** setup And solve local branching subscip */ 329 static 330 SCIP_RETCODE setupAndSolveSubscipLocalbranching( 331 SCIP* scip, /**< SCIP data structure */ 332 SCIP* subscip, /**< the subproblem created by localbranching */ 333 SCIP_HEUR* heur, /**< localbranching heuristic */ 334 SCIP_Longint nsubnodes, /**< nodelimit for subscip */ 335 SCIP_RESULT* result /**< result pointer */ 336 ) 337 { 338 SCIP_VAR** subvars; /* subproblem's variables */ 339 SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */ 340 SCIP_HEURDATA* heurdata; 341 SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */ 342 SCIP_VAR** vars; 343 344 int nvars; 345 int i; 346 347 SCIP_Bool success; 348 349 assert(scip != NULL); 350 assert(subscip != NULL); 351 assert(heur != NULL); 352 353 heurdata = SCIPheurGetData(heur); 354 assert(heurdata != NULL); 355 356 /* get the data of the variables and the best solution */ 357 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 358 359 /* create the variable mapping hash map */ 360 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) ); 361 success = FALSE; 362 363 /* create a problem copy as sub SCIP */ 364 SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "localbranching", NULL, NULL, 0, heurdata->uselprows, 365 heurdata->copycuts, &success, NULL) ); 366 367 SCIPdebugMsg(scip, "Copying SCIP was %ssuccessful.\n", success ? "" : "not "); 368 369 /* if the subproblem could not be created, free memory and return */ 370 if( !success ) 371 { 372 *result = SCIP_DIDNOTRUN; 373 goto TERMINATE; 374 } 375 376 /* create event handler for LP events */ 377 eventhdlr = NULL; 378 SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecLocalbranching, NULL) ); 379 if( eventhdlr == NULL ) 380 { 381 /* free hash map */ 382 SCIPhashmapFree(&varmapfw); 383 384 SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n"); 385 return SCIP_PLUGINNOTFOUND; 386 } 387 388 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) ); 389 for (i = 0; i < nvars; ++i) 390 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]); 391 392 /* free hash map */ 393 SCIPhashmapFree(&varmapfw); 394 395 heurdata->nodelimit = nsubnodes; 396 SCIP_CALL( SCIPsetCommonSubscipParams(scip, subscip, nsubnodes, MAX(10, nsubnodes/10), heurdata->bestsollimit) ); 397 398 /* adds the local branching constraint and the objective cutoff to the auxiliary problem */ 399 SCIP_CALL( addLocalbranchingConstraintAndObjcutoff(scip, subscip, heur, subvars) ); 400 401 /* catch LP events of sub-SCIP */ 402 if( !heurdata->uselprows ) 403 { 404 assert(eventhdlr != NULL); 405 406 SCIP_CALL( SCIPtransformProb(subscip) ); 407 SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) ); 408 } 409 410 /* solve the subproblem */ 411 SCIPdebugMsg(scip, "solving local branching subproblem with neighborhoodsize %d and maxnodes %" SCIP_LONGINT_FORMAT "\n", 412 heurdata->curneighborhoodsize, nsubnodes); 413 414 /* Errors in solving the subproblem should not kill the overall solving process 415 * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 416 */ 417 SCIP_CALL_ABORT( SCIPsolve(subscip) ); 418 419 /* drop LP events of sub-SCIP */ 420 if( !heurdata->uselprows ) 421 { 422 assert(eventhdlr != NULL); 423 424 SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) ); 425 } 426 427 /* print solving statistics of subproblem if we are in SCIP's debug mode */ 428 SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) ); 429 430 heurdata->usednodes += SCIPgetNNodes(subscip); 431 SCIPdebugMsg(scip, "local branching used %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT " nodes\n", 432 SCIPgetNNodes(subscip), nsubnodes); 433 434 /* checks the solutions of the sub SCIP and adds them to the main SCIP if feasible */ 435 SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, NULL) ); 436 437 if( success ) 438 *result = SCIP_FOUNDSOL; 439 440 /* check the status of the sub-MIP */ 441 switch( SCIPgetStatus(subscip) ) 442 { 443 case SCIP_STATUS_OPTIMAL: 444 case SCIP_STATUS_BESTSOLLIMIT: 445 heurdata->callstatus = WAITFORNEWSOL; /* new solution will immediately be installed at next call */ 446 SCIPdebugMsg(scip, " -> found new solution\n"); 447 break; 448 449 case SCIP_STATUS_NODELIMIT: 450 case SCIP_STATUS_STALLNODELIMIT: 451 case SCIP_STATUS_TOTALNODELIMIT: 452 heurdata->callstatus = EXECUTE; 453 heurdata->curneighborhoodsize = (heurdata->emptyneighborhoodsize + heurdata->curneighborhoodsize)/2; 454 heurdata->curminnodes *= 2; 455 SCIPdebugMsg(scip, " -> node limit reached: reduced neighborhood to %d, increased minnodes to %d\n", 456 heurdata->curneighborhoodsize, heurdata->curminnodes); 457 if( heurdata->curneighborhoodsize <= heurdata->emptyneighborhoodsize ) 458 { 459 heurdata->callstatus = WAITFORNEWSOL; 460 SCIPdebugMsg(scip, " -> new neighborhood was already proven to be empty: wait for new solution\n"); 461 } 462 break; 463 464 case SCIP_STATUS_INFEASIBLE: 465 case SCIP_STATUS_INFORUNBD: 466 heurdata->emptyneighborhoodsize = heurdata->curneighborhoodsize; 467 heurdata->curneighborhoodsize += heurdata->curneighborhoodsize/2; 468 heurdata->curneighborhoodsize = MAX(heurdata->curneighborhoodsize, heurdata->emptyneighborhoodsize + 2); 469 heurdata->callstatus = EXECUTE; 470 SCIPdebugMsg(scip, " -> neighborhood is empty: increased neighborhood to %d\n", heurdata->curneighborhoodsize); 471 break; 472 473 case SCIP_STATUS_UNKNOWN: 474 case SCIP_STATUS_USERINTERRUPT: 475 case SCIP_STATUS_TERMINATE: 476 case SCIP_STATUS_TIMELIMIT: 477 case SCIP_STATUS_MEMLIMIT: 478 case SCIP_STATUS_GAPLIMIT: 479 case SCIP_STATUS_SOLLIMIT: 480 case SCIP_STATUS_RESTARTLIMIT: 481 case SCIP_STATUS_UNBOUNDED: 482 default: 483 heurdata->callstatus = WAITFORNEWSOL; 484 SCIPdebugMsg(scip, " -> unexpected sub-MIP status <%d>: waiting for new solution\n", SCIPgetStatus(subscip)); 485 break; 486 } 487 488 TERMINATE: 489 /* free subproblem */ 490 SCIPfreeBufferArray(scip, &subvars); 491 492 return SCIP_OKAY; 493 } 494 495 496 /** execution method of primal heuristic */ 497 static 498 SCIP_DECL_HEUREXEC(heurExecLocalbranching) 499 { /*lint --e{715}*/ 500 SCIP_Longint maxnnodes; /* maximum number of subnodes */ 501 SCIP_Longint nsubnodes; /* nodelimit for subscip */ 502 503 SCIP_HEURDATA* heurdata; 504 SCIP* subscip; /* the subproblem created by localbranching */ 505 506 SCIP_SOL* bestsol; /* best solution so far */ 507 508 SCIP_Bool success; 509 SCIP_RETCODE retcode; 510 511 assert(heur != NULL); 512 assert(scip != NULL); 513 assert(result != NULL); 514 515 *result = SCIP_DIDNOTRUN; 516 517 /* get heuristic's data */ 518 heurdata = SCIPheurGetData(heur); 519 assert( heurdata != NULL ); 520 521 /* there should be enough binary variables that a local branching constraint makes sense */ 522 if( SCIPgetNBinVars(scip) < 2*heurdata->neighborhoodsize ) 523 return SCIP_OKAY; 524 525 *result = SCIP_DELAYED; 526 527 /* only call heuristic, if an IP solution is at hand */ 528 if( SCIPgetNSols(scip) <= 0 ) 529 return SCIP_OKAY; 530 531 bestsol = SCIPgetBestSol(scip); 532 assert(bestsol != NULL); 533 534 /* only call heuristic, if the best solution comes from transformed problem */ 535 if( SCIPsolIsOriginal(bestsol) ) 536 return SCIP_OKAY; 537 538 /* only call heuristic, if enough nodes were processed since last incumbent */ 539 if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip, bestsol) < heurdata->nwaitingnodes) 540 return SCIP_OKAY; 541 542 /* only call heuristic, if the best solution does not come from trivial heuristic */ 543 if( SCIPsolGetHeur(bestsol) != NULL && strcmp(SCIPheurGetName(SCIPsolGetHeur(bestsol)), "trivial") == 0 ) 544 return SCIP_OKAY; 545 546 /* reset neighborhood and minnodes, if new solution was found */ 547 if( heurdata->lastsol != bestsol ) 548 { 549 heurdata->curneighborhoodsize = heurdata->neighborhoodsize; 550 heurdata->curminnodes = heurdata->minnodes; 551 heurdata->emptyneighborhoodsize = 0; 552 heurdata->callstatus = EXECUTE; 553 heurdata->lastsol = bestsol; 554 } 555 556 /* if no new solution was found and local branching also seems to fail, just keep on waiting */ 557 if( heurdata->callstatus == WAITFORNEWSOL ) 558 return SCIP_OKAY; 559 560 *result = SCIP_DIDNOTRUN; 561 562 /* calculate the maximal number of branching nodes until heuristic is aborted */ 563 maxnnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip)); 564 565 /* reward local branching if it succeeded often */ 566 maxnnodes = (SCIP_Longint)(maxnnodes * (1.0 + 2.0*(SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur)+1.0))); 567 maxnnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-MIP as 100 nodes */ 568 maxnnodes += heurdata->nodesofs; 569 570 /* determine the node limit for the current process */ 571 nsubnodes = maxnnodes - heurdata->usednodes; 572 nsubnodes = MIN(nsubnodes, heurdata->maxnodes); 573 574 /* check whether we have enough nodes left to call sub problem solving */ 575 if( nsubnodes < heurdata->curminnodes ) 576 return SCIP_OKAY; 577 578 if( SCIPisStopped(scip) ) 579 return SCIP_OKAY; 580 581 /* check whether there is enough time and memory left */ 582 SCIP_CALL( SCIPcheckCopyLimits(scip, &success) ); 583 584 /* abort if no time is left or not enough memory to create a copy of SCIP */ 585 if( !success ) 586 return SCIP_OKAY; 587 588 *result = SCIP_DIDNOTFIND; 589 590 SCIPdebugMsg(scip, "running localbranching heuristic ...\n"); 591 592 SCIP_CALL( SCIPcreate(&subscip) ); 593 594 retcode = setupAndSolveSubscipLocalbranching(scip, subscip, heur, nsubnodes, result); 595 596 SCIP_CALL( SCIPfree(&subscip) ); 597 598 return retcode; 599 } 600 601 602 /* 603 * primal heuristic specific interface methods 604 */ 605 606 /** creates the localbranching primal heuristic and includes it in SCIP */ 607 SCIP_RETCODE SCIPincludeHeurLocalbranching( 608 SCIP* scip /**< SCIP data structure */ 609 ) 610 { 611 SCIP_HEURDATA* heurdata; 612 SCIP_HEUR* heur; 613 614 /* create Localbranching primal heuristic data */ 615 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 616 617 /* include primal heuristic */ 618 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 619 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 620 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecLocalbranching, heurdata) ); 621 622 assert(heur != NULL); 623 624 /* set non-NULL pointers to callback methods */ 625 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyLocalbranching) ); 626 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeLocalbranching) ); 627 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitLocalbranching) ); 628 629 /* add localbranching primal heuristic parameters */ 630 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nodesofs", 631 "number of nodes added to the contingent of the total nodes", 632 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0, INT_MAX, NULL, NULL) ); 633 634 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/neighborhoodsize", 635 "radius (using Manhattan metric) of the incumbent's neighborhood to be searched", 636 &heurdata->neighborhoodsize, FALSE, DEFAULT_NEIGHBORHOODSIZE, 1, INT_MAX, NULL, NULL) ); 637 638 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot", 639 "contingent of sub problem nodes in relation to the number of nodes of the original problem", 640 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) ); 641 642 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac", 643 "factor by which the limit on the number of LP depends on the node limit", 644 &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) ); 645 646 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minnodes", 647 "minimum number of nodes required to start the subproblem", 648 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) ); 649 650 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxnodes", 651 "maximum number of nodes to regard in the subproblem", 652 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) ); 653 654 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes", 655 "number of nodes without incumbent change that heuristic should wait", 656 &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0, INT_MAX, NULL, NULL) ); 657 658 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove", 659 "factor by which localbranching should at least improve the incumbent", 660 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) ); 661 662 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows", 663 "should subproblem be created out of the rows in the LP rows?", 664 &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) ); 665 666 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts", 667 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?", 668 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) ); 669 670 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/bestsollimit", 671 "limit on number of improving incumbent solutions in sub-CIP", 672 &heurdata->bestsollimit, FALSE, DEFAULT_BESTSOLLIMIT, -1, INT_MAX, NULL, NULL) ); 673 674 return SCIP_OKAY; 675 } 676