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_proximity.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief improvement heuristic which uses an auxiliary objective instead of the original objective function which 28 * is itself added as a constraint to a sub-SCIP instance. The heuristic was presented by Matteo Fischetti 29 * and Michele Monaci. 30 * @author Gregor Hendel 31 */ 32 33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 34 35 #include "blockmemshell/memory.h" 36 #include "scip/cons_linear.h" 37 #include "scip/heuristics.h" 38 #include "scip/heur_proximity.h" 39 #include "scip/pub_event.h" 40 #include "scip/pub_heur.h" 41 #include "scip/pub_message.h" 42 #include "scip/pub_misc.h" 43 #include "scip/pub_sol.h" 44 #include "scip/pub_var.h" 45 #include "scip/scip_branch.h" 46 #include "scip/scip_cons.h" 47 #include "scip/scip_copy.h" 48 #include "scip/scip_event.h" 49 #include "scip/scip_general.h" 50 #include "scip/scip_heur.h" 51 #include "scip/scip_lp.h" 52 #include "scip/scip_mem.h" 53 #include "scip/scip_message.h" 54 #include "scip/scip_nlp.h" 55 #include "scip/scip_nodesel.h" 56 #include "scip/scip_numerics.h" 57 #include "scip/scip_param.h" 58 #include "scip/scip_prob.h" 59 #include "scip/scip_sol.h" 60 #include "scip/scip_solve.h" 61 #include "scip/scip_solvingstats.h" 62 #include "scip/scip_timing.h" 63 #include "scip/scip_var.h" 64 #include <string.h> 65 66 #define HEUR_NAME "proximity" 67 #define HEUR_DESC "heuristic trying to improve the incumbent by an auxiliary proximity objective function" 68 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS 69 #define HEUR_PRIORITY -2000000 70 #define HEUR_FREQ -1 71 #define HEUR_FREQOFS 0 72 #define HEUR_MAXDEPTH -1 73 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE 74 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */ 75 76 /* event handler properties */ 77 #define EVENTHDLR_NAME "Proximity" 78 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" 79 80 /* default values for proximity-specific parameters */ 81 /* todo refine these values */ 82 #define DEFAULT_MAXNODES 10000LL /**< maximum number of nodes to regard in the subproblem */ 83 #define DEFAULT_MINIMPROVE 0.02 /**< factor by which proximity should at least improve the incumbent */ 84 #define DEFAULT_MINGAP 0.01 /**< minimum primal-dual gap for which the heuristic is executed */ 85 #define DEFAULT_MINNODES 1LL /**< minimum number of nodes to regard in the subproblem */ 86 #define DEFAULT_MINLPITERS 200LL /**< minimum number of LP iterations to perform in one sub-mip */ 87 #define DEFAULT_MAXLPITERS 100000LL /**< maximum number of LP iterations to be performed in the subproblem */ 88 #define DEFAULT_NODESOFS 50LL /**< number of nodes added to the contingent of the total nodes */ 89 #define DEFAULT_WAITINGNODES 100LL /**< default waiting nodes since last incumbent before heuristic is executed */ 90 #define DEFAULT_NODESQUOT 0.1 /**< default quotient of sub-MIP nodes with respect to number of processed nodes*/ 91 #define DEFAULT_USELPROWS FALSE /**< should subproblem be constructed based on LP row information? */ 92 #define DEFAULT_BINVARQUOT 0.1 /**< default threshold for percentage of binary variables required to start */ 93 #define DEFAULT_RESTART TRUE /**< should the heuristic immediately run again on its newly found solution? */ 94 #define DEFAULT_USEFINALLP FALSE /**< should the heuristic solve a final LP in case of continuous objective variables? */ 95 #define DEFAULT_LPITERSQUOT 0.2 /**< default quotient of sub-MIP LP iterations with respect to LP iterations so far */ 96 #define DEFAULT_USEUCT FALSE /**< should uct node selection be used at the beginning of the search? */ 97 98 /* 99 * Data structures 100 */ 101 102 /** primal heuristic data */ 103 struct SCIP_HeurData 104 { 105 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */ 106 SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */ 107 SCIP_Longint maxlpiters; /**< maximum number of LP iterations to be performed in the subproblem */ 108 SCIP_Longint nusedlpiters; /**< number of actually performed LP iterations */ 109 SCIP_Longint minlpiters; /**< minimum number of LP iterations to perform in one sub-mip */ 110 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */ 111 SCIP_Longint usednodes; /**< nodes already used by proximity in earlier calls */ 112 SCIP_Longint waitingnodes; /**< waiting nodes since last incumbent before heuristic is executed */ 113 SCIP_Real lpitersquot; /**< quotient of sub-MIP LP iterations with respect to LP iterations so far */ 114 SCIP_Real minimprove; /**< factor by which proximity should at least improve the incumbent */ 115 SCIP_Real mingap; /**< minimum primal-dual gap for which the heuristic is executed */ 116 SCIP_Real nodesquot; /**< quotient of sub-MIP nodes with respect to number of processed nodes */ 117 SCIP_Real binvarquot; /**< threshold for percantage of binary variables required to start */ 118 119 SCIP* subscip; /**< the subscip used by the heuristic */ 120 SCIP_HASHMAP* varmapfw; /**< map between scip variables and subscip variables */ 121 SCIP_VAR** subvars; /**< variables in subscip */ 122 SCIP_CONS* objcons; /**< the objective cutoff constraint of the subproblem */ 123 124 int nsubvars; /**< the number of subvars */ 125 int lastsolidx; /**< index of last solution on which the heuristic was processed */ 126 int subprobidx; /**< counter for the subproblem index to be solved by proximity */ 127 128 SCIP_Bool uselprows; /**< should subproblem be constructed based on LP row information? */ 129 SCIP_Bool restart; /**< should the heuristic immediately run again on its newly found solution? */ 130 SCIP_Bool usefinallp; /**< should the heuristic solve a final LP in case of continuous objective variables? */ 131 SCIP_Bool useuct; /**< should uct node selection be used at the beginning of the search? */ 132 }; 133 134 135 /* 136 * Local methods 137 */ 138 139 /** optimizes the continuous variables in an LP diving by fixing all integer variables to the given solution values */ 140 static 141 SCIP_RETCODE solveLp( 142 SCIP* scip, /**< SCIP data structure */ 143 SCIP_SOL* sol, /**< candidate solution for which continuous variables should be optimized */ 144 SCIP_Bool* success /**< was the dive successful? */ 145 ) 146 { 147 SCIP_VAR** vars; 148 SCIP_RETCODE retstat; 149 150 int v; 151 int nvars; 152 int ncontvars; 153 int nintvars; 154 155 SCIP_Bool lperror; 156 SCIP_Bool requiresnlp; 157 158 assert(success != NULL); 159 160 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, &ncontvars) ); 161 162 nintvars = nvars - ncontvars; 163 164 /**@todo in case of an MINLP, if SCIPisNLPConstructed() is TRUE rather solve the NLP instead of the LP */ 165 requiresnlp = SCIPisNLPConstructed(scip); 166 if( requiresnlp || ncontvars == 0 ) 167 return SCIP_OKAY; 168 169 /* start diving to calculate the LP relaxation */ 170 SCIP_CALL( SCIPstartDive(scip) ); 171 172 /* set the bounds of the variables: fixed for integers, global bounds for continuous */ 173 for( v = 0; v < nvars; ++v ) 174 { 175 if( SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_COLUMN ) 176 { 177 SCIP_CALL( SCIPchgVarLbDive(scip, vars[v], SCIPvarGetLbGlobal(vars[v])) ); 178 SCIP_CALL( SCIPchgVarUbDive(scip, vars[v], SCIPvarGetUbGlobal(vars[v])) ); 179 } 180 } 181 182 /* apply this after global bounds to not cause an error with intermediate empty domains */ 183 for( v = 0; v < nintvars; ++v ) 184 { 185 if( SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_COLUMN ) 186 { 187 SCIP_Real solval; 188 189 solval = SCIPgetSolVal(scip, sol, vars[v]); 190 SCIP_CALL( SCIPchgVarLbDive(scip, vars[v], solval) ); 191 SCIP_CALL( SCIPchgVarUbDive(scip, vars[v], solval) ); 192 } 193 } 194 195 /* solve LP */ 196 SCIPdebugMsg(scip, " -> old LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip)); 197 198 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic. 199 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 200 */ 201 retstat = SCIPsolveDiveLP(scip, -1, &lperror, NULL); 202 if( retstat != SCIP_OKAY ) 203 { 204 #ifdef NDEBUG 205 SCIPwarningMessage(scip, "Error while solving LP in Proximity heuristic; LP solve terminated with code <%d>\n",retstat); 206 #else 207 SCIP_CALL( retstat ); 208 #endif 209 } 210 211 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip)); 212 SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip)); 213 if( !lperror && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL ) 214 { 215 SCIP_CALL( SCIPlinkLPSol(scip, sol) ); 216 SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, TRUE, TRUE, TRUE, success) ); 217 } 218 219 /* terminate diving mode */ 220 SCIP_CALL( SCIPendDive(scip) ); 221 222 return SCIP_OKAY; 223 } 224 225 /** creates a new solution for the original problem by copying the solution of the subproblem */ 226 static 227 SCIP_RETCODE createNewSol( 228 SCIP* scip, /**< original SCIP data structure */ 229 SCIP* subscip, /**< SCIP structure of the subproblem */ 230 SCIP_VAR** subvars, /**< the variables of the subproblem */ 231 SCIP_HEUR* heur, /**< proximity heuristic structure */ 232 SCIP_SOL* subsol, /**< solution of the subproblem */ 233 SCIP_Bool usefinallp, /**< should continuous variables be optimized by a final LP */ 234 SCIP_Bool* success /**< used to store whether new solution was found or not */ 235 ) 236 { 237 SCIP_VAR** vars; /* the original problem's variables */ 238 int nvars; /* the original problem's number of variables */ 239 int ncontvars; /* the original problem's number of continuous variables */ 240 SCIP_Real* subsolvals; /* solution values of the subproblem */ 241 SCIP_SOL* newsol; /* solution to be created for the original problem */ 242 int i; 243 244 assert(scip != NULL); 245 assert(subscip != NULL); 246 assert(subvars != NULL); 247 assert(subsol != NULL); 248 assert(success != NULL); 249 250 /* get variables' data */ 251 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, &ncontvars) ); 252 253 SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) ); 254 255 /* copy the solution */ 256 for( i = 0; i < nvars; ++i ) 257 { 258 if( subvars[i] == NULL ) 259 subsolvals[i] = MIN(MAX(0.0, SCIPvarGetLbLocal(vars[i])), SCIPvarGetUbLocal(vars[i])); /*lint !e666*/ 260 else 261 subsolvals[i] = SCIPgetSolVal(subscip, subsol, subvars[i]); 262 } 263 264 /* create new solution for the original problem */ 265 SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) ); 266 SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) ); 267 268 *success = FALSE; 269 270 /* solve an LP with all integer variables fixed to improve solution quality */ 271 if( ncontvars > 0 && usefinallp && SCIPisLPConstructed(scip) ) 272 { 273 int v; 274 int ncontobjvars = 0; /* does the problem instance have continuous variables with nonzero objective coefficients? */ 275 SCIP_Real sumofobjsquares = 0.0; 276 277 /* check if continuous variables with nonzero objective coefficient are present */ 278 for( v = nvars - 1; v >= nvars - ncontvars; --v ) 279 { 280 SCIP_VAR* var; 281 282 var = vars[v]; 283 assert(vars[v] != NULL); 284 assert(!SCIPvarIsIntegral(var)); 285 286 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN && !SCIPisZero(scip, SCIPvarGetObj(var)) ) 287 { 288 ++ncontobjvars; 289 sumofobjsquares += SCIPvarGetObj(var) * SCIPvarGetObj(var); 290 } 291 } 292 293 SCIPstatisticMessage(" Continuous Objective variables: %d, Euclidean OBJ: %g total, %g continuous\n", ncontobjvars, SCIPgetObjNorm(scip), sumofobjsquares); 294 295 /* solve a final LP to optimize solution values of continuous problem variables */ 296 SCIPstatisticMessage("Solution Value before LP resolve: %g\n", SCIPgetSolOrigObj(scip, newsol)); 297 SCIP_CALL( solveLp(scip, newsol, success) ); 298 299 /* if the LP solve was not successful, reset the solution */ 300 if( !*success ) 301 { 302 for( v = nvars - 1; v >= nvars - ncontvars; --v ) 303 { 304 SCIP_CALL( SCIPsetSolVal(scip, newsol, vars[v], subsolvals[v]) ); 305 } 306 } 307 } 308 309 /* try to add new solution to SCIP and free it immediately */ 310 if( !*success ) 311 { 312 SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) ); 313 } 314 SCIP_CALL( SCIPfreeSol(scip, &newsol) ); 315 316 SCIPfreeBufferArray(scip, &subsolvals); 317 318 return SCIP_OKAY; 319 } 320 321 /** sets solving parameters for the subproblem created by the heuristic */ 322 static 323 SCIP_RETCODE setupSubproblem( 324 SCIP_HEURDATA* heurdata, /**< heuristic data structure */ 325 SCIP* subscip /**< copied SCIP data structure */ 326 ) 327 { 328 assert(subscip != NULL); 329 330 /* do not abort subproblem on CTRL-C */ 331 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) ); 332 333 #ifdef SCIP_DEBUG 334 /* for debugging, enable full output */ 335 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) ); 336 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) ); 337 #else 338 /* disable statistic timing inside sub SCIP and output to console */ 339 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) ); 340 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) ); 341 #endif 342 343 /* forbid recursive call of heuristics and separators solving sub-SCIPs */ 344 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) ); 345 346 /* use restart dfs node selection */ 347 if( SCIPfindNodesel(subscip, "restartdfs") != NULL && !SCIPisParamFixed(subscip, "nodeselection/restartdfs/stdpriority") ) 348 { 349 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/restartdfs/stdpriority", INT_MAX/4) ); 350 } 351 352 /* activate uct node selection at the top of the tree */ 353 if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") ) 354 { 355 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) ); 356 } 357 358 /* disable expensive presolving 359 * todo maybe presolving can be entirely turned off here - parameter??? 360 */ 361 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) ); 362 363 /* SCIP_CALL( SCIPsetPresolving(scip, SCIP_PARAMSETTING_OFF, TRUE) ); */ 364 if( !SCIPisParamFixed(subscip, "presolving/maxrounds") ) 365 { 366 SCIP_CALL( SCIPsetIntParam(subscip, "presolving/maxrounds", 50) ); 367 } 368 369 /* disable cutting plane separation */ 370 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) ); 371 372 /* todo: check branching rule in sub-SCIP */ 373 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") ) 374 { 375 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) ); 376 } 377 378 /* disable feasibility pump and fractional diving */ 379 if( !SCIPisParamFixed(subscip, "heuristics/feaspump/freq") ) 380 { 381 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/feaspump/freq", -1) ); 382 } 383 if( !SCIPisParamFixed(subscip, "heuristics/fracdiving/freq") ) 384 { 385 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/fracdiving/freq", -1) ); 386 } 387 388 /* todo check if 389 * SCIP_CALL( SCIPsetEmphasis(subscip, SCIP_PARAMEMPHASIS_FEASIBILITY, TRUE) ); 390 * improves performance */ 391 392 return SCIP_OKAY; 393 } 394 395 /** frees the subproblem */ 396 static 397 SCIP_RETCODE deleteSubproblem( 398 SCIP* scip, /**< SCIP data structure */ 399 SCIP_HEURDATA* heurdata /**< heuristic data */ 400 ) 401 { 402 /* free remaining memory from heuristic execution */ 403 if( heurdata->subscip != NULL ) 404 { 405 assert(heurdata->varmapfw != NULL); 406 assert(heurdata->subvars != NULL); 407 assert(heurdata->objcons != NULL); 408 409 SCIPdebugMsg(scip, "Freeing subproblem of proximity heuristic\n"); 410 SCIPfreeBlockMemoryArray(scip, &heurdata->subvars, heurdata->nsubvars); 411 SCIPhashmapFree(&heurdata->varmapfw); 412 SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &heurdata->objcons) ); 413 SCIP_CALL( SCIPfree(&heurdata->subscip) ); 414 415 heurdata->subscip = NULL; 416 heurdata->varmapfw = NULL; 417 heurdata->subvars = NULL; 418 heurdata->objcons = NULL; 419 } 420 return SCIP_OKAY; 421 } 422 423 /* ---------------- Callback methods of event handler ---------------- */ 424 425 /** exec the event handler 426 * 427 * We interrupt the solution process. 428 */ 429 static 430 SCIP_DECL_EVENTEXEC(eventExecProximity) 431 { 432 SCIP_HEURDATA* heurdata; 433 434 assert(eventhdlr != NULL); 435 assert(eventdata != NULL); 436 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 437 assert(event != NULL); 438 assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_NODESOLVED); 439 440 heurdata = (SCIP_HEURDATA*)eventdata; 441 assert(heurdata != NULL); 442 443 /* interrupt solution process of sub-SCIP 444 * todo adjust interruption limit */ 445 if( SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_ITERLIMIT || SCIPgetNLPIterations(scip) >= heurdata->maxlpiters ) 446 { 447 SCIP_CALL( SCIPinterruptSolve(scip) ); 448 } 449 450 return SCIP_OKAY; 451 } 452 453 454 /* ---------------- Callback methods of primal heuristic ---------------- */ 455 456 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 457 static 458 SCIP_DECL_HEURCOPY(heurCopyProximity) 459 { /*lint --e{715}*/ 460 assert(scip != NULL); 461 assert(heur != NULL); 462 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 463 464 /* call inclusion method of primal heuristic */ 465 SCIP_CALL( SCIPincludeHeurProximity(scip) ); 466 467 return SCIP_OKAY; 468 } 469 470 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 471 static 472 SCIP_DECL_HEURFREE(heurFreeProximity) 473 { /*lint --e{715}*/ 474 SCIP_HEURDATA* heurdata; 475 476 assert( heur != NULL ); 477 assert( scip != NULL ); 478 479 /* get heuristic data */ 480 heurdata = SCIPheurGetData(heur); 481 assert( heurdata != NULL ); 482 483 /* free heuristic data */ 484 SCIPfreeBlockMemory(scip, &heurdata); 485 SCIPheurSetData(heur, NULL); 486 487 return SCIP_OKAY; 488 } 489 490 491 /** initialization method of primal heuristic (called after problem was transformed) */ 492 static 493 SCIP_DECL_HEURINIT(heurInitProximity) 494 { /*lint --e{715}*/ 495 SCIP_HEURDATA* heurdata; 496 497 assert( heur != NULL ); 498 assert( scip != NULL ); 499 500 /* get heuristic data */ 501 heurdata = SCIPheurGetData(heur); 502 assert( heurdata != NULL ); 503 504 /* initialize data */ 505 heurdata->usednodes = 0LL; 506 heurdata->lastsolidx = -1; 507 heurdata->nusedlpiters = 0LL; 508 heurdata->subprobidx = 0; 509 510 heurdata->subscip = NULL; 511 heurdata->varmapfw = NULL; 512 heurdata->subvars = NULL; 513 heurdata->objcons = NULL; 514 515 heurdata->nsubvars = 0; 516 517 return SCIP_OKAY; 518 } 519 520 /** solution process exiting method of proximity heuristic */ 521 static 522 SCIP_DECL_HEUREXITSOL(heurExitsolProximity) 523 { 524 SCIP_HEURDATA* heurdata; 525 526 assert( heur != NULL ); 527 assert( scip != NULL ); 528 529 /* get heuristic data */ 530 heurdata = SCIPheurGetData(heur); 531 assert( heurdata != NULL ); 532 533 SCIP_CALL( deleteSubproblem(scip, heurdata) ); 534 535 assert(heurdata->subscip == NULL && heurdata->varmapfw == NULL && heurdata->subvars == NULL && heurdata->objcons == NULL); 536 537 return SCIP_OKAY; 538 } 539 540 /** execution method of primal heuristic */ 541 static 542 SCIP_DECL_HEUREXEC(heurExecProximity) 543 { /*lint --e{715}*/ 544 SCIP_HEURDATA* heurdata; /* heuristic's data */ 545 SCIP_Longint nnodes; /* number of stalling nodes for the subproblem */ 546 SCIP_Longint nlpiters; /* lp iteration limit for the subproblem */ 547 SCIP_Bool foundsol = FALSE; 548 549 assert(heur != NULL); 550 assert(scip != NULL); 551 assert(result != NULL); 552 553 *result = SCIP_DIDNOTRUN; 554 555 /* get heuristic data */ 556 heurdata = SCIPheurGetData(heur); 557 assert(heurdata != NULL); 558 559 /* do not run heuristic when there are only few binary varables */ 560 if( SCIPgetNBinVars(scip) < heurdata->binvarquot * SCIPgetNVars(scip) ) 561 return SCIP_OKAY; 562 563 /* calculate branching node limit for sub problem */ 564 /* todo maybe treat root node differently */ 565 nnodes = (SCIP_Longint) (heurdata->nodesquot * SCIPgetNNodes(scip)); 566 nnodes += heurdata->nodesofs; 567 568 /* determine the node and LP iteration limit for the solve of the sub-SCIP */ 569 nnodes -= heurdata->usednodes; 570 nnodes = MIN(nnodes, heurdata->maxnodes); 571 572 nlpiters = (SCIP_Longint) (heurdata->lpitersquot * SCIPgetNRootFirstLPIterations(scip)); 573 nlpiters = MIN(nlpiters, heurdata->maxlpiters); 574 575 /* check whether we have enough nodes left to call subproblem solving */ 576 if( nnodes < heurdata->minnodes ) 577 { 578 SCIPdebugMsg(scip, "skipping proximity: nnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nnodes, heurdata->minnodes); 579 return SCIP_OKAY; 580 } 581 582 /* do not run proximity, if the problem does not have an objective function anyway */ 583 if( SCIPgetNObjVars(scip) == 0 ) 584 { 585 SCIPdebugMsg(scip, "skipping proximity: pure feasibility problem anyway\n"); 586 return SCIP_OKAY; 587 } 588 589 do 590 { 591 /* main loop of proximity: in every iteration, a new subproblem is set up and solved until no improved solution 592 * is found or one of the heuristic limits on nodes or LP iterations is hit 593 * heuristic performs only one iteration if restart parameter is set to FALSE 594 */ 595 SCIP_Longint nusednodes = 0LL; 596 SCIP_Longint nusedlpiters = 0LL; 597 598 nlpiters = MAX(nlpiters, heurdata->minlpiters); 599 600 /* define and solve the proximity subproblem */ 601 SCIP_CALL( SCIPapplyProximity(scip, heur, result, heurdata->minimprove, nnodes, nlpiters, &nusednodes, &nusedlpiters, FALSE) ); 602 603 /* adjust node limit and LP iteration limit for future iterations */ 604 assert(nusednodes <= nnodes); 605 heurdata->usednodes += nusednodes; 606 nnodes -= nusednodes; 607 608 nlpiters -= nusedlpiters; 609 heurdata->nusedlpiters += nusedlpiters; 610 611 /* memorize if a new solution has been found in at least one iteration */ 612 if( *result == SCIP_FOUNDSOL ) 613 foundsol = TRUE; 614 } 615 while( *result == SCIP_FOUNDSOL && heurdata->restart && !SCIPisStopped(scip) && nnodes > 0 ); 616 617 /* reset result pointer if solution has been found in previous iteration */ 618 if( foundsol ) 619 *result = SCIP_FOUNDSOL; 620 621 /* free the occupied memory */ 622 if( heurdata->subscip != NULL ) 623 { 624 /* just for testing the library method, in debug mode, we call the wrapper method for the actual delete method */ 625 #ifndef NDEBUG 626 SCIP_CALL( SCIPdeleteSubproblemProximity(scip) ); 627 #else 628 SCIP_CALL( deleteSubproblem(scip, heurdata) ); 629 #endif 630 } 631 return SCIP_OKAY; 632 } 633 634 635 /* 636 * primal heuristic specific interface methods 637 */ 638 639 /** frees the sub-MIP created by proximity */ 640 SCIP_RETCODE SCIPdeleteSubproblemProximity( 641 SCIP* scip /** SCIP data structure */ 642 ) 643 { 644 SCIP_HEUR* heur; 645 SCIP_HEURDATA* heurdata; 646 647 assert(scip != NULL); 648 649 heur = SCIPfindHeur(scip, HEUR_NAME); 650 assert(heur != NULL); 651 652 heurdata = SCIPheurGetData(heur); 653 if( heurdata != NULL ) 654 { 655 SCIP_CALL( deleteSubproblem(scip, heurdata) ); 656 } 657 658 return SCIP_OKAY; 659 } 660 661 /** main procedure of the proximity heuristic, creates and solves a sub-SCIP 662 * 663 * @note The method can be applied in an iterative way, keeping the same subscip in between. If the @p freesubscip 664 * parameter is set to FALSE, the heuristic will keep the subscip data structures. Always set this parameter 665 * to TRUE, or call SCIPdeleteSubproblemProximity() afterwards. 666 */ 667 SCIP_RETCODE SCIPapplyProximity( 668 SCIP* scip, /**< original SCIP data structure */ 669 SCIP_HEUR* heur, /**< heuristic data structure */ 670 SCIP_RESULT* result, /**< result data structure */ 671 SCIP_Real minimprove, /**< factor by which proximity should at least improve the incumbent */ 672 SCIP_Longint nnodes, /**< node limit for the subproblem */ 673 SCIP_Longint nlpiters, /**< LP iteration limit for the subproblem */ 674 SCIP_Longint* nusednodes, /**< pointer to store number of used nodes in subscip */ 675 SCIP_Longint* nusedlpiters, /**< pointer to store number of used LP iterations in subscip */ 676 SCIP_Bool freesubscip /**< should the created sub-MIP be freed at the end of the method? */ 677 ) 678 { 679 SCIP* subscip; /* the subproblem created by proximity */ 680 SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */ 681 SCIP_VAR** vars; /* original problem's variables */ 682 SCIP_VAR** subvars; /* subproblem's variables */ 683 SCIP_HEURDATA* heurdata; /* heuristic's private data structure */ 684 SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */ 685 686 SCIP_SOL* incumbent; 687 SCIP_CONS* objcons; 688 SCIP_Longint iterlim; 689 690 SCIP_Real large; 691 SCIP_Real inf; 692 693 SCIP_Real bestobj; 694 SCIP_Real objcutoff; 695 SCIP_Real lowerbound; 696 697 int nvars; /* number of original problem's variables */ 698 int nfixedvars; 699 int nsubsols; 700 int solidx; 701 int i; 702 703 SCIP_Bool valid; 704 SCIP_Bool success; 705 706 assert(scip != NULL); 707 assert(heur != NULL); 708 assert(result != NULL); 709 710 assert(nnodes >= 0); 711 assert(0.0 <= minimprove && minimprove <= 1.0); 712 713 *result = SCIP_DIDNOTRUN; 714 715 /* get heuristic data */ 716 heurdata = SCIPheurGetData(heur); 717 assert(heurdata != NULL); 718 719 /* only call the heuristic if we have an incumbent */ 720 if( SCIPgetNSolsFound(scip) == 0 ) 721 return SCIP_OKAY; 722 723 /* do not use heuristic on problems without binary variables */ 724 if( SCIPgetNBinVars(scip) == 0 ) 725 return SCIP_OKAY; 726 727 incumbent = SCIPgetBestSol(scip); 728 assert(incumbent != NULL); 729 730 /* make sure that the incumbent is valid for the transformed space, otherwise terminate */ 731 if( SCIPsolIsOriginal(incumbent) ) 732 return SCIP_OKAY; 733 734 solidx = SCIPsolGetIndex(incumbent); 735 736 if( heurdata->lastsolidx == solidx ) 737 return SCIP_OKAY; 738 739 /* only call heuristic, if the best solution does not come from trivial heuristic */ 740 if( SCIPsolGetHeur(incumbent) != NULL && strcmp(SCIPheurGetName(SCIPsolGetHeur(incumbent)), "trivial") == 0 ) 741 return SCIP_OKAY; 742 743 /* waitingnodes parameter defines the minimum number of nodes to wait before a new incumbent is processed */ 744 if( SCIPgetNNodes(scip) > 1 && SCIPgetNNodes(scip) - SCIPsolGetNodenum(incumbent) < heurdata->waitingnodes ) 745 return SCIP_OKAY; 746 747 bestobj = SCIPgetSolTransObj(scip, incumbent); 748 lowerbound = SCIPgetLowerbound(scip); 749 750 /* use knowledge about integrality of objective to round up lower bound */ 751 if( SCIPisObjIntegral(scip) ) 752 { 753 SCIPdebugMsg(scip, " Rounding up lower bound: %f --> %f \n", lowerbound, SCIPfeasCeil(scip, lowerbound)); 754 lowerbound = SCIPfeasCeil(scip, lowerbound); 755 } 756 757 /* do not trigger heuristic if primal and dual bound are already close together */ 758 if( SCIPisFeasLE(scip, bestobj, lowerbound) || SCIPgetGap(scip) <= heurdata->mingap ) 759 return SCIP_OKAY; 760 761 /* calculate the minimum improvement for a heuristic solution in terms of the distance between incumbent objective 762 * and the lower bound */ 763 if( SCIPisInfinity(scip, REALABS(lowerbound)) ) 764 { 765 if( SCIPisZero(scip, bestobj) ) 766 objcutoff = bestobj - 1; 767 else 768 objcutoff = (1 - minimprove) * bestobj; 769 } 770 else 771 objcutoff = minimprove * lowerbound + (1 - minimprove) * (bestobj); 772 773 /* use integrality of the objective function to round down (and thus strengthen) the objective cutoff */ 774 if( SCIPisObjIntegral(scip) ) 775 objcutoff = SCIPfeasFloor(scip, objcutoff); 776 777 if( SCIPisFeasLT(scip, objcutoff, lowerbound) ) 778 objcutoff = lowerbound; 779 780 /* exit execution if the right hand side of the objective constraint does not change (suggests that the heuristic 781 * was not successful in a previous iteration) */ 782 if( heurdata->objcons != NULL && SCIPisFeasEQ(scip, SCIPgetRhsLinear(heurdata->subscip, heurdata->objcons), objcutoff) ) 783 return SCIP_OKAY; 784 785 /* check whether there is enough time and memory left */ 786 SCIP_CALL( SCIPcheckCopyLimits(scip, &valid) ); 787 788 if( ! valid ) 789 return SCIP_OKAY; 790 791 *result = SCIP_DIDNOTFIND; 792 793 heurdata->lastsolidx = solidx; 794 795 /* get variable data */ 796 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 797 798 /* create a subscip and copy the original scip instance into it */ 799 if( heurdata->subscip == NULL ) 800 { 801 assert(heurdata->varmapfw == NULL); 802 assert(heurdata->objcons == NULL); 803 804 /* initialize the subproblem */ 805 SCIP_CALL( SCIPcreate(&subscip) ); 806 807 /* create the variable mapping hash map */ 808 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) ); 809 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &subvars, nvars) ); 810 811 /* copy complete SCIP instance */ 812 valid = FALSE; 813 814 /* create a problem copy as sub SCIP */ 815 SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "proximity", NULL, NULL, 0, heurdata->uselprows, TRUE, 816 &success, &valid) ); 817 818 SCIPdebugMsg(scip, "Copying the SCIP instance was %s complete.\n", valid ? "" : "not "); 819 820 /* create event handler for LP events */ 821 eventhdlr = NULL; 822 SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecProximity, NULL) ); 823 if( eventhdlr == NULL ) 824 { 825 SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n"); 826 return SCIP_PLUGINNOTFOUND; 827 } 828 829 /* set up parameters for the copied instance */ 830 SCIP_CALL( setupSubproblem(heurdata, subscip) ); 831 832 /* create the objective constraint in the sub scip, first without variables and values which will be added later */ 833 SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &objcons, "objbound_of_origscip", 0, NULL, NULL, -SCIPinfinity(subscip), SCIPinfinity(subscip)) ); 834 835 /* determine large value to set variable bounds to, safe-guard to avoid fixings to infinite values */ 836 large = SCIPinfinity(scip); 837 if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) ) 838 large = 0.1 / SCIPfeastol(scip); 839 inf = SCIPinfinity(subscip); 840 841 /* get variable image and change objective to proximity function (Manhattan distance) in sub-SCIP */ 842 for( i = 0; i < nvars; i++ ) 843 { 844 SCIP_Real adjustedbound; 845 SCIP_Real lb; 846 SCIP_Real ub; 847 848 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]); 849 850 if( subvars[i] == NULL ) 851 continue; 852 853 SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], 0.0) ); 854 855 lb = SCIPvarGetLbGlobal(subvars[i]); 856 ub = SCIPvarGetUbGlobal(subvars[i]); 857 858 /* adjust infinite bounds in order to avoid that variables with non-zero objective 859 * get fixed to infinite value in proximity subproblem 860 */ 861 if( SCIPisInfinity(subscip, ub) ) 862 { 863 adjustedbound = MAX(large, lb + large); 864 adjustedbound = MIN(adjustedbound, inf); 865 SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], adjustedbound) ); 866 } 867 if( SCIPisInfinity(subscip, -lb) ) 868 { 869 adjustedbound = MIN(-large, ub - large); 870 adjustedbound = MAX(adjustedbound, -inf); 871 SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], adjustedbound) ); 872 } 873 874 /* add all nonzero objective coefficients to the objective constraint */ 875 if( !SCIPisFeasZero(subscip, SCIPvarGetObj(vars[i])) ) 876 { 877 SCIP_CALL( SCIPaddCoefLinear(subscip, objcons, subvars[i], SCIPvarGetObj(vars[i])) ); 878 } 879 } 880 881 /* add objective constraint to the subscip */ 882 SCIP_CALL( SCIPaddCons(subscip, objcons) ); 883 } 884 else 885 { 886 /* the instance, event handler, hash map and variable array were already copied in a previous iteration 887 * and stored in heuristic data 888 */ 889 assert(heurdata->varmapfw != NULL); 890 assert(heurdata->subvars != NULL); 891 assert(heurdata->objcons != NULL); 892 893 subscip = heurdata->subscip; 894 varmapfw = heurdata->varmapfw; 895 subvars = heurdata->subvars; 896 objcons = heurdata->objcons; 897 898 eventhdlr = SCIPfindEventhdlr(subscip, EVENTHDLR_NAME); 899 assert(eventhdlr != NULL); 900 } 901 902 SCIP_CALL( SCIPchgRhsLinear(subscip, objcons, objcutoff) ); 903 904 for( i = 0; i < SCIPgetNBinVars(scip); ++i ) 905 { 906 SCIP_Real solval; 907 908 if( subvars[i] == NULL ) 909 continue; 910 911 /* objective coefficients are only set for binary variables of the problem */ 912 assert(SCIPvarIsBinary(subvars[i])); 913 914 solval = SCIPgetSolVal(scip, incumbent, vars[i]); 915 assert(SCIPisFeasGE(scip, solval, 0.0)); 916 assert(SCIPisFeasLE(scip, solval, 1.0)); 917 assert(SCIPisFeasIntegral(scip, solval)); 918 919 if( solval < 0.5 ) 920 { 921 SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], 1.0) ); 922 } 923 else 924 { 925 SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], -1.0) ); 926 } 927 } 928 929 /* set limits for the subproblem */ 930 SCIP_CALL( SCIPcopyLimits(scip, subscip) ); 931 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nnodes) ); 932 SCIP_CALL( SCIPsetIntParam(subscip, "limits/solutions", 1) ); 933 934 /* restrict LP iterations */ 935 /* todo set iterations limit depending on the number of iterations of the original problem root */ 936 iterlim = nlpiters; 937 SCIP_CALL( SCIPsetLongintParam(subscip, "lp/iterlim", MAX(1, iterlim / MIN(10, nnodes))) ); 938 SCIP_CALL( SCIPsetLongintParam(subscip, "lp/rootiterlim", iterlim) ); 939 940 /* catch LP events of sub-SCIP */ 941 SCIP_CALL( SCIPtransformProb(subscip) ); 942 SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) ); 943 944 SCIPstatisticMessage("solving subproblem at Node: %" SCIP_LONGINT_FORMAT " " 945 "nnodes: %" SCIP_LONGINT_FORMAT " " 946 "iterlim: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNNodes(scip), nnodes, iterlim); 947 948 /* solve the subproblem with all previously adjusted parameters */ 949 nfixedvars = SCIPgetNFixedVars(subscip); 950 951 SCIP_CALL( SCIPpresolve(subscip) ); 952 953 nfixedvars = SCIPgetNFixedVars(subscip) - nfixedvars; 954 assert(nfixedvars >= 0); 955 SCIPstatisticMessage("presolve fixings %d: %d\n", ++(heurdata->subprobidx), nfixedvars); 956 957 /* errors in solving the subproblem should not kill the overall solving process; 958 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 959 */ 960 SCIP_CALL_ABORT( SCIPsolve(subscip) ); 961 962 /* print solving statistics of subproblem if we are in SCIP's debug mode */ 963 SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) ); 964 SCIPstatisticMessage("solve of subscip %d:" 965 "usednodes: %" SCIP_LONGINT_FORMAT " " 966 "lp iters: %" SCIP_LONGINT_FORMAT " " 967 "root iters: %" SCIP_LONGINT_FORMAT " " 968 "Presolving Time: %.2f\n", heurdata->subprobidx, 969 SCIPgetNNodes(subscip), SCIPgetNLPIterations(subscip), SCIPgetNRootLPIterations(subscip), SCIPgetPresolvingTime(subscip)); 970 971 SCIPstatisticMessage("Solving Time %d: %.2f\n", heurdata->subprobidx, SCIPgetSolvingTime(subscip) ); 972 973 /* drop LP events of sub-SCIP */ 974 SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) ); 975 976 /* keep track of relevant information for future runs of heuristic */ 977 if( nusednodes != NULL ) 978 *nusednodes = SCIPgetNNodes(subscip); 979 if( nusedlpiters != NULL ) 980 *nusedlpiters = SCIPgetNLPIterations(subscip); 981 982 /* check whether a solution was found */ 983 nsubsols = SCIPgetNSols(subscip); 984 incumbent = SCIPgetBestSol(subscip); 985 assert(nsubsols == 0 || incumbent != NULL); 986 987 SCIPstatisticMessage("primal bound before subproblem %d: %g\n", heurdata->subprobidx, SCIPgetPrimalbound(scip)); 988 if( nsubsols > 0 ) 989 { 990 /* try to translate the sub problem solution to the original scip instance */ 991 success = FALSE; 992 SCIP_CALL( createNewSol(scip, subscip, subvars, heur, incumbent, heurdata->usefinallp, &success) ); 993 994 if( success ) 995 *result = SCIP_FOUNDSOL; 996 } 997 SCIPstatisticMessage("primal bound after subproblem %d: %g\n", heurdata->subprobidx, SCIPgetPrimalbound(scip)); 998 999 /* free the transformed subproblem data */ 1000 SCIP_CALL( SCIPfreeTransform(subscip) ); 1001 1002 /* save subproblem in heuristic data for subsequent runs if it has been successful, otherwise free subproblem */ 1003 heurdata->subscip = subscip; 1004 heurdata->varmapfw = varmapfw; 1005 heurdata->subvars = subvars; 1006 heurdata->objcons = objcons; 1007 heurdata->nsubvars = nvars; 1008 1009 /* delete the sub problem */ 1010 if( freesubscip ) 1011 { 1012 SCIP_CALL( deleteSubproblem(scip, heurdata) ); 1013 } 1014 1015 return SCIP_OKAY; 1016 } 1017 1018 1019 /** creates the proximity primal heuristic and includes it in SCIP */ 1020 SCIP_RETCODE SCIPincludeHeurProximity( 1021 SCIP* scip /**< SCIP data structure */ 1022 ) 1023 { 1024 SCIP_HEURDATA* heurdata; 1025 SCIP_HEUR* heur = NULL; 1026 1027 /* create heuristic data */ 1028 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 1029 1030 /* include primal heuristic */ 1031 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 1032 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 1033 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecProximity, heurdata) ); 1034 assert(heur != NULL); 1035 1036 /* set non-NULL pointers to callback methods */ 1037 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyProximity) ); 1038 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeProximity) ); 1039 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitProximity) ); 1040 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolProximity) ); 1041 1042 /* add proximity primal heuristic parameters */ 1043 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows", 1044 "should subproblem be constructed based on LP row information?", 1045 &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) ); 1046 1047 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/restart", 1048 "should the heuristic immediately run again on its newly found solution?", 1049 &heurdata->restart, TRUE, DEFAULT_RESTART, NULL, NULL) ); 1050 1051 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usefinallp", 1052 "should the heuristic solve a final LP in case of continuous objective variables?", 1053 &heurdata->usefinallp, TRUE, DEFAULT_USEFINALLP, NULL, NULL) ); 1054 1055 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes", 1056 "maximum number of nodes to regard in the subproblem", 1057 &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1058 1059 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs", 1060 "number of nodes added to the contingent of the total nodes", 1061 &heurdata->nodesofs, TRUE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1062 1063 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes", 1064 "minimum number of nodes required to start the subproblem", 1065 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1066 1067 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxlpiters", 1068 "maximum number of LP iterations to be performed in the subproblem", 1069 &heurdata->maxlpiters, TRUE, DEFAULT_MAXLPITERS, -1LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1070 1071 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minlpiters", 1072 "minimum number of LP iterations performed in subproblem", 1073 &heurdata->minlpiters, TRUE, DEFAULT_MINLPITERS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1074 1075 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/waitingnodes", 1076 "waiting nodes since last incumbent before heuristic is executed", 1077 &heurdata->waitingnodes, TRUE, DEFAULT_WAITINGNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1078 1079 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove", 1080 "factor by which proximity should at least improve the incumbent", 1081 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) ); 1082 1083 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot", 1084 "sub-MIP node limit w.r.t number of original nodes", 1085 &heurdata->nodesquot, TRUE, DEFAULT_NODESQUOT, 0.0, SCIPinfinity(scip), NULL, NULL) ); 1086 1087 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/binvarquot", 1088 "threshold for percentage of binary variables required to start", 1089 &heurdata->binvarquot, TRUE, DEFAULT_BINVARQUOT, 0.0, 1.0, NULL, NULL) ); 1090 1091 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lpitersquot", 1092 "quotient of sub-MIP LP iterations with respect to LP iterations so far", 1093 &heurdata->lpitersquot, TRUE, DEFAULT_LPITERSQUOT, 0.0, 1.0, NULL, NULL) ); 1094 1095 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/mingap", 1096 "minimum primal-dual gap for which the heuristic is executed", 1097 &heurdata->mingap, TRUE, DEFAULT_MINGAP, 0.0, SCIPinfinity(scip), NULL, NULL) ); 1098 1099 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct", 1100 "should uct node selection be used at the beginning of the search?", 1101 &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) ); 1102 1103 return SCIP_OKAY; 1104 } 1105