prop_vbounds.c
Go to the documentation of this file.
33 * This propagator uses global bound information provided by SCIP to deduce global and local bound changes.
36 * - cliques (set of binary variables, each with a corresponding value, of which at most one variable can get the value)
37 * - variable lower/upper bounds (bounds of arbitrary variables that depend linearly on the value of another variable)
39 * The propagator does not look at a variable in whole, but at one point in time only handles one specific bound (lower
40 * or upper) of a variable and deduces changes for lower or upper bounds of other variables. The concept is as follows:
44 * Implications and cliques are stored in a way such that given a variable and its new value, we can access all bound
45 * changes that can be deduced from setting the variable to that value. However, for variable bounds, this currently
46 * does not hold, they are only stored in the other direction, i.e. for a bound of a given variable, we have a list
47 * of all other bounds of variables that directly influence the bound of the given variable and a linear function
49 * For the propagation, we need the other direction, thus we store it in the propagator data when the branch-and-bound
54 * We compute a topological order of the bounds of variables. This is needed to define an order in which we will
55 * regard bounds of variables in the propagation process in order to avoid unneccessarily regarding the same variable
56 * bound multiple times because it was changed in the meantime when propagating another bound of a variable.
57 * Therefore, we implictly regard a directed graph, in which each node corresponds to a bound of a variable and there
58 * exists a directed edge from one node to another, if the bound corresponding to the former node influences the
59 * bound corresponding to the latter node. This is done by iteratively running a DFS until all nodes were visited.
60 * Note that there might be cycles in the graph, which are randomly broken, so the order is only almost topological.
64 * For each bound of a variable, which can trigger bound changes of other variables, the propagator catches all
65 * events informing about a global change of the bound or a local tightening of the bound. The event handler
66 * then adds the bound of the variable to a priority queue, with the key in the priority queue corresponding
71 * As long as there are bounds contained in the priority queue, the propagator pops one bound from the queue, which
72 * is the one most at the beginning of the topological sort, so it should not be influenced by propagating other
73 * bounds currently contained in the queue. Starting at this bound, all implication, clique, and variable bound
74 * information is used to deduce tigther bounds for other variables and change the bounds, if a tighter one is found.
75 * These bound changes trigger an event that will lead to adding the corresponding bound to the priority queue,
76 * if it is not contained, yet. The process is iterated until the priority queue contains no more bounds.
78 * Additionally, the propagator analyzes the conflict/clique graph during presolving. It uses Tarjan's algorithm to
79 * search for strongly connected components, for each of which all variables can be aggregated to one. Additionally,
80 * it may detect invalid assignments of binary variables and fix the variable to the only possible value left.
83/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
116#define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
118#define PROP_PRESOL_PRIORITY -90000 /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers */
120#define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no
139#define DEFAULT_USEBDWIDENING TRUE /**< should bound widening be used to initialize conflict analysis? */
145#define DEFAULT_DETECTCYCLES FALSE /**< should cycles in the variable bound graph be identified? */
146#define DEFAULT_MINNEWCLIQUES 0.1 /**< minimum number of new cliques to trigger another clique table analysis */
147#define DEFAULT_MAXCLIQUESMEDIUM 50.0 /**< maximum number of cliques per variable to run clique table analysis in
149#define DEFAULT_MAXCLIQUESEXHAUSTIVE 100.0 /**< maximum number of cliques per variable to run clique table analysis in
158 * The propagator works on indices representing a bound of a variable. This index will be called bound index in the
159 * following. For a given active variable with problem index i (note that active variables have problem indices
160 * between 0 and nactivevariable - 1), the bound index of its lower bound is 2*i, the bound index of its upper
161 * bound is 2*i + 1. The other way around, a given bound index i corresponds to the variable with problem index
163 * The following macros can be used to convert bound index into variable problem index and boundtype and vice versa.
185 SCIP_VAR** vars; /**< array containing all variable which are considered within the propagator */
196 SCIP_Real** vboundcoefs; /**< array storing for each bound index the coefficients in the variable
199 SCIP_Real** vboundconstants; /**< array storing for each bound index the constants in the variable
204 int nbounds; /**< number of bounds of variables regarded (two times number of active variables) */
206 SCIP_PQUEUE* propqueue; /**< priority queue to handle the bounds of variables that were changed and have to be propagated */
207 SCIP_Bool* inqueue; /**< boolean array to store whether a bound of a variable is already contained in propqueue */
209 SCIP_Real minnewcliques; /**< minimum percentage of new cliques to trigger another clique table analysis */
210 SCIP_Real maxcliquesmedium; /**< maximum number of cliques per variable to run clique table analysis in medium presolving */
211 SCIP_Real maxcliquesexhaustive;/**< maximum number of cliques per variable to run clique table analysis in exhaustive presolving */
393 if( propdata->nvbounds[idx] == 0 && SCIPvarGetNImpls(var, lower) == 0 && SCIPvarGetNCliques(var, lower) == 0 )
405 SCIP_CALL( SCIPcatchVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*) (uintptr_t) v, NULL) ); /*lint !e571*/
453 SCIP_CALL( SCIPdropVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*) (uintptr_t) v, -1) ); /*lint !e571*/
482 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundboundedidx[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
483 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundcoefs[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
484 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundconstants[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
492 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundboundedidx[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
493 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundcoefs[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
494 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundconstants[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
506/** comparison method for two indices in the topoorder array, preferring higher indices because the order is reverse
518/* extract bound changes or infeasibility information from a cycle in the variable bound graph detected during
531 SCIP_Bool samebound, /**< does the cycle contain the same bound twice or both bounds of the same variable? */
558 /* the same bound of the variable was visited already earlier on the current path, so the start-point of the cycle
563 /* the other bound of the variable was visited earlier on the current path, so the start-point of the cycle
569 /* search for the start-point of the cycle; since the endpoint is at position stacksize - 1 we start at stacksize - 2
580 /* if we do not use implications, we assume the number of implications to be 0 (as we did before) */
583 /* stacknextedge[j] <= 0 --> the last outgoing edge traversed during dfs starting from node dfsstack[j] was given
605 * in cases a) and d), coef=-1.0 and constant=1.0; both nodes represent different types of bounds
615 /* since the coefficient and constant only depend on the type of bounds of the two nodes (see below), we do not
616 * need to search for the variable in the clique; however, if debug output is enabled, we want to print the
617 * clique, if more debugging is enabled, we explicitly check that the variable and bound we expect are in the
627 /* we processed at least one edge, so the next one should be -2 or smaller (we have a -1 offset) */
664 /* stacknextedge[j] > 0 --> the last outgoing edge traversed during dfs starting from node dfsstack[j] was given
665 * by an implication or vbound. Implications are looked at first, so if stacknextedge[j] <= ntmpimpls, it comes
738 constant = constant * propdata->vboundcoefs[dfsstack[j]][k] + propdata->vboundconstants[dfsstack[j]][k];
750 * (the relation depends on islower, i.e., whether the last node in the cycle is a lower or upper bound)
784 SCIPdebugMsg(scip, "-> found new lower bound: <%s>[%g,%g] >= %g\n", SCIPvarGetName(vars[getVarIndex(cycleidx)]),
785 SCIPvarGetLbLocal(vars[getVarIndex(cycleidx)]), SCIPvarGetUbLocal(vars[getVarIndex(cycleidx)]), newbound);
786 SCIP_CALL( SCIPtightenVarLb(scip, vars[getVarIndex(cycleidx)], newbound, FALSE, infeasible, &tightened) );
790 SCIPdebugMsg(scip, "-> found new upper bound: <%s>[%g,%g] <= %g\n", SCIPvarGetName(vars[getVarIndex(cycleidx)]),
791 SCIPvarGetLbLocal(vars[getVarIndex(cycleidx)]), SCIPvarGetUbLocal(vars[getVarIndex(cycleidx)]), newbound);
792 SCIP_CALL( SCIPtightenVarUb(scip, vars[getVarIndex(cycleidx)], newbound, FALSE, infeasible, &tightened) );
804/** performs depth-first-search in the implicitly given directed graph from the given start index */
830 /* for cycle detection, we need to mark currently active nodes, otherwise we just mark them as visited */
852 /* we run until no more bounds indices are on the stack, i.e. all changed bounds were propagated */
874 /* stacknextedge is negative, if the last visited edge from the current node belongs to a clique;
912 /* we reached a variable that was already visited on the active path, so we have a cycle in the variable
941 /* we stopped because we found an unhandled node and not because we reached the end of the list */
948 SCIPdebugMsg(scip, "clique: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
987 /* it might happen that implications point to inactive variables (normally, those are removed when a
988 * variable becomes inactive, but in some cases, it cannot be done), we have to ignore these variables
993 /* implication is just a shortcut, so we dont regard it now, because will later go the long way, anyway;
1002 /* we reached a variable that was already visited on the active path, so we have a cycle in the variable
1025 /* we stopped because we found an unhandled node and not because we reached the end of the list */
1030 SCIPdebugMsg(scip, "impl: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
1068 && !SCIPisFeasGE(scip, SCIPvarGetLbGlobal(vars[getVarIndex(idx)]), SCIPvarGetUbGlobal(vars[getVarIndex(idx)])) )
1075 /* we reached a variable that was already visited on the active path, so we have a cycle in the variable
1093 /* we stopped because we found an unhandled node and not because we reached the end of the list */
1098 SCIPdebugMsg(scip, "vbound: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
1116 SCIPdebugMsg(scip, "topoorder[%d] = %s(%s)\n", *ndfsnodes, getBoundString(lower), SCIPvarGetName(startvar));
1155 /* while there are unvisited nodes, run dfs starting from one of these nodes; the dfs orders are stored in the
1156 * topoorder array, later dfs calls are just appended after the stacks of previous dfs calls, which gives us a
1163 SCIP_CALL( dfs(scip, propdata, i, visited, dfsstack, stacknextedge, propdata->topoorder, &nsortednodes, infeasible) );
1221 /* we need to copy the variable since this array is the basis of the propagator and the corresponding variable array
1304 /* if the coefficient is positive, the type of bound is the same for the bounded and the bounding variable */
1312 * However, it might happen that vbvar was integer when the variable bound was added, but was converted
1313 * to a binary variable later during presolving when its upper bound was changed to 1. In this case,
1319 SCIPdebugMsg(scip, "varbound <%s> %s %g * <%s> + %g not added to propagator data due to reverse implication\n",
1353 SCIP_BDCHGIDX* bdchgidx /**< the index of the bound change, representing the point of time where
1380/** relaxes bound of give variable as long as the given inference bound still leads to a cutoff and add that bound
1388 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where
1406/** compute the relaxed bound which is sufficient to propagate the inference lower bound of given variable */
1423 /* check the computed relaxed lower/upper bound is a proper reason for the inference bound which has to be explained */
1434/** analyzes an infeasibility which was reached by updating the lower bound of the inference variable above its upper
1454 assert(SCIPisEQ(scip, SCIPvarGetUbLocal(infervar), SCIPgetVarUbAtIndex(scip, infervar, NULL, FALSE)));
1455 assert(SCIPisEQ(scip, SCIPgetVarUbAtIndex(scip, infervar, NULL, TRUE), SCIPgetVarUbAtIndex(scip, infervar, NULL, FALSE)));
1468 SCIPdebugMsg(scip, "try to create conflict using bound widening order: inference variable, variable bound variable\n");
1470 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1494 /* compute the relaxed bound which is sufficient to propagate the inference lower bound of given variable */
1505 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1521/** compute the relaxed bound which is sufficient to propagate the inference upper bound of given variable */
1538 /* check the computed relaxed lower/upper bound is a proper reason for the inference bound which has to be explained */
1549/** analyzes an infeasibility which was reached by updating the upper bound of the inference variable below its lower
1562 SCIP_Bool canwide /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1568 assert(SCIPisEQ(scip, SCIPvarGetLbLocal(infervar), SCIPgetVarLbAtIndex(scip, infervar, NULL, FALSE)));
1569 assert(SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, infervar, NULL, TRUE), SCIPgetVarLbAtIndex(scip, infervar, NULL, FALSE)));
1582 SCIPdebugMsg(scip, "try to create conflict using bound widening order: inference variable, variable bound variable\n");
1584 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1608 /* compute the relaxed bound which is sufficient to propagate the inference upper bound of given variable */
1619 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1651 SCIP_Bool canwide, /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1683 inferinfo = getInferInfo(boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, vbdvar) : varGetUbIndex(propdata, vbdvar), boundtype);
1685 SCIP_CALL( SCIPinferVarLbProp(scip, var, newlb, prop, inferInfoToInt(inferinfo), force, &infeasible, &tightened) );
1690 /* the infeasible results comes from the fact that the new lower bound lies above the current upper bound */
1694 SCIPdebugMsg(scip, "tightening%s lower bound of variable <%s> to %g due the %s bound of variable <%s> led to infeasibility\n",
1695 (global ? " global" : ""), SCIPvarGetName(var), newlb, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1705 SCIP_CALL( analyzeConflictLowerbound(scip, propdata, var, newlb, vbdvar, boundtype, coef, constant, canwide) );
1711 SCIPdebugMsg(scip, "tightened%s lower bound of variable <%s> to %g due the %s bound of variable <%s>\n",
1712 (global ? " global" : ""), SCIPvarGetName(var), newlb, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1735 SCIP_Bool canwide, /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1767 inferinfo = getInferInfo(boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, vbdvar) : varGetUbIndex(propdata, vbdvar), boundtype);
1769 SCIP_CALL( SCIPinferVarUbProp(scip, var, newub, prop, inferInfoToInt(inferinfo), force, &infeasible, &tightened) );
1774 /* the infeasible results comes from the fact that the new upper bound lies below the current lower bound */
1778 SCIPdebugMsg(scip, "tightening%s upper bound of variable <%s> to %g due the %s bound of variable <%s> led to infeasibility\n",
1779 (global ? " global" : ""), SCIPvarGetName(var), newub, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1789 SCIP_CALL( analyzeConflictUpperbound(scip, propdata, var, newub, vbdvar, boundtype, coef, constant, canwide) );
1795 SCIPdebugMsg(scip, "tightened%s upper bound of variable <%s> to %g due the %s bound of variable <%s>\n",
1796 (global ? " global" : ""), SCIPvarGetName(var), newub, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1835 /* we do not run the propagator in presolving, because we want to avoid doing the expensive creation of the graph twice */
1879 SCIP_CALL( SCIPpqueueInsert(propdata->propqueue, (void*)(size_t)(v + 1)) ); /*lint !e571 !e776*/
1886 /* return if no bound changes are in the priority queue (no changed bounds to handle since last propagation) */
1897 SCIPdebugMsg(scip, "varbound propagator: %d elements in the propagation queue\n", SCIPpqueueNElems(propdata->propqueue));
1899 /* get variable bound of highest priority from priority queue and try to deduce bound changes for other variables;
1912 /* do not directly set propdata->inqueue[topopos] = FALSE: we allow only one propagation sweep through the
1931 /* we only propagate binary variables if the lower bound changed to 1.0 or the upper bound changed to 0.0 */
1940 /* if the lower bound of the startvar was changed, it was fixed to 1.0, otherwise it was fixed to 0.0;
1966 /* it might happen that implications point to inactive variables (normally, those are removed when a
1967 * variable becomes inactive, but in some cases, it cannot be done), we have to ignore these variables
1996 /* if the lower bound of the startvar was changed, it was fixed to 1.0, otherwise it was fixed to 0.0;
2070 SCIP_CALL( tightenVarLb(scip, prop, propdata, boundedvar, newbound, global, startvar, starttype, force,
2075 SCIP_CALL( tightenVarUb(scip, prop, propdata, boundedvar, newbound, global, startvar, starttype, force,
2092 assert( SCIPpqueueFind(propdata->propqueue, (void*)(size_t) (queuelist[v] + 1)) == -1 ); /*lint !e571*//*lint !e776*/
2149/** presolving initialization method of propagator (called when presolving is about to begin) */
2163/** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
2214/** performs Tarjan's algorithm for strongly connected components in the implicitly given directed implication graph
2215 * from the given start index; each variable x is represented by two nodes lb(x) = 2*idx(x) and ub(x) = 2*idx(x)+1
2216 * where lb(x) means that the lower bound of x should be changed, i.e., that x is fixed to 1, and vice versa.
2222 * This quadratic number can blow up the running time of Tarjan's algorithm, which is linear in the number of
2223 * nodes and arcs of the graph. However, it suffices to consider only k of these arcs during the course of the algorithm.
2224 * To this end, when we first come to a node lb(x_i) of the clique, traverse all arcs (lb(x_i),ub(x_j)) for this particular i,
2225 * and store that we entered the clique via lb(x_i). Next time we come to any node lb(x_i') of the clique, we know
2226 * that the only arc pointing to an unvisited node is (lb(x_i'),ub(x_i)), all other edges can be disregarded.
2228 * Additionally, we try to identify infeasible fixings for binary variables. Those can be given by a path
2239 SCIP_Shortbool* nodeinfeasible, /**< array to store whether the fixing of a node was detected to be infeasible */
2241 int* predstackidx, /**< for each node on the stack: stack position of its predecessor in the Tarjan search */
2242 int* stacknextclique, /**< array of size number of nodes to store the next clique to be regarded in
2244 int* stacknextcliquevar, /**< array of size number of nodes to store the next variable in the next clique to be
2248 int* cliquefirstentry, /**< node from which a clique was entered for the first time; needed because when
2251 int* cliquecurrentexit, /**< for cliques which define an arc on the current path: target node of this arc */
2297 /* we run until no more bounds indices are on the stack, i.e., no further nodes are connected to the startnode */
2330 SCIPdebugMsg(scip, "variable %s(%s) has %d cliques\n", indexGetBoundString(curridx), SCIPvarGetName(startvar),
2377 /* we did not look at this clique before from the current node, i.e., we did not backtrack now from another
2397 int cliquefirstentryidx = (cliquefirstentry[clqidx] > 0 ? cliquefirstentry[clqidx] : -cliquefirstentry[clqidx]) - 1;
2403 * Since these two assignments together violate the clique and the second assignment is implied by the first,
2408 SCIPdebugMsg(scip, "infeasible assignment (1): %s(%s)\n", indexGetBoundString(cliquefirstentryidx),
2412 /* the first entry point of the clique was also implied by the current startnode, so this node implies
2435 /* the last node by which the clique was exited is not the negation of the current node and still on
2446 /* clique is entered for the second time; there is only one edge left to investigate, namely the edge to
2525 /* we stopped because we found an unhandled node and not because we reached the end of the list */
2536 /* the negated node corresponding to the next node is already on the stack -> the negated assignment is
2545 /* the negated node corresponding to the next node was reached from the same startnode -> the startnode is
2567 SCIPdebugMsg(scip, "clique: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
2581 SCIPdebugMsg(scip, "put %s(%s) on stack[%d]\n", indexGetBoundString(dfsstack[stacksize-1]), SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize-1])]), stacksize-1);
2607 SCIPdebugMsgPrint(scip, " %s(%s)", indexGetBoundString(idx), SCIPvarGetName(vars[getVarIndex(idx)]));
2609 SCIPdebugMsg(scip, "remove %s(%s) from stack[%d]\n", indexGetBoundString(dfsstack[stacksize]), SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize])]), stacksize);
2622 SCIPdebugMsg(scip, "remove %s(%s) from stack[%d]\n", indexGetBoundString(dfsstack[stacksize]), SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize])]), stacksize);
2629 /* in a pure dfs, the node would now leave the stack, add it to the array of nodes in reverse topological order */
2659 SCIP_Shortbool* nodeinfeasible, /**< array to store whether the fixing of a node was detected to be infeasible */
2665 int* nfixedvars, /**< pointer to number of fixed variables, increment when fixing another one */
2666 int* naggrvars, /**< pointer to number of aggregated variables, increment when aggregating another one */
2707 /* clear clean buffer array (if we did not enter the block above or stopped early due to an infeasibility) */
2744 SCIPvarGetName(vars[getVarIndex(sccvars[v])]), lower == isIndexLowerbound(sccvars[v]) ? 0.0 : 1.0,
2766/** presolving method of propagator: search for strongly connected components in the implication graph and
2767 * aggregate all variables within a component; additionally, identifies infeasible variable assignments
2768 * as a side product if a path from x=1 to x=0 (or vice versa) is found or x=1 implies both y=0 and y=1
2769 * The identification of such assignments depends on the order in which variable bounds are processed;
2770 * therefore, we are doing a second run with the bounds processed in (almost) topological order.
2815 if( presoltiming == SCIP_PRESOLTIMING_MEDIUM && ncliques > propdata->maxcliquesmedium * SCIPgetNBinVars(scip) )
2823 if( SCIPgetNCliquesCreated(scip) < (1.0 + propdata->minnewcliques) * propdata->lastpresolncliques )
2876 /* aggregate all variables within a SCC and fix all variables for which one bounds was proven infeasible */
2891 /* we already fixed or aggregated some variables in the first run, so we better clean up the cliques */
2932 SCIP_CALL( tarjan(scip, startpos, &startindex, nodeonstack, nodeindex, nodelowlink, nodeinfeasible,
2940 /* aggregate all variables within a SCC and fix all variables for which one bounds was proven infeasible */
3036 inferidx = boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, infervar) : varGetUbIndex(propdata, infervar);
3050 /* compute the relaxed bound which is sufficient to propagate the inference bound of given variable */
3092 SCIPdebugMsg(scip, "eventexec (type=%" SCIP_EVENTTYPE_FORMAT "): try to add sort index %d: %s(%s) to priority queue\n", SCIPeventGetType(event),
3096 if( SCIPeventGetType(event) == SCIP_EVENTTYPE_GUBCHANGED && SCIPvarIsBinary(SCIPeventGetVar(event))
3100 if( SCIPeventGetType(event) == SCIP_EVENTTYPE_GLBCHANGED && SCIPvarIsBinary(SCIPeventGetVar(event))
3105 assert(SCIPvarGetType(propdata->vars[getVarIndex(propdata->topoorder[idx])]) != SCIP_VARTYPE_BINARY
3111 SCIP_CALL( SCIPpqueueInsert(propdata->propqueue, (void*)(size_t)(idx + 1)) ); /*lint !e571 !e776*/
3137 SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
3147 SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolVbounds, PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS,
3151 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &propdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
3155 "propagating/" PROP_NAME "/usebdwidening", "should bound widening be used to initialize conflict analysis?",
3167 "propagating/" PROP_NAME "/dotoposort", "should the bounds be topologically sorted in advance?",
3170 "propagating/" PROP_NAME "/sortcliques", "should cliques be regarded for the topological sort?",
3173 "propagating/" PROP_NAME "/detectcycles", "should cycles in the variable bound graph be identified?",
3176 "propagating/" PROP_NAME "/minnewcliques", "minimum percentage of new cliques to trigger another clique table analysis",
3180 &propdata->maxcliquesmedium, FALSE, DEFAULT_MAXCLIQUESMEDIUM, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3182 "maximum number of cliques per variable to run clique table analysis in exhaustive presolving",
3183 &propdata->maxcliquesexhaustive, FALSE, DEFAULT_MAXCLIQUESEXHAUSTIVE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3188/** returns TRUE if the propagator has the status that all variable lower and upper bounds are propgated */
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3281
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3192
SCIP_RETCODE SCIPexecPropVbounds(SCIP *scip, SCIP_Bool force, SCIP_RESULT *result)
Definition: prop_vbounds.c:3206
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1394
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)))
Definition: misc.c:1295
SCIP_RETCODE SCIPincludePropVbounds(SCIP *scip)
Definition: prop_vbounds.c:3123
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip_conflict.c:352
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition: scip_conflict.c:323
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip_conflict.c:419
SCIP_RETCODE SCIPaddConflictRelaxedLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedlb)
Definition: scip_conflict.c:386
SCIP_RETCODE SCIPanalyzeConflict(SCIP *scip, int validdepth, SCIP_Bool *success)
Definition: scip_conflict.c:672
SCIP_RETCODE SCIPaddConflictRelaxedUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedub)
Definition: scip_conflict.c:454
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
Definition: scip_conflict.c:301
SCIP_Real SCIPgetConflictVarUb(SCIP *scip, SCIP_VAR *var)
Definition: scip_conflict.c:642
SCIP_Real SCIPgetConflictVarLb(SCIP *scip, SCIP_VAR *var)
Definition: scip_conflict.c:618
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:104
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:334
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:354
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:400
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip_prop.c:312
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_prop.c:279
SCIP_RETCODE SCIPsetPropInitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITPRE((*propinitpre)))
Definition: scip_prop.c:247
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:167
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:151
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip_prop.c:231
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
Definition: scip_prop.c:114
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:832
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:869
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:484
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:458
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:857
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5203
SCIP_RETCODE SCIPinferVarUbProp(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_PROP *inferprop, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6010
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6348
SCIP_Bool SCIPvarHasImplic(SCIP_VAR *var, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype)
Definition: var.c:11111
SCIP_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated)
Definition: scip_var.c:8401
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5320
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: scip_var.c:1794
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18373
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2128
SCIP_RETCODE SCIPcleanupCliques(SCIP *scip, SCIP_Bool *infeasible)
Definition: scip_var.c:7532
SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub)
Definition: scip_var.c:4645
SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb)
Definition: scip_var.c:4613
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18402
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18441
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8276
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1992
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18388
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6228
SCIP_RETCODE SCIPinferVarLbProp(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_PROP *inferprop, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5895
memory allocation routines
Definition: objbenders.h:44
static SCIP_RETCODE propagateVbounds(SCIP *scip, SCIP_PROP *prop, SCIP_Bool force, SCIP_RESULT *result)
Definition: prop_vbounds.c:1805
static SCIP_RETCODE relaxVbdvar(SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd)
Definition: prop_vbounds.c:1384
static SCIP_RETCODE topologicalSort(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool *infeasible)
Definition: prop_vbounds.c:1130
static SCIP_RETCODE extractCycle(SCIP *scip, SCIP_PROPDATA *propdata, int *dfsstack, int *stacknextedge, int stacksize, SCIP_Bool samebound, SCIP_Bool *infeasible)
Definition: prop_vbounds.c:522
static SCIP_RETCODE dfs(SCIP *scip, SCIP_PROPDATA *propdata, int startnode, int *visited, int *dfsstack, int *stacknextedge, int *dfsnodes, int *ndfsnodes, SCIP_Bool *infeasible)
Definition: prop_vbounds.c:806
static SCIP_Real computeRelaxedLowerbound(SCIP *scip, SCIP_VAR *var, SCIP_Real inferlb, SCIP_Real coef, SCIP_Real constant)
Definition: prop_vbounds.c:1408
static SCIP_RETCODE catchEvents(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_vbounds.c:354
static SCIP_DECL_SORTPTRCOMP(compVarboundIndices)
Definition: prop_vbounds.c:510
static int varGetLbIndex(SCIP_PROPDATA *propdata, SCIP_VAR *var)
Definition: prop_vbounds.c:302
static SCIP_RETCODE analyzeConflictUpperbound(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *infervar, SCIP_Real inferub, SCIP_VAR *vbdvar, SCIP_BOUNDTYPE boundtype, SCIP_Real coef, SCIP_Real constant, SCIP_Bool canwide)
Definition: prop_vbounds.c:1553
static SCIP_RETCODE addVbound(SCIP *scip, SCIP_PROPDATA *propdata, int startidx, int endidx, SCIP_Real coef, SCIP_Real constant)
Definition: prop_vbounds.c:463
static SCIP_RETCODE dropEvents(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_vbounds.c:413
static SCIP_RETCODE applyFixingsAndAggregations(SCIP *scip, SCIP_VAR **vars, int *infeasnodes, int ninfeasnodes, SCIP_Shortbool *nodeinfeasible, int *sccvars, int *sccstarts, int nsccs, SCIP_Bool *infeasible, int *nfixedvars, int *naggrvars, SCIP_RESULT *result)
Definition: prop_vbounds.c:2654
static SCIP_DECL_PROPEXITSOL(propExitsolVbounds)
Definition: prop_vbounds.c:2165
static SCIP_RETCODE tarjan(SCIP *scip, int startnode, int *startindex, SCIP_Shortbool *nodeonstack, int *nodeindex, int *nodelowlink, SCIP_Shortbool *nodeinfeasible, int *dfsstack, int *predstackidx, int *stacknextclique, int *stacknextcliquevar, int *topoorder, int *nordered, int *cliquefirstentry, int *cliquecurrentexit, int *sccvars, int *sccstarts, int *nsccs, int *infeasnodes, int *ninfeasnodes, SCIP_Bool *infeasible)
Definition: prop_vbounds.c:2232
static SCIP_BOUNDTYPE inferInfoGetBoundtype(INFERINFO inferinfo)
Definition: prop_vbounds.c:260
static SCIP_DECL_PROPINITPRE(propInitpreVbounds)
Definition: prop_vbounds.c:2151
static int varGetUbIndex(SCIP_PROPDATA *propdata, SCIP_VAR *var)
Definition: prop_vbounds.c:319
static SCIP_DECL_PROPRESPROP(propRespropVbounds)
Definition: prop_vbounds.c:2999
static SCIP_RETCODE analyzeConflictLowerbound(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *infervar, SCIP_Real inferlb, SCIP_VAR *vbdvar, SCIP_BOUNDTYPE boundtype, SCIP_Real coef, SCIP_Real constant, SCIP_Bool canwide)
Definition: prop_vbounds.c:1438
static SCIP_RETCODE tightenVarUb(SCIP *scip, SCIP_PROP *prop, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_Real newub, SCIP_Bool global, SCIP_VAR *vbdvar, SCIP_BOUNDTYPE boundtype, SCIP_Bool force, SCIP_Real coef, SCIP_Real constant, SCIP_Bool canwide, int *nchgbds, SCIP_RESULT *result)
Definition: prop_vbounds.c:1721
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx)
Definition: prop_vbounds.c:1348
static SCIP_RETCODE tightenVarLb(SCIP *scip, SCIP_PROP *prop, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_Real newlb, SCIP_Bool global, SCIP_VAR *vbdvar, SCIP_BOUNDTYPE boundtype, SCIP_Bool force, SCIP_Real coef, SCIP_Real constant, SCIP_Bool canwide, int *nchgbds, SCIP_RESULT *result)
Definition: prop_vbounds.c:1637
static SCIP_RETCODE initData(SCIP *scip, SCIP_PROP *prop, SCIP_Bool *infeasible)
Definition: prop_vbounds.c:1177
static INFERINFO getInferInfo(int pos, SCIP_BOUNDTYPE boundtype)
Definition: prop_vbounds.c:280
static SCIP_Real computeRelaxedUpperbound(SCIP *scip, SCIP_VAR *var, SCIP_Real inferub, SCIP_Real coef, SCIP_Real constant)
Definition: prop_vbounds.c:1523
variable upper and lower bound propagator
public methods for managing events
public methods for implications, variable bounds, and cliques
public methods for message output
public data structures and miscellaneous methods
public methods for propagators
public methods for problem variables
public methods for conflict handler plugins and conflict analysis
public methods for event handler plugins and event handlers
general public methods
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for propagator plugins
public methods for the branch-and-bound tree
public methods for SCIP variables
Definition: struct_var.h:109
Definition: struct_implics.h:76
Definition: struct_event.h:205
Definition: struct_misc.h:138
Definition: struct_misc.h:79
Definition: struct_prop.h:47
Definition: struct_var.h:208
Definition: struct_scip.h:70