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 cutpool.c 26 * @ingroup OTHER_CFILES 27 * @brief methods for storing cuts in a cut pool 28 * @author Tobias Achterberg 29 * @author Stefan Heinz 30 * @author Gerald Gamrath 31 * @author Marc Pfetsch 32 * @author Kati Wolter 33 */ 34 35 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 36 37 #include <assert.h> 38 39 #include "scip/def.h" 40 #include "scip/set.h" 41 #include "scip/stat.h" 42 #include "scip/clock.h" 43 #include "scip/lp.h" 44 #include "scip/cons.h" 45 #include "scip/sepa.h" 46 #include "scip/sepastore.h" 47 #include "scip/cutpool.h" 48 #include "scip/pub_message.h" 49 #include "scip/pub_misc.h" 50 51 #include "scip/struct_cutpool.h" 52 53 54 55 /* 56 * Hash functions 57 */ 58 59 /** gets the hash key of a cut */ 60 static 61 SCIP_DECL_HASHGETKEY(hashGetKeyCut) 62 { /*lint --e{715}*/ 63 SCIP_CUT* cut; 64 65 cut = (SCIP_CUT*)elem; 66 assert(cut != NULL); 67 assert(cut->row != NULL); 68 69 /* the key of a cut is the row */ 70 return cut->row; 71 } 72 73 /** returns TRUE iff both cuts are identical */ 74 static 75 SCIP_DECL_HASHKEYEQ(hashKeyEqCut) 76 { /*lint --e{715}*/ 77 SCIP_ROW* row1; 78 SCIP_ROW* row2; 79 SCIP_Real row1scale; 80 SCIP_Real row2scale; 81 SCIP_SET* set; 82 83 row1 = (SCIP_ROW*)key1; 84 row2 = (SCIP_ROW*)key2; 85 assert(row1 != NULL); 86 assert(row2 != NULL); 87 88 /* return true if the row is the same */ 89 if( row1 == row2 ) 90 return TRUE; 91 92 assert(row1->validminmaxidx); 93 assert(row2->validminmaxidx); 94 95 /* compare the trivial characteristics of the rows */ 96 if( row1->len != row2->len 97 || row1->minidx != row2->minidx 98 || row1->maxidx != row2->maxidx 99 ) 100 return FALSE; 101 102 set = (SCIP_SET*) userptr; 103 104 /* set scale for the rows such that the largest absolute coefficient is 1.0 */ 105 row1scale = 1.0 / SCIProwGetMaxval(row1, set); 106 row2scale = 1.0 / SCIProwGetMaxval(row2, set); 107 108 /* check if scaled min value is feas equal first */ 109 if( !SCIPsetIsFeasEQ(set, row1scale * SCIProwGetMinval(row1, set), 110 row2scale * SCIProwGetMinval(row2, set)) ) 111 return FALSE; 112 113 SCIProwSort(row1); 114 assert(row1->lpcolssorted); 115 assert(row1->nonlpcolssorted); 116 117 SCIProwSort(row2); 118 assert(row2->lpcolssorted); 119 assert(row2->nonlpcolssorted); 120 121 /* currently we are only handling rows which are completely linked or not linked at all */ 122 assert(row1->nunlinked == 0 || row1->nlpcols == 0); 123 assert(row2->nunlinked == 0 || row2->nlpcols == 0); 124 125 /* set scale sign such that the rows are of the form ax <= b */ 126 if( SCIPsetIsInfinity(set, row1->rhs) ) 127 row1scale = -row1scale; 128 if( SCIPsetIsInfinity(set, row2->rhs) ) 129 row2scale = -row2scale; 130 131 /* both rows have LP columns, or none of them has, or one has only LP colums and the other only non-LP columns, 132 * so we can rely on the sorting of the columns 133 */ 134 if( (row1->nlpcols == 0) == (row2->nlpcols == 0) 135 || (row1->nlpcols == 0 && row2->nlpcols == row2->len) 136 || (row1->nlpcols == row1->len && row2->nlpcols == 0) ) 137 { 138 int i; 139 140 if( (row1->nlpcols == 0) == (row2->nlpcols == 0) ) 141 { 142 #ifndef NDEBUG 143 /* in debug mode, we check that we can rely on the partition into LP columns and non-LP columns */ 144 int i2; 145 146 i = 0; 147 i2 = row2->nlpcols; 148 while( i < row1->nlpcols && i2 < row2->len ) 149 { 150 assert(row1->cols[i] != row2->cols[i2]); 151 if( row1->cols_index[i] < row2->cols_index[i2] ) 152 ++i; 153 else 154 { 155 assert(row1->cols_index[i] > row2->cols_index[i2]); 156 ++i2; 157 } 158 } 159 assert(i == row1->nlpcols || i2 == row2->len); 160 161 i = row1->nlpcols; 162 i2 = 0; 163 while( i < row1->len && i2 < row2->nlpcols ) 164 { 165 assert(row1->cols[i] != row2->cols[i2]); 166 if( row1->cols_index[i] < row2->cols_index[i2] ) 167 ++i; 168 else 169 { 170 assert(row1->cols_index[i] > row2->cols_index[i2]); 171 ++i2; 172 } 173 } 174 assert(i == row1->len || i2 == row2->nlpcols); 175 #endif 176 177 /* both rows are linked and the number of lpcolumns is not equal so they cannot be equal */ 178 if( row1->nlpcols != row2->nlpcols ) 179 return FALSE; 180 } 181 182 /* compare the columns of the rows */ 183 for( i = 0; i < row1->len; ++i ) 184 { 185 if( row1->cols_index[i] != row2->cols_index[i] ) 186 return FALSE; 187 } 188 189 /* compare the coefficients of the rows */ 190 for( i = 0; i < row1->len; ++i ) 191 { 192 if( !SCIPsetIsFeasEQ(set, row1scale * row1->vals[i], row2scale * row2->vals[i]) ) 193 return FALSE; 194 } 195 } 196 /* one row has LP columns, but the other not, that could be because the one without was just created and isn't 197 * linked yet; in this case, one column could be an LP column in one row and a non-LP column in the other row, so we 198 * cannot rely on the partition; thus, we iteratively check whether the next column of row1 is either the next LP 199 * column of row2 or the next non-LP column of row2 and the coefficients are equal 200 */ 201 else 202 { 203 int i1; 204 int ilp; 205 int inlp; 206 207 /* ensure that row1 is the row without LP columns, switch the rows, if neccessary */ 208 if( row2->nlpcols == 0 ) 209 { 210 SCIP_ROW* tmprow; 211 SCIP_Real tmpscale; 212 213 tmprow = row2; 214 row2 = row1; 215 row1 = tmprow; 216 217 tmpscale = row2scale; 218 row2scale = row1scale; 219 row1scale = tmpscale; 220 } 221 assert(row1->nlpcols == 0 && row2->nlpcols > 0); 222 223 ilp = 0; 224 inlp = row2->nlpcols; 225 226 /* compare the columns and coefficients of the rows */ 227 for( i1 = 0; i1 < row1->len; ++i1 ) 228 { 229 /* current column of row1 is the current LP column of row2, check the coefficient */ 230 if( ilp < row2->nlpcols && row1->cols[i1] == row2->cols[ilp] ) 231 { 232 if( !SCIPsetIsFeasEQ(set, row1scale * row1->vals[i1], row2scale * row2->vals[ilp]) ) 233 return FALSE; 234 else 235 ++ilp; 236 } 237 /* current column of row1 is the current non-LP column of row2, check the coefficient */ 238 else if( inlp < row2->len && row1->cols[i1] == row2->cols[inlp] ) 239 { 240 if( !SCIPsetIsFeasEQ(set, row1scale * row1->vals[i1], row2scale * row2->vals[inlp]) ) 241 return FALSE; 242 else 243 ++inlp; 244 } 245 /* current column of row1 is neither the current LP column of row2, nor the current non-LP column of row 2 */ 246 else 247 return FALSE; 248 } 249 } 250 251 return TRUE; 252 } 253 254 static 255 SCIP_DECL_HASHKEYVAL(hashKeyValCut) 256 { /*lint --e{715}*/ 257 SCIP_ROW* row; 258 int i; 259 SCIP_Real scale; 260 SCIP_SET* set; 261 uint64_t hash; 262 263 set = (SCIP_SET*) userptr; 264 row = (SCIP_ROW*)key; 265 assert(row != NULL); 266 assert(row->len > 0); 267 268 scale = 1.0 / SCIProwGetMaxval(row, set); 269 if( SCIPsetIsInfinity(set, row->rhs) ) 270 scale = -scale; 271 272 hash = (uint64_t) (long) row->len; 273 274 for( i = 0; i < row->len; ++i ) 275 { 276 SCIP_Real val = scale * row->vals[i]; 277 278 hash += SCIPhashTwo(SCIPrealHashCode(val), row->cols_index[i]); 279 } 280 281 return hash; 282 } 283 284 285 /* 286 * dynamic memory arrays 287 */ 288 289 /** resizes cuts array to be able to store at least num entries */ 290 static 291 SCIP_RETCODE cutpoolEnsureCutsMem( 292 SCIP_CUTPOOL* cutpool, /**< cut pool */ 293 SCIP_SET* set, /**< global SCIP settings */ 294 int num /**< minimal number of slots in array */ 295 ) 296 { 297 assert(cutpool != NULL); 298 assert(set != NULL); 299 300 if( num > cutpool->cutssize ) 301 { 302 int newsize; 303 304 newsize = SCIPsetCalcMemGrowSize(set, num); 305 SCIP_ALLOC( BMSreallocMemoryArray(&cutpool->cuts, newsize) ); 306 cutpool->cutssize = newsize; 307 } 308 assert(num <= cutpool->cutssize); 309 310 return SCIP_OKAY; 311 } 312 313 314 315 /* 316 * Cut methods 317 */ 318 319 /** creates a cut and captures the row */ 320 static 321 SCIP_RETCODE cutCreate( 322 SCIP_CUT** cut, /**< pointer to store the cut */ 323 BMS_BLKMEM* blkmem, /**< block memory */ 324 SCIP_ROW* row /**< row this cut represents */ 325 ) 326 { 327 assert(cut != NULL); 328 assert(blkmem != NULL); 329 assert(row != NULL); 330 331 /* allocate cut memory */ 332 SCIP_ALLOC( BMSallocBlockMemory(blkmem, cut) ); 333 (*cut)->row = row; 334 (*cut)->age = 0; 335 (*cut)->processedlp = -1; 336 (*cut)->processedlpsol = -1; 337 (*cut)->pos = -1; 338 339 /* capture row */ 340 SCIProwCapture(row); 341 342 return SCIP_OKAY; 343 } 344 345 /** frees a cut and releases the row */ 346 static 347 SCIP_RETCODE cutFree( 348 SCIP_CUT** cut, /**< pointer to store the cut */ 349 BMS_BLKMEM* blkmem, /**< block memory */ 350 SCIP_SET* set, /**< global SCIP settings */ 351 SCIP_LP* lp /**< current LP data */ 352 ) 353 { 354 assert(cut != NULL); 355 assert(*cut != NULL); 356 assert((*cut)->row != NULL); 357 assert(blkmem != NULL); 358 359 /* release row */ 360 SCIP_CALL( SCIProwRelease(&(*cut)->row, blkmem, set, lp) ); 361 362 /* free cut memory */ 363 BMSfreeBlockMemory(blkmem, cut); 364 365 return SCIP_OKAY; 366 } 367 368 /** returns whether the cut's age exceeds the age limit */ 369 static 370 SCIP_Bool cutIsAged( 371 SCIP_CUT* cut, /**< cut to check */ 372 int agelimit /**< maximum age a cut can reach before it is deleted from the pool, or -1 */ 373 ) 374 { 375 assert(cut != NULL); 376 377 /* since agelimit can be -1 cast to unsigned before comparison, then it is the maximum unsigned value in that case */ 378 return (unsigned int)cut->age > (unsigned int)agelimit; 379 } 380 381 /** gets the row of the cut */ 382 SCIP_ROW* SCIPcutGetRow( 383 SCIP_CUT* cut /**< cut */ 384 ) 385 { 386 assert(cut != NULL); 387 388 return cut->row; 389 } 390 391 /** gets the age of the cut: the number of consecutive cut pool separation rounds where the cut was neither in the LP nor violated */ 392 int SCIPcutGetAge( 393 SCIP_CUT* cut /**< cut */ 394 ) 395 { 396 assert(cut != NULL); 397 398 return cut->age; 399 } 400 401 /** returns the ratio of LPs where the row belonging to this cut was active in an LP solution, i.e. 402 * where the age of its row has not been increased 403 * 404 * @see SCIPcutGetAge() to get the age of a cut 405 */ 406 SCIP_Real SCIPcutGetLPActivityQuot( 407 SCIP_CUT* cut /**< cut */ 408 ) 409 { 410 SCIP_Longint nlpsaftercreation; 411 SCIP_Longint activeinlpcounter; 412 413 assert(cut != NULL); 414 assert(cut->row != NULL); 415 416 nlpsaftercreation = SCIProwGetNLPsAfterCreation(cut->row); 417 activeinlpcounter = SCIProwGetActiveLPCount(cut->row); 418 419 return (nlpsaftercreation > 0 ? activeinlpcounter / (SCIP_Real)nlpsaftercreation : 0.0); 420 } 421 422 /* 423 * Cutpool methods 424 */ 425 426 /** creates cut pool */ 427 SCIP_RETCODE SCIPcutpoolCreate( 428 SCIP_CUTPOOL** cutpool, /**< pointer to store cut pool */ 429 BMS_BLKMEM* blkmem, /**< block memory */ 430 SCIP_SET* set, /**< global SCIP settings */ 431 int agelimit, /**< maximum age a cut can reach before it is deleted from the pool */ 432 SCIP_Bool globalcutpool /**< is this the global cut pool of SCIP? */ 433 ) 434 { 435 assert(cutpool != NULL); 436 assert(agelimit >= -1); 437 438 SCIP_ALLOC( BMSallocMemory(cutpool) ); 439 440 SCIP_CALL( SCIPclockCreate(&(*cutpool)->poolclock, SCIP_CLOCKTYPE_DEFAULT) ); 441 442 SCIP_CALL( SCIPhashtableCreate(&(*cutpool)->hashtable, blkmem, 443 (set->misc_usesmalltables ? SCIP_HASHSIZE_CUTPOOLS_SMALL : SCIP_HASHSIZE_CUTPOOLS), 444 hashGetKeyCut, hashKeyEqCut, hashKeyValCut, (void*) set) ); 445 446 (*cutpool)->cuts = NULL; 447 (*cutpool)->cutssize = 0; 448 (*cutpool)->ncuts = 0; 449 (*cutpool)->nremovablecuts = 0; 450 (*cutpool)->agelimit = agelimit; 451 (*cutpool)->processedlp = -1; 452 (*cutpool)->processedlpsol = -1; 453 (*cutpool)->processedlpefficacy = SCIP_INVALID; 454 (*cutpool)->processedlpsolefficacy = SCIP_INVALID; 455 (*cutpool)->firstunprocessed = 0; 456 (*cutpool)->firstunprocessedsol = 0; 457 (*cutpool)->maxncuts = 0; 458 (*cutpool)->ncalls = 0; 459 (*cutpool)->nrootcalls = 0; 460 (*cutpool)->ncutsfound = 0; 461 (*cutpool)->ncutsadded = 0; 462 (*cutpool)->globalcutpool = globalcutpool; 463 464 return SCIP_OKAY; 465 } 466 467 /** frees cut pool */ 468 SCIP_RETCODE SCIPcutpoolFree( 469 SCIP_CUTPOOL** cutpool, /**< pointer to store cut pool */ 470 BMS_BLKMEM* blkmem, /**< block memory */ 471 SCIP_SET* set, /**< global SCIP settings */ 472 SCIP_LP* lp /**< current LP data */ 473 ) 474 { 475 assert(cutpool != NULL); 476 assert(*cutpool != NULL); 477 478 /* remove all cuts from the pool */ 479 SCIP_CALL( SCIPcutpoolClear(*cutpool, blkmem, set, lp) ); 480 481 /* free clock */ 482 SCIPclockFree(&(*cutpool)->poolclock); 483 484 /* free hash table */ 485 SCIPhashtableFree(&(*cutpool)->hashtable); 486 487 BMSfreeMemoryArrayNull(&(*cutpool)->cuts); 488 BMSfreeMemory(cutpool); 489 490 return SCIP_OKAY; 491 } 492 493 /** removes all rows from the cut pool */ 494 SCIP_RETCODE SCIPcutpoolClear( 495 SCIP_CUTPOOL* cutpool, /**< cut pool */ 496 BMS_BLKMEM* blkmem, /**< block memory */ 497 SCIP_SET* set, /**< global SCIP settings */ 498 SCIP_LP* lp /**< current LP data */ 499 ) 500 { 501 int i; 502 503 assert(cutpool != NULL); 504 505 /* free cuts */ 506 SCIPhashtableRemoveAll(cutpool->hashtable); 507 for( i = 0; i < cutpool->ncuts; ++i ) 508 { 509 if( cutpool->globalcutpool ) 510 cutpool->cuts[i]->row->inglobalcutpool = FALSE; 511 SCIProwUnlock(cutpool->cuts[i]->row); 512 SCIP_CALL( cutFree(&cutpool->cuts[i], blkmem, set, lp) ); 513 } 514 515 cutpool->ncuts = 0; 516 cutpool->nremovablecuts = 0; 517 518 return SCIP_OKAY; 519 } 520 521 /** removes the cut from the cut pool */ 522 static 523 SCIP_RETCODE cutpoolDelCut( 524 SCIP_CUTPOOL* cutpool, /**< cut pool */ 525 BMS_BLKMEM* blkmem, /**< block memory */ 526 SCIP_SET* set, /**< global SCIP settings */ 527 SCIP_STAT* stat, /**< problem statistics data */ 528 SCIP_LP* lp, /**< current LP data */ 529 SCIP_CUT* cut /**< cut to remove */ 530 ) 531 { 532 int pos; 533 534 assert(cutpool != NULL); 535 assert(cutpool->firstunprocessed <= cutpool->ncuts); 536 assert(cutpool->firstunprocessedsol <= cutpool->ncuts); 537 assert(blkmem != NULL); 538 assert(stat != NULL); 539 assert(cutpool->processedlp <= stat->lpcount); 540 assert(cutpool->processedlpsol <= stat->lpcount); 541 assert(cut != NULL); 542 assert(cut->row != NULL); 543 544 pos = cut->pos; 545 assert(0 <= pos && pos < cutpool->ncuts); 546 assert(cutpool->cuts[pos] == cut); 547 548 /* decrease the number of removable cuts counter (row might have changed its removable status -> counting might not 549 * be correct 550 */ 551 if( SCIProwIsRemovable(cut->row) && cutpool->nremovablecuts > 0 ) 552 cutpool->nremovablecuts--; 553 554 /* if this is the global cut pool of SCIP, mark the row to not be member anymore */ 555 if( cutpool->globalcutpool ) 556 { 557 assert(cut->row->inglobalcutpool); 558 cut->row->inglobalcutpool = FALSE; 559 } 560 561 /* remove the cut from the hash table */ 562 assert(SCIPhashtableExists(cutpool->hashtable, (void*)cut)); 563 SCIP_CALL( SCIPhashtableRemove(cutpool->hashtable, (void*)cut) ); 564 assert(! SCIPhashtableExists(cutpool->hashtable, (void*)cut)); 565 566 /* unlock the row */ 567 SCIProwUnlock(cut->row); 568 569 /* free the cut */ 570 SCIP_CALL( cutFree(&cutpool->cuts[pos], blkmem, set, lp) ); 571 572 --cutpool->ncuts; 573 cutpool->firstunprocessed = MIN(cutpool->firstunprocessed, cutpool->ncuts); 574 cutpool->firstunprocessedsol = MIN(cutpool->firstunprocessedsol, cutpool->ncuts); 575 576 /* move the last cut of the pool to the free position */ 577 if( pos < cutpool->ncuts ) 578 { 579 cutpool->cuts[pos] = cutpool->cuts[cutpool->ncuts]; 580 cutpool->cuts[pos]->pos = pos; 581 assert(cutpool->cuts[pos]->processedlp <= stat->lpcount); 582 assert(cutpool->cuts[pos]->processedlpsol <= stat->lpcount); 583 if( cutpool->cuts[pos]->processedlp < stat->lpcount ) 584 cutpool->firstunprocessed = MIN(cutpool->firstunprocessed, pos); 585 if( cutpool->cuts[pos]->processedlpsol < stat->lpcount ) 586 cutpool->firstunprocessedsol = MIN(cutpool->firstunprocessedsol, pos); 587 } 588 589 return SCIP_OKAY; 590 } 591 592 /** checks if cut is already existing */ 593 SCIP_Bool SCIPcutpoolIsCutNew( 594 SCIP_CUTPOOL* cutpool, /**< cut pool */ 595 SCIP_SET* set, /**< global SCIP settings */ 596 SCIP_ROW* row /**< cutting plane to add */ 597 ) 598 { 599 SCIP_CUT* othercut; 600 assert(cutpool != NULL); 601 assert(row != NULL); 602 603 if( row->len == 0 ) 604 { 605 /* trivial cut is only new if it proves infeasibility */ 606 return SCIPsetIsFeasLT(set, row->constant, row->lhs) || SCIPsetIsFeasGT(set, row->constant, row->rhs); 607 } 608 609 othercut = (SCIP_CUT*)SCIPhashtableRetrieve(cutpool->hashtable, (void*)row); 610 /* check in hash table, if cut already exists in the pool */ 611 if( othercut == NULL ) 612 { 613 return TRUE; 614 } 615 else if( othercut->row != row ) 616 { 617 SCIP_ROW* otherrow = othercut->row; 618 SCIP_Real otherrhs; 619 SCIP_Real rhs; 620 SCIP_Real scale; 621 SCIP_Real otherscale; 622 623 /* since we are comparing the improvement with an absolute value, we apply a 624 * scale to both rows such that the max absolute value is 1.0. 625 * Then bring the cut into the form ax <= b 626 */ 627 scale = 1.0 / SCIProwGetMaxval(row, set); 628 otherscale = 1.0 / SCIProwGetMaxval(otherrow, set); 629 630 if( SCIPsetIsInfinity(set, otherrow->rhs) ) 631 { 632 otherrhs = otherscale * (otherrow->constant - otherrow->lhs); 633 } 634 else 635 { 636 otherrhs = otherscale * (otherrow->rhs - otherrow->constant); 637 } 638 639 if( SCIPsetIsInfinity(set, row->rhs) ) 640 { 641 rhs = scale * (row->constant - row->lhs); 642 } 643 else 644 { 645 rhs = scale * (row->rhs - row->constant); 646 } 647 648 if( SCIPsetIsFeasLT(set, rhs, otherrhs) ) 649 return TRUE; 650 } 651 652 return FALSE; 653 } 654 655 /** if not already existing, adds row to cut pool and captures it */ 656 SCIP_RETCODE SCIPcutpoolAddRow( 657 SCIP_CUTPOOL* cutpool, /**< cut pool */ 658 BMS_BLKMEM* blkmem, /**< block memory */ 659 SCIP_SET* set, /**< global SCIP settings */ 660 SCIP_STAT* stat, /**< problem statistics data */ 661 SCIP_LP* lp, /**< current LP data */ 662 SCIP_ROW* row /**< cutting plane to add */ 663 ) 664 { 665 SCIP_CUT* othercut; 666 assert(cutpool != NULL); 667 assert(row != NULL); 668 669 if( row->len == 0 ) 670 return SCIP_OKAY; 671 672 if( !row->validminmaxidx ) 673 { 674 /* only called to ensure that minidx and maxidx are up to date */ 675 (void) SCIProwGetMaxidx(row, set); 676 } 677 assert(row->validminmaxidx); 678 679 othercut = (SCIP_CUT*)SCIPhashtableRetrieve(cutpool->hashtable, (void*)row); 680 /* check in hash table, if cut already exists in the pool */ 681 if( othercut == NULL ) 682 { 683 SCIP_CALL( SCIPcutpoolAddNewRow(cutpool, blkmem, set, stat, lp, row) ); 684 } 685 else 686 { 687 SCIP_ROW* otherrow = othercut->row; 688 SCIP_Real otherrhs; 689 SCIP_Real rhs; 690 SCIP_Real scale; 691 SCIP_Real otherscale; 692 693 /* since we are comparing the improvement with an absolute value, we apply a 694 * scale to both rows such that the max absolute value is 1.0. 695 * Then bring the cut into the form ax <= b 696 */ 697 scale = 1.0 / SCIProwGetMaxval(row, set); 698 otherscale = 1.0 / SCIProwGetMaxval(otherrow, set); 699 700 if( SCIPsetIsInfinity(set, otherrow->rhs) ) 701 { 702 otherrhs = otherscale * (otherrow->constant - otherrow->lhs); 703 } 704 else 705 { 706 otherrhs = otherscale * (otherrow->rhs - otherrow->constant); 707 } 708 709 if( SCIPsetIsInfinity(set, row->rhs) ) 710 { 711 rhs = scale * (row->constant - row->lhs); 712 } 713 else 714 { 715 rhs = scale * (row->rhs - row->constant); 716 } 717 718 if( SCIPsetIsFeasLT(set, rhs, otherrhs) ) 719 { 720 SCIP_CALL( cutpoolDelCut(cutpool, blkmem, set, stat, lp, othercut) ); 721 722 /* use recursion, since in rare cases new cut might compare equal to multiple other cuts 723 * that do not compare equal themselve due to non-transitivity of epsilon comparisons 724 */ 725 SCIP_CALL( SCIPcutpoolAddRow(cutpool, blkmem, set, stat, lp, row) ); 726 } 727 } 728 729 return SCIP_OKAY; 730 } 731 732 /** adds row to cut pool and captures it; doesn't check for multiple cuts */ 733 SCIP_RETCODE SCIPcutpoolAddNewRow( 734 SCIP_CUTPOOL* cutpool, /**< cut pool */ 735 BMS_BLKMEM* blkmem, /**< block memory */ 736 SCIP_SET* set, /**< global SCIP settings */ 737 SCIP_STAT* stat, /**< problem statistics data */ 738 SCIP_LP* lp, /**< current LP data */ 739 SCIP_ROW* row /**< cutting plane to add */ 740 ) 741 { 742 SCIP_Real thisefficacy; 743 SCIP_CUT* cut; 744 745 assert(cutpool != NULL); 746 assert(row != NULL); 747 748 /* check, if row is modifiable or local */ 749 if( SCIProwIsModifiable(row) ) 750 { 751 SCIPerrorMessage("cannot store modifiable row <%s> in a cut pool\n", SCIProwGetName(row)); 752 return SCIP_INVALIDDATA; 753 } 754 if( SCIProwIsLocal(row) ) 755 { 756 SCIPerrorMessage("cannot store locally valid row <%s> in a cut pool\n", SCIProwGetName(row)); 757 return SCIP_INVALIDDATA; 758 } 759 760 assert(! row->inglobalcutpool); 761 762 if( !row->validminmaxidx ) 763 { 764 /* only called to ensure that minidx and maxidx are up-to-date */ 765 (void) SCIProwGetMaxidx(row, set); 766 } 767 assert(row->validminmaxidx); 768 769 /* create the cut */ 770 SCIP_CALL( cutCreate(&cut, blkmem, row) ); 771 cut->pos = cutpool->ncuts; 772 773 /* add cut to the pool */ 774 SCIP_CALL( cutpoolEnsureCutsMem(cutpool, set, cutpool->ncuts+1) ); 775 cutpool->cuts[cutpool->ncuts] = cut; 776 cutpool->ncuts++; 777 cutpool->ncutsfound++; 778 cutpool->maxncuts = MAX(cutpool->maxncuts, cutpool->ncuts); 779 if( SCIProwIsRemovable(row) ) 780 cutpool->nremovablecuts++; 781 782 assert(!SCIPhashtableExists(cutpool->hashtable, (void*)cut)); 783 784 /* insert cut in the hash table */ 785 SCIP_CALL( SCIPhashtableInsert(cutpool->hashtable, (void*)cut) ); 786 787 assert(SCIPhashtableExists(cutpool->hashtable, (void*)cut)); 788 789 if( SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL ) 790 { 791 thisefficacy = SCIProwGetLPEfficacy(row, set, stat, lp); 792 stat->bestefficacy = MAX(thisefficacy, stat->bestefficacy); 793 } 794 795 /* if this is the global cut pool of SCIP, mark the row to be member of the pool */ 796 if( cutpool->globalcutpool ) 797 row->inglobalcutpool = TRUE; 798 799 /* lock the row */ 800 SCIProwLock(row); 801 802 return SCIP_OKAY; 803 } 804 805 /** removes the LP row from the cut pool */ 806 SCIP_RETCODE SCIPcutpoolDelRow( 807 SCIP_CUTPOOL* cutpool, /**< cut pool */ 808 BMS_BLKMEM* blkmem, /**< block memory */ 809 SCIP_SET* set, /**< global SCIP settings */ 810 SCIP_STAT* stat, /**< problem statistics data */ 811 SCIP_LP* lp, /**< current LP data */ 812 SCIP_ROW* row /**< row to remove */ 813 ) 814 { 815 SCIP_CUT* cut; 816 817 assert(cutpool != NULL); 818 assert(row != NULL); 819 820 /* find the cut in hash table */ 821 cut = (SCIP_CUT*)SCIPhashtableRetrieve(cutpool->hashtable, (void*)row); 822 if( cut == NULL ) 823 { 824 SCIPerrorMessage("row <%s> is not existing in cutpool %p\n", SCIProwGetName(row), (void*)cutpool); 825 return SCIP_INVALIDDATA; 826 } 827 828 SCIP_CALL( cutpoolDelCut(cutpool, blkmem, set, stat, lp, cut) ); 829 830 return SCIP_OKAY; 831 } 832 833 834 /** separates cuts of the cut pool */ 835 SCIP_RETCODE SCIPcutpoolSeparate( 836 SCIP_CUTPOOL* cutpool, /**< cut pool */ 837 BMS_BLKMEM* blkmem, /**< block memory */ 838 SCIP_SET* set, /**< global SCIP settings */ 839 SCIP_STAT* stat, /**< problem statistics data */ 840 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 841 SCIP_EVENTFILTER* eventfilter, /**< event filter for global events */ 842 SCIP_LP* lp, /**< current LP data */ 843 SCIP_SEPASTORE* sepastore, /**< separation storage */ 844 SCIP_SOL* sol, /**< solution to be separated (or NULL for LP-solution) */ 845 SCIP_Bool cutpoolisdelayed, /**< is the cutpool delayed (count cuts found)? */ 846 SCIP_Bool root, /**< are we at the root node? */ 847 SCIP_RESULT* result /**< pointer to store the result of the separation call */ 848 ) 849 { 850 SCIP_CUT* cut; 851 SCIP_Bool found; 852 SCIP_Bool cutoff; 853 SCIP_Real minefficacy; 854 SCIP_Bool retest; 855 int firstunproc; 856 int oldncutsadded; 857 int oldncutsfound; 858 int nefficaciouscuts; 859 int c; 860 861 assert(cutpool != NULL); 862 assert(stat != NULL); 863 assert(cutpool->processedlp <= stat->lpcount); 864 assert(cutpool->processedlpsol <= stat->lpcount); 865 assert(cutpool->firstunprocessed <= cutpool->ncuts); 866 assert(cutpool->firstunprocessedsol <= cutpool->ncuts); 867 assert(result != NULL); 868 869 *result = SCIP_DIDNOTRUN; 870 871 /* don't separate cut pool in the root node, if there are no removable cuts */ 872 if( root && cutpool->nremovablecuts == 0 ) 873 return SCIP_OKAY; 874 875 if ( sol == NULL ) 876 { 877 if( cutpool->processedlp < stat->lpcount ) 878 cutpool->firstunprocessed = 0; 879 if( cutpool->firstunprocessed == cutpool->ncuts ) 880 return SCIP_OKAY; 881 firstunproc = cutpool->firstunprocessed; 882 } 883 else 884 { 885 if( cutpool->processedlpsol < stat->lpcount ) 886 cutpool->firstunprocessedsol = 0; 887 if( cutpool->firstunprocessedsol == cutpool->ncuts ) 888 return SCIP_OKAY; 889 firstunproc = cutpool->firstunprocessedsol; 890 } 891 892 *result = SCIP_DIDNOTFIND; 893 cutpool->ncalls++; 894 if( root ) 895 cutpool->nrootcalls++; 896 found = FALSE; 897 if( set->sepa_filtercutpoolrel ) 898 minefficacy = stat->bestefficacy * stat->minefficacyfac; 899 else 900 minefficacy = root ? set->sepa_minefficacyroot : set->sepa_minefficacy; 901 902 if( sol == NULL ) 903 { 904 retest = cutpool->processedlpefficacy > minefficacy; 905 cutpool->processedlpefficacy = minefficacy; 906 } 907 else 908 { 909 retest = cutpool->processedlpsolefficacy > minefficacy; 910 cutpool->processedlpsolefficacy = minefficacy; 911 } 912 913 SCIPsetDebugMsg(set, "separating%s cut pool %p with %d cuts, beginning with cut %d\n", ( sol == NULL ) ? "" : " solution from", (void*)cutpool, cutpool->ncuts, firstunproc); 914 915 /* start timing */ 916 SCIPclockStart(cutpool->poolclock, set); 917 918 /* remember the current total number of found cuts */ 919 oldncutsfound = SCIPsepastoreGetNCuts(sepastore); 920 oldncutsadded = SCIPsepastoreGetNCutsAdded(sepastore); 921 nefficaciouscuts = 0; 922 923 /* process all unprocessed cuts in the pool */ 924 cutoff = FALSE; 925 for( c = firstunproc; c < cutpool->ncuts; ++c ) 926 { 927 SCIP_Longint proclp; 928 929 cut = cutpool->cuts[c]; 930 assert(cut != NULL); 931 assert(cut->processedlp <= stat->lpcount); 932 assert(cut->processedlpsol <= stat->lpcount); 933 assert(cut->pos == c); 934 935 proclp = ( sol == NULL ) ? cut->processedlp : cut->processedlpsol; 936 937 if( retest || proclp < stat->lpcount ) 938 { 939 SCIP_ROW* row; 940 941 if ( sol == NULL ) 942 cut->processedlp = stat->lpcount; 943 else 944 cut->processedlpsol = stat->lpcount; 945 946 row = cut->row; 947 if( !SCIProwIsInLP(row) ) 948 { 949 SCIP_Real efficacy; 950 951 /* if the cut is a bound change (i.e. a row with only one variable), add it as bound change instead of LP 952 * row; hence, we want to remove the bound change cut from the SCIP cut pool 953 */ 954 if( !SCIProwIsModifiable(row) && SCIProwGetNNonz(row) == 1 ) 955 { 956 /* insert bound change cut into separation store which will force that cut; 957 * fromcutpool is set for consistency. 958 */ 959 row->fromcutpool = TRUE; 960 SCIP_CALL( SCIPsepastoreAddCut(sepastore, blkmem, set, stat, eventqueue, eventfilter, lp, row, FALSE, root, &cutoff) ); 961 SCIP_CALL( cutpoolDelCut(cutpool, blkmem, set, stat, lp, cut) ); 962 963 if ( cutoff ) 964 break; 965 966 continue; 967 } 968 969 efficacy = sol == NULL ? SCIProwGetLPEfficacy(row, set, stat, lp) : SCIProwGetSolEfficacy(row, set, stat, sol); 970 if( SCIPsetIsFeasPositive(set, efficacy) ) 971 ++nefficaciouscuts; 972 973 if( efficacy >= minefficacy ) 974 { 975 /* insert cut in separation storage */ 976 row->fromcutpool = TRUE; 977 SCIPsetDebugMsg(set, " -> separated cut <%s> from the cut pool (feasibility: %g)\n", 978 SCIProwGetName(row), ( sol == NULL ) ? SCIProwGetLPFeasibility(row, set, stat, lp) : SCIProwGetSolFeasibility(row, set, stat, sol) ); 979 SCIP_CALL( SCIPsepastoreAddCut(sepastore, blkmem, set, stat, eventqueue, eventfilter, lp, row, FALSE, root, &cutoff) ); 980 981 /* count cuts */ 982 if ( cutpoolisdelayed ) 983 { 984 if ( SCIProwGetOriginSepa(row) != NULL ) 985 { 986 SCIP_SEPA* sepa; 987 988 sepa = SCIProwGetOriginSepa(row); 989 SCIPsepaIncNCutsAdded(sepa, TRUE); 990 SCIPsepaIncNCutsFoundAtNode(sepa); 991 } 992 else if ( SCIProwGetOriginConshdlr(row) != NULL ) 993 { 994 SCIP_CONSHDLR* conshdlr; 995 996 conshdlr = SCIProwGetOriginConshdlr(row); 997 SCIPconshdlrIncNCutsFound(conshdlr); 998 } 999 } 1000 1001 found = TRUE; 1002 cut->age = 0; 1003 1004 if ( cutoff ) 1005 break; 1006 } 1007 else 1008 { 1009 cut->age++; 1010 if( cutIsAged(cut, cutpool->agelimit) ) 1011 { 1012 SCIP_CALL( cutpoolDelCut(cutpool, blkmem, set, stat, lp, cut) ); 1013 } 1014 } 1015 } 1016 } 1017 } 1018 1019 if ( sol == NULL ) 1020 { 1021 cutpool->processedlp = stat->lpcount; 1022 cutpool->firstunprocessed = cutpool->ncuts; 1023 } 1024 else 1025 { 1026 cutpool->processedlpsol = stat->lpcount; 1027 cutpool->firstunprocessedsol = cutpool->ncuts; 1028 } 1029 /* update the number of found and added cuts */ 1030 cutpool->ncutsadded += SCIPsepastoreGetNCutsAdded(sepastore) - oldncutsadded; /*lint !e776*/ 1031 1032 /* check whether efficacy threshold should be tightened or relaxed */ 1033 if( set->sepa_filtercutpoolrel && nefficaciouscuts > 0 ) 1034 { 1035 int maxncuts = SCIPsetGetSepaMaxcuts(set, root); 1036 int ncuts = SCIPsepastoreGetNCuts(sepastore) - oldncutsfound; 1037 1038 maxncuts = MIN(maxncuts, nefficaciouscuts); 1039 1040 if( ncuts > (0.5 * maxncuts) ) 1041 { 1042 stat->ncutpoolfails = MIN(stat->ncutpoolfails - 1, -1); 1043 } 1044 else if( ncuts == 0 || (ncuts < (0.05 * maxncuts)) ) 1045 { 1046 stat->ncutpoolfails = MAX(stat->ncutpoolfails + 1, 1); 1047 } 1048 1049 if( stat->ncutpoolfails == (root ? 2 : 10) ) 1050 { 1051 cutpool->firstunprocessed = 0; 1052 cutpool->firstunprocessedsol = 0; 1053 stat->minefficacyfac *= 0.5; 1054 stat->ncutpoolfails = 0; 1055 } 1056 else if( stat->ncutpoolfails == -2 ) 1057 { 1058 stat->minefficacyfac *= 1.2; 1059 stat->ncutpoolfails = 0; 1060 } 1061 } 1062 1063 /* stop timing */ 1064 SCIPclockStop(cutpool->poolclock, set); 1065 1066 if ( cutoff ) 1067 *result = SCIP_CUTOFF; 1068 else if( found ) 1069 *result = SCIP_SEPARATED; 1070 1071 return SCIP_OKAY; 1072 } 1073 1074 /** gets array of cuts in the cut pool */ 1075 SCIP_CUT** SCIPcutpoolGetCuts( 1076 SCIP_CUTPOOL* cutpool /**< cut pool */ 1077 ) 1078 { 1079 assert(cutpool != NULL); 1080 1081 return cutpool->cuts; 1082 } 1083 1084 /** gets number of cuts in the cut pool */ 1085 int SCIPcutpoolGetNCuts( 1086 SCIP_CUTPOOL* cutpool /**< cut pool */ 1087 ) 1088 { 1089 assert(cutpool != NULL); 1090 1091 return cutpool->ncuts; 1092 } 1093 1094 /** gets maximum number of cuts that were stored in the cut pool at the same time */ 1095 SCIP_Longint SCIPcutpoolGetMaxNCuts( 1096 SCIP_CUTPOOL* cutpool /**< cut pool */ 1097 ) 1098 { 1099 assert(cutpool != NULL); 1100 1101 return cutpool->maxncuts; 1102 } 1103 1104 /** gets time in seconds used for separating cuts from the pool */ 1105 SCIP_Real SCIPcutpoolGetTime( 1106 SCIP_CUTPOOL* cutpool /**< cut pool */ 1107 ) 1108 { 1109 assert(cutpool != NULL); 1110 1111 return SCIPclockGetTime(cutpool->poolclock); 1112 } 1113 1114 /** get number of times the cut pool was separated */ 1115 SCIP_Longint SCIPcutpoolGetNCalls( 1116 SCIP_CUTPOOL* cutpool /**< cut pool */ 1117 ) 1118 { 1119 assert(cutpool != NULL); 1120 1121 return cutpool->ncalls; 1122 } 1123 1124 /** get number of times the cut pool was separated at the root */ 1125 SCIP_Longint SCIPcutpoolGetNRootCalls( 1126 SCIP_CUTPOOL* cutpool /**< cut pool */ 1127 ) 1128 { 1129 assert(cutpool != NULL); 1130 1131 return cutpool->nrootcalls; 1132 } 1133 1134 /** get total number of cuts that were added to the cut pool */ 1135 SCIP_Longint SCIPcutpoolGetNCutsFound( 1136 SCIP_CUTPOOL* cutpool /**< cut pool */ 1137 ) 1138 { 1139 assert(cutpool != NULL); 1140 1141 return cutpool->ncutsfound; 1142 } 1143 1144 /** get total number of cuts that were added from the cut pool to sepastore */ 1145 SCIP_Longint SCIPcutpoolGetNCutsAdded( 1146 SCIP_CUTPOOL* cutpool /**< cut pool */ 1147 ) 1148 { 1149 assert(cutpool != NULL); 1150 1151 return cutpool->ncutsadded; 1152 } 1153 1154 /** adds the maximum number of cuts that were stored in the pool; 1155 * this is primarily used to keep statistics when SCIP performs a restart */ 1156 void SCIPcutpoolAddMaxNCuts( 1157 SCIP_CUTPOOL* cutpool, /**< cut pool */ 1158 SCIP_Longint ncuts /**< number of cuts to add */ 1159 ) 1160 { 1161 assert(cutpool != NULL); 1162 1163 cutpool->maxncuts += ncuts; 1164 } 1165 1166 /** sets time in seconds used for separating cuts from the pool; 1167 * this is primarily used to keep statistics when SCIP performs a restart */ 1168 void SCIPcutpoolSetTime( 1169 SCIP_CUTPOOL* cutpool, /**< cut pool */ 1170 SCIP_Real time /**< poolclock time */ 1171 ) 1172 { 1173 assert(cutpool != NULL); 1174 1175 SCIPclockSetTime(cutpool->poolclock, time); 1176 } 1177 1178 /** adds the number of times the cut pool was separated; 1179 * this is primarily used to keep statistics when SCIP performs a restart */ 1180 void SCIPcutpoolAddNCalls( 1181 SCIP_CUTPOOL* cutpool, /**< cut pool */ 1182 SCIP_Longint ncalls /**< ncalls */ 1183 ) 1184 { 1185 assert(cutpool != NULL); 1186 1187 cutpool->ncalls += ncalls; 1188 } 1189 1190 /** adds the number of times the cut pool was separated at the root; 1191 * this is primarily used to keep statistics when SCIP performs a restart */ 1192 void SCIPcutpoolAddNRootCalls( 1193 SCIP_CUTPOOL* cutpool, /**< cut pool */ 1194 SCIP_Longint nrootcalls /**< nrootcalls */ 1195 ) 1196 { 1197 assert(cutpool != NULL); 1198 1199 cutpool->nrootcalls += nrootcalls; 1200 } 1201 1202 /** adds the total number of cuts that were added to the pool; 1203 * this is primarily used to keep statistics when SCIP performs a restart */ 1204 void SCIPcutpoolAddNCutsFound( 1205 SCIP_CUTPOOL* cutpool, /**< cut pool */ 1206 SCIP_Longint ncutsfound /**< total number of cuts added to cut pool */ 1207 ) 1208 { 1209 assert(cutpool != NULL); 1210 1211 cutpool->ncutsfound += ncutsfound; 1212 } 1213 1214 /** adds the total number of cuts that were separated from the pool; 1215 * this is primarily used to keep statistics when SCIP performs a restart */ 1216 void SCIPcutpoolAddNCutsAdded( 1217 SCIP_CUTPOOL* cutpool, /**< cut pool */ 1218 SCIP_Longint ncutsadded /**< total number of cuts added from cut pool to sepastore */ 1219 ) 1220 { 1221 assert(cutpool != NULL); 1222 1223 cutpool->ncutsadded += ncutsadded; 1224 } 1225