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 prop_rootredcost.c 26 * @ingroup DEFPLUGINS_PROP 27 * @brief reduced cost strengthening using root node reduced costs and the cutoff bound 28 * @author Tobias Achterberg 29 * @author Stefan Heinz 30 * 31 * This propagator uses the root reduced cost to (globally) propagate against the cutoff bound. The propagator checks if 32 * the variables with non-zero root reduced cost can exceed the cutoff bound. If this is the case the corresponding 33 * bound can be tightened. 34 * 35 * The propagate is performed during the search any time a new cutoff bound (primal solution) is found. 36 * 37 * @todo do not sort the variables; just store the cutoff bound which leads to a fixing. If that appears loop over all 38 * variables and fix and store the next cutoff bound which leads to an fixing 39 * @todo resolve the root LP in case of repropagation and update root reduced costs use root LP counter to check if new 40 * best root combinations might be available 41 */ 42 43 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 44 45 #include "scip/prop_rootredcost.h" 46 #include "scip/pub_message.h" 47 #include "scip/pub_misc_sort.h" 48 #include "scip/pub_prop.h" 49 #include "scip/pub_var.h" 50 #include "scip/scip_general.h" 51 #include "scip/scip_lp.h" 52 #include "scip/scip_mem.h" 53 #include "scip/scip_message.h" 54 #include "scip/scip_numerics.h" 55 #include "scip/scip_param.h" 56 #include "scip/scip_pricer.h" 57 #include "scip/scip_prob.h" 58 #include "scip/scip_probing.h" 59 #include "scip/scip_prop.h" 60 #include "scip/scip_solvingstats.h" 61 #include "scip/scip_tree.h" 62 #include "scip/scip_var.h" 63 #include <string.h> 64 65 /**@name Propagator properties 66 * 67 * @{ 68 */ 69 70 #define PROP_NAME "rootredcost" 71 #define PROP_DESC "reduced cost strengthening using root node reduced costs and the cutoff bound" 72 #define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_AFTERLPLOOP 73 #define PROP_PRIORITY +10000000 /**< propagator priority */ 74 #define PROP_FREQ 1 /**< propagator frequency */ 75 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */ 76 77 /**@} */ 78 79 /**@name Default parameter values 80 * 81 * @{ 82 */ 83 #define DEFAULT_ONLYBINARY FALSE /**< should only binary variables be propagated? */ 84 #define DEFAULT_FORCE FALSE /**< should the propagator be forced even if active pricer are present? Note that 85 * the reductions are always valid, but installing an upper bound on priced 86 * variables may lead to problems in pricing (existing variables at their upper 87 * bound may be priced again since they may have negative reduced costs) */ 88 89 /**@} */ 90 91 92 /* 93 * Data structures 94 */ 95 96 /** propagator data */ 97 struct SCIP_PropData 98 { 99 SCIP_VAR** redcostvars; /**< variables with non-zero root reduced cost */ 100 SCIP_Real lastcutoffbound; /**< cutoff bound for which the root reduced costs were already processed */ 101 int nredcostvars; /**< number of variables with non-zero root reduced cost */ 102 int nredcostbinvars; /**< number of binary variables with non-zero root reduced cost */ 103 int glbfirstnonfixed; /**< index of first globally non-fixed binary variable */ 104 SCIP_Bool initialized; /**< is the propagator data initialized */ 105 SCIP_Bool onlybinary; /**< should only binary variables be propagated? */ 106 SCIP_Bool force; /**< should the propagator be forced even if active pricer are present? */ 107 }; 108 109 110 /**@name Local methods 111 * 112 * @{ 113 */ 114 115 /** reset structure memember of propagator data structure */ 116 static 117 void propdataReset( 118 SCIP_PROPDATA* propdata /**< propagator data to reset */ 119 ) 120 { 121 propdata->redcostvars = NULL; 122 propdata->lastcutoffbound = SCIP_INVALID; 123 propdata->nredcostvars = 0; 124 propdata->nredcostbinvars = 0; 125 propdata->glbfirstnonfixed = 0; 126 propdata->initialized = FALSE; 127 } 128 129 /** compare variables with non-zero reduced cost w.r.t. 130 * (i) the cutoff bound which would lead to a fixing 131 * (ii) variable problem index; 132 */ 133 static 134 SCIP_DECL_SORTPTRCOMP(varCompRedcost) 135 { 136 SCIP_VAR* var1 = (SCIP_VAR*)elem1; 137 SCIP_VAR* var2 = (SCIP_VAR*)elem2; 138 SCIP_Real key1; 139 SCIP_Real key2; 140 141 assert(SCIPvarIsBinary(var1)); 142 assert(SCIPvarGetBestRootRedcost(var1) != 0.0); 143 144 assert(SCIPvarIsBinary(var2)); 145 assert(SCIPvarGetBestRootRedcost(var2) != 0.0); 146 147 /* collect sorting key for both variables */ 148 key1 = REALABS(SCIPvarGetBestRootRedcost(var1)) + SCIPvarGetBestRootLPObjval(var1); 149 key2 = REALABS(SCIPvarGetBestRootRedcost(var2)) + SCIPvarGetBestRootLPObjval(var2); 150 151 if( key1 < key2 ) 152 return -1; 153 else if( key1 > key2 ) 154 return +1; 155 156 /* second criteria use the problem index 157 * 158 * @note The problem index is unique. That means the resulting sorting is unique. 159 */ 160 return SCIPvarCompare(var1, var2); 161 } 162 163 /** create propagator data structure */ 164 static 165 SCIP_RETCODE propdataCreate( 166 SCIP* scip, /**< SCIP data structure */ 167 SCIP_PROPDATA** propdata /**< pointer to store the created propagator data */ 168 ) 169 { 170 SCIP_CALL( SCIPallocBlockMemory(scip, propdata) ); 171 172 propdataReset(*propdata); 173 174 return SCIP_OKAY; 175 } 176 177 /** counts the number of variables with non-zero root reduced cost */ 178 static 179 int countNonZeroRootRedcostVars( 180 SCIP* scip, /**< SCIP data structure */ 181 SCIP_VAR** vars, /**< variable array */ 182 int nvars /**< number of variables */ 183 ) 184 { 185 int count; 186 int v; 187 188 count = 0; 189 190 /* count number of variables with non-zero root reduced cost */ 191 for( v = 0; v < nvars; ++v ) 192 { 193 SCIP_Real redcost; 194 195 assert(vars[v] != NULL); 196 197 redcost = SCIPvarGetBestRootRedcost(vars[v]); 198 if( !SCIPisDualfeasZero(scip, redcost) ) 199 count++; 200 } 201 202 return count; 203 } 204 205 /** free propagator data */ 206 static 207 SCIP_RETCODE propdataExit( 208 SCIP* scip, /**< SCIP data structure */ 209 SCIP_PROPDATA* propdata /**< propagator data */ 210 ) 211 { 212 int v; 213 214 /* release all variables */ 215 for( v = 0; v < propdata->nredcostvars; ++v ) 216 { 217 SCIP_CALL( SCIPreleaseVar(scip, &propdata->redcostvars[v]) ); 218 } 219 220 /* free memory for non-zero reduced cost variables */ 221 SCIPfreeBlockMemoryArrayNull(scip, &propdata->redcostvars, propdata->nredcostvars); 222 223 propdataReset(propdata); 224 225 return SCIP_OKAY; 226 } 227 228 /** initializate the propagator */ 229 static 230 SCIP_RETCODE propdataInit( 231 SCIP* scip, /**< SCIP data structure */ 232 SCIP_PROPDATA* propdata /**< propagator data */ 233 ) 234 { 235 SCIP_VAR** vars; 236 int nvars; 237 int nbinvars; 238 int nredcostvars; 239 int nredcostbinvars; 240 int v; 241 242 assert(scip != NULL); 243 assert(propdata != NULL); 244 245 /* check if the propagator data structure is already initialized */ 246 if( propdata->initialized ) 247 return SCIP_OKAY; 248 249 /* get problem variables */ 250 vars = SCIPgetVars(scip); 251 nvars = SCIPgetNVars(scip); 252 nbinvars = SCIPgetNBinVars(scip); 253 254 /* count binary variables with non-zero root reduced cost */ 255 nredcostbinvars = countNonZeroRootRedcostVars(scip, vars, nbinvars); 256 SCIPdebugMsg(scip, "There are %d (poor) binary variables with non-zero root reduced cost <%s>.\n", nredcostbinvars, SCIPgetProbName(scip)); 257 258 /* count non-binary variables with non-zero root reduced cost */ 259 nredcostvars = countNonZeroRootRedcostVars(scip, &vars[nbinvars], nvars - nbinvars); 260 261 nredcostvars += nredcostbinvars; 262 263 /* collect the variables with non-zero reduced costs */ 264 if( nredcostvars > 0 ) 265 { 266 int k; 267 268 k = 0; 269 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->redcostvars, nredcostvars) ); 270 271 SCIPdebugMsg(scip, "Store non-zero root reduced cost variables at address <%p>.\n", (void*)propdata->redcostvars); 272 273 for( v = 0; v < nvars; ++v ) 274 { 275 SCIP_Real redcost; 276 SCIP_VAR* var; 277 278 var = vars[v]; 279 redcost = SCIPvarGetBestRootRedcost(var); 280 281 if( SCIPisDualfeasZero(scip, redcost) ) 282 continue; 283 284 assert(k < nredcostvars); 285 286 /* check if one of the non-binary variables is implicit binary */ 287 if( k >= nredcostbinvars && SCIPvarIsBinary(var) ) 288 { 289 /* move the first non-binary variable to end of the array */ 290 propdata->redcostvars[k] = propdata->redcostvars[nredcostbinvars]; 291 292 /* place the binary variable at the end of the binary section */ 293 propdata->redcostvars[nredcostbinvars] = var; 294 nredcostbinvars++; 295 } 296 else 297 propdata->redcostvars[k] = var; 298 299 /* captures the variable */ 300 SCIP_CALL( SCIPcaptureVar(scip, var) ) ; 301 302 k++; 303 304 /* check if already visited all variable with non-zero redcostective coefficient */ 305 if( k == nredcostvars ) 306 break; 307 } 308 309 /* sort binary variables with respect to their cutoff bound which would lead to an fixing; this order can be used 310 * to efficiently propagate the binary variables 311 */ 312 SCIPsortDownPtr((void**)propdata->redcostvars, varCompRedcost, nredcostbinvars); 313 314 assert(k == nredcostvars); 315 316 SCIPdebugMsg(scip, "variables with non-zero redcostective coefficient: %d binaries, %d non-binaries\n", nredcostbinvars, nredcostvars - nredcostbinvars); 317 } 318 319 propdata->nredcostvars = nredcostvars; 320 propdata->nredcostbinvars = nredcostbinvars; 321 propdata->glbfirstnonfixed = 0; 322 propdata->lastcutoffbound = SCIPinfinity(scip); 323 propdata->initialized = TRUE; 324 325 return SCIP_OKAY; 326 } 327 328 /** propagates the root reduced cost against the cutoff bound for the given variable */ 329 static 330 SCIP_RETCODE propagateRootRedcostVar( 331 SCIP* scip, /**< SCIP data structure */ 332 SCIP_VAR* var, /**< variable to propagate */ 333 SCIP_Real cutoffbound, /**< cutoff bound to use */ 334 SCIP_Bool* infeasible, /**< pointer to store whether the new domain is empty */ 335 SCIP_Bool* tightened /**< pointer to store if the bound was tightened */ 336 ) 337 { 338 SCIP_Real rootsol; 339 SCIP_Real rootredcost; 340 SCIP_Real rootlpobjval; 341 SCIP_Real newbd; 342 343 rootredcost = SCIPvarGetBestRootRedcost(var); 344 assert(rootredcost != SCIP_INVALID); /*lint !e777*/ 345 346 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to 347 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert 348 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong 349 * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect. 350 */ 351 assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasZero(scip, rootredcost)); 352 353 rootsol = SCIPvarGetBestRootSol(var); 354 rootlpobjval = SCIPvarGetBestRootLPObjval(var); 355 356 /* calculate reduced cost based bound */ 357 newbd = rootsol + (cutoffbound - rootlpobjval) / rootredcost; 358 359 if( SCIPisDualfeasPositive(scip, rootredcost) ) 360 { 361 assert(SCIPisFeasLE(scip, rootsol, SCIPvarGetLbGlobal(var))); /* lb might have been increased in the meantime */ 362 363 /* strengthen upper bound */ 364 SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, newbd, FALSE, infeasible, tightened) ); 365 } 366 else 367 { 368 assert(!SCIPisLPDualReliable(scip) || SCIPisDualfeasNegative(scip, rootredcost)); 369 assert(SCIPisFeasGE(scip, rootsol, SCIPvarGetUbGlobal(var))); /* ub might have been decreased in the meantime */ 370 371 /* strengthen lower bound */ 372 SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, newbd, FALSE, infeasible, tightened) ); 373 } 374 375 return SCIP_OKAY; 376 } 377 378 /** propagate binary variables with non-zero root reduced cost */ 379 static 380 SCIP_RETCODE propagateBinaryBestRootRedcost( 381 SCIP* scip, /**< SCIP data structure */ 382 SCIP_PROPDATA* propdata, /**< propagator data structure */ 383 SCIP_Real cutoffbound, /**< cutoff bound to use */ 384 int* nchgbds, /**< pointer to store the number of bound changes */ 385 SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */ 386 ) 387 { 388 SCIP_VAR** redcostvars; 389 int v; 390 391 assert(!(*cutoff)); 392 393 /* the binary variables are stored in the beginning of the variable array; these variables are sorted w.r.t. cutoff 394 * bound which would lead to a fixing; that give us an abort criteria (see below) 395 */ 396 redcostvars = propdata->redcostvars; 397 assert(redcostvars != NULL); 398 399 #ifndef NDEBUG 400 /* check that the binary variables are correctly sorted 401 * 402 * @note In case the assertion fails it indicates that a new LP root solving arose after we initialized the 403 * propagator; The new LP solution destroyed the sorting of the binary variables since the reduced cost of the 404 * variables changed. This could lead to potentially missing a domain reductions. Currently, it is not possible to 405 * check if a new root LP was solved, changing the root reduced costs. This case, however, should not happen in the 406 * current SCIP version. 407 */ 408 for( v = 1; v < propdata->nredcostbinvars; ++v ) 409 assert(varCompRedcost(redcostvars[v-1], redcostvars[v]) == 1); 410 411 /* check that the variables before glbfirstnonfixed are globally fixed */ 412 for( v = 0; v < propdata->glbfirstnonfixed; ++v ) 413 { 414 SCIP_VAR* var; 415 416 var = redcostvars[v]; 417 assert(var != NULL); 418 419 assert(SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5); 420 } 421 #endif 422 423 /* propagate binary variables */ 424 for( v = propdata->glbfirstnonfixed; v < propdata->nredcostbinvars; ++v ) 425 { 426 SCIP_VAR* var; 427 SCIP_Bool tightened; 428 429 var = redcostvars[v]; 430 assert(var != NULL); 431 432 /* check if the variables is already globally fixed; if so continue with the next potential candidate */ 433 if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5) 434 continue; 435 436 /* try to tighten the variable bound */ 437 SCIP_CALL( propagateRootRedcostVar(scip, var, cutoffbound, cutoff, &tightened) ); 438 439 if( tightened ) 440 { 441 /* @note The variable might not be globally fixed right away since this would destroy the local internal data 442 * structure of a search node; the bound change is in that case pending; hence we cannot assert that the 443 * variable is globally fixed 444 */ 445 assert(!(*cutoff)); 446 447 SCIPdebugMsg(scip, "globally fixed binary variable <%s> [%g,%g] bestroot sol <%g>, redcost <%g>, lpobj <%g>\n", 448 SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), 449 SCIPvarGetBestRootSol(var), SCIPvarGetBestRootRedcost(var), SCIPvarGetBestRootLPObjval(var) ); 450 451 (*nchgbds)++; 452 } 453 else 454 { 455 assert(!tightened); 456 457 /* The binary variables are sorted in non-increasing manner w.r.t. their cutoff bound which would lead to a 458 * global fixing; That is, abs(rootredcost) + rootlpobjval. Depending on the sign of the reduced cost the 459 * following two cases can arise for binary variables which are not fixed globally yet: 460 * 461 * - redcost > 0 --> newub = 0.0 + (cutoffbound - lpobjval) / redcost --> newub = 0 <=> cutoffbound < redcost + lpobjval = sorting key 462 * - redcost < 0 --> newlb = 1.0 + (cutoffbound - lpobjval) / redcost --> newlb = 1 <=> cutoffbound < -redcost + lpobjval = sorting key 463 * 464 * Due to the order of the binary variables it follows if one binary variable cannot be fixed anymore all the 465 * remaining once can also not be fixed since these have only an smaller or equal cutoff bound which would lead 466 * to global fixing. Hence, we can break that loop. 467 * 468 * Note that variables with non-zero reduced cost are sitting at one of their bound. That is the lower one if 469 * the reduced cost are positive and the upper bound if the reduced cost are negative. For binary variables 470 * that is 0 for the lower bound and 1 for the upper bound. 471 */ 472 SCIPdebugMsg(scip, "interrupt propagation for binary variables after %d from %d binary variables\n", 473 v, propdata->nredcostbinvars); 474 475 if( *cutoff ) 476 { 477 SCIPdebugMsg(scip, "detected cutoff: binary variable <%s> [%g,%g], redcost <%g>, rootsol <%g>, rootlpobjval <%g>\n", 478 SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), 479 SCIPvarGetBestRootRedcost(var), SCIPvarGetBestRootSol(var), SCIPvarGetBestRootLPObjval(var)); 480 } 481 482 break; 483 } 484 } 485 /* store the index of the variable which is not globally fixed */ 486 propdata->glbfirstnonfixed = v; 487 488 #if 0 /* due to numerics it might be that the abort criteria did not work correctly, because the sorting mechanism may 489 * have evaluated variables with a really small difference in their reduced cost values but with really huge 490 * lpobjval as the same 491 */ 492 #ifndef NDEBUG 493 /* check that the abort criteria works; that means none of the remaining binary variables can be fixed */ 494 for( ; v < propdata->nredcostbinvars && !(*cutoff); ++v ) 495 { 496 SCIP_VAR* var; 497 SCIP_Bool tightened; 498 499 var = redcostvars[v]; 500 assert(var != NULL); 501 502 /* check if the variables is already globally fixed; if so continue with the potential candidate */ 503 if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5) 504 continue; 505 506 /* try to tighten the variable bound */ 507 SCIP_CALL( propagateRootRedcostVar(scip, var, cutoffbound, cutoff, &tightened) ); 508 assert(!tightened); 509 assert(!(*cutoff)); 510 } 511 #endif 512 #endif 513 514 return SCIP_OKAY; 515 } 516 517 /**@} */ 518 519 520 /**@name Callback methods of propagator 521 * 522 * @{ 523 */ 524 525 /** copy method for propagator plugins (called when SCIP copies plugins) */ 526 static 527 SCIP_DECL_PROPCOPY(propCopyRootredcost) 528 { /*lint --e{715}*/ 529 assert(scip != NULL); 530 assert(prop != NULL); 531 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 532 533 /* call inclusion method of propagator */ 534 SCIP_CALL( SCIPincludePropRootredcost(scip) ); 535 536 return SCIP_OKAY; 537 } 538 539 /** destructor of propagator to free user data (called when SCIP is exiting) */ 540 static 541 SCIP_DECL_PROPFREE(propFreeRootredcost) 542 { /*lint --e{715}*/ 543 SCIP_PROPDATA* propdata; 544 545 /* free propagator data */ 546 propdata = SCIPpropGetData(prop); 547 assert(propdata != NULL); 548 assert(propdata->redcostvars == NULL); 549 550 SCIPfreeBlockMemory(scip, &propdata); 551 SCIPpropSetData(prop, NULL); 552 553 return SCIP_OKAY; 554 } 555 556 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */ 557 static 558 SCIP_DECL_PROPEXITSOL(propExitsolRootredcost) 559 { /*lint --e{715}*/ 560 SCIP_PROPDATA* propdata; 561 562 propdata = SCIPpropGetData(prop); 563 assert(propdata != NULL); 564 565 /* reset propagator data structure */ 566 SCIP_CALL( propdataExit(scip, propdata) ); 567 568 return SCIP_OKAY; 569 } 570 571 /** execution method of propagator */ 572 static 573 SCIP_DECL_PROPEXEC(propExecRootredcost) 574 { /*lint --e{715}*/ 575 SCIP_PROPDATA* propdata; 576 SCIP_VAR** redcostvars; 577 SCIP_Real cutoffbound; 578 SCIP_Real lpobjval; 579 SCIP_Bool cutoff; 580 int nredcostvars; 581 int nchgbds; 582 int v; 583 584 *result = SCIP_DIDNOTRUN; 585 586 /* in case we have a zero objective fucntion, we skip the root reduced cost propagator */ 587 if( SCIPgetNObjVars(scip) == 0 ) 588 return SCIP_OKAY; 589 590 /* propagator can only be applied during solving stage */ 591 if( SCIPgetStage(scip) != SCIP_STAGE_SOLVING ) 592 return SCIP_OKAY; 593 594 /* the propagator should run in all nodes except the root node; for the root node the redcost propagator does 595 * the job already 596 */ 597 if( SCIPgetDepth(scip) < 1 ) 598 return SCIP_OKAY; 599 600 /* first check root LP objective value if it exists */ 601 lpobjval = SCIPgetLPRootObjval(scip); 602 if( lpobjval == SCIP_INVALID ) /*lint !e777*/ 603 return SCIP_OKAY; 604 605 /* do not run in probing mode since this propagator changes global variable bounds */ 606 if( SCIPinProbing(scip) ) 607 return SCIP_OKAY; 608 609 /* do not run if propagation w.r.t. objective is not allowed */ 610 if( !SCIPallowWeakDualReds(scip) ) 611 return SCIP_OKAY; 612 613 /* get propagator data */ 614 propdata = SCIPpropGetData(prop); 615 assert(propdata != NULL); 616 617 /* do nothing if active pricer are present and force flag is not TRUE */ 618 if( !propdata->force && SCIPgetNActivePricers(scip) > 0 ) 619 return SCIP_OKAY; 620 621 /* get current cutoff bound */ 622 cutoffbound = SCIPgetCutoffbound(scip); 623 624 /* reduced cost strengthening can only be applied, if we have a finite upper bound on the LP value */ 625 if( SCIPisInfinity(scip, cutoffbound) ) 626 return SCIP_OKAY; 627 628 /* initialize propagator data structure */ 629 SCIP_CALL( propdataInit(scip, propdata) ); 630 assert(cutoffbound <= propdata->lastcutoffbound); 631 632 if( cutoffbound == propdata->lastcutoffbound ) /*lint !e777*/ 633 return SCIP_OKAY; 634 635 /* get variables */ 636 redcostvars = propdata->redcostvars; 637 nredcostvars = propdata->nredcostvars; 638 639 /* since no variables has non-zero reduced cost do nothing */ 640 if( nredcostvars == 0 ) 641 return SCIP_OKAY; 642 643 /* store cutoff bound to remember later that for that particular cutoff bound the propagation was already 644 * preformed 645 */ 646 propdata->lastcutoffbound = cutoffbound; 647 648 SCIPdebugMsg(scip, "searching for root reduced cost fixings\n"); 649 SCIPdebugMsg(scip, "-> cutoffbound <%g>\n", cutoffbound); 650 SCIPdebugMsg(scip, "-> LP objective value <%g>\n", lpobjval); 651 652 *result = SCIP_DIDNOTFIND; 653 nchgbds = 0; 654 cutoff = FALSE; 655 656 /* propagate the binary variables with non-zero root reduced cost */ 657 SCIP_CALL( propagateBinaryBestRootRedcost(scip, propdata, cutoffbound, &nchgbds, &cutoff) ); 658 659 if( !propdata->onlybinary ) 660 { 661 /* check reduced costs for non-binary variables that were columns of the root LP */ 662 for( v = propdata->nredcostbinvars; v < nredcostvars && !cutoff; ++v ) 663 { 664 SCIP_VAR* var; 665 SCIP_Bool tightened; 666 667 var = redcostvars[v]; 668 assert(var != NULL); 669 670 /* try to tighten the variable bound */ 671 SCIP_CALL( propagateRootRedcostVar(scip, var, cutoffbound, &cutoff, &tightened) ); 672 673 if( tightened ) 674 nchgbds++; 675 } 676 } 677 678 /* evaluate propagation results */ 679 if( cutoff ) 680 { 681 /* we are done with solving since the cutoff is w.r.t. a global bound change; cutoff root node */ 682 SCIP_CALL( SCIPcutoffNode(scip, SCIPgetRootNode(scip)) ); 683 (*result) = SCIP_CUTOFF; 684 } 685 else if( nchgbds > 0 ) 686 (*result) = SCIP_REDUCEDDOM; 687 688 SCIPdebugMsg(scip, "tightened %d variable domains (%u cutoff)\n", nchgbds, cutoff); 689 690 return SCIP_OKAY; 691 } 692 693 /**@} */ 694 695 696 /** creates the root node reduced cost strengthening propagator and includes it in SCIP */ 697 SCIP_RETCODE SCIPincludePropRootredcost( 698 SCIP* scip /**< SCIP data structure */ 699 ) 700 { 701 SCIP_PROPDATA* propdata; 702 SCIP_PROP* prop; 703 704 /* create rootredcost propagator data */ 705 SCIP_CALL( propdataCreate(scip, &propdata) ); 706 707 /* include propagator */ 708 SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING, 709 propExecRootredcost, propdata) ); 710 711 assert(prop != NULL); 712 713 /* set optional callbacks via setter functions */ 714 SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyRootredcost) ); 715 SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeRootredcost) ); 716 SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolRootredcost) ); 717 718 SCIP_CALL( SCIPaddBoolParam(scip, 719 "propagating/" PROP_NAME "/onlybinary", 720 "should only binary variables be propagated?", 721 &propdata->onlybinary, TRUE, DEFAULT_ONLYBINARY, NULL, NULL) ); 722 SCIP_CALL( SCIPaddBoolParam(scip, 723 "propagating/" PROP_NAME "/force", 724 "should the propagator be forced even if active pricer are present?", 725 &propdata->force, TRUE, DEFAULT_FORCE, NULL, NULL) ); 726 727 return SCIP_OKAY; 728 } 729