conflictstore.c
Go to the documentation of this file.
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
44 #define CONFLICTSTORE_MAXSIZE 60000 /* maximal size of a dynamic conflict store (multiplied by 3) */
70 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */
90 /** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
152 if( strcmp(SCIPconshdlrGetName(conshdlr1), "linear") == strcmp(SCIPconshdlrGetName(conshdlr2), "linear") )
198 conflictstore->maxstoresize = (int)(MIN(3.0 * conflictstore->initstoresize, CONFLICTSTORE_MAXSIZE));
254 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictstore->conflicts, conflictstore->conflictsize, \
256 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictstore->confprimalbnds, conflictstore->conflictsize, \
269 assert(num <= conflictstore->conflictsize || conflictstore->conflictsize == conflictstore->maxstoresize);
276 * we want to have at least set->conf_maxconss free slots in the conflict array, because this is the maximal number
277 * of conflicts generated at a node. we increase the size by the minimum of set->conf_maxconss and 1% of the current
324 conflictstore->ncbconflicts -= (SCIPsetIsInfinity(set, REALABS(conflictstore->confprimalbnds[pos])) ? 0 : 1);
327 SCIPsetDebugMsg(set, "-> remove conflict <%s> at pos=%d with age=%g\n", SCIPconsGetName(conflict), pos, SCIPconsGetAge(conflict));
337 SCIP_CALL( SCIPconsDelete(conflictstore->conflicts[pos], blkmem, set, stat, transprob, reopt) );
389 SCIPsetDebugMsg(set, "-> remove dual proof (ray) at pos=%d age=%g nvars=%d\n", pos, SCIPconsGetAge(dualproof), nvars);
452 SCIPsetDebugMsg(set, "-> remove dual proof (sol) at pos=%d age=%g nvars=%d\n", pos, SCIPconsGetAge(dualproof), nvars);
513 if( SCIPconsIsDeleted(conflictstore->conflicts[i]) || SCIPconsIsChecked(conflictstore->conflicts[i]) )
521 SCIPsetDebugMsg(set, "> removed %d/%d as deleted marked conflicts.\n", *ndelconfs, conflictstore->nconflicts + (*ndelconfs));
549 if( SCIPconsIsDeleted(conflictstore->dualrayconfs[i]) || SCIPconsIsChecked(conflictstore->dualrayconfs[i]) )
587 if( SCIPconsIsDeleted(conflictstore->dualsolconfs[i]) || SCIPconsIsChecked(conflictstore->dualsolconfs[i]) )
629 SCIP_CALL( cleanDeletedAndCheckedConflicts(conflictstore, set, stat, blkmem, reopt, &ndelconfs) );
643 SCIPsortPtrReal((void**)conflictstore->conflicts, conflictstore->confprimalbnds, compareConss, conflictstore->nconflicts);
678 SCIP_CALL( delPosConflict(conflictstore, set, stat, transprob, blkmem, reopt, oldest_i, TRUE) );
694 conflictstore->ncleanups, ndelconfs, conflictstore->nconflicts+ndelconfs, conflictstore->ncbconflicts);
701 * @note the constraint will be only transfered to the storage of the transformed problem after calling
717 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->origconfs, CONFLICTSTORE_MINSIZE) );
723 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictstore->origconfs, conflictstore->origconflictsize, newsize) );
776 SCIP_CALL( SCIPeventhdlrCreate(&(*conflictstore)->eventhdlr, set, EVENTHDLR_NAME, EVENTHDLR_DESC, NULL, NULL,
777 NULL, NULL, eventInitsolConflictstore, eventExitsolConflictstore, NULL, eventExecConflictstore, NULL) );
800 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->origconfs, (*conflictstore)->origconflictsize);
801 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->conflicts, (*conflictstore)->conflictsize);
802 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->confprimalbnds, (*conflictstore)->conflictsize);
803 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->dualrayconfs, CONFLICTSTORE_DUALRAYSIZE);
804 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->drayrelaxonly, CONFLICTSTORE_DUALRAYSIZE);
805 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->dualsolconfs, CONFLICTSTORE_DUALSOLSIZE);
806 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->dualprimalbnds, CONFLICTSTORE_DUALSOLSIZE);
807 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->scalefactors, CONFLICTSTORE_DUALSOLSIZE);
809 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->dsolrelaxonly, CONFLICTSTORE_DUALSOLSIZE);
829 conflictstore->norigconfs, conflictstore->nconflicts, conflictstore->ndualrayconfs + conflictstore->ndualsolconfs);
895 conflictstore->norigconfs, conflictstore->nconflicts, conflictstore->ndualrayconfs + conflictstore->ndualsolconfs);
903 * the latter case might happen during processing parallel constraints, e.g., cons_knapsack.c:detectRedundantConstraints().
904 * in that case, the conflict constraint should stay, e.g., it has the stricter capacity, and replaces a model
905 * constraint. hence, the conflict is now a constraint that is needed to stay correct. therefore, the conflictpool
908 SCIP_CALL( cleanDeletedAndCheckedConflicts(conflictstore, set, stat, blkmem, reopt, &ndelconfs) );
910 /* remove all dual infeasibility proofs that are marked as deleted or where the check flag has changed to TRUE. */
911 SCIP_CALL( cleanDeletedAndCheckedDualrayCons(conflictstore, set, stat, blkmem, reopt, &ndeldualray) );
913 /* remove all dual bound exceeding proofs that are marked as deleted or where the check flag has changed to TRUE. */
914 SCIP_CALL( cleanDeletedAndCheckedDualsolCons(conflictstore, set, stat, blkmem, reopt, &ndeldualsol) );
976 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->dualrayconfs, CONFLICTSTORE_DUALRAYSIZE) );
977 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->drayrelaxonly, CONFLICTSTORE_DUALRAYSIZE) );
990 SCIP_CALL( cleanDeletedAndCheckedDualrayCons(conflictstore, set, stat, blkmem, reopt, &ndeleted) );
992 /* if we could not remove a dual ray that is already marked as deleted we need to remove the oldest active one */
999 SCIPsortPtrBool((void**)conflictstore->dualrayconfs, conflictstore->drayrelaxonly, compareConss,
1004 while( pos < conflictstore->ndualrayconfs-1 && local != SCIPconsIsLocal(conflictstore->dualrayconfs[pos]) )
1065 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->dualsolconfs, CONFLICTSTORE_DUALSOLSIZE) );
1066 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->dualprimalbnds, CONFLICTSTORE_DUALSOLSIZE) );
1067 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->scalefactors, CONFLICTSTORE_DUALSOLSIZE) );
1068 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->updateside, CONFLICTSTORE_DUALSOLSIZE) );
1069 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->dsolrelaxonly, CONFLICTSTORE_DUALSOLSIZE) );
1082 SCIP_CALL( cleanDeletedAndCheckedDualsolCons(conflictstore, set, stat, blkmem, reopt, &ndeleted) );
1084 /* if we could not remove a dual proof that is already marked as deleted we need to remove the oldest active one */
1091 SCIPsortPtrRealRealBoolBool((void**)conflictstore->dualsolconfs, conflictstore->dualprimalbnds,
1097 while( pos < conflictstore->ndualsolconfs-1 && local != SCIPconsIsLocal(conflictstore->dualsolconfs[pos]) )
1114 conflictstore->dualprimalbnds[conflictstore->ndualsolconfs] = SCIPgetCutoffbound(set->scip) - SCIPsetSumepsilon(set);
1197 curnodenum = (SCIPtreeGetFocusNode(tree) == NULL ? -1 : SCIPnodeGetNumber(SCIPtreeGetFocusNode(tree)));
1200 if( conflictstore->lastnodenum != curnodenum || conflictstore->nconflicts == conflictstore->conflictsize )
1220 SCIPsetDebugMsg(set, "add conflict <%s> to conflict store at position %d\n", SCIPconsGetName(cons), conflictstore->nconflicts-1);
1221 SCIPsetDebugMsg(set, " -> conflict type: %d, cutoff involved = %u\n", conftype, cutoffinvolved);
1264 if( conflictstore->lastcutoffbound != SCIP_INVALID && SCIPsetIsGE(set, cutoffbound, conflictstore->lastcutoffbound) ) /*lint !e777*/
1269 /* calculate scalar to determine whether the old primal bound is worse enough to remove the conflict */
1277 * note: we cannot remove conflicts that are marked as deleted because at this point in time we would destroy
1321 if( !conflictstore->updateside[i] || SCIPsetIsLE(set, improvement * conflictstore->dualprimalbnds[i], cutoffbound) )
1510 SCIP_CALL( SCIPconflictstoreAddConflict(conflictstore, blkmem, set, stat, tree, transprob, reopt, transcons, \
1519 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:6342
SCIP_RETCODE SCIPsetIncludeEventhdlr(SCIP_SET *set, SCIP_EVENTHDLR *eventhdlr)
Definition: set.c:4643
#define BMSfreeBlockMemoryArrayNull(mem, ptr, num)
Definition: memory.h:459
internal methods for managing events
SCIP_Bool SCIPsetIsLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6045
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18334
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:423
static SCIP_DECL_EVENTEXITSOL(eventExitsolConflictstore)
Definition: conflictstore.c:92
int SCIPconflictstoreGetNConflictsInStore(SCIP_CONFLICTSTORE *conflictstore)
Definition: conflictstore.c:1422
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:1476
SCIP_RETCODE SCIPconflictstoreClean(SCIP_CONFLICTSTORE *conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_REOPT *reopt)
Definition: conflictstore.c:879
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:1230
SCIP_EVENTHDLR * SCIPsetFindEventhdlr(SCIP_SET *set, const char *name)
Definition: set.c:4666
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:566
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:241
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:315
static SCIP_RETCODE conflictstoreEnsureMem(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, BMS_BLKMEM *blkmem, int num)
Definition: conflictstore.c:220
static SCIP_RETCODE cleanDeletedAndCheckedConflicts(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt, int *ndelconfs)
Definition: conflictstore.c:492
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
Definition: cons_linear.c:18382
SCIP_EXPORT void SCIPsortPtrRealRealBoolBool(void **ptrarray, SCIP_Real *realarray1, SCIP_Real *realarray2, SCIP_Bool *boolarray1, SCIP_Bool *boolarray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
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:2558
SCIP_RETCODE SCIPconsAddLocks(SCIP_CONS *cons, SCIP_SET *set, SCIP_LOCKTYPE locktype, int nlockspos, int nlocksneg)
Definition: cons.c:7241
Definition: heur_padm.c:125
static SCIP_RETCODE cleanDeletedAndCheckedDualrayCons(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt, int *ndelproofs)
Definition: conflictstore.c:528
SCIP_RETCODE SCIPconflictstoreCreate(SCIP_CONFLICTSTORE **conflictstore, SCIP_SET *set)
Definition: conflictstore.c:736
int SCIPconflictstoreGetNDualInfProofs(SCIP_CONFLICTSTORE *conflictstore)
Definition: conflictstore.c:1540
SCIP_EXPORT void SCIPsortPtrBool(void **ptrarray, SCIP_Bool *boolarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_Bool SCIPsetIsGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6081
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:361
SCIP_RETCODE SCIPconflictstoreClear(SCIP_CONFLICTSTORE *conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_REOPT *reopt)
Definition: conflictstore.c:816
internal methods for storing and manipulating the main problem
Definition: struct_cons.h:37
SCIP_RETCODE SCIPconflictstoreAddDualraycons(SCIP_CONFLICTSTORE *conflictstore, SCIP_CONS *dualproof, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_REOPT *reopt, SCIP_Bool hasrelaxvar)
Definition: conflictstore.c:952
Definition: struct_cons.h:117
static SCIP_RETCODE conflictstoreAddOrigConflict(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, BMS_BLKMEM *blkmem, SCIP_CONS *cons)
Definition: conflictstore.c:705
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:277
SCIP_RETCODE SCIPconflictstoreFree(SCIP_CONFLICTSTORE **conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_REOPT *reopt)
Definition: conflictstore.c:786
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18358
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:1409
static SCIP_RETCODE initConflictstore(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_PROB *transprob)
Definition: conflictstore.c:164
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:302
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:6310
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:604
SCIP_RETCODE SCIPconsRelease(SCIP_CONS **cons, BMS_BLKMEM *blkmem, SCIP_SET *set)
Definition: cons.c:6195
SCIP_RETCODE SCIPsetGetIntParam(SCIP_SET *set, const char *name, int *value)
Definition: set.c:3109
SCIP_Real SCIPconflictstoreGetAvgNnzDualBndProofs(SCIP_CONFLICTSTORE *conflictstore)
Definition: conflictstore.c:1550
Definition: type_set.h:40
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:1399
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, SCIP_Bool hasrelaxvar)
Definition: conflictstore.c:1039
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:311
SCIP_Bool SCIPsetIsGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6063
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:1135
internal methods for constraints and constraint handlers
int SCIPconflictstoreGetNDualBndProofs(SCIP_CONFLICTSTORE *conflictstore)
Definition: conflictstore.c:1564
SCIP_RETCODE SCIPclearConflictStore(SCIP *scip, SCIP_EVENT *event)
Definition: scip_prob.c:3280
Definition: type_set.h:44
static SCIP_DECL_EVENTINITSOL(eventInitsolConflictstore)
Definition: conflictstore.c:72
SCIP_Real SCIPconflictstoreGetAvgNnzDualInfProofs(SCIP_CONFLICTSTORE *conflictstore)
Definition: conflictstore.c:1527
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:18403
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:114
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition: memory.h:449
SCIP_RETCODE SCIPconflictstoreGetConflicts(SCIP_CONFLICTSTORE *conflictstore, SCIP_CONS **conflicts, int conflictsize, int *nconflicts)
Definition: conflictstore.c:1432
SCIP callable library.
static void adjustStorageSize(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set)
Definition: conflictstore.c:281