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_rootsoldiving.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief LP diving heuristic that changes variable's objective values using root LP solution as guide 28 * @author Kati Wolter 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "blockmemshell/memory.h" 34 #include "scip/heur_rootsoldiving.h" 35 #include "scip/pub_heur.h" 36 #include "scip/pub_message.h" 37 #include "scip/pub_var.h" 38 #include "scip/scip_branch.h" 39 #include "scip/scip_general.h" 40 #include "scip/scip_heur.h" 41 #include "scip/scip_lp.h" 42 #include "scip/scip_mem.h" 43 #include "scip/scip_message.h" 44 #include "scip/scip_numerics.h" 45 #include "scip/scip_param.h" 46 #include "scip/scip_prob.h" 47 #include "scip/scip_sol.h" 48 #include "scip/scip_solvingstats.h" 49 #include "scip/scip_tree.h" 50 #include <string.h> 51 52 #define HEUR_NAME "rootsoldiving" 53 #define HEUR_DESC "LP diving heuristic that changes variable's objective values using root LP solution as guide" 54 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_OBJDIVING 55 #define HEUR_PRIORITY -1005000 56 #define HEUR_FREQ 20 57 #define HEUR_FREQOFS 5 58 #define HEUR_MAXDEPTH -1 59 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE 60 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */ 61 62 63 /* 64 * Default parameter settings 65 */ 66 67 #define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */ 68 #define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */ 69 #define DEFAULT_MAXLPITERQUOT 0.01 /**< maximal fraction of diving LP iterations compared to node LP iterations */ 70 #define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */ 71 #define DEFAULT_MAXSOLS -1 /**< total number of feasible solutions found up to which heuristic is called 72 * (-1: no limit) */ 73 #define DEFAULT_DEPTHFAC 0.5 /**< maximal diving depth: number of binary/integer variables times depthfac */ 74 #define DEFAULT_DEPTHFACNOSOL 2.0 /**< maximal diving depth factor if no feasible solution was found yet */ 75 76 #define MINLPITER 10000 /**< minimal number of LP iterations allowed in each LP solving call */ 77 #define DEFAULT_ALPHA 0.9 /**< soft rounding factor to fade out objective coefficients */ 78 79 80 /* locally defined heuristic data */ 81 struct SCIP_HeurData 82 { 83 SCIP_SOL* sol; /**< working solution */ 84 SCIP_Real minreldepth; /**< minimal relative depth to start diving */ 85 SCIP_Real maxreldepth; /**< maximal relative depth to start diving */ 86 SCIP_Real maxlpiterquot; /**< maximal fraction of diving LP iterations compared to node LP iterations */ 87 int maxlpiterofs; /**< additional number of allowed LP iterations */ 88 int maxsols; /**< total number of feasible solutions found up to which heuristic is called 89 * (-1: no limit) */ 90 SCIP_Real depthfac; /**< maximal diving depth: number of binary/integer variables times depthfac */ 91 SCIP_Real depthfacnosol; /**< maximal diving depth factor if no feasible solution was found yet */ 92 SCIP_Real alpha; /**< soft rounding factor to fade out objective coefficients */ 93 SCIP_Longint nlpiterations; /**< LP iterations used in this heuristic */ 94 int nsuccess; /**< number of runs that produced at least one feasible solution */ 95 }; 96 97 98 /* 99 * Callback methods 100 */ 101 102 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 103 static 104 SCIP_DECL_HEURCOPY(heurCopyRootsoldiving) 105 { /*lint --e{715}*/ 106 assert(scip != NULL); 107 assert(heur != NULL); 108 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 109 110 /* call inclusion method of primal heuristic */ 111 SCIP_CALL( SCIPincludeHeurRootsoldiving(scip) ); 112 113 return SCIP_OKAY; 114 } 115 116 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 117 static 118 SCIP_DECL_HEURFREE(heurFreeRootsoldiving) /*lint --e{715}*/ 119 { /*lint --e{715}*/ 120 SCIP_HEURDATA* heurdata; 121 122 assert(heur != NULL); 123 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 124 assert(scip != NULL); 125 126 /* free heuristic data */ 127 heurdata = SCIPheurGetData(heur); 128 assert(heurdata != NULL); 129 SCIPfreeBlockMemory(scip, &heurdata); 130 SCIPheurSetData(heur, NULL); 131 132 return SCIP_OKAY; 133 } 134 135 136 /** initialization method of primal heuristic (called after problem was transformed) */ 137 static 138 SCIP_DECL_HEURINIT(heurInitRootsoldiving) /*lint --e{715}*/ 139 { /*lint --e{715}*/ 140 SCIP_HEURDATA* heurdata; 141 142 assert(heur != NULL); 143 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 144 145 /* get heuristic data */ 146 heurdata = SCIPheurGetData(heur); 147 assert(heurdata != NULL); 148 149 /* create working solution */ 150 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) ); 151 152 /* initialize data */ 153 heurdata->nlpiterations = 0; 154 heurdata->nsuccess = 0; 155 156 return SCIP_OKAY; 157 } 158 159 160 /** deinitialization method of primal heuristic (called before transformed problem is freed) */ 161 static 162 SCIP_DECL_HEUREXIT(heurExitRootsoldiving) /*lint --e{715}*/ 163 { /*lint --e{715}*/ 164 SCIP_HEURDATA* heurdata; 165 166 assert(heur != NULL); 167 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 168 169 /* get heuristic data */ 170 heurdata = SCIPheurGetData(heur); 171 assert(heurdata != NULL); 172 173 /* free working solution */ 174 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) ); 175 176 return SCIP_OKAY; 177 } 178 179 180 /** execution method of primal heuristic */ 181 static 182 SCIP_DECL_HEUREXEC(heurExecRootsoldiving) /*lint --e{715}*/ 183 { /*lint --e{715}*/ 184 SCIP_HEURDATA* heurdata; 185 SCIP_VAR** vars; 186 SCIP_Real* rootsol; 187 SCIP_Real* objchgvals; 188 int* softroundings; 189 int* intvalrounds; 190 int nvars; 191 int nbinvars; 192 int nintvars; 193 int nlpcands; 194 SCIP_LPSOLSTAT lpsolstat; 195 SCIP_Real absstartobjval; 196 SCIP_Real objstep; 197 SCIP_Real alpha; 198 SCIP_Real oldobj; 199 SCIP_Real newobj; 200 SCIP_Bool lperror; 201 SCIP_Bool lpsolchanged; 202 SCIP_Longint nsolsfound; 203 SCIP_Longint ncalls; 204 SCIP_Longint nlpiterations; 205 SCIP_Longint maxnlpiterations; 206 int depth; 207 int maxdepth; 208 int maxdivedepth; 209 int divedepth; 210 int startnlpcands; 211 int ncycles; 212 int i; 213 214 assert(heur != NULL); 215 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 216 assert(scip != NULL); 217 assert(result != NULL); 218 assert(SCIPhasCurrentNodeLP(scip)); 219 220 *result = SCIP_DELAYED; 221 222 /* do not call heuristic of node was already detected to be infeasible */ 223 if( nodeinfeasible ) 224 return SCIP_OKAY; 225 226 /* only call heuristic, if an optimal LP solution is at hand */ 227 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 228 return SCIP_OKAY; 229 230 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */ 231 if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) ) 232 return SCIP_OKAY; 233 234 /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */ 235 if( !SCIPisLPSolBasic(scip) ) 236 return SCIP_OKAY; 237 238 /* don't dive two times at the same node */ 239 if( SCIPgetLastDivenode(scip) == SCIPgetNNodes(scip) && SCIPgetDepth(scip) > 0 ) 240 return SCIP_OKAY; 241 242 *result = SCIP_DIDNOTRUN; 243 244 /* get heuristic's data */ 245 heurdata = SCIPheurGetData(heur); 246 assert(heurdata != NULL); 247 248 /* only apply heuristic, if only a few solutions have been found */ 249 if( heurdata->maxsols >= 0 && SCIPgetNSolsFound(scip) >= heurdata->maxsols ) 250 return SCIP_OKAY; 251 252 /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */ 253 depth = SCIPgetDepth(scip); 254 maxdepth = SCIPgetMaxDepth(scip); 255 maxdepth = MAX(maxdepth, 30); 256 if( depth < heurdata->minreldepth*maxdepth || depth > heurdata->maxreldepth*maxdepth ) 257 return SCIP_OKAY; 258 259 /* calculate the maximal number of LP iterations until heuristic is aborted */ 260 nlpiterations = SCIPgetNNodeLPIterations(scip); 261 ncalls = SCIPheurGetNCalls(heur); 262 nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + heurdata->nsuccess; 263 maxnlpiterations = (SCIP_Longint)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxlpiterquot * nlpiterations); 264 maxnlpiterations += heurdata->maxlpiterofs; 265 266 /* don't try to dive, if we took too many LP iterations during diving */ 267 if( heurdata->nlpiterations >= maxnlpiterations ) 268 return SCIP_OKAY; 269 270 /* allow at least a certain number of LP iterations in this dive */ 271 maxnlpiterations = MAX(maxnlpiterations, heurdata->nlpiterations + MINLPITER); 272 273 /* get number of fractional variables, that should be integral */ 274 nlpcands = SCIPgetNLPBranchCands(scip); 275 276 /* don't try to dive, if there are no fractional variables */ 277 if( nlpcands == 0 ) 278 return SCIP_OKAY; 279 280 /* calculate the maximal diving depth */ 281 nvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip); 282 if( SCIPgetNSolsFound(scip) == 0 ) 283 maxdivedepth = (int)(heurdata->depthfacnosol * nvars); 284 else 285 maxdivedepth = (int)(heurdata->depthfac * nvars); 286 maxdivedepth = MAX(maxdivedepth, 10); 287 288 *result = SCIP_DIDNOTFIND; 289 290 /* get all variables of LP */ 291 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) ); 292 293 /* get root solution value of all binary and integer variables */ 294 SCIP_CALL( SCIPallocBufferArray(scip, &rootsol, nbinvars + nintvars) ); 295 for( i = 0; i < nbinvars + nintvars; i++ ) 296 rootsol[i] = SCIPvarGetRootSol(vars[i]); 297 298 /* get current LP objective value, and calculate length of a single step in an objective coefficient */ 299 absstartobjval = SCIPgetLPObjval(scip); 300 absstartobjval = ABS(absstartobjval); 301 absstartobjval = MAX(absstartobjval, 1.0); 302 objstep = absstartobjval / 10.0; 303 304 /* initialize array storing the preferred soft rounding directions and counting the integral value rounds */ 305 SCIP_CALL( SCIPallocBufferArray(scip, &softroundings, nbinvars + nintvars) ); 306 BMSclearMemoryArray(softroundings, nbinvars + nintvars); 307 SCIP_CALL( SCIPallocBufferArray(scip, &intvalrounds, nbinvars + nintvars) ); 308 BMSclearMemoryArray(intvalrounds, nbinvars + nintvars); 309 310 /* allocate temporary memory for buffering objective changes */ 311 SCIP_CALL( SCIPallocBufferArray(scip, &objchgvals, nbinvars + nintvars) ); 312 313 /* start diving */ 314 SCIP_CALL( SCIPstartDive(scip) ); 315 316 SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing rootsoldiving heuristic: depth=%d, %d fractionals, dualbound=%g, maxnlpiterations=%" SCIP_LONGINT_FORMAT ", maxdivedepth=%d, LPobj=%g, objstep=%g\n", 317 SCIPgetNNodes(scip), SCIPgetDepth(scip), nlpcands, SCIPgetDualbound(scip), maxnlpiterations, maxdivedepth, 318 SCIPgetLPObjval(scip), objstep); 319 320 lperror = FALSE; 321 divedepth = 0; 322 lpsolstat = SCIP_LPSOLSTAT_OPTIMAL; 323 alpha = heurdata->alpha; 324 ncycles = 0; 325 lpsolchanged = TRUE; 326 startnlpcands = nlpcands; 327 while( !lperror && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL && nlpcands > 0 && ncycles < 10 328 && (divedepth < 10 329 || nlpcands <= startnlpcands - divedepth/2 330 || (divedepth < maxdivedepth && heurdata->nlpiterations < maxnlpiterations)) 331 && !SCIPisStopped(scip) ) 332 { 333 SCIP_Bool success; 334 int hardroundingidx; 335 int hardroundingdir; 336 SCIP_Real hardroundingoldbd; 337 SCIP_Real hardroundingnewbd; 338 SCIP_Bool boundschanged; 339 340 SCIP_RETCODE retcode; 341 342 /* create solution from diving LP and try to round it */ 343 SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) ); 344 SCIP_CALL( SCIProundSol(scip, heurdata->sol, &success) ); 345 346 if( success ) 347 { 348 SCIPdebugMsg(scip, "rootsoldiving found roundable primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol)); 349 350 /* try to add solution to SCIP */ 351 SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) ); 352 353 /* check, if solution was feasible and good enough */ 354 if( success ) 355 { 356 SCIPdebugMsg(scip, " -> solution was feasible and good enough\n"); 357 *result = SCIP_FOUNDSOL; 358 } 359 } 360 361 divedepth++; 362 hardroundingidx = -1; 363 hardroundingdir = 0; 364 hardroundingoldbd = 0.0; 365 hardroundingnewbd = 0.0; 366 boundschanged = FALSE; 367 368 SCIPdebugMsg(scip, "dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ":\n", divedepth, maxdivedepth, heurdata->nlpiterations, maxnlpiterations); 369 370 /* round solution x* from diving LP: 371 * - x~_j = down(x*_j) if x*_j is integer or binary variable and x*_j <= root solution_j 372 * - x~_j = up(x*_j) if x*_j is integer or binary variable and x*_j > root solution_j 373 * - x~_j = x*_j if x*_j is continuous variable 374 * change objective function in diving LP: 375 * - if x*_j is integral, or j is a continuous variable, set obj'_j = alpha * obj_j 376 * - otherwise, set obj'_j = alpha * obj_j + sign(x*_j - x~_j) 377 */ 378 for( i = 0; i < nbinvars + nintvars; i++ ) 379 { 380 SCIP_VAR* var; 381 SCIP_Real solval; 382 383 var = vars[i]; 384 oldobj = SCIPgetVarObjDive(scip, var); 385 newobj = oldobj; 386 387 solval = SCIPvarGetLPSol(var); 388 if( SCIPisFeasIntegral(scip, solval) ) 389 { 390 /* if the variable became integral after a soft rounding, count the rounds; after a while, fix it to its 391 * current integral value; 392 * otherwise, fade out the objective value 393 */ 394 if( softroundings[i] != 0 && lpsolchanged ) 395 { 396 intvalrounds[i]++; 397 if( intvalrounds[i] == 5 && SCIPgetVarLbDive(scip, var) < SCIPgetVarUbDive(scip, var) - 0.5 ) 398 { 399 /* use exact integral value, if the variable is only integral within numerical tolerances */ 400 solval = SCIPfloor(scip, solval+0.5); 401 SCIPdebugMsg(scip, " -> fixing <%s> = %g\n", SCIPvarGetName(var), solval); 402 SCIP_CALL( SCIPchgVarLbDive(scip, var, solval) ); 403 SCIP_CALL( SCIPchgVarUbDive(scip, var, solval) ); 404 boundschanged = TRUE; 405 } 406 } 407 else 408 newobj = alpha * oldobj; 409 } 410 else if( solval <= rootsol[i] ) 411 { 412 /* if the variable was soft rounded most of the time downwards, round it downwards by changing the bounds; 413 * otherwise, apply soft rounding by changing the objective value 414 */ 415 softroundings[i]--; 416 if( softroundings[i] <= -10 && hardroundingidx == -1 ) 417 { 418 SCIPdebugMsg(scip, " -> hard rounding <%s>[%g] <= %g\n", 419 SCIPvarGetName(var), solval, SCIPfeasFloor(scip, solval)); 420 hardroundingidx = i; 421 hardroundingdir = -1; 422 hardroundingoldbd = SCIPgetVarUbDive(scip, var); 423 hardroundingnewbd = SCIPfeasFloor(scip, solval); 424 SCIP_CALL( SCIPchgVarUbDive(scip, var, hardroundingnewbd) ); 425 boundschanged = TRUE; 426 } 427 else 428 newobj = alpha * oldobj + objstep; 429 } 430 else 431 { 432 /* if the variable was soft rounded most of the time upwards, round it upwards by changing the bounds; 433 * otherwise, apply soft rounding by changing the objective value 434 */ 435 softroundings[i]++; 436 if( softroundings[i] >= +10 && hardroundingidx == -1 ) 437 { 438 SCIPdebugMsg(scip, " -> hard rounding <%s>[%g] >= %g\n", 439 SCIPvarGetName(var), solval, SCIPfeasCeil(scip, solval)); 440 hardroundingidx = i; 441 hardroundingdir = +1; 442 hardroundingoldbd = SCIPgetVarLbDive(scip, var); 443 hardroundingnewbd = SCIPfeasCeil(scip, solval); 444 SCIP_CALL( SCIPchgVarLbDive(scip, var, hardroundingnewbd) ); 445 boundschanged = TRUE; 446 } 447 else 448 newobj = alpha * oldobj - objstep; 449 } 450 451 /* remember the objective change */ 452 objchgvals[i] = newobj; 453 } 454 455 /* apply objective changes if there was no bound change */ 456 if( !boundschanged ) 457 { 458 /* apply cached changes on integer variables */ 459 for( i = 0; i < nbinvars + nintvars; ++i ) 460 { 461 SCIP_VAR* var; 462 463 var = vars[i]; 464 SCIPdebugMsg(scip, " -> i=%d var <%s>, solval=%g, rootsol=%g, oldobj=%g, newobj=%g\n", 465 i, SCIPvarGetName(var), SCIPvarGetLPSol(var), rootsol[i], SCIPgetVarObjDive(scip, var), objchgvals[i]); 466 467 SCIP_CALL( SCIPchgVarObjDive(scip, var, objchgvals[i]) ); 468 } 469 470 /* fade out the objective values of the continuous variables */ 471 for( i = nbinvars + nintvars; i < nvars; i++ ) 472 { 473 SCIP_VAR* var; 474 475 var = vars[i]; 476 oldobj = SCIPgetVarObjDive(scip, var); 477 newobj = alpha * oldobj; 478 479 SCIPdebugMsg(scip, " -> i=%d var <%s>, solval=%g, oldobj=%g, newobj=%g\n", 480 i, SCIPvarGetName(var), SCIPvarGetLPSol(var), oldobj, newobj); 481 482 SCIP_CALL( SCIPchgVarObjDive(scip, var, newobj) ); 483 } 484 } 485 486 SOLVEAGAIN: 487 /* resolve the diving LP */ 488 nlpiterations = SCIPgetNLPIterations(scip); 489 490 retcode = SCIPsolveDiveLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, NULL); 491 lpsolstat = SCIPgetLPSolstat(scip); 492 493 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic. 494 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 495 */ 496 if( retcode != SCIP_OKAY ) 497 { 498 #ifndef NDEBUG 499 if( lpsolstat != SCIP_LPSOLSTAT_UNBOUNDEDRAY ) 500 { 501 SCIP_CALL( retcode ); 502 } 503 #endif 504 SCIPwarningMessage(scip, "Error while solving LP in Rootsoldiving heuristic; LP solve terminated with code <%d>\n", retcode); 505 SCIPwarningMessage(scip, "This does not affect the remaining solution procedure --> continue\n"); 506 } 507 508 if( lperror ) 509 break; 510 511 /* update iteration count */ 512 heurdata->nlpiterations += SCIPgetNLPIterations(scip) - nlpiterations; 513 514 /* if no LP iterations were performed, we stayed at the same solution -> count this cycling */ 515 lpsolchanged = (SCIPgetNLPIterations(scip) != nlpiterations); 516 if( lpsolchanged ) 517 ncycles = 0; 518 else if( !boundschanged ) /* do not count if integral variables have been fixed */ 519 ncycles++; 520 521 /* get LP solution status and number of fractional variables, that should be integral */ 522 if( lpsolstat == SCIP_LPSOLSTAT_INFEASIBLE && hardroundingidx != -1 ) 523 { 524 SCIP_VAR* var; 525 526 var = vars[hardroundingidx]; 527 528 /* round the hard rounded variable to the opposite direction and resolve the LP */ 529 if( hardroundingdir == -1 ) 530 { 531 SCIPdebugMsg(scip, " -> opposite hard rounding <%s> >= %g\n", SCIPvarGetName(var), hardroundingnewbd + 1.0); 532 SCIP_CALL( SCIPchgVarUbDive(scip, var, hardroundingoldbd) ); 533 SCIP_CALL( SCIPchgVarLbDive(scip, var, hardroundingnewbd + 1.0) ); 534 } 535 else 536 { 537 SCIPdebugMsg(scip, " -> opposite hard rounding <%s> <= %g\n", SCIPvarGetName(var), hardroundingnewbd - 1.0); 538 SCIP_CALL( SCIPchgVarLbDive(scip, var, hardroundingoldbd) ); 539 SCIP_CALL( SCIPchgVarUbDive(scip, var, hardroundingnewbd - 1.0) ); 540 } 541 hardroundingidx = -1; 542 goto SOLVEAGAIN; 543 } 544 if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL ) 545 nlpcands = SCIPgetNLPBranchCands(scip); 546 SCIPdebugMsg(scip, " -> lpsolstat=%d, nfrac=%d\n", lpsolstat, nlpcands); 547 } 548 549 SCIPdebugMsg(scip, "---> diving finished: lpsolstat = %d, depth %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT "\n", 550 lpsolstat, divedepth, maxdivedepth, heurdata->nlpiterations, maxnlpiterations); 551 552 /* check if a solution has been found */ 553 if( nlpcands == 0 && !lperror && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL ) 554 { 555 SCIP_Bool success; 556 557 /* create solution from diving LP */ 558 SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) ); 559 SCIPdebugMsg(scip, "rootsoldiving found primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol)); 560 561 /* try to add solution to SCIP */ 562 SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) ); 563 564 /* check, if solution was feasible and good enough */ 565 if( success ) 566 { 567 SCIPdebugMsg(scip, " -> solution was feasible and good enough\n"); 568 *result = SCIP_FOUNDSOL; 569 } 570 } 571 572 /* end diving */ 573 SCIP_CALL( SCIPendDive(scip) ); 574 575 if( *result == SCIP_FOUNDSOL ) 576 heurdata->nsuccess++; 577 578 /* free temporary memory */ 579 SCIPfreeBufferArray(scip, &objchgvals); 580 SCIPfreeBufferArray(scip, &intvalrounds); 581 SCIPfreeBufferArray(scip, &softroundings); 582 SCIPfreeBufferArray(scip, &rootsol); 583 584 SCIPdebugMsg(scip, "rootsoldiving heuristic finished\n"); 585 586 return SCIP_OKAY; 587 } 588 589 590 /* 591 * heuristic specific interface methods 592 */ 593 594 /** creates the rootsoldiving heuristic and includes it in SCIP */ 595 SCIP_RETCODE SCIPincludeHeurRootsoldiving( 596 SCIP* scip /**< SCIP data structure */ 597 ) 598 { 599 SCIP_HEURDATA* heurdata; 600 SCIP_HEUR* heur; 601 602 /* create Rootsoldiving primal heuristic data */ 603 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 604 605 /* include primal heuristic */ 606 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 607 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 608 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecRootsoldiving, heurdata) ); 609 610 assert(heur != NULL); 611 612 /* set non-NULL pointers to callback methods */ 613 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyRootsoldiving) ); 614 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeRootsoldiving) ); 615 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitRootsoldiving) ); 616 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitRootsoldiving) ); 617 618 /* rootsoldiving heuristic parameters */ 619 SCIP_CALL( SCIPaddRealParam(scip, 620 "heuristics/rootsoldiving/minreldepth", 621 "minimal relative depth to start diving", 622 &heurdata->minreldepth, TRUE, DEFAULT_MINRELDEPTH, 0.0, 1.0, NULL, NULL) ); 623 SCIP_CALL( SCIPaddRealParam(scip, 624 "heuristics/rootsoldiving/maxreldepth", 625 "maximal relative depth to start diving", 626 &heurdata->maxreldepth, TRUE, DEFAULT_MAXRELDEPTH, 0.0, 1.0, NULL, NULL) ); 627 SCIP_CALL( SCIPaddRealParam(scip, 628 "heuristics/rootsoldiving/maxlpiterquot", 629 "maximal fraction of diving LP iterations compared to node LP iterations", 630 &heurdata->maxlpiterquot, FALSE, DEFAULT_MAXLPITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 631 SCIP_CALL( SCIPaddIntParam(scip, 632 "heuristics/rootsoldiving/maxlpiterofs", 633 "additional number of allowed LP iterations", 634 &heurdata->maxlpiterofs, FALSE, DEFAULT_MAXLPITEROFS, 0, INT_MAX, NULL, NULL) ); 635 SCIP_CALL( SCIPaddIntParam(scip, 636 "heuristics/rootsoldiving/maxsols", 637 "total number of feasible solutions found up to which heuristic is called (-1: no limit)", 638 &heurdata->maxsols, TRUE, DEFAULT_MAXSOLS, -1, INT_MAX, NULL, NULL) ); 639 SCIP_CALL( SCIPaddRealParam(scip, 640 "heuristics/rootsoldiving/depthfac", 641 "maximal diving depth: number of binary/integer variables times depthfac", 642 &heurdata->depthfac, TRUE, DEFAULT_DEPTHFAC, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 643 SCIP_CALL( SCIPaddRealParam(scip, 644 "heuristics/rootsoldiving/depthfacnosol", 645 "maximal diving depth factor if no feasible solution was found yet", 646 &heurdata->depthfacnosol, TRUE, DEFAULT_DEPTHFACNOSOL, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 647 SCIP_CALL( SCIPaddRealParam(scip, 648 "heuristics/rootsoldiving/alpha", 649 "soft rounding factor to fade out objective coefficients", 650 &heurdata->alpha, TRUE, DEFAULT_ALPHA, 0.0, 1.0, NULL, NULL) ); 651 652 return SCIP_OKAY; 653 } 654 655