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 sepastore.c 26 * @ingroup OTHER_CFILES 27 * @brief methods for storing separated cuts 28 * @author Tobias Achterberg 29 * @author Marc Pfetsch 30 * @author Leona Gottwald 31 */ 32 33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 34 35 #include <assert.h> 36 37 #include "scip/def.h" 38 #include "scip/set.h" 39 #include "scip/stat.h" 40 #include "scip/lp.h" 41 #include "scip/var.h" 42 #include "scip/tree.h" 43 #include "scip/reopt.h" 44 #include "scip/sepastore.h" 45 #include "scip/event.h" 46 #include "scip/sepa.h" 47 #include "scip/cons.h" 48 #include "scip/debug.h" 49 #include "scip/scip.h" 50 #include "scip/cuts.h" 51 #include "scip/cutsel.h" 52 #include "scip/struct_event.h" 53 #include "scip/struct_sepastore.h" 54 #include "scip/misc.h" 55 56 57 58 /* 59 * dynamic memory arrays 60 */ 61 62 /** resizes cuts and score arrays to be able to store at least num entries */ 63 static 64 SCIP_RETCODE sepastoreEnsureCutsMem( 65 SCIP_SEPASTORE* sepastore, /**< separation storage */ 66 SCIP_SET* set, /**< global SCIP settings */ 67 int num /**< minimal number of slots in array */ 68 ) 69 { 70 assert(sepastore != NULL); 71 assert(set != NULL); 72 73 if( num > sepastore->cutssize ) 74 { 75 int newsize; 76 77 newsize = SCIPsetCalcMemGrowSize(set, num); 78 SCIP_ALLOC( BMSreallocMemoryArray(&sepastore->cuts, newsize) ); 79 sepastore->cutssize = newsize; 80 } 81 assert(num <= sepastore->cutssize); 82 83 return SCIP_OKAY; 84 } 85 86 /** creates separation storage */ 87 SCIP_RETCODE SCIPsepastoreCreate( 88 SCIP_SEPASTORE** sepastore, /**< pointer to store separation storage */ 89 BMS_BLKMEM* blkmem, /**< block memory */ 90 SCIP_SET* set /**< global SCIP settings */ 91 ) 92 { 93 assert(sepastore != NULL); 94 95 SCIP_ALLOC( BMSallocMemory(sepastore) ); 96 97 (*sepastore)->cuts = NULL; 98 (*sepastore)->cutssize = 0; 99 (*sepastore)->ncuts = 0; 100 (*sepastore)->nforcedcuts = 0; 101 (*sepastore)->ncutsadded = 0; 102 (*sepastore)->ncutsaddedviapool = 0; 103 (*sepastore)->ncutsaddeddirect = 0; 104 (*sepastore)->ncutsfoundround = 0; 105 (*sepastore)->ncutsapplied = 0; 106 (*sepastore)->initiallp = FALSE; 107 (*sepastore)->forcecuts = FALSE; 108 109 SCIP_CALL( SCIPrandomCreate(&(*sepastore)->randnumgen, blkmem, (unsigned int)SCIPsetInitializeRandomSeed(set, 0x5EED)) ); 110 111 return SCIP_OKAY; 112 } 113 114 /** frees separation storage */ 115 SCIP_RETCODE SCIPsepastoreFree( 116 SCIP_SEPASTORE** sepastore, /**< pointer to store separation storage */ 117 BMS_BLKMEM* blkmem /**< block memory */ 118 ) 119 { 120 assert(sepastore != NULL); 121 assert(*sepastore != NULL); 122 assert((*sepastore)->ncuts == 0); 123 124 SCIPrandomFree(&(*sepastore)->randnumgen, blkmem); 125 BMSfreeMemoryArrayNull(&(*sepastore)->cuts); 126 BMSfreeMemory(sepastore); 127 128 return SCIP_OKAY; 129 } 130 131 /** informs separation storage that the setup of the initial LP starts now */ 132 void SCIPsepastoreStartInitialLP( 133 SCIP_SEPASTORE* sepastore /**< separation storage */ 134 ) 135 { 136 assert(sepastore != NULL); 137 assert(!sepastore->initiallp); 138 assert(sepastore->ncuts == 0); 139 140 sepastore->initiallp = TRUE; 141 } 142 143 /** informs separation storage that the setup of the initial LP is now finished */ 144 void SCIPsepastoreEndInitialLP( 145 SCIP_SEPASTORE* sepastore /**< separation storage */ 146 ) 147 { 148 assert(sepastore != NULL); 149 assert(sepastore->initiallp); 150 assert(sepastore->ncuts == 0); 151 152 sepastore->initiallp = FALSE; 153 } 154 155 /** informs separation storage that the following cuts should be used in any case */ 156 void SCIPsepastoreStartForceCuts( 157 SCIP_SEPASTORE* sepastore /**< separation storage */ 158 ) 159 { 160 assert(sepastore != NULL); 161 assert(!sepastore->forcecuts); 162 163 sepastore->forcecuts = TRUE; 164 } 165 166 /** informs separation storage that the following cuts should no longer be used in any case */ 167 void SCIPsepastoreEndForceCuts( 168 SCIP_SEPASTORE* sepastore /**< separation storage */ 169 ) 170 { 171 assert(sepastore != NULL); 172 assert(sepastore->forcecuts); 173 174 sepastore->forcecuts = FALSE; 175 } 176 177 /** checks cut for redundancy due to activity bounds */ 178 static 179 SCIP_Bool sepastoreIsCutRedundant( 180 SCIP_SEPASTORE* sepastore, /**< separation storage */ 181 SCIP_SET* set, /**< global SCIP settings */ 182 SCIP_STAT* stat, /**< problem statistics data */ 183 SCIP_ROW* cut /**< separated cut */ 184 ) 185 { 186 SCIP_Real minactivity; 187 SCIP_Real maxactivity; 188 SCIP_Real lhs; 189 SCIP_Real rhs; 190 191 assert(sepastore != NULL); 192 assert(cut != NULL); 193 194 /* modifiable cuts cannot be declared redundant, since we don't know all coefficients */ 195 if( SCIProwIsModifiable(cut) ) 196 return FALSE; 197 198 /* check for activity redundancy */ 199 lhs = SCIProwGetLhs(cut); 200 rhs = SCIProwGetRhs(cut); 201 minactivity = SCIProwGetMinActivity(cut, set, stat); 202 maxactivity = SCIProwGetMaxActivity(cut, set, stat); 203 204 if( (SCIPsetIsInfinity(set, -lhs) || SCIPsetIsLE(set, lhs, minactivity)) && 205 (SCIPsetIsInfinity(set, rhs) || SCIPsetIsLE(set, maxactivity, rhs)) ) 206 { 207 SCIPsetDebugMsg(set, "ignoring activity redundant cut <%s> (sides=[%g,%g], act=[%g,%g])\n", 208 SCIProwGetName(cut), lhs, rhs, minactivity, maxactivity); 209 /*SCIPdebug(SCIProwPrint(cut, set->scip->messagehdlr, NULL));*/ 210 return TRUE; 211 } 212 213 return FALSE; 214 } 215 216 /** checks cut for redundancy or infeasibility due to activity bounds */ 217 static 218 SCIP_Bool sepastoreIsCutRedundantOrInfeasible( 219 SCIP_SEPASTORE* sepastore, /**< separation storage */ 220 SCIP_SET* set, /**< global SCIP settings */ 221 SCIP_STAT* stat, /**< problem statistics data */ 222 SCIP_ROW* cut, /**< separated cut */ 223 SCIP_Bool* infeasible /**< pointer to store whether the cut has been detected to be infeasible */ 224 ) 225 { 226 SCIP_Real minactivity; 227 SCIP_Real maxactivity; 228 SCIP_Real lhs; 229 SCIP_Real rhs; 230 231 assert(sepastore != NULL); 232 assert(cut != NULL); 233 assert(infeasible != NULL); 234 235 *infeasible = FALSE; 236 237 /* modifiable cuts cannot be declared redundant or infeasible, since we don't know all coefficients */ 238 if( SCIProwIsModifiable(cut) ) 239 return FALSE; 240 241 /* check for activity redundancy */ 242 lhs = SCIProwGetLhs(cut); 243 rhs = SCIProwGetRhs(cut); 244 minactivity = SCIProwGetMinActivity(cut, set, stat); 245 maxactivity = SCIProwGetMaxActivity(cut, set, stat); 246 247 if( (SCIPsetIsInfinity(set, -lhs) || SCIPsetIsLE(set, lhs, minactivity)) && 248 (SCIPsetIsInfinity(set, rhs) || SCIPsetIsLE(set, maxactivity, rhs)) ) 249 { 250 SCIPsetDebugMsg(set, "ignoring activity redundant cut <%s> (sides=[%g,%g], act=[%g,%g])\n", 251 SCIProwGetName(cut), lhs, rhs, minactivity, maxactivity); 252 /*SCIPdebug(SCIProwPrint(cut, set->scip->messagehdlr, NULL));*/ 253 return TRUE; 254 } 255 256 if( (!SCIPsetIsInfinity(set, rhs) && SCIPsetIsFeasPositive(set, minactivity - rhs)) || 257 (!SCIPsetIsInfinity(set, -lhs) && SCIPsetIsFeasNegative(set, maxactivity - lhs)) ) 258 { 259 SCIPsetDebugMsg(set, "cut <%s> is infeasible (sides=[%g,%g], act=[%g,%g])\n", 260 SCIProwGetName(cut), lhs, rhs, minactivity, maxactivity); 261 /*SCIPdebug(SCIProwPrint(cut, set->scip->messagehdlr, NULL));*/ 262 *infeasible = TRUE; 263 return TRUE; 264 } 265 266 return FALSE; 267 } 268 269 /** checks whether a cut with only one variable can be applied as boundchange 270 * 271 * This is the case if the bound change would prove infeasibility (w.r.t feastol), or if the new bound is at least 272 * epsilon better than the old bound. In the latter case, also the opposite bound has to be taken into account. 273 */ 274 static 275 SCIP_Bool sepastoreIsBdchgApplicable( 276 SCIP_SET* set, /**< global SCIP settings */ 277 SCIP_ROW* cut /**< cut with a single variable */ 278 ) 279 { 280 SCIP_COL** cols; 281 SCIP_Real* vals; 282 SCIP_VAR* var; 283 SCIP_Real lhs; 284 SCIP_Real rhs; 285 SCIP_Bool local; 286 SCIP_Real oldlb; 287 SCIP_Real oldub; 288 289 assert(set != NULL); 290 assert(cut != NULL); 291 assert(!SCIProwIsModifiable(cut)); 292 assert(SCIProwGetNNonz(cut) == 1); 293 294 /* get the single variable and its coefficient of the cut */ 295 cols = SCIProwGetCols(cut); 296 assert(cols != NULL); 297 298 var = SCIPcolGetVar(cols[0]); 299 vals = SCIProwGetVals(cut); 300 assert(vals != NULL); 301 assert(!SCIPsetIsZero(set, vals[0])); 302 303 /* if the coefficient is nearly zero, we better ignore this cut for numerical reasons */ 304 if( SCIPsetIsFeasZero(set, vals[0]) ) 305 return FALSE; 306 307 local = SCIProwIsLocal(cut); 308 309 oldlb = local ? SCIPvarGetLbLocal(var) : SCIPvarGetLbGlobal(var); 310 oldub = local ? SCIPvarGetUbLocal(var) : SCIPvarGetUbGlobal(var); 311 312 /* get the left hand side of the cut and convert it to a bound */ 313 lhs = SCIProwGetLhs(cut); 314 if( !SCIPsetIsInfinity(set, -lhs) ) 315 { 316 lhs -= SCIProwGetConstant(cut); 317 if( vals[0] > 0.0 ) 318 { 319 /* coefficient is positive -> lhs corresponds to lower bound */ 320 SCIP_Real newlb; 321 322 newlb = lhs/vals[0]; 323 SCIPvarAdjustLb(var, set, &newlb); 324 325 /* bound changes that improve the bound sufficiently are applicable */ 326 if( SCIPsetIsFeasGT(set, newlb, oldub) || SCIPsetIsGT(set, MIN(newlb, oldub), oldlb) ) 327 return TRUE; 328 } 329 else 330 { 331 /* coefficient is negative -> lhs corresponds to upper bound */ 332 SCIP_Real newub; 333 334 newub = lhs/vals[0]; 335 SCIPvarAdjustUb(var, set, &newub); 336 337 /* bound changes that improve the bound sufficiently are applicable */ 338 if( SCIPsetIsFeasLT(set, newub, oldlb) || SCIPsetIsLT(set, MAX(newub, oldlb), oldub) ) 339 return TRUE; 340 } 341 } 342 343 /* get the right hand side of the cut and convert it to a bound */ 344 rhs = SCIProwGetRhs(cut); 345 if( !SCIPsetIsInfinity(set, rhs) ) 346 { 347 rhs -= SCIProwGetConstant(cut); 348 if( vals[0] > 0.0 ) 349 { 350 /* coefficient is positive -> rhs corresponds to upper bound */ 351 SCIP_Real newub; 352 353 newub = rhs/vals[0]; 354 SCIPvarAdjustUb(var, set, &newub); 355 356 /* bound changes that improve the bound sufficiently are applicable */ 357 if( SCIPsetIsFeasLT(set, newub, oldlb) || SCIPsetIsLT(set, MAX(newub, oldlb), oldub) ) 358 return TRUE; 359 } 360 else 361 { 362 /* coefficient is negative -> rhs corresponds to lower bound */ 363 SCIP_Real newlb; 364 365 newlb = rhs/vals[0]; 366 SCIPvarAdjustLb(var, set, &newlb); 367 368 /* bound changes that improve the bound sufficiently are applicable */ 369 if( SCIPsetIsFeasGT(set, newlb, oldub) || SCIPsetIsGT(set, MIN(newlb, oldub), oldlb) ) 370 return TRUE; 371 } 372 } 373 374 return FALSE; 375 } 376 377 /** removes a non-forced cut from the separation storage */ 378 static 379 SCIP_RETCODE sepastoreDelCut( 380 SCIP_SEPASTORE* sepastore, /**< separation storage */ 381 BMS_BLKMEM* blkmem, /**< block memory */ 382 SCIP_SET* set, /**< global SCIP settings */ 383 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 384 SCIP_EVENTFILTER* eventfilter, /**< event filter for global events */ 385 SCIP_LP* lp, /**< LP data */ 386 int pos /**< position of cut to delete */ 387 ) 388 { 389 assert(sepastore != NULL); 390 assert(sepastore->cuts != NULL); 391 assert(sepastore->nforcedcuts <= pos && pos < sepastore->ncuts); 392 393 /* check, if the row deletions from separation storage events are tracked if so, issue ROWDELETEDSEPA event */ 394 if( eventfilter->len > 0 && (eventfilter->eventmask & SCIP_EVENTTYPE_ROWDELETEDSEPA) != 0 ) 395 { 396 SCIP_EVENT* event; 397 398 SCIP_CALL( SCIPeventCreateRowDeletedSepa(&event, blkmem, sepastore->cuts[pos]) ); 399 SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, eventfilter, &event) ); 400 } 401 402 /* release the row */ 403 if( !sepastore->initiallp ) 404 { 405 sepastore->ncutsadded--; 406 if( sepastore->cuts[pos]->fromcutpool ) 407 sepastore->ncutsaddedviapool--; 408 else 409 sepastore->ncutsaddeddirect--; 410 411 if( (SCIP_ROWORIGINTYPE) sepastore->cuts[pos]->origintype == SCIP_ROWORIGINTYPE_SEPA ) 412 { 413 SCIP_SEPA* sepa; 414 sepa = SCIProwGetOriginSepa(sepastore->cuts[pos]); 415 SCIPsepaDecNCutsAdded(sepa, sepastore->cuts[pos]->fromcutpool); 416 } 417 } 418 SCIP_CALL( SCIProwRelease(&sepastore->cuts[pos], blkmem, set, lp) ); 419 420 /* move last cut to the empty position */ 421 sepastore->cuts[pos] = sepastore->cuts[sepastore->ncuts-1]; 422 sepastore->ncuts--; 423 424 return SCIP_OKAY; 425 } 426 427 /** adds cut to separation storage and captures it */ 428 SCIP_RETCODE SCIPsepastoreAddCut( 429 SCIP_SEPASTORE* sepastore, /**< separation storage */ 430 BMS_BLKMEM* blkmem, /**< block memory */ 431 SCIP_SET* set, /**< global SCIP settings */ 432 SCIP_STAT* stat, /**< problem statistics data */ 433 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 434 SCIP_EVENTFILTER* eventfilter, /**< event filter for global events */ 435 SCIP_LP* lp, /**< LP data */ 436 SCIP_ROW* cut, /**< separated cut */ 437 SCIP_Bool forcecut, /**< should the cut be forced to enter the LP? */ 438 SCIP_Bool root, /**< are we at the root node? */ 439 SCIP_Bool* infeasible /**< pointer to store whether the cut is infeasible */ 440 ) 441 { 442 SCIP_Bool redundant; 443 int pos; 444 445 assert(sepastore != NULL); 446 assert(sepastore->nforcedcuts <= sepastore->ncuts); 447 assert(set != NULL); 448 assert(cut != NULL); 449 assert(!SCIPsetIsInfinity(set, -SCIProwGetLhs(cut)) || !SCIPsetIsInfinity(set, SCIProwGetRhs(cut))); 450 assert(eventqueue != NULL); 451 assert(eventfilter != NULL); 452 453 /* debug: check cut for feasibility */ 454 SCIP_CALL( SCIPdebugCheckRow(set, cut) ); /*lint !e506 !e774*/ 455 456 /* the cut will be forced to enter the LP if the dual must be collected and the initial LP is being constructed */ 457 forcecut = forcecut || (set->lp_alwaysgetduals && sepastore->initiallp); 458 459 /* in the root node, every local cut is a global cut, and global cuts are nicer in many ways ... */ 460 if( root && SCIProwIsLocal(cut) ) 461 { 462 SCIPsetDebugMsg(set, "change local flag of cut <%s> to FALSE due to addition in root node\n", SCIProwGetName(cut)); 463 464 SCIP_CALL( SCIProwChgLocal(cut, FALSE) ); 465 466 assert(!SCIProwIsLocal(cut)); 467 } 468 469 /* check cut for redundancy or infeasibility */ 470 redundant = sepastoreIsCutRedundantOrInfeasible(sepastore, set, stat, cut, infeasible); 471 /* Note that we add infeasible rows in any case, since we cannot be sure whether the return values are handled 472 * correctly. In this way, the LP becomes infeasible. */ 473 474 /* in each separation round, make sure that at least one (even redundant) cut enters the LP to avoid cycling */ 475 if( !forcecut && sepastore->ncuts > 0 && redundant ) 476 return SCIP_OKAY; 477 478 /* if only one cut is currently present in sepastore, it could be redundant; in this case, it can now be removed 479 * again, because now a non redundant cut enters the sepastore */ 480 if( sepastore->ncuts == 1 && sepastoreIsCutRedundant(sepastore, set, stat, sepastore->cuts[0]) ) 481 { 482 /* check, if the row deletions from separation storage events are tracked if so, issue ROWDELETEDSEPA event */ 483 if( eventfilter->len > 0 && (eventfilter->eventmask & SCIP_EVENTTYPE_ROWDELETEDSEPA) != 0 ) 484 { 485 SCIP_EVENT* event; 486 487 SCIP_CALL( SCIPeventCreateRowDeletedSepa(&event, blkmem, sepastore->cuts[0]) ); 488 SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, eventfilter, &event) ); 489 } 490 /* update statistics of total number of found cuts */ 491 if( !sepastore->initiallp ) 492 { 493 sepastore->ncutsadded--; 494 if( sepastore->cuts[0]->fromcutpool ) 495 sepastore->ncutsaddedviapool--; 496 else 497 sepastore->ncutsaddeddirect--; 498 499 if( (SCIP_ROWORIGINTYPE) sepastore->cuts[0]->origintype == SCIP_ROWORIGINTYPE_SEPA ) 500 { 501 SCIP_SEPA* sepa; 502 sepa = SCIProwGetOriginSepa(sepastore->cuts[0]); 503 SCIPsepaDecNCutsAdded(sepa, sepastore->cuts[0]->fromcutpool); 504 } 505 } 506 507 SCIP_CALL( SCIProwRelease(&sepastore->cuts[0], blkmem, set, lp) ); 508 sepastore->ncuts = 0; 509 sepastore->nforcedcuts = 0; 510 } 511 512 /* a cut is forced to enter the LP if 513 * - we construct the initial LP, or 514 * - it has infinite score factor, or 515 * - it is a bound change that can be applied 516 * if it is a non-forced cut and no cuts should be added, abort 517 */ 518 forcecut = forcecut || sepastore->initiallp || sepastore->forcecuts || (!SCIProwIsModifiable(cut) && SCIProwGetNNonz(cut) == 1 && sepastoreIsBdchgApplicable(set, cut)); 519 if( !forcecut && SCIPsetGetSepaMaxcuts(set, root) == 0 ) 520 return SCIP_OKAY; 521 522 /* get enough memory to store the cut */ 523 SCIP_CALL( sepastoreEnsureCutsMem(sepastore, set, sepastore->ncuts+1) ); 524 assert(sepastore->ncuts < sepastore->cutssize); 525 526 SCIPsetDebugMsg(set, "adding cut <%s> to separation storage of size %d (forcecut=%u, len=%d)\n", 527 SCIProwGetName(cut), sepastore->ncuts, forcecut, SCIProwGetNNonz(cut)); 528 /*SCIP_CALL( SCIPprintRow(set->scip, cut, NULL) );*/ 529 530 /* capture the cut */ 531 SCIProwCapture(cut); 532 533 /* add cut to arrays */ 534 if( forcecut ) 535 { 536 /* make room at the beginning of the array for forced cut */ 537 pos = sepastore->nforcedcuts; 538 sepastore->cuts[sepastore->ncuts] = sepastore->cuts[pos]; 539 sepastore->nforcedcuts++; 540 } 541 else 542 pos = sepastore->ncuts; 543 544 sepastore->cuts[pos] = cut; 545 546 /* update statistics of total number of found cuts */ 547 if( !sepastore->initiallp ) 548 { 549 sepastore->ncutsadded++; 550 sepastore->ncutsfoundround++; 551 if( cut->fromcutpool ) 552 sepastore->ncutsaddedviapool++; 553 else 554 sepastore->ncutsaddeddirect++; 555 556 if( (SCIP_ROWORIGINTYPE) cut->origintype == SCIP_ROWORIGINTYPE_SEPA ) 557 { 558 SCIP_SEPA* sepa; 559 560 sepa = SCIProwGetOriginSepa(cut); 561 SCIPsepaIncNCutsAdded(sepa, cut->fromcutpool); 562 } 563 } 564 sepastore->ncuts++; 565 566 /* check, if the row addition to separation storage events are tracked if so, issue ROWADDEDSEPA event */ 567 if( eventfilter->len > 0 && (eventfilter->eventmask & SCIP_EVENTTYPE_ROWADDEDSEPA) != 0 ) 568 { 569 SCIP_EVENT* event; 570 571 SCIP_CALL( SCIPeventCreateRowAddedSepa(&event, blkmem, cut) ); 572 SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, eventfilter, &event) ); 573 } 574 575 /* If the duals need to be collected, then the infeasible flag is set to FALSE. This ensures that the LP is solved */ 576 if( set->lp_alwaysgetduals && sepastore->initiallp ) 577 (*infeasible) = FALSE; 578 579 return SCIP_OKAY; 580 } 581 582 /** applies a lower bound change */ 583 static 584 SCIP_RETCODE sepastoreApplyLb( 585 SCIP_SEPASTORE* sepastore, /**< separation storage */ 586 BMS_BLKMEM* blkmem, /**< block memory */ 587 SCIP_SET* set, /**< global SCIP settings */ 588 SCIP_STAT* stat, /**< problem statistics */ 589 SCIP_PROB* transprob, /**< transformed problem */ 590 SCIP_PROB* origprob, /**< original problem */ 591 SCIP_TREE* tree, /**< branch and bound tree */ 592 SCIP_REOPT* reopt, /**< reoptimization data structure */ 593 SCIP_LP* lp, /**< LP data */ 594 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 595 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 596 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 597 SCIP_VAR* var, /**< problem variable */ 598 SCIP_Real bound, /**< new lower bound of variable */ 599 SCIP_Bool local, /**< is it a local bound change? (otherwise global) */ 600 SCIP_Bool* applied, /**< pointer to store whether the domain change was applied */ 601 SCIP_Bool* cutoff /**< pointer to store TRUE, if an infeasibility has been detected */ 602 ) 603 { 604 assert(sepastore != NULL); 605 assert(cutoff != NULL); 606 assert(applied != NULL); 607 608 /* adjust bound to the one that would be applied, so the SCIPsetIsGT check below is more reliable */ 609 SCIPvarAdjustLb(var, set, &bound); 610 611 if( local ) 612 { 613 /* apply the local bound change or detect a cutoff */ 614 if( SCIPsetIsGT(set, bound, SCIPvarGetLbLocal(var)) ) 615 { 616 SCIPsetDebugMsg(set, " -> applying bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n", 617 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bound, SCIPvarGetUbLocal(var)); 618 619 /* changing the lower bound to a value >= SCIPinfinity should result in a cutoff, 620 * since "infinite" values in solutions are reserved for another meaning 621 */ 622 if( !SCIPsetIsInfinity(set, bound) && SCIPsetIsFeasLE(set, bound, SCIPvarGetUbLocal(var)) ) 623 { 624 SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(tree), blkmem, set, stat, transprob, origprob, tree, 625 reopt, lp, branchcand, eventqueue, cliquetable, var, bound, SCIP_BOUNDTYPE_LOWER, FALSE) ); 626 } 627 else 628 *cutoff = TRUE; 629 630 *applied = TRUE; 631 } 632 else 633 { 634 SCIPsetDebugMsg(set, " -> ignoring bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n", 635 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bound, SCIPvarGetUbLocal(var)); 636 } 637 } 638 else 639 { 640 /* apply the global bound change or detect a global cutoff which means we can cutoff the root node */ 641 if( SCIPsetIsGT(set, bound, SCIPvarGetLbGlobal(var)) ) 642 { 643 SCIPsetDebugMsg(set, " -> applying global bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n", 644 SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), bound, SCIPvarGetUbGlobal(var)); 645 646 /* changing the lower bound to a value >= SCIPinfinity should result in a cutoff, 647 * since "infinite" values in solutions are reserved for another meaning 648 */ 649 if( !SCIPsetIsInfinity(set, bound) && SCIPsetIsFeasLE(set, bound, SCIPvarGetUbGlobal(var)) ) 650 { 651 SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetRootNode(tree), blkmem, set, stat, transprob, origprob, tree, reopt, 652 lp, branchcand, eventqueue, cliquetable, var, bound, SCIP_BOUNDTYPE_LOWER, FALSE) ); 653 } 654 else 655 { 656 /* we are done with solving since a global bound change is infeasible */ 657 SCIP_CALL( SCIPnodeCutoff(SCIPtreeGetRootNode(tree), set, stat, tree, transprob, origprob, reopt, lp, blkmem) ); 658 *cutoff = TRUE; 659 } 660 661 *applied = TRUE; 662 } 663 else 664 { 665 SCIPsetDebugMsg(set, " -> ignoring global bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n", 666 SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), bound, SCIPvarGetUbGlobal(var)); 667 } 668 } 669 670 return SCIP_OKAY; 671 } 672 673 /** applies an upper bound change */ 674 static 675 SCIP_RETCODE sepastoreApplyUb( 676 SCIP_SEPASTORE* sepastore, /**< separation storage */ 677 BMS_BLKMEM* blkmem, /**< block memory */ 678 SCIP_SET* set, /**< global SCIP settings */ 679 SCIP_STAT* stat, /**< problem statistics */ 680 SCIP_PROB* transprob, /**< transformed problem */ 681 SCIP_PROB* origprob, /**< original problem */ 682 SCIP_TREE* tree, /**< branch and bound tree */ 683 SCIP_REOPT* reopt, /**< reoptimization data structure */ 684 SCIP_LP* lp, /**< LP data */ 685 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 686 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 687 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 688 SCIP_VAR* var, /**< problem variable */ 689 SCIP_Real bound, /**< new upper bound of variable */ 690 SCIP_Bool local, /**< is it a local bound change? (otherwise global) */ 691 SCIP_Bool* applied, /**< pointer to store whether the domain change was applied */ 692 SCIP_Bool* cutoff /**< pointer to store TRUE, if an infeasibility has been detected */ 693 ) 694 { 695 assert(sepastore != NULL); 696 assert(cutoff != NULL); 697 assert(applied != NULL); 698 699 /* adjust bound to the one that would be applied, so the SCIPsetIsGT check below is more reliable */ 700 SCIPvarAdjustUb(var, set, &bound); 701 702 if( local ) 703 { 704 /* apply the local bound change or detect a cutoff */ 705 if( SCIPsetIsLT(set, bound, SCIPvarGetUbLocal(var)) ) 706 { 707 SCIPsetDebugMsg(set, " -> applying bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n", 708 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPvarGetLbLocal(var), bound); 709 710 /* changing the upper bound to a value <= -SCIPinfinity should result in a cutoff, 711 * since "infinite" values in solutions are reserved for another meaning 712 */ 713 if( !SCIPsetIsInfinity(set, -bound) && SCIPsetIsFeasGE(set, bound, SCIPvarGetLbLocal(var)) ) 714 { 715 SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(tree), blkmem, set, stat, transprob, origprob, tree, 716 reopt, lp, branchcand, eventqueue, cliquetable, var, bound, SCIP_BOUNDTYPE_UPPER, FALSE) ); 717 } 718 else 719 *cutoff = TRUE; 720 721 *applied = TRUE; 722 } 723 else 724 { 725 SCIPsetDebugMsg(set, " -> ignoring bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n", 726 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPvarGetLbLocal(var), bound); 727 } 728 } 729 else 730 { 731 /* apply the global bound change or detect a global cutoff which means we can cutoff the root node */ 732 if( SCIPsetIsLT(set, bound, SCIPvarGetUbGlobal(var)) ) 733 { 734 SCIPsetDebugMsg(set, " -> applying global bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n", 735 SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), SCIPvarGetLbGlobal(var), bound); 736 737 /* changing the upper bound to a value <= -SCIPinfinity should result in a cutoff, 738 * since "infinite" values in solutions are reserved for another meaning 739 */ 740 if( !SCIPsetIsInfinity(set, -bound) && SCIPsetIsFeasGE(set, bound, SCIPvarGetLbGlobal(var)) ) 741 { 742 SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetRootNode(tree), blkmem, set, stat, transprob, origprob, tree, reopt, 743 lp, branchcand, eventqueue, cliquetable, var, bound, SCIP_BOUNDTYPE_UPPER, FALSE) ); 744 } 745 else 746 { 747 /* we are done with solving since a global bound change is infeasible */ 748 SCIP_CALL( SCIPnodeCutoff(SCIPtreeGetRootNode(tree), set, stat, tree, transprob, origprob, reopt, lp, blkmem) ); 749 *cutoff = TRUE; 750 } 751 752 *applied = TRUE; 753 } 754 else 755 { 756 SCIPsetDebugMsg(set, " -> ignoring global bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n", 757 SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), SCIPvarGetLbGlobal(var), bound); 758 } 759 } 760 761 return SCIP_OKAY; 762 } 763 764 /** applies a cut that is a bound change directly as bound change instead of adding it as row to the LP */ 765 static 766 SCIP_RETCODE sepastoreApplyBdchg( 767 SCIP_SEPASTORE* sepastore, /**< separation storage */ 768 BMS_BLKMEM* blkmem, /**< block memory */ 769 SCIP_SET* set, /**< global SCIP settings */ 770 SCIP_STAT* stat, /**< problem statistics */ 771 SCIP_PROB* transprob, /**< transformed problem */ 772 SCIP_PROB* origprob, /**< original problem */ 773 SCIP_TREE* tree, /**< branch and bound tree */ 774 SCIP_REOPT* reopt, /**< reoptimization data structure */ 775 SCIP_LP* lp, /**< LP data */ 776 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 777 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 778 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 779 SCIP_ROW* cut, /**< cut with a single variable */ 780 SCIP_Bool* applied, /**< pointer to store whether the domain change was applied */ 781 SCIP_Bool* cutoff /**< pointer to store whether an empty domain was created */ 782 ) 783 { 784 SCIP_COL** cols; 785 SCIP_Real* vals; 786 SCIP_VAR* var; 787 SCIP_Real lhs; 788 SCIP_Real rhs; 789 SCIP_Bool local; 790 791 assert(sepastore != NULL); 792 assert(!SCIProwIsModifiable(cut)); 793 assert(SCIProwGetNNonz(cut) == 1); 794 assert(cutoff != NULL); 795 assert(applied != NULL); 796 797 *applied = FALSE; 798 *cutoff = FALSE; 799 800 /* get the single variable and its coefficient of the cut */ 801 cols = SCIProwGetCols(cut); 802 assert(cols != NULL); 803 804 var = SCIPcolGetVar(cols[0]); 805 vals = SCIProwGetVals(cut); 806 assert(vals != NULL); 807 assert(!SCIPsetIsZero(set, vals[0])); 808 809 /* if the coefficient is nearly zero, we better ignore this cut for numerical reasons */ 810 if( SCIPsetIsFeasZero(set, vals[0]) ) 811 return SCIP_OKAY; 812 813 local = SCIProwIsLocal(cut); 814 815 /* get the left hand side of the cut and convert it to a bound */ 816 lhs = SCIProwGetLhs(cut); 817 if( !SCIPsetIsInfinity(set, -lhs) ) 818 { 819 lhs -= SCIProwGetConstant(cut); 820 if( vals[0] > 0.0 ) 821 { 822 /* coefficient is positive -> lhs corresponds to lower bound */ 823 SCIP_CALL( sepastoreApplyLb(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, 824 cliquetable, var, lhs/vals[0], local, applied, cutoff) ); 825 } 826 else 827 { 828 /* coefficient is negative -> lhs corresponds to upper bound */ 829 SCIP_CALL( sepastoreApplyUb(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, 830 cliquetable, var, lhs/vals[0], local, applied, cutoff) ); 831 } 832 } 833 834 /* get the right hand side of the cut and convert it to a bound */ 835 rhs = SCIProwGetRhs(cut); 836 if( !SCIPsetIsInfinity(set, rhs) ) 837 { 838 rhs -= SCIProwGetConstant(cut); 839 if( vals[0] > 0.0 ) 840 { 841 /* coefficient is positive -> rhs corresponds to upper bound */ 842 SCIP_CALL( sepastoreApplyUb(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, 843 cliquetable, var, rhs/vals[0], local, applied, cutoff) ); 844 } 845 else 846 { 847 /* coefficient is negative -> rhs corresponds to lower bound */ 848 SCIP_CALL( sepastoreApplyLb(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, 849 cliquetable, var, rhs/vals[0], local, applied, cutoff) ); 850 } 851 } 852 853 /* count the bound change as applied cut */ 854 if( *applied && !sepastore->initiallp ) 855 sepastore->ncutsapplied++; 856 857 return SCIP_OKAY; 858 } 859 860 /** applies the given cut to the LP and updates the orthogonalities and scores of remaining cuts */ 861 static 862 SCIP_RETCODE sepastoreApplyCut( 863 SCIP_SEPASTORE* sepastore, /**< separation storage */ 864 BMS_BLKMEM* blkmem, /**< block memory */ 865 SCIP_SET* set, /**< global SCIP settings */ 866 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 867 SCIP_EVENTFILTER* eventfilter, /**< global event filter */ 868 SCIP_LP* lp, /**< LP data */ 869 SCIP_ROW* cut, /**< cut to apply to the LP */ 870 int depth, /**< depth of current node */ 871 int* ncutsapplied /**< pointer to count the number of applied cuts */ 872 ) 873 { 874 assert(sepastore != NULL); 875 assert(ncutsapplied != NULL); 876 877 /* a row could have been added twice to the separation store; add it only once! */ 878 if( !SCIProwIsInLP(cut) ) 879 { 880 /* add cut to the LP and capture it */ 881 SCIP_CALL( SCIPlpAddRow(lp, blkmem, set, eventqueue, eventfilter, cut, depth) ); 882 883 /* update statistics -> only if we are not in the initial lp (cuts are only counted if added during run) */ 884 if( !sepastore->initiallp ) 885 { 886 sepastore->ncutsapplied++; 887 888 /* increase count of applied cuts for origins of row */ 889 /* TODO: adjust conshdlr statistics to mirror cut statistics */ 890 switch ( (SCIP_ROWORIGINTYPE) cut->origintype ) 891 { 892 case SCIP_ROWORIGINTYPE_CONSHDLR: 893 assert( cut->origin != NULL ); 894 SCIPconshdlrIncNAppliedCuts((SCIP_CONSHDLR*) cut->origin); 895 break; 896 case SCIP_ROWORIGINTYPE_CONS: 897 assert( cut->origin != NULL ); 898 SCIPconshdlrIncNAppliedCuts(SCIPconsGetHdlr((SCIP_CONS*)cut->origin)); 899 break; 900 case SCIP_ROWORIGINTYPE_SEPA: 901 assert( cut->origin != NULL ); 902 SCIPsepaIncNCutsApplied((SCIP_SEPA*)cut->origin, cut->fromcutpool); 903 break; 904 case SCIP_ROWORIGINTYPE_UNSPEC: 905 case SCIP_ROWORIGINTYPE_REOPT: 906 /* do nothing - cannot update statistics */ 907 break; 908 default: 909 SCIPerrorMessage("unknown type of row origin.\n"); 910 return SCIP_INVALIDDATA; 911 } 912 } 913 914 (*ncutsapplied)++; 915 } 916 917 return SCIP_OKAY; 918 } 919 920 /** adds cuts to the LP and clears separation storage */ 921 SCIP_RETCODE SCIPsepastoreApplyCuts( 922 SCIP_SEPASTORE* sepastore, /**< separation storage */ 923 BMS_BLKMEM* blkmem, /**< block memory */ 924 SCIP_SET* set, /**< global SCIP settings */ 925 SCIP_STAT* stat, /**< problem statistics */ 926 SCIP_PROB* transprob, /**< transformed problem */ 927 SCIP_PROB* origprob, /**< original problem */ 928 SCIP_TREE* tree, /**< branch and bound tree */ 929 SCIP_REOPT* reopt, /**< reoptimization data structure */ 930 SCIP_LP* lp, /**< LP data */ 931 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 932 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 933 SCIP_EVENTFILTER* eventfilter, /**< global event filter */ 934 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 935 SCIP_Bool root, /**< are we at the root node? */ 936 SCIP_EFFICIACYCHOICE efficiacychoice, /**< type of solution to base efficiacy computation on */ 937 SCIP_Bool* cutoff /**< pointer to store whether an empty domain was created */ 938 ) 939 { 940 SCIP_NODE* node; 941 int maxsepacuts; 942 int ncutsapplied; 943 int nselectedcuts; 944 int depth; 945 int i; 946 947 assert(sepastore != NULL); 948 assert(set != NULL); 949 assert(tree != NULL); 950 assert(lp != NULL); 951 assert(cutoff != NULL); 952 953 SCIP_UNUSED(efficiacychoice); 954 955 SCIPsetDebugMsg(set, "selecting from %d cuts\n", sepastore->ncuts); 956 957 /* get maximal number of cuts to add to the LP */ 958 maxsepacuts = SCIPsetGetSepaMaxcuts(set, root); 959 960 /* if all cuts are forced cuts, no selection is required */ 961 if( sepastore->nforcedcuts >= MIN(sepastore->ncuts, maxsepacuts) ) 962 { 963 nselectedcuts = sepastore->nforcedcuts; 964 } 965 else 966 { 967 /* call cut selection algorithms */ 968 nselectedcuts = 0; 969 SCIP_CALL( SCIPcutselsSelect(set, sepastore->cuts, sepastore->ncuts, sepastore->nforcedcuts, root, sepastore->initiallp, maxsepacuts, 970 &nselectedcuts) ); 971 assert(nselectedcuts + sepastore->nforcedcuts <= maxsepacuts); 972 973 /* note that cut selector statistics are updated here also when in probing mode; this may lead to an offset with 974 * separator/constraint handler statistics */ 975 /* @todo do not update cutselector statistics if SCIPtreeProbing(scip->tree) */ 976 nselectedcuts += sepastore->nforcedcuts; 977 } 978 979 /* 980 * apply all selected cuts 981 */ 982 ncutsapplied = 0; 983 *cutoff = FALSE; 984 985 node = SCIPtreeGetCurrentNode(tree); 986 assert(node != NULL); 987 988 /* get depth of current node */ 989 depth = SCIPnodeGetDepth(node); 990 991 for( i = 0; i < nselectedcuts && !(*cutoff); i++ ) 992 { 993 SCIP_ROW* cut; 994 995 cut = sepastore->cuts[i]; 996 997 if( i < sepastore->nforcedcuts || SCIPsetIsFeasPositive(set, SCIProwGetLPEfficacy(cut, set, stat, lp)) ) 998 { 999 SCIP_Bool applied = FALSE; 1000 1001 /* if the cut is a bound change (i.e. a row with only one variable), add it as bound change instead of LP row */ 1002 if( !SCIProwIsModifiable(cut) && SCIProwGetNNonz(cut) == 1 ) 1003 { 1004 SCIPsetDebugMsg(set, " -> applying forced cut <%s> as boundchange\n", SCIProwGetName(cut)); 1005 SCIP_CALL( sepastoreApplyBdchg(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, 1006 eventqueue, cliquetable, cut, &applied, cutoff) ); 1007 assert(applied || !sepastoreIsBdchgApplicable(set, cut)); 1008 } 1009 1010 if( !applied ) 1011 { 1012 /* add cut to the LP and update orthogonalities */ 1013 SCIPsetDebugMsg(set, " -> applying%s cut <%s>\n", (i < sepastore->nforcedcuts) ? " forced" : "", SCIProwGetName(cut)); 1014 /*SCIPdebug( SCIProwPrint(cut, set->scip->messagehdlr, NULL));*/ 1015 SCIP_CALL( sepastoreApplyCut(sepastore, blkmem, set, eventqueue, eventfilter, lp, cut, depth, &ncutsapplied) ); 1016 } 1017 } 1018 } 1019 1020 /* clear the separation storage and reset statistics for separation round */ 1021 SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) ); 1022 1023 return SCIP_OKAY; 1024 } 1025 1026 /** clears the separation storage without adding the cuts to the LP */ 1027 SCIP_RETCODE SCIPsepastoreClearCuts( 1028 SCIP_SEPASTORE* sepastore, /**< separation storage */ 1029 BMS_BLKMEM* blkmem, /**< block memory */ 1030 SCIP_SET* set, /**< global SCIP settings */ 1031 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 1032 SCIP_EVENTFILTER* eventfilter, /**< event filter for global events */ 1033 SCIP_LP* lp /**< LP data */ 1034 ) 1035 { 1036 int c; 1037 1038 assert(sepastore != NULL); 1039 1040 SCIPsetDebugMsg(set, "clearing %d cuts\n", sepastore->ncuts); 1041 1042 /* release cuts */ 1043 for( c = 0; c < sepastore->ncuts; ++c ) 1044 { 1045 /* check, if the row deletions from separation storage events are tracked if so, issue ROWDELETEDSEPA event */ 1046 if( eventfilter->len > 0 && (eventfilter->eventmask & SCIP_EVENTTYPE_ROWDELETEDSEPA) != 0 ) 1047 { 1048 SCIP_EVENT* event; 1049 1050 SCIP_CALL( SCIPeventCreateRowDeletedSepa(&event, blkmem, sepastore->cuts[c]) ); 1051 SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, eventfilter, &event) ); 1052 } 1053 1054 SCIP_CALL( SCIProwRelease(&sepastore->cuts[c], blkmem, set, lp) ); 1055 } 1056 1057 /* reset counters */ 1058 sepastore->ncuts = 0; 1059 sepastore->nforcedcuts = 0; 1060 sepastore->ncutsfoundround = 0; 1061 1062 /* if we have just finished the initial LP construction, free the (potentially large) cuts array */ 1063 if( sepastore->initiallp ) 1064 { 1065 BMSfreeMemoryArrayNull(&sepastore->cuts); 1066 sepastore->cutssize = 0; 1067 } 1068 1069 return SCIP_OKAY; 1070 } 1071 1072 /** removes cuts that are inefficacious w.r.t. the current LP solution from separation storage without adding the cuts to the LP */ 1073 SCIP_RETCODE SCIPsepastoreRemoveInefficaciousCuts( 1074 SCIP_SEPASTORE* sepastore, /**< separation storage */ 1075 BMS_BLKMEM* blkmem, /**< block memory */ 1076 SCIP_SET* set, /**< global SCIP settings */ 1077 SCIP_STAT* stat, /**< problem statistics data */ 1078 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 1079 SCIP_EVENTFILTER* eventfilter, /**< event filter for global events */ 1080 SCIP_LP* lp, /**< LP data */ 1081 SCIP_Bool root, /**< are we at the root node? */ 1082 SCIP_EFFICIACYCHOICE efficiacychoice /**< type of solution to base efficiacy computation on */ 1083 ) 1084 { 1085 int cnt = 0; 1086 int c; 1087 1088 assert( sepastore != NULL ); 1089 1090 /* check non-forced cuts only */ 1091 c = sepastore->nforcedcuts; 1092 while( c < sepastore->ncuts ) 1093 { 1094 SCIP_Real cutefficacy; 1095 1096 /* calculate cut's efficacy */ 1097 switch ( efficiacychoice ) 1098 { 1099 case SCIP_EFFICIACYCHOICE_LP: 1100 cutefficacy = SCIProwGetLPEfficacy(sepastore->cuts[c], set, stat, lp); 1101 break; 1102 case SCIP_EFFICIACYCHOICE_RELAX: 1103 cutefficacy = SCIProwGetRelaxEfficacy(sepastore->cuts[c], set, stat); 1104 break; 1105 case SCIP_EFFICIACYCHOICE_NLP: 1106 cutefficacy = SCIProwGetNLPEfficacy(sepastore->cuts[c], set, stat); 1107 break; 1108 default: 1109 SCIPerrorMessage("Invalid efficiacy choice.\n"); 1110 return SCIP_INVALIDCALL; 1111 } 1112 1113 if( !SCIPsetIsEfficacious(set, root, cutefficacy) ) 1114 { 1115 SCIP_CALL( sepastoreDelCut(sepastore, blkmem, set, eventqueue, eventfilter, lp, c) ); 1116 ++cnt; 1117 } 1118 else 1119 ++c; 1120 } 1121 SCIPsetDebugMsg(set, "removed %d non-efficacious cuts\n", cnt); 1122 1123 return SCIP_OKAY; 1124 } 1125 1126 /** indicates whether a cut is applicable 1127 * 1128 * A cut is applicable if it is modifiable, not a bound change, or a bound change that changes bounds by at least epsilon. 1129 */ 1130 SCIP_Bool SCIPsepastoreIsCutApplicable( 1131 SCIP_SET* set, /**< global SCIP settings */ 1132 SCIP_ROW* cut /**< cut to check */ 1133 ) 1134 { 1135 return SCIProwIsModifiable(cut) || SCIProwGetNNonz(cut) != 1 || sepastoreIsBdchgApplicable(set, cut); 1136 } 1137 1138 /** get cuts in the separation storage */ 1139 SCIP_ROW** SCIPsepastoreGetCuts( 1140 SCIP_SEPASTORE* sepastore /**< separation storage */ 1141 ) 1142 { 1143 assert(sepastore != NULL); 1144 1145 return sepastore->cuts; 1146 } 1147 1148 /** get number of cuts in the separation storage */ 1149 int SCIPsepastoreGetNCuts( 1150 SCIP_SEPASTORE* sepastore /**< separation storage */ 1151 ) 1152 { 1153 assert(sepastore != NULL); 1154 1155 return sepastore->ncuts; 1156 } 1157 1158 /** gets the total number of cutting planes added to the separation storage; 1159 * this is equal to the sum of added cuts directly and via the pool. */ 1160 int SCIPsepastoreGetNCutsAdded( 1161 SCIP_SEPASTORE* sepastore /**< separation storage */ 1162 ) 1163 { 1164 assert(sepastore != NULL); 1165 1166 return sepastore->ncutsadded; 1167 } 1168 1169 /** gets the number of cutting planes added to the separation storage from the cut pool */ 1170 int SCIPsepastoreGetNCutsAddedViaPool( 1171 SCIP_SEPASTORE* sepastore /**< separation storage */ 1172 ) 1173 { 1174 assert(sepastore != NULL); 1175 1176 return sepastore->ncutsaddedviapool; 1177 } 1178 1179 /** gets the number of cutting planes added to the separation storage directly */ 1180 int SCIPsepastoreGetNCutsAddedDirect( 1181 SCIP_SEPASTORE* sepastore /**< separation storage */ 1182 ) 1183 { 1184 assert(sepastore != NULL); 1185 1186 return sepastore->ncutsaddeddirect; 1187 } 1188 1189 /** get number of cuts found so far in current separation round */ 1190 int SCIPsepastoreGetNCutsFoundRound( 1191 SCIP_SEPASTORE* sepastore /**< separation storage */ 1192 ) 1193 { 1194 assert(sepastore != NULL); 1195 1196 return sepastore->ncutsfoundround; 1197 } 1198 1199 /** gets the total number of cutting planes applied to the LP */ 1200 int SCIPsepastoreGetNCutsApplied( 1201 SCIP_SEPASTORE* sepastore /**< separation storage */ 1202 ) 1203 { 1204 assert(sepastore != NULL); 1205 1206 return sepastore->ncutsapplied; 1207 } 1208