conflictstore.c
Go to the documentation of this file.
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
43 #define CONFLICTSTORE_MAXSIZE 60000 /* maximal size of a dynamic conflict store (multiplied by 3) */
69 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */
89 /** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
151 if( strcmp(SCIPconshdlrGetName(conshdlr1), "linear") == strcmp(SCIPconshdlrGetName(conshdlr2), "linear") )
197 conflictstore->maxstoresize = (int)(MIN(3.0 * conflictstore->initstoresize, CONFLICTSTORE_MAXSIZE));
253 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictstore->conflicts, conflictstore->conflictsize, \
255 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictstore->confprimalbnds, conflictstore->conflictsize, \
268 assert(num <= conflictstore->conflictsize || conflictstore->conflictsize == conflictstore->maxstoresize);
275 * we want to have at least set->conf_maxconss free slots in the conflict array, because this is the maximal number
276 * of conflicts generated at a node. we increase the size by the minimum of set->conf_maxconss and 1% of the current
323 conflictstore->ncbconflicts -= (SCIPsetIsInfinity(set, REALABS(conflictstore->confprimalbnds[pos])) ? 0 : 1);
326 SCIPsetDebugMsg(set, "-> remove conflict <%s> at pos=%d with age=%g\n", SCIPconsGetName(conflict), pos, SCIPconsGetAge(conflict));
336 SCIP_CALL( SCIPconsDelete(conflictstore->conflicts[pos], blkmem, set, stat, transprob, reopt) );
388 SCIPsetDebugMsg(set, "-> remove dual proof (ray) at pos=%d age=%g nvars=%d\n", pos, SCIPconsGetAge(dualproof), nvars);
449 SCIPsetDebugMsg(set, "-> remove dual proof (sol) at pos=%d age=%g nvars=%d\n", pos, SCIPconsGetAge(dualproof), nvars);
508 if( SCIPconsIsDeleted(conflictstore->conflicts[i]) || SCIPconsIsChecked(conflictstore->conflicts[i]) )
516 SCIPsetDebugMsg(set, "> removed %d/%d as deleted marked conflicts.\n", *ndelconfs, conflictstore->nconflicts + (*ndelconfs));
544 if( SCIPconsIsDeleted(conflictstore->dualrayconfs[i]) || SCIPconsIsChecked(conflictstore->dualrayconfs[i]) )
582 if( SCIPconsIsDeleted(conflictstore->dualsolconfs[i]) || SCIPconsIsChecked(conflictstore->dualsolconfs[i]) )
624 SCIP_CALL( cleanDeletedAndCheckedConflicts(conflictstore, set, stat, blkmem, reopt, &ndelconfs) );
638 SCIPsortPtrReal((void**)conflictstore->conflicts, conflictstore->confprimalbnds, compareConss, conflictstore->nconflicts);
673 SCIP_CALL( delPosConflict(conflictstore, set, stat, transprob, blkmem, reopt, oldest_i, TRUE) );
689 conflictstore->ncleanups, ndelconfs, conflictstore->nconflicts+ndelconfs, conflictstore->ncbconflicts);
696 * @note the constraint will be only transfered to the storage of the transformed problem after calling
712 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->origconfs, CONFLICTSTORE_MINSIZE) );
718 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictstore->origconfs, conflictstore->origconflictsize, newsize) );
769 SCIP_CALL( SCIPeventhdlrCreate(&(*conflictstore)->eventhdlr, set, EVENTHDLR_NAME, EVENTHDLR_DESC, NULL, NULL,
770 NULL, NULL, eventInitsolConflictstore, eventExitsolConflictstore, NULL, eventExecConflictstore, NULL) );
793 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->origconfs, (*conflictstore)->origconflictsize);
794 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->conflicts, (*conflictstore)->conflictsize);
795 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->confprimalbnds, (*conflictstore)->conflictsize);
796 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->dualrayconfs, CONFLICTSTORE_DUALRAYSIZE);
797 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->dualsolconfs, CONFLICTSTORE_DUALSOLSIZE);
798 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->dualprimalbnds, CONFLICTSTORE_DUALSOLSIZE);
799 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->scalefactors, CONFLICTSTORE_DUALSOLSIZE);
820 conflictstore->norigconfs, conflictstore->nconflicts, conflictstore->ndualrayconfs + conflictstore->ndualsolconfs);
885 conflictstore->norigconfs, conflictstore->nconflicts, conflictstore->ndualrayconfs + conflictstore->ndualsolconfs);
893 * the latter case might happen during processing parallel constraints, e.g., cons_knapsack.c:detectRedundantConstraints().
894 * in that case, the conflict constraint should stay, e.g., it has the stricter capacity, and replaces a model
895 * constraint. hence, the conflict is now a constraint that is needed to stay correct. therefore, the conflictpool
898 SCIP_CALL( cleanDeletedAndCheckedConflicts(conflictstore, set, stat, blkmem, reopt, &ndelconfs) );
900 /* remove all dual infeasibility proofs that are marked as deleted or where the check flag has changed to TRUE. */
901 SCIP_CALL( cleanDeletedAndCheckedDualrayCons(conflictstore, set, stat, blkmem, reopt, &ndeldualray) );
903 /* remove all dual bound exceeding proofs that are marked as deleted or where the check flag has changed to TRUE. */
904 SCIP_CALL( cleanDeletedAndCheckedDualsolCons(conflictstore, set, stat, blkmem, reopt, &ndeldualsol) );
946 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->dualrayconfs, CONFLICTSTORE_DUALRAYSIZE) );
959 SCIP_CALL( cleanDeletedAndCheckedDualrayCons(conflictstore, set, stat, blkmem, reopt, &ndeleted) );
961 /* if we could not remove a dual ray that is already marked as deleted we need to remove the oldest active one */
1017 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->dualsolconfs, CONFLICTSTORE_DUALSOLSIZE) );
1018 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->dualprimalbnds, CONFLICTSTORE_DUALSOLSIZE) );
1019 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->scalefactors, CONFLICTSTORE_DUALSOLSIZE) );
1020 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->updateside, CONFLICTSTORE_DUALSOLSIZE) );
1033 SCIP_CALL( cleanDeletedAndCheckedDualsolCons(conflictstore, set, stat, blkmem, reopt, &ndeleted) );
1035 /* if we could not remove a dual proof that is already marked as deleted we need to remove the oldest active one */
1040 conflictstore->scalefactors, (int*)conflictstore->updateside, compareConss, conflictstore->ndualsolconfs);
1051 conflictstore->dualprimalbnds[conflictstore->ndualsolconfs] = SCIPgetCutoffbound(set->scip) - SCIPsetSumepsilon(set);
1133 curnodenum = (SCIPtreeGetFocusNode(tree) == NULL ? -1 : SCIPnodeGetNumber(SCIPtreeGetFocusNode(tree)));
1136 if( conflictstore->lastnodenum != curnodenum || conflictstore->nconflicts == conflictstore->conflictsize )
1156 SCIPsetDebugMsg(set, "add conflict <%s> to conflict store at position %d\n", SCIPconsGetName(cons), conflictstore->nconflicts-1);
1157 SCIPsetDebugMsg(set, " -> conflict type: %d, cutoff involved = %u\n", conftype, cutoffinvolved);
1200 if( conflictstore->lastcutoffbound != SCIP_INVALID && SCIPsetIsGE(set, cutoffbound, conflictstore->lastcutoffbound) ) /*lint !e777*/
1205 /* calculate scalar to determine whether the old primal bound is worse enough to remove the conflict */
1213 * note: we cannot remove conflicts that are marked as deleted because at this point in time we would destroy
1257 if( !conflictstore->updateside[i] || SCIPsetIsLE(set, improvement * conflictstore->dualprimalbnds[i], cutoffbound) )
1444 SCIP_CALL( SCIPconflictstoreAddConflict(conflictstore, blkmem, set, stat, tree, transprob, reopt, transcons, \
1453 SCIPsetDebugMsg(set, "-> transform %d/%d conflicts into transformed space\n", ntransconss, conflictstore->norigconfs);
Definition: type_conflict.h:52
SCIP_RETCODE SCIPconsDelete(SCIP_CONS *cons, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_REOPT *reopt)
Definition: cons.c:6343
SCIP_RETCODE SCIPsetIncludeEventhdlr(SCIP_SET *set, SCIP_EVENTHDLR *eventhdlr)
Definition: set.c:4566
#define BMSfreeBlockMemoryArrayNull(mem, ptr, num)
Definition: memory.h:457
internal methods for managing events
SCIP_Bool SCIPsetIsLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6011
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18119
internal methods for branch and bound tree
static SCIP_RETCODE delPosDualsol(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt, int pos, SCIP_Bool deleteconflict)
Definition: conflictstore.c:420
static SCIP_DECL_EVENTEXITSOL(eventExitsolConflictstore)
Definition: conflictstore.c:91
int SCIPconflictstoreGetNConflictsInStore(SCIP_CONFLICTSTORE *conflictstore)
Definition: conflictstore.c:1356
SCIP_RETCODE SCIPconflictstoreTransform(SCIP_CONFLICTSTORE *conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_PROB *transprob, SCIP_REOPT *reopt)
Definition: conflictstore.c:1410
SCIP_RETCODE SCIPconflictstoreCleanNewIncumbent(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_PROB *transprob, SCIP_REOPT *reopt, SCIP_Real cutoffbound)
Definition: conflictstore.c:1166
SCIP_EVENTHDLR * SCIPsetFindEventhdlr(SCIP_SET *set, const char *name)
Definition: set.c:4589
Definition: type_set.h:37
static SCIP_RETCODE cleanDeletedAndCheckedDualsolCons(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt, int *ndelproofs)
Definition: conflictstore.c:561
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:240
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:314
static SCIP_RETCODE conflictstoreEnsureMem(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, BMS_BLKMEM *blkmem, int num)
Definition: conflictstore.c:219
static SCIP_RETCODE cleanDeletedAndCheckedConflicts(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt, int *ndelconfs)
Definition: conflictstore.c:487
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
Definition: cons_linear.c:18165
Definition: struct_prob.h:39
SCIP_EXPORT void SCIPsortPtrReal(void **ptrarray, SCIP_Real *realarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip_cons.c:2557
SCIP_RETCODE SCIPconsAddLocks(SCIP_CONS *cons, SCIP_SET *set, SCIP_LOCKTYPE locktype, int nlockspos, int nlocksneg)
Definition: cons.c:7242
static SCIP_RETCODE cleanDeletedAndCheckedDualrayCons(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt, int *ndelproofs)
Definition: conflictstore.c:523
SCIP_RETCODE SCIPconflictstoreClean(SCIP_CONFLICTSTORE *conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_REOPT *reopt)
Definition: conflictstore.c:870
SCIP_RETCODE SCIPconflictstoreCreate(SCIP_CONFLICTSTORE **conflictstore, SCIP_SET *set)
Definition: conflictstore.c:731
int SCIPconflictstoreGetNDualInfProofs(SCIP_CONFLICTSTORE *conflictstore)
Definition: conflictstore.c:1474
SCIP_Bool SCIPsetIsGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6047
Definition: struct_set.h:61
static SCIP_RETCODE delPosDualray(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt, int pos, SCIP_Bool deleteconflict)
Definition: conflictstore.c:360
SCIP_RETCODE SCIPconflictstoreClear(SCIP_CONFLICTSTORE *conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_REOPT *reopt)
Definition: conflictstore.c:807
internal methods for storing and manipulating the main problem
Definition: struct_cons.h:37
Definition: struct_cons.h:117
static SCIP_RETCODE conflictstoreAddOrigConflict(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, BMS_BLKMEM *blkmem, SCIP_CONS *cons)
Definition: conflictstore.c:700
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:276
SCIP_RETCODE SCIPconflictstoreFree(SCIP_CONFLICTSTORE **conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_REOPT *reopt)
Definition: conflictstore.c:779
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18142
SCIP_EXPORT void SCIPsortPtrRealRealInt(void **ptrarray, SCIP_Real *realarray1, SCIP_Real *realarray2, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
internal miscellaneous methods
Definition: type_retcode.h:33
internal methods for global SCIP settings
internal methods for storing conflicts
int SCIPconflictstoreGetInitPoolSize(SCIP_CONFLICTSTORE *conflictstore)
Definition: conflictstore.c:1343
static SCIP_RETCODE initConflictstore(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_PROB *transprob)
Definition: conflictstore.c:163
static SCIP_RETCODE delPosConflict(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt, int pos, SCIP_Bool deleteconflict)
Definition: conflictstore.c:301
SCIP_EXPORT void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
data structures and methods for collecting reoptimization information
SCIP_RETCODE SCIPconsGetNVars(SCIP_CONS *cons, SCIP_SET *set, int *nvars, SCIP_Bool *success)
Definition: cons.c:6311
Definition: struct_conflictstore.h:36
static SCIP_RETCODE conflictstoreCleanUpStorage(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt)
Definition: conflictstore.c:599
SCIP_RETCODE SCIPconsRelease(SCIP_CONS **cons, BMS_BLKMEM *blkmem, SCIP_SET *set)
Definition: cons.c:6196
SCIP_RETCODE SCIPsetGetIntParam(SCIP_SET *set, const char *name, int *value)
Definition: set.c:3032
SCIP_Real SCIPconflictstoreGetAvgNnzDualBndProofs(SCIP_CONFLICTSTORE *conflictstore)
Definition: conflictstore.c:1484
Definition: type_set.h:40
SCIP_RETCODE SCIPconflictstoreAddDualraycons(SCIP_CONFLICTSTORE *conflictstore, SCIP_CONS *dualproof, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_REOPT *reopt)
Definition: conflictstore.c:924
Definition: struct_reopt.h:130
Definition: type_var.h:85
Constraint handler for linear constraints in their most general form, .
int SCIPconflictstoreGetMaxPoolSize(SCIP_CONFLICTSTORE *conflictstore)
Definition: conflictstore.c:1333
Definition: type_set.h:36
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:310
SCIP_Bool SCIPsetIsGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6029
Definition: type_conflict.h:49
SCIP_RETCODE SCIPconflictstoreAddConflict(SCIP_CONFLICTSTORE *conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_PROB *transprob, SCIP_REOPT *reopt, SCIP_CONS *cons, SCIP_CONFTYPE conftype, SCIP_Bool cutoffinvolved, SCIP_Real primalbound)
Definition: conflictstore.c:1071
SCIP_RETCODE SCIPconflictstoreAddDualsolcons(SCIP_CONFLICTSTORE *conflictstore, SCIP_CONS *dualproof, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_REOPT *reopt, SCIP_Real scale, SCIP_Bool updateside)
Definition: conflictstore.c:993
internal methods for constraints and constraint handlers
int SCIPconflictstoreGetNDualBndProofs(SCIP_CONFLICTSTORE *conflictstore)
Definition: conflictstore.c:1498
SCIP_RETCODE SCIPclearConflictStore(SCIP *scip, SCIP_EVENT *event)
Definition: scip_prob.c:3282
Definition: type_set.h:44
static SCIP_DECL_EVENTINITSOL(eventInitsolConflictstore)
Definition: conflictstore.c:71
SCIP_Real SCIPconflictstoreGetAvgNnzDualInfProofs(SCIP_CONFLICTSTORE *conflictstore)
Definition: conflictstore.c:1461
Definition: struct_stat.h:50
Definition: struct_tree.h:175
common defines and data types used in all packages of SCIP
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
Definition: cons_linear.c:18186
Definition: objbenders.h:33
SCIP_RETCODE SCIPeventhdlrCreate(SCIP_EVENTHDLR **eventhdlr, SCIP_SET *set, const char *name, const char *desc, SCIP_DECL_EVENTCOPY((*eventcopy)), SCIP_DECL_EVENTFREE((*eventfree)), SCIP_DECL_EVENTINIT((*eventinit)), SCIP_DECL_EVENTEXIT((*eventexit)), SCIP_DECL_EVENTINITSOL((*eventinitsol)), SCIP_DECL_EVENTEXITSOL((*eventexitsol)), SCIP_DECL_EVENTDELETE((*eventdelete)), SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: event.c:113
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition: memory.h:447
SCIP_RETCODE SCIPconflictstoreGetConflicts(SCIP_CONFLICTSTORE *conflictstore, SCIP_CONS **conflicts, int conflictsize, int *nconflicts)
Definition: conflictstore.c:1366
SCIP callable library.
static void adjustStorageSize(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set)
Definition: conflictstore.c:280