conflict.c
Go to the documentation of this file.
37 * Given is a set of bound changes that are not allowed being applied simultaneously, because they
38 * render the current node infeasible (e.g. because a single constraint is infeasible in the these
39 * bounds, or because the LP relaxation is infeasible). The goal is to deduce a clause on variables
40 * -- a conflict clause -- representing the "reason" for this conflict, i.e., the branching decisions
41 * or the deductions (applied e.g. in domain propagation) that lead to the conflict. This clause can
44 * conflict was detected by a locally valid constraint. In this case, the resulting conflict clause
123 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
190 static SCIP_BDCHGINFO* confgraphcurrentbdchginfo = NULL; /**< currently resolved bound change */
205 SCIPgmlWriteNode(confgraphfile, (unsigned int)(size_t)idptr, label, nodetype, fillcolor, bordercolor);
219 SCIPgmlWriteArc(confgraphfile, (unsigned int)(size_t)source, (unsigned int)(size_t)target, NULL, color);
221 SCIPgmlWriteEdge(confgraphfile, (unsigned int)(size_t)source, (unsigned int)(size_t)target, NULL, color);
225 /** creates a file to output the current conflict graph into; adds the conflict vertex to the graph */
275 /** adds a bound change node to the conflict graph and links it to the currently resolved bound change */
312 (void) SCIPsnprintf(label, SCIP_MAXSTRLEN, "%s %s %g\n[%s:%d]", SCIPvarGetName(SCIPbdchginfoGetVar(bdchginfo)),
349 (void) SCIPsnprintf(label, SCIP_MAXSTRLEN, "conf %d (%d)", confgraphnconflictsets, conflictset->validdepth);
350 confgraphWriteNode((void*)(size_t)confgraphnconflictsets, label, "rectangle", "#ff00ff", "#000000");
352 confgraphWriteEdge((void*)(size_t)confgraphnconflictsets, conflictset->bdchginfos[i], "#ff00ff");
370 return strcmp(SCIPconflicthdlrGetName((SCIP_CONFLICTHDLR*)elem1), SCIPconflicthdlrGetName((SCIP_CONFLICTHDLR*)elem2));
383 SCIP_CALL( SCIPsetConflicthdlrPriority(scip, (SCIP_CONFLICTHDLR*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/
400 SCIPsetDebugMsg(set, "including conflict handler %s in subscip %p\n", SCIPconflicthdlrGetName(conflicthdlr), (void*)set->scip);
417 SCIP_DECL_CONFLICTCOPY((*conflictcopy)), /**< copy method of conflict handler or NULL if you don't want to copy your plugin into sub-SCIPs */
421 SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)),/**< solving process initialization method of conflict handler */
422 SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)),/**< solving process deinitialization method of conflict handler */
456 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc, &(*conflicthdlr)->priority, TRUE, \
457 priority, INT_MIN, INT_MAX, paramChgdConflicthdlrPriority, (SCIP_PARAMDATA*)(*conflicthdlr)) ); /*lint !e740*/
471 SCIP_DECL_CONFLICTCOPY((*conflictcopy)), /**< copy method of conflict handler or NULL if you don't want to
476 SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)),/**< solving process initialization method of conflict handler */
477 SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)),/**< solving process deinitialization method of conflict handler */
486 SCIP_CALL_FINALLY( doConflicthdlrCreate(conflicthdlr, set, messagehdlr, blkmem, name, desc, priority,
487 conflictcopy, conflictfree, conflictinit, conflictexit, conflictinitsol, conflictexitsol, conflictexec,
644 SCIP_Real* relaxedbds, /**< array with relaxed bounds which are efficient to create a valid conflict */
664 SCIP_CALL( conflicthdlr->conflictexec(set->scip, conflicthdlr, node, validnode, bdchginfos, relaxedbds, nbdchginfos,
665 conftype, usescutoffbound, set->conf_separate, (SCIPnodeGetDepth(validnode) > 0), set->conf_dynamic,
752 SCIP_DECL_CONFLICTINITSOL((*conflictinitsol))/**< solving process initialization method of conflict handler */
763 SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol))/**< solving process deinitialization method of conflict handler */
827 SCIP_CONFLICTHDLR* conflicthdlr, /**< the conflict handler for which all clocks should be enabled or disabled */
1156 SCIP_CALL( proofsetAddSparseData(proofset, blkmem, vals, inds, nnz, SCIPaggrRowGetRhs(aggrrow)) );
1163 /** Removes a given variable @p var from position @p pos from the proofset and updates the right-hand side according
1164 * to sign of the coefficient, i.e., rhs -= coef * bound, where bound = lb if coef >= 0 and bound = ub, otherwise.
1166 * @note: The list of non-zero indices and coefficients will be updated by swapping the last non-zero index to @p pos.
1211 /** resizes the array of the temporary bound change informations to be able to store at least num bound change entries */
1235 /** creates a temporary bound change information object that is destroyed after the conflict sets are flushed */
1335 BMScopyMemoryArray((*targetconflictset)->bdchginfos, sourceconflictset->bdchginfos, sourceconflictset->nbdchginfos);
1336 BMScopyMemoryArray((*targetconflictset)->relaxedbds, sourceconflictset->relaxedbds, sourceconflictset->nbdchginfos);
1337 BMScopyMemoryArray((*targetconflictset)->sortvals, sourceconflictset->sortvals, sourceconflictset->nbdchginfos);
1361 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictset)->bdchginfos, (*conflictset)->bdchginfossize);
1362 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictset)->relaxedbds, (*conflictset)->bdchginfossize);
1363 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictset)->sortvals, (*conflictset)->bdchginfossize);
1367 /** resizes the arrays of the conflict set to be able to store at least num bound change entries */
1384 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictset->bdchginfos, conflictset->bdchginfossize, newsize) );
1385 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictset->relaxedbds, conflictset->bdchginfossize, newsize) );
1386 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictset->sortvals, conflictset->bdchginfossize, newsize) );
1440 * (SCIP_Real)(SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL))/(SCIP_Real)(SCIPcolGetNNonz(col));
1448 * (SCIP_Real)(SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL))/(SCIP_Real)(SCIPcolGetNNonz(col));
1456 /** check if the bound change info (which is the potential next candidate which is queued) is valid for the current
1457 * conflict analysis; a bound change info can get invalid if after this one was added to the queue, a weaker bound
1458 * change was added to the queue (due the bound widening idea) which immediately makes this bound change redundant; due
1459 * to the priority we did not removed that bound change info since that cost O(log(n)); hence we have to skip/ignore it
1462 * The following situations can occur before for example the bound change info (x >= 3) is potentially popped from the
1465 * Postcondition: the reason why (x >= 3) was queued is that at this time point no lower bound of x was involved yet in
1466 * the current conflict or the lower bound which was involved until then was stronger, e.g., (x >= 2).
1468 * 1) during the time until (x >= 3) gets potentially popped no weaker lower bound was added to the queue, in that case
1469 * the conflictlbcount is valid and conflictlb is 3; that is (var->conflictlbcount == conflict->count &&
1472 * 2) a weaker bound change info gets queued (e.g., x >= 4); this bound change is popped before (x >= 3) since it has
1473 * higher priority (which is the time stamp of the bound change info and (x >= 4) has to be done after (x >= 3)
1476 * a) if (x >= 4) is popped and added to the conflict set the conflictlbcount is still valid and conflictlb is at
1477 * most 4; that is (var->conflictlbcount == conflict->count && var->conflictlb >= 4); it follows that any bound
1480 * b) if (x >= 4) is popped and resolved without introducing a new lower bound on x until (x >= 3) is a potentially
1484 * 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
1485 * pooped, the conflictlbcount indicates that bound change is currently present; that is (var->conflictlbcount ==
1486 * conflict->count); however the (x >= 3) only has be explained if conflictlb matches that one; that is
1502 /* the bound change info of a binary (domained) variable can never be invalid since the concepts of relaxed bounds
1508 /* check if the bdchginfo is invaild since a tight/weaker bound change was already explained */
1511 if( var->conflictlbcount != conflict->count || var->conflictlb != SCIPbdchginfoGetNewbound(bdchginfo) ) /*lint !e777*/
1521 if( var->conflictubcount != conflict->count || var->conflictub != SCIPbdchginfoGetNewbound(bdchginfo) ) /*lint !e777*/
1554 SCIP_CALL( conflictsetEnsureBdchginfosMem(conflictset, blkmem, set, conflictset->nbdchginfos+1) );
1556 /* insert the new bound change in the arrays sorted by increasing variable index and by bound type */
1565 sortval = 2*idx + (int)boundtype; /* first sorting criteria: variable index, second criteria: boundtype */
1567 /* insert new element into the sorted arrays; if an element exits with the same value insert the new element afterwards
1569 * @todo check if it better (faster) to first search for the position O(log n) and compare the sort values and if
1573 SCIPsortedvecInsertIntPtrReal(sortvals, (void**)bdchginfos, relaxedbds, sortval, (void*)bdchginfo, relaxedbd, &conflictset->nbdchginfos, &pos);
1583 SCIPsortedvecDelPosIntPtrReal(sortvals, (void**)bdchginfos, relaxedbds, pos-1, &conflictset->nbdchginfos);
1588 SCIPsortedvecDelPosIntPtrReal(sortvals, (void**)bdchginfos, relaxedbds, pos, &conflictset->nbdchginfos);
1592 /* both bound change are equivalent; hence, keep the worse relaxed bound and remove one of them */
1593 relaxedbds[pos-1] = boundtype == SCIP_BOUNDTYPE_LOWER ? MAX(relaxedbds[pos-1], relaxedbd) : MIN(relaxedbds[pos-1], relaxedbd);
1594 SCIPsortedvecDelPosIntPtrReal(sortvals, (void**)bdchginfos, relaxedbds, pos, &conflictset->nbdchginfos);
1645 SCIP_CALL( conflictsetAddBound(conflictset, blkmem, set, bdchginfo, SCIPbdchginfoGetRelaxedBound(bdchginfo)) );
1649 SCIPsetDebugMsg(set, "-> bound change info [%d:<%s> %s %g] is invaild -> ignore it\n", SCIPbdchginfoGetDepth(bdchginfo),
1661 SCIP_CALL( conflictsetEnsureBdchginfosMem(conflictset, blkmem, set, confnbdchginfos + nbdchginfos) );
1686 sortval = 2*idx + (int)boundtype; /* first sorting criteria: variable index, second criteria: boundtype */
1699 SCIPsetDebugMsg(set, "-> bound change info [%d:<%s> %s %g] is invaild -> ignore it\n", SCIPbdchginfoGetDepth(bdchginfo),
1738 /* both bound change are equivalent; hence, keep the worse relaxed bound and remove one of them */
1739 confrelaxedbds[k] = (confsortvals[k] % 2 == 0) ? MAX(confrelaxedbds[k], confrelaxedbds[i]) : MIN(confrelaxedbds[k], confrelaxedbds[i]);
1761 /* the number of bound change infos cannot be decreased, it would mean that the conflict set was not merged
1809 * - if the branching rule operates on variables only, and if all branching variables up to a certain
1810 * depth level are member of the conflict, the conflict constraint can only be violated in the subtree
1811 * of the node at that depth, because in all other nodes, at least one of these branching variables
1813 * - if there is at least one branching variable in a node, we assume, that this branching was performed
1814 * on variables, and that the siblings of this node are disjunct w.r.t. the branching variables' fixings
1848 depth = MIN(depth, currentdepth+1); /* put diving/probing/strong branching changes in this depth level */
1853 while( conflictset->insertdepth < currentdepth && branchingincluded[conflictset->insertdepth+1] )
1859 assert(conflictset->validdepth <= conflictset->insertdepth && conflictset->insertdepth <= currentdepth);
1881 /* check, if all bound changes in conflictset2 are also present at least as tight in conflictset1;
1882 * we can stop immediately, if more bound changes are remaining in conflictset2 than in conflictset1
1884 for( i1 = 0, i2 = 0; i2 < conflictset2->nbdchginfos && conflictset1->nbdchginfos - i1 >= conflictset2->nbdchginfos - i2;
1892 for( ; i1 < conflictset1->nbdchginfos && conflictset1->sortvals[i1] < sortval; ++i1 ) /*lint !e445*/
1995 /** inserts conflict set into sorted conflictsets array and deletes the conflict set pointer */
2019 /* if we apply repropagations, the conflict set should be inserted at most at its repropdepth */
2026 SCIPsetDebugMsg(set, "inserting conflict set (valid: %d, insert: %d, conf: %d, reprop: %d):\n",
2027 (*conflictset)->validdepth, (*conflictset)->insertdepth, (*conflictset)->conflictdepth, (*conflictset)->repropdepth);
2034 for( pos = 0; pos < conflict->nconflictsets && score < conflict->conflictsetscores[pos]; ++pos )
2045 /**@todo like in sepastore.c: calculate overlap between conflictsets -> large overlap reduces score */
2130 branchdir = (boundtype == SCIP_BOUNDTYPE_LOWER ? SCIP_BRANCHDIR_UPWARDS : SCIP_BRANCHDIR_DOWNWARDS); /*lint !e641*/
2173 branchdir = (boundtype == SCIP_BOUNDTYPE_LOWER ? SCIP_BRANCHDIR_UPWARDS : SCIP_BRANCHDIR_DOWNWARDS); /*lint !e641*/
2175 SCIP_CALL( SCIPvarIncNActiveConflicts(var, blkmem, set, stat, branchdir, bound, (SCIP_Real)conflictlength) );
2190 /** check conflict set for redundancy, other conflicts in the same conflict analysis could have led to global reductions
2221 assert(SCIPbdchginfoGetBoundtype(bdchginfos[v]) == SCIP_BOUNDTYPE_LOWER || SCIPsetIsGE(set, relaxedbds[v], SCIPbdchginfoGetNewbound(bdchginfos[v])));
2222 assert(SCIPbdchginfoGetBoundtype(bdchginfos[v]) == SCIP_BOUNDTYPE_UPPER || SCIPsetIsLE(set, relaxedbds[v], SCIPbdchginfoGetNewbound(bdchginfos[v])));
2265 SCIP_Bool* redundant /**< did we found a global reduction on a conflict set variable, which makes this conflict redundant */
2294 /* due to other conflict in the same conflict analysis, this conflict set might have become redundant */
2315 /* due to multiple conflict sets for one conflict, it can happen, that we already have redundant information in the
2332 SCIPsetDebugMsg(set, "remove redundant variable <%s> from conflict set\n", SCIPvarGetName(var));
2344 SCIPsetDebugMsg(set, "trivially removed %d redundant of %d variables from conflictset (%p)\n", ntrivialredvars, conflictset->nbdchginfos, (void*)conflictset);
2347 /* all variables where removed, the conflict cannot be fulfilled, i.e., we have an infeasibility proof */
2352 if( conflictset->nbdchginfos > set->conf_maxvarsdetectimpliedbounds || conflictset->nbdchginfos == 1 )
2376 assert(SCIPbdchginfoGetBoundtype(bdchginfos[v]) == SCIP_BOUNDTYPE_LOWER || SCIPsetIsGE(set, relaxedbds[v], SCIPbdchginfoGetNewbound(bdchginfos[v])));
2377 assert(SCIPbdchginfoGetBoundtype(bdchginfos[v]) == SCIP_BOUNDTYPE_UPPER || SCIPsetIsLE(set, relaxedbds[v], SCIPbdchginfoGetNewbound(bdchginfos[v])));
2379 /* for continuous variables, we can only use the relaxed version of the bounds negation: !(x <= u) -> x >= u */
2405 /* the literal is satisfied in global bounds (may happen due to weak "negation" of continuous variables)
2420 if( v == nbdchginfos && ((!set->conf_fullshortenconflict && nzeroimpls < 2) || (set->conf_fullshortenconflict && nzeroimpls < nbdchginfos)) )
2429 SCIPsetDebugMsg(set, "checking for global reductions and redundant conflict variables(in %s) on conflict:\n", SCIPprobGetName(prob));
2433 SCIPsetDebugMsgPrint(set, "%s %s %g", SCIPvarGetName(SCIPbdchginfoGetVar(bdchginfos[v])), (!boundtypes[v]) ? ">=" : "<=", bounds[v]);
2446 SCIP_CALL( SCIPshrinkDisjunctiveVarSet(set->scip, vars, bounds, boundtypes, redundants, nbdchginfos, nredvars, \
2461 SCIPsetDebugMsg(set, "conflict set (%p) led to %d global bound reductions\n", (void*) conflictset, *nbdchgs);
2468 SCIPsetDebugMsg(set, "conflict set (%p) is redundant because at least one global reduction, fulfills the conflict constraint\n", (void*)conflictset);
2484 SCIPsetDebugMsg(set, "remove redundant variable <%s> from conflict set\n", SCIPvarGetName(SCIPbdchginfoGetVar(bdchginfos[v])));
2498 SCIPsetDebugMsg(set, "removed %d redundant of %d variables from conflictset (%p)\n", (*nredvars), conflictset->nbdchginfos, (void*)conflictset);
2525 * in this case we need to create and add a constraint of size one such that propagating this constraint will
2570 || (boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsGE(set, newbound, SCIPvarGetUbGlobal(var)))) )
2578 || (boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsLT(set, newbound, SCIPvarGetLbGlobal(var)))) )
2580 SCIPsetDebugMsg(set, "detected global infeasibility at var <%s>: locdom=[%g,%g] glbdom=[%g,%g] new %s bound=%g\n",
2584 SCIP_CALL( SCIPnodeCutoff(tree->path[0], set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
2596 SCIPvarGetName(var), varGetChar(var), boundtype == SCIP_BOUNDTYPE_UPPER ? "<=" : ">=", newbound,
2638 SCIP_CALL( SCIPnodeAddBoundchg(tree->path[0], blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, \
2683 SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables (or NULL for global bounds) */
2684 SCIP_Real* curvarubs, /**< current upper bounds of active problem variables (or NULL for global bounds) */
2685 SCIP_Bool* infdelta /**< pointer to store whether at least one variable contributes with an infinite value */
2764 SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables (or NULL for global bounds) */
2765 SCIP_Real* curvarubs /**< current upper bounds of active problem variables (or NULL for global bounds) */
2830 SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables (or NULL for global bounds) */
2831 SCIP_Real* curvarubs /**< current upper bounds of active problem variables (or NULL for global bounds) */
2959 SCIP_CALL( tightenSingleVar(conflict, set, stat, tree, blkmem, origprob, transprob, reopt, lp, branchcand, \
2977 SCIP_CALL( tightenSingleVar(conflict, set, stat, tree, blkmem, origprob, transprob, reopt, lp, branchcand, \
2981 /* the minimal activity should stay unchanged because we tightened the bound that doesn't contribute to the
2984 assert(SCIPsetIsEQ(set, minact, getMinActivity(set, transprob, coefs, inds, nnz, NULL, NULL)));
3064 SCIPsetDebugMsg(set, "detect global infeasibility: minactivity=%g, rhs=%g\n", globalminactivity, rhs);
3066 SCIP_CALL( SCIPnodeCutoff(tree->path[proofset->validdepth], set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
3086 fillin += SCIPconflictstoreGetNDualInfProofs(conflictstore) * SCIPconflictstoreGetAvgNnzDualInfProofs(conflictstore);
3092 assert(conflicttype == SCIP_CONFTYPE_BNDEXCEEDING || conflicttype == SCIP_CONFTYPE_ALTBNDPROOF);
3094 fillin += SCIPconflictstoreGetNDualBndProofs(conflictstore) * SCIPconflictstoreGetAvgNnzDualBndProofs(conflictstore);
3107 SCIP_CALL( propagateLongProof(conflict, set, stat, reopt, tree, blkmem, origprob, transprob, lp, branchcand,
3113 /* check if conflict contains variables that are invalid after a restart to label it appropriately */
3128 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "dualproof_inf_%" SCIP_LONGINT_FORMAT, conflict->ndualproofsinfsuccess);
3129 else if( conflicttype == SCIP_CONFTYPE_BNDEXCEEDING || conflicttype == SCIP_CONFTYPE_ALTBNDPROOF )
3130 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "dualproof_bnd_%" SCIP_LONGINT_FORMAT, conflict->ndualproofsbndsuccess);
3134 SCIP_CALL( SCIPcreateConsLinear(set->scip, &cons, name, 0, NULL, NULL, -SCIPsetInfinity(set), rhs,
3148 /* try to automatically convert a linear constraint into a more specific and more specialized constraint */
3169 SCIP_CALL( SCIPconflictstoreAddDualraycons(conflictstore, cons, blkmem, set, stat, transprob, reopt, hasrelaxvar) );
3176 /* In some cases the constraint could not be updated to a more special type. However, it is possible that
3177 * constraint got scaled. Therefore, we need to be very careful when updating the lhs/rhs after the incumbent
3223 SCIP_CALL( SCIPconflictstoreAddDualsolcons(conflictstore, cons, blkmem, set, stat, transprob, reopt, scale, updateside, hasrelaxvar) );
3236 SCIPsetDebugMsg(set, "added proof-constraint to node %p (#%lld) in depth %d (nproofconss %d)\n",
3240 ? SCIPconflictstoreGetNDualInfProofs(conflictstore) : SCIPconflictstoreGetNDualBndProofs(conflictstore));
3258 assert(conflicttype == SCIP_CONFTYPE_BNDEXCEEDING || conflicttype == SCIP_CONFTYPE_ALTBNDPROOF);
3292 /* only one variable has a coefficient different to zero, we add this bound change instead of a constraint */
3306 SCIP_CALL( tightenSingleVar(conflict, set, stat, tree, blkmem, origprob, transprob, reopt, lp, \
3307 branchcand, eventqueue, cliquetable, vars[inds[0]], coefs[0], rhs, conflict->proofset->conflicttype,
3318 if( set->conf_prefinfproof && proofsetGetConftype(conflict->proofset) == SCIP_CONFTYPE_BNDEXCEEDING )
3335 SCIP_CALL( createAndAddProofcons(conflict, conflictstore, conflict->proofset, set, stat, origprob, transprob, \
3353 /* only one variable has a coefficient different to zero, we add this bound change instead of a constraint */
3374 SCIP_CALL( createAndAddProofcons(conflict, conflictstore, conflict->proofsets[i], set, stat, origprob, \
3422 /* try to derive global bound changes and shorten the conflictset by using implication and clique and variable bound
3435 SCIP_CALL( SCIPdebugCheckConflict(blkmem, set, tree->root, conflictset->bdchginfos, conflictset->relaxedbds, conflictset->nbdchginfos) );
3440 SCIP_CALL( detectImpliedBounds(set, transprob, conflictset, &nbdchgs, &nredvars, &redundant) );
3450 SCIP_CALL( SCIPdebugCheckConflict(blkmem, set, tree->root, conflictset->bdchginfos, conflictset->relaxedbds, conflictset->nbdchginfos) ); /*lint !e506 !e774*/
3454 SCIPsetDebugMsg(set, " -> conflict set removed %d redundant variables (old nvars %d, new nvars = %d)\n", nredvars, oldnbdchginfos, conflictset->nbdchginfos);
3455 SCIPsetDebugMsg(set, " -> conflict set led to %d global bound changes %s(cdpt:%d, fdpt:%d, confdpt:%d, len:%d):\n",
3456 nbdchgs, redundant ? "(conflict became redundant) " : "", SCIPtreeGetCurrentDepth(tree), SCIPtreeGetFocusDepth(tree),
3472 /* in case the conflict set contains only one bound change which is globally valid we apply that bound change
3473 * directly (except if we are in strong branching or diving - in this case a bound change would yield an unflushed LP
3476 * @note A bound change can only be applied if it is are related to the active node or if is a global bound
3477 * change. Bound changes which are related to any other node cannot be handled at point due to the internal
3492 /* for continuous variables, we can only use the relaxed version of the bounds negation: !(x <= u) -> x >= u */
3502 SCIP_CALL( SCIPnodeAddBoundchg(tree->path[conflictset->validdepth], blkmem, set, stat, transprob, origprob, tree,
3522 conflictset->nbdchginfos, conflictset->conflicttype, conflictset->usescutoffbound, *success, &result) );
3529 SCIPsetDebugMsg(set, " -> call conflict handler <%s> (prio=%d) to create conflict set with %d bounds returned result %d\n",
3530 SCIPconflicthdlrGetName(set->conflicthdlrs[h]), SCIPconflicthdlrGetPriority(set->conflicthdlrs[h]),
3537 /* TODO would be nice to still create a constraint?, if we can make sure that we the constraint does not survive a restart */
3543 /** adds the collected conflict constraints to the corresponding nodes; the best set->conf_maxconss conflict constraints
3544 * are added to the node of their validdepth; additionally (if not yet added, and if repropagation is activated), the
3545 * conflict constraint that triggers the earliest repropagation is added to the node of its validdepth
3583 /* calculate the maximal number of conflict sets to accept, and the maximal size of each accepted conflict set */
3594 SCIPsetDebugMsg(set, "flushing %d conflict sets at focus depth %d (maxconflictsets: %d, maxsize: %d)\n",
3615 assert(conflictset->repropdepth <= currentdepth || conflictset->repropdepth == INT_MAX); /* INT_MAX for dive/probing/strong */
3616 assert(conflictset->conflictdepth <= currentdepth || conflictset->conflictdepth == INT_MAX); /* INT_MAX for dive/probing/strong */
3626 /* if no conflict bounds exist, the node and its sub tree in the conflict set's valid depth can be
3634 SCIP_CALL( SCIPnodeCutoff(tree->path[conflictset->validdepth], set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
3639 /* if the conflict set is too long, use the conflict set only if it decreases the repropagation depth */
3642 SCIPsetDebugMsg(set, " -> conflict set is too long: %d > %d literals\n", conflictset->nbdchginfos, maxsize);
3643 if( set->conf_keepreprop && conflictset->repropagate && conflictset->repropdepth < repropdepth )
3654 SCIP_CALL( conflictAddConflictCons(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, \
3657 /* if no conflict bounds exist, the node and its sub tree in the conflict set's valid depth can be
3667 SCIP_CALL( SCIPnodeCutoff(tree->path[conflictset->validdepth], set, stat, tree, transprob, origprob, \
3675 SCIPsetDebugMsg(set, " -> conflict set %d/%d added (cdpt:%d, fdpt:%d, insert:%d, valid:%d, conf:%d, reprop:%d, len:%d):\n",
3676 nconflictsetsused+1, maxconflictsets, SCIPtreeGetCurrentDepth(tree), SCIPtreeGetFocusDepth(tree),
3677 conflictset->insertdepth, conflictset->validdepth, conflictset->conflictdepth, conflictset->repropdepth,
3691 /* reactivate propagation on the first node where one of the new conflict sets trigger a deduction */
3697 /* if the conflict constraint of smallest repropagation depth was not yet added, insert it now */
3705 SCIP_CALL( conflictAddConflictCons(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, \
3708 /* if no conflict bounds exist, the node and its sub tree in the conflict set's valid depth can be
3715 SCIPsetDebugMsg(set, " -> empty reprop conflict set in depth %d cuts off sub tree at depth %d\n",
3718 SCIP_CALL( SCIPnodeCutoff(tree->path[repropconflictset->validdepth], set, stat, tree, transprob, \
3725 SCIPsetDebugMsg(set, " -> additional reprop conflict set added (cdpt:%d, fdpt:%d, insert:%d, valid:%d, conf:%d, reprop:%d, len:%d):\n",
3727 repropconflictset->insertdepth, repropconflictset->validdepth, repropconflictset->conflictdepth,
3737 SCIPsetDebugMsg(set, "marked node %p in depth %d to be repropagated due to conflicts found in depth %d\n",
3775 /** returns the total number of literals in conflict constraints that were added to the problem */
3795 /** returns the total number of conflict constraints that were added globally to the problem */
3805 /** returns the total number of literals in conflict constraints that were added globally to the problem */
3835 /** returns the total number of literals in conflict constraints that were added locally to the problem */
3852 /** returns whether bound change has a valid reason that can be resolved in conflict analysis */
3885 if( !SCIPbdchgidxIsEarlierNonNull(SCIPbdchginfoGetIdx(bdchginfo1), SCIPbdchginfoGetIdx(bdchginfo2)) )
3891 /** return TRUE if conflict analysis is applicable; In case the function return FALSE there is no need to initialize the
3930 SCIP_CALL( SCIPpqueueCreate(&(*conflict)->bdchgqueue, set->mem_arraygrowinit, set->mem_arraygrowfac,
3932 SCIP_CALL( SCIPpqueueCreate(&(*conflict)->forcedbdchgqueue, set->mem_arraygrowinit, set->mem_arraygrowfac,
4075 /* increase the conflict counter, such that binary variables of new conflict set and new conflict queue are labeled
4079 if( conflict->count == 0 ) /* make sure, 0 is not a valid conflict counter (may happen due to integer overflow) */
4089 /* if the conflict score for the next conflict exceeds 1000.0, rescale all history conflict scores */
4113 /** marks bound to be present in the current conflict and returns whether a bound which is at least as tight was already
4139 /* the variable is already member of the conflict; hence check if the new bound is redundant */
4142 SCIPsetDebugMsg(set, "ignoring redundant bound change <%s> >= %g since a stronger lower bound exist <%s> >= %g\n",
4148 SCIPsetDebugMsg(set, "ignoring redundant bound change <%s> >= %g since this lower bound is already present\n", SCIPvarGetName(var), newbound);
4158 /* remember the lower bound and relaxed bound to allow only better/tighter lower bounds for that variables
4170 /* the variable is already member of the conflict; hence check if the new bound is redundant */
4173 SCIPsetDebugMsg(set, "ignoring redundant bound change <%s> <= %g since a stronger upper bound exist <%s> <= %g\n",
4179 SCIPsetDebugMsg(set, "ignoring redundant bound change <%s> <= %g since this upper bound is already present\n", SCIPvarGetName(var), newbound);
4189 /* remember the upper bound and relaxed bound to allow only better/tighter upper bounds for that variables
4218 assert(SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER || SCIPsetIsGE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
4219 assert(SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_UPPER || SCIPsetIsLE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
4221 SCIPsetDebugMsg(set, "putting bound change <%s> %s %g(%g) at depth %d to current conflict set\n",
4223 SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", SCIPbdchginfoGetNewbound(bdchginfo),
4226 /* mark the bound to be member of the conflict and check if a bound which is at least as tight is already member of
4247 /** returns whether the negation of the given bound change would lead to a globally valid literal */
4263 && ((boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsFeasGE(set, bound, SCIPvarGetUbGlobal(var)))
4264 || (boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsFeasLE(set, bound, SCIPvarGetLbGlobal(var)))));
4282 assert(SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER || SCIPsetIsGE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
4283 assert(SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_UPPER || SCIPsetIsLE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
4285 /* mark the bound to be member of the conflict and check if a bound which is at least as tight is already member of
4318 SCIP_BOUNDTYPE* boundtype, /**< pointer to type of bound that was changed: lower or upper bound */
4365 SCIPsetDebugMsg(set, " -> adding bound <%s> %s %.15g(%.15g) [status:%d, type:%d, depth:%d, pos:%d, reason:<%s>, info:%d] to candidates\n",
4374 : (SCIPbdchginfoGetInferProp(bdchginfo) != NULL ? SCIPpropGetName(SCIPbdchginfoGetInferProp(bdchginfo))
4376 SCIPbdchginfoGetChgtype(bdchginfo) != SCIP_BOUNDCHGTYPE_BRANCHING ? SCIPbdchginfoGetInferInfo(bdchginfo) : -1);
4379 * we even put bound changes without inference information on the queue in order to automatically
4388 assert(boundtype == SCIP_BOUNDTYPE_LOWER ? SCIPsetIsLE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)) : SCIPsetIsGE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
4391 assert(boundtype == SCIP_BOUNDTYPE_LOWER ? SCIPsetIsGT(set, relaxedbd, SCIPbdchginfoGetOldbound(bdchginfo)) : SCIPsetIsLT(set, relaxedbd, SCIPbdchginfoGetOldbound(bdchginfo)));
4400 SCIP_CALL( incVSIDS(var, blkmem, set, stat, boundtype, relaxedbd, set->conf_conflictgraphweight) );
4413 SCIP_BDCHGIDX* bdchgidx /**< bound change index (time stamp of bound change), or NULL for current time */
4453 /* if bound of variable was not changed (this means it is still the global bound), we can ignore the conflicting
4461 SCIP_CALL( conflictAddBound(conflict, blkmem, set, stat, var, boundtype, bdchginfo, SCIPbdchginfoGetNewbound(bdchginfo)) );
4474 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
4497 SCIPsetDebugMsg(set, "ignoring relaxed bound information since variable <%s> is multi-aggregated active\n", SCIPvarGetName(var));
4509 /* if bound of variable was not changed (this means it is still the global bound), we can ignore the conflicting
4518 /* get the position of the bound change information within the bound change array of the variable */
4522 /* if the relaxed bound should be ignored, set the relaxed bound to the bound given by the bdchgidx; that ensures
4536 /* due to numericis we compare the relaxed lower bound to the one present at the particular time point and take
4542 /* check if relaxed lower bound is smaller or equal to global lower bound; if so we can ignore the conflicting
4552 /* check if the old lower bound is greater than or equal to relaxed lower bound; if not we found the bound
4560 SCIPsetDebugMsg(set, "lower bound change %d oldbd=%.15g, newbd=%.15g, depth=%d, pos=%d, redundant=%u\n",
4565 /* if bound change is redundant (this means it now a global bound), we can ignore the conflicting bound */
4582 /* due to numericis we compare the relaxed upper bound to the one present at the particular time point and take
4588 /* check if relaxed upper bound is greater or equal to global upper bound; if so we can ignore the conflicting
4598 /* check if the old upper bound is smaller than or equal to the relaxed upper bound; if not we found the
4606 SCIPsetDebugMsg(set, "upper bound change %d oldbd=%.15g, newbd=%.15g, depth=%d, pos=%d, redundant=%u\n",
4611 /* if bound change is redundant (this means it now a global bound), we can ignore the conflicting bound */
4623 SCIP_CALL( conflictAddBound(conflict, blkmem, set, stat, var, boundtype, bdchginfo, relaxedbd) );
4628 /** checks if the given variable is already part of the current conflict set or queued for resolving with the same or
4636 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
4645 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED || SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR )
4660 SCIPsetDebugMsg(set, "already queued bound change <%s> >= %g\n", SCIPvarGetName(var), newbound);
4672 SCIPsetDebugMsg(set, "already queued bound change <%s> <= %g\n", SCIPvarGetName(var), newbound);
4688 /** returns the conflict lower bound if the variable is present in the current conflict set; otherwise the global lower
4705 /** returns the conflict upper bound if the variable is present in the current conflict set; otherwise the global upper
4743 /* mark the bound change to be no longer in the conflict (it will be either added again to the conflict set or
4784 SCIPdebugMessage("bound change info [%d:<%s> %s %g] is invaild -> pop it from the force queue\n", SCIPbdchginfoGetDepth(bdchginfo),
4803 SCIPdebugMessage("bound change info [%d:<%s> %s %g] is invaild -> pop it from the queue\n", SCIPbdchginfoGetDepth(bdchginfo),
4820 /** adds the current conflict set (extended by all remaining bound changes in the queue) to the pool of conflict sets */
4862 assert(0 <= conflict->conflictset->validdepth && conflict->conflictset->validdepth <= currentdepth);
4869 /* create a copy of the current conflict set, allocating memory for the additional elements of the queue */
4875 SCIPsetDebugMsg(set, "adding %d variables from the queue as temporary conflict variables\n", nbdchginfos);
4876 SCIP_CALL( conflictsetAddBounds(conflict, conflictset, blkmem, set, bdchginfos, nbdchginfos) );
4880 assert(conflictset->validdepth <= conflictset->insertdepth && conflictset->insertdepth <= currentdepth);
4881 SCIPsetDebugMsg(set, " -> conflict with %d literals found at depth %d is active in depth %d and valid in depth %d\n",
4887 if( (diving || conflictset->insertdepth < currentdepth) && conflictset->insertdepth <= focusdepth )
4889 /* if the conflict should not be located only in the subtree where it is useful, put it to its valid depth level */
4898 conflictset->bdchginfos, conflictset->relaxedbds, conflictset->nbdchginfos) ); /*lint !e506 !e774*/
4915 * current minimal valid depth level, because this depth level is the topmost level to add the conflict
4959 SCIPsetDebugMsg(set, "processing next conflicting bound (depth: %d, valid depth: %d, bdchgtype: %s [%s], vartype: %d): [<%s> %s %g(%g)]\n",
4975 SCIPsetDebugMsgPrint(set, " [%d:<%s> %s %g(%g)]", SCIPbdchginfoGetDepth(conflict->conflictset->bdchginfos[i]),
4977 SCIPbdchginfoGetBoundtype(conflict->conflictset->bdchginfos[i]) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
4978 SCIPbdchginfoGetNewbound(conflict->conflictset->bdchginfos[i]), conflict->conflictset->relaxedbds[i]);
4986 SCIPsetDebugMsgPrint(set, " [%d:<%s> %s %g(%g)]", SCIPbdchginfoGetDepth(info), SCIPvarGetName(SCIPbdchginfoGetVar(info)),
4987 bdchginfoIsInvalid(conflict, info) ? "<!>" : SCIPbdchginfoGetBoundtype(info) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
4996 SCIPsetDebugMsgPrint(set, " [%d:<%s> %s %g(%g)]", SCIPbdchginfoGetDepth(info), SCIPvarGetName(SCIPbdchginfoGetVar(info)),
4997 bdchginfoIsInvalid(conflict, info) ? "<!>" : SCIPbdchginfoGetBoundtype(info) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
5006 * current minimal valid depth level (which is initialized with the valid depth level of the initial
5007 * conflict set), because this depth level is the topmost level to add the conflict constraint to anyways
5022 /* resolve bound change by asking the constraint that infered the bound to put all bounds that were
5031 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",
5044 /* in case the inference variables is not an active variables, we need to transform the relaxed bound */
5053 || (SCIPvarGetStatus(infervar) == SCIP_VARSTATUS_MULTAGGR && SCIPvarGetMultaggrNVars(infervar) == 1));
5068 SCIP_CALL( SCIPconsResolvePropagation(infercons, set, infervar, inferinfo, inferboundtype, bdchgidx, relaxedbd, &result) );
5082 /* resolve bound change by asking the propagator that infered the bound to put all bounds that were
5091 SCIPsetDebugMsg(set, "resolving bound <%s> %s %g(%g) [status:%d, depth:%d, pos:%d]: <%s> %s %g [prop:<%s>, info:%d]\n",
5101 SCIP_CALL( SCIPpropResolvePropagation(inferprop, set, infervar, inferinfo, inferboundtype, bdchgidx, relaxedbd, &result) );
5122 /* in case the bound change was not resolved, the conflict queues should have the same size (contents) */
5129 /** if only one conflicting bound change of the last depth level was used, and if this can be resolved,
5130 * creates GRASP-like reconvergence conflict constraints in the conflict graph up to the branching variable of this
5145 int* nreconvliterals /**< pointer to store the number of literals generated reconvergence constraints */
5167 /* check, whether local constraints are allowed; however, don't generate reconvergence constraints that are only valid
5179 /* for each succeeding UIP pair of the last depth level, create one reconvergence constraint */
5181 while( uip != NULL && SCIPbdchginfoGetDepth(uip) == SCIPbdchginfoGetDepth(firstuip) && bdchginfoIsResolvable(uip) )
5193 SCIPsetDebugMsg(set, "creating reconvergence constraint for UIP <%s> %s %g in depth %d pos %d\n",
5194 SCIPvarGetName(SCIPbdchginfoGetVar(uip)), SCIPbdchginfoGetBoundtype(uip) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
5205 * for reconvergence constraints for continuous variables we can only use the "negation" !(x <= u) == (x >= u);
5206 * during conflict analysis, we treat a continuous bound "x >= u" in the conflict set as "x > u", and in the
5218 oppositeuipboundtype == SCIP_BOUNDTYPE_LOWER ? SCIP_REAL_MIN : SCIP_REAL_MAX, oppositeuipbound, &oppositeuip) );
5240 /* remove currently processed candidate and get next conflicting bound from the conflict candidate queue before
5241 * we remove the candidate we have to collect the relaxed bound since removing the candidate from the queue
5251 assert(nextbdchginfo == NULL || SCIPbdchginfoGetDepth(bdchginfo) >= SCIPbdchginfoGetDepth(nextbdchginfo)
5255 /* bound changes that are higher in the tree than the valid depth of the conflict can be ignored;
5299 assert(conflict->conflictset->nbdchginfos >= 1); /* starting UIP is already member of the conflict set */
5301 /* if this is the first variable of the conflict set besides the current starting UIP, it is the next
5318 /* get next conflicting bound from the conflict candidate queue (this does not need to be nextbdchginfo, because
5326 /* if only one propagation was resolved, the reconvergence constraint is already member of the constraint set
5339 conflict->conflictset->nbdchginfos, conflict->bdchgqueue, conflict->forcedbdchgqueue) ); /*lint !e506 !e774*/
5341 SCIPsetDebugMsg(set, "creating reconvergence constraint from UIP <%s> to UIP <%s> in depth %d with %d literals after %d resolutions\n",
5346 SCIP_CALL( conflictAddConflictset(conflict, blkmem, set, stat, tree, validdepth, diving, FALSE, &success, &nlits) );
5354 /* clear the conflict candidate queue and the conflict set (to make sure, oppositeuip is not referenced anymore) */
5366 /** analyzes conflicting bound changes that were added with calls to SCIPconflictAddBound() and
5367 * SCIPconflictAddRelaxedBound(), and on success, calls the conflict handlers to create a conflict constraint out of
5380 SCIP_Bool mustresolve, /**< should the conflict set only be used, if a resolution was applied? */
5382 int* nliterals, /**< pointer to store the number of literals in generated conflict constraints */
5384 int* nreconvliterals /**< pointer to store the number of literals generated reconvergence constraints */
5419 /* if we must resolve at least one bound change, find the first UIP at least in the last depth level */
5423 SCIPsetDebugMsg(set, "analyzing conflict with %d+%d conflict candidates and starting conflict set of size %d in depth %d (resolvedepth=%d)\n",
5432 /* check, whether local conflicts are allowed; however, don't generate conflict constraints that are only valid in the
5439 /* allocate temporary memory for storing first UIPs (in each depth level, at most two bound changes can be flagged
5453 NULL, conflict->conflictset->bdchginfos, conflict->conflictset->relaxedbds, conflict->conflictset->nbdchginfos, \
5475 assert(SCIPbdchginfoGetPos(bdchginfo) < (int)tree->path[bdchgdepth]->domchg->domchgbound.nboundchgs);
5476 assert(tree->path[bdchgdepth]->domchg->domchgbound.boundchgs[SCIPbdchginfoGetPos(bdchginfo)].var
5478 assert(tree->path[bdchgdepth]->domchg->domchgbound.boundchgs[SCIPbdchginfoGetPos(bdchginfo)].newbound
5481 ? SCIPvarGetLbGlobal(SCIPbdchginfoGetVar(bdchginfo)) : SCIPvarGetUbGlobal(SCIPbdchginfoGetVar(bdchginfo)))
5483 assert((SCIP_BOUNDTYPE)tree->path[bdchgdepth]->domchg->domchgbound.boundchgs[SCIPbdchginfoGetPos(bdchginfo)].boundtype