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_simplerounding.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief simple and fast LP rounding heuristic 28 * @author Tobias Achterberg 29 * @author Marc Pfetsch 30 * 31 * The heuristic also tries to round relaxation solutions if available. 32 */ 33 34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 35 36 #include "blockmemshell/memory.h" 37 #include "scip/heur_simplerounding.h" 38 #include "scip/pub_heur.h" 39 #include "scip/pub_message.h" 40 #include "scip/pub_var.h" 41 #include "scip/scip_branch.h" 42 #include "scip/scip_heur.h" 43 #include "scip/scip_lp.h" 44 #include "scip/scip_mem.h" 45 #include "scip/scip_message.h" 46 #include "scip/scip_numerics.h" 47 #include "scip/scip_param.h" 48 #include "scip/scip_prob.h" 49 #include "scip/scip_sol.h" 50 #include "scip/scip_solvingstats.h" 51 #include "scip/scip_var.h" 52 #include <string.h> 53 54 #define HEUR_NAME "simplerounding" 55 #define HEUR_DESC "simple and fast LP rounding heuristic" 56 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING 57 #define HEUR_PRIORITY -30 58 #define HEUR_FREQ 1 59 #define HEUR_FREQOFS 0 60 #define HEUR_MAXDEPTH -1 61 #define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_DURINGPRICINGLOOP 62 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */ 63 64 #define DEFAULT_ONCEPERNODE FALSE /**< should the heuristic only be called once per node? */ 65 66 /* locally defined heuristic data */ 67 struct SCIP_HeurData 68 { 69 SCIP_SOL* sol; /**< working solution */ 70 SCIP_Longint lastlp; /**< last LP number where the heuristic was applied */ 71 int nroundablevars; /**< number of variables that can be rounded (-1 if not yet calculated) */ 72 SCIP_Bool oncepernode; /**< should the heuristic only be called once per node? */ 73 }; 74 75 76 /* 77 * Local methods 78 */ 79 80 /** perform rounding */ 81 static 82 SCIP_RETCODE performSimpleRounding( 83 SCIP* scip, /**< SCIP main data structure */ 84 SCIP_SOL* sol, /**< solution to round */ 85 SCIP_VAR** cands, /**< candidate variables */ 86 SCIP_Real* candssol, /**< solutions of candidate variables */ 87 int ncands, /**< number of candidates */ 88 SCIP_RESULT* result /**< pointer to store the result of the heuristic call */ 89 ) 90 { 91 int c; 92 int nunroundableimplints = 0; 93 94 /* round all roundable fractional columns in the corresponding direction as long as no unroundable column was found */ 95 for (c = 0; c < ncands; ++c) 96 { 97 SCIP_VAR* var; 98 SCIP_Real oldsolval; 99 SCIP_Real newsolval; 100 SCIP_Bool mayrounddown; 101 SCIP_Bool mayroundup; 102 103 oldsolval = candssol[c]; 104 assert( ! SCIPisFeasIntegral(scip, oldsolval) ); 105 var = cands[c]; 106 assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN ); 107 mayrounddown = SCIPvarMayRoundDown(var); 108 mayroundup = SCIPvarMayRoundUp(var); 109 SCIPdebugMsg(scip, "simple rounding heuristic: var <%s>, val=%g, rounddown=%u, roundup=%u\n", 110 SCIPvarGetName(var), oldsolval, mayrounddown, mayroundup); 111 112 /* choose rounding direction */ 113 if ( mayrounddown && mayroundup ) 114 { 115 /* we can round in both directions: round in objective function direction */ 116 if ( SCIPvarGetObj(var) >= 0.0 ) 117 newsolval = SCIPfeasFloor(scip, oldsolval); 118 else 119 newsolval = SCIPfeasCeil(scip, oldsolval); 120 } 121 else if ( mayrounddown ) 122 newsolval = SCIPfeasFloor(scip, oldsolval); 123 else if ( mayroundup ) 124 newsolval = SCIPfeasCeil(scip, oldsolval); 125 else if( SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT ) 126 { 127 ++nunroundableimplints; 128 continue; 129 } 130 else 131 break; 132 133 /* store new solution value */ 134 SCIP_CALL( SCIPsetSolVal(scip, sol, var, newsolval) ); 135 } 136 137 /* check, if rounding was successful */ 138 if( c == ncands ) 139 { 140 SCIP_Bool stored; 141 SCIP_Bool checklprows; 142 143 /* unroundable implicit integers are adjusted. LP rows must be checked afterwards */ 144 if( nunroundableimplints > 0 ) 145 { 146 SCIP_CALL( SCIPadjustImplicitSolVals(scip, sol, TRUE) ); 147 checklprows = TRUE; 148 } 149 else 150 checklprows = FALSE; 151 152 if( SCIPallColsInLP(scip) ) 153 { 154 /* check solution for feasibility, and add it to solution store if possible 155 * integrality need not be checked, because all fractional 156 * variables were already moved in feasible direction to the next integer 157 * 158 * feasibility of LP rows must be checked again at the presence of 159 * unroundable, implicit integer variables with fractional LP solution 160 * value 161 */ 162 SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, FALSE, FALSE, checklprows, &stored) ); 163 } 164 else 165 { 166 /* if there are variables which are not present in the LP, e.g., for 167 * column generation, we need to check their bounds 168 */ 169 SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, TRUE, FALSE, checklprows, &stored) ); 170 } 171 172 if( stored ) 173 { 174 #ifdef SCIP_DEBUG 175 SCIPdebugMsg(scip, "found feasible rounded solution:\n"); 176 SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) ); 177 #endif 178 *result = SCIP_FOUNDSOL; 179 } 180 } 181 return SCIP_OKAY; 182 } 183 184 /** perform LP-rounding */ 185 static 186 SCIP_RETCODE performLPSimpleRounding( 187 SCIP* scip, /**< SCIP main data structure */ 188 SCIP_HEURDATA* heurdata, /**< heuristic data */ 189 SCIP_HEURTIMING heurtiming, /**< heuristic timing mask */ 190 SCIP_RESULT* result /**< pointer to store the result of the heuristic call */ 191 ) 192 { 193 SCIP_SOL* sol; 194 SCIP_VAR** lpcands; 195 SCIP_Real* lpcandssol; 196 SCIP_Longint nlps; 197 int nlpcands; 198 int nfracimplvars; 199 200 /* only call heuristic, if an optimal LP solution is at hand */ 201 if ( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 202 return SCIP_OKAY; 203 204 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */ 205 if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) ) 206 return SCIP_OKAY; 207 208 /* get fractional variables, that should be integral */ 209 SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL, &nlpcands, NULL, &nfracimplvars) ); 210 211 /* only call heuristic, if LP solution is fractional; except we are called during pricing, in this case we 212 * want to detect a (mixed) integer (LP) solution which is primal feasible 213 */ 214 if ( nlpcands == 0 && heurtiming != SCIP_HEURTIMING_DURINGPRICINGLOOP ) 215 return SCIP_OKAY; 216 217 /* don't call heuristic, if there are more fractional variables than roundable ones. We do not consider 218 * fractional implicit integer variables here, because simple rounding may adjust those separately, 219 * even if they aren't roundable 220 */ 221 if ( nlpcands > heurdata->nroundablevars ) 222 return SCIP_OKAY; 223 224 /* get the working solution from heuristic's local data */ 225 sol = heurdata->sol; 226 assert( sol != NULL ); 227 228 /* copy the current LP solution to the working solution */ 229 SCIP_CALL( SCIPlinkLPSol(scip, sol) ); 230 231 /* don't call heuristic, if we have already processed the current LP solution */ 232 nlps = SCIPgetNLPs(scip); 233 if( nlps == heurdata->lastlp ) 234 return SCIP_OKAY; 235 heurdata->lastlp = nlps; 236 237 /* perform simple rounding */ 238 SCIPdebugMsg(scip, "executing simple LP-rounding heuristic, fractionals: %d + %d\n", nlpcands, nfracimplvars); 239 SCIP_CALL( performSimpleRounding(scip, sol, lpcands, lpcandssol, nlpcands + nfracimplvars, result) ); 240 241 return SCIP_OKAY; 242 } 243 244 /** perform relaxation solution rounding */ 245 static 246 SCIP_RETCODE performRelaxSimpleRounding( 247 SCIP* scip, /**< SCIP main data structure */ 248 SCIP_HEURDATA* heurdata, /**< heuristic data */ 249 SCIP_RESULT* result /**< pointer to store the result of the heuristic call */ 250 ) 251 { 252 SCIP_SOL* sol; 253 SCIP_VAR** vars; 254 SCIP_VAR** relaxcands; 255 SCIP_Real* relaxcandssol; 256 int nrelaxcands = 0; 257 int nbinvars; 258 int nintvars; 259 int nimplvars; 260 int ndiscretevars; 261 int v; 262 263 /* do not call heuristic if no relaxation solution is available */ 264 if ( ! SCIPisRelaxSolValid(scip) ) 265 return SCIP_OKAY; 266 267 /* get variables */ 268 SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, &nimplvars, NULL) ); 269 ndiscretevars = nbinvars + nintvars + nimplvars; /* consider binary, integral, and implicit integer variables */ 270 271 /* get storage */ 272 SCIP_CALL( SCIPallocBufferArray(scip, &relaxcands, ndiscretevars) ); 273 SCIP_CALL( SCIPallocBufferArray(scip, &relaxcandssol, ndiscretevars) ); 274 275 /* get fractional variables, that should be integral */ 276 for (v = 0; v < nbinvars + nintvars; ++v) 277 { 278 SCIP_Real val; 279 280 val = SCIPgetRelaxSolVal(scip, vars[v]); 281 if ( ! SCIPisFeasIntegral(scip, val) ) 282 { 283 relaxcands[nrelaxcands] = vars[v]; 284 relaxcandssol[nrelaxcands++] = val; 285 } 286 } 287 288 /* don't call heuristic, if there are more fractional variables than roundable ones. We explicitly 289 * do not consider implicit integer variables with fractional relaxation solution here 290 * because they may be feasibly adjusted, although they are not roundable 291 */ 292 if ( nrelaxcands > heurdata->nroundablevars ) 293 { 294 SCIPfreeBufferArray(scip, &relaxcands); 295 SCIPfreeBufferArray(scip, &relaxcandssol); 296 return SCIP_OKAY; 297 } 298 299 /* collect implicit integer variables with fractional solution value */ 300 for( v = nbinvars + nintvars; v < ndiscretevars; ++v ) 301 { 302 SCIP_Real val; 303 304 val = SCIPgetRelaxSolVal(scip, vars[v]); 305 if ( ! SCIPisFeasIntegral(scip, val) ) 306 { 307 relaxcands[nrelaxcands] = vars[v]; 308 relaxcandssol[nrelaxcands++] = val; 309 } 310 } 311 /* get the working solution from heuristic's local data */ 312 sol = heurdata->sol; 313 assert( sol != NULL ); 314 315 /* copy the current relaxation solution to the working solution */ 316 SCIP_CALL( SCIPlinkRelaxSol(scip, sol) ); 317 318 /* perform simple rounding */ 319 SCIPdebugMsg(scip, "executing simple rounding heuristic on relaxation solution: %d fractionals\n", nrelaxcands); 320 SCIP_CALL( performSimpleRounding(scip, sol, relaxcands, relaxcandssol, nrelaxcands, result) ); 321 322 /* free storage */ 323 SCIPfreeBufferArray(scip, &relaxcands); 324 SCIPfreeBufferArray(scip, &relaxcandssol); 325 326 return SCIP_OKAY; 327 } 328 329 330 /* 331 * Callback methods 332 */ 333 334 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 335 static 336 SCIP_DECL_HEURCOPY(heurCopySimplerounding) 337 { /*lint --e{715}*/ 338 assert(scip != NULL); 339 assert(heur != NULL); 340 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 341 342 /* call inclusion method of primal heuristic */ 343 SCIP_CALL( SCIPincludeHeurSimplerounding(scip) ); 344 345 return SCIP_OKAY; 346 } 347 348 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 349 static 350 SCIP_DECL_HEURFREE(heurFreeSimplerounding) /*lint --e{715}*/ 351 { /*lint --e{715}*/ 352 SCIP_HEURDATA* heurdata; 353 354 assert(heur != NULL); 355 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 356 assert(scip != NULL); 357 358 /* free heuristic data */ 359 heurdata = SCIPheurGetData(heur); 360 assert(heurdata != NULL); 361 SCIPfreeBlockMemory(scip, &heurdata); 362 SCIPheurSetData(heur, NULL); 363 364 return SCIP_OKAY; 365 } 366 367 368 /** initialization method of primal heuristic (called after problem was transformed) */ 369 static 370 SCIP_DECL_HEURINIT(heurInitSimplerounding) /*lint --e{715}*/ 371 { /*lint --e{715}*/ 372 SCIP_HEURDATA* heurdata; 373 374 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 375 heurdata = SCIPheurGetData(heur); 376 assert(heurdata != NULL); 377 378 /* create heuristic data */ 379 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) ); 380 heurdata->lastlp = -1; 381 heurdata->nroundablevars = -1; 382 383 return SCIP_OKAY; 384 } 385 386 387 /** deinitialization method of primal heuristic (called before transformed problem is freed) */ 388 static 389 SCIP_DECL_HEUREXIT(heurExitSimplerounding) /*lint --e{715}*/ 390 { /*lint --e{715}*/ 391 SCIP_HEURDATA* heurdata; 392 393 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 394 395 /* free heuristic data */ 396 heurdata = SCIPheurGetData(heur); 397 assert(heurdata != NULL); 398 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) ); 399 400 return SCIP_OKAY; 401 } 402 403 404 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */ 405 static 406 SCIP_DECL_HEURINITSOL(heurInitsolSimplerounding) 407 { 408 SCIP_HEURDATA* heurdata; 409 410 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 411 412 heurdata = SCIPheurGetData(heur); 413 assert(heurdata != NULL); 414 heurdata->lastlp = -1; 415 416 /* change the heuristic's timingmask, if it should be called only once per node */ 417 if( heurdata->oncepernode ) 418 SCIPheurSetTimingmask(heur, SCIP_HEURTIMING_AFTERLPNODE); 419 420 return SCIP_OKAY; 421 } 422 423 424 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */ 425 static 426 SCIP_DECL_HEUREXITSOL(heurExitsolSimplerounding) 427 { 428 /* reset the timing mask to its default value */ 429 SCIPheurSetTimingmask(heur, HEUR_TIMING); 430 431 return SCIP_OKAY; 432 } 433 434 435 /** execution method of primal heuristic */ 436 static 437 SCIP_DECL_HEUREXEC(heurExecSimplerounding) /*lint --e{715}*/ 438 { /*lint --e{715}*/ 439 SCIP_HEURDATA* heurdata; 440 441 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 442 assert(result != NULL); 443 assert(SCIPhasCurrentNodeLP(scip)); 444 445 *result = SCIP_DIDNOTRUN; 446 447 /* only call heuristic, if an optimal LP solution is at hand or if relaxation solution is available */ 448 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL && ! SCIPisRelaxSolValid(scip) ) 449 return SCIP_OKAY; 450 451 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */ 452 if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) ) 453 return SCIP_OKAY; 454 455 /* get heuristic data */ 456 heurdata = SCIPheurGetData(heur); 457 assert(heurdata != NULL); 458 459 /* don't call heuristic, if we have already processed the current LP solution but no relaxation solution is available */ 460 if ( SCIPgetNLPs(scip) == heurdata->lastlp && ! SCIPisRelaxSolValid(scip) ) 461 return SCIP_OKAY; 462 463 /* on our first call or after each pricing round, calculate the number of roundable variables */ 464 if( heurdata->nroundablevars == -1 || heurtiming == SCIP_HEURTIMING_DURINGPRICINGLOOP ) 465 { 466 SCIP_VAR** vars; 467 int nbinintvars; 468 int nroundablevars; 469 int i; 470 471 vars = SCIPgetVars(scip); 472 nbinintvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip); 473 nroundablevars = 0; 474 for( i = 0; i < nbinintvars; ++i ) 475 { 476 if( SCIPvarMayRoundDown(vars[i]) || SCIPvarMayRoundUp(vars[i]) ) 477 nroundablevars++; 478 } 479 heurdata->nroundablevars = nroundablevars; 480 } 481 482 /* don't call heuristic if there are no roundable variables; except we are called during pricing, in this case we 483 * want to detect a (mixed) integer (LP) solution which is primal feasible */ 484 if( heurdata->nroundablevars == 0 && heurtiming != SCIP_HEURTIMING_DURINGPRICINGLOOP ) 485 return SCIP_OKAY; 486 487 *result = SCIP_DIDNOTFIND; 488 489 /* try to round LP solution */ 490 SCIP_CALL( performLPSimpleRounding(scip, heurdata, heurtiming, result) ); 491 492 /* try to round relaxation solution */ 493 SCIP_CALL( performRelaxSimpleRounding(scip, heurdata, result) ); 494 495 return SCIP_OKAY; 496 } 497 498 /* 499 * heuristic specific interface methods 500 */ 501 502 /** creates the simple rounding heuristic and includes it in SCIP */ 503 SCIP_RETCODE SCIPincludeHeurSimplerounding( 504 SCIP* scip /**< SCIP data structure */ 505 ) 506 { 507 SCIP_HEURDATA* heurdata; 508 SCIP_HEUR* heur; 509 510 /* create heuristic data */ 511 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 512 513 /* include primal heuristic */ 514 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 515 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 516 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecSimplerounding, heurdata) ); 517 assert(heur != NULL); 518 519 /* set non-NULL pointers to callback methods */ 520 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopySimplerounding) ); 521 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitSimplerounding) ); 522 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitSimplerounding) ); 523 SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolSimplerounding) ); 524 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolSimplerounding) ); 525 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeSimplerounding) ); 526 527 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/oncepernode", 528 "should the heuristic only be called once per node?", 529 &heurdata->oncepernode, TRUE, DEFAULT_ONCEPERNODE, NULL, NULL) ); 530 531 return SCIP_OKAY; 532 } 533