conflict_graphanalysis.c
Go to the documentation of this file.
38 * Given is a set of bound changes that are not allowed being applied simultaneously, because they
39 * render the current node infeasible (e.g. because a single constraint is infeasible in the these
40 * bounds, or because the LP relaxation is infeasible). The goal is to deduce a clause on variables
41 * -- a conflict clause -- representing the "reason" for this conflict, i.e., the branching decisions
42 * or the deductions (applied e.g. in domain propagation) that lead to the conflict. This clause can
45 * conflict was detected by a locally valid constraint. In this case, the resulting conflict clause
124 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
185 static SCIP_BDCHGINFO* confgraphcurrentbdchginfo = NULL; /**< currently resolved bound change */
201 SCIPdotWriteNode(confgraphfile, (int)(size_t) idptr, label, nodetype, fillcolor, bordercolor); /*lint !e571*/
204 SCIPgmlWriteNode(confgraphfile, (unsigned int)(size_t)idptr, label, nodetype, fillcolor, bordercolor); /*lint !e571*/
224 SCIPgmlWriteArc(confgraphfile, (unsigned int)(size_t)source, (unsigned int)(size_t)target, NULL, color); /*lint !e571*/
227 SCIPgmlWriteEdge(confgraphfile, (unsigned int)(size_t)source, (unsigned int)(size_t)target, NULL, color); /*lint !e571*/
232 /** creates a file to output the current conflict graph into; adds the conflict vertex to the graph */
292 /** adds a bound change node to the conflict graph and links it to the currently resolved bound change */
329 (void) SCIPsnprintf(label, SCIP_MAXSTRLEN, "%s %s %g\n[%s:%d]", SCIPvarGetName(SCIPbdchginfoGetVar(bdchginfo)),
366 (void) SCIPsnprintf(label, SCIP_MAXSTRLEN, "conf %d (%d)", confgraphnconflictsets, conflictset->validdepth);
367 confgraphWriteNode((void*)(size_t)confgraphnconflictsets, label, "rectangle", "#ff00ff", "#000000"); /*lint !e571*/
369 confgraphWriteEdge((void*)(size_t)confgraphnconflictsets, conflictset->bdchginfos[i], "#ff00ff"); /*lint !e571*/
376 /** resizes the arrays of the conflict set to be able to store at least num bound change entries */
393 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictset->bdchginfos, conflictset->bdchginfossize, newsize) );
394 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictset->relaxedbds, conflictset->bdchginfossize, newsize) );
395 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictset->sortvals, conflictset->bdchginfossize, newsize) );
426 SCIP_CALL( conflictsetEnsureBdchginfosMem(conflictset, blkmem, set, conflictset->nbdchginfos+1) );
428 /* insert the new bound change in the arrays sorted by increasing variable index and by bound type */
437 sortval = 2*idx + (int)boundtype; /* first sorting criteria: variable index, second criteria: boundtype */
439 /* insert new element into the sorted arrays; if an element exits with the same value insert the new element afterwards
441 * @todo check if it better (faster) to first search for the position O(log n) and compare the sort values and if
445 SCIPsortedvecInsertIntPtrReal(sortvals, (void**)bdchginfos, relaxedbds, sortval, (void*)bdchginfo, relaxedbd, &conflictset->nbdchginfos, &pos);
455 SCIPsortedvecDelPosIntPtrReal(sortvals, (void**)bdchginfos, relaxedbds, pos-1, &conflictset->nbdchginfos);
460 SCIPsortedvecDelPosIntPtrReal(sortvals, (void**)bdchginfos, relaxedbds, pos, &conflictset->nbdchginfos);
464 /* both bound change are equivalent; hence, keep the worse relaxed bound and remove one of them */
465 relaxedbds[pos-1] = boundtype == SCIP_BOUNDTYPE_LOWER ? MAX(relaxedbds[pos-1], relaxedbd) : MIN(relaxedbds[pos-1], relaxedbd);
466 SCIPsortedvecDelPosIntPtrReal(sortvals, (void**)bdchginfos, relaxedbds, pos, &conflictset->nbdchginfos);
512 * - if the branching rule operates on variables only, and if all branching variables up to a certain
513 * depth level are member of the conflict, the conflict constraint can only be violated in the subtree
514 * of the node at that depth, because in all other nodes, at least one of these branching variables
516 * - if there is at least one branching variable in a node, we assume, that this branching was performed
517 * on variables, and that the siblings of this node are disjunct w.r.t. the branching variables' fixings
551 depth = MIN(depth, currentdepth+1); /* put diving/probing/strong branching changes in this depth level */
556 while( conflictset->insertdepth < currentdepth && branchingincluded[conflictset->insertdepth+1] )
562 assert(conflictset->validdepth <= conflictset->insertdepth && conflictset->insertdepth <= currentdepth);
584 /* check, if all bound changes in conflictset2 are also present at least as tight in conflictset1;
585 * we can stop immediately, if more bound changes are remaining in conflictset2 than in conflictset1
587 for( i1 = 0, i2 = 0; i2 < conflictset2->nbdchginfos && conflictset1->nbdchginfos - i1 >= conflictset2->nbdchginfos - i2;
595 for( ; i1 < conflictset1->nbdchginfos && conflictset1->sortvals[i1] < sortval; ++i1 ) /*lint !e445*/
629 /** check conflict set for redundancy, other conflicts in the same conflict analysis could have led to global reductions
660 assert(SCIPbdchginfoGetBoundtype(bdchginfos[v]) == SCIP_BOUNDTYPE_LOWER || SCIPsetIsGE(set, relaxedbds[v], SCIPbdchginfoGetNewbound(bdchginfos[v])));
661 assert(SCIPbdchginfoGetBoundtype(bdchginfos[v]) == SCIP_BOUNDTYPE_UPPER || SCIPsetIsLE(set, relaxedbds[v], SCIPbdchginfoGetNewbound(bdchginfos[v])));
710 SCIP_Bool* redundant /**< did we found a global reduction on a conflict set variable, which makes this conflict redundant */
739 /* due to other conflict in the same conflict analysis, this conflict set might have become redundant */
760 /* due to multiple conflict sets for one conflict, it can happen, that we already have redundant information in the
777 SCIPsetDebugMsg(set, "remove redundant variable <%s> from conflict set\n", SCIPvarGetName(var));
789 SCIPsetDebugMsg(set, "trivially removed %d redundant of %d variables from conflictset (%p)\n", ntrivialredvars, conflictset->nbdchginfos, (void*)conflictset);
792 /* all variables where removed, the conflict cannot be fulfilled, i.e., we have an infeasibility proof */
797 if( conflictset->nbdchginfos > set->conf_maxvarsdetectimpliedbounds || conflictset->nbdchginfos == 1 )
821 assert(SCIPbdchginfoGetBoundtype(bdchginfos[v]) == SCIP_BOUNDTYPE_LOWER || SCIPsetIsGE(set, relaxedbds[v], SCIPbdchginfoGetNewbound(bdchginfos[v])));
822 assert(SCIPbdchginfoGetBoundtype(bdchginfos[v]) == SCIP_BOUNDTYPE_UPPER || SCIPsetIsLE(set, relaxedbds[v], SCIPbdchginfoGetNewbound(bdchginfos[v])));
824 /* for continuous variables, we can only use the relaxed version of the bounds negation: !(x <= u) -> x >= u */
850 /* the literal is satisfied in global bounds (may happen due to weak "negation" of continuous variables)
865 if( v == nbdchginfos && ((!set->conf_fullshortenconflict && nzeroimpls < 2) || (set->conf_fullshortenconflict && nzeroimpls < nbdchginfos)) )
874 SCIPsetDebugMsg(set, "checking for global reductions and redundant conflict variables(in %s) on conflict:\n", SCIPprobGetName(prob));
878 SCIPsetDebugMsgPrint(set, "%s %s %g", SCIPvarGetName(SCIPbdchginfoGetVar(bdchginfos[v])), (!boundtypes[v]) ? ">=" : "<=", bounds[v]);
891 SCIP_CALL( SCIPshrinkDisjunctiveVarSet(set->scip, vars, bounds, boundtypes, redundants, nbdchginfos, nredvars, \
898 SCIP_CALL( SCIPnodeCutoff(SCIPtreeGetRootNode(tree), set, stat, tree, prob, origprob, reopt, lp, blkmem) );
908 SCIPsetDebugMsg(set, "conflict set (%p) led to %d global bound reductions\n", (void*) conflictset, *nbdchgs);
915 SCIPsetDebugMsg(set, "conflict set (%p) is redundant because at least one global reduction, fulfills the conflict constraint\n", (void*)conflictset);
931 SCIPsetDebugMsg(set, "remove redundant variable <%s> from conflict set\n", SCIPvarGetName(SCIPbdchginfoGetVar(bdchginfos[v])));
945 SCIPsetDebugMsg(set, "removed %d redundant of %d variables from conflictset (%p)\n", (*nredvars), conflictset->nbdchginfos, (void*)conflictset);
1028 BMScopyMemoryArray((*targetconflictset)->bdchginfos, sourceconflictset->bdchginfos, sourceconflictset->nbdchginfos);
1029 BMScopyMemoryArray((*targetconflictset)->relaxedbds, sourceconflictset->relaxedbds, sourceconflictset->nbdchginfos);
1030 BMScopyMemoryArray((*targetconflictset)->sortvals, sourceconflictset->sortvals, sourceconflictset->nbdchginfos);
1053 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictset)->bdchginfos, (*conflictset)->bdchginfossize);
1054 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictset)->relaxedbds, (*conflictset)->bdchginfossize);
1055 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictset)->sortvals, (*conflictset)->bdchginfossize);
1090 return strcmp(SCIPconflicthdlrGetName((SCIP_CONFLICTHDLR*)elem1), SCIPconflicthdlrGetName((SCIP_CONFLICTHDLR*)elem2));
1103 SCIP_CALL( SCIPsetConflicthdlrPriority(scip, (SCIP_CONFLICTHDLR*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/
1120 SCIPsetDebugMsg(set, "including conflict handler %s in subscip %p\n", SCIPconflicthdlrGetName(conflicthdlr), (void*)set->scip);
1137 SCIP_DECL_CONFLICTCOPY((*conflictcopy)), /**< copy method of conflict handler or NULL if you don't want to copy your plugin into sub-SCIPs */
1141 SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)),/**< solving process initialization method of conflict handler */
1142 SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)),/**< solving process deinitialization method of conflict handler */
1143 SCIP_DECL_CONFLICTEXEC((*conflictexec)), /**< conflict processing method of conflict handler */
1176 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc, &(*conflicthdlr)->priority, TRUE, \
1177 priority, INT_MIN, INT_MAX, paramChgdConflicthdlrPriority, (SCIP_PARAMDATA*)(*conflicthdlr)) ); /*lint !e740*/
1191 SCIP_DECL_CONFLICTCOPY((*conflictcopy)), /**< copy method of conflict handler or NULL if you don't want to
1196 SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)),/**< solving process initialization method of conflict handler */
1197 SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)),/**< solving process deinitialization method of conflict handler */
1198 SCIP_DECL_CONFLICTEXEC((*conflictexec)), /**< conflict processing method of conflict handler */
1206 SCIP_CALL_FINALLY( doConflicthdlrCreate(conflicthdlr, set, messagehdlr, blkmem, name, desc, priority,
1207 conflictcopy, conflictfree, conflictinit, conflictexit, conflictinitsol, conflictexitsol, conflictexec,
1364 SCIP_Real* relaxedbds, /**< array with relaxed bounds which are efficient to create a valid conflict */
1384 SCIP_CALL( conflicthdlr->conflictexec(set->scip, conflicthdlr, node, validnode, bdchginfos, relaxedbds, nbdchginfos,
1385 conftype, usescutoffbound, set->conf_separate, (SCIPnodeGetDepth(validnode) > 0), set->conf_dynamic,
1473 SCIP_DECL_CONFLICTINITSOL((*conflictinitsol))/**< solving process initialization method of conflict handler */
1484 SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol))/**< solving process deinitialization method of conflict handler */
1548 SCIP_CONFLICTHDLR* conflicthdlr, /**< the conflict handler for which all clocks should be enabled or disabled */
1578 /** return TRUE if conflict analysis is applicable; In case the function return FALSE there is no need to initialize the
1596 /** resizes the array of the temporary bound change informations to be able to store at least num bound change entries */
1620 /** creates a temporary bound change information object that is destroyed after the conflict sets are flushed */
1682 branchdir = (boundtype == SCIP_BOUNDTYPE_LOWER ? SCIP_BRANCHDIR_UPWARDS : SCIP_BRANCHDIR_DOWNWARDS); /*lint !e641*/
1725 branchdir = (boundtype == SCIP_BOUNDTYPE_LOWER ? SCIP_BRANCHDIR_UPWARDS : SCIP_BRANCHDIR_DOWNWARDS); /*lint !e641*/
1727 SCIP_CALL( SCIPvarIncNActiveConflicts(var, blkmem, set, stat, branchdir, bound, (SCIP_Real)conflictlength) );
1774 /* try to derive global bound changes and shorten the conflictset by using implication and clique and variable bound
1787 SCIP_CALL( SCIPdebugCheckConflict(blkmem, set, tree->root, conflictset->bdchginfos, conflictset->relaxedbds, conflictset->nbdchginfos) );
1792 SCIP_CALL( detectImpliedBounds(set, transprob, stat, tree, blkmem, origprob, reopt, lp, conflictset, &nbdchgs, &nredvars, &redundant) );
1802 SCIP_CALL( SCIPdebugCheckConflict(blkmem, set, tree->root, conflictset->bdchginfos, conflictset->relaxedbds, conflictset->nbdchginfos) ); /*lint !e506 !e774*/
1806 SCIPsetDebugMsg(set, " -> conflict set removed %d redundant variables (old nvars %d, new nvars = %d)\n", nredvars, oldnbdchginfos, conflictset->nbdchginfos);
1807 SCIPsetDebugMsg(set, " -> conflict set led to %d global bound changes %s(cdpt:%d, fdpt:%d, confdpt:%d, len:%d):\n",
1808 nbdchgs, redundant ? "(conflict became redundant) " : "", SCIPtreeGetCurrentDepth(tree), SCIPtreeGetFocusDepth(tree),
1824 /* in case the conflict set contains only one bound change which is globally valid we apply that bound change
1825 * directly (except if we are in strong branching or diving - in this case a bound change would yield an unflushed LP
1828 * @note A bound change can only be applied if it is are related to the active node or if is a global bound
1829 * change. Bound changes which are related to any other node cannot be handled at point due to the internal
1844 /* for continuous variables, we can only use the relaxed version of the bounds negation: !(x <= u) -> x >= u */
1854 SCIP_CALL( SCIPnodeAddBoundchg(tree->path[conflictset->validdepth], blkmem, set, stat, transprob, origprob, tree,
1874 conflictset->nbdchginfos, conflictset->conflicttype, conflictset->usescutoffbound, *success, &result) );
1881 SCIPsetDebugMsg(set, " -> call conflict handler <%s> (prio=%d) to create conflict set with %d bounds returned result %d\n",
1882 SCIPconflicthdlrGetName(set->conflicthdlrs[h]), SCIPconflicthdlrGetPriority(set->conflicthdlrs[h]),
1889 /* TODO would be nice to still create a constraint?, if we can make sure that we the constraint does not survive a restart */
1912 /** adds the collected conflict constraints to the corresponding nodes; the best set->conf_maxconss conflict constraints
1913 * are added to the node of their validdepth; additionally (if not yet added, and if repropagation is activated), the
1914 * conflict constraint that triggers the earliest repropagation is added to the node of its validdepth
1952 /* calculate the maximal number of conflict sets to accept, and the maximal size of each accepted conflict set */
1963 SCIPsetDebugMsg(set, "flushing %d conflict sets at focus depth %d (maxconflictsets: %d, maxsize: %d)\n",
1984 assert(conflictset->repropdepth <= currentdepth || conflictset->repropdepth == INT_MAX); /* INT_MAX for dive/probing/strong */
1985 assert(conflictset->conflictdepth <= currentdepth || conflictset->conflictdepth == INT_MAX); /* INT_MAX for dive/probing/strong */
1995 /* if no conflict bounds exist, the node and its sub tree in the conflict set's valid depth can be
2003 SCIP_CALL( SCIPnodeCutoff(tree->path[conflictset->validdepth], set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
2008 /* if the conflict set is too long, use the conflict set only if it decreases the repropagation depth */
2011 SCIPsetDebugMsg(set, " -> conflict set is too long: %d > %d literals\n", conflictset->nbdchginfos, maxsize);
2012 if( set->conf_keepreprop && conflictset->repropagate && conflictset->repropdepth < repropdepth )
2023 SCIP_CALL( conflictAddConflictCons(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, \
2026 /* if no conflict bounds exist, the node and its sub tree in the conflict set's valid depth can be
2036 SCIP_CALL( SCIPnodeCutoff(tree->path[conflictset->validdepth], set, stat, tree, transprob, origprob, \
2044 SCIPsetDebugMsg(set, " -> conflict set %d/%d added (cdpt:%d, fdpt:%d, insert:%d, valid:%d, conf:%d, reprop:%d, len:%d):\n",
2045 nconflictsetsused+1, maxconflictsets, SCIPtreeGetCurrentDepth(tree), SCIPtreeGetFocusDepth(tree),
2046 conflictset->insertdepth, conflictset->validdepth, conflictset->conflictdepth, conflictset->repropdepth,
2060 /* reactivate propagation on the first node where one of the new conflict sets trigger a deduction */
2066 /* if the conflict constraint of smallest repropagation depth was not yet added, insert it now */
2074 SCIP_CALL( conflictAddConflictCons(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, \
2077 /* if no conflict bounds exist, the node and its sub tree in the conflict set's valid depth can be
2084 SCIPsetDebugMsg(set, " -> empty reprop conflict set in depth %d cuts off sub tree at depth %d\n",
2087 SCIP_CALL( SCIPnodeCutoff(tree->path[repropconflictset->validdepth], set, stat, tree, transprob, \
2094 SCIPsetDebugMsg(set, " -> additional reprop conflict set added (cdpt:%d, fdpt:%d, insert:%d, valid:%d, conf:%d, reprop:%d, len:%d):\n",
2096 repropconflictset->insertdepth, repropconflictset->validdepth, repropconflictset->conflictdepth,
2106 SCIPsetDebugMsg(set, "marked node %p in depth %d to be repropagated due to conflicts found in depth %d\n",
2149 /** inserts conflict set into sorted conflictsets array and deletes the conflict set pointer */
2173 /* if we apply repropagations, the conflict set should be inserted at most at its repropdepth */
2180 SCIPsetDebugMsg(set, "inserting conflict set (valid: %d, insert: %d, conf: %d, reprop: %d):\n",
2181 (*conflictset)->validdepth, (*conflictset)->insertdepth, (*conflictset)->conflictdepth, (*conflictset)->repropdepth);
2188 for( pos = 0; pos < conflict->nconflictsets && score < conflict->conflictsetscores[pos]; ++pos )
2199 /**@todo like in sepastore.c: calculate overlap between conflictsets -> large overlap reduces score */
2243 /** marks bound to be present in the current conflict and returns whether a bound which is at least as tight was already
2269 /* the variable is already member of the conflict; hence check if the new bound is redundant */
2272 SCIPsetDebugMsg(set, "ignoring redundant bound change <%s> >= %g since a stronger lower bound exist <%s> >= %g\n",
2278 SCIPsetDebugMsg(set, "ignoring redundant bound change <%s> >= %g since this lower bound is already present\n", SCIPvarGetName(var), newbound);
2288 /* remember the lower bound and relaxed bound to allow only better/tighter lower bounds for that variables
2300 /* the variable is already member of the conflict; hence check if the new bound is redundant */
2303 SCIPsetDebugMsg(set, "ignoring redundant bound change <%s> <= %g since a stronger upper bound exist <%s> <= %g\n",
2309 SCIPsetDebugMsg(set, "ignoring redundant bound change <%s> <= %g since this upper bound is already present\n", SCIPvarGetName(var), newbound);
2319 /* remember the upper bound and relaxed bound to allow only better/tighter upper bounds for that variables
2348 assert(SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER || SCIPsetIsGE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
2349 assert(SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_UPPER || SCIPsetIsLE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
2351 SCIPsetDebugMsg(set, "putting bound change <%s> %s %g(%g) at depth %d to current conflict set\n",
2353 SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", SCIPbdchginfoGetNewbound(bdchginfo),
2356 /* mark the bound to be member of the conflict and check if a bound which is at least as tight is already member of
2377 /** returns whether the negation of the given bound change would lead to a globally valid literal */
2393 && ((boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsFeasGE(set, bound, SCIPvarGetUbGlobal(var)))
2394 || (boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsFeasLE(set, bound, SCIPvarGetLbGlobal(var)))));
2412 assert(SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER || SCIPsetIsGE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
2413 assert(SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_UPPER || SCIPsetIsLE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
2415 /* mark the bound to be member of the conflict and check if a bound which is at least as tight is already member of
2460 SCIPsetDebugMsg(set, " -> adding bound <%s> %s %.15g(%.15g) [status:%d, type:%d, depth:%d, pos:%d, reason:<%s>, info:%d] to candidates\n",
2469 : (SCIPbdchginfoGetInferProp(bdchginfo) != NULL ? SCIPpropGetName(SCIPbdchginfoGetInferProp(bdchginfo))
2471 SCIPbdchginfoGetChgtype(bdchginfo) != SCIP_BOUNDCHGTYPE_BRANCHING ? SCIPbdchginfoGetInferInfo(bdchginfo) : -1);
2474 * we even put bound changes without inference information on the queue in order to automatically
2483 assert(boundtype == SCIP_BOUNDTYPE_LOWER ? SCIPsetIsLE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)) : SCIPsetIsGE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
2486 assert(boundtype == SCIP_BOUNDTYPE_LOWER ? SCIPsetIsGT(set, relaxedbd, SCIPbdchginfoGetOldbound(bdchginfo)) : SCIPsetIsLT(set, relaxedbd, SCIPbdchginfoGetOldbound(bdchginfo)));
2495 SCIP_CALL( incVSIDS(var, blkmem, set, stat, boundtype, relaxedbd, set->conf_conflictgraphweight) );
2500 /** applies conflict analysis starting with given bound changes, that could not be undone during previous
2511 int* lbchginfoposs, /**< positions of currently active lower bound change information in variables' arrays */
2512 int* ubchginfoposs, /**< positions of currently active upper bound change information in variables' arrays */
2514 int* nliterals, /**< pointer to store the number of literals in generated conflict constraints */
2516 int* nreconvliterals /**< pointer to store the number of literals generated reconvergence constraints */
2577 assert((lbchginfoposs[v] == var->nlbchginfos) != (ubchginfoposs[v] == var->nubchginfos)); /* only one can be tight in the dual! */
2578 assert(lbchginfoposs[v] < var->nlbchginfos || SCIPvarGetLbLP(var, set) > SCIPvarGetLbLocal(var));
2579 assert(ubchginfoposs[v] < var->nubchginfos || SCIPvarGetUbLP(var, set) < SCIPvarGetUbLocal(var));
2608 SCIP_CALL( incVSIDS(var, blkmem, set, stat, SCIPbdchginfoGetBoundtype(bdchginfo), relaxedbd, set->conf_conflictgraphweight) );
2617 &var->lbchginfos[lbchginfoposs[v]], SCIPbdchginfoGetNewbound(&var->lbchginfos[lbchginfoposs[v]])) );
2624 &var->ubchginfos[ubchginfoposs[v]], SCIPbdchginfoGetNewbound(&var->ubchginfos[ubchginfoposs[v]])) );
2633 SCIP_CALL( conflictAnalyze(conflict, blkmem, set, stat, prob, tree, diving, 0, FALSE, nconss, nliterals, \
2640 /** check if the bound change info (which is the potential next candidate which is queued) is valid for the current
2641 * conflict analysis; a bound change info can get invalid if after this one was added to the queue, a weaker bound
2642 * change was added to the queue (due the bound widening idea) which immediately makes this bound change redundant; due
2643 * to the priority we did not removed that bound change info since that cost O(log(n)); hence we have to skip/ignore it
2646 * The following situations can occur before for example the bound change info (x >= 3) is potentially popped from the
2649 * Postcondition: the reason why (x >= 3) was queued is that at this time point no lower bound of x was involved yet in
2650 * the current conflict or the lower bound which was involved until then was stronger, e.g., (x >= 2).
2652 * 1) during the time until (x >= 3) gets potentially popped no weaker lower bound was added to the queue, in that case
2653 * the conflictlbcount is valid and conflictlb is 3; that is (var->conflictlbcount == conflict->count &&
2656 * 2) a weaker bound change info gets queued (e.g., x >= 4); this bound change is popped before (x >= 3) since it has
2657 * higher priority (which is the time stamp of the bound change info and (x >= 4) has to be done after (x >= 3)
2660 * a) if (x >= 4) is popped and added to the conflict set the conflictlbcount is still valid and conflictlb is at
2661 * most 4; that is (var->conflictlbcount == conflict->count && var->conflictlb >= 4); it follows that any bound
2664 * b) if (x >= 4) is popped and resolved without introducing a new lower bound on x until (x >= 3) is a potentially
2668 * 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
2669 * pooped, the conflictlbcount indicates that bound change is currently present; that is (var->conflictlbcount ==
2670 * conflict->count); however the (x >= 3) only has be explained if conflictlb matches that one; that is
2686 /* the bound change info of a binary (domained) variable can never be invalid since the concepts of relaxed bounds
2692 /* check if the bdchginfo is invalid since a tight/weaker bound change was already explained */
2695 if( var->conflictlbcount != conflict->count || var->conflictlb != SCIPbdchginfoGetNewbound(bdchginfo) ) /*lint !e777*/
2705 if( var->conflictubcount != conflict->count || var->conflictub != SCIPbdchginfoGetNewbound(bdchginfo) ) /*lint !e777*/
2756 SCIP_CALL( conflictsetAddBound(conflictset, blkmem, set, bdchginfo, SCIPbdchginfoGetRelaxedBound(bdchginfo)) );
2760 SCIPsetDebugMsg(set, "-> bound change info [%d:<%s> %s %g] is invalid -> ignore it\n", SCIPbdchginfoGetDepth(bdchginfo),
2772 SCIP_CALL( conflictsetEnsureBdchginfosMem(conflictset, blkmem, set, confnbdchginfos + nbdchginfos) );
2797 sortval = 2*idx + (int)boundtype; /* first sorting criteria: variable index, second criteria: boundtype */
2810 SCIPsetDebugMsg(set, "-> bound change info [%d:<%s> %s %g] is invalid -> ignore it\n", SCIPbdchginfoGetDepth(bdchginfo),
2849 /* both bound change are equivalent; hence, keep the worse relaxed bound and remove one of them */
2850 confrelaxedbds[k] = (confsortvals[k] % 2 == 0) ? MAX(confrelaxedbds[k], confrelaxedbds[i]) : MIN(confrelaxedbds[k], confrelaxedbds[i]);
2872 /* the number of bound change infos cannot be decreased, it would mean that the conflict set was not merged
2905 /* mark the bound change to be no longer in the conflict (it will be either added again to the conflict set or
2946 SCIPdebugMessage("bound change info [%d:<%s> %s %g] is invalid -> pop it from the force queue\n", SCIPbdchginfoGetDepth(bdchginfo),
2965 SCIPdebugMessage("bound change info [%d:<%s> %s %g] is invalid -> pop it from the queue\n", SCIPbdchginfoGetDepth(bdchginfo),
2982 /** adds the current conflict set (extended by all remaining bound changes in the queue) to the pool of conflict sets */
3024 assert(0 <= conflict->conflictset->validdepth && conflict->conflictset->validdepth <= currentdepth);
3031 /* create a copy of the current conflict set, allocating memory for the additional elements of the queue */
3037 SCIPsetDebugMsg(set, "adding %d variables from the queue as temporary conflict variables\n", nbdchginfos);
3038 SCIP_CALL( conflictsetAddBounds(conflict, conflictset, blkmem, set, bdchginfos, nbdchginfos) );
3042 assert(conflictset->validdepth <= conflictset->insertdepth && conflictset->insertdepth <= currentdepth);
3043 SCIPsetDebugMsg(set, " -> conflict with %d literals found at depth %d is active in depth %d and valid in depth %d\n",
3049 if( (diving || conflictset->insertdepth < currentdepth) && conflictset->insertdepth <= focusdepth )
3051 /* if the conflict should not be located only in the subtree where it is useful, put it to its valid depth level */
3060 conflictset->bdchginfos, conflictset->relaxedbds, conflictset->nbdchginfos) ); /*lint !e506 !e774*/
3077 * current minimal valid depth level, because this depth level is the topmost level to add the conflict
3121 SCIPsetDebugMsg(set, "processing next conflicting bound (depth: %d, valid depth: %d, bdchgtype: %s [%s], vartype: %d): [<%s> %s %g(%g)]\n",
3137 SCIPsetDebugMsgPrint(set, " [%d:<%s> %s %g(%g)]", SCIPbdchginfoGetDepth(conflict->conflictset->bdchginfos[i]),
3139 SCIPbdchginfoGetBoundtype(conflict->conflictset->bdchginfos[i]) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
3140 SCIPbdchginfoGetNewbound(conflict->conflictset->bdchginfos[i]), conflict->conflictset->relaxedbds[i]);
3148 SCIPsetDebugMsgPrint(set, " [%d:<%s> %s %g(%g)]", SCIPbdchginfoGetDepth(info), SCIPvarGetName(SCIPbdchginfoGetVar(info)),
3149 bdchginfoIsInvalid(conflict, info) ? "<!>" : SCIPbdchginfoGetBoundtype(info) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
3158 SCIPsetDebugMsgPrint(set, " [%d:<%s> %s %g(%g)]", SCIPbdchginfoGetDepth(info), SCIPvarGetName(SCIPbdchginfoGetVar(info)),
3159 bdchginfoIsInvalid(conflict, info) ? "<!>" : SCIPbdchginfoGetBoundtype(info) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
3168 * current minimal valid depth level (which is initialized with the valid depth level of the initial
3169 * conflict set), because this depth level is the topmost level to add the conflict constraint to anyways
3184 /* resolve bound change by asking the constraint that inferred the bound to put all bounds that were
3193 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",
3206 /* in case the inference variables is not an active variables, we need to transform the relaxed bound */
3215 || (SCIPvarGetStatus(infervar) == SCIP_VARSTATUS_MULTAGGR && SCIPvarGetMultaggrNVars(infervar) == 1));
3230 SCIP_CALL( SCIPconsResolvePropagation(infercons, set, infervar, inferinfo, inferboundtype, bdchgidx, relaxedbd, &result) );
3244 /* resolve bound change by asking the propagator that inferred the bound to put all bounds that were
3253 SCIPsetDebugMsg(set, "resolving bound <%s> %s %g(%g) [status:%d, depth:%d, pos:%d]: <%s> %s %g [prop:<%s>, info:%d]\n",
3263 SCIP_CALL( SCIPpropResolvePropagation(inferprop, set, infervar, inferinfo, inferboundtype, bdchgidx, relaxedbd, &result) );
3284 /* in case the bound change was not resolved, the conflict queues should have the same size (contents) */
3332 /* increase the conflict counter, such that binary variables of new conflict set and new conflict queue are labeled
3336 if( conflict->count == 0 ) /* make sure, 0 is not a valid conflict counter (may happen due to integer overflow) */
3346 /* if the conflict score for the next conflict exceeds 1000.0, rescale all history conflict scores */
3375 SCIP_BOUNDTYPE* boundtype, /**< pointer to type of bound that was changed: lower or upper bound */
3405 /** returns whether bound change has a valid reason that can be resolved in conflict analysis */
3420 /** if only one conflicting bound change of the last depth level was used, and if this can be resolved,
3421 * creates GRASP-like reconvergence conflict constraints in the conflict graph up to the branching variable of this
3436 int* nreconvliterals /**< pointer to store the number of literals generated reconvergence constraints */
3458 /* check, whether local constraints are allowed; however, don't generate reconvergence constraints that are only valid
3470 /* for each succeeding UIP pair of the last depth level, create one reconvergence constraint */
3472 while( uip != NULL && SCIPbdchginfoGetDepth(uip) == SCIPbdchginfoGetDepth(firstuip) && bdchginfoIsResolvable(uip) )
3484 SCIPsetDebugMsg(set, "creating reconvergence constraint for UIP <%s> %s %g in depth %d pos %d\n",
3485 SCIPvarGetName(SCIPbdchginfoGetVar(uip)), SCIPbdchginfoGetBoundtype(uip) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
3496 * for reconvergence constraints for continuous variables we can only use the "negation" !(x <= u) == (x >= u);
3497 * during conflict analysis, we treat a continuous bound "x >= u" in the conflict set as "x > u", and in the
3509 oppositeuipboundtype == SCIP_BOUNDTYPE_LOWER ? SCIP_REAL_MIN : SCIP_REAL_MAX, oppositeuipbound, &oppositeuip) );
3531 /* remove currently processed candidate and get next conflicting bound from the conflict candidate queue before
3532 * we remove the candidate we have to collect the relaxed bound since removing the candidate from the queue
3542 assert(nextbdchginfo == NULL || SCIPbdchginfoGetDepth(bdchginfo) >= SCIPbdchginfoGetDepth(nextbdchginfo)
3546 /* bound changes that are higher in the tree than the valid depth of the conflict can be ignored;
3590 assert(conflict->conflictset->nbdchginfos >= 1); /* starting UIP is already member of the conflict set */
3592 /* if this is the first variable of the conflict set besides the current starting UIP, it is the next
3609 /* get next conflicting bound from the conflict candidate queue (this does not need to be nextbdchginfo, because
3617 /* if only one propagation was resolved, the reconvergence constraint is already member of the constraint set
3630 conflict->conflictset->nbdchginfos, conflict->bdchgqueue, conflict->forcedbdchgqueue) ); /*lint !e506 !e774*/
3632 SCIPsetDebugMsg(set, "creating reconvergence constraint from UIP <%s> to UIP <%s> in depth %d with %d literals after %d resolutions\n",
3637 SCIP_CALL( conflictAddConflictset(conflict, blkmem, set, stat, tree, validdepth, diving, FALSE, &success, &nlits) );
3645 /* clear the conflict candidate queue and the conflict set (to make sure, oppositeuip is not referenced anymore) */
3657 /** analyzes conflicting bound changes that were added with calls to SCIPconflictAddBound() and
3658 * SCIPconflictAddRelaxedBound(), and on success, calls the conflict handlers to create a conflict constraint out of
3670 SCIP_Bool mustresolve, /**< should the conflict set only be used, if a resolution was applied? */
3672 int* nliterals, /**< pointer to store the number of literals in generated conflict constraints */
3674 int* nreconvliterals /**< pointer to store the number of literals generated reconvergence constraints */
3709 /* if we must resolve at least one bound change, find the first UIP at least in the last depth level */
3713 SCIPsetDebugMsg(set, "analyzing conflict with %d+%d conflict candidates and starting conflict set of size %d in depth %d (resolvedepth=%d)\n",
3722 /* check, whether local conflicts are allowed; however, don't generate conflict constraints that are only valid in the
3729 /* allocate temporary memory for storing first UIPs (in each depth level, at most two bound changes can be flagged
3743 NULL, conflict->conflictset->bdchginfos, conflict->conflictset->relaxedbds, conflict->conflictset->nbdchginfos, \
3765 assert(SCIPbdchginfoGetPos(bdchginfo) < (int)tree->path[bdchgdepth]->domchg->domchgbound.nboundchgs);
3766 assert(tree->path[bdchgdepth]->domchg->domchgbound.boundchgs[SCIPbdchginfoGetPos(bdchginfo)].var
3768 assert(tree->path[bdchgdepth]->domchg->domchgbound.boundchgs[SCIPbdchginfoGetPos(bdchginfo)].newbound
3771 ? SCIPvarGetLbGlobal(SCIPbdchginfoGetVar(bdchginfo)) : SCIPvarGetUbGlobal(SCIPbdchginfoGetVar(bdchginfo)))
3773 assert((SCIP_BOUNDTYPE)tree->path[bdchgdepth]->domchg->domchgbound.boundchgs[SCIPbdchginfoGetPos(bdchginfo)].boundtype
3781 lastconsresoldepth = bdchgdepth; /* all intermediate depth levels consisted of only unresolved bound changes */
3782 else if( bdchgdepth < lastconsresoldepth && (set->conf_interconss == -1 || *nconss < set->conf_interconss) )
3788 SCIPsetDebugMsg(set, "creating intermediate conflictset after %d resolutions up to depth %d (valid at depth %d): %d conflict bounds, %d bounds in queue\n",
3792 SCIP_CALL( conflictAddConflictset(conflict, blkmem, set, stat, tree, validdepth, diving, TRUE, &success, &nlits) );
3803 /* remove currently processed candidate and get next conflicting bound from the conflict candidate queue before
3804 * we remove the candidate we have to collect the relaxed bound since removing the candidate from the queue
3813 assert(nextbdchginfo == NULL || SCIPbdchginfoGetDepth(bdchginfo) >= SCIPbdchginfoGetDepth(nextbdchginfo)
3816 /* we don't need to resolve bound changes that are already active in the valid depth of the current conflict set,
3817 * because the conflict set can only be added locally at the valid depth, and all bound changes applied in this
3818 * depth or earlier can be removed from the conflict constraint, since they are already applied in the constraint's
3882 bdchginfo, conflict->conflictset->bdchginfos, conflict->conflictset->relaxedbds, conflict->conflictset->nbdchginfos, \
3885 /* get next conflicting bound from the conflict candidate queue (this needs not to be nextbdchginfo, because
3903 SCIP_CALL( conflictAddConflictset(conflict, blkmem, set, stat, tree, validdepth, diving, TRUE, &success, &nlits) );
3973 * (SCIP_Real)(SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL))/(SCIP_Real)(SCIPcolGetNNonz(col));
3981 * (SCIP_Real)(SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL))/(SCIP_Real)(SCIPcolGetNNonz(col));
4020 /** after changing the global bound of a variable, the bdchginfos that are now redundant are replaced with
4021 * oldbound = newbound = global bound; if the current bdchginfo is of such kind, the bound is equal to the
4022 * global bound and we can ignore it by installing a -1 as the corresponding bound change info position
4038 == (var->lbchginfos[*lbchginfopos].oldbound == var->lbchginfos[*lbchginfopos].newbound)); /*lint !e777*/
4041 == (var->ubchginfos[*ubchginfopos].oldbound == var->ubchginfos[*ubchginfopos].newbound)); /*lint !e777*/
4043 if( *lbchginfopos >= 0 && *lbchginfopos < var->nlbchginfos && var->lbchginfos[*lbchginfopos].redundant )
4048 if( *ubchginfopos >= 0 && *ubchginfopos < var->nubchginfos && var->ubchginfos[*ubchginfopos].redundant )
4063 SCIP_BDCHGIDX* bdchgidx /**< bound change index (time stamp of bound change), or NULL for current time */
4103 /* if bound of variable was not changed (this means it is still the global bound), we can ignore the conflicting
4111 SCIP_CALL( conflictAddBound(conflict, blkmem, set, stat, var, boundtype, bdchginfo, SCIPbdchginfoGetNewbound(bdchginfo)) );
4124 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
4147 SCIPsetDebugMsg(set, "ignoring relaxed bound information since variable <%s> is multi-aggregated active\n", SCIPvarGetName(var));
4159 /* if bound of variable was not changed (this means it is still the global bound), we can ignore the conflicting
4168 /* get the position of the bound change information within the bound change array of the variable */
4172 /* if the relaxed bound should be ignored, set the relaxed bound to the bound given by the bdchgidx; that ensures
4186 /* due to numericis we compare the relaxed lower bound to the one present at the particular time point and take
4192 /* check if relaxed lower bound is smaller or equal to global lower bound; if so we can ignore the conflicting
4202 /* check if the old lower bound is greater than or equal to relaxed lower bound; if not we found the bound
4210 SCIPsetDebugMsg(set, "lower bound change %d oldbd=%.15g, newbd=%.15g, depth=%d, pos=%d, redundant=%u\n",
4215 /* if bound change is redundant (this means it now a global bound), we can ignore the conflicting bound */
4232 /* due to numericis we compare the relaxed upper bound to the one present at the particular time point and take
4238 /* check if relaxed upper bound is greater or equal to global upper bound; if so we can ignore the conflicting
4248 /* check if the old upper bound is smaller than or equal to the relaxed upper bound; if not we found the
4256 SCIPsetDebugMsg(set, "upper bound change %d oldbd=%.15g, newbd=%.15g, depth=%d, pos=%d, redundant=%u\n",
4261 /* if bound change is redundant (this means it now a global bound), we can ignore the conflicting bound */
4273 SCIP_CALL( conflictAddBound(conflict, blkmem, set, stat, var, boundtype, bdchginfo, relaxedbd) );
4278 /** checks if the given variable is already part of the current conflict set or queued for resolving with the same or
4286 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
4295 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED || SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR )
4310 SCIPsetDebugMsg(set, "already queued bound change <%s> >= %g\n", SCIPvarGetName(var), newbound);
4322 SCIPsetDebugMsg(set, "already queued bound change <%s> <= %g\n", SCIPvarGetName(var), newbound);
4346 SCIP_LPBDCHGS* relaxedlpbdchgs, /**< relaxed LP bound changes used for reset the LP bound change */
4347 SCIP_LPI* lpi /**< pointer to LPi to access infinity of LP solver; necessary to set correct value */
4378 assert((SCIPlpiIsInfinity(lpi, -oldlpbdchgs->bdchglbs[oldlpbdchgs->bdchgcolinds[c]]) && SCIPsetIsInfinity(set, -SCIPvarGetLbLP(var, set))) ||
4379 SCIPsetIsEQ(set, oldlpbdchgs->bdchglbs[oldlpbdchgs->bdchgcolinds[c]], SCIPvarGetLbLP(var, set)));
4380 assert((SCIPlpiIsInfinity(lpi, oldlpbdchgs->bdchgubs[oldlpbdchgs->bdchgcolinds[c]]) && SCIPsetIsInfinity(set, SCIPvarGetUbLP(var, set))) ||
4381 SCIPsetIsEQ(set, oldlpbdchgs->bdchgubs[oldlpbdchgs->bdchgcolinds[c]], SCIPvarGetUbLP(var, set)));
4407 relaxedlpbdchgs->bdchglbs[idx] = SCIPsetIsInfinity(set, -newlb) ? -SCIPlpiInfinity(lpi) : newlb;
4419 /** adds variable to candidate list, if the current best bound corresponding to the proof coefficient is local;
4420 * returns the array position in the candidate list, where the new candidate was inserted, or -1 if the
4423 * - prefer bound changes that have been applied deeper in the tree, to get a more global conflict
4424 * - prefer variables with small Farkas coefficient to get rid of as many bound changes as possible
4431 int lbchginfopos, /**< positions of currently active lower bound change information in variable's array */
4432 int ubchginfopos, /**< positions of currently active upper bound change information in variable's array */
4439 SCIP_Real** proofactdeltas, /**< pointer to proof activity increase array for undoing bound changes */
4468 /* in the infeasibility or dual bound proof, the variable's bound is chosen to maximize the proof's activity */
4471 assert(ubchginfopos >= 0); /* otherwise, undoBdchgsProof() should already have relaxed the local bound */
4493 assert(lbchginfopos >= 0); /* otherwise, undoBdchgsProof() should already have relaxed the local bound */
4520 score = calcBdchgScore(prooflhs, proofact, QUAD_TO_DBL(proofactdelta), proofcoef, depth, currentdepth, var, set);
4530 SCIP_CALL( ensureCandsSize(set, cands, candscores, newbounds, proofactdeltas, candssize, (*ncands)+1) );
4536 SCIPsetDebugMsg(set, " -> local <%s> %s %g, relax <%s> %s %g, proofcoef=%g, dpt=%d, resolve=%u, delta=%g, score=%g\n",
4568 int* lbchginfoposs, /**< positions of currently active lower bound change information in variables' arrays */
4569 int* ubchginfoposs, /**< positions of currently active upper bound change information in variables' arrays */
4570 SCIP_LPBDCHGS* oldlpbdchgs, /**< old LP bound changes used for reset the LP bound change, or NULL */
4571 SCIP_LPBDCHGS* relaxedlpbdchgs, /**< relaxed LP bound changes used for reset the LP bound change, or NULL */
4572 SCIP_Bool* resolve, /**< pointer to store whether the changed LP should be resolved again, or NULL */
4573 SCIP_LPI* lpi /**< pointer to LPi to access infinity of LP solver; necessary to set correct values */
4602 /* calculate the order in which the bound changes are tried to be undone, and relax all bounds if this doesn't
4618 /* after changing the global bound of a variable, the bdchginfos that are now redundant are replaced with
4619 * oldbound = newbound = global bound; if the current bdchginfo is of such kind, the bound is equal to the
4661 SCIP_CALL( addBdchg(set, var, curvarlbs[v], curvarubs[v], oldlpbdchgs, relaxedlpbdchgs, lpi) );
4668 prooflhs, (*proofact), &cands, &candscores, &newbounds, &proofactdeltas, &candssize, &ncands, 0) );
4682 assert((lbchginfoposs[SCIPvarGetProbindex(cands[i])] >= 0) != (ubchginfoposs[SCIPvarGetProbindex(cands[i])] >= 0));
4684 /* when relaxing a constraint we still need to stay infeasible; therefore we need to do the comparison in
4685 * feasibility tolerance because if 'prooflhs' is (feas-))equal to 'proofact + proofactdeltas[i]' it would mean
4694 SCIPsetDebugMsg(set, " -> relaxing variable <%s>[%g,%g] to [%g,%g]: proofcoef=%g, %g <= %g + %g\n",
4737 SCIP_CALL( addBdchg(set, cands[i], curvarlbs[v], curvarubs[v], oldlpbdchgs, relaxedlpbdchgs, lpi) );
4743 /* after changing the global bound of a variable, the bdchginfos that are now redundant are replaced with
4744 * oldbound = newbound = global bound; if the current bdchginfo is of such kind, the bound is equal to the
4752 SCIP_CALL( addCand(set, currentdepth, cands[i], lbchginfoposs[v], ubchginfoposs[v], proofcoefs[v],
4753 prooflhs, (*proofact), &cands, &candscores, &newbounds, &proofactdeltas, &candssize, &ncands, i+1) );
4778 int* lbchginfoposs, /**< positions of currently active lower bound change information in variables' arrays */
4779 int* ubchginfoposs, /**< positions of currently active upper bound change information in variables' arrays */
4780 SCIP_LPBDCHGS* oldlpbdchgs, /**< old LP bound changes used for reset the LP bound change, or NULL */
4781 SCIP_LPBDCHGS* relaxedlpbdchgs, /**< relaxed LP bound changes used for reset the LP bound change, or NULL */
4809 /* check, if the Farkas row is still violated (using current bounds and ignoring local rows) */
4813 SCIP_CALL( SCIPundoBdchgsProof(set, prob, currentdepth, farkascoefs, farkaslhs, farkasactivity, \
4814 curvarlbs, curvarubs, lbchginfoposs, ubchginfoposs, oldlpbdchgs, relaxedlpbdchgs, resolve, lpi) );
4818 /* resolving does not make sense: the old dual ray is still valid -> resolving will not change the solution */
4894 /** adds removal of row's side to side change arrays; finite sides are only replaced by near infinite sides, such
4929 SCIP_CALL( ensureSidechgsSize(set, sidechginds, sidechgoldlhss, sidechgoldrhss, sidechgnewlhss, sidechgnewrhss, \
4999 /** analyzes an LP exceeding the objective limit and undoes additional bound changes while staying beyond the
5010 int* lbchginfoposs, /**< positions of currently active lower bound change information in variables' arrays */
5011 int* ubchginfoposs, /**< positions of currently active upper bound change information in variables' arrays */
5012 SCIP_LPBDCHGS* oldlpbdchgs, /**< old LP bound changes used for reset the LP bound change, or NULL */
5013 SCIP_LPBDCHGS* relaxedlpbdchgs, /**< relaxed LP bound changes used for reset the LP bound change, or NULL */
5038 SCIPsetDebugMsg(set, "undoing bound changes in LP exceeding cutoff: cutoff=%g\n", lp->cutoffbound);
5047 SCIP_CALL( SCIPundoBdchgsProof(set, prob, currentdepth, dualcoefs, duallhs, dualactivity, curvarlbs, curvarubs, \
5085 int* lbchginfoposs, /**< positions of currently active lower bound change information in variables' arrays */
5086 int* ubchginfoposs, /**< positions of currently active upper bound change information in variables' arrays */
5088 SCIP_Bool marklpunsolved, /**< whether LP should be marked unsolved after analysis (needed for strong branching) */
5117 SCIP_CALL( undoBdchgsDualfarkas(set, transprob, lp, currentdepth, curvarlbs, curvarubs, lbchginfoposs, \
5118 ubchginfoposs, oldlpbdchgs, relaxedlpbdchgs, valid, &resolve, proofcoefs, *prooflhs, proofactivity) );
5123 SCIP_CALL( undoBdchgsDualsol(set, transprob, lp, currentdepth, curvarlbs, curvarubs, lbchginfoposs, ubchginfoposs, \
5186 SCIP_CALL( addSideRemoval(set, rows[r], lpiinfinity, &sidechginds, &sidechgoldlhss, &sidechgoldrhss,
5211 SCIPsetDebugMsg(set, "infeasible LP conflict analysis loop %d (changed col bounds: %d)\n", nloops, relaxedlpbdchgs->nbdchgs);
5217 SCIPsetDebugMsg(set, " -> applying %d bound changes to the LP solver\n", relaxedlpbdchgs->nbdchgs);
5247 SCIPsetDebugMsg(set, " -> resolved LP in %d iterations (total: %" SCIP_LONGINT_FORMAT ") (infeasible:%u)\n",
5281 /* the original LP exceeds the current cutoff bound, thus, we have not constructed the Farkas proof */
5282 SCIP_CALL( SCIPgetFarkasProof(set, transprob, lp, lpi, tree, farkasrow, proofactivity, &validdepth,
5300 SCIP_CALL( SCIPconflictAnalyzeDualProof(conflict, set, stat, blkmem, origprob, transprob, tree, reopt, lp, \
5306 /* todo: in theory, we could apply conflict graph analysis for locally valid proofs, too, but this needs to be implemented */
5332 SCIP_CALL( undoBdchgsDualfarkas(set, transprob, lp, currentdepth, curvarlbs, curvarubs, lbchginfoposs, \
5333 ubchginfoposs, oldlpbdchgs, relaxedlpbdchgs, valid, &resolve, proofcoefs, (*prooflhs), proofactivity) );
5351 SCIP_CALL( SCIPgetDualProof(set, transprob, lp, lpi, tree, proofrow, proofactivity, &validdepth,
5360 /* in contrast to the infeasible case we don't want to analyze the (probably identical) proof again. */
5381 SCIP_CALL( undoBdchgsDualsol(set, transprob, lp, currentdepth, curvarlbs, curvarubs, lbchginfoposs, \
5382 ubchginfoposs, oldlpbdchgs, relaxedlpbdchgs, valid, &resolve, proofcoefs, *prooflhs, proofactivity) );
5387 SCIPsetDebugMsg(set, " -> finished infeasible LP conflict analysis loop %d (iter: %d, nbdchgs: %d)\n",
5391 SCIPsetDebugMsg(set, "finished undoing bound changes after %d loops (valid=%u, nbdchgs: %d)\n",