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_intdiving.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief LP diving heuristic that fixes variables with integral LP value 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_intdiving.h" 35 #include "scip/pub_heur.h" 36 #include "scip/pub_lp.h" 37 #include "scip/pub_message.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_probing.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 "intdiving" 56 #define HEUR_DESC "LP diving heuristic that fixes binary variables with large LP value to one" 57 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING 58 #define HEUR_PRIORITY -1003500 59 #define HEUR_FREQ -1 60 #define HEUR_FREQOFS 9 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.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */ 73 #define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */ 74 #define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) 75 * where diving is performed (0.0: no limit) */ 76 #define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) 77 * where diving is performed (0.0: no limit) */ 78 #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */ 79 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */ 80 #define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */ 81 82 #define MINLPITER 10000 /**< minimal number of LP iterations allowed in each LP solving call */ 83 84 85 /* locally defined heuristic data */ 86 struct SCIP_HeurData 87 { 88 SCIP_SOL* sol; /**< working solution */ 89 SCIP_Real minreldepth; /**< minimal relative depth to start diving */ 90 SCIP_Real maxreldepth; /**< maximal relative depth to start diving */ 91 SCIP_Real maxlpiterquot; /**< maximal fraction of diving LP iterations compared to node LP iterations */ 92 int maxlpiterofs; /**< additional number of allowed LP iterations */ 93 SCIP_Real maxdiveubquot; /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) 94 * where diving is performed (0.0: no limit) */ 95 SCIP_Real maxdiveavgquot; /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) 96 * where diving is performed (0.0: no limit) */ 97 SCIP_Real maxdiveubquotnosol; /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */ 98 SCIP_Real maxdiveavgquotnosol;/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */ 99 SCIP_Bool backtrack; /**< use one level of backtracking if infeasibility is encountered? */ 100 SCIP_Longint nlpiterations; /**< LP iterations used in this heuristic */ 101 int nsuccess; /**< number of runs that produced at least one feasible solution */ 102 }; 103 104 105 /* 106 * local methods 107 */ 108 109 110 /* 111 * Callback methods 112 */ 113 114 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 115 static 116 SCIP_DECL_HEURCOPY(heurCopyIntdiving) 117 { /*lint --e{715}*/ 118 assert(scip != NULL); 119 assert(heur != NULL); 120 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 121 122 /* call inclusion method of primal heuristic */ 123 SCIP_CALL( SCIPincludeHeurIntdiving(scip) ); 124 125 return SCIP_OKAY; 126 } 127 128 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 129 static 130 SCIP_DECL_HEURFREE(heurFreeIntdiving) /*lint --e{715}*/ 131 { /*lint --e{715}*/ 132 SCIP_HEURDATA* heurdata; 133 134 assert(heur != NULL); 135 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 136 assert(scip != NULL); 137 138 /* free heuristic data */ 139 heurdata = SCIPheurGetData(heur); 140 assert(heurdata != NULL); 141 SCIPfreeBlockMemory(scip, &heurdata); 142 SCIPheurSetData(heur, NULL); 143 144 return SCIP_OKAY; 145 } 146 147 148 /** initialization method of primal heuristic (called after problem was transformed) */ 149 static 150 SCIP_DECL_HEURINIT(heurInitIntdiving) /*lint --e{715}*/ 151 { /*lint --e{715}*/ 152 SCIP_HEURDATA* heurdata; 153 154 assert(heur != NULL); 155 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 156 157 /* get heuristic data */ 158 heurdata = SCIPheurGetData(heur); 159 assert(heurdata != NULL); 160 161 /* create working solution */ 162 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) ); 163 164 /* initialize data */ 165 heurdata->nlpiterations = 0; 166 heurdata->nsuccess = 0; 167 168 return SCIP_OKAY; 169 } 170 171 172 /** deinitialization method of primal heuristic (called before transformed problem is freed) */ 173 static 174 SCIP_DECL_HEUREXIT(heurExitIntdiving) /*lint --e{715}*/ 175 { /*lint --e{715}*/ 176 SCIP_HEURDATA* heurdata; 177 178 assert(heur != NULL); 179 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 180 181 /* get heuristic data */ 182 heurdata = SCIPheurGetData(heur); 183 assert(heurdata != NULL); 184 185 /* free working solution */ 186 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) ); 187 188 return SCIP_OKAY; 189 } 190 191 192 /** execution method of primal heuristic */ 193 static 194 SCIP_DECL_HEUREXEC(heurExecIntdiving) /*lint --e{715}*/ 195 { /*lint --e{715}*/ 196 SCIP_HEURDATA* heurdata; 197 SCIP_LPSOLSTAT lpsolstat; 198 SCIP_VAR** pseudocands; 199 SCIP_VAR** fixcands; 200 SCIP_Real* fixcandscores; 201 SCIP_Real searchubbound; 202 SCIP_Real searchavgbound; 203 SCIP_Real searchbound; 204 SCIP_Real objval; 205 SCIP_Bool lperror; 206 SCIP_Bool cutoff; 207 SCIP_Bool backtracked; 208 SCIP_Longint ncalls; 209 SCIP_Longint nsolsfound; 210 SCIP_Longint nlpiterations; 211 SCIP_Longint maxnlpiterations; 212 int nfixcands; 213 int nbinfixcands; 214 int depth; 215 int maxdepth; 216 int maxdivedepth; 217 int divedepth; 218 int nextcand; 219 int c; 220 221 assert(heur != NULL); 222 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 223 assert(scip != NULL); 224 assert(result != NULL); 225 assert(SCIPhasCurrentNodeLP(scip)); 226 227 *result = SCIP_DELAYED; 228 229 /* do not call heuristic of node was already detected to be infeasible */ 230 if( nodeinfeasible ) 231 return SCIP_OKAY; 232 233 /* only call heuristic, if an optimal LP solution is at hand */ 234 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 235 return SCIP_OKAY; 236 237 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */ 238 if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) ) 239 return SCIP_OKAY; 240 241 /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */ 242 if( !SCIPisLPSolBasic(scip) ) 243 return SCIP_OKAY; 244 245 /* don't dive two times at the same node */ 246 if( SCIPgetLastDivenode(scip) == SCIPgetNNodes(scip) && SCIPgetDepth(scip) > 0 ) 247 return SCIP_OKAY; 248 249 *result = SCIP_DIDNOTRUN; 250 251 /* get heuristic's data */ 252 heurdata = SCIPheurGetData(heur); 253 assert(heurdata != NULL); 254 255 /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */ 256 depth = SCIPgetDepth(scip); 257 maxdepth = SCIPgetMaxDepth(scip); 258 maxdepth = MAX(maxdepth, 100); 259 if( depth < heurdata->minreldepth*maxdepth || depth > heurdata->maxreldepth*maxdepth ) 260 return SCIP_OKAY; 261 262 /* calculate the maximal number of LP iterations until heuristic is aborted */ 263 nlpiterations = SCIPgetNNodeLPIterations(scip); 264 ncalls = SCIPheurGetNCalls(heur); 265 nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + heurdata->nsuccess; 266 maxnlpiterations = (SCIP_Longint)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxlpiterquot * nlpiterations); 267 maxnlpiterations += heurdata->maxlpiterofs; 268 269 /* don't try to dive, if we took too many LP iterations during diving */ 270 if( heurdata->nlpiterations >= maxnlpiterations ) 271 return SCIP_OKAY; 272 273 /* allow at least a certain number of LP iterations in this dive */ 274 maxnlpiterations = MAX(maxnlpiterations, heurdata->nlpiterations + MINLPITER); 275 276 /* get unfixed integer variables */ 277 SCIP_CALL( SCIPgetPseudoBranchCands(scip, &pseudocands, &nfixcands, NULL) ); 278 279 /* don't try to dive, if there are no fractional variables */ 280 if( nfixcands == 0 ) 281 return SCIP_OKAY; 282 283 /* calculate the objective search bound */ 284 if( SCIPgetNSolsFound(scip) == 0 ) 285 { 286 if( heurdata->maxdiveubquotnosol > 0.0 ) 287 searchubbound = SCIPgetLowerbound(scip) 288 + heurdata->maxdiveubquotnosol * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip)); 289 else 290 searchubbound = SCIPinfinity(scip); 291 if( heurdata->maxdiveavgquotnosol > 0.0 ) 292 searchavgbound = SCIPgetLowerbound(scip) 293 + heurdata->maxdiveavgquotnosol * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip)); 294 else 295 searchavgbound = SCIPinfinity(scip); 296 } 297 else 298 { 299 if( heurdata->maxdiveubquot > 0.0 ) 300 searchubbound = SCIPgetLowerbound(scip) 301 + heurdata->maxdiveubquot * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip)); 302 else 303 searchubbound = SCIPinfinity(scip); 304 if( heurdata->maxdiveavgquot > 0.0 ) 305 searchavgbound = SCIPgetLowerbound(scip) 306 + heurdata->maxdiveavgquot * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip)); 307 else 308 searchavgbound = SCIPinfinity(scip); 309 } 310 searchbound = MIN(searchubbound, searchavgbound); 311 if( SCIPisObjIntegral(scip) ) 312 searchbound = SCIPceil(scip, searchbound); 313 314 /* calculate the maximal diving depth: 10 * min{number of integer variables, max depth} */ 315 maxdivedepth = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip); 316 maxdivedepth = MIN(maxdivedepth, maxdepth); 317 maxdivedepth *= 10; 318 319 *result = SCIP_DIDNOTFIND; 320 321 /* start diving */ 322 SCIP_CALL( SCIPstartProbing(scip) ); 323 324 /* enables collection of variable statistics during probing */ 325 SCIPenableVarHistory(scip); 326 327 SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing intdiving heuristic: depth=%d, %d non-fixed, dualbound=%g, searchbound=%g\n", 328 SCIPgetNNodes(scip), SCIPgetDepth(scip), nfixcands, SCIPgetDualbound(scip), SCIPretransformObj(scip, searchbound)); 329 330 /* copy the pseudo candidates into own array, because we want to reorder them */ 331 SCIP_CALL( SCIPduplicateBufferArray(scip, &fixcands, pseudocands, nfixcands) ); 332 333 /* sort non-fixed variables by non-increasing inference score, but prefer binaries over integers in any case */ 334 SCIP_CALL( SCIPallocBufferArray(scip, &fixcandscores, nfixcands) ); 335 nbinfixcands = 0; 336 for( c = 0; c < nfixcands; ++c ) 337 { 338 SCIP_VAR* var; 339 SCIP_Real score; 340 int colveclen; 341 int left; 342 int right; 343 int i; 344 345 assert(c >= nbinfixcands); 346 var = fixcands[c]; 347 assert(SCIPvarIsIntegral(var)); 348 colveclen = (SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN ? SCIPcolGetNNonz(SCIPvarGetCol(var)) : 0); 349 if( SCIPvarIsBinary(var) ) 350 { 351 score = 500.0 * SCIPvarGetNCliques(var, TRUE) + 100.0 * SCIPvarGetNImpls(var, TRUE) 352 + SCIPgetVarAvgInferenceScore(scip, var) + (SCIP_Real)colveclen/100.0; 353 354 /* shift the non-binary variables one slot to the right */ 355 for( i = c; i > nbinfixcands; --i ) 356 { 357 fixcands[i] = fixcands[i-1]; 358 fixcandscores[i] = fixcandscores[i-1]; 359 } 360 /* put the new candidate into the first nbinfixcands slot */ 361 left = 0; 362 right = nbinfixcands; 363 nbinfixcands++; 364 } 365 else 366 { 367 score = 5.0 * (SCIPvarGetNCliques(var, FALSE) + SCIPvarGetNCliques(var, TRUE)) 368 + SCIPvarGetNImpls(var, FALSE) + SCIPvarGetNImpls(var, TRUE) + SCIPgetVarAvgInferenceScore(scip, var) 369 + (SCIP_Real)colveclen/10000.0; 370 371 /* put the new candidate in the slots after the binary candidates */ 372 left = nbinfixcands; 373 right = c; 374 } 375 for( i = right; i > left && score > fixcandscores[i-1]; --i ) 376 { 377 fixcands[i] = fixcands[i-1]; 378 fixcandscores[i] = fixcandscores[i-1]; 379 } 380 fixcands[i] = var; 381 fixcandscores[i] = score; 382 SCIPdebugMsg(scip, " <%s>: ncliques=%d/%d, nimpls=%d/%d, inferencescore=%g, colveclen=%d -> score=%g\n", 383 SCIPvarGetName(var), SCIPvarGetNCliques(var, FALSE), SCIPvarGetNCliques(var, TRUE), 384 SCIPvarGetNImpls(var, FALSE), SCIPvarGetNImpls(var, TRUE), SCIPgetVarAvgInferenceScore(scip, var), 385 colveclen, score); 386 } 387 SCIPfreeBufferArray(scip, &fixcandscores); 388 389 /* get LP objective value */ 390 lpsolstat = SCIP_LPSOLSTAT_OPTIMAL; 391 objval = SCIPgetLPObjval(scip); 392 393 /* dive as long we are in the given objective, depth and iteration limits, but if possible, we dive at least with 394 * the depth 10 395 */ 396 lperror = FALSE; 397 cutoff = FALSE; 398 divedepth = 0; 399 nextcand = 0; 400 while( !lperror && !cutoff && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL 401 && (divedepth < 10 402 || (divedepth < maxdivedepth && heurdata->nlpiterations < maxnlpiterations && objval < searchbound)) 403 && !SCIPisStopped(scip) ) 404 { 405 SCIP_VAR* var; 406 SCIP_Real bestsolval; 407 SCIP_Real bestfixval; 408 int bestcand; 409 SCIP_Longint nnewlpiterations; 410 SCIP_Longint nnewdomreds; 411 412 /* open a new probing node if this will not exceed the maximal tree depth, otherwise stop here */ 413 if( SCIPgetDepth(scip) < SCIP_MAXTREEDEPTH ) 414 { 415 SCIP_CALL( SCIPnewProbingNode(scip) ); 416 divedepth++; 417 } 418 else 419 break; 420 421 nnewlpiterations = 0; 422 nnewdomreds = 0; 423 424 /* fix binary variable that is closest to 1 in the LP solution to 1; 425 * if all binary variables are fixed, fix integer variable with least fractionality in LP solution 426 */ 427 bestcand = -1; 428 bestsolval = -1.0; 429 bestfixval = 1.0; 430 431 /* look in the binary variables for fixing candidates */ 432 for( c = nextcand; c < nbinfixcands; ++c ) 433 { 434 SCIP_Real solval; 435 436 var = fixcands[c]; 437 438 /* ignore already fixed variables */ 439 if( var == NULL ) 440 continue; 441 if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 ) 442 { 443 fixcands[c] = NULL; 444 continue; 445 } 446 447 /* get the LP solution value */ 448 solval = SCIPvarGetLPSol(var); 449 450 if( solval > bestsolval ) 451 { 452 bestcand = c; 453 bestfixval = 1.0; 454 bestsolval = solval; 455 if( SCIPisGE(scip, bestsolval, 1.0) ) 456 { 457 /* we found an unfixed binary variable with LP solution value of 1.0 - there cannot be a better candidate */ 458 break; 459 } 460 else if( SCIPisLE(scip, bestsolval, 0.0) ) 461 { 462 /* the variable is currently at 0.0 - this is the only situation where we want to fix it to 0.0 */ 463 bestfixval = 0.0; 464 } 465 } 466 } 467 468 /* if all binary variables are fixed, look in the integer variables for a fixing candidate */ 469 if( bestcand == -1 ) 470 { 471 SCIP_Real bestfrac; 472 473 bestfrac = SCIP_INVALID; 474 for( c = MAX(nextcand, nbinfixcands); c < nfixcands; ++c ) 475 { 476 SCIP_Real solval; 477 SCIP_Real frac; 478 479 var = fixcands[c]; 480 481 /* ignore already fixed variables */ 482 if( var == NULL ) 483 continue; 484 if( SCIPvarGetUbLocal(var) - SCIPvarGetLbLocal(var) < 0.5 ) 485 { 486 fixcands[c] = NULL; 487 continue; 488 } 489 490 /* get the LP solution value */ 491 solval = SCIPvarGetLPSol(var); 492 frac = SCIPfrac(scip, solval); 493 494 /* ignore integer variables that are currently integral */ 495 if( SCIPisFeasFracIntegral(scip, frac) ) 496 continue; 497 498 if( frac < bestfrac ) 499 { 500 bestcand = c; 501 bestsolval = solval; 502 bestfrac = frac; 503 bestfixval = SCIPfloor(scip, bestsolval + 0.5); 504 if( SCIPisZero(scip, bestfrac) ) 505 { 506 /* we found an unfixed integer variable with integral LP solution value */ 507 break; 508 } 509 } 510 } 511 } 512 assert(-1 <= bestcand && bestcand < nfixcands); 513 514 /* if there is no unfixed candidate left, we are done */ 515 if( bestcand == -1 ) 516 break; 517 518 var = fixcands[bestcand]; 519 assert(var != NULL); 520 assert(SCIPvarIsIntegral(var)); 521 assert(SCIPvarGetUbLocal(var) - SCIPvarGetLbLocal(var) > 0.5); 522 assert(SCIPisGE(scip, bestfixval, SCIPvarGetLbLocal(var))); 523 assert(SCIPisLE(scip, bestfixval, SCIPvarGetUbLocal(var))); 524 525 backtracked = FALSE; 526 do 527 { 528 /* if the variable is already fixed or if the solution value is outside the domain, numerical troubles may have 529 * occured or variable was fixed by propagation while backtracking => Abort diving! 530 */ 531 if( SCIPvarGetLbLocal(var) >= SCIPvarGetUbLocal(var) - 0.5 ) 532 { 533 SCIPdebugMsg(scip, "Selected variable <%s> already fixed to [%g,%g], diving aborted \n", 534 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)); 535 cutoff = TRUE; 536 break; 537 } 538 if( SCIPisFeasLT(scip, bestfixval, SCIPvarGetLbLocal(var)) || SCIPisFeasGT(scip, bestfixval, SCIPvarGetUbLocal(var)) ) 539 { 540 SCIPdebugMsg(scip, "selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n", 541 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestfixval); 542 assert(backtracked); 543 break; 544 } 545 546 /* apply fixing of best candidate */ 547 SCIPdebugMsg(scip, " dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ", %d unfixed: var <%s>, sol=%g, oldbounds=[%g,%g], fixed to %g\n", 548 divedepth, maxdivedepth, heurdata->nlpiterations, maxnlpiterations, SCIPgetNPseudoBranchCands(scip), 549 SCIPvarGetName(var), bestsolval, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestfixval); 550 SCIP_CALL( SCIPfixVarProbing(scip, var, bestfixval) ); 551 552 /* apply domain propagation */ 553 SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, &nnewdomreds) ); 554 if( !cutoff ) 555 { 556 /* if the best candidate was just fixed to its LP value and no domain reduction was found, the LP solution 557 * stays valid, and the LP does not need to be resolved 558 */ 559 if( nnewdomreds > 0 || !SCIPisEQ(scip, bestsolval, bestfixval) ) 560 { 561 /* resolve the diving LP */ 562 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic. 563 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 564 */ 565 #ifdef NDEBUG 566 SCIP_RETCODE retstat; 567 nlpiterations = SCIPgetNLPIterations(scip); 568 retstat = SCIPsolveProbingLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, &cutoff); 569 if( retstat != SCIP_OKAY ) 570 { 571 SCIPwarningMessage(scip, "Error while solving LP in Intdiving heuristic; LP solve terminated with code <%d>\n",retstat); 572 } 573 #else 574 nlpiterations = SCIPgetNLPIterations(scip); 575 SCIP_CALL( SCIPsolveProbingLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, &cutoff) ); 576 #endif 577 578 if( lperror ) 579 break; 580 581 /* update iteration count */ 582 nnewlpiterations = SCIPgetNLPIterations(scip) - nlpiterations; 583 heurdata->nlpiterations += nnewlpiterations; 584 585 /* get LP solution status */ 586 lpsolstat = SCIPgetLPSolstat(scip); 587 assert(cutoff || (lpsolstat != SCIP_LPSOLSTAT_OBJLIMIT && lpsolstat != SCIP_LPSOLSTAT_INFEASIBLE && 588 (lpsolstat != SCIP_LPSOLSTAT_OPTIMAL || SCIPisLT(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip))))); 589 } 590 } 591 592 /* perform backtracking if a cutoff was detected */ 593 if( cutoff && !backtracked && heurdata->backtrack ) 594 { 595 SCIPdebugMsg(scip, " *** cutoff detected at level %d - backtracking\n", SCIPgetProbingDepth(scip)); 596 SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) ); 597 598 /* after backtracking there has to be at least one open node without exceeding the maximal tree depth */ 599 assert(SCIP_MAXTREEDEPTH > SCIPgetDepth(scip)); 600 601 SCIP_CALL( SCIPnewProbingNode(scip) ); 602 603 bestfixval = SCIPvarIsBinary(var) 604 ? 1.0 - bestfixval 605 : (SCIPisGT(scip, bestsolval, bestfixval) && SCIPisFeasLE(scip, bestfixval + 1, SCIPvarGetUbLocal(var)) ? bestfixval + 1 : bestfixval - 1); 606 607 backtracked = TRUE; 608 } 609 else 610 backtracked = FALSE; 611 } 612 while( backtracked ); 613 614 if( !lperror && !cutoff && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL ) 615 { 616 SCIP_Bool success; 617 618 /* get new objective value */ 619 objval = SCIPgetLPObjval(scip); 620 621 if( nnewlpiterations > 0 || !SCIPisEQ(scip, bestsolval, bestfixval) ) 622 { 623 /* we must start again with the first candidate, since the LP solution changed */ 624 nextcand = 0; 625 626 /* create solution from diving LP and try to round it */ 627 SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) ); 628 SCIP_CALL( SCIProundSol(scip, heurdata->sol, &success) ); 629 if( success ) 630 { 631 SCIPdebugMsg(scip, "intdiving found roundable primal solution: obj=%g\n", 632 SCIPgetSolOrigObj(scip, heurdata->sol)); 633 634 /* try to add solution to SCIP */ 635 SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) ); 636 637 /* check, if solution was feasible and good enough */ 638 if( success ) 639 { 640 SCIPdebugMsg(scip, " -> solution was feasible and good enough\n"); 641 *result = SCIP_FOUNDSOL; 642 } 643 } 644 } 645 else 646 nextcand = bestcand+1; /* continue with the next candidate in the following loop */ 647 } 648 SCIPdebugMsg(scip, " -> lpsolstat=%d, objval=%g/%g\n", lpsolstat, objval, searchbound); 649 } 650 651 /* free temporary memory */ 652 SCIPfreeBufferArray(scip, &fixcands); 653 654 /* end diving */ 655 SCIP_CALL( SCIPendProbing(scip) ); 656 657 if( *result == SCIP_FOUNDSOL ) 658 heurdata->nsuccess++; 659 660 SCIPdebugMsg(scip, "intdiving heuristic finished\n"); 661 662 return SCIP_OKAY; /*lint !e438*/ 663 } 664 665 666 /* 667 * heuristic specific interface methods 668 */ 669 670 /** creates the intdiving heuristic and includes it in SCIP */ 671 SCIP_RETCODE SCIPincludeHeurIntdiving( 672 SCIP* scip /**< SCIP data structure */ 673 ) 674 { 675 SCIP_HEURDATA* heurdata; 676 SCIP_HEUR* heur; 677 678 /* create Intdiving primal heuristic data */ 679 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 680 681 /* include primal heuristic */ 682 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 683 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 684 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecIntdiving, heurdata) ); 685 686 assert(heur != NULL); 687 688 /* set non-NULL pointers to callback methods */ 689 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyIntdiving) ); 690 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeIntdiving) ); 691 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitIntdiving) ); 692 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitIntdiving) ); 693 694 /* intdiving heuristic parameters */ 695 SCIP_CALL( SCIPaddRealParam(scip, 696 "heuristics/intdiving/minreldepth", 697 "minimal relative depth to start diving", 698 &heurdata->minreldepth, TRUE, DEFAULT_MINRELDEPTH, 0.0, 1.0, NULL, NULL) ); 699 SCIP_CALL( SCIPaddRealParam(scip, 700 "heuristics/intdiving/maxreldepth", 701 "maximal relative depth to start diving", 702 &heurdata->maxreldepth, TRUE, DEFAULT_MAXRELDEPTH, 0.0, 1.0, NULL, NULL) ); 703 SCIP_CALL( SCIPaddRealParam(scip, 704 "heuristics/intdiving/maxlpiterquot", 705 "maximal fraction of diving LP iterations compared to node LP iterations", 706 &heurdata->maxlpiterquot, FALSE, DEFAULT_MAXLPITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 707 SCIP_CALL( SCIPaddIntParam(scip, 708 "heuristics/intdiving/maxlpiterofs", 709 "additional number of allowed LP iterations", 710 &heurdata->maxlpiterofs, FALSE, DEFAULT_MAXLPITEROFS, 0, INT_MAX, NULL, NULL) ); 711 SCIP_CALL( SCIPaddRealParam(scip, 712 "heuristics/intdiving/maxdiveubquot", 713 "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)", 714 &heurdata->maxdiveubquot, TRUE, DEFAULT_MAXDIVEUBQUOT, 0.0, 1.0, NULL, NULL) ); 715 SCIP_CALL( SCIPaddRealParam(scip, 716 "heuristics/intdiving/maxdiveavgquot", 717 "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)", 718 &heurdata->maxdiveavgquot, TRUE, DEFAULT_MAXDIVEAVGQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 719 SCIP_CALL( SCIPaddRealParam(scip, 720 "heuristics/intdiving/maxdiveubquotnosol", 721 "maximal UBQUOT when no solution was found yet (0.0: no limit)", 722 &heurdata->maxdiveubquotnosol, TRUE, DEFAULT_MAXDIVEUBQUOTNOSOL, 0.0, 1.0, NULL, NULL) ); 723 SCIP_CALL( SCIPaddRealParam(scip, 724 "heuristics/intdiving/maxdiveavgquotnosol", 725 "maximal AVGQUOT when no solution was found yet (0.0: no limit)", 726 &heurdata->maxdiveavgquotnosol, TRUE, DEFAULT_MAXDIVEAVGQUOTNOSOL, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 727 SCIP_CALL( SCIPaddBoolParam(scip, 728 "heuristics/intdiving/backtrack", 729 "use one level of backtracking if infeasibility is encountered?", 730 &heurdata->backtrack, FALSE, DEFAULT_BACKTRACK, NULL, NULL) ); 731 732 return SCIP_OKAY; 733 } 734