prop_vbounds.c
Go to the documentation of this file.
24 * This propagator uses global bound information provided by SCIP to deduce global and local bound changes.
27 * - cliques (set of binary variables, each with a corresponding value, of which at most one variable can get the value)
28 * - variable lower/upper bounds (bounds of arbitrary variables that depend linearly on the value of another variable)
30 * The propagator does not look at a variable in whole, but at one point in time only handles one specific bound (lower
31 * or upper) of a variable and deduces changes for lower or upper bounds of other variables. The concept is as follows:
35 * Implications and cliques are stored in a way such that given a variable and its new value, we can access all bound
36 * changes that can be deduced from setting the variable to that value. However, for variable bounds, this currently
37 * does not hold, they are only stored in the other direction, i.e. for a bound of a given variable, we have a list
38 * of all other bounds of variables that directly influence the bound of the given variable and a linear function
40 * For the propagation, we need the other direction, thus we store it in the propagator data when the branch-and-bound
45 * We compute a topological order of the bounds of variables. This is needed to define an order in which we will
46 * regard bounds of variables in the propagation process in order to avoid unneccessarily regarding the same variable
47 * bound multiple times because it was changed in the meantime when propagating another bound of a variable.
48 * Therefore, we implictly regard a directed graph, in which each node corresponds to a bound of a variable and there
49 * exists a directed edge from one node to another, if the bound corresponding to the former node influences the
50 * bound corresponding to the latter node. This is done by iteratively running a DFS until all nodes were visited.
51 * Note that there might be cycles in the graph, which are randomly broken, so the order is only almost topological.
55 * For each bound of a variable, which can trigger bound changes of other variables, the propagator catches all
56 * events informing about a global change of the bound or a local tightening of the bound. The event handler
57 * then adds the bound of the variable to a priority queue, with the key in the priority queue corresponding
62 * As long as there are bounds contained in the priority queue, the propagator pops one bound from the queue, which
63 * is the one most at the beginning of the topological sort, so it should not be influenced by propagating other
64 * bounds currently contained in the queue. Starting at this bound, all implication, clique, and variable bound
65 * information is used to deduce tigther bounds for other variables and change the bounds, if a tighter one is found.
66 * These bound changes trigger an event that will lead to adding the corresponding bound to the priority queue,
67 * if it is not contained, yet. The process is iterated until the priority queue contains no more bounds.
69 * Additionally, the propagator analyzes the conflict/clique graph during presolving. It uses Tarjan's algorithm to
70 * search for strongly connected components, for each of which all variables can be aggregated to one. Additionally,
71 * it may detect invalid assignments of binary variables and fix the variable to the only possible value left.
74 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
107 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
109 #define PROP_PRESOL_PRIORITY -90000 /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers */
111 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no
130 #define DEFAULT_USEBDWIDENING TRUE /**< should bound widening be used to initialize conflict analysis? */
136 #define DEFAULT_DETECTCYCLES FALSE /**< should cycles in the variable bound graph be identified? */
137 #define DEFAULT_MINNEWCLIQUES 0.1 /**< minimum number of new cliques to trigger another clique table analysis */
138 #define DEFAULT_MAXCLIQUESMEDIUM 50.0 /**< maximum number of cliques per variable to run clique table analysis in
140 #define DEFAULT_MAXCLIQUESEXHAUSTIVE 100.0 /**< maximum number of cliques per variable to run clique table analysis in
149 * The propagator works on indices representing a bound of a variable. This index will be called bound index in the
150 * following. For a given active variable with problem index i (note that active variables have problem indices
151 * between 0 and nactivevariable - 1), the bound index of its lower bound is 2*i, the bound index of its upper
152 * bound is 2*i + 1. The other way around, a given bound index i corresponds to the variable with problem index
154 * The following macros can be used to convert bound index into variable problem index and boundtype and vice versa.
176 SCIP_VAR** vars; /**< array containing all variable which are considered within the propagator */
187 SCIP_Real** vboundcoefs; /**< array storing for each bound index the coefficients in the variable
190 SCIP_Real** vboundconstants; /**< array storing for each bound index the constants in the variable
195 int nbounds; /**< number of bounds of variables regarded (two times number of active variables) */
197 SCIP_PQUEUE* propqueue; /**< priority queue to handle the bounds of variables that were changed and have to be propagated */
198 SCIP_Bool* inqueue; /**< boolean array to store whether a bound of a variable is already contained in propqueue */
200 SCIP_Real minnewcliques; /**< minimum percentage of new cliques to trigger another clique table analysis */
201 SCIP_Real maxcliquesmedium; /**< maximum number of cliques per variable to run clique table analysis in medium presolving */
202 SCIP_Real maxcliquesexhaustive;/**< maximum number of cliques per variable to run clique table analysis in exhaustive presolving */
232 {
245 {
254 {
265 {
274 )
296 )
313 )
330 {
348 )
384 if( propdata->nvbounds[idx] == 0 && SCIPvarGetNImpls(var, lower) == 0 && SCIPvarGetNCliques(var, lower) == 0 )
396 SCIP_CALL( SCIPcatchVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*) (uintptr_t) v, NULL) ); /*lint !e571*/
407 )
444 SCIP_CALL( SCIPdropVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*) (uintptr_t) v, -1) ); /*lint !e571*/
473 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundboundedidx[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
474 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundcoefs[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
475 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundconstants[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
483 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundboundedidx[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
484 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundcoefs[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
485 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundconstants[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
497 /** comparison method for two indices in the topoorder array, preferring higher indices because the order is reverse
509 /* extract bound changes or infeasibility information from a cycle in the variable bound graph detected during
522 SCIP_Bool samebound, /**< does the cycle contain the same bound twice or both bounds of the same variable? */
549 /* the same bound of the variable was visited already earlier on the current path, so the start-point of the cycle
554 /* the other bound of the variable was visited earlier on the current path, so the start-point of the cycle
560 /* search for the start-point of the cycle; since the endpoint is at position stacksize - 1 we start at stacksize - 2
571 /* if we do not use implications, we assume the number of implications to be 0 (as we did before) */
574 /* stacknextedge[j] <= 0 --> the last outgoing edge traversed during dfs starting from node dfsstack[j] was given
596 * in cases a) and d), coef=-1.0 and constant=1.0; both nodes represent different types of bounds
606 /* since the coefficient and constant only depend on the type of bounds of the two nodes (see below), we do not
607 * need to search for the variable in the clique; however, if debug output is enabled, we want to print the
608 * clique, if more debugging is enabled, we explicitly check that the variable and bound we expect are in the
618 /* we processed at least one edge, so the next one should be -2 or smaller (we have a -1 offset) */
655 /* stacknextedge[j] > 0 --> the last outgoing edge traversed during dfs starting from node dfsstack[j] was given
656 * by an implication or vbound. Implications are looked at first, so if stacknextedge[j] <= ntmpimpls, it comes
729 constant = constant * propdata->vboundcoefs[dfsstack[j]][k] + propdata->vboundconstants[dfsstack[j]][k];
741 * (the relation depends on islower, i.e., whether the last node in the cycle is a lower or upper bound)
775 SCIPdebugMsg(scip, "-> found new lower bound: <%s>[%g,%g] >= %g\n", SCIPvarGetName(vars[getVarIndex(cycleidx)]),
776 SCIPvarGetLbLocal(vars[getVarIndex(cycleidx)]), SCIPvarGetUbLocal(vars[getVarIndex(cycleidx)]), newbound);
777 SCIP_CALL( SCIPtightenVarLb(scip, vars[getVarIndex(cycleidx)], newbound, FALSE, infeasible, &tightened) );
781 SCIPdebugMsg(scip, "-> found new upper bound: <%s>[%g,%g] <= %g\n", SCIPvarGetName(vars[getVarIndex(cycleidx)]),
782 SCIPvarGetLbLocal(vars[getVarIndex(cycleidx)]), SCIPvarGetUbLocal(vars[getVarIndex(cycleidx)]), newbound);
783 SCIP_CALL( SCIPtightenVarUb(scip, vars[getVarIndex(cycleidx)], newbound, FALSE, infeasible, &tightened) );
795 /** performs depth-first-search in the implicitly given directed graph from the given start index */
821 /* for cycle detection, we need to mark currently active nodes, otherwise we just mark them as visited */
843 /* we run until no more bounds indices are on the stack, i.e. all changed bounds were propagated */
865 /* stacknextedge is negative, if the last visited edge from the current node belongs to a clique;
903 /* we reached a variable that was already visited on the active path, so we have a cycle in the variable
932 /* we stopped because we found an unhandled node and not because we reached the end of the list */
939 SCIPdebugMsg(scip, "clique: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
978 /* it might happen that implications point to inactive variables (normally, those are removed when a
979 * variable becomes inactive, but in some cases, it cannot be done), we have to ignore these variables
984 /* implication is just a shortcut, so we dont regard it now, because will later go the long way, anyway;
993 /* we reached a variable that was already visited on the active path, so we have a cycle in the variable
1016 /* we stopped because we found an unhandled node and not because we reached the end of the list */
1021 SCIPdebugMsg(scip, "impl: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
1059 && !SCIPisFeasGE(scip, SCIPvarGetLbGlobal(vars[getVarIndex(idx)]), SCIPvarGetUbGlobal(vars[getVarIndex(idx)])) )
1066 /* we reached a variable that was already visited on the active path, so we have a cycle in the variable
1084 /* we stopped because we found an unhandled node and not because we reached the end of the list */
1089 SCIPdebugMsg(scip, "vbound: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
1107 SCIPdebugMsg(scip, "topoorder[%d] = %s(%s)\n", *ndfsnodes, getBoundString(lower), SCIPvarGetName(startvar));
1146 /* while there are unvisited nodes, run dfs starting from one of these nodes; the dfs orders are stored in the
1147 * topoorder array, later dfs calls are just appended after the stacks of previous dfs calls, which gives us a
1154 SCIP_CALL( dfs(scip, propdata, i, visited, dfsstack, stacknextedge, propdata->topoorder, &nsortednodes, infeasible) );
1212 /* we need to copy the variable since this array is the basis of the propagator and the corresponding variable array
1295 /* if the coefficient is positive, the type of bound is the same for the bounded and the bounding variable */
1303 * However, it might happen that vbvar was integer when the variable bound was added, but was converted
1304 * to a binary variable later during presolving when its upper bound was changed to 1. In this case,
1310 SCIPdebugMsg(scip, "varbound <%s> %s %g * <%s> + %g not added to propagator data due to reverse implication\n",
1344 SCIP_BDCHGIDX* bdchgidx /**< the index of the bound change, representing the point of time where
1371 /** relaxes bound of give variable as long as the given inference bound still leads to a cutoff and add that bound
1379 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where
1397 /** compute the relaxed bound which is sufficient to propagate the inference lower bound of given variable */
1414 /* check the computed relaxed lower/upper bound is a proper reason for the inference bound which has to be explained */
1425 /** analyzes an infeasibility which was reached by updating the lower bound of the inference variable above its upper
1445 assert(SCIPisEQ(scip, SCIPvarGetUbLocal(infervar), SCIPgetVarUbAtIndex(scip, infervar, NULL, FALSE)));
1446 assert(SCIPisEQ(scip, SCIPgetVarUbAtIndex(scip, infervar, NULL, TRUE), SCIPgetVarUbAtIndex(scip, infervar, NULL, FALSE)));
1459 SCIPdebugMsg(scip, "try to create conflict using bound widening order: inference variable, variable bound variable\n");
1461 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1485 /* compute the relaxed bound which is sufficient to propagate the inference lower bound of given variable */
1496 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1512 /** compute the relaxed bound which is sufficient to propagate the inference upper bound of given variable */
1529 /* check the computed relaxed lower/upper bound is a proper reason for the inference bound which has to be explained */
1540 /** analyzes an infeasibility which was reached by updating the upper bound of the inference variable below its lower
1553 SCIP_Bool canwide /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1559 assert(SCIPisEQ(scip, SCIPvarGetLbLocal(infervar), SCIPgetVarLbAtIndex(scip, infervar, NULL, FALSE)));
1560 assert(SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, infervar, NULL, TRUE), SCIPgetVarLbAtIndex(scip, infervar, NULL, FALSE)));
1573 SCIPdebugMsg(scip, "try to create conflict using bound widening order: inference variable, variable bound variable\n");
1575 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1599 /* compute the relaxed bound which is sufficient to propagate the inference upper bound of given variable */
1610 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1642 SCIP_Bool canwide, /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1674 inferinfo = getInferInfo(boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, vbdvar) : varGetUbIndex(propdata, vbdvar), boundtype);
1676 SCIP_CALL( SCIPinferVarLbProp(scip, var, newlb, prop, inferInfoToInt(inferinfo), force, &infeasible, &tightened) );
1681 /* the infeasible results comes from the fact that the new lower bound lies above the current upper bound */
1685 SCIPdebugMsg(scip, "tightening%s lower bound of variable <%s> to %g due the %s bound of variable <%s> led to infeasibility\n",
1686 (global ? " global" : ""), SCIPvarGetName(var), newlb, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1696 SCIP_CALL( analyzeConflictLowerbound(scip, propdata, var, newlb, vbdvar, boundtype, coef, constant, canwide) );
1702 SCIPdebugMsg(scip, "tightened%s lower bound of variable <%s> to %g due the %s bound of variable <%s>\n",
1703 (global ? " global" : ""), SCIPvarGetName(var), newlb, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1726 SCIP_Bool canwide, /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1758 inferinfo = getInferInfo(boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, vbdvar) : varGetUbIndex(propdata, vbdvar), boundtype);
1760 SCIP_CALL( SCIPinferVarUbProp(scip, var, newub, prop, inferInfoToInt(inferinfo), force, &infeasible, &tightened) );
1765 /* the infeasible results comes from the fact that the new upper bound lies below the current lower bound */
1769 SCIPdebugMsg(scip, "tightening%s upper bound of variable <%s> to %g due the %s bound of variable <%s> led to infeasibility\n",
1770 (global ? " global" : ""), SCIPvarGetName(var), newub, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1780 SCIP_CALL( analyzeConflictUpperbound(scip, propdata, var, newub, vbdvar, boundtype, coef, constant, canwide) );
1786 SCIPdebugMsg(scip, "tightened%s upper bound of variable <%s> to %g due the %s bound of variable <%s>\n",
1787 (global ? " global" : ""), SCIPvarGetName(var), newub, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1826 /* we do not run the propagator in presolving, because we want to avoid doing the expensive creation of the graph twice */
1870 SCIP_CALL( SCIPpqueueInsert(propdata->propqueue, (void*)(size_t)(v + 1)) ); /*lint !e571 !e776*/
1877 /* return if no bound changes are in the priority queue (no changed bounds to handle since last propagation) */
1888 SCIPdebugMsg(scip, "varbound propagator: %d elements in the propagation queue\n", SCIPpqueueNElems(propdata->propqueue));
1890 /* get variable bound of highest priority from priority queue and try to deduce bound changes for other variables;
1903 /* do not directly set propdata->inqueue[topopos] = FALSE: we allow only one propagation sweep through the
1922 /* we only propagate binary variables if the lower bound changed to 1.0 or the upper bound changed to 0.0 */
1931 /* if the lower bound of the startvar was changed, it was fixed to 1.0, otherwise it was fixed to 0.0;
1957 /* it might happen that implications point to inactive variables (normally, those are removed when a
1958 * variable becomes inactive, but in some cases, it cannot be done), we have to ignore these variables
1987 /* if the lower bound of the startvar was changed, it was fixed to 1.0, otherwise it was fixed to 0.0;
2061 SCIP_CALL( tightenVarLb(scip, prop, propdata, boundedvar, newbound, global, startvar, starttype, force,
2066 SCIP_CALL( tightenVarUb(scip, prop, propdata, boundedvar, newbound, global, startvar, starttype, force,
2083 assert( SCIPpqueueFind(propdata->propqueue, (void*)(size_t) (queuelist[v] + 1)) == -1 ); /*lint !e571*//*lint !e776*/
2140 /** presolving initialization method of propagator (called when presolving is about to begin) */
2154 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
2205 /** performs Tarjan's algorithm for strongly connected components in the implicitly given directed implication graph
2206 * 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
2207 * where lb(x) means that the lower bound of x should be changed, i.e., that x is fixed to 1, and vice versa.
2213 * This quadratic number can blow up the running time of Tarjan's algorithm, which is linear in the number of
2214 * nodes and arcs of the graph. However, it suffices to consider only k of these arcs during the course of the algorithm.
2215 * 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,
2216 * 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
2217 * that the only arc pointing to an unvisited node is (lb(x_i'),ub(x_i)), all other edges can be disregarded.
2219 * Additionally, we try to identify infeasible fixings for binary variables. Those can be given by a path
2230 SCIP_Shortbool* nodeinfeasible, /**< array to store whether the fixing of a node was detected to be infeasible */
2232 int* predstackidx, /**< for each node on the stack: stack position of its predecessor in the Tarjan search */
2233 int* stacknextclique, /**< array of size number of nodes to store the next clique to be regarded in
2235 int* stacknextcliquevar, /**< array of size number of nodes to store the next variable in the next clique to be
2239 int* cliquefirstentry, /**< node from which a clique was entered for the first time; needed because when
2242 int* cliquecurrentexit, /**< for cliques which define an arc on the current path: target node of this arc */
2288 /* we run until no more bounds indices are on the stack, i.e., no further nodes are connected to the startnode */
2321 SCIPdebugMsg(scip, "variable %s(%s) has %d cliques\n", indexGetBoundString(curridx), SCIPvarGetName(startvar),
2368 /* we did not look at this clique before from the current node, i.e., we did not backtrack now from another
2388 int cliquefirstentryidx = (cliquefirstentry[clqidx] > 0 ? cliquefirstentry[clqidx] : -cliquefirstentry[clqidx]) - 1;
2394 * Since these two assignments together violate the clique and the second assignment is implied by the first,
2399 SCIPdebugMsg(scip, "infeasible assignment (1): %s(%s)\n", indexGetBoundString(cliquefirstentryidx),
2403 /* the first entry point of the clique was also implied by the current startnode, so this node implies
2426 /* the last node by which the clique was exited is not the negation of the current node and still on
2437 /* clique is entered for the second time; there is only one edge left to investigate, namely the edge to
2516 /* we stopped because we found an unhandled node and not because we reached the end of the list */
2527 /* the negated node corresponding to the next node is already on the stack -> the negated assignment is
2536 /* the negated node corresponding to the next node was reached from the same startnode -> the startnode is
2558 SCIPdebugMsg(scip, "clique: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
2572 SCIPdebugMsg(scip, "put %s(%s) on stack[%d]\n", indexGetBoundString(dfsstack[stacksize-1]), SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize-1])]), stacksize-1);
2598 SCIPdebugMsgPrint(scip, " %s(%s)", indexGetBoundString(idx), SCIPvarGetName(vars[getVarIndex(idx)]));
2600 SCIPdebugMsg(scip, "remove %s(%s) from stack[%d]\n", indexGetBoundString(dfsstack[stacksize]), SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize])]), stacksize);
2613 SCIPdebugMsg(scip, "remove %s(%s) from stack[%d]\n", indexGetBoundString(dfsstack[stacksize]), SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize])]), stacksize);
2620 /* in a pure dfs, the node would now leave the stack, add it to the array of nodes in reverse topological order */
2650 SCIP_Shortbool* nodeinfeasible, /**< array to store whether the fixing of a node was detected to be infeasible */
2656 int* nfixedvars, /**< pointer to number of fixed variables, increment when fixing another one */
2657 int* naggrvars, /**< pointer to number of aggregated variables, increment when aggregating another one */
2698 /* clear clean buffer array (if we did not enter the block above or stopped early due to an infeasibility) */
2735 SCIPvarGetName(vars[getVarIndex(sccvars[v])]), lower == isIndexLowerbound(sccvars[v]) ? 0.0 : 1.0,
2757 /** presolving method of propagator: search for strongly connected components in the implication graph and
2758 * aggregate all variables within a component; additionally, identifies infeasible variable assignments
2759 * 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
2760 * The identification of such assignments depends on the order in which variable bounds are processed;
2761 * therefore, we are doing a second run with the bounds processed in (almost) topological order.
2806 if( presoltiming == SCIP_PRESOLTIMING_MEDIUM && ncliques > propdata->maxcliquesmedium * SCIPgetNBinVars(scip) )
2814 if( SCIPgetNCliquesCreated(scip) < (1.0 + propdata->minnewcliques) * propdata->lastpresolncliques )
2867 /* aggregate all variables within a SCC and fix all variables for which one bounds was proven infeasible */
2882 /* we already fixed or aggregated some variables in the first run, so we better clean up the cliques */
2923 SCIP_CALL( tarjan(scip, startpos, &startindex, nodeonstack, nodeindex, nodelowlink, nodeinfeasible,
2931 /* aggregate all variables within a SCC and fix all variables for which one bounds was proven infeasible */
3027 inferidx = boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, infervar) : varGetUbIndex(propdata, infervar);
3041 /* compute the relaxed bound which is sufficient to propagate the inference bound of given variable */
3083 SCIPdebugMsg(scip, "eventexec (type=%" SCIP_EVENTTYPE_FORMAT "): try to add sort index %d: %s(%s) to priority queue\n", SCIPeventGetType(event),
3087 if( SCIPeventGetType(event) == SCIP_EVENTTYPE_GUBCHANGED && SCIPvarIsBinary(SCIPeventGetVar(event))
3091 if( SCIPeventGetType(event) == SCIP_EVENTTYPE_GLBCHANGED && SCIPvarIsBinary(SCIPeventGetVar(event))
3096 assert(SCIPvarGetType(propdata->vars[getVarIndex(propdata->topoorder[idx])]) != SCIP_VARTYPE_BINARY
3102 SCIP_CALL( SCIPpqueueInsert(propdata->propqueue, (void*)(size_t)(idx + 1)) ); /*lint !e571 !e776*/
3117 {
3128 SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
3138 SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolVbounds, PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS,
3142 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &propdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
3146 "propagating/" PROP_NAME "/usebdwidening", "should bound widening be used to initialize conflict analysis?",
3158 "propagating/" PROP_NAME "/dotoposort", "should the bounds be topologically sorted in advance?",
3161 "propagating/" PROP_NAME "/sortcliques", "should cliques be regarded for the topological sort?",
3164 "propagating/" PROP_NAME "/detectcycles", "should cycles in the variable bound graph be identified?",
3167 "propagating/" PROP_NAME "/minnewcliques", "minimum percentage of new cliques to trigger another clique table analysis",
3171 &propdata->maxcliquesmedium, FALSE, DEFAULT_MAXCLIQUESMEDIUM, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3173 "maximum number of cliques per variable to run clique table analysis in exhaustive presolving",
3174 &propdata->maxcliquesexhaustive, FALSE, DEFAULT_MAXCLIQUESEXHAUSTIVE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3179 /** returns TRUE if the propagator has the status that all variable lower and upper bounds are propgated */
3183 {
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_prop.c:270
static SCIP_RETCODE addVbound(SCIP *scip, SCIP_PROPDATA *propdata, int startidx, int endidx, SCIP_Real coef, SCIP_Real constant)
Definition: prop_vbounds.c:457
Definition: type_result.h:33
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:1342
SCIP_RETCODE SCIPexecPropVbounds(SCIP *scip, SCIP_Bool force, SCIP_RESULT *result)
Definition: prop_vbounds.c:3200
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5200
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2125
public methods for SCIP parameter handling
static SCIP_Real computeRelaxedLowerbound(SCIP *scip, SCIP_VAR *var, SCIP_Real inferlb, SCIP_Real coef, SCIP_Real constant)
Definition: prop_vbounds.c:1402
Definition: struct_scip.h:59
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1989
static SCIP_RETCODE dropEvents(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_vbounds.c:407
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:1547
public methods for memory management
Definition: type_conflict.h:50
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:345
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:117
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_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18273
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:5892
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
Definition: struct_var.h:198
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:862
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:825
SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub)
Definition: scip_var.c:4642
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
SCIP_Bool SCIPvarHasImplic(SCIP_VAR *var, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype)
Definition: var.c:11107
SCIP_Real SCIPgetConflictVarUb(SCIP *scip, SCIP_VAR *var)
Definition: scip_conflict.c:633
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip_conflict.c:410
Definition: type_var.h:53
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3132
static SCIP_DECL_PROPINITPRE(propInitpreVbounds)
Definition: prop_vbounds.c:2145
public methods for problem variables
SCIP_RETCODE SCIPaddConflictRelaxedLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedlb)
Definition: scip_conflict.c:377
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition: scip_conflict.c:314
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5317
static SCIP_BOUNDTYPE inferInfoGetBoundtype(INFERINFO inferinfo)
Definition: prop_vbounds.c:254
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:123
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:1432
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb)
Definition: scip_var.c:4610
public methods for SCIP variables
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip_conflict.c:343
SCIP_RETCODE SCIPincludePropVbounds(SCIP *scip)
Definition: prop_vbounds.c:3117
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:1631
public methods for numerical tolerances
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
Definition: scip_conflict.c:292
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:1517
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:133
variable upper and lower bound propagator
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:96
Definition: struct_misc.h:128
Definition: type_result.h:35
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
public methods for event handler plugins and event handlers
Definition: type_lp.h:47
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: scip_var.c:1791
SCIP_Real SCIPgetConflictVarLb(SCIP *scip, SCIP_VAR *var)
Definition: scip_conflict.c:609
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6225
static int varGetUbIndex(SCIP_PROPDATA *propdata, SCIP_VAR *var)
Definition: prop_vbounds.c:313
Definition: type_retcode.h:33
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:6007
Definition: type_result.h:42
static SCIP_DECL_PROPEXITSOL(propExitsolVbounds)
Definition: prop_vbounds.c:2159
Definition: struct_prop.h:37
static SCIP_RETCODE initData(SCIP *scip, SCIP_PROP *prop, SCIP_Bool *infeasible)
Definition: prop_vbounds.c:1171
public data structures and miscellaneous methods
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18220
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:2648
SCIP_RETCODE SCIPaddConflictRelaxedUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedub)
Definition: scip_conflict.c:445
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:800
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:142
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:391
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:516
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8273
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18234
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip_prop.c:222
static SCIP_RETCODE relaxVbdvar(SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd)
Definition: prop_vbounds.c:1378
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)))
Definition: misc.c:1236
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18205
static int varGetLbIndex(SCIP_PROPDATA *propdata, SCIP_VAR *var)
Definition: prop_vbounds.c:296
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:2226
public methods for managing events
general public methods
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip_prop.c:303
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
static INFERINFO getInferInfo(int pos, SCIP_BOUNDTYPE boundtype)
Definition: prop_vbounds.c:274
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1335
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:1715
static SCIP_RETCODE catchEvents(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_vbounds.c:348
Definition: type_lp.h:48
public methods for message output
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:850
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:8398
Definition: struct_implics.h:66
public methods for message handling
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:158
public methods for propagator plugins
static SCIP_RETCODE propagateVbounds(SCIP *scip, SCIP_PROP *prop, SCIP_Bool force, SCIP_RESULT *result)
Definition: prop_vbounds.c:1799
static SCIP_DECL_SORTPTRCOMP(compVarboundIndices)
Definition: prop_vbounds.c:504
Definition: type_set.h:44
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6345
static SCIP_DECL_PROPRESPROP(propRespropVbounds)
Definition: prop_vbounds.c:2993
SCIPallocBlockMemory(scip, subsol))
Definition: type_retcode.h:43
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3221
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:325
SCIP_RETCODE SCIPsetPropInitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITPRE((*propinitpre)))
Definition: scip_prop.c:238
Definition: objbenders.h:33
SCIP_RETCODE SCIPcleanupCliques(SCIP *scip, SCIP_Bool *infeasible)
Definition: scip_var.c:7529
public methods for global and local (sub)problems
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_RETCODE SCIPanalyzeConflict(SCIP *scip, int validdepth, SCIP_Bool *success)
Definition: scip_conflict.c:663
Definition: type_result.h:39
Definition: struct_event.h:195
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
public methods for propagators
static SCIP_RETCODE topologicalSort(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool *infeasible)
Definition: prop_vbounds.c:1124
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
memory allocation routines