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_zeroobj.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief heuristic that tries to solve the problem without objective. In Gurobi, this heuristic is known as "Hail Mary" 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/cons_linear.h" 35 #include "scip/heur_zeroobj.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_var.h" 41 #include "scip/scip_branch.h" 42 #include "scip/scip_cons.h" 43 #include "scip/scip_copy.h" 44 #include "scip/scip_event.h" 45 #include "scip/scip_general.h" 46 #include "scip/scip_heur.h" 47 #include "scip/scip_lp.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_sol.h" 55 #include "scip/scip_solve.h" 56 #include "scip/scip_solvingstats.h" 57 #include "scip/scip_tree.h" 58 #include "scip/scip_var.h" 59 #include <string.h> 60 61 #define HEUR_NAME "zeroobj" 62 #define HEUR_DESC "heuristic trying to solve the problem without objective" 63 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS 64 #define HEUR_PRIORITY 100 65 #define HEUR_FREQ -1 66 #define HEUR_FREQOFS 0 67 #define HEUR_MAXDEPTH 0 68 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_BEFOREPRESOL 69 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */ 70 71 /* event handler properties */ 72 #define EVENTHDLR_NAME "Zeroobj" 73 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" 74 75 /* default values for zeroobj-specific plugins */ 76 #define DEFAULT_MAXNODES 1000LL /* maximum number of nodes to regard in the subproblem */ 77 #define DEFAULT_MINIMPROVE 0.01 /* factor by which zeroobj should at least improve the incumbent */ 78 #define DEFAULT_MINNODES 100LL /* minimum number of nodes to regard in the subproblem */ 79 #define DEFAULT_MAXLPITERS 5000LL /* maximum number of LP iterations to be performed in the subproblem */ 80 #define DEFAULT_NODESOFS 100LL /* number of nodes added to the contingent of the total nodes */ 81 #define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */ 82 #define DEFAULT_ADDALLSOLS FALSE /* should all subproblem solutions be added to the original SCIP? */ 83 #define DEFAULT_ONLYWITHOUTSOL TRUE /**< should heuristic only be executed if no primal solution was found, yet? */ 84 #define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */ 85 86 /* 87 * Data structures 88 */ 89 90 /** primal heuristic data */ 91 struct SCIP_HeurData 92 { 93 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */ 94 SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */ 95 SCIP_Longint maxlpiters; /**< maximum number of LP iterations to be performed in the subproblem */ 96 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */ 97 SCIP_Longint usednodes; /**< nodes already used by zeroobj in earlier calls */ 98 SCIP_Real minimprove; /**< factor by which zeroobj should at least improve the incumbent */ 99 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */ 100 SCIP_Bool addallsols; /**< should all subproblem solutions be added to the original SCIP? */ 101 SCIP_Bool onlywithoutsol; /**< should heuristic only be executed if no primal solution was found, yet? */ 102 SCIP_Bool useuct; /**< should uct node selection be used at the beginning of the search? */ 103 }; 104 105 106 /* 107 * Local methods 108 */ 109 110 /* ---------------- Callback methods of event handler ---------------- */ 111 112 /* exec the event handler 113 * 114 * we interrupt the solution process 115 */ 116 static 117 SCIP_DECL_EVENTEXEC(eventExecZeroobj) 118 { 119 SCIP_HEURDATA* heurdata; 120 121 assert(eventhdlr != NULL); 122 assert(eventdata != NULL); 123 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 124 assert(event != NULL); 125 assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_NODESOLVED); 126 127 heurdata = (SCIP_HEURDATA*)eventdata; 128 assert(heurdata != NULL); 129 130 /* interrupt solution process of sub-SCIP */ 131 if( SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_ITERLIMIT || SCIPgetNLPIterations(scip) >= heurdata->maxlpiters ) 132 { 133 SCIP_CALL( SCIPinterruptSolve(scip) ); 134 } 135 136 return SCIP_OKAY; 137 } 138 /* ---------------- Callback methods of primal heuristic ---------------- */ 139 140 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 141 static 142 SCIP_DECL_HEURCOPY(heurCopyZeroobj) 143 { /*lint --e{715}*/ 144 assert(scip != NULL); 145 assert(heur != NULL); 146 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 147 148 /* call inclusion method of primal heuristic */ 149 SCIP_CALL( SCIPincludeHeurZeroobj(scip) ); 150 151 return SCIP_OKAY; 152 } 153 154 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 155 static 156 SCIP_DECL_HEURFREE(heurFreeZeroobj) 157 { /*lint --e{715}*/ 158 SCIP_HEURDATA* heurdata; 159 160 assert( heur != NULL ); 161 assert( scip != NULL ); 162 163 /* get heuristic data */ 164 heurdata = SCIPheurGetData(heur); 165 assert( heurdata != NULL ); 166 167 /* free heuristic data */ 168 SCIPfreeBlockMemory(scip, &heurdata); 169 SCIPheurSetData(heur, NULL); 170 171 return SCIP_OKAY; 172 } 173 174 175 /** initialization method of primal heuristic (called after problem was transformed) */ 176 static 177 SCIP_DECL_HEURINIT(heurInitZeroobj) 178 { /*lint --e{715}*/ 179 SCIP_HEURDATA* heurdata; 180 181 assert( heur != NULL ); 182 assert( scip != NULL ); 183 184 /* get heuristic data */ 185 heurdata = SCIPheurGetData(heur); 186 assert( heurdata != NULL ); 187 188 /* initialize data */ 189 heurdata->usednodes = 0; 190 191 return SCIP_OKAY; 192 } 193 194 195 /** execution method of primal heuristic */ 196 static 197 SCIP_DECL_HEUREXEC(heurExecZeroobj) 198 { /*lint --e{715}*/ 199 SCIP_HEURDATA* heurdata; /* heuristic's data */ 200 SCIP_Longint nnodes; /* number of stalling nodes for the subproblem */ 201 202 assert( heur != NULL ); 203 assert( scip != NULL ); 204 assert( result != NULL ); 205 206 /* get heuristic data */ 207 heurdata = SCIPheurGetData(heur); 208 assert( heurdata != NULL ); 209 210 /* calculate the maximal number of branching nodes until heuristic is aborted */ 211 nnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip)); 212 213 /* reward zeroobj if it succeeded often */ 214 nnodes = (SCIP_Longint)(nnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0)); 215 nnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-SCIP as 100 nodes */ 216 nnodes += heurdata->nodesofs; 217 218 /* determine the node limit for the current process */ 219 nnodes -= heurdata->usednodes; 220 nnodes = MIN(nnodes, heurdata->maxnodes); 221 222 /* check whether we have enough nodes left to call subproblem solving */ 223 if( nnodes < heurdata->minnodes ) 224 { 225 SCIPdebugMsg(scip, "skipping zeroobj: nnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nnodes, heurdata->minnodes); 226 return SCIP_OKAY; 227 } 228 229 /* do not run zeroobj, if the problem does not have an objective function anyway */ 230 if( SCIPgetNObjVars(scip) == 0 ) 231 { 232 SCIPdebugMsg(scip, "skipping zeroobj: pure feasibility problem anyway\n"); 233 return SCIP_OKAY; 234 } 235 236 if( SCIPisStopped(scip) ) 237 return SCIP_OKAY; 238 239 SCIP_CALL( SCIPapplyZeroobj(scip, heur, result, heurdata->minimprove, nnodes) ); 240 241 return SCIP_OKAY; 242 } 243 244 /** setup and solve subscip */ 245 static 246 SCIP_RETCODE setupAndSolveSubscip( 247 SCIP* scip, /**< SCIP data structure */ 248 SCIP* subscip, /**< SCIP data structure */ 249 SCIP_HEUR* heur, /**< heuristic data structure */ 250 SCIP_RESULT* result, /**< result data structure */ 251 SCIP_Real minimprove, /**< factor by which zeroobj should at least improve the incumbent */ 252 SCIP_Longint nnodes /**< node limit for the subproblem */ 253 ) 254 { 255 SCIP_Real cutoff; /* objective cutoff for the subproblem */ 256 SCIP_Real large; 257 SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */ 258 SCIP_VAR** vars; /* original problem's variables */ 259 SCIP_VAR** subvars; /* subproblem's variables */ 260 SCIP_SOL** subsols; 261 SCIP_HEURDATA* heurdata; /* heuristic's private data structure */ 262 SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */ 263 264 int nsubsols; 265 int nvars; /* number of original problem's variables */ 266 int i; 267 SCIP_Bool success; 268 SCIP_Bool valid; 269 270 assert(scip != NULL); 271 assert(subscip != NULL); 272 assert(heur != NULL); 273 assert(result != NULL); 274 275 heurdata = SCIPheurGetData(heur); 276 assert(heurdata != NULL); 277 278 /* get variable data */ 279 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 280 281 /* create the variable mapping hash map */ 282 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) ); 283 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) ); 284 285 /* different methods to create sub-problem: either copy LP relaxation or the CIP with all constraints */ 286 valid = FALSE; 287 288 /* copy complete SCIP instance */ 289 SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL, "zeroobj", TRUE, FALSE, FALSE, TRUE, &valid) ); 290 SCIPdebugMsg(scip, "Copying the SCIP instance was %s complete.\n", valid ? "" : "not "); 291 292 /* create event handler for LP events */ 293 eventhdlr = NULL; 294 SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecZeroobj, NULL) ); 295 if( eventhdlr == NULL ) 296 { 297 SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n"); 298 return SCIP_PLUGINNOTFOUND; 299 } 300 301 /* determine large value to set variables to */ 302 large = SCIPinfinity(scip); 303 if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) ) 304 large = 0.1 / SCIPfeastol(scip); 305 306 /* get variable image and change to 0.0 in sub-SCIP */ 307 for( i = 0; i < nvars; i++ ) 308 { 309 SCIP_Real adjustedbound; 310 SCIP_Real lb; 311 SCIP_Real ub; 312 SCIP_Real inf; 313 314 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]); 315 if( subvars[i] == NULL ) 316 continue; 317 318 SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], 0.0) ); 319 320 lb = SCIPvarGetLbGlobal(subvars[i]); 321 ub = SCIPvarGetUbGlobal(subvars[i]); 322 inf = SCIPinfinity(subscip); 323 324 /* adjust infinite bounds in order to avoid that variables with non-zero objective 325 * get fixed to infinite value in zeroobj subproblem 326 */ 327 if( SCIPisInfinity(subscip, ub ) ) 328 { 329 adjustedbound = MAX(large, lb+large); 330 adjustedbound = MIN(adjustedbound, inf); 331 SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], adjustedbound) ); 332 } 333 if( SCIPisInfinity(subscip, -lb ) ) 334 { 335 adjustedbound = MIN(-large, ub-large); 336 adjustedbound = MAX(adjustedbound, -inf); 337 SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], adjustedbound) ); 338 } 339 } 340 341 /* free hash map */ 342 SCIPhashmapFree(&varmapfw); 343 344 /* do not abort subproblem on CTRL-C */ 345 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) ); 346 347 #ifdef SCIP_DEBUG 348 /* for debugging, enable full output */ 349 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) ); 350 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) ); 351 #else 352 /* disable statistic timing inside sub SCIP and output to console */ 353 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) ); 354 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) ); 355 #endif 356 357 /* set limits for the subproblem */ 358 SCIP_CALL( SCIPcopyLimits(scip, subscip) ); 359 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nnodes) ); 360 SCIP_CALL( SCIPsetIntParam(subscip, "limits/solutions", 1) ); 361 362 /* forbid recursive call of heuristics and separators solving sub-SCIPs */ 363 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) ); 364 365 /* disable expensive techniques that merely work on the dual bound */ 366 367 /* disable cutting plane separation */ 368 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) ); 369 370 /* disable expensive presolving */ 371 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) ); 372 if( !SCIPisParamFixed(subscip, "presolving/maxrounds") ) 373 { 374 SCIP_CALL( SCIPsetIntParam(subscip, "presolving/maxrounds", 50) ); 375 } 376 377 /* use restart dfs node selection */ 378 if( SCIPfindNodesel(subscip, "restartdfs") != NULL && !SCIPisParamFixed(subscip, "nodeselection/restartdfs/stdpriority") ) 379 { 380 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/restartdfs/stdpriority", INT_MAX/4) ); 381 } 382 383 /* activate uct node selection at the top of the tree */ 384 if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") ) 385 { 386 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) ); 387 } 388 /* use least infeasible branching */ 389 if( SCIPfindBranchrule(subscip, "leastinf") != NULL && !SCIPisParamFixed(subscip, "branching/leastinf/priority") ) 390 { 391 SCIP_CALL( SCIPsetIntParam(subscip, "branching/leastinf/priority", INT_MAX/4) ); 392 } 393 394 /* disable feaspump and fracdiving */ 395 if( !SCIPisParamFixed(subscip, "heuristics/feaspump/freq") ) 396 { 397 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/feaspump/freq", -1) ); 398 } 399 if( !SCIPisParamFixed(subscip, "heuristics/fracdiving/freq") ) 400 { 401 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/fracdiving/freq", -1) ); 402 } 403 404 /* speed up sub-SCIP by not checking dual LP feasibility */ 405 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) ); 406 407 /* restrict LP iterations */ 408 SCIP_CALL( SCIPsetLongintParam(subscip, "lp/iterlim", 2*heurdata->maxlpiters / MAX(1,nnodes)) ); 409 SCIP_CALL( SCIPsetLongintParam(subscip, "lp/rootiterlim", heurdata->maxlpiters) ); 410 411 /* if there is already a solution, add an objective cutoff */ 412 if( SCIPgetNSols(scip) > 0 ) 413 { 414 SCIP_Real upperbound; 415 SCIP_CONS* origobjcons; 416 #ifndef NDEBUG 417 int nobjvars; 418 nobjvars = 0; 419 #endif 420 421 assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) ); 422 423 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip); 424 425 if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) ) 426 { 427 cutoff = (1-minimprove)*SCIPgetUpperbound(scip) + minimprove*SCIPgetLowerbound(scip); 428 } 429 else 430 { 431 if( SCIPgetUpperbound(scip) >= 0 ) 432 cutoff = ( 1 - minimprove ) * SCIPgetUpperbound ( scip ); 433 else 434 cutoff = ( 1 + minimprove ) * SCIPgetUpperbound ( scip ); 435 } 436 cutoff = MIN(upperbound, cutoff); 437 438 SCIP_CALL( SCIPcreateConsLinear(subscip, &origobjcons, "objbound_of_origscip", 0, NULL, NULL, -SCIPinfinity(subscip), cutoff, 439 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 440 for( i = 0; i < nvars; ++i) 441 { 442 if( !SCIPisFeasZero(subscip, SCIPvarGetObj(vars[i])) ) 443 { 444 assert(subvars[i] != NULL); /* subvars[i] can be NULL for relax-only vars, but they cannot appear in the objective */ 445 SCIP_CALL( SCIPaddCoefLinear(subscip, origobjcons, subvars[i], SCIPvarGetObj(vars[i])) ); 446 #ifndef NDEBUG 447 nobjvars++; 448 #endif 449 } 450 } 451 SCIP_CALL( SCIPaddCons(subscip, origobjcons) ); 452 SCIP_CALL( SCIPreleaseCons(subscip, &origobjcons) ); 453 assert(nobjvars == SCIPgetNObjVars(scip)); 454 } 455 456 /* catch LP events of sub-SCIP */ 457 SCIP_CALL( SCIPtransformProb(subscip) ); 458 SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) ); 459 460 SCIPdebugMsg(scip, "solving subproblem: nnodes=%" SCIP_LONGINT_FORMAT "\n", nnodes); 461 462 /* errors in solving the subproblem should not kill the overall solving process; 463 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 464 */ 465 SCIP_CALL_ABORT( SCIPsolve(subscip) ); 466 467 /* drop LP events of sub-SCIP */ 468 SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) ); 469 470 /* check, whether a solution was found; 471 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted 472 */ 473 nsubsols = SCIPgetNSols(subscip); 474 subsols = SCIPgetSols(subscip); 475 success = FALSE; 476 for( i = 0; i < nsubsols && (!success || heurdata->addallsols); ++i ) 477 { 478 SCIP_SOL* newsol; 479 480 SCIP_CALL( SCIPtranslateSubSol(scip, subscip, subsols[i], heur, subvars, &newsol) ); 481 482 SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) ); 483 if( success ) 484 *result = SCIP_FOUNDSOL; 485 } 486 487 #ifdef SCIP_DEBUG 488 SCIP_CALL( SCIPprintStatistics(subscip, NULL) ); 489 #endif 490 491 /* free subproblem */ 492 SCIPfreeBufferArray(scip, &subvars); 493 494 return SCIP_OKAY; 495 } 496 497 498 /* 499 * primal heuristic specific interface methods 500 */ 501 502 503 /** main procedure of the zeroobj heuristic, creates and solves a sub-SCIP */ 504 SCIP_RETCODE SCIPapplyZeroobj( 505 SCIP* scip, /**< original SCIP data structure */ 506 SCIP_HEUR* heur, /**< heuristic data structure */ 507 SCIP_RESULT* result, /**< result data structure */ 508 SCIP_Real minimprove, /**< factor by which zeroobj should at least improve the incumbent */ 509 SCIP_Longint nnodes /**< node limit for the subproblem */ 510 ) 511 { 512 SCIP* subscip; /* the subproblem created by zeroobj */ 513 SCIP_HEURDATA* heurdata; /* heuristic's private data structure */ 514 SCIP_Bool success; 515 SCIP_RETCODE retcode; 516 517 assert(scip != NULL); 518 assert(heur != NULL); 519 assert(result != NULL); 520 521 assert(nnodes >= 0); 522 assert(0.0 <= minimprove && minimprove <= 1.0); 523 524 *result = SCIP_DIDNOTRUN; 525 526 /* only call heuristic once at the root */ 527 if( SCIPgetDepth(scip) <= 0 && SCIPheurGetNCalls(heur) > 0 ) 528 return SCIP_OKAY; 529 530 /* get heuristic data */ 531 heurdata = SCIPheurGetData(heur); 532 assert(heurdata != NULL); 533 534 /* only call the heuristic if we do not have an incumbent */ 535 if( SCIPgetNSolsFound(scip) > 0 && heurdata->onlywithoutsol ) 536 return SCIP_OKAY; 537 538 /* check whether there is enough time and memory left */ 539 SCIP_CALL( SCIPcheckCopyLimits(scip, &success) ); 540 541 if( !success ) 542 return SCIP_OKAY; 543 544 *result = SCIP_DIDNOTFIND; 545 546 /* initialize the subproblem */ 547 SCIP_CALL( SCIPcreate(&subscip) ); 548 549 retcode = setupAndSolveSubscip(scip, subscip, heur, result, minimprove, nnodes); 550 551 SCIP_CALL( SCIPfree(&subscip) ); 552 553 return retcode; 554 } 555 556 557 /** creates the zeroobj primal heuristic and includes it in SCIP */ 558 SCIP_RETCODE SCIPincludeHeurZeroobj( 559 SCIP* scip /**< SCIP data structure */ 560 ) 561 { 562 SCIP_HEURDATA* heurdata; 563 SCIP_HEUR* heur; 564 565 /* create heuristic data */ 566 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 567 568 /* include primal heuristic */ 569 heur = NULL; 570 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 571 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 572 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecZeroobj, heurdata) ); 573 assert(heur != NULL); 574 575 /* set non-NULL pointers to callback methods */ 576 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyZeroobj) ); 577 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeZeroobj) ); 578 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitZeroobj) ); 579 580 /* add zeroobj primal heuristic parameters */ 581 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes", 582 "maximum number of nodes to regard in the subproblem", 583 &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 584 585 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs", 586 "number of nodes added to the contingent of the total nodes", 587 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 588 589 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes", 590 "minimum number of nodes required to start the subproblem", 591 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 592 593 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxlpiters", 594 "maximum number of LP iterations to be performed in the subproblem", 595 &heurdata->maxlpiters, TRUE, DEFAULT_MAXLPITERS, -1LL, SCIP_LONGINT_MAX, NULL, NULL) ); 596 597 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot", 598 "contingent of sub problem nodes in relation to the number of nodes of the original problem", 599 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) ); 600 601 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove", 602 "factor by which zeroobj should at least improve the incumbent", 603 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) ); 604 605 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/addallsols", 606 "should all subproblem solutions be added to the original SCIP?", 607 &heurdata->addallsols, TRUE, DEFAULT_ADDALLSOLS, NULL, NULL) ); 608 609 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlywithoutsol", 610 "should heuristic only be executed if no primal solution was found, yet?", 611 &heurdata->onlywithoutsol, TRUE, DEFAULT_ONLYWITHOUTSOL, NULL, NULL) ); 612 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct", 613 "should uct node selection be used at the beginning of the search?", 614 &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) ); 615 616 return SCIP_OKAY; 617 } 618