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_randrounding.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief randomized LP rounding heuristic which also generates conflicts via an auxiliary probing tree 28 * @author Gregor Hendel 29 * 30 * Randomized LP rounding uses a random variable from a uniform distribution 31 * over [0,1] to determine whether the fractional LP value x should be rounded 32 * up with probability x - floor(x) or down with probability ceil(x) - x. 33 * 34 * This implementation uses domain propagation techniques to tighten the variable domains after every 35 * rounding step. 36 */ 37 38 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 39 40 #include "blockmemshell/memory.h" 41 #include "scip/heur_randrounding.h" 42 #include "scip/pub_heur.h" 43 #include "scip/pub_message.h" 44 #include "scip/pub_misc.h" 45 #include "scip/pub_var.h" 46 #include "scip/scip_branch.h" 47 #include "scip/scip_general.h" 48 #include "scip/scip_heur.h" 49 #include "scip/scip_lp.h" 50 #include "scip/scip_mem.h" 51 #include "scip/scip_message.h" 52 #include "scip/scip_numerics.h" 53 #include "scip/scip_param.h" 54 #include "scip/scip_probing.h" 55 #include "scip/scip_randnumgen.h" 56 #include "scip/scip_sol.h" 57 #include "scip/scip_solvingstats.h" 58 #include "scip/scip_tree.h" 59 #include "scip/scip_var.h" 60 #include <string.h> 61 62 #define HEUR_NAME "randrounding" 63 #define HEUR_DESC "fast LP rounding heuristic" 64 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING 65 #define HEUR_PRIORITY -200 66 #define HEUR_FREQ 20 67 #define HEUR_FREQOFS 0 68 #define HEUR_MAXDEPTH -1 69 #define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP 70 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */ 71 72 #define DEFAULT_ONCEPERNODE FALSE /**< should the heuristic only be called once per node? */ 73 #define DEFAULT_RANDSEED 23 /**< default random seed */ 74 #define DEFAULT_USESIMPLEROUNDING FALSE /**< should the heuristic apply the variable lock strategy of simple rounding, 75 * if possible? */ 76 #define DEFAULT_MAXPROPROUNDS 1 /**< limit of rounds for each propagation call */ 77 #define DEFAULT_PROPAGATEONLYROOT TRUE /**< should the probing part of the heuristic be applied exclusively at the root node */ 78 79 /* locally defined heuristic data */ 80 struct SCIP_HeurData 81 { 82 SCIP_SOL* sol; /**< working solution */ 83 SCIP_RANDNUMGEN* randnumgen; /**< random number generation */ 84 SCIP_Longint lastlp; /**< last LP number where the heuristic was applied */ 85 int maxproprounds; /**< limit of rounds for each propagation call */ 86 SCIP_Bool oncepernode; /**< should the heuristic only be called once per node? */ 87 SCIP_Bool usesimplerounding; /**< should the heuristic apply the variable lock strategy of simple rounding, 88 * if possible? */ 89 SCIP_Bool propagateonlyroot; /**< should the probing part of the heuristic be applied exclusively at the root node? */ 90 }; 91 92 /* 93 * Local methods 94 */ 95 96 /** perform randomized rounding of the given solution. Domain propagation is optionally applied after every rounding 97 * step 98 */ 99 static 100 SCIP_RETCODE performRandRounding( 101 SCIP* scip, /**< SCIP main data structure */ 102 SCIP_HEURDATA* heurdata, /**< heuristic data */ 103 SCIP_SOL* sol, /**< solution to round */ 104 SCIP_VAR** cands, /**< candidate variables */ 105 int ncands, /**< number of candidates */ 106 SCIP_Bool propagate, /**< should the rounding be propagated? */ 107 SCIP_RESULT* result /**< pointer to store the result of the heuristic call */ 108 ) 109 { 110 int c; 111 SCIP_Bool stored; 112 SCIP_VAR** permutedcands; 113 SCIP_Bool cutoff; 114 115 assert(heurdata != NULL); 116 117 /* start probing tree before rounding begins */ 118 if( propagate ) 119 { 120 SCIP_CALL( SCIPstartProbing(scip) ); 121 SCIPenableVarHistory(scip); 122 } 123 124 /* copy and permute the candidate array */ 125 SCIP_CALL( SCIPduplicateBufferArray(scip, &permutedcands, cands, ncands) ); 126 127 assert(permutedcands != NULL); 128 129 SCIPrandomPermuteArray(heurdata->randnumgen, (void **)permutedcands, 0, ncands); 130 cutoff = FALSE; 131 132 /* loop over candidates and perform randomized rounding and optionally probing. */ 133 for (c = 0; c < ncands && !cutoff; ++c) 134 { 135 SCIP_VAR* var; 136 SCIP_Real oldsolval; 137 SCIP_Real newsolval; 138 SCIP_Bool mayrounddown; 139 SCIP_Bool mayroundup; 140 SCIP_Longint ndomreds; 141 SCIP_Real lb; 142 SCIP_Real ub; 143 SCIP_Real ceilval; 144 SCIP_Real floorval; 145 146 /* get next variable from permuted candidate array */ 147 var = permutedcands[c]; 148 oldsolval = SCIPgetSolVal(scip, sol, var); 149 lb = SCIPvarGetLbLocal(var); 150 ub = SCIPvarGetUbLocal(var); 151 152 assert( ! SCIPisFeasIntegral(scip, oldsolval) ); 153 assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN ); 154 155 mayrounddown = SCIPvarMayRoundDown(var); 156 mayroundup = SCIPvarMayRoundUp(var); 157 ceilval = SCIPfeasCeil(scip, oldsolval); 158 floorval = SCIPfeasFloor(scip, oldsolval); 159 160 SCIPdebugMsg(scip, "rand rounding heuristic: var <%s>, val=%g, rounddown=%u, roundup=%u\n", 161 SCIPvarGetName(var), oldsolval, mayrounddown, mayroundup); 162 163 /* abort if rounded ceil and floor value lie outside the variable domain. Otherwise, check if 164 * bounds allow only one rounding direction, anyway */ 165 if( lb > ceilval + 0.5 || ub < floorval - 0.5 ) 166 { 167 cutoff = TRUE; 168 break; 169 } 170 else if( SCIPisFeasEQ(scip, lb, ceilval) ) 171 { 172 /* only rounding up possible */ 173 assert(SCIPisFeasGE(scip, ub, ceilval)); 174 newsolval = ceilval; 175 } 176 else if( SCIPisFeasEQ(scip, ub, floorval) ) 177 { 178 /* only rounding down possible */ 179 assert(SCIPisFeasLE(scip,lb, floorval)); 180 newsolval = floorval; 181 } 182 else if( !heurdata->usesimplerounding || !(mayroundup || mayrounddown) ) 183 { 184 /* the standard randomized rounding */ 185 SCIP_Real randnumber; 186 187 randnumber = SCIPrandomGetReal(heurdata->randnumgen, 0.0, 1.0); 188 if( randnumber <= oldsolval - floorval ) 189 newsolval = ceilval; 190 else 191 newsolval = floorval; 192 } 193 /* choose rounding direction, if possible, or use the only direction guaranteed to be feasible */ 194 else if( mayrounddown && mayroundup ) 195 { 196 /* we can round in both directions: round in objective function direction */ 197 if ( SCIPvarGetObj(var) >= 0.0 ) 198 newsolval = floorval; 199 else 200 newsolval = ceilval; 201 } 202 else if( mayrounddown ) 203 newsolval = floorval; 204 else 205 { 206 assert(mayroundup); 207 newsolval = ceilval; 208 } 209 210 assert(SCIPisFeasLE(scip, lb, newsolval)); 211 assert(SCIPisFeasGE(scip, ub, newsolval)); 212 213 /* if propagation is enabled, fix the candidate variable to its rounded value and propagate the solution */ 214 if( propagate ) 215 { 216 SCIP_Bool lbadjust; 217 SCIP_Bool ubadjust; 218 219 lbadjust = SCIPisGT(scip, newsolval, lb); 220 ubadjust = SCIPisLT(scip, newsolval, ub); 221 222 assert( lbadjust || ubadjust || SCIPisFeasEQ(scip, lb, ub)); 223 224 /* enter a new probing node if the variable was not already fixed before */ 225 if( lbadjust || ubadjust ) 226 { 227 if( SCIPisStopped(scip) ) 228 break; 229 230 /* We only want to create a new probing node if we do not exceeed the maximal tree depth, 231 * otherwise we finish at this point. 232 * @todo: Maybe we want to continue with the same node because we do not backtrack. 233 */ 234 if( SCIPgetDepth(scip) < SCIP_MAXTREEDEPTH ) 235 { 236 SCIP_CALL( SCIPnewProbingNode(scip) ); 237 } 238 else 239 break; 240 241 /* tighten the bounds to fix the variable for the probing node */ 242 if( lbadjust ) 243 { 244 SCIP_CALL( SCIPchgVarLbProbing(scip, var, newsolval) ); 245 } 246 if( ubadjust ) 247 { 248 SCIP_CALL( SCIPchgVarUbProbing(scip, var, newsolval) ); 249 } 250 251 /* call propagation routines for the reduced problem */ 252 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, &cutoff, &ndomreds) ); 253 } 254 } 255 /* store new solution value */ 256 SCIP_CALL( SCIPsetSolVal(scip, sol, var, newsolval) ); 257 } 258 259 /* if no cutoff was detected, the solution is a candidate to be checked for feasibility */ 260 if( !cutoff && ! SCIPisStopped(scip) ) 261 { 262 if( SCIPallColsInLP(scip) ) 263 { 264 /* check solution for feasibility, and add it to solution store if possible 265 * neither integrality nor feasibility of LP rows has to be checked, because all fractional 266 * variables were already moved in feasible direction to the next integer 267 */ 268 SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, FALSE, FALSE, TRUE, &stored) ); 269 } 270 else 271 { 272 /* if there are variables which are not present in the LP, e.g., for 273 * column generation, we need to check their bounds 274 */ 275 SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, TRUE, FALSE, TRUE, &stored) ); 276 } 277 278 if( stored ) 279 { 280 #ifdef SCIP_DEBUG 281 SCIPdebugMsg(scip, "found feasible rounded solution:\n"); 282 SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) ); 283 #endif 284 *result = SCIP_FOUNDSOL; 285 } 286 } 287 288 assert( !propagate || SCIPinProbing(scip) ); 289 290 /* exit probing mode and free locally allocated memory */ 291 if( propagate ) 292 { 293 SCIP_CALL( SCIPendProbing(scip) ); 294 } 295 296 SCIPfreeBufferArray(scip, &permutedcands); 297 298 return SCIP_OKAY; 299 } 300 301 /** perform randomized LP-rounding */ 302 static 303 SCIP_RETCODE performLPRandRounding( 304 SCIP* scip, /**< SCIP main data structure */ 305 SCIP_HEURDATA* heurdata, /**< heuristic data */ 306 SCIP_HEURTIMING heurtiming, /**< heuristic timing mask */ 307 SCIP_Bool propagate, /**< should the heuristic apply SCIP's propagation? */ 308 SCIP_RESULT* result /**< pointer to store the result of the heuristic call */ 309 ) 310 { 311 SCIP_SOL* sol; 312 SCIP_VAR** lpcands; 313 SCIP_Longint nlps; 314 int nlpcands; 315 316 /* only call heuristic, if an optimal LP solution is at hand */ 317 assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL); 318 319 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */ 320 if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) ) 321 return SCIP_OKAY; 322 323 /* get fractional variables, that should be integral */ 324 SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, NULL, NULL, &nlpcands, NULL, NULL) ); 325 326 /* only call heuristic, if LP solution is fractional; except we are called during pricing, in this case we 327 * want to detect a (mixed) integer (LP) solution which is primal feasible */ 328 if ( nlpcands == 0 && heurtiming != SCIP_HEURTIMING_DURINGPRICINGLOOP ) 329 return SCIP_OKAY; 330 331 /* get the working solution from heuristic's local data */ 332 sol = heurdata->sol; 333 assert( sol != NULL ); 334 335 /* copy the current LP solution to the working solution */ 336 SCIP_CALL( SCIPlinkLPSol(scip, sol) ); 337 338 /* don't call heuristic, if we have already processed the current LP solution */ 339 nlps = SCIPgetNLPs(scip); 340 if( nlps == heurdata->lastlp ) 341 return SCIP_OKAY; 342 heurdata->lastlp = nlps; 343 344 *result = SCIP_DIDNOTFIND; 345 346 /* perform random rounding */ 347 SCIPdebugMsg(scip, "executing rand LP-rounding heuristic: %d fractionals\n", nlpcands); 348 SCIP_CALL( performRandRounding(scip, heurdata, sol, lpcands, nlpcands, propagate, result) ); 349 350 return SCIP_OKAY; 351 } 352 353 /* 354 * Callback methods 355 */ 356 357 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 358 static 359 SCIP_DECL_HEURCOPY(heurCopyRandrounding) 360 { /*lint --e{715}*/ 361 assert(scip != NULL); 362 assert(heur != NULL); 363 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 364 365 /* call inclusion method of primal heuristic */ 366 SCIP_CALL( SCIPincludeHeurRandrounding(scip) ); 367 368 return SCIP_OKAY; 369 } 370 371 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 372 static 373 SCIP_DECL_HEURFREE(heurFreeRandrounding) /*lint --e{715}*/ 374 { /*lint --e{715}*/ 375 SCIP_HEURDATA* heurdata; 376 377 assert(heur != NULL); 378 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 379 assert(scip != NULL); 380 381 /* free heuristic data */ 382 heurdata = SCIPheurGetData(heur); 383 assert(heurdata != NULL); 384 SCIPfreeBlockMemory(scip, &heurdata); 385 SCIPheurSetData(heur, NULL); 386 387 return SCIP_OKAY; 388 } 389 390 /** initialization method of primal heuristic (called after problem was transformed) */ 391 static 392 SCIP_DECL_HEURINIT(heurInitRandrounding) /*lint --e{715}*/ 393 { /*lint --e{715}*/ 394 SCIP_HEURDATA* heurdata; 395 396 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 397 heurdata = SCIPheurGetData(heur); 398 assert(heurdata != NULL); 399 400 /* create heuristic data */ 401 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) ); 402 heurdata->lastlp = -1; 403 404 /* create random number generator */ 405 SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen, 406 DEFAULT_RANDSEED, TRUE) ); 407 408 return SCIP_OKAY; 409 } 410 411 /** deinitialization method of primal heuristic (called before transformed problem is freed) */ 412 static 413 SCIP_DECL_HEUREXIT(heurExitRandrounding) /*lint --e{715}*/ 414 { /*lint --e{715}*/ 415 SCIP_HEURDATA* heurdata; 416 417 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 418 419 /* free heuristic data */ 420 heurdata = SCIPheurGetData(heur); 421 assert(heurdata != NULL); 422 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) ); 423 424 /* free random number generator */ 425 SCIPfreeRandom(scip, &heurdata->randnumgen); 426 427 return SCIP_OKAY; 428 } 429 430 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */ 431 static 432 SCIP_DECL_HEURINITSOL(heurInitsolRandrounding) 433 { 434 SCIP_HEURDATA* heurdata; 435 436 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 437 438 heurdata = SCIPheurGetData(heur); 439 assert(heurdata != NULL); 440 heurdata->lastlp = -1; 441 442 /* change the heuristic's timingmask, if it should be called only once per node */ 443 if( heurdata->oncepernode ) 444 SCIPheurSetTimingmask(heur, SCIP_HEURTIMING_AFTERLPNODE); 445 446 return SCIP_OKAY; 447 } 448 449 450 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */ 451 static 452 SCIP_DECL_HEUREXITSOL(heurExitsolRandrounding) 453 { 454 /* reset the timing mask to its default value */ 455 SCIPheurSetTimingmask(heur, HEUR_TIMING); 456 457 return SCIP_OKAY; 458 } 459 460 /** execution method of primal heuristic */ 461 static 462 SCIP_DECL_HEUREXEC(heurExecRandrounding) /*lint --e{715}*/ 463 { /*lint --e{715}*/ 464 SCIP_HEURDATA* heurdata; 465 SCIP_Bool propagate; 466 467 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 468 assert(result != NULL); 469 assert(SCIPhasCurrentNodeLP(scip)); 470 471 *result = SCIP_DIDNOTRUN; 472 473 /* only call heuristic, if an optimal LP solution is at hand */ 474 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 475 return SCIP_OKAY; 476 477 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */ 478 if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) ) 479 return SCIP_OKAY; 480 481 /* get heuristic data */ 482 heurdata = SCIPheurGetData(heur); 483 assert(heurdata != NULL); 484 485 /* don't call heuristic, if we have already processed the current LP solution */ 486 if( SCIPgetNLPs(scip) == heurdata->lastlp ) 487 return SCIP_OKAY; 488 489 propagate = (!heurdata->propagateonlyroot || SCIPgetDepth(scip) == 0); 490 491 /* try to round LP solution */ 492 SCIP_CALL( performLPRandRounding(scip, heurdata, heurtiming, propagate, result) ); 493 494 return SCIP_OKAY; 495 } 496 497 /* 498 * heuristic specific interface methods 499 */ 500 501 /** creates the rand rounding heuristic and includes it in SCIP */ 502 SCIP_RETCODE SCIPincludeHeurRandrounding( 503 SCIP* scip /**< SCIP data structure */ 504 ) 505 { 506 SCIP_HEURDATA* heurdata; 507 SCIP_HEUR* heur; 508 509 /* create heuristic data */ 510 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 511 512 /* include primal heuristic */ 513 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 514 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 515 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecRandrounding, heurdata) ); 516 assert(heur != NULL); 517 518 /* set non-NULL pointers to callback methods */ 519 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyRandrounding) ); 520 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitRandrounding) ); 521 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitRandrounding) ); 522 SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolRandrounding) ); 523 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolRandrounding) ); 524 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeRandrounding) ); 525 526 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/oncepernode", 527 "should the heuristic only be called once per node?", 528 &heurdata->oncepernode, TRUE, DEFAULT_ONCEPERNODE, NULL, NULL) ); 529 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usesimplerounding", "should the heuristic apply the variable lock strategy of simple rounding, if possible?", 530 &heurdata->usesimplerounding, TRUE, DEFAULT_USESIMPLEROUNDING, NULL, NULL) ); 531 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/propagateonlyroot", 532 "should the probing part of the heuristic be applied exclusively at the root node?", 533 &heurdata->propagateonlyroot, TRUE, DEFAULT_PROPAGATEONLYROOT, NULL, NULL) ); 534 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds", 535 "limit of rounds for each propagation call", 536 &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, 537 -1, INT_MAX, NULL, NULL) ); 538 return SCIP_OKAY; 539 } 540