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_redcost.c 26 * @ingroup DEFPLUGINS_PROP 27 * @brief propagator using the LP reduced cost and the cutoff bound 28 * @author Tobias Achterberg 29 * @author Stefan Heinz 30 * @author Matthias Miltenberger 31 * @author Michael Winkler 32 * 33 * This propagator uses the reduced cost of an optimal solved LP relaxation to propagate the variables against the 34 * cutoff bound. 35 */ 36 37 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 38 39 #include "lpi/type_lpi.h" 40 #include "scip/prop_redcost.h" 41 #include "scip/pub_lp.h" 42 #include "scip/pub_message.h" 43 #include "scip/pub_prop.h" 44 #include "scip/pub_tree.h" 45 #include "scip/pub_var.h" 46 #include "scip/scip_branch.h" 47 #include "scip/scip_general.h" 48 #include "scip/scip_lp.h" 49 #include "scip/scip_mem.h" 50 #include "scip/scip_message.h" 51 #include "scip/scip_numerics.h" 52 #include "scip/scip_param.h" 53 #include "scip/scip_pricer.h" 54 #include "scip/scip_prob.h" 55 #include "scip/scip_prop.h" 56 #include "scip/scip_solvingstats.h" 57 #include "scip/scip_tree.h" 58 #include "scip/scip_var.h" 59 #include <string.h> 60 61 /**@name Propagator properties 62 * 63 * @{ 64 */ 65 66 #define PROP_NAME "redcost" 67 #define PROP_DESC "reduced cost strengthening propagator" 68 #define PROP_TIMING SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP 69 #define PROP_PRIORITY +1000000 /**< propagator priority */ 70 #define PROP_FREQ 1 /**< propagator frequency */ 71 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */ 72 73 /**@} */ 74 75 76 /**@name Default parameter values 77 * 78 * @{ 79 */ 80 81 #define DEFAULT_CONTINUOUS FALSE /**< should reduced cost fixing be also applied to continuous variables? */ 82 #define DEFAULT_USEIMPLICS FALSE /**< should implications be used to strength the reduced cost for binary variables? */ 83 #define DEFAULT_FORCE FALSE /**< should the propagator be forced even if active pricer are present? Note that 84 * the reductions are always valid, but installing an upper bound on priced 85 * variables may lead to problems in pricing (existing variables at their upper 86 * bound may be priced again since they may have negative reduced costs) */ 87 88 /**@} */ 89 90 91 /* 92 * Data structures 93 */ 94 95 96 /** propagator data */ 97 struct SCIP_PropData 98 { 99 SCIP_Bool continuous; /**< should reduced cost fixing be also applied to continuous variables? */ 100 SCIP_Real maxredcost; /**< maximum reduced cost of a single binary variable */ 101 SCIP_Bool usefullimplics; /**< are the implied reduced cost useful */ 102 SCIP_Bool useimplics; /**< should implications be used to strength the reduced cost for binary variables? */ 103 SCIP_Bool force; /**< should the propagator be forced even if active pricer are present? */ 104 }; 105 106 107 /**@name Local methods 108 * 109 * @{ 110 */ 111 112 /** propagate the given binary variable/column using the root reduced cost stored in the SCIP internal data structures 113 * and check if the implications can be useful. Depending on that implications are used or not used during the search to 114 * strength the reduced costs. 115 */ 116 static 117 SCIP_RETCODE propagateRootRedcostBinvar( 118 SCIP* scip, /**< SCIP data structure */ 119 SCIP_PROPDATA* propdata, /**< propagator data structure */ 120 SCIP_VAR* var, /**< variable to use for propagation */ 121 SCIP_COL* col, /**< LP column of the variable */ 122 SCIP_Real cutoffbound, /**< the current cutoff bound */ 123 int* nchgbds /**< pointer to count the number of bound changes */ 124 ) 125 { 126 SCIP_Real rootredcost; 127 SCIP_Real rootsol; 128 SCIP_Real rootlpobjval; 129 130 assert(scip != NULL); 131 assert(SCIPgetDepth(scip) == 0); 132 133 /* skip binary variable if it is locally fixed */ 134 if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 ) 135 return SCIP_OKAY; 136 137 rootredcost = SCIPvarGetBestRootRedcost(var); 138 rootsol = SCIPvarGetBestRootSol(var); 139 rootlpobjval = SCIPvarGetBestRootLPObjval(var); 140 141 if( SCIPisDualfeasZero(scip, rootredcost) ) 142 return SCIP_OKAY; 143 144 assert(rootlpobjval != SCIP_INVALID); /*lint !e777*/ 145 146 if( rootsol > 0.5 ) 147 { 148 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to 149 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert 150 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong 151 * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect. 152 */ 153 assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasPositive(scip, rootredcost)); 154 155 /* update maximum reduced cost of a single binary variable */ 156 propdata->maxredcost = MAX(propdata->maxredcost, -rootredcost); 157 158 if( rootlpobjval - rootredcost > cutoffbound ) 159 { 160 SCIPdebugMsg(scip, "globally fix binary variable <%s> to 1.0\n", SCIPvarGetName(var)); 161 162 SCIP_CALL( SCIPchgVarLb(scip, var, 1.0) ); 163 (*nchgbds)++; 164 return SCIP_OKAY; 165 } 166 } 167 else 168 { 169 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to 170 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert 171 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong 172 * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect. 173 */ 174 assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasNegative(scip, rootredcost)); 175 176 /* update maximum reduced cost of a single binary variable */ 177 propdata->maxredcost = MAX(propdata->maxredcost, rootredcost); 178 179 if( rootlpobjval + rootredcost > cutoffbound ) 180 { 181 SCIPdebugMsg(scip, "globally fix binary variable <%s> to 0.0\n", SCIPvarGetName(var)); 182 183 SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) ); 184 (*nchgbds)++; 185 return SCIP_OKAY; 186 } 187 } 188 189 /* evaluate if the implications are useful; the implications are seen to be useful if they provide an increase for 190 * the root reduced costs 191 */ 192 if( !propdata->usefullimplics ) 193 { 194 SCIP_Real lbredcost; 195 SCIP_Real ubredcost; 196 197 lbredcost = SCIPgetVarImplRedcost(scip, var, FALSE); 198 assert(!SCIPisDualfeasPositive(scip, lbredcost)); 199 200 ubredcost = SCIPgetVarImplRedcost(scip, var, TRUE); 201 assert(!SCIPisDualfeasNegative(scip, ubredcost)); 202 203 switch( SCIPcolGetBasisStatus(col) ) 204 { 205 case SCIP_BASESTAT_LOWER: 206 ubredcost -= SCIPgetVarRedcost(scip, var); 207 208 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to 209 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert 210 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong 211 * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect. 212 */ 213 assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasNegative(scip, ubredcost)); 214 break; 215 216 case SCIP_BASESTAT_UPPER: 217 lbredcost -= SCIPgetVarRedcost(scip, var); 218 219 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to 220 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert 221 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong 222 * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect. 223 */ 224 assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasPositive(scip, lbredcost)); 225 break; 226 227 case SCIP_BASESTAT_BASIC: 228 case SCIP_BASESTAT_ZERO: 229 default: 230 break; 231 } 232 233 propdata->usefullimplics = (lbredcost < 0.0) || (ubredcost > 0.0); 234 } 235 236 return SCIP_OKAY; 237 } 238 239 /** propagate the given binary variable/column using the reduced cost */ 240 static 241 SCIP_RETCODE propagateRedcostBinvar( 242 SCIP* scip, /**< SCIP data structure */ 243 SCIP_PROPDATA* propdata, /**< propagator data structure */ 244 SCIP_VAR* var, /**< variable to use for propagation */ 245 SCIP_COL* col, /**< LP column of the variable */ 246 SCIP_Real requiredredcost, /**< required reduset cost to be able to fix a binary variable */ 247 int* nchgbds, /**< pointer to count the number of bound changes */ 248 SCIP_Bool* cutoff /**< pointer to store if an cutoff was detected */ 249 ) 250 { 251 SCIP_Real lbredcost; 252 SCIP_Real ubredcost; 253 SCIP_Real redcost; 254 255 /* skip binary variable if it is locally fixed */ 256 if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 ) 257 return SCIP_OKAY; 258 259 /* first use the redcost cost to fix the binary variable */ 260 switch( SCIPcolGetBasisStatus(col) ) 261 { 262 case SCIP_BASESTAT_LOWER: 263 redcost = SCIPgetVarRedcost(scip, var); 264 265 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to 266 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert 267 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong 268 * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect. 269 */ 270 assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasNegative(scip, redcost)); 271 272 if( redcost > requiredredcost ) 273 { 274 SCIPdebugMsg(scip, "variable <%s>: fixed 0.0 (requiredredcost <%g>, redcost <%g>)\n", 275 SCIPvarGetName(var), requiredredcost, redcost); 276 277 SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) ); 278 (*nchgbds)++; 279 return SCIP_OKAY; 280 } 281 break; 282 283 case SCIP_BASESTAT_UPPER: 284 redcost = SCIPgetVarRedcost(scip, var); 285 286 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to 287 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert 288 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong 289 * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect. 290 */ 291 assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasPositive(scip, redcost)); 292 293 if( -redcost > requiredredcost ) 294 { 295 SCIPdebugMsg(scip, "variable <%s>: fixed 1.0 (requiredredcost <%g>, redcost <%g>)\n", 296 SCIPvarGetName(var), requiredredcost, redcost); 297 298 SCIP_CALL( SCIPchgVarLb(scip, var, 1.0) ); 299 (*nchgbds)++; 300 return SCIP_OKAY; 301 } 302 break; 303 304 case SCIP_BASESTAT_BASIC: 305 return SCIP_OKAY; 306 307 case SCIP_BASESTAT_ZERO: 308 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to 309 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert 310 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong 311 * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect. 312 */ 313 assert(!SCIPisLPDualReliable(scip) || SCIPisDualfeasZero(scip, SCIPgetColRedcost(scip, col))); 314 return SCIP_OKAY; 315 316 default: 317 SCIPerrorMessage("invalid basis state\n"); 318 return SCIP_INVALIDDATA; 319 } 320 321 /* second, if the implications should be used and if the implications are seen to be promising use the implied 322 * reduced costs to fix the binary variable 323 */ 324 if( propdata->useimplics && propdata->usefullimplics ) 325 { 326 /* collect implied reduced costs if the variable would be fixed to its lower bound */ 327 lbredcost = SCIPgetVarImplRedcost(scip, var, FALSE); 328 329 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to 330 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert 331 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong 332 * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect. 333 */ 334 assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasPositive(scip, lbredcost) 335 || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) ); 336 337 /* collect implied reduced costs if the variable would be fixed to its upper bound */ 338 ubredcost = SCIPgetVarImplRedcost(scip, var, TRUE); 339 assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasNegative(scip, ubredcost) 340 || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) ); 341 342 if( -lbredcost > requiredredcost && ubredcost > requiredredcost ) 343 { 344 SCIPdebugMsg(scip, "variable <%s>: cutoff (requiredredcost <%g>, lbredcost <%g>, ubredcost <%g>)\n", 345 SCIPvarGetName(var), requiredredcost, lbredcost, ubredcost); 346 347 (*cutoff) = TRUE; 348 } 349 else if( -lbredcost > requiredredcost ) 350 { 351 SCIPdebugMsg(scip, "variable <%s>: fixed 1.0 (requiredredcost <%g>, redcost <%g>, lbredcost <%g>)\n", 352 SCIPvarGetName(var), requiredredcost, redcost, lbredcost); 353 354 SCIP_CALL( SCIPchgVarLb(scip, var, 1.0) ); 355 (*nchgbds)++; 356 } 357 else if( ubredcost > requiredredcost ) 358 { 359 SCIPdebugMsg(scip, "variable <%s>: fixed 0.0 (requiredredcost <%g>, redcost <%g>, ubredcost <%g>)\n", 360 SCIPvarGetName(var), requiredredcost, redcost, ubredcost); 361 362 SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) ); 363 (*nchgbds)++; 364 } 365 366 /* update maximum reduced cost of a single binary variable */ 367 propdata->maxredcost = MAX3(propdata->maxredcost, -lbredcost, ubredcost); 368 } 369 370 return SCIP_OKAY; 371 } 372 373 /** propagate the given none binary variable/column using the reduced cost */ 374 static 375 SCIP_RETCODE propagateRedcostVar( 376 SCIP* scip, /**< SCIP data structure */ 377 SCIP_VAR* var, /**< variable to use for propagation */ 378 SCIP_COL* col, /**< LP column of the variable */ 379 SCIP_Real lpobjval, /**< objective value of the current LP */ 380 SCIP_Real cutoffbound, /**< the current cutoff bound */ 381 int* nchgbds /**< pointer to count the number of bound changes */ 382 ) 383 { 384 SCIP_Real redcost; 385 386 switch( SCIPcolGetBasisStatus(col) ) 387 { 388 case SCIP_BASESTAT_LOWER: 389 redcost = SCIPgetColRedcost(scip, col); 390 391 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to 392 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert 393 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong 394 * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect. 395 */ 396 assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasNegative(scip, redcost) 397 || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) ); 398 399 if( SCIPisDualfeasPositive(scip, redcost) ) 400 { 401 SCIP_Real oldlb; 402 SCIP_Real oldub; 403 404 oldlb = SCIPvarGetLbLocal(var); 405 oldub = SCIPvarGetUbLocal(var); 406 assert(SCIPisEQ(scip, oldlb, SCIPcolGetLb(col))); 407 assert(SCIPisEQ(scip, oldub, SCIPcolGetUb(col))); 408 409 if( SCIPisFeasLT(scip, oldlb, oldub) ) 410 { 411 SCIP_Real newub; 412 SCIP_Bool strengthen; 413 414 /* calculate reduced cost based bound */ 415 newub = (cutoffbound - lpobjval) / redcost + oldlb; 416 417 /* check, if new bound is good enough: 418 * - integer variables: take all possible strengthenings 419 * - continuous variables: strengthening must cut part of the variable's dynamic range, and 420 * at least 20% of the current domain 421 */ 422 if( SCIPvarIsIntegral(var) ) 423 { 424 newub = SCIPadjustedVarUb(scip, var, newub); 425 strengthen = (newub < oldub - 0.5); 426 } 427 else 428 strengthen = (newub < SCIPcolGetMaxPrimsol(col) && newub <= 0.2 * oldlb + 0.8 * oldub); 429 430 if( strengthen ) 431 { 432 /* strengthen upper bound */ 433 SCIPdebugMsg(scip, "redcost strengthening upper bound: <%s> [%g,%g] -> [%g,%g] (ub=%g, lb=%g, redcost=%g)\n", 434 SCIPvarGetName(var), oldlb, oldub, oldlb, newub, cutoffbound, lpobjval, redcost); 435 SCIP_CALL( SCIPchgVarUb(scip, var, newub) ); 436 (*nchgbds)++; 437 } 438 } 439 } 440 break; 441 442 case SCIP_BASESTAT_BASIC: 443 break; 444 445 case SCIP_BASESTAT_UPPER: 446 redcost = SCIPgetColRedcost(scip, col); 447 448 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to 449 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert 450 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong 451 * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect. 452 */ 453 assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasPositive(scip, redcost) 454 || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) ); 455 456 if( SCIPisDualfeasNegative(scip, redcost) ) 457 { 458 SCIP_Real oldlb; 459 SCIP_Real oldub; 460 461 oldlb = SCIPvarGetLbLocal(var); 462 oldub = SCIPvarGetUbLocal(var); 463 assert(SCIPisEQ(scip, oldlb, SCIPcolGetLb(col))); 464 assert(SCIPisEQ(scip, oldub, SCIPcolGetUb(col))); 465 466 if( SCIPisFeasLT(scip, oldlb, oldub) ) 467 { 468 SCIP_Real newlb; 469 SCIP_Bool strengthen; 470 471 /* calculate reduced cost based bound */ 472 newlb = (cutoffbound - lpobjval) / redcost + oldub; 473 474 /* check, if new bound is good enough: 475 * - integer variables: take all possible strengthenings 476 * - continuous variables: strengthening must cut part of the variable's dynamic range, and 477 * at least 20% of the current domain 478 */ 479 if( SCIPvarIsIntegral(var) ) 480 { 481 newlb = SCIPadjustedVarLb(scip, var, newlb); 482 strengthen = (newlb > oldlb + 0.5); 483 } 484 else 485 strengthen = (newlb > SCIPcolGetMinPrimsol(col) && newlb >= 0.8 * oldlb + 0.2 * oldub); 486 487 /* check, if new bound is good enough: at least 20% strengthening for continuous variables */ 488 if( strengthen ) 489 { 490 /* strengthen lower bound */ 491 SCIPdebugMsg(scip, "redcost strengthening lower bound: <%s> [%g,%g] -> [%g,%g] (ub=%g, lb=%g, redcost=%g)\n", 492 SCIPvarGetName(var), oldlb, oldub, newlb, oldub, cutoffbound, lpobjval, redcost); 493 SCIP_CALL( SCIPchgVarLb(scip, var, newlb) ); 494 (*nchgbds)++; 495 } 496 } 497 } 498 break; 499 500 case SCIP_BASESTAT_ZERO: 501 /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to 502 * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert 503 * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong 504 * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect. 505 */ 506 assert(!SCIPisLPDualReliable(scip) || SCIPisDualfeasZero(scip, SCIPgetColRedcost(scip, col))); 507 break; 508 509 default: 510 SCIPerrorMessage("invalid basis state\n"); 511 return SCIP_INVALIDDATA; 512 } 513 514 return SCIP_OKAY; 515 } 516 517 /**@} */ 518 519 /**@name Callback methods of propagator 520 * 521 * @{ 522 */ 523 524 /** copy method for propagator plugins (called when SCIP copies plugins) */ 525 static 526 SCIP_DECL_PROPCOPY(propCopyRedcost) 527 { /*lint --e{715}*/ 528 assert(scip != NULL); 529 assert(prop != NULL); 530 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 531 532 /* call inclusion method of constraint handler */ 533 SCIP_CALL( SCIPincludePropRedcost(scip) ); 534 535 return SCIP_OKAY; 536 } 537 538 /** destructor of propagator to free user data (called when SCIP is exiting) */ 539 /**! [SnippetPropFreeRedcost] */ 540 static 541 SCIP_DECL_PROPFREE(propFreeRedcost) 542 { /*lint --e{715}*/ 543 SCIP_PROPDATA* propdata; 544 545 /* free propagator data */ 546 propdata = SCIPpropGetData(prop); 547 assert(propdata != NULL); 548 549 SCIPfreeBlockMemory(scip, &propdata); 550 551 SCIPpropSetData(prop, NULL); 552 553 return SCIP_OKAY; 554 } 555 /**! [SnippetPropFreeRedcost] */ 556 557 /** solving process initialization method of propagator (called when branch and bound process is about to begin) */ 558 static 559 SCIP_DECL_PROPINITSOL(propInitsolRedcost) 560 { 561 SCIP_PROPDATA* propdata; 562 563 propdata = SCIPpropGetData(prop); 564 assert(propdata != NULL); 565 566 propdata->usefullimplics = FALSE; 567 propdata->maxredcost = 0.0; 568 569 return SCIP_OKAY; 570 } 571 572 /** reduced cost propagation method for an LP solution */ 573 static 574 SCIP_DECL_PROPEXEC(propExecRedcost) 575 { /*lint --e{715}*/ 576 SCIP_PROPDATA* propdata; 577 SCIP_COL** cols; 578 SCIP_Real requiredredcost; 579 SCIP_Real cutoffbound; 580 SCIP_Real lpobjval; 581 SCIP_Bool propbinvars; 582 SCIP_Bool cutoff; 583 int nchgbds; 584 int ncols; 585 int c; 586 587 *result = SCIP_DIDNOTRUN; 588 589 /* in case we have a zero objective function, we skip the reduced cost propagator */ 590 if( SCIPgetNObjVars(scip) == 0 ) 591 return SCIP_OKAY; 592 593 /* propagator can only be applied during solving stage */ 594 if( SCIPgetStage(scip) < SCIP_STAGE_SOLVING ) 595 return SCIP_OKAY; 596 597 /* we cannot apply reduced cost fixing, if we want to solve exactly */ 598 /**@todo implement reduced cost fixing with interval arithmetics */ 599 if( SCIPisExactSolve(scip) ) 600 return SCIP_OKAY; 601 602 /* only call propagator, if the current node has an LP */ 603 if( !SCIPhasCurrentNodeLP(scip) ) 604 return SCIP_OKAY; 605 606 /* only call propagator, if an optimal LP solution is at hand */ 607 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 608 return SCIP_OKAY; 609 610 /* only call propagator, if the current LP is a valid relaxation */ 611 if( !SCIPisLPRelax(scip) ) 612 return SCIP_OKAY; 613 614 /* we cannot apply reduced cost strengthening, if no simplex basis is available */ 615 if( !SCIPisLPSolBasic(scip) ) 616 return SCIP_OKAY; 617 618 /* do not run if propagation w.r.t. objective is not allowed */ 619 if( !SCIPallowWeakDualReds(scip) ) 620 return SCIP_OKAY; 621 622 /* get current cutoff bound */ 623 cutoffbound = SCIPgetCutoffbound(scip); 624 625 /* reduced cost strengthening can only be applied, if we have a finite cutoff */ 626 if( SCIPisInfinity(scip, cutoffbound) ) 627 return SCIP_OKAY; 628 629 /* get LP columns */ 630 cols = SCIPgetLPCols(scip); 631 ncols = SCIPgetNLPCols(scip); 632 633 /* do nothing if the LP has no columns (is empty) */ 634 if( ncols == 0 ) 635 return SCIP_OKAY; 636 637 /* get propagator data */ 638 propdata = SCIPpropGetData(prop); 639 assert(propdata != NULL); 640 641 /* do nothing if active pricer are present and force flag is not TRUE */ 642 if( !propdata->force && SCIPgetNActivePricers(scip) > 0 ) 643 return SCIP_OKAY; 644 645 /* check if all integral variables are fixed and the continuous variables should not be propagated */ 646 if( !propdata->continuous && SCIPgetNPseudoBranchCands(scip) == 0 ) 647 return SCIP_OKAY; 648 649 /* get LP objective value */ 650 lpobjval = SCIPgetLPObjval(scip); 651 652 /* check if binary variables should be propagated */ 653 propbinvars = (SCIPgetDepth(scip) == 0) || (cutoffbound - lpobjval < 5 * propdata->maxredcost); 654 655 /* skip the propagator if the problem has only binary variables and those should not be propagated */ 656 if( !propbinvars && SCIPgetNVars(scip) == SCIPgetNBinVars(scip) ) 657 return SCIP_OKAY; 658 659 *result = SCIP_DIDNOTFIND; 660 cutoff = FALSE; 661 nchgbds = 0; 662 663 /* compute the required reduced cost which are needed for a binary variable to be fixed */ 664 requiredredcost = cutoffbound - lpobjval; 665 666 SCIPdebugMsg(scip, "lpobjval <%g>, cutoffbound <%g>, max reduced <%g>, propgate binary %u, use implics %u\n", 667 lpobjval, cutoffbound, propdata->maxredcost, propbinvars, propdata->usefullimplics); 668 669 /* check reduced costs for non-basic columns */ 670 for( c = 0; c < ncols && !cutoff; ++c ) 671 { 672 SCIP_VAR* var; 673 674 var = SCIPcolGetVar(cols[c]); 675 676 /* skip continuous variables in case the corresponding parameter is set */ 677 if( !propdata->continuous && !SCIPvarIsIntegral(var) ) 678 continue; 679 680 if( SCIPvarIsBinary(var) ) 681 { 682 if( propbinvars ) 683 { 684 if( SCIPgetDepth(scip) == 0 ) 685 { 686 SCIP_CALL( propagateRootRedcostBinvar(scip, propdata, var, cols[c], cutoffbound, &nchgbds) ); 687 } 688 else 689 { 690 SCIP_CALL( propagateRedcostBinvar(scip, propdata, var, cols[c], requiredredcost, &nchgbds, &cutoff) ); 691 } 692 } 693 } 694 else 695 { 696 SCIP_CALL( propagateRedcostVar(scip, var, cols[c], lpobjval, cutoffbound, &nchgbds) ); 697 } 698 } 699 700 if( cutoff ) 701 { 702 *result = SCIP_CUTOFF; 703 704 SCIPdebugMsg(scip, "node %" SCIP_LONGINT_FORMAT ": detected cutoff\n", 705 SCIPnodeGetNumber(SCIPgetCurrentNode(scip))); 706 } 707 else if( nchgbds > 0 ) 708 { 709 *result = SCIP_REDUCEDDOM; 710 711 SCIPdebugMsg(scip, "node %" SCIP_LONGINT_FORMAT ": %d bound changes (max redcost <%g>)\n", 712 SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) , nchgbds, propdata->maxredcost); 713 } 714 715 return SCIP_OKAY; 716 } 717 718 /**@} */ 719 720 /** creates the redcost propagator and includes it in SCIP */ 721 SCIP_RETCODE SCIPincludePropRedcost( 722 SCIP* scip /**< SCIP data structure */ 723 ) 724 { 725 SCIP_PROPDATA* propdata; 726 SCIP_PROP* prop; 727 728 /* create redcost propagator data */ 729 SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) ); 730 731 /* include propagator */ 732 SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING, 733 propExecRedcost, propdata) ); 734 735 assert(prop != NULL); 736 737 /* set optional callbacks via setter functions */ 738 SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyRedcost) ); 739 SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolRedcost) ); 740 SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeRedcost) ); 741 742 /* add redcost propagator parameters */ 743 SCIP_CALL( SCIPaddBoolParam(scip, 744 "propagating/" PROP_NAME "/continuous", 745 "should reduced cost fixing be also applied to continuous variables?", 746 &propdata->continuous, FALSE, DEFAULT_CONTINUOUS, NULL, NULL) ); 747 SCIP_CALL( SCIPaddBoolParam(scip, 748 "propagating/" PROP_NAME "/useimplics", 749 "should implications be used to strength the reduced cost for binary variables?", 750 &propdata->useimplics, FALSE, DEFAULT_USEIMPLICS, NULL, NULL) ); 751 SCIP_CALL( SCIPaddBoolParam(scip, 752 "propagating/" PROP_NAME "/force", 753 "should the propagator be forced even if active pricer are present?", 754 &propdata->force, TRUE, DEFAULT_FORCE, NULL, NULL) ); 755 756 return SCIP_OKAY; 757 } 758