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