prop_vbounds.c
Go to the documentation of this file.
23 * This propagator uses global bound information provided by SCIP to deduce global and local bound changes.
26 * - cliques (set of binary variables, each with a corresponding value, of which at most one variable can get the value)
27 * - variable lower/upper bounds (bounds of arbitrary variables that depend linearly on the value of another variable)
29 * The propagator does not look at a variable in whole, but at one point in time only handles one specific bound (lower
30 * or upper) of a variable and deduces changes for lower or upper bounds of other variables. The concept is as follows:
34 * Implications and cliques are stored in a way such that given a variable and its new value, we can access all bound
35 * changes that can be deduced from setting the variable to that value. However, for variable bounds, this currently
36 * does not hold, they are only stored in the other direction, i.e. for a bound of a given variable, we have a list
37 * of all other bounds of variables that directly influence the bound of the given variable and a linear function
39 * For the propagation, we need the other direction, thus we store it in the propagator data when the branch-and-bound
44 * We compute a topological order of the bounds of variables. This is needed to define an order in which we will
45 * regard bounds of variables in the propagation process in order to avoid unneccessarily regarding the same variable
46 * bound multiple times because it was changed in the meantime when propagating another bound of a variable.
47 * Therefore, we implictly regard a directed graph, in which each node corresponds to a bound of a variable and there
48 * exists a directed edge from one node to another, if the bound corresponding to the former node influences the
49 * bound corresponding to the latter node. This is done by iteratively running a DFS until all nodes were visited.
50 * Note that there might be cycles in the graph, which are randomly broken, so the order is only almost topological.
54 * For each bound of a variable, which can trigger bound changes of other variables, the propagator catches all
55 * events informing about a global change of the bound or a local tightening of the bound. The event handler
56 * then adds the bound of the variable to a priority queue, with the key in the priority queue corresponding
61 * As long as there are bounds contained in the priority queue, the propagator pops one bound from the queue, which
62 * is the one most at the beginning of the topological sort, so it should not be influenced by propagating other
63 * bounds currently contained in the queue. Starting at this bound, all implication, clique, and variable bound
64 * information is used to deduce tigther bounds for other variables and change the bounds, if a tighter one is found.
65 * These bound changes trigger an event that will lead to adding the corresponding bound to the priority queue,
66 * if it is not contained, yet. The process is iterated until the priority queue contains no more bounds.
68 * Additionally, the propagator analyzes the conflict/clique graph during presolving. It uses Tarjan's algorithm to
69 * search for strongly connected components, for each of which all variables can be aggregated to one. Additionally,
70 * it may detect invalid assignments of binary variables and fix the variable to the only possible value left.
73 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
106 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
108 #define PROP_PRESOL_PRIORITY -90000 /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers */
110 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no
129 #define DEFAULT_USEBDWIDENING TRUE /**< should bound widening be used to initialize conflict analysis? */
135 #define DEFAULT_DETECTCYCLES FALSE /**< should cycles in the variable bound graph be identified? */
136 #define DEFAULT_MINNEWCLIQUES 0.1 /**< minimum number of new cliques to trigger another clique table analysis */
137 #define DEFAULT_MAXCLIQUESMEDIUM 50.0 /**< maximum number of cliques per variable to run clique table analysis in
139 #define DEFAULT_MAXCLIQUESEXHAUSTIVE 100.0 /**< maximum number of cliques per variable to run clique table analysis in
148 * The propagator works on indices representing a bound of a variable. This index will be called bound index in the
149 * following. For a given active variable with problem index i (note that active variables have problem indices
150 * between 0 and nactivevariable - 1), the bound index of its lower bound is 2*i, the bound index of its upper
151 * bound is 2*i + 1. The other way around, a given bound index i corresponds to the variable with problem index
153 * The following macros can be used to convert bound index into variable problem index and boundtype and vice versa.
175 SCIP_VAR** vars; /**< array containing all variable which are considered within the propagator */
186 SCIP_Real** vboundcoefs; /**< array storing for each bound index the coefficients in the variable
189 SCIP_Real** vboundconstants; /**< array storing for each bound index the constants in the variable
194 int nbounds; /**< number of bounds of variables regarded (two times number of active variables) */
196 SCIP_PQUEUE* propqueue; /**< priority queue to handle the bounds of variables that were changed and have to be propagated */
197 SCIP_Bool* inqueue; /**< boolean array to store whether a bound of a variable is already contained in propqueue */
199 SCIP_Real minnewcliques; /**< minimum percentage of new cliques to trigger another clique table analysis */
200 SCIP_Real maxcliquesmedium; /**< maximum number of cliques per variable to run clique table analysis in medium presolving */
201 SCIP_Real maxcliquesexhaustive;/**< maximum number of cliques per variable to run clique table analysis in exhaustive presolving */
231 {
244 {
253 {
264 {
273 )
295 )
297 assert(SCIPhashmapExists(propdata->varhashmap, var) == (SCIPhashmapGetImageInt(propdata->varhashmap, var) > 0));
307 )
309 assert(SCIPhashmapExists(propdata->varhashmap, var) == (SCIPhashmapGetImageInt(propdata->varhashmap, var) > 0));
319 {
337 )
373 if( propdata->nvbounds[idx] == 0 && SCIPvarGetNImpls(var, lower) == 0 && SCIPvarGetNCliques(var, lower) == 0 )
385 SCIP_CALL( SCIPcatchVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*) (uintptr_t) v, NULL) ); /*lint !e571*/
396 )
433 SCIP_CALL( SCIPdropVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*) (uintptr_t) v, -1) ); /*lint !e571*/
462 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundboundedidx[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
463 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundcoefs[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
464 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundconstants[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
472 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundboundedidx[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
473 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundcoefs[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
474 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundconstants[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
486 /** comparison method for two indices in the topoorder array, preferring higher indices because the order is reverse
498 /* extract bound changes or infeasibility information from a cycle in the variable bound graph detected during
511 SCIP_Bool samebound, /**< does the cycle contain the same bound twice or both bounds of the same variable? */
538 /* the same bound of the variable was visited already earlier on the current path, so the start-point of the cycle
543 /* the other bound of the variable was visited earlier on the current path, so the start-point of the cycle
549 /* search for the start-point of the cycle; since the endpoint is at position stacksize - 1 we start at stacksize - 2
560 /* if we do not use implications, we assume the number of implications to be 0 (as we did before) */
563 /* stacknextedge[j] <= 0 --> the last outgoing edge traversed during dfs starting from node dfsstack[j] was given
585 * in cases a) and d), coef=-1.0 and constant=1.0; both nodes represent different types of bounds
595 /* since the coefficient and constant only depend on the type of bounds of the two nodes (see below), we do not
596 * need to search for the variable in the clique; however, if debug output is enabled, we want to print the
597 * clique, if more debugging is enabled, we explicitly check that the variable and bound we expect are in the
607 /* we processed at least one edge, so the next one should be -2 or smaller (we have a -1 offset) */
644 /* stacknextedge[j] > 0 --> the last outgoing edge traversed during dfs starting from node dfsstack[j] was given
645 * by an implication or vbound. Implications are looked at first, so if stacknextedge[j] <= ntmpimpls, it comes
718 constant = constant * propdata->vboundcoefs[dfsstack[j]][k] + propdata->vboundconstants[dfsstack[j]][k];
730 * (the relation depends on islower, i.e., whether the last node in the cycle is a lower or upper bound)
764 SCIPdebugMsg(scip, "-> found new lower bound: <%s>[%g,%g] >= %g\n", SCIPvarGetName(vars[getVarIndex(cycleidx)]),
765 SCIPvarGetLbLocal(vars[getVarIndex(cycleidx)]), SCIPvarGetUbLocal(vars[getVarIndex(cycleidx)]), newbound);
766 SCIP_CALL( SCIPtightenVarLb(scip, vars[getVarIndex(cycleidx)], newbound, FALSE, infeasible, &tightened) );
770 SCIPdebugMsg(scip, "-> found new upper bound: <%s>[%g,%g] <= %g\n", SCIPvarGetName(vars[getVarIndex(cycleidx)]),
771 SCIPvarGetLbLocal(vars[getVarIndex(cycleidx)]), SCIPvarGetUbLocal(vars[getVarIndex(cycleidx)]), newbound);
772 SCIP_CALL( SCIPtightenVarUb(scip, vars[getVarIndex(cycleidx)], newbound, FALSE, infeasible, &tightened) );
784 /** performs depth-first-search in the implicitly given directed graph from the given start index */
810 /* for cycle detection, we need to mark currently active nodes, otherwise we just mark them as visited */
832 /* we run until no more bounds indices are on the stack, i.e. all changed bounds were propagated */
854 /* stacknextedge is negative, if the last visited edge from the current node belongs to a clique;
892 /* we reached a variable that was already visited on the active path, so we have a cycle in the variable
921 /* we stopped because we found an unhandled node and not because we reached the end of the list */
928 SCIPdebugMsg(scip, "clique: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
967 /* it might happen that implications point to inactive variables (normally, those are removed when a
968 * variable becomes inactive, but in some cases, it cannot be done), we have to ignore these variables
973 /* implication is just a shortcut, so we dont regard it now, because will later go the long way, anyway;
982 /* we reached a variable that was already visited on the active path, so we have a cycle in the variable
1005 /* we stopped because we found an unhandled node and not because we reached the end of the list */
1010 SCIPdebugMsg(scip, "impl: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
1048 && !SCIPisFeasGE(scip, SCIPvarGetLbGlobal(vars[getVarIndex(idx)]), SCIPvarGetUbGlobal(vars[getVarIndex(idx)])) )
1055 /* we reached a variable that was already visited on the active path, so we have a cycle in the variable
1073 /* we stopped because we found an unhandled node and not because we reached the end of the list */
1078 SCIPdebugMsg(scip, "vbound: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
1096 SCIPdebugMsg(scip, "topoorder[%d] = %s(%s)\n", *ndfsnodes, getBoundString(lower), SCIPvarGetName(startvar));
1135 /* while there are unvisited nodes, run dfs starting from one of these nodes; the dfs orders are stored in the
1136 * topoorder array, later dfs calls are just appended after the stacks of previous dfs calls, which gives us a
1143 SCIP_CALL( dfs(scip, propdata, i, visited, dfsstack, stacknextedge, propdata->topoorder, &nsortednodes, infeasible) );
1201 /* we need to copy the variable since this array is the basis of the propagator and the corresponding variable array
1284 /* if the coefficient is positive, the type of bound is the same for the bounded and the bounding variable */
1292 * However, it might happen that vbvar was integer when the variable bound was added, but was converted
1293 * to a binary variable later during presolving when its upper bound was changed to 1. In this case,
1299 SCIPdebugMsg(scip, "varbound <%s> %s %g * <%s> + %g not added to propagator data due to reverse implication\n",
1333 SCIP_BDCHGIDX* bdchgidx /**< the index of the bound change, representing the point of time where
1360 /** relaxes bound of give variable as long as the given inference bound still leads to a cutoff and add that bound
1368 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where
1386 /** compute the relaxed bound which is sufficient to propagate the inference lower bound of given variable */
1403 /* check the computed relaxed lower/upper bound is a proper reason for the inference bound which has to be explained */
1414 /** analyzes an infeasibility which was reached by updating the lower bound of the inference variable above its upper
1434 assert(SCIPisEQ(scip, SCIPvarGetUbLocal(infervar), SCIPgetVarUbAtIndex(scip, infervar, NULL, FALSE)));
1435 assert(SCIPisEQ(scip, SCIPgetVarUbAtIndex(scip, infervar, NULL, TRUE), SCIPgetVarUbAtIndex(scip, infervar, NULL, FALSE)));
1448 SCIPdebugMsg(scip, "try to create conflict using bound widening order: inference variable, variable bound variable\n");
1450 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1474 /* compute the relaxed bound which is sufficient to propagate the inference lower bound of given variable */
1485 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1501 /** compute the relaxed bound which is sufficient to propagate the inference upper bound of given variable */
1518 /* check the computed relaxed lower/upper bound is a proper reason for the inference bound which has to be explained */
1529 /** analyzes an infeasibility which was reached by updating the upper bound of the inference variable below its lower
1542 SCIP_Bool canwide /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1548 assert(SCIPisEQ(scip, SCIPvarGetLbLocal(infervar), SCIPgetVarLbAtIndex(scip, infervar, NULL, FALSE)));
1549 assert(SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, infervar, NULL, TRUE), SCIPgetVarLbAtIndex(scip, infervar, NULL, FALSE)));
1562 SCIPdebugMsg(scip, "try to create conflict using bound widening order: inference variable, variable bound variable\n");
1564 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1588 /* compute the relaxed bound which is sufficient to propagate the inference upper bound of given variable */
1599 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1631 SCIP_Bool canwide, /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1663 inferinfo = getInferInfo(boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, vbdvar) : varGetUbIndex(propdata, vbdvar), boundtype);
1665 SCIP_CALL( SCIPinferVarLbProp(scip, var, newlb, prop, inferInfoToInt(inferinfo), force, &infeasible, &tightened) );
1670 /* the infeasible results comes from the fact that the new lower bound lies above the current upper bound */
1674 SCIPdebugMsg(scip, "tightening%s lower bound of variable <%s> to %g due the %s bound of variable <%s> led to infeasibility\n",
1675 (global ? " global" : ""), SCIPvarGetName(var), newlb, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1685 SCIP_CALL( analyzeConflictLowerbound(scip, propdata, var, newlb, vbdvar, boundtype, coef, constant, canwide) );
1691 SCIPdebugMsg(scip, "tightened%s lower bound of variable <%s> to %g due the %s bound of variable <%s>\n",
1692 (global ? " global" : ""), SCIPvarGetName(var), newlb, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1715 SCIP_Bool canwide, /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1747 inferinfo = getInferInfo(boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, vbdvar) : varGetUbIndex(propdata, vbdvar), boundtype);
1749 SCIP_CALL( SCIPinferVarUbProp(scip, var, newub, prop, inferInfoToInt(inferinfo), force, &infeasible, &tightened) );
1754 /* the infeasible results comes from the fact that the new upper bound lies below the current lower bound */
1758 SCIPdebugMsg(scip, "tightening%s upper bound of variable <%s> to %g due the %s bound of variable <%s> led to infeasibility\n",
1759 (global ? " global" : ""), SCIPvarGetName(var), newub, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1769 SCIP_CALL( analyzeConflictUpperbound(scip, propdata, var, newub, vbdvar, boundtype, coef, constant, canwide) );
1775 SCIPdebugMsg(scip, "tightened%s upper bound of variable <%s> to %g due the %s bound of variable <%s>\n",
1776 (global ? " global" : ""), SCIPvarGetName(var), newub, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1813 /* we do not run the propagator in presolving, because we want to avoid doing the expensive creation of the graph twice */
1857 SCIP_CALL( SCIPpqueueInsert(propdata->propqueue, (void*)(size_t)(v + 1)) ); /*lint !e571 !e776*/
1864 /* return if no bound changes are in the priority queue (no changed bounds to handle since last propagation) */
1873 SCIPdebugMsg(scip, "varbound propagator: %d elements in the propagation queue\n", SCIPpqueueNElems(propdata->propqueue));
1875 /* get variable bound of highest priority from priority queue and try to deduce bound changes for other variables;
1903 /* we only propagate binary variables if the lower bound changed to 1.0 or the upper bound changed to 0.0 */
1912 /* if the lower bound of the startvar was changed, it was fixed to 1.0, otherwise it was fixed to 0.0;
1938 /* it might happen that implications point to inactive variables (normally, those are removed when a
1939 * variable becomes inactive, but in some cases, it cannot be done), we have to ignore these variables
1966 /* if the lower bound of the startvar was changed, it was fixed to 1.0, otherwise it was fixed to 0.0;
2037 SCIP_CALL( tightenVarLb(scip, prop, propdata, boundedvar, newbound, global, startvar, starttype, force,
2042 SCIP_CALL( tightenVarUb(scip, prop, propdata, boundedvar, newbound, global, startvar, starttype, force,
2097 /** presolving initialization method of propagator (called when presolving is about to begin) */
2111 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
2162 /** performs Tarjan's algorithm for strongly connected components in the implicitly given directed implication graph
2163 * 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
2164 * where lb(x) means that the lower bound of x should be changed, i.e., that x is fixed to 1, and vice versa.
2170 * This quadratic number can blow up the running time of Tarjan's algorithm, which is linear in the number of
2171 * nodes and arcs of the graph. However, it suffices to consider only k of these arcs during the course of the algorithm.
2172 * 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,
2173 * 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
2174 * that the only arc pointing to an unvisited node is (lb(x_i'),ub(x_i)), all other edges can be disregarded.
2176 * Additionally, we try to identify infeasible fixings for binary variables. Those can be given by a path
2187 SCIP_Shortbool* nodeinfeasible, /**< array to store whether the fixing of a node was detected to be infeasible */
2189 int* predstackidx, /**< for each node on the stack: stack position of its predecessor in the Tarjan search */
2190 int* stacknextclique, /**< array of size number of nodes to store the next clique to be regarded in
2192 int* stacknextcliquevar, /**< array of size number of nodes to store the next variable in the next clique to be
2196 int* cliquefirstentry, /**< node from which a clique was entered for the first time; needed because when
2199 int* cliquecurrentexit, /**< for cliques which define an arc on the current path: target node of this arc */
2245 /* we run until no more bounds indices are on the stack, i.e., no further nodes are connected to the startnode */
2278 SCIPdebugMsg(scip, "variable %s(%s) has %d cliques\n", indexGetBoundString(curridx), SCIPvarGetName(startvar),
2325 /* we did not look at this clique before from the current node, i.e., we did not backtrack now from another
2345 int cliquefirstentryidx = (cliquefirstentry[clqidx] > 0 ? cliquefirstentry[clqidx] : -cliquefirstentry[clqidx]) - 1;
2351 * Since these two assignments together violate the clique and the second assignment is implied by the first,
2356 SCIPdebugMsg(scip, "infeasible assignment (1): %s(%s)\n", indexGetBoundString(cliquefirstentryidx),
2360 /* the first entry point of the clique was also implied by the current startnode, so this node implies
2383 /* the last node by which the clique was exited is not the negation of the current node and still on
2394 /* clique is entered for the second time; there is only one edge left to investigate, namely the edge to
2473 /* we stopped because we found an unhandled node and not because we reached the end of the list */
2484 /* the negated node corresponding to the next node is already on the stack -> the negated assignment is
2493 /* the negated node corresponding to the next node was reached from the same startnode -> the startnode is
2515 SCIPdebugMsg(scip, "clique: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
2529 SCIPdebugMsg(scip, "put %s(%s) on stack[%d]\n", indexGetBoundString(dfsstack[stacksize-1]), SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize-1])]), stacksize-1);
2555 SCIPdebugMsgPrint(scip, " %s(%s)", indexGetBoundString(idx), SCIPvarGetName(vars[getVarIndex(idx)]));
2557 SCIPdebugMsg(scip, "remove %s(%s) from stack[%d]\n", indexGetBoundString(dfsstack[stacksize]), SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize])]), stacksize);
2570 SCIPdebugMsg(scip, "remove %s(%s) from stack[%d]\n", indexGetBoundString(dfsstack[stacksize]), SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize])]), stacksize);
2577 /* in a pure dfs, the node would now leave the stack, add it to the array of nodes in reverse topological order */
2607 SCIP_Shortbool* nodeinfeasible, /**< array to store whether the fixing of a node was detected to be infeasible */
2613 int* nfixedvars, /**< pointer to number of fixed variables, increment when fixing another one */
2614 int* naggrvars, /**< pointer to number of aggregated variables, increment when aggregating another one */
2655 /* clear clean buffer array (if we did not enter the block above or stopped early due to an infeasibility) */
2692 SCIPvarGetName(vars[getVarIndex(sccvars[v])]), lower == isIndexLowerbound(sccvars[v]) ? 0.0 : 1.0,
2714 /** presolving method of propagator: search for strongly connected components in the implication graph and
2715 * aggregate all variables within a component; additionally, identifies infeasible variable assignments
2716 * 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
2717 * The identification of such assignments depends on the order in which variable bounds are processed;
2718 * therefore, we are doing a second run with the bounds processed in (almost) topological order.
2763 if( presoltiming == SCIP_PRESOLTIMING_MEDIUM && ncliques > propdata->maxcliquesmedium * SCIPgetNBinVars(scip) )
2771 if( SCIPgetNCliquesCreated(scip) < (1.0 + propdata->minnewcliques) * propdata->lastpresolncliques )
2824 /* aggregate all variables within a SCC and fix all variables for which one bounds was proven infeasible */
2839 /* we already fixed or aggregated some variables in the first run, so we better clean up the cliques */
2880 SCIP_CALL( tarjan(scip, startpos, &startindex, nodeonstack, nodeindex, nodelowlink, nodeinfeasible,
2888 /* aggregate all variables within a SCC and fix all variables for which one bounds was proven infeasible */
2984 inferidx = boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, infervar) : varGetUbIndex(propdata, infervar);
2998 /* compute the relaxed bound which is sufficient to propagate the inference bound of given variable */
3040 SCIPdebugMsg(scip, "eventexec (type=%llu): try to add sort index %d: %s(%s) to priority queue\n", SCIPeventGetType(event),
3044 if( SCIPeventGetType(event) == SCIP_EVENTTYPE_GUBCHANGED && SCIPvarIsBinary(SCIPeventGetVar(event))
3048 if( SCIPeventGetType(event) == SCIP_EVENTTYPE_GLBCHANGED && SCIPvarIsBinary(SCIPeventGetVar(event))
3053 assert(SCIPvarGetType(propdata->vars[getVarIndex(propdata->topoorder[idx])]) != SCIP_VARTYPE_BINARY
3059 SCIP_CALL( SCIPpqueueInsert(propdata->propqueue, (void*)(size_t)(idx + 1)) ); /*lint !e571 !e776*/
3078 {
3089 SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
3099 SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolVbounds, PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS,
3103 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &propdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
3107 "propagating/" PROP_NAME "/usebdwidening", "should bound widening be used to initialize conflict analysis?",
3119 "propagating/" PROP_NAME "/dotoposort", "should the bounds be topologically sorted in advance?",
3122 "propagating/" PROP_NAME "/sortcliques", "should cliques be regarded for the topological sort?",
3125 "propagating/" PROP_NAME "/detectcycles", "should cycles in the variable bound graph be identified?",
3128 "propagating/" PROP_NAME "/minnewcliques", "minimum percentage of new cliques to trigger another clique table analysis",
3132 &propdata->maxcliquesmedium, FALSE, DEFAULT_MAXCLIQUESMEDIUM, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3134 "maximum number of cliques per variable to run clique table analysis in exhaustive presolving",
3135 &propdata->maxcliquesexhaustive, FALSE, DEFAULT_MAXCLIQUESEXHAUSTIVE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3140 /** returns TRUE if the propagator has the status that all variable lower and upper bounds are propgated */
3144 {
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
static SCIP_RETCODE addVbound(SCIP *scip, SCIP_PROPDATA *propdata, int startidx, int endidx, SCIP_Real coef, SCIP_Real constant)
Definition: prop_vbounds.c:446
Definition: type_result.h:33
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
Definition: scip_conflict.c:292
Definition: struct_var.h:99
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx)
Definition: prop_vbounds.c:1331
public methods for SCIP parameter handling
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1996
SCIP_RETCODE SCIPsetPropInitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITPRE((*propinitpre)))
Definition: scip_prop.c:238
SCIP_RETCODE SCIPcleanupCliques(SCIP *scip, SCIP_Bool *infeasible)
Definition: scip_var.c:7513
static SCIP_Real computeRelaxedLowerbound(SCIP *scip, SCIP_VAR *var, SCIP_Real inferlb, SCIP_Real coef, SCIP_Real constant)
Definition: prop_vbounds.c:1391
Definition: struct_scip.h:59
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5184
static SCIP_RETCODE dropEvents(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_vbounds.c:396
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:5876
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:1536
public methods for memory management
Definition: type_conflict.h:50
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:113
public methods for implications, variable bounds, and cliques
Definition: struct_misc.h:69
public methods for conflict handler plugins and conflict analysis
Definition: type_result.h:49
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5301
Definition: struct_var.h:198
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition: scip_conflict.c:314
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3131
SCIP_EXPORT SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17957
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:5991
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:862
Definition: type_var.h:53
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip_conflict.c:343
static SCIP_DECL_PROPINITPRE(propInitpreVbounds)
Definition: prop_vbounds.c:2102
public methods for problem variables
SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub)
Definition: scip_var.c:4646
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:48
SCIP_EXPORT SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17986
static SCIP_BOUNDTYPE inferInfoGetBoundtype(INFERINFO inferinfo)
Definition: prop_vbounds.c:253
SCIP_RETCODE SCIPanalyzeConflict(SCIP *scip, int validdepth, SCIP_Bool *success)
Definition: scip_conflict.c:663
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:119
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:1421
SCIP_RETCODE SCIPaddConflictRelaxedLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedlb)
Definition: scip_conflict.c:377
public methods for SCIP variables
SCIP_Real SCIPgetConflictVarUb(SCIP *scip, SCIP_VAR *var)
Definition: scip_conflict.c:633
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:142
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:1620
public methods for numerical tolerances
SCIP_RETCODE SCIPincludePropVbounds(SCIP *scip)
Definition: prop_vbounds.c:3078
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3220
public methods for the branch-and-bound tree
static SCIP_Real computeRelaxedUpperbound(SCIP *scip, SCIP_VAR *var, SCIP_Real inferub, SCIP_Real coef, SCIP_Real constant)
Definition: prop_vbounds.c:1506
SCIP_Real SCIPgetConflictVarLb(SCIP *scip, SCIP_VAR *var)
Definition: scip_conflict.c:609
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:325
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:129
variable upper and lower bound propagator
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3362
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:92
Definition: struct_misc.h:128
Definition: type_result.h:35
SCIP_EXPORT int * SCIPvarGetImplIds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18002
SCIP_EXPORT int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17940
public methods for event handler plugins and event handlers
SCIP_RETCODE SCIPexecPropVbounds(SCIP *scip, SCIP_Bool force, SCIP_RESULT *result)
Definition: prop_vbounds.c:3161
Definition: type_lp.h:47
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:158
static int varGetUbIndex(SCIP_PROPDATA *propdata, SCIP_VAR *var)
Definition: prop_vbounds.c:307
Definition: type_retcode.h:33
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip_prop.c:222
Definition: type_result.h:42
static SCIP_DECL_PROPEXITSOL(propExitsolVbounds)
Definition: prop_vbounds.c:2116
Definition: struct_prop.h:37
static SCIP_RETCODE initData(SCIP *scip, SCIP_PROP *prop, SCIP_Bool *infeasible)
Definition: prop_vbounds.c:1160
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip_conflict.c:410
public data structures and miscellaneous methods
SCIP_EXPORT SCIP_Bool SCIPvarHasImplic(SCIP_VAR *var, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype)
Definition: var.c:10915
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:391
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3013
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:2605
Definition: type_set.h:40
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:789
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:505
SCIP_RETCODE SCIPaddConflictRelaxedUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedub)
Definition: scip_conflict.c:445
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8255
SCIP_EXPORT SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18025
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:825
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:95
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:130
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2132
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip_prop.c:303
static SCIP_RETCODE relaxVbdvar(SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd)
Definition: prop_vbounds.c:1367
static int varGetLbIndex(SCIP_PROPDATA *propdata, SCIP_VAR *var)
Definition: prop_vbounds.c:295
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:2183
public methods for managing events
general public methods
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)))
Definition: misc.c:1235
static INFERINFO getInferInfo(int pos, SCIP_BOUNDTYPE boundtype)
Definition: prop_vbounds.c:273
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:1704
static SCIP_RETCODE catchEvents(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_vbounds.c:337
Definition: type_lp.h:48
public methods for message output
SCIP_EXPORT SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
Definition: var.c:17886
Definition: struct_implics.h:66
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
public methods for message handling
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_prop.c:270
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6329
SCIP_EXPORT SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17972
public methods for propagator plugins
static SCIP_RETCODE propagateVbounds(SCIP *scip, SCIP_PROP *prop, SCIP_Bool force, SCIP_RESULT *result)
Definition: prop_vbounds.c:1788
static SCIP_DECL_SORTPTRCOMP(compVarboundIndices)
Definition: prop_vbounds.c:493
Definition: type_set.h:44
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: scip_var.c:1798
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:345
static SCIP_DECL_PROPRESPROP(propRespropVbounds)
Definition: prop_vbounds.c:2950
SCIP_EXPORT int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18014
Definition: type_retcode.h:43
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:105
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:8380
Definition: objbenders.h:33
public methods for global and local (sub)problems
SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb)
Definition: scip_var.c:4614
SCIP_EXPORT SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
Definition: var.c:17928
Definition: type_result.h:39
Definition: struct_event.h:195
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6209
public methods for propagators
static SCIP_RETCODE topologicalSort(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool *infeasible)
Definition: prop_vbounds.c:1113
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:850
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1334
memory allocation routines