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 conflictstore.c 26 * @ingroup OTHER_CFILES 27 * @brief methods for storing conflicts 28 * @author Jakob Witzig 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include <assert.h> 34 #include <string.h> 35 36 #include "scip/conflictstore.h" 37 #include "scip/cons.h" 38 #include "scip/event.h" 39 #include "scip/set.h" 40 #include "scip/tree.h" 41 #include "scip/misc.h" 42 #include "scip/prob.h" 43 #include "scip/reopt.h" 44 #include "scip/scip.h" 45 #include "scip/def.h" 46 #include "scip/cons_linear.h" 47 #include "scip/struct_conflictstore.h" 48 49 50 #define CONFLICTSTORE_DUALRAYSIZE 100 /* default size of conflict store */ 51 #define CONFLICTSTORE_DUALSOLSIZE 75 /* default size of conflict store */ 52 #define CONFLICTSTORE_MINSIZE 2000 /* default minimal size of a dynamic conflict store */ 53 #define CONFLICTSTORE_MAXSIZE 60000 /* maximal size of a dynamic conflict store (multiplied by 3) */ 54 #define CONFLICTSTORE_SIZE 10000 /* default size of conflict store */ 55 #define CONFLICTSTORE_SORTFREQ 20 /* frequency to resort the conflict array */ 56 57 /* event handler properties */ 58 #define EVENTHDLR_NAME "ConflictStore" 59 #define EVENTHDLR_DESC "Solution event handler for conflict store." 60 61 62 /* exec the event handler */ 63 static 64 SCIP_DECL_EVENTEXEC(eventExecConflictstore) 65 {/*lint --e{715}*/ 66 assert(eventhdlr != NULL); 67 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 68 assert(event != NULL); 69 assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_BESTSOLFOUND); 70 71 if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING || SCIPgetStage(scip) == SCIP_STAGE_SOLVING ) 72 { 73 SCIP_CALL( SCIPclearConflictStore(scip, event) ); 74 } 75 76 return SCIP_OKAY; 77 } 78 79 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */ 80 static 81 SCIP_DECL_EVENTINITSOL(eventInitsolConflictstore) 82 { 83 SCIP_Bool cleanboundexceeding; 84 85 assert(scip != NULL); 86 assert(eventhdlr != NULL); 87 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 88 89 SCIP_CALL( SCIPgetBoolParam(scip, "conflict/cleanboundexceedings", &cleanboundexceeding) ); 90 91 if( !cleanboundexceeding ) 92 return SCIP_OKAY; 93 94 SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_BESTSOLFOUND, eventhdlr, NULL, NULL) ); 95 96 return SCIP_OKAY; 97 } 98 99 /** solving process deinitialization method of event handler (called before branch and bound process data is freed) */ 100 static 101 SCIP_DECL_EVENTEXITSOL(eventExitsolConflictstore) 102 { 103 SCIP_Bool cleanboundexceeding; 104 105 assert(scip != NULL); 106 assert(eventhdlr != NULL); 107 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 108 109 SCIP_CALL( SCIPgetBoolParam(scip, "conflict/cleanboundexceedings", &cleanboundexceeding) ); 110 111 if( !cleanboundexceeding ) 112 return SCIP_OKAY; 113 114 SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_BESTSOLFOUND, eventhdlr, NULL, -1) ); 115 116 return SCIP_OKAY; 117 } 118 119 /* comparison method for constraints */ 120 static 121 SCIP_DECL_SORTPTRCOMP(compareConss) 122 { 123 /*lint --e{715}*/ 124 SCIP_CONS* cons1 = (SCIP_CONS*)elem1; 125 SCIP_CONS* cons2 = (SCIP_CONS*)elem2; 126 127 assert(cons1 != NULL); 128 assert(cons2 != NULL); 129 130 if( SCIPconsGetAge(cons1) > SCIPconsGetAge(cons2) + 1e-09 ) 131 return -1; 132 else if ( SCIPconsGetAge(cons1) < SCIPconsGetAge(cons2) - 1e-09 ) 133 return +1; 134 else 135 #ifdef SCIP_DISABLED_CODE 136 /* @todo if both constraints have the same age we prefere the constraint with more non-zeros 137 * this requires a larges change of the callback, passing void-pointer (i.e. a scip 138 * object) would necessary. 139 */ 140 { 141 SCIP_Bool success; 142 int nvars1; 143 int nvars2; 144 145 SCIP_CALL( SCIPgetConsNVars(scip, cons1, &nvars1, &success) ); 146 assert(success); 147 148 SCIP_CALL( SCIPgetConsNVars(scip, cons2, &nvars2, &success) ); 149 assert(success); 150 151 if( nvars1 >= nvars2 ) 152 return -1; 153 else 154 return +1; 155 } 156 #else 157 { 158 SCIP_CONSHDLR* conshdlr1 = SCIPconsGetHdlr(cons1); 159 SCIP_CONSHDLR* conshdlr2 = SCIPconsGetHdlr(cons2); 160 161 if( strcmp(SCIPconshdlrGetName(conshdlr1), "linear") == strcmp(SCIPconshdlrGetName(conshdlr2), "linear") ) 162 return 0; 163 else if( strcmp(SCIPconshdlrGetName(conshdlr1), "linear") == 0 ) 164 return -1; 165 else 166 return +1; 167 } 168 #endif 169 } 170 171 /* initializes the conflict store */ 172 static 173 SCIP_RETCODE initConflictstore( 174 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 175 SCIP_SET* set, /**< global SCIP settings */ 176 SCIP_PROB* transprob /**< transformed problem */ 177 ) 178 { 179 assert(conflictstore != NULL); 180 181 /* calculate the maximal size of the conflict store */ 182 if( conflictstore->maxstoresize == -1 ) 183 { 184 SCIP_CALL( SCIPsetGetIntParam(set, "conflict/maxstoresize", &conflictstore->maxstoresize) ); 185 186 /* the size should be dynamic wrt number of variables after presolving */ 187 if( conflictstore->maxstoresize == -1 ) 188 { 189 int nconss; 190 int nvars; 191 192 nconss = SCIPprobGetNConss(transprob); 193 nvars = SCIPprobGetNVars(transprob); 194 195 conflictstore->initstoresize = CONFLICTSTORE_MINSIZE; 196 conflictstore->initstoresize += 2*nconss; 197 198 if( nvars/2 <= 500 ) 199 conflictstore->initstoresize += (int) CONFLICTSTORE_MAXSIZE/100; 200 else if( nvars/2 <= 5000 ) 201 conflictstore->initstoresize += (int) CONFLICTSTORE_MAXSIZE/10; 202 else 203 conflictstore->initstoresize += CONFLICTSTORE_MAXSIZE/2; 204 205 conflictstore->initstoresize = MIN(conflictstore->initstoresize, CONFLICTSTORE_MAXSIZE); 206 conflictstore->storesize = conflictstore->initstoresize; 207 conflictstore->maxstoresize = (int)(MIN(3.0 * conflictstore->initstoresize, CONFLICTSTORE_MAXSIZE)); 208 } 209 else 210 { 211 conflictstore->initstoresize = conflictstore->maxstoresize; 212 conflictstore->storesize = conflictstore->maxstoresize; 213 } 214 215 #ifdef NDEBUG 216 if( conflictstore->maxstoresize == 0 ) 217 SCIPsetDebugMsg(set, "usage of conflict pool is disabled.\n"); 218 else 219 SCIPsetDebugMsg(set, "[init,max] size of conflict pool is [%d,%d].\n", 220 conflictstore->initstoresize, conflictstore->maxstoresize); 221 #endif 222 } 223 224 return SCIP_OKAY; 225 } 226 227 /** resizes conflict and primal bound arrays to be able to store at least num entries */ 228 static 229 SCIP_RETCODE conflictstoreEnsureMem( 230 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 231 SCIP_SET* set, /**< global SCIP settings */ 232 BMS_BLKMEM* blkmem, /**< block memory */ 233 int num /**< minimal number of slots in array */ 234 ) 235 { 236 assert(conflictstore != NULL); 237 assert(set != NULL); 238 239 /* we do not allocate more memory as allowed */ 240 if( conflictstore->conflictsize == conflictstore->maxstoresize ) 241 return SCIP_OKAY; 242 243 if( num > conflictstore->conflictsize ) 244 { 245 int newsize; 246 #ifndef NDEBUG 247 int i; 248 #endif 249 /* initialize the complete data structure */ 250 if( conflictstore->conflictsize == 0 ) 251 { 252 assert(conflictstore->storesize > 0); 253 254 newsize = MIN(conflictstore->storesize, CONFLICTSTORE_SIZE); 255 newsize = MAX(newsize, num); 256 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->conflicts, newsize) ); 257 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->confprimalbnds, newsize) ); 258 } 259 else 260 { 261 newsize = SCIPsetCalcMemGrowSize(set, num); 262 newsize = MIN(conflictstore->maxstoresize, newsize); 263 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictstore->conflicts, conflictstore->conflictsize, \ 264 newsize) ); 265 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictstore->confprimalbnds, conflictstore->conflictsize, \ 266 newsize) ); 267 } 268 269 #ifndef NDEBUG 270 for( i = conflictstore->nconflicts; i < newsize; i++ ) 271 { 272 conflictstore->conflicts[i] = NULL; 273 conflictstore->confprimalbnds[i] = -SCIPsetInfinity(set); 274 } 275 #endif 276 conflictstore->conflictsize = newsize; 277 } 278 assert(num <= conflictstore->conflictsize || conflictstore->conflictsize == conflictstore->maxstoresize); 279 280 return SCIP_OKAY; 281 } 282 283 /* increase the dynamic storage if we could not delete enough conflicts 284 * 285 * we want to have at least set->conf_maxconss free slots in the conflict array, because this is the maximal number 286 * of conflicts generated at a node. we increase the size by the minimum of set->conf_maxconss and 1% of the current 287 * store size. nevertheless, we don't exceed conflictstore->maxstoresize. 288 */ 289 static 290 void adjustStorageSize( 291 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 292 SCIP_SET* set /**< global SCIP settings */ 293 ) 294 { 295 assert(conflictstore != NULL); 296 297 /* increase storage */ 298 if( conflictstore->storesize - conflictstore->nconflicts <= set->conf_maxconss 299 && conflictstore->storesize < conflictstore->maxstoresize ) 300 { 301 SCIP_Real increase = ceil(0.01 * conflictstore->storesize); 302 conflictstore->storesize += MIN(set->conf_maxconss, (int)(increase)); 303 conflictstore->storesize = MIN(conflictstore->storesize, conflictstore->maxstoresize); 304 } 305 306 return; 307 } 308 309 /* removes conflict at position pos */ 310 static 311 SCIP_RETCODE delPosConflict( 312 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 313 SCIP_SET* set, /**< global SCIP settings */ 314 SCIP_STAT* stat, /**< dynamic SCIP statistics */ 315 SCIP_PROB* transprob, /**< transformed problem, or NULL if delete = FALSE */ 316 BMS_BLKMEM* blkmem, /**< block memory */ 317 SCIP_REOPT* reopt, /**< reoptimization data */ 318 int pos, /**< position to remove */ 319 SCIP_Bool deleteconflict /**< should the conflict be deleted? */ 320 ) 321 { 322 SCIP_CONS* conflict; 323 int lastpos; 324 325 assert(conflictstore != NULL); 326 assert(pos >= 0 && pos < conflictstore->nconflicts); 327 328 lastpos = conflictstore->nconflicts-1; 329 conflict = conflictstore->conflicts[pos]; 330 assert(conflict != NULL); 331 332 /* decrease number of conflicts depending an a cutoff bound */ 333 conflictstore->ncbconflicts -= (SCIPsetIsInfinity(set, REALABS(conflictstore->confprimalbnds[pos])) ? 0 : 1); 334 335 #ifdef SCIP_PRINT_DETAILS 336 SCIPsetDebugMsg(set, "-> remove conflict <%s> at pos=%d with age=%g\n", SCIPconsGetName(conflict), pos, SCIPconsGetAge(conflict)); 337 #endif 338 339 /* remove conflict locks */ 340 SCIP_CALL( SCIPconsAddLocks(conflict, set, SCIP_LOCKTYPE_CONFLICT, -1, 0) ); 341 342 /* mark the constraint as deleted */ 343 if( deleteconflict && !SCIPconsIsDeleted(conflict) ) 344 { 345 assert(transprob != NULL); 346 SCIP_CALL( SCIPconsDelete(conflictstore->conflicts[pos], blkmem, set, stat, transprob, reopt) ); 347 } 348 SCIP_CALL( SCIPconsRelease(&conflictstore->conflicts[pos], blkmem, set) ); 349 350 /* replace with conflict at the last position */ 351 if( pos < lastpos ) 352 { 353 conflictstore->conflicts[pos] = conflictstore->conflicts[lastpos]; 354 conflictstore->confprimalbnds[pos] = conflictstore->confprimalbnds[lastpos]; 355 } 356 357 #ifndef NDEBUG 358 conflictstore->conflicts[lastpos] = NULL; 359 conflictstore->confprimalbnds[lastpos] = -SCIPsetInfinity(set); 360 #endif 361 362 /* decrease number of conflicts */ 363 --conflictstore->nconflicts; 364 365 return SCIP_OKAY; 366 } 367 368 /* removes proof based on a dual ray at position pos */ 369 static 370 SCIP_RETCODE delPosDualray( 371 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 372 SCIP_SET* set, /**< global SCIP settings */ 373 SCIP_STAT* stat, /**< dynamic SCIP statistics */ 374 SCIP_PROB* transprob, /**< transformed problem, or NULL if delete = FALSE */ 375 BMS_BLKMEM* blkmem, /**< block memory */ 376 SCIP_REOPT* reopt, /**< reoptimization data */ 377 int pos, /**< position to remove */ 378 SCIP_Bool deleteconflict /**< should the dual ray be deleted? */ 379 ) 380 { 381 SCIP_CONS* dualproof; 382 SCIP_Bool success; 383 int lastpos; 384 int nvars; 385 386 assert(conflictstore != NULL); 387 388 lastpos = conflictstore->ndualrayconfs-1; 389 dualproof = conflictstore->dualrayconfs[pos]; 390 assert(dualproof != NULL); 391 392 /* decrease the number of non-zeros */ 393 SCIP_CALL( SCIPconsGetNVars(dualproof, set, &nvars, &success) ); 394 assert(success); 395 conflictstore->nnzdualrays -= nvars; 396 397 #ifdef SCIP_PRINT_DETAILS 398 SCIPsetDebugMsg(set, "-> remove dual proof (ray) at pos=%d age=%g nvars=%d\n", pos, SCIPconsGetAge(dualproof), nvars); 399 #endif 400 401 /* remove conflict locks */ 402 SCIP_CALL( SCIPconsAddLocks(dualproof, set, SCIP_LOCKTYPE_CONFLICT, -1, 0) ); 403 404 /* mark the constraint as deleted */ 405 if( deleteconflict && !SCIPconsIsDeleted(dualproof) ) 406 { 407 assert(transprob != NULL); 408 SCIP_CALL( SCIPconsDelete(dualproof, blkmem, set, stat, transprob, reopt) ); 409 } 410 SCIP_CALL( SCIPconsRelease(&dualproof, blkmem, set) ); 411 412 /* replace with dual ray at the last position */ 413 if( pos < lastpos ) 414 { 415 conflictstore->dualrayconfs[pos] = conflictstore->dualrayconfs[lastpos]; 416 conflictstore->drayrelaxonly[pos] = conflictstore->drayrelaxonly[lastpos]; 417 418 #ifndef NDEBUG 419 conflictstore->dualrayconfs[lastpos] = NULL; 420 conflictstore->drayrelaxonly[lastpos] = TRUE; 421 #endif 422 } 423 424 /* decrease number of dual rays */ 425 --conflictstore->ndualrayconfs; 426 427 return SCIP_OKAY; 428 } 429 430 /* removes proof based on a dual solution at position pos */ 431 static 432 SCIP_RETCODE delPosDualsol( 433 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 434 SCIP_SET* set, /**< global SCIP settings */ 435 SCIP_STAT* stat, /**< dynamic SCIP statistics */ 436 SCIP_PROB* transprob, /**< transformed problem, or NULL if delete = FALSE */ 437 BMS_BLKMEM* blkmem, /**< block memory */ 438 SCIP_REOPT* reopt, /**< reoptimization data */ 439 int pos, /**< position to remove */ 440 SCIP_Bool deleteconflict /**< should the dual ray be deleted? */ 441 ) 442 { 443 SCIP_CONS* dualproof; 444 SCIP_Bool success; 445 int lastpos; 446 int nvars; 447 448 assert(conflictstore != NULL); 449 assert(pos >= 0 && pos < conflictstore->ndualsolconfs); 450 451 lastpos = conflictstore->ndualsolconfs-1; 452 dualproof = conflictstore->dualsolconfs[pos]; 453 assert(dualproof != NULL); 454 455 /* decrease the number of non-zeros */ 456 SCIP_CALL( SCIPconsGetNVars(dualproof, set, &nvars, &success) ); 457 assert(success); 458 conflictstore->nnzdualsols -= nvars; 459 460 #ifdef SCIP_PRINT_DETAILS 461 SCIPsetDebugMsg(set, "-> remove dual proof (sol) at pos=%d age=%g nvars=%d\n", pos, SCIPconsGetAge(dualproof), nvars); 462 #endif 463 464 /* remove conflict locks */ 465 SCIP_CALL( SCIPconsAddLocks(dualproof, set, SCIP_LOCKTYPE_CONFLICT, -1, 0) ); 466 467 /* mark the constraint as deleted */ 468 if( deleteconflict && !SCIPconsIsDeleted(dualproof) ) 469 { 470 assert(transprob != NULL); 471 SCIP_CALL( SCIPconsDelete(dualproof, blkmem, set, stat, transprob, reopt) ); 472 } 473 SCIP_CALL( SCIPconsRelease(&dualproof, blkmem, set) ); 474 475 /* replace with dual ray at the last position */ 476 if( pos < lastpos ) 477 { 478 conflictstore->dualsolconfs[pos] = conflictstore->dualsolconfs[lastpos]; 479 conflictstore->dualprimalbnds[pos] = conflictstore->dualprimalbnds[lastpos]; 480 conflictstore->scalefactors[pos] = conflictstore->scalefactors[lastpos]; 481 conflictstore->updateside[pos] = conflictstore->updateside[lastpos]; 482 conflictstore->dsolrelaxonly[pos] = conflictstore->dsolrelaxonly[lastpos]; 483 484 #ifndef NDEBUG 485 conflictstore->dualsolconfs[lastpos] = NULL; 486 conflictstore->dualprimalbnds[lastpos] = SCIP_UNKNOWN; 487 conflictstore->scalefactors[lastpos] = 1.0; 488 conflictstore->updateside[lastpos] = FALSE; 489 conflictstore->dsolrelaxonly[lastpos] = TRUE; 490 #endif 491 } 492 493 /* decrease number of dual rays */ 494 --conflictstore->ndualsolconfs; 495 496 return SCIP_OKAY; 497 } 498 499 /** removes all deleted conflicts from the storage */ 500 static 501 SCIP_RETCODE cleanDeletedAndCheckedConflicts( 502 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 503 SCIP_SET* set, /**< global SCIP settings */ 504 SCIP_STAT* stat, /**< dynamic SCIP statistics */ 505 BMS_BLKMEM* blkmem, /**< block memory */ 506 SCIP_REOPT* reopt, /**< reoptimization data */ 507 int* ndelconfs /**< pointer to store the number of deleted conflicts */ 508 ) 509 { 510 int i; 511 512 assert(conflictstore != NULL); 513 514 (*ndelconfs) = 0; 515 516 /* we traverse backwards to avoid swapping of pointers */ 517 for( i = conflictstore->nconflicts-1; i >= 0; i-- ) 518 { 519 assert(conflictstore->conflicts[i] != NULL); 520 521 /* check whether the constraint is already marked as deleted */ 522 if( SCIPconsIsDeleted(conflictstore->conflicts[i]) || SCIPconsIsChecked(conflictstore->conflicts[i]) ) 523 { 524 /* remove conflict at current position */ 525 SCIP_CALL( delPosConflict(conflictstore, set, stat, NULL, blkmem, reopt, i, FALSE) ); 526 527 ++(*ndelconfs); 528 } 529 } 530 SCIPsetDebugMsg(set, "> removed %d/%d as deleted marked conflicts.\n", *ndelconfs, conflictstore->nconflicts + (*ndelconfs)); 531 532 return SCIP_OKAY; 533 } 534 535 /** removes all deleted dual proofs of infeasible LP relaxations from the storage */ 536 static 537 SCIP_RETCODE cleanDeletedAndCheckedDualrayCons( 538 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 539 SCIP_SET* set, /**< global SCIP settings */ 540 SCIP_STAT* stat, /**< dynamic SCIP statistics */ 541 BMS_BLKMEM* blkmem, /**< block memory */ 542 SCIP_REOPT* reopt, /**< reoptimization data */ 543 int* ndelproofs /**< pointer to store the number of deleted conflicts */ 544 ) 545 { 546 int i; 547 548 assert(conflictstore != NULL); 549 550 (*ndelproofs) = 0; 551 552 /* we traverse backwards to avoid swapping of pointers */ 553 for( i = conflictstore->ndualrayconfs-1; i >= 0; i-- ) 554 { 555 assert(conflictstore->dualrayconfs[i] != NULL); 556 557 /* check whether the constraint is already marked as deleted */ 558 if( SCIPconsIsDeleted(conflictstore->dualrayconfs[i]) || SCIPconsIsChecked(conflictstore->dualrayconfs[i]) ) 559 { 560 /* remove proof at current position */ 561 SCIP_CALL( delPosDualray(conflictstore, set, stat, NULL, blkmem, reopt, i, FALSE) ); 562 563 ++(*ndelproofs); 564 } 565 } 566 567 SCIPsetDebugMsg(set, "> removed %d/%d as deleted marked dual infeasibility proofs.\n", 568 *ndelproofs, conflictstore->ndualrayconfs + (*ndelproofs)); 569 570 return SCIP_OKAY; 571 } 572 573 /** removes all deleted dual proofs of bound exceeding LP relaxations from the storage */ 574 static 575 SCIP_RETCODE cleanDeletedAndCheckedDualsolCons( 576 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 577 SCIP_SET* set, /**< global SCIP settings */ 578 SCIP_STAT* stat, /**< dynamic SCIP statistics */ 579 BMS_BLKMEM* blkmem, /**< block memory */ 580 SCIP_REOPT* reopt, /**< reoptimization data */ 581 int* ndelproofs /**< pointer to store the number of deleted conflicts */ 582 ) 583 { 584 int i; 585 586 assert(conflictstore != NULL); 587 588 (*ndelproofs) = 0; 589 590 /* we traverse backwards to avoid swapping of pointers */ 591 for( i = conflictstore->ndualsolconfs-1; i >= 0; i-- ) 592 { 593 assert(conflictstore->dualsolconfs[i] != NULL); 594 595 /* check whether the constraint is already marked as deleted */ 596 if( SCIPconsIsDeleted(conflictstore->dualsolconfs[i]) || SCIPconsIsChecked(conflictstore->dualsolconfs[i]) ) 597 { 598 /* remove proof at current position */ 599 SCIP_CALL( delPosDualsol(conflictstore, set, stat, NULL, blkmem, reopt, i, FALSE) ); 600 601 ++(*ndelproofs); 602 } 603 } 604 605 SCIPsetDebugMsg(set, "> removed %d/%d as deleted marked dual boundexceeding proofs.\n", 606 *ndelproofs, conflictstore->ndualrayconfs + (*ndelproofs)); 607 608 return SCIP_OKAY; 609 } 610 611 /** cleans up the storage */ 612 static 613 SCIP_RETCODE conflictstoreCleanUpStorage( 614 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 615 SCIP_SET* set, /**< global SCIP settings */ 616 SCIP_STAT* stat, /**< dynamic SCIP statistics */ 617 SCIP_PROB* transprob, /**< transformed problem */ 618 BMS_BLKMEM* blkmem, /**< block memory */ 619 SCIP_REOPT* reopt /**< reoptimization data */ 620 ) 621 { 622 int ndelconfs; 623 624 assert(conflictstore != NULL); 625 assert(blkmem != NULL); 626 assert(set != NULL); 627 assert(stat != NULL); 628 assert(transprob != NULL); 629 630 /* the storage is empty */ 631 if( conflictstore->nconflicts == 0 ) 632 return SCIP_OKAY; 633 assert(conflictstore->nconflicts >= 1); 634 635 ndelconfs = 0; 636 637 /* remove all as deleted marked conflicts */ 638 SCIP_CALL( cleanDeletedAndCheckedConflicts(conflictstore, set, stat, blkmem, reopt, &ndelconfs) ); 639 640 /* return if at least one conflict could be deleted */ 641 if( ndelconfs > 0 ) 642 goto TERMINATE; 643 644 /* only clean up the storage if it is filled enough */ 645 if( conflictstore->nconflicts < conflictstore->conflictsize ) 646 goto TERMINATE; 647 648 /* resort the array regularly */ 649 if( conflictstore->ncleanups % CONFLICTSTORE_SORTFREQ == 0 ) 650 { 651 /* sort conflict */ 652 SCIPsortPtrReal((void**)conflictstore->conflicts, conflictstore->confprimalbnds, compareConss, conflictstore->nconflicts); 653 assert(SCIPsetIsGE(set, SCIPconsGetAge(conflictstore->conflicts[0]), 654 SCIPconsGetAge(conflictstore->conflicts[conflictstore->nconflicts-1]))); 655 } 656 assert(conflictstore->nconflicts > 0); 657 658 if( conflictstore->ncleanups % CONFLICTSTORE_SORTFREQ == 0 ) 659 { 660 /* remove conflict at first position (array is sorted) */ 661 SCIP_CALL( delPosConflict(conflictstore, set, stat, transprob, blkmem, reopt, 0, TRUE) ); 662 } 663 else 664 { 665 SCIP_Real maxage; 666 int oldest_i; 667 int i; 668 669 assert(!SCIPconsIsDeleted(conflictstore->conflicts[0])); 670 671 maxage = SCIPconsGetAge(conflictstore->conflicts[0]); 672 oldest_i = 0; 673 674 /* check the first 10% of conflicts and find the oldest */ 675 for( i = 1; i < 0.1 * conflictstore->nconflicts; i++ ) 676 { 677 assert(!SCIPconsIsDeleted(conflictstore->conflicts[i])); 678 679 if( SCIPconsGetAge(conflictstore->conflicts[i]) > maxage ) 680 { 681 maxage = SCIPconsGetAge(conflictstore->conflicts[i]); 682 oldest_i = i; 683 } 684 } 685 686 /* remove conflict at position oldest_i */ 687 SCIP_CALL( delPosConflict(conflictstore, set, stat, transprob, blkmem, reopt, oldest_i, TRUE) ); 688 } 689 ++ndelconfs; 690 691 /* adjust size of the storage if we use a dynamic store */ 692 if( set->conf_maxstoresize == -1 ) 693 adjustStorageSize(conflictstore, set); 694 assert(conflictstore->initstoresize <= conflictstore->storesize); 695 assert(conflictstore->storesize <= conflictstore->maxstoresize); 696 697 TERMINATE: 698 699 /* increase the number of clean ups */ 700 ++conflictstore->ncleanups; 701 702 SCIPsetDebugMsg(set, "clean-up #%lld: removed %d/%d conflicts, %d depending on cutoff bound\n", 703 conflictstore->ncleanups, ndelconfs, conflictstore->nconflicts+ndelconfs, conflictstore->ncbconflicts); 704 705 return SCIP_OKAY; /*lint !e438*/ 706 } 707 708 /** adds an original conflict constraint to the store 709 * 710 * @note the constraint will be only transfered to the storage of the transformed problem after calling 711 * SCIPconflictstoreTransform() 712 */ 713 static 714 SCIP_RETCODE conflictstoreAddOrigConflict( 715 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 716 SCIP_SET* set, /**< global SCIP settings */ 717 BMS_BLKMEM* blkmem, /**< block memory */ 718 SCIP_CONS* cons /**< conflict constraint */ 719 ) 720 { 721 assert(conflictstore != NULL); 722 assert(cons != NULL); 723 724 if( conflictstore->origconfs == NULL ) 725 { 726 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->origconfs, CONFLICTSTORE_MINSIZE) ); 727 conflictstore->origconflictsize = CONFLICTSTORE_MINSIZE; 728 } 729 else if( conflictstore->norigconfs == conflictstore->origconflictsize ) 730 { 731 int newsize = SCIPsetCalcMemGrowSize(set, conflictstore->origconflictsize+1); 732 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictstore->origconfs, conflictstore->origconflictsize, newsize) ); 733 conflictstore->origconflictsize = newsize; 734 } 735 736 SCIPconsCapture(cons); 737 conflictstore->origconfs[conflictstore->norigconfs] = cons; 738 ++conflictstore->norigconfs; 739 740 return SCIP_OKAY; 741 } 742 743 744 /** creates conflict store */ 745 SCIP_RETCODE SCIPconflictstoreCreate( 746 SCIP_CONFLICTSTORE** conflictstore, /**< pointer to store conflict store */ 747 SCIP_SET* set /**< global SCIP settings */ 748 ) 749 { 750 assert(conflictstore != NULL); 751 752 SCIP_ALLOC( BMSallocMemory(conflictstore) ); 753 754 (*conflictstore)->conflicts = NULL; 755 (*conflictstore)->confprimalbnds = NULL; 756 (*conflictstore)->dualprimalbnds = NULL; 757 (*conflictstore)->scalefactors = NULL; 758 (*conflictstore)->updateside = NULL; 759 (*conflictstore)->drayrelaxonly = NULL; 760 (*conflictstore)->dsolrelaxonly = NULL; 761 (*conflictstore)->dualrayconfs = NULL; 762 (*conflictstore)->dualsolconfs = NULL; 763 (*conflictstore)->origconfs = NULL; 764 (*conflictstore)->nnzdualrays = 0; 765 (*conflictstore)->nnzdualsols = 0; 766 (*conflictstore)->conflictsize = 0; 767 (*conflictstore)->origconflictsize = 0; 768 (*conflictstore)->nconflicts = 0; 769 (*conflictstore)->ndualrayconfs = 0; 770 (*conflictstore)->ndualsolconfs = 0; 771 (*conflictstore)->norigconfs = 0; 772 (*conflictstore)->ncbconflicts = 0; 773 (*conflictstore)->nconflictsfound = 0; 774 (*conflictstore)->initstoresize = -1; 775 (*conflictstore)->storesize = -1; 776 (*conflictstore)->maxstoresize = -1; 777 (*conflictstore)->ncleanups = 0; 778 (*conflictstore)->lastcutoffbound = SCIP_INVALID; 779 (*conflictstore)->lastnodenum = -1; 780 (*conflictstore)->eventhdlr = SCIPsetFindEventhdlr(set, EVENTHDLR_NAME); 781 782 /* create event handler for LP events */ 783 if( (*conflictstore)->eventhdlr == NULL ) 784 { 785 SCIP_CALL( SCIPeventhdlrCreate(&(*conflictstore)->eventhdlr, set, EVENTHDLR_NAME, EVENTHDLR_DESC, NULL, NULL, 786 NULL, NULL, eventInitsolConflictstore, eventExitsolConflictstore, NULL, eventExecConflictstore, NULL) ); 787 SCIP_CALL( SCIPsetIncludeEventhdlr(set, (*conflictstore)->eventhdlr) ); 788 } 789 assert((*conflictstore)->eventhdlr != NULL); 790 791 return SCIP_OKAY; 792 } 793 794 /** frees conflict store */ 795 SCIP_RETCODE SCIPconflictstoreFree( 796 SCIP_CONFLICTSTORE** conflictstore, /**< pointer to store conflict store */ 797 BMS_BLKMEM* blkmem, /**< block memory */ 798 SCIP_SET* set, /**< global SCIP settings */ 799 SCIP_STAT* stat, /**< dynamic SCIP statistics */ 800 SCIP_REOPT* reopt /**< reoptimization data */ 801 ) 802 { 803 assert(conflictstore != NULL); 804 assert(*conflictstore != NULL); 805 806 /* clear the storage */ 807 SCIP_CALL( SCIPconflictstoreClear(*conflictstore, blkmem, set, stat, reopt) ); 808 809 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->origconfs, (*conflictstore)->origconflictsize); 810 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->conflicts, (*conflictstore)->conflictsize); 811 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->confprimalbnds, (*conflictstore)->conflictsize); 812 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->dualrayconfs, CONFLICTSTORE_DUALRAYSIZE); 813 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->drayrelaxonly, CONFLICTSTORE_DUALRAYSIZE); 814 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->dualsolconfs, CONFLICTSTORE_DUALSOLSIZE); 815 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->dualprimalbnds, CONFLICTSTORE_DUALSOLSIZE); 816 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->scalefactors, CONFLICTSTORE_DUALSOLSIZE); 817 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->updateside, CONFLICTSTORE_DUALSOLSIZE); 818 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->dsolrelaxonly, CONFLICTSTORE_DUALSOLSIZE); 819 BMSfreeMemoryNull(conflictstore); 820 821 return SCIP_OKAY; 822 } 823 824 /** clears conflict store */ 825 SCIP_RETCODE SCIPconflictstoreClear( 826 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 827 BMS_BLKMEM* blkmem, /**< block memory */ 828 SCIP_SET* set, /**< global SCIP settings */ 829 SCIP_STAT* stat, /**< dynamic SCIP statistics */ 830 SCIP_REOPT* reopt /**< reoptimization data */ 831 ) 832 { 833 int i; 834 835 assert(conflictstore != NULL); 836 837 SCIPsetDebugMsg(set, "clearing conflict store: %d origconfs, %d conflicts, %d dual proofs\n", 838 conflictstore->norigconfs, conflictstore->nconflicts, conflictstore->ndualrayconfs + conflictstore->ndualsolconfs); 839 840 /* remove original constraints (if present) */ 841 if( conflictstore->origconfs != NULL ) 842 { 843 for( i = 0; i < conflictstore->norigconfs; i++ ) 844 { 845 SCIP_CONS* conflict = conflictstore->origconfs[i]; 846 SCIP_CALL( SCIPconsRelease(&conflict, blkmem, set) ); 847 } 848 conflictstore->norigconfs = 0; 849 } 850 851 /* clean up storage of conflict constraints */ 852 if( conflictstore->conflicts != NULL ) 853 { 854 /* we traverse in reverse order to avoid swapping of pointers */ 855 for( i = conflictstore->nconflicts-1; i >= 0; i--) 856 { 857 SCIP_CALL( delPosConflict(conflictstore, set, stat, NULL, blkmem, reopt, i, FALSE) ); 858 } 859 assert(conflictstore->nconflicts == 0); 860 } 861 862 /* clean up storage of proof constraints based on dual rays */ 863 if( conflictstore->dualrayconfs != NULL ) 864 { 865 /* we traverse in reverse order to avoid swapping of pointers */ 866 for( i = conflictstore->ndualrayconfs-1; i >= 0; i-- ) 867 { 868 SCIP_CALL( delPosDualray(conflictstore, set, stat, NULL, blkmem, reopt, i, FALSE) ); 869 } 870 assert(conflictstore->ndualrayconfs == 0); 871 } 872 873 /* clean up storage of proof constraints based on dual solutions */ 874 if( conflictstore->dualsolconfs != NULL ) 875 { 876 /* we traverse in reverse order to avoid swapping of pointers */ 877 for( i = conflictstore->ndualsolconfs-1; i >= 0; i-- ) 878 { 879 SCIP_CALL( delPosDualsol(conflictstore, set, stat, NULL, blkmem, reopt, i, FALSE) ); 880 } 881 assert(conflictstore->ndualsolconfs == 0); 882 } 883 884 return SCIP_OKAY; 885 } 886 887 /** cleans up conflict store */ 888 SCIP_RETCODE SCIPconflictstoreClean( 889 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 890 BMS_BLKMEM* blkmem, /**< block memory */ 891 SCIP_SET* set, /**< global SCIP settings */ 892 SCIP_STAT* stat, /**< dynamic SCIP statistics */ 893 SCIP_PROB* transprob, /**< transformed problem */ 894 SCIP_REOPT* reopt /**< reoptimization data */ 895 ) 896 { 897 int ndelconfs; 898 int ndeldualray; 899 int ndeldualsol; 900 901 assert(conflictstore != NULL); 902 903 SCIPsetDebugMsg(set, "cleaning conflict store: %d conflicts, %d dual proofs\n", 904 conflictstore->nconflicts, conflictstore->ndualrayconfs + conflictstore->ndualsolconfs); 905 906 ndelconfs = 0; 907 ndeldualray = 0; 908 ndeldualsol = 0; 909 910 /* remove all conflicts that are marked as deleted or where the check flag has changed to TRUE. 911 * 912 * the latter case might happen during processing parallel constraints, e.g., cons_knapsack.c:detectRedundantConstraints(). 913 * in that case, the conflict constraint should stay, e.g., it has the stricter capacity, and replaces a model 914 * constraint. hence, the conflict is now a constraint that is needed to stay correct. therefore, the conflictpool 915 * is not allowed to delete this constraint from the entire problem. 916 */ 917 SCIP_CALL( cleanDeletedAndCheckedConflicts(conflictstore, set, stat, blkmem, reopt, &ndelconfs) ); 918 919 /* remove all dual infeasibility proofs that are marked as deleted or where the check flag has changed to TRUE. */ 920 SCIP_CALL( cleanDeletedAndCheckedDualrayCons(conflictstore, set, stat, blkmem, reopt, &ndeldualray) ); 921 922 /* remove all dual bound exceeding proofs that are marked as deleted or where the check flag has changed to TRUE. */ 923 SCIP_CALL( cleanDeletedAndCheckedDualsolCons(conflictstore, set, stat, blkmem, reopt, &ndeldualsol) ); 924 925 /* don't update bound exceeding proofs after a restart 926 * 927 * TODO: check whether we want to delete bound exceeding proofs in general during a restart 928 */ 929 if( SCIPisInRestart(set->scip) ) 930 { 931 int i; 932 933 for( i = conflictstore->ndualrayconfs-1; i >= 0 ; i-- ) 934 { 935 if( conflictstore->drayrelaxonly[i] ) 936 { 937 SCIP_CALL( delPosDualray(conflictstore, set, stat, transprob, blkmem, reopt, i, TRUE) ); 938 } 939 } 940 941 for( i = conflictstore->ndualsolconfs-1; i >= 0 ; i-- ) 942 { 943 if( conflictstore->dsolrelaxonly[i] ) 944 { 945 SCIP_CALL( delPosDualsol(conflictstore, set, stat, transprob, blkmem, reopt, i, TRUE) ); 946 } 947 else 948 { 949 conflictstore->updateside[i] = FALSE; 950 } 951 } 952 } 953 954 return SCIP_OKAY; 955 } 956 957 /** adds a constraint to the pool of proof constraints based on dual rays 958 * 959 * @note this methods captures the constraint 960 */ 961 SCIP_RETCODE SCIPconflictstoreAddDualraycons( 962 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 963 SCIP_CONS* dualproof, /**< constraint based on a dual ray */ 964 BMS_BLKMEM* blkmem, /**< block memory */ 965 SCIP_SET* set, /**< global SCIP settings */ 966 SCIP_STAT* stat, /**< dynamic SCIP statistics */ 967 SCIP_PROB* transprob, /**< transformed problem */ 968 SCIP_REOPT* reopt, /**< reoptimization data */ 969 SCIP_Bool hasrelaxvar /**< does the dual proof contain at least one variable that exists in 970 * the current relaxation only? */ 971 ) 972 { 973 int nvars; 974 SCIP_Bool success; 975 976 assert(conflictstore != NULL); 977 assert(conflictstore->ndualrayconfs <= CONFLICTSTORE_DUALRAYSIZE); 978 979 /* mark the constraint to be a conflict */ 980 SCIPconsMarkConflict(dualproof); 981 982 /* create an array to store constraints based on dual rays */ 983 if( conflictstore->dualrayconfs == NULL ) 984 { 985 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->dualrayconfs, CONFLICTSTORE_DUALRAYSIZE) ); 986 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->drayrelaxonly, CONFLICTSTORE_DUALRAYSIZE) ); 987 } 988 989 /* the store is full, we proceed as follows 990 * 991 * 1. check whether some constraints are marked as deleted and remove those 992 * 2. if no constraint is marked as deleted: remove the oldest 993 */ 994 if( conflictstore->ndualrayconfs == CONFLICTSTORE_DUALRAYSIZE ) 995 { 996 int ndeleted = 0; 997 998 /* remove all as deleted marked dual infeasibility proofs */ 999 SCIP_CALL( cleanDeletedAndCheckedDualrayCons(conflictstore, set, stat, blkmem, reopt, &ndeleted) ); 1000 1001 /* if we could not remove a dual ray that is already marked as deleted we need to remove the oldest active one */ 1002 if( ndeleted == 0 ) 1003 { 1004 SCIP_Bool local = SCIPconsIsLocal(dualproof); 1005 int pos = 0; 1006 1007 /* sort dual rays */ 1008 SCIPsortPtrBool((void**)conflictstore->dualrayconfs, conflictstore->drayrelaxonly, compareConss, 1009 conflictstore->ndualrayconfs); 1010 assert(SCIPsetIsGE(set, SCIPconsGetAge(conflictstore->dualrayconfs[0]), 1011 SCIPconsGetAge(conflictstore->dualrayconfs[conflictstore->ndualrayconfs-1]))); 1012 1013 while( pos < conflictstore->ndualrayconfs-1 && local != SCIPconsIsLocal(conflictstore->dualrayconfs[pos]) ) 1014 pos++; 1015 1016 /* we don't want to keep the dual proof */ 1017 if( pos >= conflictstore->ndualrayconfs ) 1018 { 1019 SCIP_CALL( SCIPconsDelete(dualproof, blkmem, set, stat, transprob, reopt) ); 1020 return SCIP_OKAY; 1021 } 1022 1023 SCIP_CALL( delPosDualray(conflictstore, set, stat, transprob, blkmem, reopt, pos, TRUE) ); 1024 } 1025 } 1026 1027 /* add the new constraint based on a dual ray at the last position */ 1028 SCIPconsCapture(dualproof); 1029 conflictstore->dualrayconfs[conflictstore->ndualrayconfs] = dualproof; 1030 conflictstore->drayrelaxonly[conflictstore->ndualrayconfs] = hasrelaxvar; 1031 ++conflictstore->ndualrayconfs; 1032 1033 /* add conflict locks */ 1034 SCIP_CALL( SCIPconsAddLocks(dualproof, set, SCIP_LOCKTYPE_CONFLICT, +1, 0) ); 1035 1036 /* increase the number of non-zeros */ 1037 SCIP_CALL( SCIPconsGetNVars(dualproof, set, &nvars, &success) ); 1038 assert(success); 1039 conflictstore->nnzdualrays += nvars; 1040 1041 return SCIP_OKAY; 1042 } 1043 1044 /** adds a constraint to the pool of proof constraints based on dual solutions 1045 * 1046 * @note this methods captures the constraint 1047 */ 1048 SCIP_RETCODE SCIPconflictstoreAddDualsolcons( 1049 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 1050 SCIP_CONS* dualproof, /**< constraint based on a dual solution */ 1051 BMS_BLKMEM* blkmem, /**< block memory */ 1052 SCIP_SET* set, /**< global SCIP settings */ 1053 SCIP_STAT* stat, /**< dynamic SCIP statistics */ 1054 SCIP_PROB* transprob, /**< transformed problem */ 1055 SCIP_REOPT* reopt, /**< reoptimization data */ 1056 SCIP_Real scale, /**< scaling factor that needs to be considered when updating the side */ 1057 SCIP_Bool updateside, /**< should the side be updated if a new incumbent is found */ 1058 SCIP_Bool hasrelaxvar /**< does the dual proof contain at least one variable that exists in 1059 * the current relaxation only? */ 1060 ) 1061 { 1062 int nvars; 1063 SCIP_Bool success; 1064 1065 assert(conflictstore != NULL); 1066 assert(conflictstore->ndualsolconfs <= CONFLICTSTORE_DUALSOLSIZE); 1067 1068 /* mark the constraint to be a conflict */ 1069 SCIPconsMarkConflict(dualproof); 1070 1071 /* create an array to store constraints based on dual rays */ 1072 if( conflictstore->dualsolconfs == NULL ) 1073 { 1074 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->dualsolconfs, CONFLICTSTORE_DUALSOLSIZE) ); 1075 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->dualprimalbnds, CONFLICTSTORE_DUALSOLSIZE) ); 1076 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->scalefactors, CONFLICTSTORE_DUALSOLSIZE) ); 1077 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->updateside, CONFLICTSTORE_DUALSOLSIZE) ); 1078 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->dsolrelaxonly, CONFLICTSTORE_DUALSOLSIZE) ); 1079 } 1080 1081 /* the store is full, we proceed as follows 1082 * 1083 * 1. check whether some constraints are marked as deleted and remove those 1084 * 2. if no constraint is marked as deleted: remove the oldest 1085 */ 1086 if( conflictstore->ndualsolconfs == CONFLICTSTORE_DUALSOLSIZE ) 1087 { 1088 int ndeleted = 0; 1089 1090 /* remove all as deleted marked dual bound exceeding proofs */ 1091 SCIP_CALL( cleanDeletedAndCheckedDualsolCons(conflictstore, set, stat, blkmem, reopt, &ndeleted) ); 1092 1093 /* if we could not remove a dual proof that is already marked as deleted we need to remove the oldest active one */ 1094 if( ndeleted == 0 ) 1095 { 1096 SCIP_Bool local = SCIPconsIsLocal(dualproof); 1097 int pos = 0; 1098 1099 /* sort dual rays */ 1100 SCIPsortPtrRealRealBoolBool((void**)conflictstore->dualsolconfs, conflictstore->dualprimalbnds, 1101 conflictstore->scalefactors, conflictstore->updateside, conflictstore->dsolrelaxonly, 1102 compareConss, conflictstore->ndualsolconfs); 1103 assert(SCIPsetIsGE(set, SCIPconsGetAge(conflictstore->dualsolconfs[0]), 1104 SCIPconsGetAge(conflictstore->dualsolconfs[conflictstore->ndualsolconfs-1]))); 1105 1106 while( pos < conflictstore->ndualsolconfs-1 && local != SCIPconsIsLocal(conflictstore->dualsolconfs[pos]) ) 1107 pos++; 1108 1109 /* we don't want to keep the dual proof */ 1110 if( pos >= conflictstore->ndualsolconfs ) 1111 { 1112 SCIP_CALL( SCIPconsDelete(dualproof, blkmem, set, stat, transprob, reopt) ); 1113 return SCIP_OKAY; 1114 } 1115 1116 SCIP_CALL( delPosDualsol(conflictstore, set, stat, transprob, blkmem, reopt, pos, TRUE) ); 1117 } 1118 } 1119 1120 /* add the new constraint based on a dual solution at the last position */ 1121 SCIPconsCapture(dualproof); 1122 conflictstore->dualsolconfs[conflictstore->ndualsolconfs] = dualproof; 1123 conflictstore->dualprimalbnds[conflictstore->ndualsolconfs] = SCIPgetCutoffbound(set->scip) - (SCIPprobIsObjIntegral(transprob) ? SCIPsetCutoffbounddelta(set) : 0.0); 1124 conflictstore->scalefactors[conflictstore->ndualsolconfs] = scale; 1125 conflictstore->updateside[conflictstore->ndualsolconfs] = updateside; 1126 conflictstore->dsolrelaxonly[conflictstore->ndualsolconfs] = hasrelaxvar; 1127 ++conflictstore->ndualsolconfs; 1128 1129 /* add conflict locks */ 1130 SCIP_CALL( SCIPconsAddLocks(dualproof, set, SCIP_LOCKTYPE_CONFLICT, +1, 0) ); 1131 1132 /* increase the number of non-zeros */ 1133 SCIP_CALL( SCIPconsGetNVars(dualproof, set, &nvars, &success) ); 1134 assert(success); 1135 conflictstore->nnzdualsols += nvars; 1136 1137 return SCIP_OKAY; 1138 } 1139 1140 /** adds a conflict to the conflict store 1141 * 1142 * @note this method captures the constraint 1143 */ 1144 SCIP_RETCODE SCIPconflictstoreAddConflict( 1145 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 1146 BMS_BLKMEM* blkmem, /**< block memory */ 1147 SCIP_SET* set, /**< global SCIP settings */ 1148 SCIP_STAT* stat, /**< dynamic SCIP statistics */ 1149 SCIP_TREE* tree, /**< branch and bound tree (or NULL for an original constraint) */ 1150 SCIP_PROB* transprob, /**< transformed problem (or NULL for an original constraint) */ 1151 SCIP_REOPT* reopt, /**< reoptimization data */ 1152 SCIP_CONS* cons, /**< constraint representing the conflict */ 1153 SCIP_CONFTYPE conftype, /**< type of the conflict */ 1154 SCIP_Bool cutoffinvolved, /**< is a cutoff bound involved in this conflict */ 1155 SCIP_Real primalbound /**< primal bound the conflict depend on (or -SCIPinfinity) */ 1156 ) 1157 { 1158 SCIP_Longint curnodenum; 1159 int nconflicts; 1160 1161 assert(conflictstore != NULL); 1162 assert(blkmem != NULL); 1163 assert(set != NULL); 1164 assert(stat != NULL); 1165 assert(tree != NULL || SCIPconsIsOriginal(cons)); 1166 assert(transprob != NULL || SCIPconsIsOriginal(cons)); 1167 assert(cons != NULL); 1168 assert(conftype != SCIP_CONFTYPE_BNDEXCEEDING || cutoffinvolved); 1169 assert(!cutoffinvolved || !SCIPsetIsInfinity(set, REALABS(primalbound))); 1170 1171 /* mark the constraint to be a conflict */ 1172 SCIPconsMarkConflict(cons); 1173 1174 /* add the constraint to a special store */ 1175 if( SCIPconsIsOriginal(cons) ) 1176 { 1177 assert(SCIPsetGetStage(set) == SCIP_STAGE_PROBLEM); 1178 SCIP_CALL( conflictstoreAddOrigConflict(conflictstore, set, blkmem, cons) ); 1179 return SCIP_OKAY; 1180 } 1181 1182 nconflicts = conflictstore->nconflicts; 1183 1184 /* initialize the storage */ 1185 if( conflictstore->maxstoresize == -1 ) 1186 { 1187 SCIP_CALL( initConflictstore(conflictstore, set, transprob) ); 1188 } 1189 assert(conflictstore->initstoresize >= 0); 1190 assert(conflictstore->initstoresize <= conflictstore->maxstoresize); 1191 1192 /* return if conflict pool is disabled */ 1193 if( conflictstore->maxstoresize <= 0 ) 1194 return SCIP_OKAY; 1195 1196 SCIP_CALL( conflictstoreEnsureMem(conflictstore, set, blkmem, nconflicts+1) ); 1197 1198 /* return if the store has size zero */ 1199 if( conflictstore->conflictsize == 0 ) 1200 { 1201 assert(conflictstore->maxstoresize == 0); 1202 return SCIP_OKAY; 1203 } 1204 1205 assert(tree != NULL); 1206 curnodenum = (SCIPtreeGetFocusNode(tree) == NULL ? -1 : SCIPnodeGetNumber(SCIPtreeGetFocusNode(tree))); 1207 1208 /* clean up the storage if we are at a new node or the storage is full */ 1209 if( conflictstore->lastnodenum != curnodenum || conflictstore->nconflicts == conflictstore->conflictsize ) 1210 { 1211 SCIP_CALL( conflictstoreCleanUpStorage(conflictstore, set, stat, transprob, blkmem, reopt) ); 1212 } 1213 1214 /* update the last seen node */ 1215 conflictstore->lastnodenum = curnodenum; 1216 1217 SCIPconsCapture(cons); 1218 conflictstore->conflicts[conflictstore->nconflicts] = cons; 1219 conflictstore->confprimalbnds[conflictstore->nconflicts] = primalbound; 1220 conflictstore->ncbconflicts += (SCIPsetIsInfinity(set, REALABS(primalbound)) ? 0 : 1); 1221 1222 ++conflictstore->nconflicts; 1223 ++conflictstore->nconflictsfound; 1224 1225 /* add conflict locks */ 1226 SCIP_CALL( SCIPconsAddLocks(cons, set, SCIP_LOCKTYPE_CONFLICT, +1, 0) ); 1227 1228 #ifdef SCIP_PRINT_DETAILS 1229 SCIPsetDebugMsg(set, "add conflict <%s> to conflict store at position %d\n", SCIPconsGetName(cons), conflictstore->nconflicts-1); 1230 SCIPsetDebugMsg(set, " -> conflict type: %d, cutoff involved = %u\n", conftype, cutoffinvolved); 1231 if( cutoffinvolved ) 1232 SCIPsetDebugMsg(set, " -> current primal bound: %g\n", primalbound); 1233 #endif 1234 1235 return SCIP_OKAY; 1236 } 1237 1238 /** deletes all conflicts depending on a cutoff bound larger than the given bound */ 1239 SCIP_RETCODE SCIPconflictstoreCleanNewIncumbent( 1240 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 1241 SCIP_SET* set, /**< global SCIP settings */ 1242 SCIP_STAT* stat, /**< dynamic SCIP statistics */ 1243 BMS_BLKMEM* blkmem, /**< block memory */ 1244 SCIP_PROB* transprob, /**< transformed problem*/ 1245 SCIP_REOPT* reopt, /**< reoptimization data */ 1246 SCIP_Real cutoffbound /**< current cutoff bound */ 1247 ) 1248 { 1249 SCIP_Real improvement; 1250 int ndelconfs; 1251 int nchgsides; 1252 int i; 1253 1254 assert(conflictstore != NULL); 1255 assert(set != NULL); 1256 assert(stat != NULL); 1257 assert(blkmem != NULL); 1258 assert(transprob != NULL); 1259 1260 /* return if we do not want to use the storage */ 1261 if( set->conf_maxstoresize == 0 ) 1262 return SCIP_OKAY; 1263 1264 /* return if we do not want to remove conflicts related to an older cutoff bound */ 1265 if( !set->conf_cleanbnddepend ) 1266 return SCIP_OKAY; 1267 1268 /* there is nothing to clean */ 1269 if( conflictstore->ndualsolconfs == 0 && conflictstore->nconflicts == 0 ) 1270 return SCIP_OKAY; 1271 1272 /* we can stop whenever we have found a new incumbent but the cutoff bound has not changed */ 1273 if( conflictstore->lastcutoffbound != SCIP_INVALID && SCIPsetIsGE(set, cutoffbound, conflictstore->lastcutoffbound) ) /*lint !e777*/ 1274 return SCIP_OKAY; 1275 1276 conflictstore->lastcutoffbound = cutoffbound; 1277 1278 /* calculate scalar to determine whether the old primal bound is worse enough to remove the conflict */ 1279 if( SCIPsetIsPositive(set, cutoffbound) ) 1280 improvement = (1 - set->conf_minimprove); 1281 else 1282 improvement = (1 + set->conf_minimprove); 1283 1284 /* remove all conflicts depending on a primalbound*improvement > cutoffbound 1285 * 1286 * note: we cannot remove conflicts that are marked as deleted because at this point in time we would destroy 1287 * the internal data structure 1288 */ 1289 ndelconfs = 0; 1290 for( i = 0; i < conflictstore->nconflicts; ) 1291 { 1292 assert(conflictstore->conflicts[i] != NULL); 1293 1294 /* check if the conflict depends on the cutoff bound */ 1295 if( SCIPsetIsGT(set, improvement * conflictstore->confprimalbnds[i], cutoffbound) ) 1296 { 1297 /* remove conflict at current position 1298 * 1299 * don't increase i because delPosConflict will swap the last pointer to the i-th position 1300 */ 1301 SCIP_CALL( delPosConflict(conflictstore, set, stat, transprob, blkmem, reopt, i, TRUE) ); 1302 ++ndelconfs; 1303 } 1304 else 1305 /* increase i */ 1306 ++i; 1307 } 1308 assert(conflictstore->ncbconflicts >= 0); 1309 assert(conflictstore->nconflicts >= 0); 1310 1311 SCIPsetDebugMsg(set, "-> removed %d/%d conflicts, %d depending on cutoff bound\n", ndelconfs, 1312 conflictstore->nconflicts+ndelconfs, ndelconfs); 1313 1314 ndelconfs = 0; 1315 nchgsides = 0; 1316 /* update all proof constraints based on a dual solution */ 1317 for( i = 0; i < conflictstore->ndualsolconfs; ) 1318 { 1319 SCIP_CONSHDLR* conshdlr; 1320 SCIP_CONS* dualproof; 1321 1322 dualproof = conflictstore->dualsolconfs[i]; 1323 assert(dualproof != NULL); 1324 1325 if( SCIPconsIsDeleted(dualproof) ) 1326 { 1327 ++i; 1328 continue; 1329 } 1330 if( !conflictstore->updateside[i] || SCIPsetIsLE(set, improvement * conflictstore->dualprimalbnds[i], cutoffbound) ) 1331 { 1332 ++i; 1333 continue; 1334 } 1335 conshdlr = SCIPconsGetHdlr(dualproof); 1336 assert(conshdlr != NULL); 1337 1338 if( strcmp(SCIPconshdlrGetName(conshdlr), "linear") == 0 ) 1339 { 1340 SCIP_Real rhs; 1341 SCIP_Real newside; 1342 1343 assert(SCIPsetIsGT(set, conflictstore->dualprimalbnds[i], cutoffbound)); 1344 1345 rhs = SCIPgetRhsLinear(set->scip, dualproof); 1346 1347 if( !SCIPsetIsInfinity(set, rhs) ) 1348 { 1349 assert(SCIPsetIsInfinity(set, -SCIPgetLhsLinear(set->scip, dualproof))); 1350 assert(SCIPsetIsPositive(set, conflictstore->scalefactors[i])); 1351 1352 /* get unscaled rhs */ 1353 newside = rhs * conflictstore->scalefactors[i]; 1354 newside -= conflictstore->dualprimalbnds[i]; 1355 newside += cutoffbound - (SCIPprobIsObjIntegral(transprob) ? SCIPsetCutoffbounddelta(set) : 0.0); 1356 1357 /* scale rhs */ 1358 newside /= conflictstore->scalefactors[i]; 1359 1360 SCIP_CALL( SCIPchgRhsLinear(set->scip, dualproof, newside) ); 1361 } 1362 else 1363 { 1364 SCIP_Real lhs; 1365 1366 lhs = SCIPgetLhsLinear(set->scip, dualproof); 1367 assert(!SCIPsetIsInfinity(set, -lhs)); 1368 assert(SCIPsetIsNegative(set, conflictstore->scalefactors[i])); 1369 1370 /* get unscaled lhs */ 1371 newside = lhs * conflictstore->scalefactors[i]; 1372 newside += conflictstore->dualprimalbnds[i]; 1373 newside -= (cutoffbound - (SCIPprobIsObjIntegral(transprob) ? SCIPsetCutoffbounddelta(set) : 0.0)); 1374 1375 /* scale lhs */ 1376 newside /= conflictstore->scalefactors[i]; 1377 1378 SCIP_CALL( SCIPchgLhsLinear(set->scip, dualproof, newside) ); 1379 } 1380 1381 ++nchgsides; 1382 1383 conflictstore->dualprimalbnds[i] = cutoffbound - (SCIPprobIsObjIntegral(transprob) ? SCIPsetCutoffbounddelta(set) : 0.0); 1384 1385 ++i; 1386 } 1387 else if( SCIPsetIsGT(set, improvement * conflictstore->dualprimalbnds[i], cutoffbound) ) 1388 { 1389 /* remove conflict at current position 1390 * 1391 * don't increase i because delPosDualsol will swap the last pointer to the i-th position 1392 */ 1393 SCIP_CALL( delPosDualsol(conflictstore, set, stat, transprob, blkmem, reopt, i, TRUE) ); 1394 ++ndelconfs; 1395 } 1396 else 1397 /* increase i */ 1398 ++i; 1399 } 1400 1401 SCIPsetDebugMsg(set, "-> changed %d sides of dual solution constraints\n", nchgsides); 1402 SCIPsetDebugMsg(set, "-> deleted %d dual solution constraints\n", ndelconfs); 1403 1404 return SCIP_OKAY; 1405 } 1406 1407 /** returns the maximal size of the conflict pool */ 1408 int SCIPconflictstoreGetMaxPoolSize( 1409 SCIP_CONFLICTSTORE* conflictstore /**< conflict store */ 1410 ) 1411 { 1412 assert(conflictstore != NULL); 1413 1414 return MIN(conflictstore->storesize, conflictstore->maxstoresize); 1415 } 1416 1417 /** returns the initial size of the conflict pool */ 1418 int SCIPconflictstoreGetInitPoolSize( 1419 SCIP_CONFLICTSTORE* conflictstore /**< conflict store */ 1420 ) 1421 { 1422 assert(conflictstore != NULL); 1423 1424 return conflictstore->initstoresize; 1425 } 1426 1427 /** returns the number of stored conflicts on the conflict pool 1428 * 1429 * @note the number of active conflicts can be less 1430 */ 1431 int SCIPconflictstoreGetNConflictsInStore( 1432 SCIP_CONFLICTSTORE* conflictstore /**< conflict store */ 1433 ) 1434 { 1435 assert(conflictstore != NULL); 1436 1437 return conflictstore->nconflicts; 1438 } 1439 1440 /** returns all active conflicts stored in the conflict store */ 1441 SCIP_RETCODE SCIPconflictstoreGetConflicts( 1442 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 1443 SCIP_CONS** conflicts, /**< array to store conflicts */ 1444 int conflictsize, /**< size of the conflict array */ 1445 int* nconflicts /**< pointer to store the number of conflicts */ 1446 ) 1447 { 1448 int i; 1449 1450 assert(conflictstore != NULL); 1451 1452 /* return if the allocated memory is obviously to small */ 1453 if( conflictstore->nconflicts > conflictsize ) 1454 { 1455 (*nconflicts) = conflictstore->nconflicts; 1456 return SCIP_OKAY; 1457 } 1458 1459 (*nconflicts) = 0; 1460 for( i = 0; i < conflictstore->nconflicts; i++ ) 1461 { 1462 SCIP_CONS* conflict; 1463 1464 conflict = conflictstore->conflicts[i]; 1465 assert(conflict != NULL); 1466 1467 /* skip deactivated and deleted constraints */ 1468 if( !SCIPconsIsActive(conflict) || SCIPconsIsDeleted(conflict) ) 1469 continue; 1470 1471 /* count exact number conflicts */ 1472 if( *nconflicts > conflictsize ) 1473 ++(*nconflicts); 1474 else 1475 { 1476 conflicts[*nconflicts] = conflict; 1477 ++(*nconflicts); 1478 } 1479 } 1480 1481 return SCIP_OKAY; 1482 } 1483 1484 /** transformes all original conflicts into transformed conflicts */ 1485 SCIP_RETCODE SCIPconflictstoreTransform( 1486 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 1487 BMS_BLKMEM* blkmem, /**< block memory */ 1488 SCIP_SET* set, /**< global SCIP settings */ 1489 SCIP_STAT* stat, /**< dynamic SCIP statistics */ 1490 SCIP_TREE* tree, /**< branch and bound tree */ 1491 SCIP_PROB* transprob, /**< transformed problem */ 1492 SCIP_REOPT* reopt /**< reoptimization data */ 1493 ) 1494 { 1495 int ntransconss; 1496 int i; 1497 1498 assert(conflictstore != NULL); 1499 assert(set != NULL); 1500 assert(SCIPsetGetStage(set) == SCIP_STAGE_TRANSFORMING); 1501 1502 /* return if no original constraints are stored */ 1503 if( conflictstore->norigconfs == 0 ) 1504 return SCIP_OKAY; 1505 1506 ntransconss = 0; 1507 1508 for( i = 0; i < conflictstore->norigconfs; i++ ) 1509 { 1510 SCIP_CONS* transcons; 1511 1512 assert(conflictstore->origconfs[i] != NULL); 1513 assert(SCIPconsIsOriginal(conflictstore->origconfs[i])); 1514 1515 transcons = SCIPconsGetTransformed(conflictstore->origconfs[i]); 1516 1517 if( transcons != NULL ) 1518 { 1519 SCIP_CALL( SCIPconflictstoreAddConflict(conflictstore, blkmem, set, stat, tree, transprob, reopt, transcons, \ 1520 SCIP_CONFTYPE_UNKNOWN, FALSE, -SCIPsetInfinity(set)) ); 1521 1522 ++ntransconss; 1523 } 1524 1525 SCIP_CALL( SCIPconsRelease(&conflictstore->origconfs[i], blkmem, set) ); 1526 } 1527 1528 SCIPsetDebugMsg(set, "-> transform %d/%d conflicts into transformed space\n", ntransconss, conflictstore->norigconfs); 1529 1530 conflictstore->norigconfs = 0; 1531 1532 return SCIP_OKAY; 1533 } 1534 1535 /** returns the average number of non-zeros over all stored dual ray constraints */ 1536 SCIP_Real SCIPconflictstoreGetAvgNnzDualInfProofs( 1537 SCIP_CONFLICTSTORE* conflictstore /**< conflict store */ 1538 ) 1539 { 1540 assert(conflictstore != NULL); 1541 1542 if( conflictstore->ndualrayconfs == 0 ) 1543 return 0.0; 1544 else 1545 return (SCIP_Real) conflictstore->nnzdualrays / ((SCIP_Real) conflictstore->ndualrayconfs); 1546 } 1547 1548 /** returns the number of all stored dual ray constraints */ 1549 int SCIPconflictstoreGetNDualInfProofs( 1550 SCIP_CONFLICTSTORE* conflictstore /**< conflict store */ 1551 ) 1552 { 1553 assert(conflictstore != NULL); 1554 1555 return conflictstore->ndualrayconfs; 1556 } 1557 1558 /** returns the average number of non-zeros over all stored boundexceeding proofs */ 1559 SCIP_Real SCIPconflictstoreGetAvgNnzDualBndProofs( 1560 SCIP_CONFLICTSTORE* conflictstore /**< conflict store */ 1561 ) 1562 { 1563 assert(conflictstore != NULL); 1564 assert(conflictstore->ndualsolconfs >= 0); 1565 1566 if( conflictstore->ndualsolconfs == 0 ) 1567 return 0.0; 1568 else 1569 return (SCIP_Real) conflictstore->nnzdualsols / ((SCIP_Real) conflictstore->ndualsolconfs); 1570 } 1571 1572 /** returns the number of all stored boundexceeding proofs */ 1573 int SCIPconflictstoreGetNDualBndProofs( 1574 SCIP_CONFLICTSTORE* conflictstore /**< conflict store */ 1575 ) 1576 { 1577 assert(conflictstore != NULL); 1578 1579 return conflictstore->ndualsolconfs; 1580 } 1581 1582