conflict.c
Go to the documentation of this file.
27 * Given is a set of bound changes that are not allowed being applied simultaneously, because they
28 * render the current node infeasible (e.g. because a single constraint is infeasible in the these
29 * bounds, or because the LP relaxation is infeasible). The goal is to deduce a clause on variables
30 * -- a conflict clause -- representing the "reason" for this conflict, i.e., the branching decisions
31 * or the deductions (applied e.g. in domain propagation) that lead to the conflict. This clause can
34 * conflict was detected by a locally valid constraint. In this case, the resulting conflict clause
113 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
179 static SCIP_BDCHGINFO* confgraphcurrentbdchginfo = NULL; /**< currently resolved bound change */
194 SCIPgmlWriteNode(confgraphfile, (unsigned int)(size_t)idptr, label, nodetype, fillcolor, bordercolor);
208 SCIPgmlWriteArc(confgraphfile, (unsigned int)(size_t)source, (unsigned int)(size_t)target, NULL, color);
210 SCIPgmlWriteEdge(confgraphfile, (unsigned int)(size_t)source, (unsigned int)(size_t)target, NULL, color);
214 /** creates a file to output the current conflict graph into; adds the conflict vertex to the graph */
264 /** adds a bound change node to the conflict graph and links it to the currently resolved bound change */
301 (void) SCIPsnprintf(label, SCIP_MAXSTRLEN, "%s %s %g\n[%s:%d]", SCIPvarGetName(SCIPbdchginfoGetVar(bdchginfo)),
338 (void) SCIPsnprintf(label, SCIP_MAXSTRLEN, "conf %d (%d)", confgraphnconflictsets, conflictset->validdepth);
339 confgraphWriteNode((void*)(size_t)confgraphnconflictsets, label, "rectangle", "#ff00ff", "#000000");
341 confgraphWriteEdge((void*)(size_t)confgraphnconflictsets, conflictset->bdchginfos[i], "#ff00ff");
359 return strcmp(SCIPconflicthdlrGetName((SCIP_CONFLICTHDLR*)elem1), SCIPconflicthdlrGetName((SCIP_CONFLICTHDLR*)elem2));
372 SCIP_CALL( SCIPsetConflicthdlrPriority(scip, (SCIP_CONFLICTHDLR*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/
389 SCIPsetDebugMsg(set, "including conflict handler %s in subscip %p\n", SCIPconflicthdlrGetName(conflicthdlr), (void*)set->scip);
406 SCIP_DECL_CONFLICTCOPY((*conflictcopy)), /**< copy method of conflict handler or NULL if you don't want to copy your plugin into sub-SCIPs */
410 SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)),/**< solving process initialization method of conflict handler */
411 SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)),/**< solving process deinitialization method of conflict handler */
445 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc, &(*conflicthdlr)->priority, TRUE, \
446 priority, INT_MIN, INT_MAX, paramChgdConflicthdlrPriority, (SCIP_PARAMDATA*)(*conflicthdlr)) ); /*lint !e740*/
460 SCIP_DECL_CONFLICTCOPY((*conflictcopy)), /**< copy method of conflict handler or NULL if you don't want to
465 SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)),/**< solving process initialization method of conflict handler */
466 SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)),/**< solving process deinitialization method of conflict handler */
475 SCIP_CALL_FINALLY( doConflicthdlrCreate(conflicthdlr, set, messagehdlr, blkmem, name, desc, priority,
476 conflictcopy, conflictfree, conflictinit, conflictexit, conflictinitsol, conflictexitsol, conflictexec,
633 SCIP_Real* relaxedbds, /**< array with relaxed bounds which are efficient to create a valid conflict */
653 SCIP_CALL( conflicthdlr->conflictexec(set->scip, conflicthdlr, node, validnode, bdchginfos, relaxedbds, nbdchginfos,
654 conftype, usescutoffbound, set->conf_separate, (SCIPnodeGetDepth(validnode) > 0), set->conf_dynamic,
741 SCIP_DECL_CONFLICTINITSOL((*conflictinitsol))/**< solving process initialization method of conflict handler */
752 SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol))/**< solving process deinitialization method of conflict handler */
816 SCIP_CONFLICTHDLR* conflicthdlr, /**< the conflict handler for which all clocks should be enabled or disabled */
1130 SCIP_CALL( proofsetAddSparseData(proofset, blkmem, vals, inds, nnz, SCIPaggrRowGetRhs(aggrrow)) );
1137 /** Removes a given variable @p var from position @p pos from the proofset and updates the right-hand side according
1138 * to sign of the coefficient, i.e., rhs -= coef * bound, where bound = lb if coef >= 0 and bound = ub, otherwise.
1140 * @note: The list of non-zero indices and coefficients will be updated by swapping the last non-zero index to @p pos.
1185 /** resizes the array of the temporary bound change informations to be able to store at least num bound change entries */
1209 /** creates a temporary bound change information object that is destroyed after the conflict sets are flushed */
1308 BMScopyMemoryArray((*targetconflictset)->bdchginfos, sourceconflictset->bdchginfos, sourceconflictset->nbdchginfos);
1309 BMScopyMemoryArray((*targetconflictset)->relaxedbds, sourceconflictset->relaxedbds, sourceconflictset->nbdchginfos);
1310 BMScopyMemoryArray((*targetconflictset)->sortvals, sourceconflictset->sortvals, sourceconflictset->nbdchginfos);
1333 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictset)->bdchginfos, (*conflictset)->bdchginfossize);
1334 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictset)->relaxedbds, (*conflictset)->bdchginfossize);
1335 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictset)->sortvals, (*conflictset)->bdchginfossize);
1339 /** resizes the arrays of the conflict set to be able to store at least num bound change entries */
1356 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictset->bdchginfos, conflictset->bdchginfossize, newsize) );
1357 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictset->relaxedbds, conflictset->bdchginfossize, newsize) );
1358 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictset->sortvals, conflictset->bdchginfossize, newsize) );
1412 * (SCIP_Real)(SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL))/(SCIP_Real)(SCIPcolGetNNonz(col));
1420 * (SCIP_Real)(SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL))/(SCIP_Real)(SCIPcolGetNNonz(col));
1428 /** check if the bound change info (which is the potential next candidate which is queued) is valid for the current
1429 * conflict analysis; a bound change info can get invalid if after this one was added to the queue, a weaker bound
1430 * change was added to the queue (due the bound widening idea) which immediately makes this bound change redundant; due
1431 * to the priority we did not removed that bound change info since that cost O(log(n)); hence we have to skip/ignore it
1434 * The following situations can occur before for example the bound change info (x >= 3) is potentially popped from the
1437 * Postcondition: the reason why (x >= 3) was queued is that at this time point no lower bound of x was involved yet in
1438 * the current conflict or the lower bound which was involved until then was stronger, e.g., (x >= 2).
1440 * 1) during the time until (x >= 3) gets potentially popped no weaker lower bound was added to the queue, in that case
1441 * the conflictlbcount is valid and conflictlb is 3; that is (var->conflictlbcount == conflict->count &&
1444 * 2) a weaker bound change info gets queued (e.g., x >= 4); this bound change is popped before (x >= 3) since it has
1445 * higher priority (which is the time stamp of the bound change info and (x >= 4) has to be done after (x >= 3)
1448 * a) if (x >= 4) is popped and added to the conflict set the conflictlbcount is still valid and conflictlb is at
1449 * most 4; that is (var->conflictlbcount == conflict->count && var->conflictlb >= 4); it follows that any bound
1452 * b) if (x >= 4) is popped and resolved without introducing a new lower bound on x until (x >= 3) is a potentially
1456 * c) if (x >= 4) is popped and resolved and a new lower bound on x (e.g., x >= 2) is introduced until (x >= 3) is
1457 * pooped, the conflictlbcount indicates that bound change is currently present; that is (var->conflictlbcount ==
1458 * conflict->count); however the (x >= 3) only has be explained if conflictlb matches that one; that is
1474 /* the bound change info of a binary (domained) variable can never be invalid since the concepts of relaxed bounds
1480 /* check if the bdchginfo is invaild since a tight/weaker bound change was already explained */
1483 if( var->conflictlbcount != conflict->count || var->conflictlb != SCIPbdchginfoGetNewbound(bdchginfo) ) /*lint !e777*/
1493 if( var->conflictubcount != conflict->count || var->conflictub != SCIPbdchginfoGetNewbound(bdchginfo) ) /*lint !e777*/
1526 SCIP_CALL( conflictsetEnsureBdchginfosMem(conflictset, blkmem, set, conflictset->nbdchginfos+1) );
1528 /* insert the new bound change in the arrays sorted by increasing variable index and by bound type */
1537 sortval = 2*idx + (int)boundtype; /* first sorting criteria: variable index, second criteria: boundtype */
1539 /* insert new element into the sorted arrays; if an element exits with the same value insert the new element afterwards
1541 * @todo check if it better (faster) to first search for the position O(log n) and compare the sort values and if
1545 SCIPsortedvecInsertIntPtrReal(sortvals, (void**)bdchginfos, relaxedbds, sortval, (void*)bdchginfo, relaxedbd, &conflictset->nbdchginfos, &pos);
1555 SCIPsortedvecDelPosIntPtrReal(sortvals, (void**)bdchginfos, relaxedbds, pos-1, &conflictset->nbdchginfos);
1560 SCIPsortedvecDelPosIntPtrReal(sortvals, (void**)bdchginfos, relaxedbds, pos, &conflictset->nbdchginfos);
1564 /* both bound change are equivalent; hence, keep the worse relaxed bound and remove one of them */
1565 relaxedbds[pos-1] = boundtype == SCIP_BOUNDTYPE_LOWER ? MAX(relaxedbds[pos-1], relaxedbd) : MIN(relaxedbds[pos-1], relaxedbd);
1566 SCIPsortedvecDelPosIntPtrReal(sortvals, (void**)bdchginfos, relaxedbds, pos, &conflictset->nbdchginfos);
1614 SCIP_CALL( conflictsetAddBound(conflictset, blkmem, set, bdchginfo, SCIPbdchginfoGetRelaxedBound(bdchginfo)) );
1618 SCIPsetDebugMsg(set, "-> bound change info [%d:<%s> %s %g] is invaild -> ignore it\n", SCIPbdchginfoGetDepth(bdchginfo),
1630 SCIP_CALL( conflictsetEnsureBdchginfosMem(conflictset, blkmem, set, confnbdchginfos + nbdchginfos) );
1655 sortval = 2*idx + (int)boundtype; /* first sorting criteria: variable index, second criteria: boundtype */
1665 SCIPsetDebugMsg(set, "-> bound change info [%d:<%s> %s %g] is invaild -> ignore it\n", SCIPbdchginfoGetDepth(bdchginfo),
1704 /* both bound change are equivalent; hence, keep the worse relaxed bound and remove one of them */
1705 confrelaxedbds[k] = (confsortvals[k] % 2 == 0) ? MAX(confrelaxedbds[k], confrelaxedbds[i]) : MIN(confrelaxedbds[k], confrelaxedbds[i]);
1727 /* the number of bound change infos cannot be decreased, it would mean that the conflict set was not merged
1775 * - if the branching rule operates on variables only, and if all branching variables up to a certain
1776 * depth level are member of the conflict, the conflict constraint can only be violated in the subtree
1777 * of the node at that depth, because in all other nodes, at least one of these branching variables
1779 * - if there is at least one branching variable in a node, we assume, that this branching was performed
1780 * on variables, and that the siblings of this node are disjunct w.r.t. the branching variables' fixings
1814 depth = MIN(depth, currentdepth+1); /* put diving/probing/strong branching changes in this depth level */
1819 while( conflictset->insertdepth < currentdepth && branchingincluded[conflictset->insertdepth+1] )
1825 assert(conflictset->validdepth <= conflictset->insertdepth && conflictset->insertdepth <= currentdepth);
1847 /* check, if all bound changes in conflictset2 are also present at least as tight in conflictset1;
1848 * we can stop immediately, if more bound changes are remaining in conflictset2 than in conflictset1
1850 for( i1 = 0, i2 = 0; i2 < conflictset2->nbdchginfos && conflictset1->nbdchginfos - i1 >= conflictset2->nbdchginfos - i2;
1961 /** inserts conflict set into sorted conflictsets array and deletes the conflict set pointer */
1985 /* if we apply repropagations, the conflict set should be inserted at most at its repropdepth */
1992 SCIPsetDebugMsg(set, "inserting conflict set (valid: %d, insert: %d, conf: %d, reprop: %d):\n",
1993 (*conflictset)->validdepth, (*conflictset)->insertdepth, (*conflictset)->conflictdepth, (*conflictset)->repropdepth);
2000 for( pos = 0; pos < conflict->nconflictsets && score < conflict->conflictsetscores[pos]; ++pos )
2011 /**@todo like in sepastore.c: calculate overlap between conflictsets -> large overlap reduces score */
2096 branchdir = (boundtype == SCIP_BOUNDTYPE_LOWER ? SCIP_BRANCHDIR_UPWARDS : SCIP_BRANCHDIR_DOWNWARDS); /*lint !e641*/
2139 branchdir = (boundtype == SCIP_BOUNDTYPE_LOWER ? SCIP_BRANCHDIR_UPWARDS : SCIP_BRANCHDIR_DOWNWARDS); /*lint !e641*/
2141 SCIP_CALL( SCIPvarIncNActiveConflicts(var, blkmem, set, stat, branchdir, bound, (SCIP_Real)conflictlength) );
2156 /** check conflict set for redundancy, other conflicts in the same conflict analysis could have led to global reductions
2187 assert(SCIPbdchginfoGetBoundtype(bdchginfos[v]) == SCIP_BOUNDTYPE_LOWER || SCIPsetIsGE(set, relaxedbds[v], SCIPbdchginfoGetNewbound(bdchginfos[v])));
2188 assert(SCIPbdchginfoGetBoundtype(bdchginfos[v]) == SCIP_BOUNDTYPE_UPPER || SCIPsetIsLE(set, relaxedbds[v], SCIPbdchginfoGetNewbound(bdchginfos[v])));
2231 SCIP_Bool* redundant /**< did we found a global reduction on a conflict set variable, which makes this conflict redundant */
2260 /* due to other conflict in the same conflict analysis, this conflict set might have become redundant */
2281 /* due to multiple conflict sets for one conflict, it can happen, that we already have redundant information in the
2298 SCIPsetDebugMsg(set, "remove redundant variable <%s> from conflict set\n", SCIPvarGetName(var));
2310 SCIPsetDebugMsg(set, "trivially removed %d redundant of %d variables from conflictset (%p)\n", ntrivialredvars, conflictset->nbdchginfos, (void*)conflictset);
2313 /* all variables where removed, the conflict cannot be fulfilled, i.e., we have an infeasibility proof */
2318 if( conflictset->nbdchginfos > set->conf_maxvarsdetectimpliedbounds || conflictset->nbdchginfos == 1 )
2342 assert(SCIPbdchginfoGetBoundtype(bdchginfos[v]) == SCIP_BOUNDTYPE_LOWER || SCIPsetIsGE(set, relaxedbds[v], SCIPbdchginfoGetNewbound(bdchginfos[v])));
2343 assert(SCIPbdchginfoGetBoundtype(bdchginfos[v]) == SCIP_BOUNDTYPE_UPPER || SCIPsetIsLE(set, relaxedbds[v], SCIPbdchginfoGetNewbound(bdchginfos[v])));
2345 /* for continuous variables, we can only use the relaxed version of the bounds negation: !(x <= u) -> x >= u */
2371 /* the literal is satisfied in global bounds (may happen due to weak "negation" of continuous variables)
2386 if( v == nbdchginfos && ((!set->conf_fullshortenconflict && nzeroimpls < 2) || (set->conf_fullshortenconflict && nzeroimpls < nbdchginfos)) )
2395 SCIPsetDebugMsg(set, "checking for global reductions and redundant conflict variables(in %s) on conflict:\n", SCIPprobGetName(prob));
2399 SCIPsetDebugMsgPrint(set, "%s %s %g", SCIPvarGetName(SCIPbdchginfoGetVar(bdchginfos[v])), (!boundtypes[v]) ? ">=" : "<=", bounds[v]);
2412 SCIP_CALL( SCIPshrinkDisjunctiveVarSet(set->scip, vars, bounds, boundtypes, redundants, nbdchginfos, nredvars, \
2424 SCIPsetDebugMsg(set, "conflict set (%p) led to %d global bound reductions\n", (void*) conflictset, *nbdchgs);
2431 SCIPsetDebugMsg(set, "conflict set (%p) is redundant because at least one global reduction, fulfills the conflict constraint\n", (void*)conflictset);
2446 SCIPsetDebugMsg(set, "remove redundant variable <%s> from conflict set\n", SCIPvarGetName(SCIPbdchginfoGetVar(bdchginfos[v])));
2460 SCIPsetDebugMsg(set, "removed %d redundant of %d variables from conflictset (%p)\n", (*nredvars), conflictset->nbdchginfos, (void*)conflictset);
2482 * in this case we need to create and add a constraint of size one such that propagating this constraint will
2526 || (boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsGE(set, newbound, SCIPvarGetUbGlobal(var))) )
2533 || (boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsLT(set, newbound, SCIPvarGetLbGlobal(var))) )
2535 SCIPsetDebugMsg(set, "detect global infeasibility at var <%s>: locdom=[%g,%g] glbdom=[%g,%g] new %s bound=%g\n",
2539 SCIP_CALL( SCIPnodeCutoff(tree->path[0], set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
2543 SCIPsetDebugMsg(set, "change %s bound of <%s>: %g -> %g\n", (boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper"),
2544 SCIPvarGetName(var), (boundtype == SCIP_BOUNDTYPE_LOWER ? SCIPvarGetLbGlobal(var) : SCIPvarGetUbGlobal(var)),
2577 SCIP_CALL( SCIPnodeAddBoundchg(tree->root, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, \
2610 SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables (or NULL for global bounds) */
2611 SCIP_Real* curvarubs /**< current upper bounds of active problem variables (or NULL for global bounds) */
2652 SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables (or NULL for global bounds) */
2653 SCIP_Real* curvarubs /**< current upper bounds of active problem variables (or NULL for global bounds) */
2692 SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables (or NULL for global bounds) */
2693 SCIP_Real* curvarubs /**< current upper bounds of active problem variables (or NULL for global bounds) */
2791 SCIP_CALL( tightenSingleVar(conflict, set, stat, tree, blkmem, origprob, transprob, reopt, lp, branchcand, \
2809 SCIP_CALL( tightenSingleVar(conflict, set, stat, tree, blkmem, origprob, transprob, reopt, lp, branchcand, \
2813 /* the minimal activity should stay unchanged because we tightened the bound that doesn't contribute to the
2891 SCIPsetDebugMsg(set, "detect global infeasibility: minactivity=%g, rhs=%g\n", globalminactivity, rhs);
2893 SCIP_CALL( SCIPnodeCutoff(tree->path[0], set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
2912 fillin += SCIPconflictstoreGetNDualInfProofs(conflictstore) * SCIPconflictstoreGetAvgNnzDualInfProofs(conflictstore);
2918 assert(conflicttype == SCIP_CONFTYPE_BNDEXCEEDING || conflicttype == SCIP_CONFTYPE_ALTBNDPROOF);
2920 fillin += SCIPconflictstoreGetNDualBndProofs(conflictstore) * SCIPconflictstoreGetAvgNnzDualBndProofs(conflictstore);
2931 SCIP_CALL( propagateLongProof(conflict, set, stat, reopt, tree, blkmem, origprob, transprob, lp, branchcand,
2938 else if( conflicttype == SCIP_CONFTYPE_BNDEXCEEDING || conflicttype == SCIP_CONFTYPE_ALTBNDPROOF )
2943 SCIP_CALL( SCIPcreateConsLinear(set->scip, &cons, name, 0, NULL, NULL, -SCIPsetInfinity(set), rhs,
2956 /* try to automatically convert a linear constraint into a more specific and more specialized constraint */
2977 SCIP_CALL( SCIPconflictstoreAddDualraycons(conflictstore, cons, blkmem, set, stat, transprob, reopt) );
2984 /* In some cases the constraint could not be updated to a more special type. However, it is possible that
2985 * constraint got scaled. Therefore, we need to be very careful when updating the lhs/rhs after the incumbent
3031 SCIP_CALL( SCIPconflictstoreAddDualsolcons(conflictstore, cons, blkmem, set, stat, transprob, reopt, scale, updateside) );
3037 SCIPsetDebugMsg(set, "added proof-constraint to node %p in depth 0 (nproofconss %d)\n", (void*)tree->path[0],
3053 assert(conflicttype == SCIP_CONFTYPE_BNDEXCEEDING || conflicttype == SCIP_CONFTYPE_ALTBNDPROOF);
3083 /* only one variable has a coefficient different to zero, we add this bound change instead of a constraint */
3097 SCIP_CALL( tightenSingleVar(conflict, set, stat, tree, blkmem, origprob, transprob, reopt, lp, \
3098 branchcand, eventqueue, cliquetable, vars[inds[0]], coefs[0], rhs, conflict->proofset->conflicttype) );
3108 if( set->conf_prefinfproof && proofsetGetConftype(conflict->proofset) == SCIP_CONFTYPE_BNDEXCEEDING )
3125 SCIP_CALL( createAndAddProofcons(conflict, conflictstore, conflict->proofset, set, stat, origprob, transprob, \
3143 /* only one variable has a coefficient different to zero, we add this bound change instead of a constraint */
3164 SCIP_CALL( createAndAddProofcons(conflict, conflictstore, conflict->proofsets[i], set, stat, origprob, \
3212 /* try to derive global bound changes and shorten the conflictset by using implication and clique and variable bound
3227 SCIP_CALL( detectImpliedBounds(set, transprob, conflictset, &nbdchgs, &nredvars, &redundant) );
3237 SCIP_CALL( SCIPdebugCheckConflict(blkmem, set, tree->root, conflictset->bdchginfos, conflictset->relaxedbds, conflictset->nbdchginfos) ); /*lint !e506 !e774*/
3241 SCIPsetDebugMsg(set, " -> conflict set removed %d redundant variables (old nvars %d, new nvars = %d)\n", nredvars, oldnbdchginfos, conflictset->nbdchginfos);
3242 SCIPsetDebugMsg(set, " -> conflict set led to %d global bound changes %s(cdpt:%d, fdpt:%d, confdpt:%d, len:%d):\n",
3243 nbdchgs, redundant ? "(conflict became redundant) " : "", SCIPtreeGetCurrentDepth(tree), SCIPtreeGetFocusDepth(tree),
3259 /* in case the conflict set contains only one bound change which is globally valid we apply that bound change
3260 * directly (except if we are in strong branching or diving - in this case a bound change would yield an unflushed LP
3263 * @note A bound change can only be applied if it is are related to the active node or if is a global bound
3264 * change. Bound changes which are related to any other node cannot be handled at point due to the internal
3279 /* for continuous variables, we can only use the relaxed version of the bounds negation: !(x <= u) -> x >= u */
3289 SCIP_CALL( SCIPnodeAddBoundchg(tree->path[conflictset->validdepth], blkmem, set, stat, transprob, origprob, tree,
3309 conflictset->nbdchginfos, conflictset->conflicttype, conflictset->usescutoffbound, *success, &result) );
3316 SCIPsetDebugMsg(set, " -> call conflict handler <%s> (prio=%d) to create conflict set with %d bounds returned result %d\n",
3317 SCIPconflicthdlrGetName(set->conflicthdlrs[h]), SCIPconflicthdlrGetPriority(set->conflicthdlrs[h]),
3325 /** adds the collected conflict constraints to the corresponding nodes; the best set->conf_maxconss conflict constraints
3326 * are added to the node of their validdepth; additionally (if not yet added, and if repropagation is activated), the
3327 * conflict constraint that triggers the earliest repropagation is added to the node of its validdepth
3365 /* calculate the maximal number of conflict sets to accept, and the maximal size of each accepted conflict set */
3376 SCIPsetDebugMsg(set, "flushing %d conflict sets at focus depth %d (maxconflictsets: %d, maxsize: %d)\n",
3397 assert(conflictset->repropdepth <= currentdepth || conflictset->repropdepth == INT_MAX); /* INT_MAX for dive/probing/strong */
3398 assert(conflictset->conflictdepth <= currentdepth || conflictset->conflictdepth == INT_MAX); /* INT_MAX for dive/probing/strong */
3408 /* if no conflict bounds exist, the node and its sub tree in the conflict set's valid depth can be
3416 SCIP_CALL( SCIPnodeCutoff(tree->path[conflictset->validdepth], set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
3421 /* if the conflict set is too long, use the conflict set only if it decreases the repropagation depth */
3424 SCIPsetDebugMsg(set, " -> conflict set is too long: %d > %d literals\n", conflictset->nbdchginfos, maxsize);
3425 if( set->conf_keepreprop && conflictset->repropagate && conflictset->repropdepth < repropdepth )
3436 SCIP_CALL( conflictAddConflictCons(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, \
3439 /* if no conflict bounds exist, the node and its sub tree in the conflict set's valid depth can be
3449 SCIP_CALL( SCIPnodeCutoff(tree->path[conflictset->validdepth], set, stat, tree, transprob, origprob, \
3457 SCIPsetDebugMsg(set, " -> conflict set %d/%d added (cdpt:%d, fdpt:%d, insert:%d, valid:%d, conf:%d, reprop:%d, len:%d):\n",
3458 nconflictsetsused+1, maxconflictsets, SCIPtreeGetCurrentDepth(tree), SCIPtreeGetFocusDepth(tree),
3459 conflictset->insertdepth, conflictset->validdepth, conflictset->conflictdepth, conflictset->repropdepth,
3473 /* reactivate propagation on the first node where one of the new conflict sets trigger a deduction */
3479 /* if the conflict constraint of smallest repropagation depth was not yet added, insert it now */
3487 SCIP_CALL( conflictAddConflictCons(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, \
3490 /* if no conflict bounds exist, the node and its sub tree in the conflict set's valid depth can be
3497 SCIPsetDebugMsg(set, " -> empty reprop conflict set in depth %d cuts off sub tree at depth %d\n",
3500 SCIP_CALL( SCIPnodeCutoff(tree->path[repropconflictset->validdepth], set, stat, tree, transprob, \
3507 SCIPsetDebugMsg(set, " -> additional reprop conflict set added (cdpt:%d, fdpt:%d, insert:%d, valid:%d, conf:%d, reprop:%d, len:%d):\n",
3509 repropconflictset->insertdepth, repropconflictset->validdepth, repropconflictset->conflictdepth,
3519 SCIPsetDebugMsg(set, "marked node %p in depth %d to be repropagated due to conflicts found in depth %d\n",
3557 /** returns the total number of literals in conflict constraints that were added to the problem */
3577 /** returns the total number of conflict constraints that were added globally to the problem */
3587 /** returns the total number of literals in conflict constraints that were added globally to the problem */
3617 /** returns the total number of literals in conflict constraints that were added locally to the problem */
3634 /** returns whether bound change has a valid reason that can be resolved in conflict analysis */
3664 if( !SCIPbdchgidxIsEarlierNonNull(SCIPbdchginfoGetIdx(bdchginfo1), SCIPbdchginfoGetIdx(bdchginfo2)) )
3670 /** return TRUE if conflict analysis is applicable; In case the function return FALSE there is no need to initialize the
3709 SCIP_CALL( SCIPpqueueCreate(&(*conflict)->bdchgqueue, set->mem_arraygrowinit, set->mem_arraygrowfac,
3711 SCIP_CALL( SCIPpqueueCreate(&(*conflict)->forcedbdchgqueue, set->mem_arraygrowinit, set->mem_arraygrowfac,
3852 /* increase the conflict counter, such that binary variables of new conflict set and new conflict queue are labeled
3856 if( conflict->count == 0 ) /* make sure, 0 is not a valid conflict counter (may happen due to integer overflow) */
3866 /* if the conflict score for the next conflict exceeds 1000.0, rescale all history conflict scores */
3890 /** marks bound to be present in the current conflict and returns whether a bound which is at least as tight was already
3916 /* the variable is already member of the conflict; hence check if the new bound is redundant */
3919 SCIPsetDebugMsg(set, "ignoring redundant bound change <%s> >= %g since a stronger lower bound exist <%s> >= %g\n",
3925 SCIPsetDebugMsg(set, "ignoring redundant bound change <%s> >= %g since this lower bound is already present\n", SCIPvarGetName(var), newbound);
3935 /* remember the lower bound and relaxed bound to allow only better/tighter lower bounds for that variables
3947 /* the variable is already member of the conflict; hence check if the new bound is redundant */
3950 SCIPsetDebugMsg(set, "ignoring redundant bound change <%s> <= %g since a stronger upper bound exist <%s> <= %g\n",
3956 SCIPsetDebugMsg(set, "ignoring redundant bound change <%s> <= %g since this upper bound is already present\n", SCIPvarGetName(var), newbound);
3966 /* remember the upper bound and relaxed bound to allow only better/tighter upper bounds for that variables
3995 assert(SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER || SCIPsetIsGE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
3996 assert(SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_UPPER || SCIPsetIsLE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
3998 SCIPsetDebugMsg(set, "putting bound change <%s> %s %g(%g) at depth %d to current conflict set\n",
4000 SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", SCIPbdchginfoGetNewbound(bdchginfo),
4003 /* mark the bound to be member of the conflict and check if a bound which is at least as tight is already member of
4024 /** returns whether the negation of the given bound change would lead to a globally valid literal */
4040 && ((boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsFeasGE(set, bound, SCIPvarGetUbGlobal(var)))
4041 || (boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsFeasLE(set, bound, SCIPvarGetLbGlobal(var)))));
4059 assert(SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER || SCIPsetIsGE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
4060 assert(SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_UPPER || SCIPsetIsLE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
4062 /* mark the bound to be member of the conflict and check if a bound which is at least as tight is already member of
4095 SCIP_BOUNDTYPE* boundtype, /**< pointer to type of bound that was changed: lower or upper bound */
4142 SCIPsetDebugMsg(set, " -> adding bound <%s> %s %.15g(%.15g) [status:%d, type:%d, depth:%d, pos:%d, reason:<%s>, info:%d] to candidates\n",
4151 : (SCIPbdchginfoGetInferProp(bdchginfo) != NULL ? SCIPpropGetName(SCIPbdchginfoGetInferProp(bdchginfo))
4153 SCIPbdchginfoGetChgtype(bdchginfo) != SCIP_BOUNDCHGTYPE_BRANCHING ? SCIPbdchginfoGetInferInfo(bdchginfo) : -1);
4156 * we even put bound changes without inference information on the queue in order to automatically
4165 assert(boundtype == SCIP_BOUNDTYPE_LOWER ? SCIPsetIsLE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)) : SCIPsetIsGE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
4168 assert(boundtype == SCIP_BOUNDTYPE_LOWER ? SCIPsetIsGT(set, relaxedbd, SCIPbdchginfoGetOldbound(bdchginfo)) : SCIPsetIsLT(set, relaxedbd, SCIPbdchginfoGetOldbound(bdchginfo)));
4177 SCIP_CALL( incVSIDS(var, blkmem, set, stat, boundtype, relaxedbd, set->conf_conflictgraphweight) );
4190 SCIP_BDCHGIDX* bdchgidx /**< bound change index (time stamp of bound change), or NULL for current time */
4230 /* if bound of variable was not changed (this means it is still the global bound), we can ignore the conflicting
4238 SCIP_CALL( conflictAddBound(conflict, blkmem, set, stat, var, boundtype, bdchginfo, SCIPbdchginfoGetNewbound(bdchginfo)) );
4251 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
4274 SCIPsetDebugMsg(set, "ignoring relaxed bound information since variable <%s> is multi-aggregated active\n", SCIPvarGetName(var));
4286 /* if bound of variable was not changed (this means it is still the global bound), we can ignore the conflicting
4295 /* get the position of the bound change information within the bound change array of the variable */
4299 /* if the relaxed bound should be ignored, set the relaxed bound to the bound given by the bdchgidx; that ensures
4313 /* due to numericis we compare the relaxed lower bound to the one present at the particular time point and take
4319 /* check if relaxed lower bound is smaller or equal to global lower bound; if so we can ignore the conflicting
4329 /* check if the old lower bound is greater than or equal to relaxed lower bound; if not we found the bound
4337 SCIPsetDebugMsg(set, "lower bound change %d oldbd=%.15g, newbd=%.15g, depth=%d, pos=%d, redundant=%u\n",
4342 /* if bound change is redundant (this means it now a global bound), we can ignore the conflicting bound */
4359 /* due to numericis we compare the relaxed upper bound to the one present at the particular time point and take
4365 /* check if relaxed upper bound is greater or equal to global upper bound; if so we can ignore the conflicting
4375 /* check if the old upper bound is smaller than or equal to the relaxed upper bound; if not we found the
4383 SCIPsetDebugMsg(set, "upper bound change %d oldbd=%.15g, newbd=%.15g, depth=%d, pos=%d, redundant=%u\n",
4388 /* if bound change is redundant (this means it now a global bound), we can ignore the conflicting bound */
4400 SCIP_CALL( conflictAddBound(conflict, blkmem, set, stat, var, boundtype, bdchginfo, relaxedbd) );
4405 /** checks if the given variable is already part of the current conflict set or queued for resolving with the same or
4413 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
4422 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED || SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR )
4437 SCIPsetDebugMsg(set, "already queued bound change <%s> >= %g\n", SCIPvarGetName(var), newbound);
4449 SCIPsetDebugMsg(set, "already queued bound change <%s> <= %g\n", SCIPvarGetName(var), newbound);
4465 /** returns the conflict lower bound if the variable is present in the current conflict set; otherwise the global lower
4482 /** returns the conflict upper bound if the variable is present in the current conflict set; otherwise the global upper
4520 /* mark the bound change to be no longer in the conflict (it will be either added again to the conflict set or
4561 SCIPdebugMessage("bound change info [%d:<%s> %s %g] is invaild -> pop it from the force queue\n", SCIPbdchginfoGetDepth(bdchginfo),
4580 SCIPdebugMessage("bound change info [%d:<%s> %s %g] is invaild -> pop it from the queue\n", SCIPbdchginfoGetDepth(bdchginfo),
4597 /** adds the current conflict set (extended by all remaining bound changes in the queue) to the pool of conflict sets */
4639 assert(0 <= conflict->conflictset->validdepth && conflict->conflictset->validdepth <= currentdepth);
4646 /* create a copy of the current conflict set, allocating memory for the additional elements of the queue */
4652 SCIPsetDebugMsg(set, "adding %d variables from the queue as temporary conflict variables\n", nbdchginfos);
4653 SCIP_CALL( conflictsetAddBounds(conflict, conflictset, blkmem, set, bdchginfos, nbdchginfos) );
4657 assert(conflictset->validdepth <= conflictset->insertdepth && conflictset->insertdepth <= currentdepth);
4658 SCIPsetDebugMsg(set, " -> conflict with %d literals found at depth %d is active in depth %d and valid in depth %d\n",
4664 if( (diving || conflictset->insertdepth < currentdepth) && conflictset->insertdepth <= focusdepth )
4666 /* if the conflict should not be located only in the subtree where it is useful, put it to its valid depth level */
4675 conflictset->bdchginfos, conflictset->relaxedbds, conflictset->nbdchginfos) ); /*lint !e506 !e774*/
4692 * current minimal valid depth level, because this depth level is the topmost level to add the conflict
4736 SCIPsetDebugMsg(set, "processing next conflicting bound (depth: %d, valid depth: %d, bdchgtype: %s [%s], vartype: %d): [<%s> %s %g(%g)]\n",
4752 SCIPsetDebugMsgPrint(set, " [%d:<%s> %s %g(%g)]", SCIPbdchginfoGetDepth(conflict->conflictset->bdchginfos[i]),
4754 SCIPbdchginfoGetBoundtype(conflict->conflictset->bdchginfos[i]) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
4755 SCIPbdchginfoGetNewbound(conflict->conflictset->bdchginfos[i]), conflict->conflictset->relaxedbds[i]);
4763 SCIPsetDebugMsgPrint(set, " [%d:<%s> %s %g(%g)]", SCIPbdchginfoGetDepth(info), SCIPvarGetName(SCIPbdchginfoGetVar(info)),
4764 bdchginfoIsInvalid(conflict, info) ? "<!>" : SCIPbdchginfoGetBoundtype(info) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
4773 SCIPsetDebugMsgPrint(set, " [%d:<%s> %s %g(%g)]", SCIPbdchginfoGetDepth(info), SCIPvarGetName(SCIPbdchginfoGetVar(info)),
4774 bdchginfoIsInvalid(conflict, info) ? "<!>" : SCIPbdchginfoGetBoundtype(info) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
4783 * current minimal valid depth level (which is initialized with the valid depth level of the initial
4784 * conflict set), because this depth level is the topmost level to add the conflict constraint to anyways
4799 /* resolve bound change by asking the constraint that infered the bound to put all bounds that were
4808 SCIPsetDebugMsg(set, "resolving bound <%s> %s %g(%g) [status:%d, type:%d, depth:%d, pos:%d]: <%s> %s %g [cons:<%s>(%s), info:%d]\n",
4821 /* in case the inference variables is not an active variables, we need to transform the relaxed bound */
4830 || (SCIPvarGetStatus(infervar) == SCIP_VARSTATUS_MULTAGGR && SCIPvarGetMultaggrNVars(infervar) == 1));
4845 SCIP_CALL( SCIPconsResolvePropagation(infercons, set, infervar, inferinfo, inferboundtype, bdchgidx, relaxedbd, &result) );
4859 /* resolve bound change by asking the propagator that infered the bound to put all bounds that were
4868 SCIPsetDebugMsg(set, "resolving bound <%s> %s %g(%g) [status:%d, depth:%d, pos:%d]: <%s> %s %g [prop:<%s>, info:%d]\n",
4878 SCIP_CALL( SCIPpropResolvePropagation(inferprop, set, infervar, inferinfo, inferboundtype, bdchgidx, relaxedbd, &result) );
4899 /* in case the bound change was not resolved, the conflict queues should have the same size (contents) */
4906 /** if only one conflicting bound change of the last depth level was used, and if this can be resolved,
4907 * creates GRASP-like reconvergence conflict constraints in the conflict graph up to the branching variable of this
4922 int* nreconvliterals /**< pointer to store the number of literals generated reconvergence constraints */
4944 /* check, whether local constraints are allowed; however, don't generate reconvergence constraints that are only valid
4956 /* for each succeeding UIP pair of the last depth level, create one reconvergence constraint */
4958 while( uip != NULL && SCIPbdchginfoGetDepth(uip) == SCIPbdchginfoGetDepth(firstuip) && bdchginfoIsResolvable(uip) )
4970 SCIPsetDebugMsg(set, "creating reconvergence constraint for UIP <%s> %s %g in depth %d pos %d\n",
4971 SCIPvarGetName(SCIPbdchginfoGetVar(uip)), SCIPbdchginfoGetBoundtype(uip) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
4982 * for reconvergence constraints for continuous variables we can only use the "negation" !(x <= u) == (x >= u);
4983 * during conflict analysis, we treat a continuous bound "x >= u" in the conflict set as "x > u", and in the
4995 oppositeuipboundtype == SCIP_BOUNDTYPE_LOWER ? SCIP_REAL_MIN : SCIP_REAL_MAX, oppositeuipbound, &oppositeuip) );
5017 /* remove currently processed candidate and get next conflicting bound from the conflict candidate queue before
5018 * we remove the candidate we have to collect the relaxed bound since removing the candidate from the queue
5028 assert(nextbdchginfo == NULL || SCIPbdchginfoGetDepth(bdchginfo) >= SCIPbdchginfoGetDepth(nextbdchginfo)
5032 /* bound changes that are higher in the tree than the valid depth of the conflict can be ignored;
5076 assert(conflict->conflictset->nbdchginfos >= 1); /* starting UIP is already member of the conflict set */
5078 /* if this is the first variable of the conflict set besides the current starting UIP, it is the next
5095 /* get next conflicting bound from the conflict candidate queue (this does not need to be nextbdchginfo, because
5103 /* if only one propagation was resolved, the reconvergence constraint is already member of the constraint set
5116 conflict->conflictset->nbdchginfos, conflict->bdchgqueue, conflict->forcedbdchgqueue) ); /*lint !e506 !e774*/
5118 SCIPsetDebugMsg(set, "creating reconvergence constraint from UIP <%s> to UIP <%s> in depth %d with %d literals after %d resolutions\n",
5123 SCIP_CALL( conflictAddConflictset(conflict, blkmem, set, stat, tree, validdepth, diving, FALSE, &success, &nlits) );
5131 /* clear the conflict candidate queue and the conflict set (to make sure, oppositeuip is not referenced anymore) */
5143 /** analyzes conflicting bound changes that were added with calls to SCIPconflictAddBound() and
5144 * SCIPconflictAddRelaxedBound(), and on success, calls the conflict handlers to create a conflict constraint out of
5157 SCIP_Bool mustresolve, /**< should the conflict set only be used, if a resolution was applied? */
5159 int* nliterals, /**< pointer to store the number of literals in generated conflict constraints */
5161 int* nreconvliterals /**< pointer to store the number of literals generated reconvergence constraints */
5196 /* if we must resolve at least one bound change, find the first UIP at least in the last depth level */
5200 SCIPsetDebugMsg(set, "analyzing conflict with %d+%d conflict candidates and starting conflict set of size %d in depth %d (resolvedepth=%d)\n",
5209 /* check, whether local conflicts are allowed; however, don't generate conflict constraints that are only valid in the
5216 /* allocate temporary memory for storing first UIPs (in each depth level, at most two bound changes can be flagged
5230 NULL, conflict->conflictset->bdchginfos, conflict->conflictset->relaxedbds, conflict->conflictset->nbdchginfos, \
5252 assert(SCIPbdchginfoGetPos(bdchginfo) < (int)tree->path[bdchgdepth]->domchg->domchgbound.nboundchgs);
5253 assert(tree->path[bdchgdepth]->domchg->domchgbound.boundchgs[SCIPbdchginfoGetPos(bdchginfo)].var
5255 assert(tree->path[bdchgdepth]->domchg->domchgbound.boundchgs[SCIPbdchginfoGetPos(bdchginfo)].newbound
5258 ? SCIPvarGetLbGlobal(SCIPbdchginfoGetVar(bdchginfo)) : SCIPvarGetUbGlobal(SCIPbdchginfoGetVar(bdchginfo)))
5260 assert((SCIP_BOUNDTYPE)tree->path[bdchgdepth]->domchg->domchgbound.boundchgs[SCIPbdchginfoGetPos(bdchginfo)].boundtype
5268 lastconsresoldepth = bdchgdepth; /* all intermediate depth levels consisted of only unresolved bound changes */
5269 else if( bdchgdepth < lastconsresoldepth && (set->conf_interconss == -1 || *nconss < set->conf_interconss) )
5275 SCIPsetDebugMsg(set, "creating intermediate conflictset after %d resolutions up to depth %d (valid at depth %d): %d conflict bounds, %d bounds in queue\n",
5279 SCIP_CALL( conflictAddConflictset(conflict, blkmem, set, stat, tree, validdepth, diving, TRUE, &success, &nlits) );
5290 /* remove currently processed candidate and get next conflicting bound from the conflict candidate queue before
5291 * we remove the candidate we have to collect the relaxed bound since removing the candidate from the queue
5300 assert(nextbdchginfo == NULL || SCIPbdchginfoGetDepth(bdchginfo) >= SCIPbdchginfoGetDepth(nextbdchginfo)
5303 /* we don't need to resolve bound changes that are already active in the valid depth of the current conflict set,
5304 * because the conflict set can only be added locally at the valid depth, and all bound changes applied in this
5305 * depth or earlier can be removed from the conflict constraint, since they are already applied in the constraint's
5369 bdchginfo, conflict->conflictset->bdchginfos, conflict->conflictset->relaxedbds, conflict->conflictset->nbdchginfos, \
5372 /* get next conflicting bound from the conflict candidate queue (this needs not to be nextbdchginfo, because
5390 SCIP_CALL( conflictAddConflictset(conflict, blkmem, set, stat, tree, validdepth, diving, TRUE, &success, &nlits) );
5431 /** analyzes conflicting bound changes that were added with calls to SCIPconflictAddBound(), and on success, calls the
5468 SCIPsetDebugMsg(set, "analyzing conflict after infeasible propagation in depth %d\n", SCIPtreeGetCurrentDepth(tree));
5476 SCIP_CALL( conflictAnalyze(conflict, blkmem, set, stat, prob, tree, FALSE, validdepth, TRUE, &nconss, &nliterals, \