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*/
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",
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) */
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",
5398 SCIP_CALL( SCIPlpiChgBounds(lpi, oldlpbdchgs->nbdchgs, oldlpbdchgs->bdchginds, oldlpbdchgs->bdchglbs, oldlpbdchgs->bdchgubs) );
5444/** analyzes conflicting bound changes that were added with calls to SCIPconflictAddBound(), and on success, calls the
5481 SCIPsetDebugMsg(set, "analyzing conflict after infeasible propagation in depth %d\n", SCIPtreeGetCurrentDepth(tree));
5489 SCIP_CALL( conflictAnalyze(conflict, blkmem, set, stat, prob, tree, FALSE, validdepth, TRUE, &nconss, &nliterals, \
void SCIPclockEnableOrDisable(SCIP_CLOCK *clck, SCIP_Bool enable)
Definition: clock.c:260
SCIP_RETCODE SCIPclockCreate(SCIP_CLOCK **clck, SCIP_CLOCKTYPE clocktype)
Definition: clock.c:170
internal methods for clocks and timing issues
internal methods for conflict analysis
SCIP_RETCODE SCIPconflictAnalyzeDualProof(SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_AGGRROW *proofrow, int validdepth, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, SCIP_Bool initialproof, SCIP_Bool *globalinfeasible, SCIP_Bool *success)
Definition: conflict_dualproofanalysis.c:1605
internal methods for dual proof conflict analysis
SCIP_RETCODE SCIPgetFarkasProof(SCIP_SET *set, SCIP_PROB *prob, SCIP_LP *lp, SCIP_LPI *lpi, SCIP_TREE *tree, SCIP_AGGRROW *farkasrow, SCIP_Real *farkasact, int *validdepth, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, SCIP_Bool *valid)
Definition: conflict_general.c:1161
SCIP_RETCODE SCIPgetDualProof(SCIP_SET *set, SCIP_PROB *transprob, SCIP_LP *lp, SCIP_LPI *lpi, SCIP_TREE *tree, SCIP_AGGRROW *farkasrow, SCIP_Real *farkasact, int *validdepth, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, SCIP_Bool *valid)
Definition: conflict_general.c:1341
void SCIPconflictsetFree(SCIP_CONFLICTSET **conflictset, BMS_BLKMEM *blkmem)
Definition: conflict_graphanalysis.c:1045
static SCIP_Bool conflictsetIsRedundant(SCIP_CONFLICTSET *conflictset1, SCIP_CONFLICTSET *conflictset2)
Definition: conflict_graphanalysis.c:569
static SCIP_RETCODE detectImpliedBounds(SCIP_SET *set, SCIP_PROB *prob, SCIP_STAT *stat, SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_PROB *origprob, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_CONFLICTSET *conflictset, int *nbdchgs, int *nredvars, SCIP_Bool *redundant)
Definition: conflict_graphanalysis.c:698
SCIP_RETCODE SCIPconflictFlushConss(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable)
Definition: conflict_graphanalysis.c:1916
static SCIP_RETCODE ensureSidechgsSize(SCIP_SET *set, int **sidechginds, SCIP_Real **sidechgoldlhss, SCIP_Real **sidechgoldrhss, SCIP_Real **sidechgnewlhss, SCIP_Real **sidechgnewrhss, int *sidechgssize, int num)
Definition: conflict_graphanalysis.c:4859
static SCIP_RETCODE conflictQueueBound(SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_BDCHGINFO *bdchginfo, SCIP_Real relaxedbd)
Definition: conflict_graphanalysis.c:2399
static SCIP_RETCODE undoBdchgsDualsol(SCIP_SET *set, SCIP_PROB *prob, SCIP_LP *lp, int currentdepth, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, int *lbchginfoposs, int *ubchginfoposs, SCIP_LPBDCHGS *oldlpbdchgs, SCIP_LPBDCHGS *relaxedlpbdchgs, SCIP_Bool *valid, SCIP_Bool *resolve, SCIP_Real *dualcoefs, SCIP_Real duallhs, SCIP_Real *dualactivity)
Definition: conflict_graphanalysis.c:5003
static void conflictClear(SCIP_CONFLICT *conflict)
Definition: conflict_graphanalysis.c:3293
void SCIPconflicthdlrEnableOrDisableClocks(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_Bool enable)
Definition: conflict_graphanalysis.c:1547
SCIP_RETCODE conflictCreateTmpBdchginfo(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_Real oldbound, SCIP_Real newbound, SCIP_BDCHGINFO **bdchginfo)
Definition: conflict_graphanalysis.c:1621
SCIP_RETCODE SCIPconflictAnalyzeRemainingBdchgs(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_TREE *tree, SCIP_Bool diving, int *lbchginfoposs, int *ubchginfoposs, int *nconss, int *nliterals, int *nreconvconss, int *nreconvliterals)
Definition: conflict_graphanalysis.c:2503
static SCIP_RETCODE conflictEnsureTmpbdchginfosMem(SCIP_CONFLICT *conflict, SCIP_SET *set, int num)
Definition: conflict_graphanalysis.c:1598
static SCIP_Bool isBoundchgUseless(SCIP_SET *set, SCIP_BDCHGINFO *bdchginfo)
Definition: conflict_graphanalysis.c:2379
SCIP_RETCODE SCIPconflicthdlrCreate(SCIP_CONFLICTHDLR **conflicthdlr, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int priority, SCIP_DECL_CONFLICTCOPY((*conflictcopy)), SCIP_DECL_CONFLICTFREE((*conflictfree)), SCIP_DECL_CONFLICTINIT((*conflictinit)), SCIP_DECL_CONFLICTEXIT((*conflictexit)), SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)), SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)), SCIP_DECL_CONFLICTEXEC((*conflictexec)), SCIP_CONFLICTHDLRDATA *conflicthdlrdata)
Definition: conflict_graphanalysis.c:1183
static void conflictsetCalcConflictDepth(SCIP_CONFLICTSET *conflictset)
Definition: conflict_graphanalysis.c:478
SCIP_RETCODE SCIPconflicthdlrExit(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set)
Definition: conflict_graphanalysis.c:1279
static SCIP_Bool bdchginfoIsInvalid(SCIP_CONFLICT *conflict, SCIP_BDCHGINFO *bdchginfo)
Definition: conflict_graphanalysis.c:2674
static SCIP_Real calcBdchgScore(SCIP_Real prooflhs, SCIP_Real proofact, SCIP_Real proofactdelta, SCIP_Real proofcoef, int depth, int currentdepth, SCIP_VAR *var, SCIP_SET *set)
Definition: conflict_graphanalysis.c:3946
void SCIPconflicthdlrSetInit(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_DECL_CONFLICTINIT((*conflictinit)))
Definition: conflict_graphanalysis.c:1449
int conflictCalcMaxsize(SCIP_SET *set, SCIP_PROB *prob)
Definition: conflict_graphanalysis.c:1896
void SCIPconflicthdlrSetPriority(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set, int priority)
Definition: conflict_graphanalysis.c:1523
SCIP_RETCODE SCIPconflictAddBound(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx)
Definition: conflict_graphanalysis.c:4056
static SCIP_RETCODE conflictAddConflictCons(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_CONFLICTSET *conflictset, int insertdepth, SCIP_Bool *success)
Definition: conflict_graphanalysis.c:1743
SCIP_RETCODE SCIPconflicthdlrFree(SCIP_CONFLICTHDLR **conflicthdlr, SCIP_SET *set)
Definition: conflict_graphanalysis.c:1214
SCIP_RETCODE SCIPconflictAnalyze(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_TREE *tree, int validdepth, SCIP_Bool *success)
Definition: conflict_graphanalysis.c:5448
static SCIP_RETCODE undoBdchgsDualfarkas(SCIP_SET *set, SCIP_PROB *prob, SCIP_LP *lp, int currentdepth, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, int *lbchginfoposs, int *ubchginfoposs, SCIP_LPBDCHGS *oldlpbdchgs, SCIP_LPBDCHGS *relaxedlpbdchgs, SCIP_Bool *valid, SCIP_Bool *resolve, SCIP_Real *farkascoefs, SCIP_Real farkaslhs, SCIP_Real *farkasactivity)
Definition: conflict_graphanalysis.c:4771
static SCIP_RETCODE addCand(SCIP_SET *set, int currentdepth, SCIP_VAR *var, int lbchginfopos, int ubchginfopos, SCIP_Real proofcoef, SCIP_Real prooflhs, SCIP_Real proofact, SCIP_VAR ***cands, SCIP_Real **candscores, SCIP_Real **newbounds, SCIP_Real **proofactdeltas, int *candssize, int *ncands, int firstcand)
Definition: conflict_graphanalysis.c:4427
static SCIP_RETCODE addBdchg(SCIP_SET *set, SCIP_VAR *var, SCIP_Real newlb, SCIP_Real newub, SCIP_LPBDCHGS *oldlpbdchgs, SCIP_LPBDCHGS *relaxedlpbdchgs, SCIP_LPI *lpi)
Definition: conflict_graphanalysis.c:4340
static SCIP_RETCODE conflictCreateReconvergenceConss(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_TREE *tree, SCIP_Bool diving, int validdepth, SCIP_BDCHGINFO *firstuip, int *nreconvconss, int *nreconvliterals)
Definition: conflict_graphanalysis.c:3425
SCIP_RETCODE SCIPconflicthdlrExitsol(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set)
Definition: conflict_graphanalysis.c:1334
SCIP_Bool SCIPconflictApplicable(SCIP_SET *set)
Definition: conflict_graphanalysis.c:1581
SCIP_RETCODE SCIPrunBoundHeuristic(SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_Real *proofcoefs, SCIP_Real *prooflhs, SCIP_Real *proofactivity, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, int *lbchginfoposs, int *ubchginfoposs, int *iterations, SCIP_Bool marklpunsolved, SCIP_Bool *dualproofsuccess, SCIP_Bool *valid)
Definition: conflict_graphanalysis.c:5069
static SCIP_RETCODE conflictResolveBound(SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_BDCHGINFO *bdchginfo, SCIP_Real relaxedbd, int validdepth, SCIP_Bool *resolved)
Definition: conflict_graphanalysis.c:3083
static void conflictsetClear(SCIP_CONFLICTSET *conflictset)
Definition: conflict_graphanalysis.c:971
SCIP_RETCODE SCIPconflictAddRelaxedBound(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd)
Definition: conflict_graphanalysis.c:4117
void SCIPconflicthdlrSetFree(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_DECL_CONFLICTFREE((*conflictfree)))
Definition: conflict_graphanalysis.c:1437
static SCIP_Real conflictsetCalcScore(SCIP_CONFLICTSET *conflictset, SCIP_SET *set)
Definition: conflict_graphanalysis.c:1064
void SCIPconflicthdlrSetExitsol(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)))
Definition: conflict_graphanalysis.c:1482
static SCIP_RETCODE conflictAddConflictBound(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_BDCHGINFO *bdchginfo, SCIP_Real relaxedbd)
Definition: conflict_graphanalysis.c:2336
static SCIP_RETCODE lpbdchgsCreate(SCIP_LPBDCHGS **lpbdchgs, SCIP_SET *set, int ncols)
Definition: conflict_graphanalysis.c:4832
static SCIP_RETCODE doConflicthdlrCreate(SCIP_CONFLICTHDLR **conflicthdlr, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int priority, SCIP_DECL_CONFLICTCOPY((*conflictcopy)), SCIP_DECL_CONFLICTFREE((*conflictfree)), SCIP_DECL_CONFLICTINIT((*conflictinit)), SCIP_DECL_CONFLICTEXIT((*conflictexit)), SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)), SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)), SCIP_DECL_CONFLICTEXEC((*conflictexec)), SCIP_CONFLICTHDLRDATA *conflicthdlrdata)
Definition: conflict_graphanalysis.c:1129
static SCIP_RETCODE conflictsetCopy(SCIP_CONFLICTSET **targetconflictset, BMS_BLKMEM *blkmem, SCIP_CONFLICTSET *sourceconflictset, int nadditionalelems)
Definition: conflict_graphanalysis.c:1009
static SCIP_RETCODE conflictsetAddBound(SCIP_CONFLICTSET *conflictset, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_BDCHGINFO *bdchginfo, SCIP_Real relaxedbd)
Definition: conflict_graphanalysis.c:405
static SCIP_Bool conflictMarkBoundCheckPresence(SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_BDCHGINFO *bdchginfo, SCIP_Real relaxedbd)
Definition: conflict_graphanalysis.c:2247
SCIP_RETCODE SCIPconflicthdlrCopyInclude(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set)
Definition: conflict_graphanalysis.c:1109
void SCIPconflicthdlrSetExit(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_DECL_CONFLICTEXIT((*conflictexit)))
Definition: conflict_graphanalysis.c:1460
SCIP_RETCODE SCIPundoBdchgsProof(SCIP_SET *set, SCIP_PROB *prob, int currentdepth, SCIP_Real *proofcoefs, SCIP_Real prooflhs, SCIP_Real *proofact, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, int *lbchginfoposs, int *ubchginfoposs, SCIP_LPBDCHGS *oldlpbdchgs, SCIP_LPBDCHGS *relaxedlpbdchgs, SCIP_Bool *resolve, SCIP_LPI *lpi)
Definition: conflict_graphanalysis.c:4559
static SCIP_RETCODE conflictsetAddBounds(SCIP_CONFLICT *conflict, SCIP_CONFLICTSET *conflictset, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_BDCHGINFO **bdchginfos, int nbdchginfos)
Definition: conflict_graphanalysis.c:2717
static SCIP_RETCODE addSideRemoval(SCIP_SET *set, SCIP_ROW *row, SCIP_Real lpiinfinity, int **sidechginds, SCIP_Real **sidechgoldlhss, SCIP_Real **sidechgoldrhss, SCIP_Real **sidechgnewlhss, SCIP_Real **sidechgnewrhss, int *sidechgssize, int *nsidechgs)
Definition: conflict_graphanalysis.c:4898
static SCIP_RETCODE convertToActiveVar(SCIP_VAR **var, SCIP_SET *set, SCIP_BOUNDTYPE *boundtype, SCIP_Real *bound)
Definition: conflict_graphanalysis.c:3372
static SCIP_RETCODE incVSIDS(SCIP_VAR *var, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_BOUNDTYPE boundtype, SCIP_Real value, SCIP_Real weight)
Definition: conflict_graphanalysis.c:1661
static SCIP_Bool bdchginfoIsResolvable(SCIP_BDCHGINFO *bdchginfo)
Definition: conflict_graphanalysis.c:3407
SCIP_RETCODE conflictAnalyze(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_TREE *tree, SCIP_Bool diving, int validdepth, SCIP_Bool mustresolve, int *nconss, int *nliterals, int *nreconvconss, int *nreconvliterals)
Definition: conflict_graphanalysis.c:3661
void SCIPconflicthdlrSetCopy(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_DECL_CONFLICTCOPY((*conflictcopy)))
Definition: conflict_graphanalysis.c:1426
static SCIP_Bool checkRedundancy(SCIP_SET *set, SCIP_CONFLICTSET *conflictset)
Definition: conflict_graphanalysis.c:633
static void lpbdchgsReset(SCIP_LPBDCHGS *lpbdchgs, int ncols)
Definition: conflict_graphanalysis.c:4972
SCIP_RETCODE SCIPconflictIsVarUsed(SCIP_CONFLICT *conflict, SCIP_VAR *var, SCIP_SET *set, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool *used)
Definition: conflict_graphanalysis.c:4281
static SCIP_RETCODE conflictAddBound(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGINFO *bdchginfo, SCIP_Real relaxedbd)
Definition: conflict_graphanalysis.c:2445
SCIP_RETCODE SCIPconflictsetCreate(SCIP_CONFLICTSET **conflictset, BMS_BLKMEM *blkmem)
Definition: conflict_graphanalysis.c:989
static SCIP_RETCODE conflictsetCalcInsertDepth(SCIP_CONFLICTSET *conflictset, SCIP_SET *set, SCIP_TREE *tree)
Definition: conflict_graphanalysis.c:522
static SCIP_BDCHGINFO * conflictRemoveCand(SCIP_CONFLICT *conflict)
Definition: conflict_graphanalysis.c:2886
static SCIP_DECL_PARAMCHGD(paramChgdConflicthdlrPriority)
Definition: conflict_graphanalysis.c:1095
static SCIP_RETCODE conflictsetEnsureBdchginfosMem(SCIP_CONFLICTSET *conflictset, BMS_BLKMEM *blkmem, SCIP_SET *set, int num)
Definition: conflict_graphanalysis.c:378
static SCIP_BDCHGINFO * conflictFirstCand(SCIP_CONFLICT *conflict)
Definition: conflict_graphanalysis.c:2930
SCIP_RETCODE SCIPconflictInit(SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_CONFTYPE conftype, SCIP_Bool usescutoffbound)
Definition: conflict_graphanalysis.c:3305
static SCIP_RETCODE ensureCandsSize(SCIP_SET *set, SCIP_VAR ***cands, SCIP_Real **candscores, SCIP_Real **newbounds, SCIP_Real **proofactdeltas, int *candssize, int num)
Definition: conflict_graphanalysis.c:3991
SCIP_RETCODE SCIPconflicthdlrExec(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set, SCIP_NODE *node, SCIP_NODE *validnode, SCIP_BDCHGINFO **bdchginfos, SCIP_Real *relaxedbds, int nbdchginfos, SCIP_CONFTYPE conftype, SCIP_Bool usescutoffbound, SCIP_Bool resolved, SCIP_RESULT *result)
Definition: conflict_graphanalysis.c:1358
SCIP_RETCODE SCIPconflicthdlrInitsol(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set)
Definition: conflict_graphanalysis.c:1310
static void skipRedundantBdchginfos(SCIP_VAR *var, int *lbchginfopos, int *ubchginfopos)
Definition: conflict_graphanalysis.c:4025
static SCIP_RETCODE conflictInsertConflictset(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_CONFLICTSET **conflictset)
Definition: conflict_graphanalysis.c:2151
static SCIP_RETCODE conflictEnsureConflictsetsMem(SCIP_CONFLICT *conflict, SCIP_SET *set, int num)
Definition: conflict_graphanalysis.c:2126
static void lpbdchgsFree(SCIP_LPBDCHGS **lpbdchgs, SCIP_SET *set)
Definition: conflict_graphanalysis.c:4985
SCIP_RETCODE SCIPconflicthdlrInit(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set)
Definition: conflict_graphanalysis.c:1242
static SCIP_RETCODE conflictAddConflictset(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, int validdepth, SCIP_Bool diving, SCIP_Bool repropagate, SCIP_Bool *success, int *nliterals)
Definition: conflict_graphanalysis.c:2984
static void conflictFreeTmpBdchginfos(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem)
Definition: conflict_graphanalysis.c:1645
void SCIPconflicthdlrSetInitsol(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)))
Definition: conflict_graphanalysis.c:1471
static SCIP_RETCODE updateStatistics(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_CONFLICTSET *conflictset, int insertdepth)
Definition: conflict_graphanalysis.c:1692
methods and datastructures for conflict analysis
SCIP_RETCODE SCIPconsResolvePropagation(SCIP_CONS *cons, SCIP_SET *set, SCIP_VAR *infervar, int inferinfo, SCIP_BOUNDTYPE inferboundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd, SCIP_RESULT *result)
Definition: cons.c:7318
internal methods for constraints and constraint handlers
Constraint handler for linear constraints in their most general form, .
methods for the aggregation rows
#define SCIPdebugCheckConflict(blkmem, set, node, bdchginfos, relaxedbds, nliterals)
Definition: debug.h:295
#define SCIPdebugCheckConflictFrontier(blkmem, set, node, bdchginfo, bdchginfos, relaxedbds, nliterals, bdchgqueue, forcedbdchgqueue)
Definition: debug.h:296
void SCIPdotWriteArc(FILE *file, int source, int target, const char *color)
Definition: misc.c:736
void SCIPgmlWriteNode(FILE *file, unsigned int id, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor)
Definition: misc.c:497
void SCIPdotWriteNode(FILE *file, int node, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor)
Definition: misc.c:721
void SCIPgmlWriteEdge(FILE *file, unsigned int source, unsigned int target, const char *label, const char *color)
Definition: misc.c:595
void SCIPgmlWriteArc(FILE *file, unsigned int source, unsigned int target, const char *label, const char *color)
Definition: misc.c:639
SCIP_RETCODE SCIPlpiChgSides(SCIP_LPI *lpi, int nrows, const int *ind, const SCIP_Real *lhs, const SCIP_Real *rhs)
Definition: lpi_clp.cpp:1167
SCIP_Bool SCIPlpiIsInfinity(SCIP_LPI *lpi, SCIP_Real val)
Definition: lpi_clp.cpp:3931
SCIP_RETCODE SCIPlpiSetRealpar(SCIP_LPI *lpi, SCIP_LPPARAM type, SCIP_Real dval)
Definition: lpi_clp.cpp:3833
SCIP_RETCODE SCIPlpiGetObjval(SCIP_LPI *lpi, SCIP_Real *objval)
Definition: lpi_clp.cpp:2766
SCIP_RETCODE SCIPlpiChgBounds(SCIP_LPI *lpi, int ncols, const int *ind, const SCIP_Real *lb, const SCIP_Real *ub)
Definition: lpi_clp.cpp:1084
SCIP_RETCODE SCIPlpiSetIntpar(SCIP_LPI *lpi, SCIP_LPPARAM type, int ival)
Definition: lpi_clp.cpp:3692
SCIP_Bool SCIPlpiIsPrimalInfeasible(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2502
SCIP_RETCODE SCIPlpiGetIterations(SCIP_LPI *lpi, int *iterations)
Definition: lpi_clp.cpp:2921
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1394
SCIP_BOUNDTYPE SCIPboundtypeOpposite(SCIP_BOUNDTYPE boundtype)
Definition: lp.c:17203
SCIP_CONFLICTHDLRDATA * SCIPconflicthdlrGetData(SCIP_CONFLICTHDLR *conflicthdlr)
Definition: conflict_graphanalysis.c:1405
SCIP_DECL_SORTPTRCOMP(SCIPconflicthdlrComp)
Definition: conflict_graphanalysis.c:1082
int SCIPconflicthdlrGetPriority(SCIP_CONFLICTHDLR *conflicthdlr)
Definition: conflict_graphanalysis.c:1513
const char * SCIPconflicthdlrGetName(SCIP_CONFLICTHDLR *conflicthdlr)
Definition: conflict_graphanalysis.c:1493
void SCIPconflicthdlrSetData(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_CONFLICTHDLRDATA *conflicthdlrdata)
Definition: conflict_graphanalysis.c:1415
SCIP_Bool SCIPconflicthdlrIsInitialized(SCIP_CONFLICTHDLR *conflicthdlr)
Definition: conflict_graphanalysis.c:1537
SCIP_Real SCIPconflicthdlrGetTime(SCIP_CONFLICTHDLR *conflicthdlr)
Definition: conflict_graphanalysis.c:1569
SCIP_Real SCIPconflicthdlrGetSetupTime(SCIP_CONFLICTHDLR *conflicthdlr)
Definition: conflict_graphanalysis.c:1559
const char * SCIPconflicthdlrGetDesc(SCIP_CONFLICTHDLR *conflicthdlr)
Definition: conflict_graphanalysis.c:1503
SCIP_RETCODE SCIPsetConflicthdlrPriority(SCIP *scip, SCIP_CONFLICTHDLR *conflicthdlr, int priority)
Definition: scip_conflict.c:273
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:1723
static INLINE SCIP_Real SCIPaggrRowGetProbvarValue(SCIP_AGGRROW *aggrrow, int probindex)
Definition: cuts.h:251
SCIP_RETCODE SCIPshrinkDisjunctiveVarSet(SCIP *scip, SCIP_VAR **vars, SCIP_Real *bounds, SCIP_Bool *boundtypes, SCIP_Bool *redundants, int nvars, int *nredvars, int *nglobalred, SCIP_Bool *setredundant, SCIP_Bool *glbinfeas, SCIP_Bool fullshortening)
Definition: presolve.c:995
SCIP_Real SCIPgetVarBdAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2264
SCIP_Bool SCIPbdchginfoIsRedundant(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18808
SCIP_Bool SCIPbdchgidxIsEarlier(SCIP_BDCHGIDX *bdchgidx1, SCIP_BDCHGIDX *bdchgidx2)
Definition: var.c:18640
SCIP_BDCHGIDX * SCIPbdchginfoGetIdx(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18730
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3353
SCIP_PROP * SCIPbdchginfoGetInferProp(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18764
int SCIPbdchginfoGetInferInfo(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18775
SCIP_CONS * SCIPbdchginfoGetInferCons(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18752
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2128
SCIP_Real SCIPbdchginfoGetOldbound(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18660
SCIP_BOUNDTYPE SCIPbdchginfoGetInferBoundtype(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18787
SCIP_BDCHGINFO * SCIPvarGetBdchgInfo(SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16689
SCIP_Bool SCIPbdchginfoIsTighter(SCIP_BDCHGINFO *bdchginfo1, SCIP_BDCHGINFO *bdchginfo2)
Definition: var.c:18833
SCIP_BOUNDCHGTYPE SCIPbdchginfoGetChgtype(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18690
SCIP_VAR * SCIPbdchginfoGetInferVar(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18740
SCIP_Bool SCIPbdchginfoHasInferenceReason(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18819
SCIP_BDCHGINFO * SCIPvarGetBdchgInfoLb(SCIP_VAR *var, int pos)
Definition: var.c:18478
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1992
SCIP_BOUNDTYPE SCIPbdchginfoGetBoundtype(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18700
SCIP_Real SCIPbdchginfoGetNewbound(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18670
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3295
SCIP_BDCHGINFO * SCIPvarGetBdchgInfoUb(SCIP_VAR *var, int pos)
Definition: var.c:18498
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
Definition: var.c:17870
void SCIPsortedvecInsertIntPtrReal(int *intarray, void **ptrarray, SCIP_Real *realarray, int keyval, void *field1val, SCIP_Real field2val, int *len, int *pos)
void SCIPsortIntPtrReal(int *intarray, void **ptrarray, SCIP_Real *realarray, int len)
void SCIPsortLongPtrRealRealBool(SCIP_Longint *longarray, void **ptrarray, SCIP_Real *realarray, SCIP_Real *realarray2, SCIP_Bool *boolarray, int len)
void SCIPsortedvecDelPosIntPtrReal(int *intarray, void **ptrarray, SCIP_Real *realarray, int pos, int *len)
void SCIPhistoryIncNActiveConflicts(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real length)
Definition: history.c:549
void SCIPhistoryScaleVSIDS(SCIP_HISTORY *history, SCIP_Real scalar)
Definition: history.c:524
void SCIPhistoryIncVSIDS(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
Definition: history.c:510
internal methods for branching and inference history
internal methods for LP management
interface methods for specific LP solvers
#define BMSfreeBlockMemoryArrayNull(mem, ptr, num)
Definition: memory.h:468
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition: memory.h:458
Definition: objbenders.h:44
methods commonly used for presolving
SCIP_Bool SCIPprobAllColsInLP(SCIP_PROB *prob, SCIP_SET *set, SCIP_LP *lp)
Definition: prob.c:2350
internal methods for storing and manipulating the main problem
SCIP_RETCODE SCIPpropResolvePropagation(SCIP_PROP *prop, SCIP_SET *set, SCIP_VAR *infervar, int inferinfo, SCIP_BOUNDTYPE inferboundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd, SCIP_RESULT *result)
Definition: prop.c:737
internal methods for propagators
public methods for conflict analysis handlers
public methods for managing constraints
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for handling parameter settings
public methods for propagators
public methods for branch and bound tree
public methods for problem variables
public methods for conflict handler plugins and conflict analysis
public methods for constraint handler plugins and constraints
public methods for memory management
public methods for message handling
public methods for solutions
public methods for SCIP variables
SCIP_RETCODE SCIPsetAddIntParam(SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: set.c:2984
SCIP_Bool SCIPsetIsGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6293
SCIP_Bool SCIPsetIsFeasGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6663
SCIP_Bool SCIPsetIsFeasLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6641
SCIP_Bool SCIPsetIsFeasEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6597
SCIP_Bool SCIPsetIsLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6257
SCIP_Bool SCIPsetIsEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6221
SCIP_Bool SCIPsetIsFeasLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6619
SCIP_Bool SCIPsetIsLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6239
SCIP_Bool SCIPsetIsGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6275
SCIP_Bool SCIPsetIsFeasGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6685
internal methods for global SCIP settings
#define SCIPsetAllocCleanBufferArray(set, ptr, num)
Definition: set.h:1759
internal methods for storing primal CIP solutions
Definition: struct_cuts.h:41
Definition: struct_var.h:109
Definition: struct_var.h:116
Definition: struct_branch.h:47
Definition: struct_implics.h:98
Definition: struct_lp.h:136
Definition: struct_conflict.h:69
Definition: struct_conflict.h:114
Definition: struct_conflict.h:50
SCIP_CONFLICTHDLRDATA * conflicthdlrdata
Definition: struct_conflict.h:60
Definition: struct_cons.h:47
Definition: struct_event.h:224
Definition: struct_conflict.h:103
Definition: lpi_clp.cpp:105
Definition: struct_lp.h:270
Definition: struct_message.h:46
Definition: struct_tree.h:142
Definition: struct_prob.h:49
Definition: struct_prop.h:47
Definition: struct_reopt.h:140
Definition: struct_lp.h:202
Definition: struct_set.h:74
Definition: struct_stat.h:60
Definition: struct_tree.h:185
Definition: struct_var.h:208
datastructures for conflict analysis
data structures for LP management
datastructures for storing and manipulating the main problem
datastructures for global SCIP settings
datastructures for problem statistics
data structures for branch and bound tree
datastructures for problem variables
Definition: heur_padm.c:135
SCIP_RETCODE SCIPnodeCutoff(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_REOPT *reopt, SCIP_LP *lp, BMS_BLKMEM *blkmem)
Definition: tree.c:1234
void SCIPnodePropagateAgain(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree)
Definition: tree.c:1294
int SCIPtreeGetEffectiveRootDepth(SCIP_TREE *tree)
Definition: tree.c:8491
SCIP_RETCODE SCIPnodeAddBoundchg(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var, SCIP_Real newbound, SCIP_BOUNDTYPE boundtype, SCIP_Bool probingchange)
Definition: tree.c:2097
internal methods for branch and bound tree
struct SCIP_ConflicthdlrData SCIP_CONFLICTHDLRDATA
Definition: type_conflict.h:50
void SCIPbdchginfoFree(SCIP_BDCHGINFO **bdchginfo, BMS_BLKMEM *blkmem)
Definition: var.c:16563
SCIP_RETCODE SCIPvarIncVSIDS(SCIP_VAR *var, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Real weight)
Definition: var.c:15051
SCIP_RETCODE SCIPvarIncNActiveConflicts(SCIP_VAR *var, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Real length)
Definition: var.c:15187
void SCIPvarAdjustLb(SCIP_VAR *var, SCIP_SET *set, SCIP_Real *lb)
Definition: var.c:6517
SCIP_RETCODE SCIPvarScaleVSIDS(SCIP_VAR *var, SCIP_Real scalar)
Definition: var.c:15137
SCIP_RETCODE SCIPbdchginfoCreate(SCIP_BDCHGINFO **bdchginfo, BMS_BLKMEM *blkmem, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_Real oldbound, SCIP_Real newbound)
Definition: var.c:16533
SCIP_RETCODE SCIPvarGetProbvarSum(SCIP_VAR **var, SCIP_SET *set, SCIP_Real *scalar, SCIP_Real *constant)
Definition: var.c:12647
void SCIPvarAdjustUb(SCIP_VAR *var, SCIP_SET *set, SCIP_Real *ub)
Definition: var.c:6534
SCIP_Real SCIPbdchginfoGetRelaxedBound(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18799
internal methods for problem variables
void SCIPvisualFoundConflict(SCIP_VISUAL *visual, SCIP_STAT *stat, SCIP_NODE *node)
Definition: visual.c:612
methods for creating output for visualization tools (VBC, BAK)