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_rens.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief LNS heuristic that finds the optimal rounding to a given point 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_rens.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_nlp.h" 52 #include "scip/scip_nlpi.h" 53 #include "scip/scip_nodesel.h" 54 #include "scip/scip_numerics.h" 55 #include "scip/scip_param.h" 56 #include "scip/scip_prob.h" 57 #include "scip/scip_sol.h" 58 #include "scip/scip_solve.h" 59 #include "scip/scip_solvingstats.h" 60 #include "scip/scip_timing.h" 61 #include "scip/scip_var.h" 62 #include <string.h> 63 64 /* default values for standard parameters that every primal heuristic has in SCIP */ 65 #define HEUR_NAME "rens" 66 #define HEUR_DESC "LNS exploring fractional neighborhood of relaxation's optimum" 67 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS 68 #define HEUR_PRIORITY -1100000 69 #define HEUR_FREQ 0 70 #define HEUR_FREQOFS 0 71 #define HEUR_MAXDEPTH -1 72 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE 73 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */ 74 75 /* default values for RENS-specific plugins */ 76 #define DEFAULT_BINARYBOUNDS TRUE /* should general integers get binary bounds [floor(.),ceil(.)] ? */ 77 #define DEFAULT_MAXNODES 5000LL /* maximum number of nodes to regard in the subproblem */ 78 #define DEFAULT_MINFIXINGRATE 0.5 /* minimum percentage of integer variables that have to be fixed */ 79 #define DEFAULT_MINIMPROVE 0.01 /* factor by which RENS should at least improve the incumbent */ 80 #define DEFAULT_MINNODES 50LL /* minimum number of nodes to regard in the subproblem */ 81 #define DEFAULT_NODESOFS 500LL /* number of nodes added to the contingent of the total nodes */ 82 #define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */ 83 #define DEFAULT_LPLIMFAC 2.0 /* factor by which the limit on the number of LP depends on the node limit */ 84 #define DEFAULT_STARTSOL 'l' /* solution that is used for fixing values */ 85 #define STARTSOL_CHOICES "nl" /* possible values for startsol ('l'p relaxation, 'n'lp relaxation) */ 86 #define DEFAULT_USELPROWS FALSE /* should subproblem be created out of the rows in the LP rows, 87 * otherwise, the copy constructors of the constraints handlers are used */ 88 #define DEFAULT_COPYCUTS TRUE /* if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool 89 * of the original scip be copied to constraints of the subscip 90 */ 91 #define DEFAULT_EXTRATIME FALSE /* should the RENS sub-CIP get its own full time limit? This is only 92 * implemented for testing and not recommended to be used! 93 */ 94 #define DEFAULT_ADDALLSOLS FALSE /* should all subproblem solutions be added to the original SCIP? */ 95 96 #define DEFAULT_FULLSCALE FALSE /* should the RENS sub-CIP be solved with full-scale SCIP settings, including 97 * techniques that merely work on the dual bound, e.g., cuts? This is only 98 * implemented for testing and not recommended to be used! 99 */ 100 #define DEFAULT_BESTSOLLIMIT -1 /* limit on number of improving incumbent solutions in sub-CIP */ 101 #define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */ 102 103 /* event handler properties */ 104 #define EVENTHDLR_NAME "Rens" 105 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" 106 107 /* 108 * Data structures 109 */ 110 111 /** primal heuristic data */ 112 struct SCIP_HeurData 113 { 114 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */ 115 SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */ 116 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */ 117 SCIP_Longint usednodes; /**< nodes already used by RENS in earlier calls */ 118 SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */ 119 SCIP_Real minimprove; /**< factor by which RENS should at least improve the incumbent */ 120 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */ 121 SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/ 122 SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */ 123 char startsol; /**< solution used for fixing values ('l'p relaxation, 'n'lp relaxation) */ 124 SCIP_Bool binarybounds; /**< should general integers get binary bounds [floor(.),ceil(.)] ? */ 125 SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */ 126 SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied 127 * to constraints in subproblem? */ 128 SCIP_Bool extratime; /**< should the RENS sub-CIP get its own full time limit? This is only 129 * implemented for testing and not recommended to be used! */ 130 SCIP_Bool addallsols; /**< should all subproblem solutions be added to the original SCIP? */ 131 SCIP_Bool fullscale; /**< should the RENS sub-CIP be solved with full-scale SCIP settings, 132 * including techniques that merely work on the dual bound, e.g., cuts? 133 * This is only implemented for testing and not recommended to be used! */ 134 int bestsollimit; /**< limit on number of improving incumbent solutions in sub-CIP */ 135 SCIP_Bool useuct; /**< should uct node selection be used at the beginning of the search? */ 136 }; 137 138 139 /* 140 * Local methods 141 */ 142 143 /** compute the number of initial fixings and check whether the fixing rate exceeds the minimum fixing rate */ 144 static 145 SCIP_RETCODE computeFixingrate( 146 SCIP* scip, /**< SCIP data structure */ 147 SCIP_VAR** fixedvars, /**< array to store source SCIP variables whose copies should be fixed in the sub-SCIP */ 148 SCIP_Real* fixedvals, /**< array to store solution values for variable fixing */ 149 int* nfixedvars, /**< pointer to store the number of fixed variables */ 150 int fixedvarssize, /**< size of the arrays to store fixing variables */ 151 SCIP_Real minfixingrate, /**< percentage of integer variables that have to be fixed */ 152 char* startsol, /**< pointer to solution used for fixing values ('l'p relaxation, 'n'lp relaxation) */ 153 SCIP_Real* fixingrate, /**< percentage of integers that get actually fixed */ 154 SCIP_Bool* success /**< pointer to store whether minimum fixingrate is exceeded */ 155 ) 156 { 157 SCIP_VAR** vars; 158 int nintvars; 159 int nbinvars; 160 int i; 161 162 assert(fixedvars != NULL); 163 assert(fixedvals != NULL); 164 assert(nfixedvars != NULL); 165 166 *fixingrate = 1.0; 167 *success = FALSE; 168 169 /* if there is no NLP relaxation available (e.g., because the presolved problem is linear), use LP relaxation */ 170 if( !SCIPisNLPConstructed(scip) ) 171 { 172 SCIPdebugMsg(scip, "no NLP present, use LP relaxation instead\n"); 173 (*startsol) = 'l'; 174 } 175 176 /* get required variable data */ 177 SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) ); 178 assert(fixedvarssize >= nbinvars + nintvars); 179 (*nfixedvars) = 0; 180 181 /* try to solve NLP relaxation */ 182 if( (*startsol) == 'n' ) 183 { 184 SCIP_NLPSOLSTAT stat; 185 186 /* only call this function if NLP relaxation is available */ 187 assert(SCIPisNLPConstructed(scip)); 188 189 SCIPdebugMsg(scip, "try to solve NLP relaxation to obtain fixing values\n"); 190 191 /* set starting point to LP solution */ 192 SCIP_CALL( SCIPsetNLPInitialGuessSol(scip, NULL) ); 193 194 /* solve NLP relaxation 195 * TODO pick some less arbitrary iterlimit 196 */ 197 SCIP_CALL( SCIPsolveNLP(scip, .iterlimit = 3000) ); /*lint !e666*/ 198 199 /* get solution status of NLP solver */ 200 stat = SCIPgetNLPSolstat(scip); 201 *success = (stat == SCIP_NLPSOLSTAT_GLOBOPT) || (stat == SCIP_NLPSOLSTAT_LOCOPT) || stat == (SCIP_NLPSOLSTAT_FEASIBLE); 202 SCIPdebugMsg(scip, "solving NLP relaxation was %s successful (stat=%d)\n", *success ? "" : "not", stat); 203 204 /* it the NLP was not successfully solved we stop the heuristic right away */ 205 if( !(*success) ) 206 return SCIP_OKAY; 207 } 208 else 209 { 210 assert(*startsol == 'l'); 211 } 212 213 /* count the number of variables with integral solution values in the current NLP or LP solution */ 214 for( i = 0; i < nbinvars + nintvars; ++i ) 215 { 216 SCIP_Real solval; 217 218 /* get solution value in the relaxation in question */ 219 solval = (*startsol == 'l') ? SCIPvarGetLPSol(vars[i]) : SCIPvarGetNLPSol(vars[i]); 220 221 /* append variable to the buffer storage for integer variables with integer solution values */ 222 if( SCIPisFeasIntegral(scip, solval) ) 223 { 224 /* fix variables to current LP/NLP solution if it is integral, 225 * use exact integral value, if the variable is only integral within numerical tolerances 226 */ 227 solval = SCIPfloor(scip, solval+0.5); 228 fixedvars[(*nfixedvars)] = vars[i]; 229 fixedvals[(*nfixedvars)] = solval; 230 (*nfixedvars)++; 231 } 232 } 233 234 /* abort, if all integer variables were fixed (which should not happen for MIP), 235 * but frequently happens for MINLPs using an LP relaxation 236 */ 237 if( (*nfixedvars) == nbinvars + nintvars ) 238 return SCIP_OKAY; 239 240 *fixingrate = (*nfixedvars) / (SCIP_Real)(MAX(nbinvars + nintvars, 1)); 241 242 /* abort, if the amount of fixed variables is insufficient */ 243 if( *fixingrate < minfixingrate ) 244 return SCIP_OKAY; 245 246 *success = TRUE; 247 return SCIP_OKAY; 248 } 249 250 /** fixes bounds of unfixed integer variables to binary bounds */ 251 static 252 SCIP_RETCODE restrictToBinaryBounds( 253 SCIP* scip, /**< original SCIP data structure */ 254 SCIP* subscip, /**< SCIP data structure for the subproblem */ 255 SCIP_VAR** subvars, /**< the variables of the subproblem */ 256 char startsol /**< solution used for fixing values ('l'p relaxation, 'n'lp relaxation) */ 257 ) 258 { 259 SCIP_VAR** vars; /* original SCIP variables */ 260 261 int nbinvars; 262 int nintvars; 263 int i; 264 265 assert(scip != NULL); 266 assert(subscip != NULL); 267 assert(subvars != NULL); 268 269 assert(startsol == 'l' || startsol == 'n'); 270 271 /* get required variable data */ 272 SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) ); 273 274 /* change bounds of integer variables of the subproblem */ 275 for( i = nbinvars; i < nbinvars + nintvars; i++ ) 276 { 277 SCIP_Real solval; 278 SCIP_Real lb; 279 SCIP_Real ub; 280 281 if( subvars[i] == NULL ) 282 continue; 283 284 /* get the current LP/NLP solution for each variable */ 285 if( startsol == 'l') 286 solval = SCIPvarGetLPSol(vars[i]); 287 else 288 solval = SCIPvarGetNLPSol(vars[i]); 289 290 /* restrict bounds to nearest integers if the solution value is not already integer */ 291 if( !SCIPisFeasIntegral(scip, solval) ) 292 { 293 lb = SCIPfeasFloor(scip, solval); 294 ub = SCIPfeasCeil(scip, solval); 295 296 /* perform the bound change */ 297 SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], lb) ); 298 SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], ub) ); 299 } 300 else 301 { 302 /* the variable bounds should be already fixed to this solution value */ 303 assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(subvars[i]), SCIPfloor(scip, solval+0.5))); 304 assert(SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(subvars[i]), SCIPfloor(scip, solval+0.5))); 305 } 306 } 307 308 return SCIP_OKAY; 309 } 310 311 312 /* ---------------- Callback methods of event handler ---------------- */ 313 314 /* exec the event handler 315 * 316 * we interrupt the solution process 317 */ 318 static 319 SCIP_DECL_EVENTEXEC(eventExecRens) 320 { 321 SCIP_HEURDATA* heurdata; 322 323 assert(eventhdlr != NULL); 324 assert(eventdata != NULL); 325 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 326 assert(event != NULL); 327 assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED); 328 329 heurdata = (SCIP_HEURDATA*)eventdata; 330 assert(heurdata != NULL); 331 332 /* interrupt solution process of sub-SCIP */ 333 if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit ) 334 { 335 SCIPdebugMsg(scip, "interrupt after %" SCIP_LONGINT_FORMAT " LPs\n",SCIPgetNLPs(scip)); 336 SCIP_CALL( SCIPinterruptSolve(scip) ); 337 } 338 339 return SCIP_OKAY; 340 } 341 342 /** setup and solve the RENS sub-SCIP */ 343 static 344 SCIP_RETCODE setupAndSolveSubscip( 345 SCIP* scip, /**< SCIP data structure */ 346 SCIP* subscip, /**< sub SCIP data structure */ 347 SCIP_RESULT* result, /**< result pointer */ 348 SCIP_HEUR* heur, /**< heuristic data structure */ 349 SCIP_VAR** fixedvars, /**< array of variables that should be fixed */ 350 SCIP_Real* fixedvals, /**< array of fixing values */ 351 int nfixedvars, /**< number of variables that should be fixed */ 352 SCIP_Real intfixingrate, /**< percentage of integer variables fixed */ 353 SCIP_Real minfixingrate, /**< minimum percentage of integer variables that have to be fixed */ 354 SCIP_Real minimprove, /**< factor by which RENS should at least improve the incumbent */ 355 SCIP_Longint maxnodes, /**< maximum number of nodes for the subproblem */ 356 SCIP_Longint nstallnodes, /**< number of stalling nodes for the subproblem */ 357 char startsol, /**< solution used for fixing values ('l'p relaxation, 'n'lp relaxation) */ 358 SCIP_Bool binarybounds, /**< should general integers get binary bounds [floor(.),ceil(.)]? */ 359 SCIP_Bool uselprows /**< should subproblem be created out of the rows in the LP rows? */ 360 ) 361 { 362 SCIP_VAR** vars; /* original problem's variables */ 363 SCIP_VAR** subvars; /* subproblem's variables */ 364 SCIP_HEURDATA* heurdata; /* heuristic data */ 365 SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */ 366 SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */ 367 SCIP_Real cutoff; /* objective cutoff for the subproblem */ 368 SCIP_Real allfixingrate; /* percentage of all variables fixed */ 369 SCIP_Bool success; 370 int i; 371 int nvars; /* number of original problem's variables */ 372 SCIP_RETCODE retcode; 373 374 assert(scip != NULL); 375 assert(subscip != NULL); 376 assert(heur != NULL); 377 assert(result != NULL); 378 379 heurdata = SCIPheurGetData(heur); 380 assert(heurdata != NULL); 381 382 /* get variable data */ 383 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 384 385 /* create the variable mapping hash map */ 386 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) ); 387 388 /* create a problem copy as sub SCIP */ 389 SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "rens", fixedvars, fixedvals, nfixedvars, uselprows, 390 heurdata->copycuts, &success, NULL) ); 391 392 eventhdlr = NULL; 393 /* create event handler for LP events */ 394 SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecRens, NULL) ); 395 if( eventhdlr == NULL ) 396 { 397 SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n"); 398 return SCIP_PLUGINNOTFOUND; 399 } 400 401 /* copy subproblem variables into the same order as the source SCIP variables */ 402 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) ); 403 for( i = 0; i < nvars; i++ ) 404 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]); 405 406 /* free hash map */ 407 SCIPhashmapFree(&varmapfw); 408 409 /* restrict the integer variables to binary bounds */ 410 if( binarybounds ) 411 { 412 SCIP_CALL( restrictToBinaryBounds(scip, subscip, subvars, startsol) ); 413 } 414 415 SCIPdebugMsg(scip, "RENS subproblem: %d vars, %d cons\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip)); 416 417 /* do not abort subproblem on CTRL-C */ 418 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) ); 419 420 #ifdef SCIP_DEBUG 421 /* for debugging, enable full output */ 422 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) ); 423 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) ); 424 #else 425 /* disable statistic timing inside sub SCIP and output to console */ 426 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) ); 427 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) ); 428 #endif 429 430 /* set limits for the subproblem */ 431 SCIP_CALL( SCIPcopyLimits(scip, subscip) ); 432 heurdata->nodelimit = maxnodes; 433 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) ); 434 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", maxnodes) ); 435 SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsollimit) ); 436 437 /* forbid recursive call of heuristics and separators solving sub-SCIPs */ 438 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) ); 439 440 /* disable expensive techniques that merely work on the dual bound */ 441 if( !heurdata->fullscale ) 442 { 443 /* disable cutting plane separation */ 444 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) ); 445 446 /* disable expensive presolving */ 447 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) ); 448 449 /* use best estimate node selection */ 450 if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") ) 451 { 452 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) ); 453 } 454 455 /* activate uct node selection at the top of the tree */ 456 if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") ) 457 { 458 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) ); 459 } 460 461 /* use inference branching */ 462 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") ) 463 { 464 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) ); 465 } 466 467 /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */ 468 if( !SCIPisParamFixed(subscip, "conflict/enable") ) 469 { 470 SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) ); 471 } 472 if( !SCIPisParamFixed(subscip, "conflict/useboundlp") ) 473 { 474 SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') ); 475 } 476 if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") ) 477 { 478 SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) ); 479 } 480 481 /* speed up sub-SCIP by not checking dual LP feasibility */ 482 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) ); 483 } 484 485 /* if there is already a solution, add an objective cutoff */ 486 if( SCIPgetNSols(scip) > 0 ) 487 { 488 SCIP_Real upperbound; 489 assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) ); 490 491 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip); 492 493 if( !SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) ) 494 { 495 cutoff = (1 - minimprove) * SCIPgetUpperbound(scip) 496 + minimprove * SCIPgetLowerbound(scip); 497 } 498 else 499 { 500 if( SCIPgetUpperbound(scip) >= 0 ) 501 cutoff = (1 - minimprove) * SCIPgetUpperbound(scip); 502 else 503 cutoff = (1 + minimprove) * SCIPgetUpperbound(scip); 504 } 505 cutoff = MIN(upperbound, cutoff); 506 SCIP_CALL(SCIPsetObjlimit(subscip, cutoff)); 507 } 508 509 /* presolve the subproblem */ 510 retcode = SCIPpresolve(subscip); 511 512 /* errors in solving the subproblem should not kill the overall solving process; 513 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 514 */ 515 if( retcode != SCIP_OKAY ) 516 { 517 SCIPwarningMessage(scip, "Error while presolving subproblem in RENS heuristic; sub-SCIP terminated with code <%d>\n", retcode); 518 SCIPABORT(); /*lint --e{527}*/ 519 goto TERMINATE; 520 } 521 522 SCIPdebugMsg(scip, "RENS presolved subproblem: %d vars, %d cons, success=%u\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip), success); 523 524 allfixingrate = (SCIPgetNOrigVars(subscip) - SCIPgetNVars(subscip)) / (SCIP_Real)SCIPgetNOrigVars(subscip); 525 526 /* additional variables added in presolving may lead to the subSCIP having more variables than the original */ 527 allfixingrate = MAX(allfixingrate, 0.0); 528 529 /* after presolving, we should have at least reached a certain fixing rate over ALL variables (including continuous) 530 * to ensure that not only the MIP but also the LP relaxation is easy enough 531 */ 532 if( allfixingrate >= minfixingrate / 2.0 ) 533 { 534 SCIP_SOL** subsols; 535 int nsubsols; 536 537 /* catch LP events of sub-SCIP */ 538 assert(eventhdlr != NULL); 539 SCIP_CALL( SCIPtransformProb(subscip) ); 540 SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) ); 541 542 /* solve the subproblem */ 543 SCIPdebugMsg(scip, "solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT ", maxnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, maxnodes); 544 retcode = SCIPsolve(subscip); 545 546 /* drop LP events of sub-SCIP */ 547 SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) ); 548 549 /* errors in solving the subproblem should not kill the overall solving process; 550 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 551 */ 552 if( retcode != SCIP_OKAY ) 553 { 554 SCIPwarningMessage(scip, "Error while solving subproblem in RENS heuristic; sub-SCIP terminated with code <%d>\n", retcode); 555 SCIPABORT(); 556 goto TERMINATE; 557 } 558 else 559 { 560 /* transfer variable statistics from sub-SCIP */ 561 SCIP_CALL( SCIPmergeVariableStatistics(subscip, scip, subvars, vars, nvars) ); 562 } 563 564 /* print solving statistics of subproblem if we are in SCIP's debug mode */ 565 SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) ); 566 567 /* check, whether a solution was found; 568 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted 569 */ 570 nsubsols = SCIPgetNSols(subscip); 571 subsols = SCIPgetSols(subscip); 572 success = FALSE; 573 for( i = 0; i < nsubsols && (!success || heurdata->addallsols); ++i ) 574 { 575 SCIP_SOL* newsol; 576 577 SCIP_CALL( SCIPtranslateSubSol(scip, subscip, subsols[i], heur, subvars, &newsol) ); 578 579 SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) ); 580 if( success ) 581 *result = SCIP_FOUNDSOL; 582 } 583 584 SCIPstatisticPrintf("RENS statistic: fixed %6.3f integer variables, %6.3f all variables, needed %6.1f seconds, %" SCIP_LONGINT_FORMAT " nodes, solution %10.4f found at node %" SCIP_LONGINT_FORMAT "\n", 585 intfixingrate, allfixingrate, SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip), success ? SCIPgetPrimalbound(scip) : SCIPinfinity(scip), 586 nsubsols > 0 ? SCIPsolGetNodenum(SCIPgetBestSol(subscip)) : -1 ); 587 } 588 else 589 { 590 SCIPstatisticPrintf("RENS statistic: fixed only %6.3f integer variables, %6.3f all variables --> abort \n", intfixingrate, allfixingrate); 591 } 592 593 TERMINATE: 594 /* free sub problem data */ 595 SCIPfreeBufferArray(scip, &subvars); 596 597 return SCIP_OKAY; 598 } 599 600 /* ---------------- external methods of RENS heuristic ---------------- */ 601 602 /** main procedure of the RENS heuristic, creates and solves a sub-SCIP */ 603 SCIP_RETCODE SCIPapplyRens( 604 SCIP* scip, /**< original SCIP data structure */ 605 SCIP_HEUR* heur, /**< heuristic data structure */ 606 SCIP_RESULT* result, /**< result data structure */ 607 SCIP_Real minfixingrate, /**< minimum percentage of integer variables that have to be fixed */ 608 SCIP_Real minimprove, /**< factor by which RENS should at least improve the incumbent */ 609 SCIP_Longint maxnodes, /**< maximum number of nodes for the subproblem */ 610 SCIP_Longint nstallnodes, /**< number of stalling nodes for the subproblem */ 611 char startsol, /**< solution used for fixing values ('l'p relaxation, 'n'lp relaxation) */ 612 SCIP_Bool binarybounds, /**< should general integers get binary bounds [floor(.),ceil(.)]? */ 613 SCIP_Bool uselprows /**< should subproblem be created out of the rows in the LP rows? */ 614 ) 615 { 616 SCIP* subscip; /* the subproblem created by RENS */ 617 618 SCIP_Real intfixingrate; /* percentage of integer variables fixed */ 619 620 SCIP_VAR** fixedvars; 621 SCIP_Real* fixedvals; 622 int nfixedvars; 623 int fixedvarssize; 624 int nbinvars; 625 int nintvars; 626 627 SCIP_Bool success; 628 SCIP_RETCODE retcode; 629 630 assert(scip != NULL); 631 assert(heur != NULL); 632 assert(result != NULL); 633 634 assert(maxnodes >= 0); 635 assert(nstallnodes >= 0); 636 637 assert(0.0 <= minfixingrate && minfixingrate <= 1.0); 638 assert(0.0 <= minimprove && minimprove <= 1.0); 639 assert(startsol == 'l' || startsol == 'n'); 640 641 *result = SCIP_DIDNOTRUN; 642 643 nbinvars = SCIPgetNBinVars(scip); 644 nintvars = SCIPgetNIntVars(scip); 645 646 /* allocate buffer storage to keep fixings for the variables in the sub SCIP */ 647 fixedvarssize = nbinvars + nintvars; 648 SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, fixedvarssize) ); 649 SCIP_CALL( SCIPallocBufferArray(scip, &fixedvals, fixedvarssize) ); 650 nfixedvars = 0; 651 652 /* compute the number of initial fixings and check if the fixing rate exceeds the minimum fixing rate */ 653 SCIP_CALL( computeFixingrate(scip, fixedvars, fixedvals, &nfixedvars, fixedvarssize, minfixingrate, &startsol, &intfixingrate, &success) ); 654 655 if( !success ) 656 { 657 SCIPstatisticPrintf("RENS statistic: fixed only %5.2f integer variables --> abort \n", intfixingrate); 658 goto TERMINATE; 659 } 660 661 /* check whether there is enough time and memory left */ 662 SCIP_CALL( SCIPcheckCopyLimits(scip, &success) ); 663 664 if( !success ) 665 goto TERMINATE; 666 667 *result = SCIP_DIDNOTFIND; 668 669 /* initialize the subproblem */ 670 SCIP_CALL( SCIPcreate(&subscip) ); 671 672 retcode = setupAndSolveSubscip(scip, subscip, result, heur, fixedvars, fixedvals, nfixedvars, intfixingrate, minfixingrate, minimprove, maxnodes, nstallnodes, startsol, binarybounds, uselprows); 673 674 SCIP_CALL( SCIPfree(&subscip) ); 675 676 SCIP_CALL( retcode ); 677 678 TERMINATE: 679 /* free buffer storage for variable fixings */ 680 SCIPfreeBufferArray(scip, &fixedvals); 681 SCIPfreeBufferArray(scip, &fixedvars); 682 683 return SCIP_OKAY; 684 } 685 686 687 /* 688 * Callback methods of primal heuristic 689 */ 690 691 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 692 static 693 SCIP_DECL_HEURCOPY(heurCopyRens) 694 { /*lint --e{715}*/ 695 assert(scip != NULL); 696 assert(heur != NULL); 697 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 698 699 /* call inclusion method of primal heuristic */ 700 SCIP_CALL( SCIPincludeHeurRens(scip) ); 701 702 return SCIP_OKAY; 703 } 704 705 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 706 static 707 SCIP_DECL_HEURFREE(heurFreeRens) 708 { /*lint --e{715}*/ 709 SCIP_HEURDATA* heurdata; 710 711 assert( heur != NULL ); 712 assert( scip != NULL ); 713 714 /* get heuristic data */ 715 heurdata = SCIPheurGetData(heur); 716 assert( heurdata != NULL ); 717 718 /* free heuristic data */ 719 SCIPfreeBlockMemory(scip, &heurdata); 720 SCIPheurSetData(heur, NULL); 721 722 return SCIP_OKAY; 723 } 724 725 /** initialization method of primal heuristic (called after problem was transformed) */ 726 static 727 SCIP_DECL_HEURINIT(heurInitRens) 728 { /*lint --e{715}*/ 729 SCIP_HEURDATA* heurdata; 730 731 assert( heur != NULL ); 732 assert( scip != NULL ); 733 734 /* get heuristic data */ 735 heurdata = SCIPheurGetData(heur); 736 assert( heurdata != NULL ); 737 738 /* initialize data */ 739 heurdata->usednodes = 0; 740 741 return SCIP_OKAY; 742 } 743 744 745 /** execution method of primal heuristic */ 746 static 747 SCIP_DECL_HEUREXEC(heurExecRens) 748 { /*lint --e{715}*/ 749 SCIP_HEURDATA* heurdata; /* heuristic's data */ 750 SCIP_Longint nstallnodes; /* number of stalling nodes for the subproblem */ 751 752 assert( heur != NULL ); 753 assert( scip != NULL ); 754 assert( result != NULL ); 755 assert( SCIPhasCurrentNodeLP(scip) ); 756 757 *result = SCIP_DELAYED; 758 759 /* do not call heuristic of node was already detected to be infeasible */ 760 if( nodeinfeasible ) 761 return SCIP_OKAY; 762 763 /* get heuristic data */ 764 heurdata = SCIPheurGetData(heur); 765 assert( heurdata != NULL ); 766 767 /* only call heuristic, if an optimal LP solution is at hand */ 768 if( heurdata->startsol == 'l' && SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 769 return SCIP_OKAY; 770 771 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */ 772 if( heurdata->startsol == 'l' && SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) ) 773 return SCIP_OKAY; 774 775 /* only continue with some fractional variables */ 776 if( heurdata->startsol == 'l' && SCIPgetNLPBranchCands(scip) == 0 ) 777 return SCIP_OKAY; 778 779 /* do not proceed, when we should use the NLP relaxation, but there is no NLP solver included in SCIP */ 780 if( heurdata->startsol == 'n' && SCIPgetNNlpis(scip) == 0 ) 781 return SCIP_OKAY; 782 783 *result = SCIP_DIDNOTRUN; 784 785 /* calculate the maximal number of branching nodes until heuristic is aborted */ 786 nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip)); 787 788 /* reward RENS if it succeeded often */ 789 nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0)); 790 nstallnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-SCIP as 100 nodes */ 791 nstallnodes += heurdata->nodesofs; 792 793 /* determine the node limit for the current process */ 794 nstallnodes -= heurdata->usednodes; 795 nstallnodes = MIN(nstallnodes, heurdata->maxnodes); 796 797 /* check whether we have enough nodes left to call subproblem solving */ 798 if( nstallnodes < heurdata->minnodes ) 799 { 800 SCIPdebugMsg(scip, "skipping RENS: nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->minnodes); 801 return SCIP_OKAY; 802 } 803 804 if( SCIPisStopped(scip) && !heurdata->extratime ) 805 return SCIP_OKAY; 806 807 SCIP_CALL( SCIPapplyRens(scip, heur, result, heurdata->minfixingrate, heurdata->minimprove, 808 heurdata->maxnodes, nstallnodes, heurdata->startsol, heurdata->binarybounds, heurdata->uselprows) ); 809 810 return SCIP_OKAY; 811 } 812 813 814 /* 815 * primal heuristic specific interface methods 816 */ 817 818 /** creates the rens primal heuristic and includes it in SCIP */ 819 SCIP_RETCODE SCIPincludeHeurRens( 820 SCIP* scip /**< SCIP data structure */ 821 ) 822 { 823 SCIP_HEURDATA* heurdata; 824 SCIP_HEUR* heur; 825 826 /* create Rens primal heuristic data */ 827 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 828 829 /* include primal heuristic */ 830 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 831 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 832 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecRens, heurdata) ); 833 834 assert(heur != NULL); 835 836 /* set non-NULL pointers to callback methods */ 837 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyRens) ); 838 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeRens) ); 839 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitRens) ); 840 841 /* add rens primal heuristic parameters */ 842 843 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate", 844 "minimum percentage of integer variables that have to be fixable", 845 &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) ); 846 847 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes", 848 "maximum number of nodes to regard in the subproblem", 849 &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 850 851 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs", 852 "number of nodes added to the contingent of the total nodes", 853 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 854 855 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes", 856 "minimum number of nodes required to start the subproblem", 857 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 858 859 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot", 860 "contingent of sub problem nodes in relation to the number of nodes of the original problem", 861 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) ); 862 863 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove", 864 "factor by which RENS should at least improve the incumbent", 865 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) ); 866 867 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac", 868 "factor by which the limit on the number of LP depends on the node limit", 869 &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) ); 870 871 SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/startsol", 872 "solution that is used for fixing values ('l'p relaxation, 'n'lp relaxation)", 873 &heurdata->startsol, FALSE, DEFAULT_STARTSOL, STARTSOL_CHOICES, NULL, NULL) ); 874 875 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/binarybounds", 876 "should general integers get binary bounds [floor(.),ceil(.)] ?", 877 &heurdata->binarybounds, TRUE, DEFAULT_BINARYBOUNDS, NULL, NULL) ); 878 879 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows", 880 "should subproblem be created out of the rows in the LP rows?", 881 &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) ); 882 883 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts", 884 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?", 885 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) ); 886 887 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/extratime", 888 "should the RENS sub-CIP get its own full time limit? This is only for testing and not recommended!", 889 &heurdata->extratime, TRUE, DEFAULT_EXTRATIME, NULL, NULL) ); 890 891 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/addallsols", 892 "should all subproblem solutions be added to the original SCIP?", 893 &heurdata->addallsols, TRUE, DEFAULT_ADDALLSOLS, NULL, NULL) ); 894 895 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/fullscale", 896 "should the RENS sub-CIP be solved with cuts, conflicts, strong branching,... This is only for testing and not recommended!", 897 &heurdata->fullscale, TRUE, DEFAULT_FULLSCALE, NULL, NULL) ); 898 899 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/bestsollimit", 900 "limit on number of improving incumbent solutions in sub-CIP", 901 &heurdata->bestsollimit, FALSE, DEFAULT_BESTSOLLIMIT, -1, INT_MAX, NULL, NULL) ); 902 903 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct", 904 "should uct node selection be used at the beginning of the search?", 905 &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) ); 906 907 return SCIP_OKAY; 908 } 909