Scippy

SCIP

Solving Constraint Integer Programs

prop_vbounds.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file prop_vbounds.c
17  * @ingroup DEFPLUGINS_PROP
18  * @brief variable upper and lower bound propagator
19  * @author Stefan Heinz
20  * @author Jens Schulz
21  * @author Gerald Gamrath
22  * @author Marc Pfetsch
23  *
24  * This propagator uses global bound information provided by SCIP to deduce global and local bound changes.
25  * It can take into account
26  * - implications (bound change following from specific value of a binary variable)
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)
29  *
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:
32  *
33  * 1) Extract variable bound data
34  *
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
39  * describing how they do this.
40  * For the propagation, we need the other direction, thus we store it in the propagator data when the branch-and-bound
41  * solving process is about to begin.
42  *
43  * 2) Topological sorting of bounds of variable
44  *
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.
52  *
53  * 3) Collecting bound changes
54  *
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
58  * to the position of the bound in the topological sort.
59  *
60  * 4) Propagating Bounds
61  *
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.
68  *
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.
72  */
73 
74 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
75 
76 #include "blockmemshell/memory.h"
77 #include "scip/prop_vbounds.h"
78 #include "scip/pub_event.h"
79 #include "scip/pub_implics.h"
80 #include "scip/pub_message.h"
81 #include "scip/pub_misc.h"
82 #include "scip/pub_prop.h"
83 #include "scip/pub_var.h"
84 #include "scip/scip_conflict.h"
85 #include "scip/scip_event.h"
86 #include "scip/scip_general.h"
87 #include "scip/scip_mem.h"
88 #include "scip/scip_message.h"
89 #include "scip/scip_numerics.h"
90 #include "scip/scip_param.h"
91 #include "scip/scip_prob.h"
92 #include "scip/scip_prop.h"
93 #include "scip/scip_tree.h"
94 #include "scip/scip_var.h"
95 #include <string.h>
96 
97 /**@name Propagator properties
98  *
99  * @{
100  */
101 
102 #define PROP_NAME "vbounds"
103 #define PROP_DESC "propagates variable upper and lower bounds"
104 #define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_AFTERLPLOOP
105 #define PROP_PRIORITY 3000000 /**< propagator priority */
106 #define PROP_FREQ 1 /**< propagator frequency */
107 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
108 
109 #define PROP_PRESOL_PRIORITY -90000 /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers */
110 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM | SCIP_PRESOLTIMING_EXHAUSTIVE
111 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no
112  * limit) */
113 /**@} */
114 
115 /**@name Event handler properties
116  *
117  * @{
118  */
119 
120 #define EVENTHDLR_NAME "vbounds"
121 #define EVENTHDLR_DESC "bound change event handler for for vbounds propagator"
123 /**@} */
124 
125 /**@name Default parameter values
126  *
127  * @{
128  */
129 
130 #define DEFAULT_USEBDWIDENING TRUE /**< should bound widening be used to initialize conflict analysis? */
131 #define DEFAULT_USEIMPLICS FALSE /**< should implications be propagated? */
132 #define DEFAULT_USECLIQUES FALSE /**< should cliques be propagated? */
133 #define DEFAULT_USEVBOUNDS TRUE /**< should variable bounds be propagated? */
134 #define DEFAULT_DOTOPOSORT TRUE /**< should the bounds be topologically sorted in advance? */
135 #define DEFAULT_SORTCLIQUES FALSE /**< should cliques be regarded for the topological sort? */
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
139  * medium presolving */
140 #define DEFAULT_MAXCLIQUESEXHAUSTIVE 100.0 /**< maximum number of cliques per variable to run clique table analysis in
141  * exhaustive presolving */
143 /**@} */
144 
145 /**@name Propagator defines
146  *
147  * @{
148  *
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
153  * i/2 (rounded down), and to the lower bound, if i is even, to the upper bound if i is odd.
154  * The following macros can be used to convert bound index into variable problem index and boundtype and vice versa.
155  */
156 #define getLbIndex(idx) (2*(idx))
157 #define getUbIndex(idx) (2*(idx)+1)
158 #define getVarIndex(idx) ((idx)/2)
159 #define getBoundtype(idx) (((idx) % 2 == 0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER)
160 #define isIndexLowerbound(idx) ((idx) % 2 == 0)
161 #define getBoundString(lower) ((lower) ? "lb" : "ub")
162 #define getBoundtypeString(type) ((type) == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper")
163 #define indexGetBoundString(idx) (getBoundString(isIndexLowerbound(idx)))
164 #define getOtherBoundIndex(idx) ((idx) + 1 - 2 * ((idx) % 2))
166 /**@} */
168 /*
169  * Data structures
170  */
171 
172 /** propagator data */
173 struct SCIP_PropData
174 {
175  SCIP_EVENTHDLR* eventhdlr; /**< event handler for catching bound changes */
176  SCIP_VAR** vars; /**< array containing all variable which are considered within the propagator */
177  SCIP_HASHMAP* varhashmap; /**< hashmap mapping from variable to index in the vars array */
178  int* topoorder; /**< array mapping on the bounds of variables in topological order;
179  * or -1, if the bound that should be at that position has no outgoing
180  * implications, cliques, or vbounds;
181  * i.e., for i < j and topoorder[i] != -1 != topoorder[j], the variable
182  * and boundtype represented by index topoorder[i] are earlier in the
183  * topological order than those represented by index topoorder[j]
184  */
185  int** vboundboundedidx; /**< array storing for each bound index the bound indices of all bounds
186  * influenced by this bound through variable bounds */
187  SCIP_Real** vboundcoefs; /**< array storing for each bound index the coefficients in the variable
188  * bounds influencing the corresponding bound index stored in
189  * vboundboundedidx */
190  SCIP_Real** vboundconstants; /**< array storing for each bound index the constants in the variable
191  * bounds influencing the corresponding bound index stored in
192  * vboundboundedidx */
193  int* nvbounds; /**< array storing for each bound index the number of vbounds stored */
194  int* vboundsize; /**< array with sizes of vbound arrays for the nodes */
195  int nbounds; /**< number of bounds of variables regarded (two times number of active variables) */
196  int lastpresolncliques; /**< number of cliques created until the last call to the presolver */
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 */
199  SCIP_Bool initialized; /**< was the data for propagation already initialized? */
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 */
203  SCIP_Bool usebdwidening; /**< should bound widening be used to initialize conflict analysis? */
204  SCIP_Bool useimplics; /**< should implications be propagated? */
205  SCIP_Bool usecliques; /**< should cliques be propagated? */
206  SCIP_Bool usevbounds; /**< should variable bounds be propagated? */
207  SCIP_Bool dotoposort; /**< should the bounds be topologically sorted in advance? */
208  SCIP_Bool sortcliques; /**< should cliques be regarded for the topological sort? */
209  SCIP_Bool detectcycles; /**< should cycles in the variable bound graph be identified? */
210 };
211 
212 /** inference information */
213 struct InferInfo
214 {
215  union
216  {
217  struct
218  {
219  unsigned int pos:31; /**< position of the variable which forced that propagation */
220  unsigned int boundtype:1; /**< bound type which was the reason (0: lower, 1: upper) */
221  } asbits;
222  int asint; /**< inference information as a single int value */
223  } val;
224 };
225 typedef struct InferInfo INFERINFO;
226 
227 /** converts an integer into an inference information */
228 static
229 INFERINFO intToInferInfo(
230  int i /**< integer to convert */
231  )
232 {
233  INFERINFO inferinfo;
234 
235  inferinfo.val.asint = i;
236 
237  return inferinfo;
238 }
239 
240 /** converts an inference information into an int */
241 static
242 int inferInfoToInt(
243  INFERINFO inferinfo /**< inference information to convert */
244  )
245 {
246  return inferinfo.val.asint;
247 }
248 
249 /** returns the propagation rule stored in the inference information */
250 static
252  INFERINFO inferinfo /**< inference information to convert */
253  )
254 {
255  assert((SCIP_BOUNDTYPE)inferinfo.val.asbits.boundtype == SCIP_BOUNDTYPE_LOWER
256  || (SCIP_BOUNDTYPE)inferinfo.val.asbits.boundtype == SCIP_BOUNDTYPE_UPPER);
257  return (SCIP_BOUNDTYPE)inferinfo.val.asbits.boundtype;
258 }
259 
260 /** returns the position stored in the inference information */
261 static
262 int inferInfoGetPos(
263  INFERINFO inferinfo /**< inference information to convert */
264  )
265 {
266  return (int) inferinfo.val.asbits.pos;
267 }
268 
269 /** constructs an inference information out of a position of a variable and a boundtype */
270 static
271 INFERINFO getInferInfo(
272  int pos, /**< position of the variable which forced that propagation */
273  SCIP_BOUNDTYPE boundtype /**< propagation rule that deduced the value */
274  )
275 {
276  INFERINFO inferinfo;
277 
278  assert(boundtype == SCIP_BOUNDTYPE_LOWER || boundtype == SCIP_BOUNDTYPE_UPPER);
279  assert(pos >= 0);
280 
281  inferinfo.val.asbits.pos = (unsigned int) pos; /*lint !e732*/
282  inferinfo.val.asbits.boundtype = (unsigned int) boundtype; /*lint !e641*/
283 
284  return inferinfo;
285 }
286 
287 /*
288  * Local methods
289  */
290 
291 /* returns the lower bound index of a variable */
292 static
293 int varGetLbIndex(
294  SCIP_PROPDATA* propdata, /**< propagator data */
295  SCIP_VAR* var /**< variable to get the index for */
296  )
297 {
298  int i;
299 
300  i = SCIPhashmapGetImageInt(propdata->varhashmap, var);
301 
302  assert(SCIPhashmapExists(propdata->varhashmap, var) == (i != INT_MAX));
303  assert(i >= 0);
304 
305  return getLbIndex(i == INT_MAX ? -1 : i);
306 }
307 
308 /* returns the upper bound index of a variable */
309 static
310 int varGetUbIndex(
311  SCIP_PROPDATA* propdata, /**< propagator data */
312  SCIP_VAR* var /**< variable to get the index for */
313  )
314 {
315  int i;
316 
317  i = SCIPhashmapGetImageInt(propdata->varhashmap, var);
318 
319  assert(SCIPhashmapExists(propdata->varhashmap, var) == (i != INT_MAX));
320  assert(i >= 0);
321 
322  return getUbIndex(i == INT_MAX ? -1 : i);
323 }
324 
325 /** reset propagation data */
326 static
327 void resetPropdata(
328  SCIP_PROPDATA* propdata /**< propagator data */
329  )
330 {
331  propdata->vars = NULL;
332  propdata->varhashmap = NULL;
333  propdata->topoorder = NULL;
334  propdata->vboundboundedidx = NULL;
335  propdata->vboundcoefs = NULL;
336  propdata->vboundconstants = NULL;
337  propdata->nvbounds = NULL;
338  propdata->vboundsize = NULL;
339  propdata->nbounds = 0;
340  propdata->initialized = FALSE;
341 }
342 
343 /** catches events for variables */
344 static
346  SCIP* scip, /**< SCIP data structure */
347  SCIP_PROPDATA* propdata /**< propagator data */
348  )
349 {
350  SCIP_EVENTHDLR* eventhdlr;
351  SCIP_EVENTTYPE eventtype;
352  SCIP_VAR** vars;
353  SCIP_VAR* var;
354  SCIP_Bool lower;
355  int nbounds;
356  int v;
357  int idx;
358 
359  assert(scip != NULL);
360  assert(propdata != NULL);
361  assert(propdata->vars != NULL);
362  assert(propdata->topoorder != NULL);
363 
364  /* catch variable events according to computed eventtypes */
365  eventhdlr = propdata->eventhdlr;
366  assert(eventhdlr != NULL);
367 
368  vars = propdata->vars;
369  nbounds = propdata->nbounds;
370 
371  /* setup events */
372  for( v = 0; v < nbounds; ++v )
373  {
374  idx = propdata->topoorder[v];
375  assert(idx >= 0 && idx < nbounds);
376 
377  var = vars[getVarIndex(idx)];
378  lower = isIndexLowerbound(idx);
379 
380  /* if the bound does not influence another bound by implications, cliques, or vbounds,
381  * we do not create an event and do not catch changes of the bound;
382  * we mark this by setting the value in topoorder to -1
383  */
384  if( propdata->nvbounds[idx] == 0 && SCIPvarGetNImpls(var, lower) == 0 && SCIPvarGetNCliques(var, lower) == 0 )
385  {
386  propdata->topoorder[v] = -1;
387  continue;
388  }
389 
390  /* determine eventtype that we want to catch depending on boundtype of variable */
391  if( lower )
393  else
395 
396  SCIP_CALL( SCIPcatchVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*) (uintptr_t) v, NULL) ); /*lint !e571*/
397  }
398 
399  return SCIP_OKAY;
400 }
401 
402 /** drops events for variables */
403 static
405  SCIP* scip, /**< SCIP data structure */
406  SCIP_PROPDATA* propdata /**< propagator data */
407  )
408 {
409  SCIP_EVENTHDLR* eventhdlr;
410  SCIP_EVENTTYPE eventtype;
411  SCIP_VAR** vars;
412  SCIP_VAR* var;
413  SCIP_Bool lower;
414  int nbounds;
415  int v;
416  int idx;
417 
418  assert(propdata != NULL);
419 
420  eventhdlr = propdata->eventhdlr;
421  assert(eventhdlr != NULL);
422 
423  vars = propdata->vars;
424  nbounds = propdata->nbounds;
425 
426  for( v = 0; v < nbounds; ++v )
427  {
428  idx = propdata->topoorder[v];
429 
430  if( idx == -1 )
431  continue;
432 
433  assert(idx >= 0 && idx < nbounds);
434 
435  var = vars[getVarIndex(idx)];
436  lower = isIndexLowerbound(idx);
437 
438  /* determine eventtype that we catch and now want to drop depending on boundtype of variable */
439  if( lower )
441  else
443 
444  SCIP_CALL( SCIPdropVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*) (uintptr_t) v, -1) ); /*lint !e571*/
445  }
446 
447  return SCIP_OKAY;
448 }
449 
450 #define INITMEMSIZE 5
451 
452 /* adds a vbound to the propagator data to store it internally and allow forward propagation */
453 static
455  SCIP* scip, /**< SCIP data structure */
456  SCIP_PROPDATA* propdata, /**< propagator data */
457  int startidx, /**< index of bound of variable influencing the other variable */
458  int endidx, /**< index of bound of variable which is influenced */
459  SCIP_Real coef, /**< coefficient in the variable bound */
460  SCIP_Real constant /**< constant in the variable bound */
461  )
462 {
463  int nvbounds;
464 
465  assert(scip != NULL);
466  assert(propdata != NULL);
467 
468  if( propdata->vboundsize[startidx] == 0 )
469  {
470  /* allocate memory for storing vbounds */
471  propdata->vboundsize[startidx] = INITMEMSIZE;
472 
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*/
476  }
477  else if( propdata->nvbounds[startidx] >= propdata->vboundsize[startidx] )
478  {
479  /* reallocate memory for storing vbounds */
480  propdata->vboundsize[startidx] = SCIPcalcMemGrowSize(scip, propdata->nvbounds[startidx] + 1);
481  assert(propdata->nvbounds[startidx] < propdata->vboundsize[startidx]);
482 
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*/
486  }
487 
488  nvbounds = propdata->nvbounds[startidx];
489  propdata->vboundboundedidx[startidx][nvbounds] = endidx;
490  propdata->vboundcoefs[startidx][nvbounds] = coef;
491  propdata->vboundconstants[startidx][nvbounds] = constant;
492  (propdata->nvbounds[startidx])++;
493 
494  return SCIP_OKAY;
495 }
496 
497 /** comparison method for two indices in the topoorder array, preferring higher indices because the order is reverse
498  * topological
499  */
500 static
501 SCIP_DECL_SORTPTRCOMP(compVarboundIndices)
502 {
503  int idx1 = (int)(size_t)elem1;
504  int idx2 = (int)(size_t)elem2;
505 
506  return idx2 - idx1;
507 }
508 
509 /* extract bound changes or infeasibility information from a cycle in the variable bound graph detected during
510  * depth-first search
511  */
512 static
514  SCIP* scip, /**< SCIP data structure */
515  SCIP_PROPDATA* propdata, /**< propagator data */
516  int* dfsstack, /**< array of size number of nodes to store the stack;
517  * only needed for performance reasons */
518  int* stacknextedge, /**< array storing the next edge to be visited in dfs for all nodes on the
519  * stack/in the current path; negative numbers represent a clique,
520  * positive numbers an implication (smaller numbers) or a variable bound */
521  int stacksize, /**< current stack size */
522  SCIP_Bool samebound, /**< does the cycle contain the same bound twice or both bounds of the same variable? */
523  SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
524 
525  )
526 {
527  SCIP_VAR** vars;
528  SCIP_VAR* currvar;
529  SCIP_Bool currlower;
530 
531  SCIP_Real coef = 1.0;
532  SCIP_Real constant = 0.0;
533  SCIP_Bool islower;
534  SCIP_Real newbound;
535  int cycleidx;
536  int startidx;
537  int ntmpimpls;
538  int j;
539  int k;
540 
541  assert(scip != NULL);
542  assert(propdata != NULL);
543 
544  vars = propdata->vars;
545 
546  /* the last element on the stack is the end-point of the cycle */
547  cycleidx = dfsstack[stacksize - 1];
548 
549  /* the same bound of the variable was visited already earlier on the current path, so the start-point of the cycle
550  * has the same index
551  */
552  if( samebound )
553  startidx = cycleidx;
554  /* the other bound of the variable was visited earlier on the current path, so the start-point of the cycle
555  * has the index of the other bound
556  */
557  else
558  startidx = getOtherBoundIndex(cycleidx);
559 
560  /* search for the start-point of the cycle; since the endpoint is at position stacksize - 1 we start at stacksize - 2
561  * and go backwards
562  */
563  for( j = stacksize - 2; dfsstack[j] != startidx && j >= 0; --j ){};
564  assert(j >= 0);
565 
566  for( ; j < stacksize - 1; ++j )
567  {
568  currvar = vars[getVarIndex(dfsstack[j])];
569  currlower = isIndexLowerbound(dfsstack[j]);
570 
571  /* if we do not use implications, we assume the number of implications to be 0 (as we did before) */
572  ntmpimpls = (propdata->useimplics ? SCIPvarGetNImpls(currvar, currlower) : 0);
573 
574  /* stacknextedge[j] <= 0 --> the last outgoing edge traversed during dfs starting from node dfsstack[j] was given
575  * by a clique
576  */
577  if( stacknextedge[j] <= 0 )
578  {
579  SCIP_Bool nextlower = isIndexLowerbound(dfsstack[j+1]);
580 #if defined(SCIP_DEBUG) || defined(SCIP_MORE_DEBUG)
581  SCIP_CLIQUE** tmpcliques = SCIPvarGetCliques(currvar, currlower);
582  SCIP_VAR** cliquevars;
583  SCIP_Bool* cliquevals;
584  int ntmpcliques = SCIPvarGetNCliques(currvar, currlower);
585  int ncliquevars;
586  int v;
587 #endif
588  /* there are four cases:
589  * a) lb(x) -> ub(y) ==> clique(x,y,...) ==> y <= 1 - x
590  * b) lb(x) -> lb(y) ==> clique(x,~y,...) ==> y >= x
591  * c) ub(x) -> ub(y) ==> clique(~x,y,...) ==> y <= x
592  * d) ub(x) -> lb(y) ==> clique(~x,~y,...) ==> y >= 1 - x
593  *
594  * in cases b) and c), coef=1.0 and constant=0.0; these are the cases where both nodes represent
595  * the same type of bound
596  * in cases a) and d), coef=-1.0 and constant=1.0; both nodes represent different types of bounds
597  *
598  * we do not need to change the overall coef and constant in cases b) and c), but for the others
599  */
600  if( currlower != nextlower )
601  {
602  coef = -coef;
603  constant = -constant + 1.0;
604  }
605 
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
609  * clique
610  */
611 #if defined(SCIP_DEBUG) || defined(SCIP_MORE_DEBUG)
612  if( stacknextedge[j] == 0 )
613  {
614  k = ntmpcliques - 1;
615  }
616  else
617  {
618  /* we processed at least one edge, so the next one should be -2 or smaller (we have a -1 offset) */
619  assert(stacknextedge[j] <= -2);
620 
621  k = -stacknextedge[j] - 2;
622 
623  assert(k < ntmpcliques);
624  }
625 
626  cliquevars = SCIPcliqueGetVars(tmpcliques[k]);
627  cliquevals = SCIPcliqueGetValues(tmpcliques[k]);
628  ncliquevars = SCIPcliqueGetNVars(tmpcliques[k]);
629 #ifdef SCIP_DEBUG
630  SCIPdebugMsg(scip, "clique: ");
631  for( v = 0; v < ncliquevars; ++v )
632  {
633  SCIPdebugMsg(scip, "%s%s ", cliquevals[v] ? "" : "~", SCIPvarGetName(cliquevars[v]));
634  }
635  SCIPdebugMsg(scip, "(equation:%d)\n", SCIPcliqueIsEquation(tmpcliques[k]));
636 #endif
637 #ifdef SCIP_MORE_DEBUG
638  for( v = 0; v < ncliquevars; ++v )
639  {
640  if( cliquevars[v] == vars[getVarIndex(dfsstack[j+1])] && cliquevals[v] == !nextlower )
641  break;
642  }
643  assert(v < ncliquevars);
644 #endif
645 
646  SCIPdebugMsg(scip, "%s(%s) -- (*%g + %g)[clique(<%s%s>,<%s%s>,...)] --> %s(%s)\n",
647  indexGetBoundString(dfsstack[j]), SCIPvarGetName(currvar),
648  (currlower != nextlower ? -1.0 : 1.0),
649  (currlower != nextlower ? 1.0 : 0.0),
650  (currlower ? "" : "~"), SCIPvarGetName(currvar),
651  (nextlower ? "~" : ""), SCIPvarGetName(vars[getVarIndex(dfsstack[j+1])]),
652  indexGetBoundString(dfsstack[j+1]), SCIPvarGetName(currvar));
653 #endif
654  }
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
657  * from an implication
658  */
659  else if( stacknextedge[j] <= ntmpimpls )
660  {
661 #ifndef NDEBUG
662  SCIP_VAR** implvars = SCIPvarGetImplVars(currvar, currlower);
663 #endif
664  SCIP_BOUNDTYPE* impltypes = SCIPvarGetImplTypes(currvar, currlower);
665  SCIP_Real* implbounds = SCIPvarGetImplBounds(currvar, currlower);
666  SCIP_VAR* nextvar = vars[getVarIndex(dfsstack[j+1])];
667  SCIP_Real newconstant;
668  SCIP_Real newcoef;
669 
670  k = stacknextedge[j] - 1;
671 
672  assert(dfsstack[j+1] == (impltypes[k] == SCIP_BOUNDTYPE_LOWER ?
673  varGetLbIndex(propdata, implvars[k]) : varGetUbIndex(propdata, implvars[k])));
674 
675  if( impltypes[k] == SCIP_BOUNDTYPE_LOWER )
676  {
677  newcoef = implbounds[k] - SCIPvarGetLbLocal(nextvar);
678 
679  if( currlower )
680  {
681  newconstant = SCIPvarGetLbLocal(nextvar);
682  }
683  else
684  {
685  newconstant = implbounds[k];
686  newcoef *= -1.0;
687  }
688  }
689  else
690  {
691  assert(impltypes[k] == SCIP_BOUNDTYPE_UPPER);
692 
693  newcoef = SCIPvarGetUbLocal(nextvar) - implbounds[k];
694 
695  if( currlower )
696  {
697  newconstant = SCIPvarGetUbLocal(nextvar);
698  newcoef *= -1.0;
699  }
700  else
701  {
702  newconstant = implbounds[k];
703  }
704  }
705 
706  coef = coef * newcoef;
707  constant = constant * newcoef + newconstant;
708 
709  SCIPdebugMsg(scip, "%s(%s) -- (*%g + %g) --> %s(%s)\n",
710  indexGetBoundString(dfsstack[j]), SCIPvarGetName(vars[getVarIndex(dfsstack[j])]),
711  newcoef, newconstant,
712  indexGetBoundString(dfsstack[j+1]), SCIPvarGetName(vars[getVarIndex(dfsstack[j+1])]));
713  }
714  /* the edge was given by a variable bound relation */
715  else
716  {
717  assert(stacknextedge[j] > ntmpimpls);
718 
719  k = stacknextedge[j] - ntmpimpls - 1;
720  assert(k < propdata->nvbounds[dfsstack[j]]);
721  assert(propdata->vboundboundedidx[dfsstack[j]][k] == dfsstack[j+1]);
722 
723  SCIPdebugMsg(scip, "%s(%s) -- (*%g + %g) --> %s(%s)\n",
724  indexGetBoundString(dfsstack[j]), SCIPvarGetName(vars[getVarIndex(dfsstack[j])]),
725  propdata->vboundcoefs[dfsstack[j]][k], propdata->vboundconstants[dfsstack[j]][k],
726  indexGetBoundString(dfsstack[j+1]), SCIPvarGetName(vars[getVarIndex(dfsstack[j+1])]));
727 
728  coef = coef * propdata->vboundcoefs[dfsstack[j]][k];
729  constant = constant * propdata->vboundcoefs[dfsstack[j]][k] + propdata->vboundconstants[dfsstack[j]][k];
730  }
731  }
732 
733  SCIPdebugMsg(scip, "==> %s(%s) -- (*%g + %g) --> %s(%s)\n",
734  indexGetBoundString(startidx), SCIPvarGetName(vars[getVarIndex(startidx)]),
735  coef, constant,
736  indexGetBoundString(cycleidx), SCIPvarGetName(vars[getVarIndex(cycleidx)]));
737 
738  islower = isIndexLowerbound(cycleidx);
739 
740  /* we have a relation x <=/>= coef * x + constant now
741  * (the relation depends on islower, i.e., whether the last node in the cycle is a lower or upper bound)
742  * case 1) coef is 1.0 --> x cancels out and we have a statement 0 <=/>= constant.
743  * if we have a >= relation and constant is positive, we have a contradiction 0 >= constant
744  * if we have a <= relation and constant is negative, we have a contradiction 0 <= constant
745  * case 2) coef != 1.0 --> we have a relation x - coef * x <=/>= constant
746  * <=> (1 - coef) * x <=/>= constant
747  * if coef < 1.0 this gives us x >= constant / (1 - coef) (if islower=TRUE)
748  * or x <= constant / (1 - coef) (if islower=FALSE)
749  * if coef > 1.0, the relation signs need to be switched.
750  */
751  if( SCIPisEQ(scip, coef, 1.0) )
752  {
753  if( islower && SCIPisFeasPositive(scip, constant) )
754  {
755  SCIPdebugMsg(scip, "-> infeasible aggregated variable bound relation 0 >= %g\n", constant);
756  *infeasible = TRUE;
757  }
758  else if( !islower && SCIPisFeasNegative(scip, constant) )
759  {
760  SCIPdebugMsg(scip, "-> infeasible aggregated variable bound relation 0 <= %g\n", constant);
761  *infeasible = TRUE;
762  }
763  }
764  else
765  {
766  SCIP_Bool tightened;
767 
768  newbound = constant / (1.0 - coef);
769 
770  if( SCIPisGT(scip, coef, 1.0) )
771  islower = !islower;
772 
773  if( islower )
774  {
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) );
778  }
779  else
780  {
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) );
784  }
785 
786  if( tightened )
787  SCIPdebugMsg(scip, "---> applied new bound\n");
788  }
789 
790  return SCIP_OKAY;
791 }
792 
793 #define VISITED 1
794 #define ACTIVE 2
795 /** performs depth-first-search in the implicitly given directed graph from the given start index */
796 static
798  SCIP* scip, /**< SCIP data structure */
799  SCIP_PROPDATA* propdata, /**< propagator data */
800  int startnode, /**< node to start the depth-first-search */
801  int* visited, /**< array to store for each node, whether it was already visited */
802  int* dfsstack, /**< array of size number of nodes to store the stack;
803  * only needed for performance reasons */
804  int* stacknextedge, /**< array of size number of nodes to store the next edge to be visited in
805  * dfs for all nodes on the stack/in the current path; only needed for
806  * performance reasons */
807  int* dfsnodes, /**< array of nodes that can be reached starting at startnode, in reverse
808  * dfs order */
809  int* ndfsnodes, /**< pointer to store number of nodes that can be reached starting at
810  * startnode */
811  SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
812  )
813 {
814  SCIP_VAR** vars;
815  SCIP_VAR* startvar;
816  SCIP_Bool lower;
817  int stacksize;
818  int curridx;
819  int nimpls;
820  int idx;
821  /* for cycle detection, we need to mark currently active nodes, otherwise we just mark them as visited */
822  int visitedflag = (propdata->detectcycles ? ACTIVE : VISITED);
823 
824  assert(startnode >= 0);
825  assert(startnode < propdata->nbounds);
826  assert(visited != NULL);
827  assert(visited[startnode] == 0);
828  assert(dfsstack != NULL);
829  assert(dfsnodes != NULL);
830  assert(ndfsnodes != NULL);
831  assert(infeasible != NULL);
832 
833  *infeasible = FALSE;
834 
835  vars = propdata->vars;
836 
837  /* put start node on the stack */
838  dfsstack[0] = startnode;
839  stacknextedge[0] = 0;
840  stacksize = 1;
841  idx = -1;
842 
843  /* we run until no more bounds indices are on the stack, i.e. all changed bounds were propagated */
844  while( stacksize > 0 )
845  {
846  /* get next node from stack */
847  curridx = dfsstack[stacksize - 1];
848 
849  /* mark current node as visited */
850  assert((visited[curridx] != 0) == (stacknextedge[stacksize - 1] != 0));
851  visited[curridx] = visitedflag;
852 
853  startvar = vars[getVarIndex(curridx)];
854  lower = isIndexLowerbound(curridx);
855 
856  /* if the variable was fixed in the meantime, it is a loose end in the variable bound graph */
857  if( SCIPisFeasGE(scip, SCIPvarGetLbGlobal(startvar), SCIPvarGetUbGlobal(startvar)) )
858  goto REMOVE;
859 
860  nimpls = 0;
861 
862  if( propdata->sortcliques && propdata->usecliques && stacknextedge[stacksize - 1] == 0 )
863  stacknextedge[stacksize - 1] = -1;
864 
865  /* stacknextedge is negative, if the last visited edge from the current node belongs to a clique;
866  * the index of the clique in the variable's clique list equals abs(stacknextedge) - 1
867  */
868  if( propdata->sortcliques && propdata->usecliques && stacknextedge[stacksize - 1] < 0 )
869  {
870  SCIP_CLIQUE** cliques;
871  int ncliques;
872  int j;
873  int i;
874  SCIP_Bool found;
875 
876  ncliques = SCIPvarGetNCliques(startvar, lower);
877  cliques = SCIPvarGetCliques(startvar, lower);
878  found = FALSE;
879 
880  assert(stacknextedge[stacksize - 1] == -1 || -stacknextedge[stacksize - 1] - 1 <= ncliques);
881 
882  /* iterate over all not yet handled cliques and search for an unvisited node */
883  for( j = -stacknextedge[stacksize - 1] - 1; j < ncliques; ++j )
884  {
885  SCIP_VAR** cliquevars;
886  SCIP_Bool* cliquevals;
887  int ncliquevars;
888 
889  cliquevars = SCIPcliqueGetVars(cliques[j]);
890  cliquevals = SCIPcliqueGetValues(cliques[j]);
891  ncliquevars = SCIPcliqueGetNVars(cliques[j]);
892 
893  for( i = 0; i < ncliquevars; ++i )
894  {
895  if( cliquevars[i] == startvar )
896  continue;
897 
898  if( cliquevals[i] )
899  idx = varGetUbIndex(propdata, cliquevars[i]);
900  else
901  idx = varGetLbIndex(propdata, cliquevars[i]);
902 
903  /* we reached a variable that was already visited on the active path, so we have a cycle in the variable
904  * bound graph and try to extract valid bound changes from it or detect infeasibility
905  */
906  if( idx >= 0 && (visited[idx] == ACTIVE || visited[getOtherBoundIndex(idx)] == ACTIVE)
907  && !SCIPisFeasGE(scip, SCIPvarGetLbGlobal(cliquevars[i]), SCIPvarGetUbGlobal(cliquevars[i])) )
908  {
909  SCIPdebugMsg(scip, "found cycle\n");
910 
911  dfsstack[stacksize] = idx;
912  stacknextedge[stacksize - 1] = -j - 2;
913 
914  SCIP_CALL( extractCycle(scip, propdata, dfsstack, stacknextedge, stacksize + 1,
915  visited[idx] == ACTIVE, infeasible) );
916 
917  if( *infeasible )
918  break;
919  }
920 
921  /* break when the first unvisited node is reached */
922  if( idx >= 0 && !visited[idx] )
923  {
924  found = TRUE;
925  break;
926  }
927  }
928  if( found )
929  break;
930  }
931 
932  /* we stopped because we found an unhandled node and not because we reached the end of the list */
933  if( found )
934  {
935  assert(idx >= 0);
936  assert(!visited[idx]);
937  assert(j < ncliques);
938 
939  SCIPdebugMsg(scip, "clique: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
941 
942  /* put the adjacent node onto the stack */
943  dfsstack[stacksize] = idx;
944  stacknextedge[stacksize] = 0;
945  stacknextedge[stacksize - 1] = -j - 2;
946  stacksize++;
947  assert(stacksize <= propdata->nbounds);
948 
949  /* restart while loop, get next index from stack */
950  continue;
951  }
952  else
953  {
954  /* we did not find an edge to an unhandled node given by a clique */
955  stacknextedge[stacksize - 1] = 0;
956  }
957  }
958  assert(stacknextedge[stacksize - 1] >= 0);
959 
960  /* go over edges given by implications */
961  if( propdata->useimplics )
962  {
963  nimpls = SCIPvarGetNImpls(startvar, lower);
964 
965  if( stacknextedge[stacksize - 1] < nimpls )
966  {
967  SCIP_VAR** implvars;
968  SCIP_BOUNDTYPE* impltypes;
969  int* implids;
970  int i;
971 
972  implvars = SCIPvarGetImplVars(startvar, lower);
973  impltypes = SCIPvarGetImplTypes(startvar, lower);
974  implids = SCIPvarGetImplIds(startvar, lower);
975 
976  for( i = stacknextedge[stacksize - 1]; i < nimpls; ++i )
977  {
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
980  */
981  if( !SCIPvarIsActive(implvars[i]) )
982  continue;
983 
984  /* implication is just a shortcut, so we dont regard it now, because will later go the long way, anyway;
985  * however, if we do regard cliques for the topological order, we use them to get a better order
986  */
987  if( propdata->usecliques && !propdata->sortcliques && implids[i] < 0 )
988  continue;
989 
990  idx = (impltypes[i] == SCIP_BOUNDTYPE_LOWER ?
991  varGetLbIndex(propdata, implvars[i]) : varGetUbIndex(propdata, implvars[i]));
992 
993  /* we reached a variable that was already visited on the active path, so we have a cycle in the variable
994  * bound graph and try to extract valid bound changes from it or detect infeasibility
995  */
996  if( idx >= 0 && (visited[idx] == ACTIVE || visited[getOtherBoundIndex(idx)] == ACTIVE)
997  && !SCIPisFeasGE(scip, SCIPvarGetLbGlobal(implvars[i]), SCIPvarGetUbGlobal(implvars[i])) )
998  {
999  SCIPdebugMsg(scip, "found cycle\n");
1000 
1001  dfsstack[stacksize] = idx;
1002  stacknextedge[stacksize - 1] = i + 1;
1003 
1004  SCIP_CALL( extractCycle(scip, propdata, dfsstack, stacknextedge, stacksize + 1,
1005  visited[idx] == ACTIVE, infeasible) );
1006 
1007  if( *infeasible )
1008  break;
1009  }
1010 
1011  /* break when the first unvisited node is reached */
1012  if( idx >= 0 && !visited[idx] )
1013  break;
1014  }
1015 
1016  /* we stopped because we found an unhandled node and not because we reached the end of the list */
1017  if( i < nimpls )
1018  {
1019  assert(!visited[idx]);
1020 
1021  SCIPdebugMsg(scip, "impl: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
1022  indexGetBoundString(idx), SCIPvarGetName(vars[getVarIndex(idx)]));
1023 
1024  /* put the adjacent node onto the stack */
1025  dfsstack[stacksize] = idx;
1026  stacknextedge[stacksize] = 0;
1027  stacknextedge[stacksize - 1] = i + 1;
1028  stacksize++;
1029  assert(stacksize <= propdata->nbounds);
1030 
1031  /* restart while loop, get next index from stack */
1032  continue;
1033  }
1034  else
1035  {
1036  stacknextedge[stacksize - 1] = nimpls;
1037  }
1038  }
1039  }
1040  assert(stacknextedge[stacksize - 1] >= nimpls);
1041 
1042  /* go over edges corresponding to varbounds */
1043  if( propdata->usevbounds )
1044  {
1045  int nvbounds;
1046  int* vboundidx;
1047  int i;
1048 
1049  nvbounds = propdata->nvbounds[curridx];
1050  vboundidx = propdata->vboundboundedidx[curridx];
1051 
1052  /* iterate over all vbounds for the given bound */
1053  for( i = stacknextedge[stacksize - 1] - nimpls; i < nvbounds; ++i )
1054  {
1055  idx = vboundidx[i];
1056  assert(idx >= 0);
1057 
1058  if( (visited[idx] == ACTIVE || visited[getOtherBoundIndex(idx)] == ACTIVE)
1059  && !SCIPisFeasGE(scip, SCIPvarGetLbGlobal(vars[getVarIndex(idx)]), SCIPvarGetUbGlobal(vars[getVarIndex(idx)])) )
1060  {
1061  SCIPdebugMsg(scip, "found cycle\n");
1062 
1063  dfsstack[stacksize] = idx;
1064  stacknextedge[stacksize - 1] = nimpls + i + 1;
1065 
1066  /* we reached a variable that was already visited on the active path, so we have a cycle in the variable
1067  * bound graph and try to extract valid bound changes from it or detect infeasibility
1068  */
1069  SCIP_CALL( extractCycle(scip, propdata, dfsstack, stacknextedge, stacksize + 1,
1070  visited[idx] == ACTIVE, infeasible) );
1071 
1072  if( *infeasible )
1073  break;
1074  }
1075 
1076  /* break when the first unvisited node is reached */
1077  if( !visited[idx] )
1078  break;
1079  }
1080 
1081  if( *infeasible )
1082  break;
1083 
1084  /* we stopped because we found an unhandled node and not because we reached the end of the list */
1085  if( i < nvbounds )
1086  {
1087  assert(!visited[idx]);
1088 
1089  SCIPdebugMsg(scip, "vbound: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
1090  indexGetBoundString(idx), SCIPvarGetName(vars[getVarIndex(idx)]));
1091 
1092  /* put the adjacent node onto the stack */
1093  dfsstack[stacksize] = idx;
1094  stacknextedge[stacksize] = 0;
1095  stacknextedge[stacksize - 1] = nimpls + i + 1;
1096  stacksize++;
1097  assert(stacksize <= propdata->nbounds);
1098 
1099  /* restart while loop, get next index from stack */
1100  continue;
1101  }
1102  }
1103  REMOVE:
1104  /* the current node was completely handled, remove it from stack */
1105  stacksize--;
1106 
1107  SCIPdebugMsg(scip, "topoorder[%d] = %s(%s)\n", *ndfsnodes, getBoundString(lower), SCIPvarGetName(startvar));
1108 
1109  /* store node in the sorted nodes array */
1110  dfsnodes[(*ndfsnodes)] = curridx;
1111  assert(visited[curridx] == visitedflag);
1112  visited[curridx] = VISITED;
1113  (*ndfsnodes)++;
1114  }
1115 
1116  return SCIP_OKAY;
1117 }
1118 
1119 /** sort the bounds of variables topologically */
1120 static
1122  SCIP* scip, /**< SCIP data structure */
1123  SCIP_PROPDATA* propdata, /**< propagator data */
1124  SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
1125  )
1126 {
1127  int* dfsstack;
1128  int* stacknextedge;
1129  int* visited;
1130  int nsortednodes;
1131  int nbounds;
1132  int i;
1133 
1134  assert(scip != NULL);
1135  assert(propdata != NULL);
1136  assert(infeasible != NULL);
1137 
1138  nbounds = propdata->nbounds;
1139 
1140  SCIP_CALL( SCIPallocBufferArray(scip, &dfsstack, nbounds) );
1141  SCIP_CALL( SCIPallocBufferArray(scip, &stacknextedge, nbounds) );
1142  SCIP_CALL( SCIPallocClearBufferArray(scip, &visited, nbounds) );
1143 
1144  nsortednodes = 0;
1145 
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
1148  * reverse topological order
1149  */
1150  for( i = 0; i < nbounds && !(*infeasible); ++i )
1151  {
1152  if( !visited[i] )
1153  {
1154  SCIP_CALL( dfs(scip, propdata, i, visited, dfsstack, stacknextedge, propdata->topoorder, &nsortednodes, infeasible) );
1155  }
1156  }
1157  assert((nsortednodes == nbounds) || (*infeasible));
1158 
1159  SCIPfreeBufferArray(scip, &visited);
1160  SCIPfreeBufferArray(scip, &stacknextedge);
1161  SCIPfreeBufferArray(scip, &dfsstack);
1162 
1163  return SCIP_OKAY;
1164 }
1165 
1166 /** initializes the internal data for the variable bounds propagator */
1167 static
1169  SCIP* scip, /**< SCIP data structure */
1170  SCIP_PROP* prop, /**< vbounds propagator */
1171  SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
1172  )
1173 {
1174  SCIP_PROPDATA* propdata;
1175  SCIP_VAR** vars;
1176  int nvars;
1177  int nbounds;
1178  int startidx;
1179  int v;
1180  int n;
1181 
1182  assert(scip != NULL);
1183  assert(prop != NULL);
1184  assert(infeasible != NULL);
1185 
1186  /* get propagator data */
1187  propdata = SCIPpropGetData(prop);
1188  assert(propdata != NULL);
1189  assert(!propdata->initialized);
1190 
1191  SCIPdebugMsg(scip, "initialize vbounds propagator for problem <%s>\n", SCIPgetProbName(scip));
1192 
1193  vars = SCIPgetVars(scip);
1194  nvars = SCIPgetNVars(scip);
1195  nbounds = 2 * nvars;
1196 
1197  *infeasible = FALSE;
1198 
1199  /* store size of the bounds of variables array */
1200  propdata->nbounds = nbounds;
1201 
1202  if( nbounds == 0 )
1203  return SCIP_OKAY;
1204 
1205  propdata->initialized = TRUE;
1206 
1207  /* prepare priority queue structure */
1208  SCIP_CALL( SCIPpqueueCreate(&propdata->propqueue, nvars, 2.0, compVarboundIndices, NULL) );
1209  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->inqueue, nbounds) );
1210  BMSclearMemoryArray(propdata->inqueue, nbounds);
1211 
1212  /* we need to copy the variable since this array is the basis of the propagator and the corresponding variable array
1213  * within SCIP might change during the search
1214  */
1215  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &propdata->vars, vars, nvars) );
1216  SCIP_CALL( SCIPhashmapCreate(&propdata->varhashmap, SCIPblkmem(scip), nvars) );
1217 
1218  for( v = 0; v < nvars; ++v )
1219  {
1220  SCIP_CALL( SCIPhashmapInsertInt(propdata->varhashmap, propdata->vars[v], v) );
1221  }
1222 
1223  /* allocate memory for the arrays of the propdata */
1224  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->topoorder, nbounds) );
1225  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->vboundboundedidx, nbounds) );
1226  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->vboundcoefs, nbounds) );
1227  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->vboundconstants, nbounds) );
1228  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->nvbounds, nbounds) );
1229  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->vboundsize, nbounds) );
1230  BMSclearMemoryArray(propdata->vboundboundedidx, nbounds);
1231  BMSclearMemoryArray(propdata->vboundcoefs, nbounds);
1232  BMSclearMemoryArray(propdata->vboundconstants, nbounds);
1233  BMSclearMemoryArray(propdata->nvbounds, nbounds);
1234  BMSclearMemoryArray(propdata->vboundsize, nbounds);
1235 
1236  for( v = 0; v < nbounds; ++v )
1237  {
1238  propdata->topoorder[v] = v;
1239  propdata->vboundboundedidx[v] = NULL;
1240  propdata->vboundcoefs[v] = NULL;
1241  propdata->vboundconstants[v] = NULL;
1242  propdata->nvbounds[v] = 0;
1243  propdata->vboundsize[v] = 0;
1244  }
1245 
1246  /* collect information about varbounds */
1247  for( v = 0; v < nbounds; ++v )
1248  {
1249  SCIP_VAR** vbvars;
1250  SCIP_VAR* var;
1251  SCIP_Real* coefs;
1252  SCIP_Real* constants;
1253  SCIP_Bool lower;
1254  int nvbvars;
1255 
1256  var = vars[getVarIndex(v)];
1257  lower = isIndexLowerbound(v);
1258 
1259  /* get the variable bound informations for the current variable */
1260  if( lower )
1261  {
1262  vbvars = SCIPvarGetVlbVars(var);
1263  coefs = SCIPvarGetVlbCoefs(var);
1264  constants = SCIPvarGetVlbConstants(var);
1265  nvbvars = SCIPvarGetNVlbs(var);
1266  }
1267  else
1268  {
1269  vbvars = SCIPvarGetVubVars(var);
1270  coefs = SCIPvarGetVubCoefs(var);
1271  constants = SCIPvarGetVubConstants(var);
1272  nvbvars = SCIPvarGetNVubs(var);
1273  }
1274 
1275  /* loop over all variable bounds; a variable lower bound has the form: x >= b*y + d,
1276  * a variable upper bound the form x <= b*y + d */
1277  for( n = 0; n < nvbvars; ++n )
1278  {
1279  SCIP_VAR* vbvar;
1280  SCIP_Real coef;
1281  SCIP_Real constant;
1282 
1283  vbvar = vbvars[n];
1284  coef = coefs[n];
1285  constant = constants[n];
1286  assert(vbvar != NULL);
1287 
1288  /* transform variable bound variable to an active variable, if possible */
1289  SCIP_CALL( SCIPgetProbvarSum(scip, &vbvar, &coef, &constant) );
1290  assert(vbvar != NULL);
1291 
1292  if( !SCIPvarIsActive(vbvar) )
1293  continue;
1294 
1295  /* if the coefficient is positive, the type of bound is the same for the bounded and the bounding variable */
1296  if( SCIPisPositive(scip, coef) )
1297  startidx = (lower ? varGetLbIndex(propdata, vbvar) : varGetUbIndex(propdata, vbvar));
1298  else
1299  startidx = (lower ? varGetUbIndex(propdata, vbvar) : varGetLbIndex(propdata, vbvar));
1300  assert(startidx >= 0);
1301 
1302  /* If the vbvar is binary, the vbound should be stored as an implication already.
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,
1305  * the implication might not have been created.
1306  */
1307  if( SCIPvarGetType(vbvar) == SCIP_VARTYPE_BINARY
1308  && SCIPvarHasImplic(vbvar, isIndexLowerbound(startidx), var, getBoundtype(v)) )
1309  {
1310  SCIPdebugMsg(scip, "varbound <%s> %s %g * <%s> + %g not added to propagator data due to reverse implication\n",
1311  SCIPvarGetName(var), (lower ? ">=" : "<="), coef,
1312  SCIPvarGetName(vbvar), constant);
1313  }
1314  else
1315  {
1316  SCIP_CALL( addVbound(scip, propdata, startidx, v, coef, constant) );
1317 
1318  SCIPdebugMsg(scip, "varbound <%s> %s %g * <%s> + %g added to propagator data\n",
1319  SCIPvarGetName(var), (lower ? ">=" : "<="), coef,
1320  SCIPvarGetName(vbvar), constant);
1321  }
1322  }
1323  }
1324 
1325  /* sort the bounds topologically */
1326  if( propdata->dotoposort )
1327  {
1328  SCIP_CALL( topologicalSort(scip, propdata, infeasible) );
1329  }
1330 
1331  /* catch variable events */
1332  SCIP_CALL( catchEvents(scip, propdata) );
1333 
1334  return SCIP_OKAY;
1335 }
1336 
1337 /** resolves a propagation by adding the variable which implied that bound change */
1338 static
1340  SCIP* scip, /**< SCIP data structure */
1341  SCIP_PROPDATA* propdata, /**< propagator data */
1342  SCIP_VAR* var, /**< variable to be reported */
1343  SCIP_BOUNDTYPE boundtype, /**< bound to be reported */
1344  SCIP_BDCHGIDX* bdchgidx /**< the index of the bound change, representing the point of time where
1345  * the change took place, or NULL for the current local bounds */
1346  )
1347 {
1348  assert(propdata != NULL);
1349  assert(boundtype == SCIP_BOUNDTYPE_LOWER || boundtype == SCIP_BOUNDTYPE_UPPER);
1350 
1351  SCIPdebugMsg(scip, " -> add %s bound of variable <%s> as reason\n",
1352  getBoundtypeString(boundtype), SCIPvarGetName(var));
1353 
1354  switch( boundtype )
1355  {
1356  case SCIP_BOUNDTYPE_LOWER:
1357  SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) );
1358  break;
1359  case SCIP_BOUNDTYPE_UPPER:
1360  SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) );
1361  break;
1362  default:
1363  SCIPerrorMessage("invalid bound type <%d>\n", boundtype);
1364  SCIPABORT();
1365  return SCIP_INVALIDDATA; /*lint !e527*/
1366  }
1367 
1368  return SCIP_OKAY;
1369 }
1370 
1371 /** relaxes bound of give variable as long as the given inference bound still leads to a cutoff and add that bound
1372  * change to the conflict set
1373  */
1374 static
1376  SCIP* scip, /**< SCIP data structure */
1377  SCIP_VAR* var, /**< variable for which the upper bound should be relaxed */
1378  SCIP_BOUNDTYPE boundtype, /**< boundtype used for the variable bound variable */
1379  SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where
1380  * the change took place, or NULL for the current local bounds */
1381  SCIP_Real relaxedbd /**< relaxed bound */
1382  )
1383 {
1384  if( boundtype == SCIP_BOUNDTYPE_LOWER )
1385  {
1386  SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, relaxedbd) );
1387  }
1388  else
1389  {
1390  assert(boundtype == SCIP_BOUNDTYPE_UPPER);
1391  SCIP_CALL( SCIPaddConflictRelaxedUb(scip, var, bdchgidx, relaxedbd) );
1392  }
1393 
1394  return SCIP_OKAY;
1395 }
1396 
1397 /** compute the relaxed bound which is sufficient to propagate the inference lower bound of given variable */
1398 static
1400  SCIP* scip, /**< SCIP data structure */
1401  SCIP_VAR* var, /**< variable which was propagated */
1402  SCIP_Real inferlb, /**< inference lower bound */
1403  SCIP_Real coef, /**< inference variable bound coefficient used */
1404  SCIP_Real constant /**< inference variable bound constant used */
1405  )
1406 {
1407  SCIP_Real relaxedbd;
1408 
1409  if( SCIPvarIsIntegral(var) && inferlb < SCIPgetHugeValue(scip) * SCIPfeastol(scip) )
1410  relaxedbd = (inferlb - 1.0 + 2*SCIPfeastol(scip) - constant) / coef;
1411  else
1412  relaxedbd = (inferlb - constant) / coef;
1413 
1414  /* check the computed relaxed lower/upper bound is a proper reason for the inference bound which has to be explained */
1415  assert(SCIPisEQ(scip, inferlb, SCIPadjustedVarLb(scip, var, relaxedbd * coef + constant)));
1416 
1417  if( coef > 0.0 )
1418  relaxedbd += SCIPfeastol(scip);
1419  else
1420  relaxedbd -= SCIPfeastol(scip);
1421 
1422  return relaxedbd;
1423 }
1424 
1425 /** analyzes an infeasibility which was reached by updating the lower bound of the inference variable above its upper
1426  * bound
1427  */
1428 static
1430  SCIP* scip, /**< SCIP data structure */
1431  SCIP_PROPDATA* propdata, /**< propagator data */
1432  SCIP_VAR* infervar, /**< variable which led to a cutoff */
1433  SCIP_Real inferlb, /**< lower bound which led to infeasibility */
1434  SCIP_VAR* vbdvar, /**< variable which is the reason for the lower bound change */
1435  SCIP_BOUNDTYPE boundtype, /**< bound which is the reason for the lower bound change */
1436  SCIP_Real coef, /**< inference variable bound coefficient used */
1437  SCIP_Real constant, /**< inference variable bound constant used */
1438  SCIP_Bool canwide /**< can bound widening be used (for vbounds) or not
1439  * (for implications or cliques) */
1440  )
1441 {
1442  assert(scip != NULL);
1443  assert(propdata != NULL);
1444  assert(infervar != NULL);
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)));
1447  assert(SCIPisGT(scip, inferlb, SCIPvarGetUbLocal(infervar)));
1448  assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING);
1449 
1450  /* check if conflict analysis is applicable */
1452  return SCIP_OKAY;
1453 
1454  if( canwide && propdata->usebdwidening )
1455  {
1456  SCIP_Real relaxedbd;
1457  SCIP_Real relaxedub;
1458 
1459  SCIPdebugMsg(scip, "try to create conflict using bound widening order: inference variable, variable bound variable\n");
1460 
1461  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1463 
1464  /* adjust lower bound */
1465  inferlb = SCIPadjustedVarLb(scip, infervar, inferlb);
1466 
1467  /* compute a relaxed upper bound which would be sufficient to be still infeasible */
1468  if( SCIPvarIsIntegral(infervar) )
1469  relaxedub = inferlb - 1.0;
1470  else
1471  relaxedub = inferlb - 2*SCIPfeastol(scip);
1472 
1473  /* try to relax inference variable upper bound such that the infeasibility is still given */
1474  SCIP_CALL( SCIPaddConflictRelaxedUb(scip, infervar, NULL, relaxedub) );
1475 
1476  /* collect the upper bound which is reported to the conflict analysis */
1477  relaxedub = SCIPgetConflictVarUb(scip, infervar);
1478 
1479  /* adjust inference bound with respect to the upper bound reported to the conflict analysis */
1480  if( SCIPvarIsIntegral(infervar) )
1481  relaxedub = relaxedub + 1.0;
1482  else
1483  relaxedub = relaxedub + 2*SCIPfeastol(scip);
1484 
1485  /* compute the relaxed bound which is sufficient to propagate the inference lower bound of given variable */
1486  relaxedbd = computeRelaxedLowerbound(scip, infervar, relaxedub, coef, constant);
1487 
1488  /* try to relax variable bound variable */
1489  SCIP_CALL( relaxVbdvar(scip, vbdvar, boundtype, NULL, relaxedbd) );
1490 
1491  /* analyze the conflict */
1492  SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
1493  }
1494  else
1495  {
1496  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1498 
1499  /* add upper bound of the variable for which we tried to change the lower bound */
1500  SCIP_CALL( SCIPaddConflictUb(scip, infervar, NULL) );
1501 
1502  /* add (correct) bound of the variable which let to the new lower bound */
1503  SCIP_CALL( resolvePropagation(scip, propdata, vbdvar, boundtype, NULL) );
1504 
1505  /* analyze the conflict */
1506  SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
1507  }
1508 
1509  return SCIP_OKAY;
1510 }
1511 
1512 /** compute the relaxed bound which is sufficient to propagate the inference upper bound of given variable */
1513 static
1515  SCIP* scip, /**< SCIP data structure */
1516  SCIP_VAR* var, /**< variable which was propagated */
1517  SCIP_Real inferub, /**< inference upper bound */
1518  SCIP_Real coef, /**< inference variable bound coefficient used */
1519  SCIP_Real constant /**< inference variable bound constant used */
1520  )
1521 {
1522  SCIP_Real relaxedbd;
1523 
1524  if( SCIPvarIsIntegral(var) && inferub < SCIPgetHugeValue(scip) * SCIPfeastol(scip) )
1525  relaxedbd = (inferub + 1.0 - 2*SCIPfeastol(scip) - constant) / coef;
1526  else
1527  relaxedbd = (inferub - constant) / coef;
1528 
1529  /* check the computed relaxed lower/upper bound is a proper reason for the inference bound which has to be explained */
1530  assert(SCIPisEQ(scip, inferub, SCIPadjustedVarUb(scip, var, relaxedbd * coef + constant)));
1531 
1532  if( coef > 0.0 )
1533  relaxedbd -= SCIPfeastol(scip);
1534  else
1535  relaxedbd += SCIPfeastol(scip);
1536 
1537  return relaxedbd;
1538 }
1539 
1540 /** analyzes an infeasibility which was reached by updating the upper bound of the inference variable below its lower
1541  * bound
1542  */
1543 static
1545  SCIP* scip, /**< SCIP data structure */
1546  SCIP_PROPDATA* propdata, /**< propagator data */
1547  SCIP_VAR* infervar, /**< variable which led to a cutoff */
1548  SCIP_Real inferub, /**< upper bound which led to infeasibility */
1549  SCIP_VAR* vbdvar, /**< variable which is the reason for the upper bound change */
1550  SCIP_BOUNDTYPE boundtype, /**< bound which is the reason for the upper bound change */
1551  SCIP_Real coef, /**< inference variable bound coefficient used */
1552  SCIP_Real constant, /**< inference variable bound constant used */
1553  SCIP_Bool canwide /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1554  )
1555 {
1556  assert(scip != NULL);
1557  assert(propdata != NULL);
1558  assert(infervar != NULL);
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)));
1561  assert(SCIPisLT(scip, inferub, SCIPvarGetLbLocal(infervar)));
1562  assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING);
1563 
1564  /* check if conflict analysis is applicable */
1566  return SCIP_OKAY;
1567 
1568  if( canwide && propdata->usebdwidening )
1569  {
1570  SCIP_Real relaxedbd;
1571  SCIP_Real relaxedlb;
1572 
1573  SCIPdebugMsg(scip, "try to create conflict using bound widening order: inference variable, variable bound variable\n");
1574 
1575  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1577 
1578  /* adjust upper bound */
1579  inferub = SCIPadjustedVarUb(scip, infervar, inferub);
1580 
1581  /* compute a relaxed lower bound which would be sufficient to be still infeasible */
1582  if( SCIPvarIsIntegral(infervar) )
1583  relaxedlb = inferub + 1.0;
1584  else
1585  relaxedlb = inferub + 2*SCIPfeastol(scip);
1586 
1587  /* try to relax inference variable lower bound such that the infeasibility is still given */
1588  SCIP_CALL( SCIPaddConflictRelaxedLb(scip, infervar, NULL, relaxedlb) );
1589 
1590  /* collect the lower bound which is reported to the conflict analysis */
1591  relaxedlb = SCIPgetConflictVarLb(scip, infervar);
1592 
1593  /* adjust inference bound with respect to the upper bound reported to the conflict analysis */
1594  if( SCIPvarIsIntegral(infervar) )
1595  relaxedlb = relaxedlb - 1.0;
1596  else
1597  relaxedlb = relaxedlb - 2*SCIPfeastol(scip);
1598 
1599  /* compute the relaxed bound which is sufficient to propagate the inference upper bound of given variable */
1600  relaxedbd = computeRelaxedUpperbound(scip, infervar, relaxedlb, coef, constant);
1601 
1602  /* try to relax variable bound variable */
1603  SCIP_CALL( relaxVbdvar(scip, vbdvar, boundtype, NULL, relaxedbd) );
1604 
1605  /* analyze the conflict */
1606  SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
1607  }
1608  else
1609  {
1610  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1612 
1613  /* add lower bound of the variable for which we tried to change the upper bound */
1614  SCIP_CALL( SCIPaddConflictLb(scip, infervar, NULL) );
1615 
1616  /* add (correct) bound of the variable which let to the new upper bound */
1617  SCIP_CALL( resolvePropagation(scip, propdata, vbdvar, boundtype, NULL) );
1618 
1619  /* analyze the conflict */
1620  SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
1621  }
1622 
1623  return SCIP_OKAY;
1624 }
1625 
1626 /* tries to tighten the (global) lower bound of the given variable to the given new bound */
1627 static
1629  SCIP* scip, /**< SCIP data structure */
1630  SCIP_PROP* prop, /**< vbounds propagator */
1631  SCIP_PROPDATA* propdata, /**< propagator data */
1632  SCIP_VAR* var, /**< variable whose lower bound should be tightened */
1633  SCIP_Real newlb, /**< new lower bound for the variable */
1634  SCIP_Bool global, /**< is the bound globally valid? */
1635  SCIP_VAR* vbdvar, /**< variable which is the reason for the lower bound change */
1636  SCIP_BOUNDTYPE boundtype, /**< bound which is the reason for the lower bound change */
1637  SCIP_Bool force, /**< should domain changes for continuous variables be forced */
1638  SCIP_Real coef, /**< coefficient in vbound constraint causing the propagation;
1639  * or 0.0 if propagation is caused by clique or implication */
1640  SCIP_Real constant, /**< constant in vbound constraint causing the propagation;
1641  * or 0.0 if propagation is caused by clique or implication */
1642  SCIP_Bool canwide, /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1643  int* nchgbds, /**< pointer to increase, if a bound was changed */
1644  SCIP_RESULT* result /**< pointer to store the result of the propagation */
1645  )
1646 {
1647  INFERINFO inferinfo;
1648  SCIP_Real lb;
1649  SCIP_Bool tightened;
1650  SCIP_Bool infeasible;
1651 
1652  assert(scip != NULL);
1653  assert(prop != NULL);
1654  assert(propdata != NULL);
1655  assert(var != NULL);
1656  assert(nchgbds != NULL);
1657  assert(result != NULL);
1658 
1659  lb = SCIPvarGetLbLocal(var);
1660 
1661  /* check that the new upper bound is better */
1662  if( (SCIPvarIsIntegral(var) && newlb - lb > 0.5) || (force && SCIPisGT(scip, newlb, lb)) )
1663  force = TRUE;
1664  else
1665  force = FALSE;
1666 
1667  /* try to tighten the lower bound */
1668  if( global )
1669  {
1670  SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, newlb, force, &infeasible, &tightened) );
1671  }
1672  else
1673  {
1674  inferinfo = getInferInfo(boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, vbdvar) : varGetUbIndex(propdata, vbdvar), boundtype);
1675 
1676  SCIP_CALL( SCIPinferVarLbProp(scip, var, newlb, prop, inferInfoToInt(inferinfo), force, &infeasible, &tightened) );
1677  }
1678 
1679  if( infeasible )
1680  {
1681  /* the infeasible results comes from the fact that the new lower bound lies above the current upper bound */
1682  assert(SCIPisGT(scip, newlb, SCIPvarGetUbLocal(var)));
1683  assert(!global || SCIPisGT(scip, newlb, SCIPvarGetUbGlobal(var)));
1684 
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));
1687 
1688  if( global )
1689  {
1690  /* cutoff the root node */
1691  SCIP_CALL( SCIPcutoffNode(scip, SCIPgetRootNode(scip)) );
1692  }
1693  else
1694  {
1695  /* analyzes a infeasibility via conflict analysis */
1696  SCIP_CALL( analyzeConflictLowerbound(scip, propdata, var, newlb, vbdvar, boundtype, coef, constant, canwide) );
1697  }
1698  *result = SCIP_CUTOFF;
1699  }
1700  else if( tightened )
1701  {
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));
1704  (*nchgbds)++;
1705  }
1706 
1707  return SCIP_OKAY;
1708 }
1709 
1710 /* tries to tighten the (global) upper bound of the given variable to the given new bound */
1711 static
1713  SCIP* scip, /**< SCIP data structure */
1714  SCIP_PROP* prop, /**< vbounds propagator */
1715  SCIP_PROPDATA* propdata, /**< propagator data */
1716  SCIP_VAR* var, /**< variable whose upper bound should be tightened */
1717  SCIP_Real newub, /**< new upper bound of the variable */
1718  SCIP_Bool global, /**< is the bound globally valid? */
1719  SCIP_VAR* vbdvar, /**< variable which is the reason for the upper bound change */
1720  SCIP_BOUNDTYPE boundtype, /**< bound which is the reason for the upper bound change */
1721  SCIP_Bool force, /**< should domain changes for continuous variables be forced */
1722  SCIP_Real coef, /**< coefficient in vbound constraint causing the propagation;
1723  * or 0.0 if propagation is caused by clique or implication */
1724  SCIP_Real constant, /**< constant in vbound constraint causing the propagation;
1725  * or 0.0 if propagation is caused by clique or implication */
1726  SCIP_Bool canwide, /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1727  int* nchgbds, /**< pointer to increase, if a bound was changed */
1728  SCIP_RESULT* result /**< pointer to store the result of the propagation */
1729  )
1730 {
1731  INFERINFO inferinfo;
1732  SCIP_Real ub;
1733  SCIP_Bool tightened;
1734  SCIP_Bool infeasible;
1735 
1736  assert(scip != NULL);
1737  assert(prop != NULL);
1738  assert(propdata != NULL);
1739  assert(var != NULL);
1740  assert(nchgbds != NULL);
1741  assert(result != NULL);
1742 
1743  ub = SCIPvarGetUbLocal(var);
1744 
1745  /* check that the new upper bound is better */
1746  if( (SCIPvarIsIntegral(var) && ub - newub > 0.5) || (force && SCIPisLT(scip, newub, ub)) )
1747  force = TRUE;
1748  else
1749  force = FALSE;
1750 
1751  /* try to tighten the upper bound */
1752  if( global )
1753  {
1754  SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, newub, force, &infeasible, &tightened) );
1755  }
1756  else
1757  {
1758  inferinfo = getInferInfo(boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, vbdvar) : varGetUbIndex(propdata, vbdvar), boundtype);
1759 
1760  SCIP_CALL( SCIPinferVarUbProp(scip, var, newub, prop, inferInfoToInt(inferinfo), force, &infeasible, &tightened) );
1761  }
1762 
1763  if( infeasible )
1764  {
1765  /* the infeasible results comes from the fact that the new upper bound lies below the current lower bound */
1766  assert(SCIPisLT(scip, newub, SCIPvarGetLbLocal(var)));
1767  assert(!global || SCIPisLT(scip, newub, SCIPvarGetLbGlobal(var)));
1768 
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));
1771 
1772  if( global )
1773  {
1774  /* cutoff the root node */
1775  SCIP_CALL( SCIPcutoffNode(scip, SCIPgetRootNode(scip)) );
1776  }
1777  else
1778  {
1779  /* analyzes a infeasibility via conflict analysis */
1780  SCIP_CALL( analyzeConflictUpperbound(scip, propdata, var, newub, vbdvar, boundtype, coef, constant, canwide) );
1781  }
1782  *result = SCIP_CUTOFF;
1783  }
1784  else if( tightened )
1785  {
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));
1788  (*nchgbds)++;
1789  }
1790 
1791  return SCIP_OKAY;
1792 }
1793 
1794 /** performs propagation of variables lower and upper bounds, implications, and cliques */
1795 static
1797  SCIP* scip, /**< SCIP data structure */
1798  SCIP_PROP* prop, /**< vbounds propagator */
1799  SCIP_Bool force, /**< should domain changes for continuous variables be forced */
1800  SCIP_RESULT* result /**< pointer to store the result of the propagation */
1801  )
1802 {
1803  SCIP_PROPDATA* propdata;
1804  SCIP_VAR** vars;
1805  SCIP_VAR* startvar;
1806  SCIP_BOUNDTYPE starttype;
1807  SCIP_Real startbound;
1808  SCIP_Real globalbound;
1809  int* queuelist = NULL;
1810  int nqueuelist = 0;
1811  int startpos;
1812  int topopos;
1813  int v;
1814  int n;
1815  int nchgbds;
1816  int nbounds;
1817  SCIP_Bool lower;
1818  SCIP_Bool global;
1819 
1820  assert(scip != NULL);
1821  assert(prop != NULL);
1822  assert(result != NULL);
1823 
1824  (*result) = SCIP_DIDNOTRUN;
1825 
1826  /* we do not run the propagator in presolving, because we want to avoid doing the expensive creation of the graph twice */
1827  if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING )
1828  return SCIP_OKAY;
1829 
1830  propdata = SCIPpropGetData(prop);
1831  assert(propdata != NULL);
1832 
1833  /* initialize propagator data needed for propagation, if not done yet */
1834  if( !propdata->initialized )
1835  {
1836  SCIP_Bool infeasible;
1837 
1838  SCIP_CALL( initData(scip, prop, &infeasible) );
1839 
1840  if( infeasible )
1841  {
1842  *result = SCIP_CUTOFF;
1843  return SCIP_OKAY;
1844  }
1845  }
1846  assert(propdata->nbounds == 0 || propdata->propqueue != NULL);
1847 
1848  vars = propdata->vars;
1849  nbounds = propdata->nbounds;
1850 
1851  if( nbounds == 0 )
1852  return SCIP_OKAY;
1853 
1854  /* propagate all variables if we are in repropagation */
1855  if( SCIPinRepropagation(scip) )
1856  {
1857  SCIP_VAR* var;
1858  int idx;
1859 
1860  for( v = nbounds - 1; v >= 0; --v )
1861  {
1862  idx = propdata->topoorder[v];
1863  if( idx != -1 && !propdata->inqueue[v] )
1864  {
1865  var = vars[getVarIndex(idx)];
1866  lower = isIndexLowerbound(idx);
1867  if( !SCIPvarIsBinary(var) || (lower && SCIPvarGetLbLocal(var) > 0.5)
1868  || (!lower && SCIPvarGetUbLocal(var) < 0.5) )
1869  {
1870  SCIP_CALL( SCIPpqueueInsert(propdata->propqueue, (void*)(size_t)(v + 1)) ); /*lint !e571 !e776*/
1871  propdata->inqueue[v] = TRUE;
1872  }
1873  }
1874  }
1875  }
1876 
1877  /* return if no bound changes are in the priority queue (no changed bounds to handle since last propagation) */
1878  if( SCIPpqueueNElems(propdata->propqueue) == 0 )
1879  return SCIP_OKAY;
1880 
1881  nchgbds = 0;
1882 
1883  (*result) = SCIP_DIDNOTFIND;
1884 
1885  /* allocate space for variables added to the queue - needed to clean up data */
1886  SCIP_CALL( SCIPallocBufferArray(scip, &queuelist, nbounds) );
1887 
1888  SCIPdebugMsg(scip, "varbound propagator: %d elements in the propagation queue\n", SCIPpqueueNElems(propdata->propqueue));
1889 
1890  /* get variable bound of highest priority from priority queue and try to deduce bound changes for other variables;
1891  * the priority queue is ordered w.r.t the topological sort of the varbound graph
1892  */
1893  while( SCIPpqueueNElems(propdata->propqueue) > 0 )
1894  {
1895  /* coverity[pointer_conversion_loses_bits] */
1896  topopos = ((int)(size_t)SCIPpqueueRemove(propdata->propqueue)) - 1;
1897  assert(propdata->inqueue[topopos]);
1898  startpos = propdata->topoorder[topopos];
1899  assert(startpos >= 0);
1900  queuelist[nqueuelist++] = topopos;
1901  assert( nqueuelist <= nbounds );
1902 
1903  /* do not directly set propdata->inqueue[topopos] = FALSE: we allow only one propagation sweep through the
1904  * topologically ordered bounds; otherwise an infinite loop could occur */
1905 
1906  startvar = vars[getVarIndex(startpos)];
1907  starttype = getBoundtype(startpos);
1908  lower = (starttype == SCIP_BOUNDTYPE_LOWER);
1909  startbound = ( lower ? SCIPvarGetLbLocal(startvar) : SCIPvarGetUbLocal(startvar) );
1910  globalbound = ( lower ? SCIPvarGetLbGlobal(startvar) : SCIPvarGetUbGlobal(startvar));
1911  global = SCIPisEQ(scip, startbound, globalbound);
1912 
1913  SCIPdebugMsg(scip, "propagate new %s bound of %g of variable <%s>:\n",
1914  getBoundtypeString(starttype), startbound, SCIPvarGetName(startvar));
1915 
1916  /* there should be neither implications nor cliques for non-binary variables */
1917  assert(SCIPvarIsBinary(startvar) || SCIPvarGetNImpls(startvar, lower) == 0);
1918  assert(SCIPvarIsBinary(startvar) || SCIPvarGetNCliques(startvar, lower) == 0);
1919 
1920  if( SCIPvarIsBinary(startvar) )
1921  {
1922  /* we only propagate binary variables if the lower bound changed to 1.0 or the upper bound changed to 0.0 */
1923  if( lower != (startbound > 0.5) )
1924  continue;
1925 
1926  /* propagate implications */
1927  if( propdata->useimplics )
1928  {
1929  int nimplvars;
1930 
1931  /* if the lower bound of the startvar was changed, it was fixed to 1.0, otherwise it was fixed to 0.0;
1932  * get all implications for this varfixing
1933  */
1934  nimplvars = SCIPvarGetNImpls(startvar, lower);
1935 
1936  /* if there are implications for the varfixing, propagate them */
1937  if( nimplvars > 0 )
1938  {
1939  SCIP_VAR** implvars;
1940  SCIP_BOUNDTYPE* impltypes;
1941  SCIP_Real* implbounds;
1942  int* implids;
1943 
1944  implvars = SCIPvarGetImplVars(startvar, lower);
1945  impltypes = SCIPvarGetImplTypes(startvar, lower);
1946  implbounds = SCIPvarGetImplBounds(startvar, lower);
1947  implids = SCIPvarGetImplIds(startvar, lower);
1948 
1949  for( n = 0; n < nimplvars; ++n )
1950  {
1951  /* implication is just a shortcut, so we do not propagate it now,
1952  * because we will propagate the longer way, anyway
1953  */
1954  if( implids[n] < 0 )
1955  continue;
1956 
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
1959  */
1960  if( !SCIPvarIsActive(implvars[n]) )
1961  continue;
1962 
1963  if( impltypes[n] == SCIP_BOUNDTYPE_LOWER )
1964  {
1965  SCIP_CALL( tightenVarLb(scip, prop, propdata, implvars[n], implbounds[n], global, startvar,
1966  starttype, force, 0.0, 0.0, FALSE, &nchgbds, result) );
1967  }
1968  else
1969  {
1970  SCIP_CALL( tightenVarUb(scip, prop, propdata, implvars[n], implbounds[n], global, startvar,
1971  starttype, force, 0.0, 0.0, FALSE, &nchgbds, result) );
1972  }
1973 
1974  if( *result == SCIP_CUTOFF )
1975  break;
1976  }
1977  if( *result == SCIP_CUTOFF )
1978  break;
1979  }
1980  }
1981 
1982  /* propagate cliques */
1983  if( propdata->usecliques )
1984  {
1985  int ncliques;
1986 
1987  /* if the lower bound of the startvar was changed, it was fixed to 1.0, otherwise it was fixed to 0.0;
1988  * get all cliques for this varfixing
1989  */
1990  ncliques = SCIPvarGetNCliques(startvar, lower);
1991 
1992  /* if there are cliques for the varfixing, propagate them */
1993  if( ncliques > 0 )
1994  {
1995  SCIP_CLIQUE** cliques;
1996  int j;
1997 
1998  cliques = SCIPvarGetCliques(startvar, lower);
1999 
2000  for( j = 0; j < ncliques; ++j )
2001  {
2002  SCIP_VAR** cliquevars;
2003  SCIP_Bool* cliquevals;
2004  int ncliquevars;
2005 
2006  cliquevars = SCIPcliqueGetVars(cliques[j]);
2007  cliquevals = SCIPcliqueGetValues(cliques[j]);
2008  ncliquevars = SCIPcliqueGetNVars(cliques[j]);
2009 
2010  /* fix all variables except for the startvar to the value which is not in the clique */
2011  for( n = 0; n < ncliquevars; ++n )
2012  {
2013  if( cliquevars[n] == startvar )
2014  continue;
2015 
2016  /* try to tighten the bound */
2017  if( cliquevals[n] )
2018  {
2019  /* unnegated variable is in clique, so it has to be fixed to 0.0 */
2020  SCIP_CALL( tightenVarUb(scip, prop, propdata, cliquevars[n], 0.0, global, startvar, starttype,
2021  force, 0.0, 0.0, FALSE, &nchgbds, result) );
2022  }
2023  else
2024  {
2025  /* negated variable is in clique, so it has to be fixed to 1.0 */
2026  SCIP_CALL( tightenVarLb(scip, prop, propdata, cliquevars[n], 1.0, global, startvar, starttype,
2027  force, 0.0, 0.0, FALSE, &nchgbds, result) );
2028  }
2029 
2030  if( *result == SCIP_CUTOFF )
2031  break;
2032  }
2033  }
2034  if( *result == SCIP_CUTOFF )
2035  break;
2036  }
2037  }
2038  }
2039 
2040  /* propagate vbounds */
2041  if( propdata->usevbounds && ! SCIPisInfinity(scip, REALABS(startbound)) )
2042  {
2043  SCIP_VAR* boundedvar;
2044  SCIP_Real newbound;
2045  SCIP_Real coef;
2046  SCIP_Real constant;
2047 
2048  /* iterate over all vbounds for the given bound */
2049  for( n = 0; n < propdata->nvbounds[startpos]; ++n )
2050  {
2051  boundedvar = vars[getVarIndex(propdata->vboundboundedidx[startpos][n])];
2052  coef = propdata->vboundcoefs[startpos][n];
2053  constant = propdata->vboundconstants[startpos][n];
2054 
2055  /* compute new bound */
2056  newbound = startbound * coef + constant;
2057 
2058  /* try to tighten the bound */
2059  if( isIndexLowerbound(propdata->vboundboundedidx[startpos][n]) )
2060  {
2061  SCIP_CALL( tightenVarLb(scip, prop, propdata, boundedvar, newbound, global, startvar, starttype, force,
2062  coef, constant, TRUE, &nchgbds, result) );
2063  }
2064  else
2065  {
2066  SCIP_CALL( tightenVarUb(scip, prop, propdata, boundedvar, newbound, global, startvar, starttype, force,
2067  coef, constant, TRUE, &nchgbds, result) );
2068  }
2069 
2070  if( *result == SCIP_CUTOFF )
2071  break;
2072  }
2073  if( *result == SCIP_CUTOFF )
2074  break;
2075  }
2076  }
2077 
2078  /* clean up inqueue */
2079  for( v = 0; v < nqueuelist; ++v )
2080  {
2081  assert( 0 <= queuelist[v] && queuelist[v] < nbounds );
2082  propdata->inqueue[queuelist[v]] = FALSE;
2083  assert( SCIPpqueueFind(propdata->propqueue, (void*)(size_t) (queuelist[v] + 1)) == -1 ); /*lint !e571*//*lint !e776*/
2084  }
2085  SCIPfreeBufferArray(scip, &queuelist);
2086 
2087 #ifdef SCIP_DEBUG
2088  for( v = 0; v < nbounds; ++v)
2089  {
2090  if( propdata->inqueue[v] )
2091  assert( SCIPpqueueFind(propdata->propqueue, (void*)(size_t) (v + 1)) >= 0 );
2092  else
2093  assert( SCIPpqueueFind(propdata->propqueue, (void*)(size_t) (v + 1)) == -1 );
2094  }
2095 #endif
2096 
2097  SCIPdebugMsg(scip, "tightened %d variable bounds\n", nchgbds);
2098 
2099  /* set the result depending on whether bound changes were found or not */
2100  if( *result != SCIP_CUTOFF && nchgbds > 0 )
2101  (*result) = SCIP_REDUCEDDOM;
2102 
2103  return SCIP_OKAY;
2104 }
2105 
2106 /**@name Callback methods of propagator
2107  *
2108  * @{
2109  */
2110 
2111 /** copy method for propagator plugins (called when SCIP copies plugins) */
2112 static
2113 SCIP_DECL_PROPCOPY(propCopyVbounds)
2114 { /*lint --e{715}*/
2115  assert(scip != NULL);
2116  assert(prop != NULL);
2117  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2118 
2119  /* call inclusion method of propagator */
2121 
2122  return SCIP_OKAY;
2123 }
2124 
2125 /** destructor of propagator to free user data (called when SCIP is exiting) */
2126 static
2127 SCIP_DECL_PROPFREE(propFreeVbounds)
2128 { /*lint --e{715}*/
2129  SCIP_PROPDATA* propdata;
2131  /* free propagator data */
2132  propdata = SCIPpropGetData(prop);
2133 
2134  SCIPfreeBlockMemory(scip, &propdata);
2135  SCIPpropSetData(prop, NULL);
2136 
2137  return SCIP_OKAY;
2138 }
2139 
2140 /** presolving initialization method of propagator (called when presolving is about to begin) */
2141 static
2142 SCIP_DECL_PROPINITPRE(propInitpreVbounds)
2143 { /*lint --e{715}*/
2144  SCIP_PROPDATA* propdata;
2146  propdata = SCIPpropGetData(prop);
2147  assert(propdata != NULL);
2148 
2149  propdata->lastpresolncliques = 0;
2150 
2151  return SCIP_OKAY;
2152 }
2153 
2154 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
2155 static
2156 SCIP_DECL_PROPEXITSOL(propExitsolVbounds)
2157 { /*lint --e{715}*/
2158  SCIP_PROPDATA* propdata;
2159  int v;
2160 
2161  propdata = SCIPpropGetData(prop);
2162  assert(propdata != NULL);
2163 
2164  /* free data stored for propagation */
2165  if( propdata->initialized )
2166  {
2167  /* drop all variable events */
2168  SCIP_CALL( dropEvents(scip, propdata) );
2169 
2170  /* release all variables */
2171  for( v = 0; v < propdata->nbounds; ++v )
2172  {
2173  /* free vbound data */
2174  if( propdata->vboundsize[v] > 0 )
2175  {
2176  SCIPfreeMemoryArray(scip, &propdata->vboundboundedidx[v]);
2177  SCIPfreeMemoryArray(scip, &propdata->vboundcoefs[v]);
2178  SCIPfreeMemoryArray(scip, &propdata->vboundconstants[v]);
2179  }
2180  }
2181 
2182  /* free priority queue */
2183  SCIPpqueueFree(&propdata->propqueue);
2184 
2185  /* free arrays */
2186  SCIPfreeBlockMemoryArray(scip, &propdata->vboundsize, propdata->nbounds);
2187  SCIPfreeBlockMemoryArray(scip, &propdata->nvbounds, propdata->nbounds);
2188  SCIPfreeBlockMemoryArray(scip, &propdata->vboundconstants, propdata->nbounds);
2189  SCIPfreeBlockMemoryArray(scip, &propdata->vboundcoefs, propdata->nbounds);
2190  SCIPfreeBlockMemoryArray(scip, &propdata->vboundboundedidx, propdata->nbounds);
2191  SCIPfreeBlockMemoryArray(scip, &propdata->inqueue, propdata->nbounds);
2192  SCIPfreeBlockMemoryArray(scip, &propdata->topoorder, propdata->nbounds);
2193 
2194  /* free variable array and hashmap */
2195  SCIPhashmapFree(&propdata->varhashmap);
2196  SCIPfreeBlockMemoryArray(scip, &propdata->vars, propdata->nbounds / 2);
2197  }
2198 
2199  /* reset propagation data */
2200  resetPropdata(propdata);
2201 
2202  return SCIP_OKAY;
2203 }
2204 
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.
2208  *
2209  * The algorithm is an iterative version of Tarjans algorithm
2210  * (see https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm)
2211  * with some additional tweaks.
2212  * Each clique x_1 + ... + x_k <= 1 is represented by k(k-1) arcs (lb(x_i),ub(x_j)), j != i.
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.
2218  * After that, we can disregard the clique for the further search.
2219  * Additionally, we try to identify infeasible fixings for binary variables. Those can be given by a path
2220  * from x=1 to x=0 (or vice versa) or if x=0 (or 1) implies both y=0 and y=1.
2221  */
2222 static
2224  SCIP* scip, /**< SCIP data structure */
2225  int startnode, /**< node to start the depth-first-search */
2226  int* startindex, /**< next index to assign to a processed node */
2227  SCIP_Shortbool* nodeonstack, /**< array to store the whether a each node is on the stack */
2228  int* nodeindex, /**< array to store the dfs index for each node */
2229  int* nodelowlink, /**< array to store the lowlink for each node */
2230  SCIP_Shortbool* nodeinfeasible, /**< array to store whether the fixing of a node was detected to be infeasible */
2231  int* dfsstack, /**< array of size number of nodes to store the stack */
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
2234  * the algorithm for all nodes on the stack */
2235  int* stacknextcliquevar, /**< array of size number of nodes to store the next variable in the next clique to be
2236  * regarded in the algorithm for all nodes on the stack */
2237  int* topoorder, /**< array with reverse (almost) topological ordering of the nodes */
2238  int* nordered, /**< number of ordered nodes (disconnected nodes are disregarded) */
2239  int* cliquefirstentry, /**< node from which a clique was entered for the first time; needed because when
2240  * entering the clique a second time, only the other bound corresponding to this node
2241  * remains to be processed */
2242  int* cliquecurrentexit, /**< for cliques which define an arc on the current path: target node of this arc */
2243  int* sccvars, /**< array with all nontrivial strongly connected components in the graph */
2244  int* sccstarts, /**< start indices of SCCs in sccvars array; one additional entry at the end
2245  * to give length of used part of sccvars array */
2246  int* nsccs, /**< pointer to store number of strongly connected components */
2247  int* infeasnodes, /**< sparse array with node indices of infeasible nodes */
2248  int* ninfeasnodes, /**< pointer to store the number of infeasible nodes */
2249  SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
2250  )
2251 {
2252  SCIP_VAR** vars;
2253  SCIP_VAR* startvar;
2254  SCIP_Bool lower;
2255  int label = *startindex;
2256  int stacksize;
2257  int currstackidx;
2258  int curridx;
2259  int idx;
2260 
2261  assert(startnode >= 0);
2262  assert(startnode < 2 * (SCIPgetNVars(scip) - SCIPgetNContVars(scip)));
2263  assert(nodeindex != NULL);
2264  assert(nodeindex[startnode] == 0);
2265  assert(nodelowlink != NULL);
2266  assert(nodelowlink[startnode] == 0);
2267  assert(dfsstack != NULL);
2268  assert(stacknextclique != NULL);
2269  assert(infeasible != NULL);
2270 
2271  *infeasible = FALSE;
2272 
2273  vars = SCIPgetVars(scip);
2274 
2275  /* put start node on the stack */
2276  dfsstack[0] = startnode;
2277  stacknextclique[0] = 0;
2278  stacknextcliquevar[0] = 0;
2279  predstackidx[0] = -1;
2280  stacksize = 1;
2281  idx = -1;
2282  currstackidx = 0;
2283 #ifdef DEBUG_TARJAN
2284  SCIPdebugMsg(scip, "put %s(%s) on stack[%d]\n", indexGetBoundString(dfsstack[stacksize-1]),
2285  SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize-1])]), stacksize-1);
2286 #endif
2287 
2288  /* we run until no more bounds indices are on the stack, i.e., no further nodes are connected to the startnode */
2289  while( stacksize > 0 )
2290  {
2291  SCIP_CLIQUE** cliques;
2292  int ncliques;
2293  SCIP_Bool found;
2294  int clqidx = -1;
2295  int j;
2296  int i;
2297 
2298  /* get next node from stack */
2299  curridx = dfsstack[currstackidx];
2300  assert(nodelowlink[curridx] <= nodeindex[curridx]);
2301 
2302  startvar = vars[getVarIndex(curridx)];
2303  lower = isIndexLowerbound(curridx);
2304 
2305  /* mark current node as on stack, assign index and lowlink */
2306  if( nodeindex[curridx] == 0 )
2307  {
2308  assert(!nodeonstack[curridx]);
2309  assert(stacknextclique[currstackidx] == 0);
2310  assert(stacknextcliquevar[currstackidx] == 0);
2311  nodeonstack[curridx] = 1;
2312  nodeindex[curridx] = label;
2313  nodelowlink[curridx] = label;
2314  ++label;
2315 
2316 #ifdef DEBUG_TARJAN
2317  {
2318  ncliques = SCIPvarGetNCliques(startvar, lower);
2319  cliques = SCIPvarGetCliques(startvar, lower);
2320 
2321  SCIPdebugMsg(scip, "variable %s(%s) has %d cliques\n", indexGetBoundString(curridx), SCIPvarGetName(startvar),
2322  ncliques);
2323  for( j = 0; j < ncliques; ++j )
2324  {
2325  SCIP_VAR** cliquevars;
2326  SCIP_Bool* cliquevals;
2327  int ncliquevars;
2328 
2329  clqidx = SCIPcliqueGetIndex(cliques[j]);
2330  cliquevars = SCIPcliqueGetVars(cliques[j]);
2331  cliquevals = SCIPcliqueGetValues(cliques[j]);
2332  ncliquevars = SCIPcliqueGetNVars(cliques[j]);
2333 
2334  SCIPdebugMsg(scip, "clique %d [%d vars, stacksize: %d]...\n", clqidx, ncliquevars, stacksize);
2335  for( int v = 0; v < ncliquevars; ++v )
2336  SCIPdebugMsgPrint(scip, " %s<%s>", cliquevals[v] ? "" : "~", SCIPvarGetName(cliquevars[v]));
2337  SCIPdebugMsgPrint(scip, "\n");
2338  }
2339  }
2340 #endif
2341  }
2342  /* we just did a backtrack and still need to investigate some outgoing edges of the node;
2343  * however, we should have investigated some of the outgoing edges before
2344  */
2345  else
2346  {
2347  assert(stacknextclique[currstackidx] > 0 || stacknextcliquevar[currstackidx] > 0);
2348  assert(nodeindex[curridx] < label);
2349  }
2350  assert(stacknextclique[currstackidx] >= 0);
2351 
2352  ncliques = SCIPvarGetNCliques(startvar, lower);
2353  cliques = SCIPvarGetCliques(startvar, lower);
2354  found = FALSE;
2355 
2356  /* iterate over all not yet handled cliques and search for an unvisited node */
2357  for( j = stacknextclique[currstackidx]; j < ncliques; ++j )
2358  {
2359  SCIP_VAR** cliquevars;
2360  SCIP_Bool* cliquevals;
2361  int ncliquevars;
2362 
2363  clqidx = SCIPcliqueGetIndex(cliques[j]);
2364  cliquevars = SCIPcliqueGetVars(cliques[j]);
2365  cliquevals = SCIPcliqueGetValues(cliques[j]);
2366  ncliquevars = SCIPcliqueGetNVars(cliques[j]);
2367 
2368  /* we did not look at this clique before from the current node, i.e., we did not backtrack now from another
2369  * node which was reached via this clique
2370  */
2371  if( stacknextcliquevar[currstackidx] == 0 )
2372  {
2373 #ifdef DEBUG_TARJAN
2374  SCIPdebugMsg(scip, "clique %d [%d vars, stacksize: %d]...\n", clqidx, ncliquevars, stacksize);
2375  for( int v = 0; v < ncliquevars; ++v )
2376  SCIPdebugMsgPrint(scip, " %s<%s>", cliquevals[v] ? "" : "~", SCIPvarGetName(cliquevars[v]));
2377  SCIPdebugMsgPrint(scip, "\n");
2378 #endif
2379  /* the clique was not entered before, remember that we first entered it from curridx
2380  * (add 1 to distinguish it from 0 initialization)
2381  */
2382  if( cliquefirstentry[clqidx] == 0 )
2383  {
2384  cliquefirstentry[clqidx] = curridx + 1;
2385  }
2386  else
2387  {
2388  int cliquefirstentryidx = (cliquefirstentry[clqidx] > 0 ? cliquefirstentry[clqidx] : -cliquefirstentry[clqidx]) - 1;
2389  int infeasnode = -1;
2390  assert(cliquefirstentryidx != curridx);
2391 
2392  /* The node by which we entered the clique the first time is still on the stack, so there is a
2393  * way from that node to the node by which we are entering the clique right now.
2394  * Since these two assignments together violate the clique and the second assignment is implied by the first,
2395  * the first one is infeasible
2396  */
2397  if( nodeonstack[cliquefirstentryidx] && !nodeinfeasible[cliquefirstentryidx] )
2398  {
2399  SCIPdebugMsg(scip, "infeasible assignment (1): %s(%s)\n", indexGetBoundString(cliquefirstentryidx),
2400  SCIPvarGetName(vars[getVarIndex(cliquefirstentryidx)]));
2401  infeasnode = cliquefirstentryidx;
2402  }
2403  /* the first entry point of the clique was also implied by the current startnode, so this node implies
2404  * two variables in the clique and is therefore infeasible
2405  */
2406  else if( nodeindex[cliquefirstentryidx] >= *startindex && !nodeinfeasible[startnode] )
2407  {
2408  SCIPdebugMsg(scip, "infeasible assignment (2): %s(%s)\n", indexGetBoundString(startnode),
2409  SCIPvarGetName(vars[getVarIndex(startnode)]));
2410  infeasnode = startnode;
2411  }
2412 
2413  /* we identified an infeasibility */
2414  if( infeasnode >= 0 )
2415  {
2416  /* both values are invalid for the variable, the whole problem is infeasible */
2417  if( nodeinfeasible[getOtherBoundIndex(infeasnode)] )
2418  {
2419  *infeasible = TRUE;
2420  return SCIP_OKAY;
2421  }
2422  infeasnodes[*ninfeasnodes] = infeasnode;
2423  nodeinfeasible[infeasnode] = TRUE;
2424  ++(*ninfeasnodes);
2425 
2426  /* the last node by which the clique was exited is not the negation of the current node and still on
2427  * the stack: update the lowlink of the current node
2428  */
2429  if( cliquecurrentexit[clqidx] > 0
2430  && curridx != getOtherBoundIndex(cliquecurrentexit[clqidx] - 1)
2431  && nodeonstack[cliquecurrentexit[clqidx] - 1]
2432  && nodeindex[cliquecurrentexit[clqidx] - 1] < nodelowlink[curridx] )
2433  {
2434  nodelowlink[curridx] = nodeindex[cliquecurrentexit[clqidx] - 1];
2435  }
2436  }
2437  /* clique is entered for the second time; there is only one edge left to investigate, namely the edge to
2438  * the negation of the first entry point
2439  */
2440  else if( cliquefirstentry[clqidx] > 0 )
2441  {
2442 #ifdef DEBUG_TARJAN
2443  SCIPdebugMsg(scip, "entering clique %d a second time\n", clqidx);
2444 #endif
2445  idx = getOtherBoundIndex(cliquefirstentry[clqidx] - 1);
2446 
2447  /* node was not investigated yet, we found the next node to process */
2448  if( nodeindex[idx] == 0 )
2449  found = TRUE;
2450  /* update lowlink if the node is on the stack */
2451  else if( nodeonstack[idx] && nodeindex[idx] < nodelowlink[curridx] )
2452  nodelowlink[curridx] = nodeindex[idx];
2453 
2454  /* cliquefirstentry[clqidx] < 0 means that we entered the clique at least two times already */
2455  cliquefirstentry[clqidx] = -cliquefirstentry[clqidx];
2456  }
2457  else
2458  {
2459 #ifdef DEBUG_TARJAN
2460  SCIPdebugMsg(scip, "skip clique %d: visited more than twice already!\n", clqidx);
2461 #endif
2462  }
2463  stacknextcliquevar[currstackidx] = ncliquevars;
2464  }
2465  }
2466 
2467  /* iterate over variables in the clique; start where we stopped last time */
2468  for( i = stacknextcliquevar[currstackidx]; i < ncliquevars; ++i )
2469  {
2470  if( cliquevars[i] == startvar )
2471  continue;
2472 
2473  if( !SCIPvarIsActive(cliquevars[i]) )
2474  continue;
2475 
2476  if( cliquevals[i] )
2477  idx = getUbIndex(SCIPvarGetProbindex(cliquevars[i]));
2478  else
2479  idx = getLbIndex(SCIPvarGetProbindex(cliquevars[i]));
2480  assert(idx >= 0);
2481 
2482  /* break when the first unvisited node is reached */
2483  if( nodeindex[idx] == 0 )
2484  {
2485  assert(!nodeonstack[idx]);
2486  stacknextcliquevar[currstackidx] = i + 1;
2487  found = TRUE;
2488  break;
2489  }
2490  else if( nodeonstack[idx] && nodeindex[idx] < nodelowlink[curridx] )
2491  {
2492  nodelowlink[curridx] = nodeindex[idx];
2493  }
2494  }
2495  if( found )
2496  {
2497  if( stacknextcliquevar[currstackidx] < ncliquevars )
2498  stacknextclique[currstackidx] = j;
2499  else
2500  {
2501  stacknextclique[currstackidx] = j + 1;
2502  stacknextcliquevar[currstackidx] = 0;
2503  }
2504  break;
2505  }
2506  else
2507  {
2508  assert(i == ncliquevars);
2509  stacknextclique[currstackidx] = j + 1;
2510  stacknextcliquevar[currstackidx] = 0;
2511  }
2512  }
2513  assert(found || j == ncliques);
2514  assert(found || stacknextclique[currstackidx] == ncliques);
2515 
2516  /* we stopped because we found an unhandled node and not because we reached the end of the list */
2517  if( found )
2518  {
2519  int otheridx = getOtherBoundIndex(idx);
2520  int infeasnode = -1;
2521 
2522  assert(idx >= 0);
2523  assert(!nodeonstack[idx]);
2524  assert(j < ncliques);
2525  assert(clqidx >= 0);
2526 
2527  /* the negated node corresponding to the next node is already on the stack -> the negated assignment is
2528  * infeasible
2529  */
2530  if( nodeonstack[otheridx] && !nodeinfeasible[otheridx] )
2531  {
2532  SCIPdebugMsg(scip, "infeasible assignment (3): %s(%s)\n", indexGetBoundString(otheridx),
2533  SCIPvarGetName(vars[getVarIndex(otheridx)]));
2534  infeasnode = otheridx;
2535  }
2536  /* the negated node corresponding to the next node was reached from the same startnode -> the startnode is
2537  * infeasible
2538  */
2539  else if( nodeindex[otheridx] >= *startindex && !nodeinfeasible[startnode] )
2540  {
2541  SCIPdebugMsg(scip, "infeasible assignment (4): %s(%s)\n", indexGetBoundString(startnode),
2542  SCIPvarGetName(vars[getVarIndex(startnode)]));
2543  infeasnode = startnode;
2544  }
2545  /* treat infeasible case */
2546  if( infeasnode >= 0 )
2547  {
2548  if( nodeinfeasible[getOtherBoundIndex(infeasnode)] )
2549  {
2550  *infeasible = TRUE;
2551  return SCIP_OKAY;
2552  }
2553  infeasnodes[*ninfeasnodes] = infeasnode;
2554  nodeinfeasible[infeasnode] = TRUE;
2555  ++(*ninfeasnodes);
2556  }
2557 
2558  SCIPdebugMsg(scip, "clique: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
2559  indexGetBoundString(idx), SCIPvarGetName(vars[getVarIndex(idx)]));
2560 
2561  /* put the adjacent node onto the stack */
2562  dfsstack[stacksize] = idx;
2563  stacknextclique[stacksize] = 0;
2564  stacknextcliquevar[stacksize] = 0;
2565  cliquecurrentexit[clqidx] = idx + 1;
2566  predstackidx[stacksize] = currstackidx;
2567  currstackidx = stacksize;
2568  stacksize++;
2569  assert(stacksize <= 2 * (SCIPgetNVars(scip) - SCIPgetNContVars(scip)));
2570 
2571 #ifdef DEBUG_TARJAN
2572  SCIPdebugMsg(scip, "put %s(%s) on stack[%d]\n", indexGetBoundString(dfsstack[stacksize-1]), SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize-1])]), stacksize-1);
2573 #endif
2574  /* restart while loop, get next index from stack */
2575  continue;
2576  }
2577  assert(stacknextclique[currstackidx] == ncliques);
2578 
2579  /* no node with a smaller index can be reached from this node -> it is the root of a SCC,
2580  * consisting of all nodes above it on the stack, including the node itself
2581  */
2582  if( nodelowlink[curridx] == nodeindex[curridx] )
2583  {
2584  /* we are only interested in SCCs with more than one node */
2585  if( dfsstack[stacksize-1] != curridx )
2586  {
2587  int sccvarspos = sccstarts[*nsccs];
2588 
2589  SCIPdebugMsg(scip, "SCC:");
2590 
2591  /* store the SCC in sccvars */
2592  do{
2593  stacksize--;
2594  idx = dfsstack[stacksize];
2595  nodeonstack[idx] = 0;
2596  sccvars[sccvarspos] = idx;
2597  ++sccvarspos;
2598  SCIPdebugMsgPrint(scip, " %s(%s)", indexGetBoundString(idx), SCIPvarGetName(vars[getVarIndex(idx)]));
2599 #ifdef DEBUG_TARJAN
2600  SCIPdebugMsg(scip, "remove %s(%s) from stack[%d]\n", indexGetBoundString(dfsstack[stacksize]), SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize])]), stacksize);
2601 #endif
2602  }
2603  while( idx != curridx );
2604  SCIPdebugMsgPrint(scip, "\n");
2605  ++(*nsccs);
2606  sccstarts[*nsccs] = sccvarspos;
2607  }
2608  /* trivial SCC: remove the single node from the stack, but don't store it as a SCC */
2609  else
2610  {
2611  stacksize--;
2612 #ifdef DEBUG_TARJAN
2613  SCIPdebugMsg(scip, "remove %s(%s) from stack[%d]\n", indexGetBoundString(dfsstack[stacksize]), SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize])]), stacksize);
2614 #endif
2615  idx = dfsstack[stacksize];
2616  nodeonstack[idx] = 0;
2617  assert(nodeindex[idx] > 0);
2618  }
2619  }
2620  /* in a pure dfs, the node would now leave the stack, add it to the array of nodes in reverse topological order */
2621  if( topoorder != NULL && (stacksize > 0 || label > *startindex + 1) )
2622  {
2623  assert(nordered != NULL);
2624  topoorder[*nordered] = curridx;
2625  ++(*nordered);
2626  }
2627 
2628  /* the current node was handled, backtrack */
2629  if( stacksize > 0 )
2630  {
2631  idx = dfsstack[predstackidx[currstackidx]];
2632  nodelowlink[idx] = MIN(nodelowlink[idx], nodelowlink[curridx]);
2633  currstackidx = predstackidx[currstackidx];
2634  }
2635  }
2636 
2637  *startindex = label;
2638 
2639  return SCIP_OKAY;
2640 }
2641 
2642 
2643 /** apply fixings and aggregations found by the clique graph analysis */
2644 static
2646  SCIP* scip, /**< SCIP data structure */
2647  SCIP_VAR** vars, /**< array of active variables */
2648  int* infeasnodes, /**< sparse array with node indices of infeasible nodes */
2649  int ninfeasnodes, /**< pointer to store the number of infeasible nodes */
2650  SCIP_Shortbool* nodeinfeasible, /**< array to store whether the fixing of a node was detected to be infeasible */
2651  int* sccvars, /**< array with all nontrivial strongly connected components in the graph */
2652  int* sccstarts, /**< start indices of SCCs in sccvars array; one additional entry at the end
2653  * to give length of used part of sccvars array */
2654  int nsccs, /**< pointer to store number of strongly connected components */
2655  SCIP_Bool* infeasible, /**< pointer to store whether an infeasibility was detected */
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 */
2658  SCIP_RESULT* result /**< pointer to store result of the call */
2659  )
2660 {
2661  int i = 0;
2662 
2663  assert(scip != NULL);
2664  assert(vars != NULL);
2665  assert(infeasible != NULL);
2666 
2667  /* for all infeasible node: fix variable to the other bound */
2668  if( !(*infeasible) && ninfeasnodes > 0 )
2669  {
2670  for( i = 0; i < ninfeasnodes; ++i )
2671  {
2672  SCIP_VAR* var = vars[getVarIndex(infeasnodes[i])];
2673  SCIP_Bool lower = isIndexLowerbound(infeasnodes[i]);
2674  SCIP_Bool fixed;
2675 
2676  assert(nodeinfeasible[infeasnodes[i]]);
2677  nodeinfeasible[infeasnodes[i]] = FALSE;
2678 
2679  SCIP_CALL( SCIPfixVar(scip, var, lower ? 0.0 : 1.0, infeasible, &fixed) );
2680 
2681  SCIPdebugMsg(scip, "fix <%s>[%d] to %g: inf=%d, fixed=%d\n",
2682  SCIPvarGetName(var), infeasnodes[i], lower ? 0.0 : 1.0, *infeasible, fixed);
2683 
2684  /* fixing was infeasible */
2685  if( *infeasible )
2686  break;
2687 
2688  /* increase fixing counter and update result pointer */
2689  if( fixed )
2690  {
2691  *result = SCIP_SUCCESS;
2692  ++(*nfixedvars);
2693  }
2694  }
2695  }
2696  assert((*infeasible) || i == ninfeasnodes);
2697 
2698  /* clear clean buffer array (if we did not enter the block above or stopped early due to an infeasibility) */
2699  for( ; i < ninfeasnodes; ++i )
2700  {
2701  assert(nodeinfeasible[infeasnodes[i]]);
2702  nodeinfeasible[infeasnodes[i]] = FALSE;
2703  }
2704 
2705  if( !(*infeasible) && nsccs > 0 )
2706  {
2707  /* for each strongly connected component: aggregate all variables to the first one */
2708  for( i = 0; i < nsccs; ++i )
2709  {
2710  SCIP_VAR* startvar;
2711  SCIP_Bool lower;
2712  SCIP_Bool aggregated;
2713  SCIP_Bool redundant;
2714  int v;
2715 
2716  assert(sccstarts[i] < sccstarts[i+1] - 1);
2717 
2718  /* get variable and boundtype for first node of the SCC */
2719  startvar = vars[getVarIndex(sccvars[sccstarts[i]])];
2720  lower = isIndexLowerbound(sccvars[sccstarts[i]]);
2721 
2722  for( v = sccstarts[i] + 1; v < sccstarts[i+1]; ++v )
2723  {
2724  /* aggregate variables: if both nodes represent the same bound, we have x=1 <=> y=1,
2725  * and thus aggregate x - y = 0; if both represent different bounds we have
2726  * x=1 <=> y=0, so we aggregate x + y = 1
2727  */
2728  SCIP_CALL( SCIPaggregateVars(scip, startvar, vars[getVarIndex(sccvars[v])], 1.0,
2729  lower == isIndexLowerbound(sccvars[v]) ? -1.0 : 1.0,
2730  lower == isIndexLowerbound(sccvars[v]) ? 0.0 : 1.0,
2731  infeasible, &redundant, &aggregated) );
2732 
2733  SCIPdebugMsg(scip, "aggregate <%s> + %g <%s> = %g: inf=%d, red=%d, aggr=%d\n",
2734  SCIPvarGetName(startvar), lower == isIndexLowerbound(sccvars[v]) ? -1.0 : 1.0,
2735  SCIPvarGetName(vars[getVarIndex(sccvars[v])]), lower == isIndexLowerbound(sccvars[v]) ? 0.0 : 1.0,
2736  *infeasible, redundant, aggregated);
2737 
2738  /* aggregation was infeasible */
2739  if( *infeasible )
2740  break;
2741 
2742  /* increase aggregation counter and update result pointer */
2743  if( aggregated )
2744  {
2745  ++(*naggrvars);
2746  *result = SCIP_SUCCESS;
2747  }
2748  }
2749  }
2750  }
2751 
2752  return SCIP_OKAY;
2753 }
2754 
2755 
2756 
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.
2762  */
2763 static
2764 SCIP_DECL_PROPPRESOL(propPresolVbounds)
2765 { /*lint --e{715}*/
2766  SCIP_PROPDATA* propdata;
2767  SCIP_VAR** tmpvars;
2768  SCIP_VAR** vars;
2769  int* dfsstack;
2770  int* stacknextclique;
2771  int* stacknextcliquevar;
2772  int* nodeindex;
2773  int* nodelowlink;
2774  int* predstackidx;
2775  int* cliquefirstentry;
2776  int* cliquecurrentexit;
2777  int* topoorder;
2778  int* sccvars;
2779  int* sccstarts;
2780  int* infeasnodes;
2781  SCIP_Shortbool* nodeonstack;
2782  SCIP_Shortbool* nodeinfeasible;
2783  int ninfeasnodes;
2784  int nsccs;
2785  int nbounds;
2786  int nbinvars;
2787  int ncliques;
2788  int startindex = 1;
2789  int nordered = 0;
2790  int i;
2791  SCIP_Bool infeasible = FALSE;
2792 
2793  assert(scip != NULL);
2794 
2795  propdata = SCIPpropGetData(prop);
2796  assert(propdata != NULL);
2797 
2798  ncliques = SCIPgetNCliques(scip);
2799 
2800  *result = SCIP_DIDNOTRUN;
2801 
2802  if( ncliques < 2 )
2803  return SCIP_OKAY;
2804 
2805  /* too many cliques for medium presolving */
2806  if( presoltiming == SCIP_PRESOLTIMING_MEDIUM && ncliques > propdata->maxcliquesmedium * SCIPgetNBinVars(scip) )
2807  return SCIP_OKAY;
2808 
2809  /* too many cliques for exhaustive presolving */
2810  if( ncliques > propdata->maxcliquesexhaustive * SCIPgetNBinVars(scip) )
2811  return SCIP_OKAY;
2812 
2813  /* only run if enough new cliques were created since the last successful call */
2814  if( SCIPgetNCliquesCreated(scip) < (1.0 + propdata->minnewcliques) * propdata->lastpresolncliques )
2815  return SCIP_OKAY;
2816 
2817  *result = SCIP_DIDNOTFIND;
2818 
2819  nbinvars = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
2820  nbounds = 2 * nbinvars;
2821 
2822  /* cleanup cliques, stop if this proved infeasibility already */
2823  SCIP_CALL( SCIPcleanupCliques(scip, &infeasible) );
2824 
2825  if( infeasible )
2826  {
2827  *result = SCIP_CUTOFF;
2828  return SCIP_OKAY;
2829  }
2830 
2831  tmpvars = SCIPgetVars(scip);
2832 
2833  /* duplicate variable array; needed to get the fixings right later */
2834  SCIP_CALL( SCIPduplicateBufferArray(scip, &vars, tmpvars, nbinvars) );
2835 
2836  SCIP_CALL( SCIPallocBufferArray(scip, &dfsstack, nbounds) );
2837  SCIP_CALL( SCIPallocBufferArray(scip, &stacknextclique, nbounds) );
2838  SCIP_CALL( SCIPallocBufferArray(scip, &stacknextcliquevar, nbounds) );
2839  SCIP_CALL( SCIPallocBufferArray(scip, &predstackidx, nbounds) );
2840  SCIP_CALL( SCIPallocBufferArray(scip, &topoorder, nbounds) );
2841  SCIP_CALL( SCIPallocBufferArray(scip, &sccvars, nbounds) );
2842  SCIP_CALL( SCIPallocBufferArray(scip, &sccstarts, nbinvars + 1) );
2843  SCIP_CALL( SCIPallocBufferArray(scip, &infeasnodes, nbounds) );
2844  SCIP_CALL( SCIPallocClearBufferArray(scip, &nodeindex, nbounds) );
2845  SCIP_CALL( SCIPallocClearBufferArray(scip, &nodelowlink, nbounds) );
2846  SCIP_CALL( SCIPallocClearBufferArray(scip, &cliquefirstentry, ncliques) );
2847  SCIP_CALL( SCIPallocClearBufferArray(scip, &cliquecurrentexit, ncliques) );
2848  SCIP_CALL( SCIPallocClearBufferArray(scip, &nodeonstack, nbounds) );
2849  SCIP_CALL( SCIPallocCleanBufferArray(scip, &nodeinfeasible, nbounds) );
2850  sccstarts[0] = 0;
2851  nsccs = 0;
2852  ninfeasnodes = 0;
2853 
2854  /* while there are unvisited nodes, run Tarjan's algorithm starting from one of these nodes */
2855  for( i = 0; i < nbounds && !infeasible; ++i )
2856  {
2857  if( nodeindex[i] == 0 )
2858  {
2859  SCIP_CALL( tarjan(scip, i, &startindex, nodeonstack, nodeindex, nodelowlink, nodeinfeasible,
2860  dfsstack, predstackidx, stacknextclique, stacknextcliquevar, topoorder, &nordered,
2861  cliquefirstentry, cliquecurrentexit, sccvars, sccstarts, &nsccs,
2862  infeasnodes, &ninfeasnodes, &infeasible) );
2863  }
2864  }
2865  assert(nordered <= nbounds);
2866 
2867  /* aggregate all variables within a SCC and fix all variables for which one bounds was proven infeasible */
2868  if( ninfeasnodes > 0 || nsccs > 0 )
2869  {
2870  SCIP_CALL( applyFixingsAndAggregations(scip, vars, infeasnodes, ninfeasnodes, nodeinfeasible,
2871  sccvars, sccstarts, nsccs, &infeasible, nfixedvars, naggrvars, result) );
2872  }
2873 
2874  /* second round, now with topological order! */
2875  if( !infeasible && nordered > 0 )
2876  {
2877  SCIP_VAR** vars2;
2878  int nbounds2;
2879 
2880  assert(nordered > 1);
2881 
2882  /* we already fixed or aggregated some variables in the first run, so we better clean up the cliques */
2883  if( *result == SCIP_SUCCESS )
2884  {
2885  SCIP_CALL( SCIPcleanupCliques(scip, &infeasible) );
2886 
2887  if( infeasible )
2888  goto TERMINATE;
2889  }
2890 
2891  nbounds2 = 2 * (SCIPgetNVars(scip) - SCIPgetNContVars(scip));
2892  ncliques = SCIPgetNCliques(scip);
2893 
2894  SCIP_CALL( SCIPduplicateBufferArray(scip, &vars2, tmpvars, nbounds2/2) );
2895 
2896  /* clear arrays that should be initialized to 0 */
2897  BMSclearMemoryArray(nodeonstack, nbounds2);
2898  BMSclearMemoryArray(nodeindex, nbounds2);
2899  BMSclearMemoryArray(nodelowlink, nbounds2);
2900  BMSclearMemoryArray(cliquefirstentry, ncliques);
2901  BMSclearMemoryArray(cliquecurrentexit, ncliques);
2902  sccstarts[0] = 0;
2903  nsccs = 0;
2904  ninfeasnodes = 0;
2905  startindex = 1;
2906 
2907  /* while there are unvisited nodes, run Tarjan's algorithm starting from one of these nodes */
2908  for( i = nordered - 1; i >= 0 && !infeasible; --i )
2909  {
2910  int varindex;
2911  int startpos;
2912  assert(topoorder[i] < nbounds);
2913 
2914  /* variable of next node in topological order */
2915  varindex = SCIPvarGetProbindex(vars[getVarIndex(topoorder[i])]);
2916 
2917  /* variable was not fixed after the first run */
2918  if( varindex >= 0 )
2919  {
2920  startpos = isIndexLowerbound(topoorder[i]) ? getLbIndex(varindex) : getUbIndex(varindex);
2921  if( nodeindex[startpos] == 0 )
2922  {
2923  SCIP_CALL( tarjan(scip, startpos, &startindex, nodeonstack, nodeindex, nodelowlink, nodeinfeasible,
2924  dfsstack, predstackidx, stacknextclique, stacknextcliquevar, NULL, NULL,
2925  cliquefirstentry, cliquecurrentexit, sccvars, sccstarts, &nsccs,
2926  infeasnodes, &ninfeasnodes, &infeasible) );
2927  }
2928  }
2929  }
2930 
2931  /* aggregate all variables within a SCC and fix all variables for which one bounds was proven infeasible */
2932  if( ninfeasnodes > 0 || nsccs > 0 )
2933  {
2934  SCIP_CALL( applyFixingsAndAggregations(scip, vars2, infeasnodes, ninfeasnodes, nodeinfeasible,
2935  sccvars, sccstarts, nsccs, &infeasible, nfixedvars, naggrvars, result) );
2936  }
2937 
2938  SCIPfreeBufferArray(scip, &vars2);
2939  }
2940 
2941  TERMINATE:
2942  if( infeasible )
2943  *result = SCIP_CUTOFF;
2944 #ifndef NDEBUG
2945  for( i = 0; i < nbounds; ++i )
2946  {
2947  assert(nodeinfeasible[i] == FALSE);
2948  }
2949 #endif
2950  SCIPfreeCleanBufferArray(scip, &nodeinfeasible);
2951  SCIPfreeBufferArray(scip, &nodeonstack);
2952  SCIPfreeBufferArray(scip, &cliquecurrentexit);
2953  SCIPfreeBufferArray(scip, &cliquefirstentry);
2954  SCIPfreeBufferArray(scip, &nodelowlink);
2955  SCIPfreeBufferArray(scip, &nodeindex);
2956  SCIPfreeBufferArray(scip, &infeasnodes);
2957  SCIPfreeBufferArray(scip, &sccstarts);
2958  SCIPfreeBufferArray(scip, &sccvars);
2959  SCIPfreeBufferArray(scip, &topoorder);
2960  SCIPfreeBufferArray(scip, &predstackidx);
2961  SCIPfreeBufferArray(scip, &stacknextcliquevar);
2962  SCIPfreeBufferArray(scip, &stacknextclique);
2963  SCIPfreeBufferArray(scip, &dfsstack);
2964  SCIPfreeBufferArray(scip, &vars);
2965 
2966  propdata->lastpresolncliques = SCIPgetNCliquesCreated(scip);
2967 
2968  return SCIP_OKAY;
2969 }
2970 
2971 
2972 
2973 /** execution method of propagator */
2974 static
2975 SCIP_DECL_PROPEXEC(propExecVbounds)
2976 { /*lint --e{715}*/
2977  *result = SCIP_DIDNOTRUN;
2979  /* perform variable lower and upper bound propagation */
2980  SCIP_CALL( propagateVbounds(scip, prop, FALSE, result) );
2981 
2982  assert((*result) == SCIP_CUTOFF || (*result) == SCIP_DIDNOTRUN
2983  || (*result) == SCIP_DIDNOTFIND || (*result) == SCIP_REDUCEDDOM);
2984 
2985  return SCIP_OKAY;
2986 }
2987 
2988 /** propagation conflict resolving method of propagator */
2989 static
2990 SCIP_DECL_PROPRESPROP(propRespropVbounds)
2991 { /*lint --e{715}*/
2992  SCIP_PROPDATA* propdata;
2993  SCIP_VAR** vars;
2994  SCIP_VAR* startvar;
2995  SCIP_BOUNDTYPE starttype;
2996  int pos;
2997 
2998  propdata = SCIPpropGetData(prop);
2999  assert(propdata != NULL);
3000 
3001  starttype = inferInfoGetBoundtype(intToInferInfo(inferinfo));
3002  pos = inferInfoGetPos(intToInferInfo(inferinfo));
3003  assert(pos >= 0);
3004  assert(pos < propdata->nbounds);
3005 
3006  vars = propdata->vars;
3007  assert(vars != NULL);
3008  startvar = vars[getVarIndex(pos)];
3009  assert(startvar != NULL);
3010  assert(startvar != infervar);
3011 
3012  SCIPdebugMsg(scip, "explain %s bound change of variable <%s>\n",
3013  getBoundtypeString(boundtype), SCIPvarGetName(infervar));
3014 
3015  if( !SCIPvarIsBinary(startvar) && propdata->usebdwidening )
3016  {
3017  int* vboundboundedidx;
3018  SCIP_Real constant;
3019  SCIP_Real coef;
3020  int inferidx;
3021  int nvbounds;
3022  int b;
3023 
3024  nvbounds = propdata->nvbounds[pos];
3025  vboundboundedidx = propdata->vboundboundedidx[pos];
3026 
3027  inferidx = boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, infervar) : varGetUbIndex(propdata, infervar);
3028  assert(inferidx >= 0);
3029 
3030  for( b = 0; b < nvbounds; ++b )
3031  {
3032  if( vboundboundedidx[b] == inferidx )
3033  break;
3034  }
3035  assert(b < nvbounds);
3036 
3037  coef = propdata->vboundcoefs[pos][b];
3038  constant = propdata->vboundconstants[pos][b];
3039  assert(!SCIPisZero(scip, coef));
3040 
3041  /* compute the relaxed bound which is sufficient to propagate the inference bound of given variable */
3042  if( boundtype == SCIP_BOUNDTYPE_LOWER )
3043  relaxedbd = computeRelaxedLowerbound(scip, infervar, relaxedbd, coef, constant);
3044  else
3045  relaxedbd = computeRelaxedUpperbound(scip, infervar, relaxedbd, coef, constant);
3046 
3047  /* try to relax variable bound variable */
3048  SCIP_CALL( relaxVbdvar(scip, startvar, starttype, bdchgidx, relaxedbd) );
3049  }
3050  else
3051  {
3052  SCIP_CALL( resolvePropagation(scip, propdata, startvar, starttype, bdchgidx) );
3053  }
3054 
3055  (*result) = SCIP_SUCCESS;
3056 
3057  return SCIP_OKAY;
3058 }
3059 
3060 /**@} */
3061 
3062 /**@name Callback methods of event handler
3063  *
3064  * @{
3065  */
3066 
3067 /** execution method of bound change event handler */
3068 static
3069 SCIP_DECL_EVENTEXEC(eventExecVbound)
3070 { /*lint --e{715}*/
3071  SCIP_PROPDATA* propdata;
3072  int idx;
3073 
3074  assert(eventhdlr != NULL);
3075 
3076  propdata = (SCIP_PROPDATA*)SCIPeventhdlrGetData(eventhdlr);
3077  assert(propdata != NULL);
3078 
3079  /* coverity[pointer_conversion_loses_bits] */
3080  idx = (int) (size_t) eventdata;
3081  assert(idx >= 0);
3082 
3083  SCIPdebugMsg(scip, "eventexec (type=%lu): try to add sort index %d: %s(%s) to priority queue\n", SCIPeventGetType(event),
3084  idx, indexGetBoundString(propdata->topoorder[idx]),
3085  SCIPvarGetName(propdata->vars[getVarIndex(propdata->topoorder[idx])]));
3086 
3088  && SCIPeventGetNewbound(event) > 0.5 )
3089  return SCIP_OKAY;
3090 
3092  && SCIPeventGetNewbound(event) < 0.5 )
3093  return SCIP_OKAY;
3094 
3095  assert(getVarIndex(propdata->topoorder[idx]) < SCIPgetNVars(scip));
3096  assert(SCIPvarGetType(propdata->vars[getVarIndex(propdata->topoorder[idx])]) != SCIP_VARTYPE_BINARY
3097  || (isIndexLowerbound(propdata->topoorder[idx]) == (SCIPeventGetNewbound(event) > 0.5)));
3098 
3099  /* add the bound change to the propagation queue, if it is not already contained */
3100  if( !propdata->inqueue[idx] )
3101  {
3102  SCIP_CALL( SCIPpqueueInsert(propdata->propqueue, (void*)(size_t)(idx + 1)) ); /*lint !e571 !e776*/
3103  propdata->inqueue[idx] = TRUE;
3104  assert(SCIPpqueueNElems(propdata->propqueue) > 0);
3105  }
3106 
3107  return SCIP_OKAY;
3108 }
3109 
3110 /**@} */
3111 
3112 /**@name Interface methods
3113  *
3114  * @{
3115  */
3116 
3117 /** creates the vbounds propagator and includes it in SCIP */
3119  SCIP* scip /**< SCIP data structure */
3120  )
3122  SCIP_PROPDATA* propdata;
3123  SCIP_PROP* prop;
3124 
3125  /* create vbounds propagator data */
3126  SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
3127 
3128  /* reset propagation data */
3129  resetPropdata(propdata);
3130 
3131  /* include propagator */
3133  propExecVbounds, propdata) );
3134  assert(prop != NULL);
3135 
3136  /* set optional callbacks via setter functions */
3137  SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyVbounds) );
3138  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeVbounds) );
3139  SCIP_CALL( SCIPsetPropInitpre(scip, prop, propInitpreVbounds) );
3140  SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolVbounds) );
3141  SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropVbounds) );
3142  SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolVbounds, PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS,
3143  PROP_PRESOLTIMING) );
3144 
3145  /* include event handler for bound change events */
3146  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &propdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
3147  eventExecVbound, (SCIP_EVENTHDLRDATA*)propdata) );
3148 
3150  "propagating/" PROP_NAME "/usebdwidening", "should bound widening be used to initialize conflict analysis?",
3151  &propdata->usebdwidening, FALSE, DEFAULT_USEBDWIDENING, NULL, NULL) );
3153  "propagating/" PROP_NAME "/useimplics", "should implications be propagated?",
3154  &propdata->useimplics, TRUE, DEFAULT_USEIMPLICS, NULL, NULL) );
3156  "propagating/" PROP_NAME "/usecliques", "should cliques be propagated?",
3157  &propdata->usecliques, TRUE, DEFAULT_USECLIQUES, NULL, NULL) );
3159  "propagating/" PROP_NAME "/usevbounds", "should vbounds be propagated?",
3160  &propdata->usevbounds, TRUE, DEFAULT_USEVBOUNDS, NULL, NULL) );
3162  "propagating/" PROP_NAME "/dotoposort", "should the bounds be topologically sorted in advance?",
3163  &propdata->dotoposort, FALSE, DEFAULT_DOTOPOSORT, NULL, NULL) );
3165  "propagating/" PROP_NAME "/sortcliques", "should cliques be regarded for the topological sort?",
3166  &propdata->sortcliques, TRUE, DEFAULT_SORTCLIQUES, NULL, NULL) );
3168  "propagating/" PROP_NAME "/detectcycles", "should cycles in the variable bound graph be identified?",
3169  &propdata->detectcycles, FALSE, DEFAULT_DETECTCYCLES, NULL, NULL) );
3171  "propagating/" PROP_NAME "/minnewcliques", "minimum percentage of new cliques to trigger another clique table analysis",
3172  &propdata->minnewcliques, FALSE, DEFAULT_MINNEWCLIQUES, 0.0, 1.0, NULL, NULL) );
3173  SCIP_CALL( SCIPaddRealParam(scip, "propagating/" PROP_NAME "/maxcliquesmedium",
3174  "maximum number of cliques per variable to run clique table analysis in medium presolving",
3175  &propdata->maxcliquesmedium, FALSE, DEFAULT_MAXCLIQUESMEDIUM, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3176  SCIP_CALL( SCIPaddRealParam(scip, "propagating/" PROP_NAME "/maxcliquesexhaustive",
3177  "maximum number of cliques per variable to run clique table analysis in exhaustive presolving",
3178  &propdata->maxcliquesexhaustive, FALSE, DEFAULT_MAXCLIQUESEXHAUSTIVE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3179 
3180  return SCIP_OKAY;
3181 }
3182 
3183 /** returns TRUE if the propagator has the status that all variable lower and upper bounds are propgated */
3185  SCIP* scip /**< SCIP data structure */
3186  )
3188  SCIP_PROP* prop;
3189  SCIP_PROPDATA* propdata;
3190 
3191  prop = SCIPfindProp(scip, PROP_NAME);
3192  assert(prop != NULL);
3193 
3194  propdata = SCIPpropGetData(prop);
3195  assert(propdata != NULL);
3196 
3197  return (SCIPpqueueNElems(propdata->propqueue) == 0);
3198 }
3199 
3200 /** performs propagation of variables lower and upper bounds */
3202  SCIP* scip, /**< SCIP data structure */
3203  SCIP_Bool force, /**< should domain changes for continuous variables be forced */
3204  SCIP_RESULT* result /**< pointer to store result */
3205  )
3206 {
3207  SCIP_PROP* prop;
3208 
3209  prop = SCIPfindProp(scip, PROP_NAME);
3210  assert(prop != NULL);
3211 
3212  /* perform variable lower and upper bound propagation */
3213  SCIP_CALL( propagateVbounds(scip, prop, force, result) );
3214 
3215  assert((*result) == SCIP_CUTOFF || (*result) == SCIP_DIDNOTRUN
3216  || (*result) == SCIP_DIDNOTFIND || (*result) == SCIP_REDUCEDDOM);
3217 
3218  return SCIP_OKAY;
3219 }
3220 
3221 /**@} */
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define PROP_PRESOL_MAXROUNDS
Definition: prop_vbounds.c:111
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static void resetPropdata(SCIP_PROPDATA *propdata)
Definition: prop_vbounds.c:330
#define DEFAULT_MAXCLIQUESEXHAUSTIVE
Definition: prop_vbounds.c:142
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
void * SCIPpqueueRemove(SCIP_PQUEUE *pqueue)
Definition: misc.c:1434
SCIP_Real SCIPfeastol(SCIP *scip)
#define PROP_PRESOL_PRIORITY
Definition: prop_vbounds.c:109
#define PROP_FREQ
Definition: prop_vbounds.c:106
static SCIP_RETCODE addVbound(SCIP *scip, SCIP_PROPDATA *propdata, int startidx, int endidx, SCIP_Real coef, SCIP_Real constant)
Definition: prop_vbounds.c:457
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2166
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
#define getVarIndex(idx)
Definition: prop_vbounds.c:161
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
#define DEFAULT_USEBDWIDENING
Definition: prop_vbounds.c:131
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx)
void SCIPpqueueFree(SCIP_PQUEUE **pqueue)
Definition: misc.c:1263
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
Definition: implics.c:3351
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
public methods for SCIP parameter handling
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1989
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:7506
static SCIP_Real computeRelaxedLowerbound(SCIP *scip, SCIP_VAR *var, SCIP_Real inferlb, SCIP_Real coef, SCIP_Real constant)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5177
static SCIP_RETCODE dropEvents(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_vbounds.c:407
#define DEFAULT_USECLIQUES
Definition: prop_vbounds.c:133
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:5869
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)
public methods for memory management
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:113
public methods for implications, variable bounds, and cliques
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:69
#define PROP_PRESOLTIMING
Definition: prop_vbounds.c:110
public methods for conflict handler plugins and conflict analysis
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5294
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
Definition: type_event.h:146
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3132
#define getLbIndex(idx)
Definition: prop_vbounds.c:159
SCIP_EXPORT SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17197
SCIP_EXPORT SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17962
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1986
int SCIPcliqueGetIndex(SCIP_CLIQUE *clique)
Definition: implics.c:3387
#define FALSE
Definition: def.h:73
#define DEFAULT_SORTCLIQUES
Definition: prop_vbounds.c:136
#define DEFAULT_MAXCLIQUESMEDIUM
Definition: prop_vbounds.c:139
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:5984
SCIP_EXPORT SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17182
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_Bool SCIPcliqueIsEquation(SCIP_CLIQUE *clique)
Definition: implics.c:3407
int SCIPpqueueNElems(SCIP_PQUEUE *pqueue)
Definition: misc.c:1468
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:424
#define SCIP_EVENTTYPE_GLBCHANGED
Definition: type_event.h:66
static SCIP_DECL_PROPINITPRE(propInitpreVbounds)
SCIP_EXPORT SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17340
public methods for problem variables
SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub)
Definition: scip_var.c:4639
static SCIP_DECL_PROPCOPY(propCopyVbounds)
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
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_EXPORT SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17991
static SCIP_BOUNDTYPE inferInfoGetBoundtype(INFERINFO inferinfo)
Definition: prop_vbounds.c:254
SCIP_RETCODE SCIPanalyzeConflict(SCIP *scip, int validdepth, SCIP_Bool *success)
#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)
SCIP_RETCODE SCIPaddConflictRelaxedLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedlb)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:136
#define isIndexLowerbound(idx)
Definition: prop_vbounds.c:163
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
Definition: prop.c:790
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
public methods for SCIP variables
static int inferInfoToInt(INFERINFO inferinfo)
Definition: prop_vbounds.c:245
#define SCIPdebugMsgPrint
Definition: scip_message.h:70
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Real SCIPgetConflictVarUb(SCIP *scip, SCIP_VAR *var)
#define VISITED
Definition: prop_vbounds.c:796
SCIP_EXPORT SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
Definition: var.c:17871
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
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)
public methods for numerical tolerances
SCIP_RETCODE SCIPincludePropVbounds(SCIP *scip)
#define DEFAULT_USEIMPLICS
Definition: prop_vbounds.c:132
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3221
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)
SCIP_Real SCIPgetConflictVarLb(SCIP *scip, SCIP_VAR *var)
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:3363
#define PROP_DESC
Definition: prop_vbounds.c:103
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:92
#define SCIP_PRESOLTIMING_MEDIUM
Definition: type_timing.h:44
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17017
SCIP_EXPORT SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17208
SCIP_EXPORT int * SCIPvarGetImplIds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18007
#define SCIPerrorMessage
Definition: pub_message.h:55
static SCIP_DECL_EVENTEXEC(eventExecVbound)
#define indexGetBoundString(idx)
Definition: prop_vbounds.c:166
SCIP_EXPORT int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17945
public methods for event handler plugins and event handlers
SCIP_RETCODE SCIPexecPropVbounds(SCIP *scip, SCIP_Bool force, SCIP_RESULT *result)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1941
SCIP_Real SCIPgetHugeValue(SCIP *scip)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip_tree.c:100
#define INITMEMSIZE
Definition: prop_vbounds.c:453
SCIP_EXPORT SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition: var.c:17923
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:932
#define SCIPreallocMemoryArray(scip, ptr, newnum)
Definition: scip_mem.h:59
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:164
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:158
int SCIPgetNCliques(SCIP *scip)
Definition: scip_var.c:7549
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_Shortbool
Definition: def.h:78
#define REALABS(x)
Definition: def.h:187
static int varGetUbIndex(SCIP_PROPDATA *propdata, SCIP_VAR *var)
Definition: prop_vbounds.c:313
#define PROP_NAME
Definition: prop_vbounds.c:102
#define SCIP_CALL(x)
Definition: def.h:370
SCIP_EXPORT int SCIPvarGetNVubs(SCIP_VAR *var)
Definition: var.c:17901
#define SCIP_EVENTTYPE_LBTIGHTENED
Definition: type_event.h:68
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip_prop.c:222
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1021
static INFERINFO intToInferInfo(int i)
Definition: prop_vbounds.c:232
SCIP_Real SCIPeventGetNewbound(SCIP_EVENT *event)
Definition: event.c:1233
#define DEFAULT_DOTOPOSORT
Definition: prop_vbounds.c:135
#define PROP_TIMING
Definition: prop_vbounds.c:104
static SCIP_DECL_PROPEXEC(propExecVbounds)
static SCIP_DECL_PROPEXITSOL(propExitsolVbounds)
int SCIPpqueueFind(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1490
static SCIP_RETCODE initData(SCIP *scip, SCIP_PROP *prop, SCIP_Bool *infeasible)
static int inferInfoGetPos(INFERINFO inferinfo)
Definition: prop_vbounds.c:265
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:130
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:10920
#define SCIP_Bool
Definition: def.h:70
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:391
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1065
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17677
#define EVENTHDLR_NAME
Definition: prop_vbounds.c:121
#define getBoundtype(idx)
Definition: prop_vbounds.c:162
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)
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
Definition: implics.c:3363
SCIP_PROP * SCIPfindProp(SCIP *scip, const char *name)
Definition: scip_prop.c:320
#define EVENTHDLR_DESC
Definition: prop_vbounds.c:122
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
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 SCIPaddConflictRelaxedUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedub)
int SCIPgetNCliquesCreated(SCIP *scip)
Definition: scip_var.c:7576
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8250
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition: type_event.h:70
SCIP_EXPORT SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18030
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17723
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:2125
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip_prop.c:303
#define SCIP_REAL_MAX
Definition: def.h:164
static SCIP_RETCODE relaxVbdvar(SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd)
#define getBoundString(lower)
Definition: prop_vbounds.c:164
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17733
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:780
#define PROP_DELAY
Definition: prop_vbounds.c:107
static int varGetLbIndex(SCIP_PROPDATA *propdata, SCIP_VAR *var)
Definition: prop_vbounds.c:296
#define DEFAULT_MINNEWCLIQUES
Definition: prop_vbounds.c:138
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)
SCIP_VAR ** b
Definition: circlepacking.c:56
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:1236
#define ACTIVE
Definition: prop_vbounds.c:797
static INFERINFO getInferInfo(int pos, SCIP_BOUNDTYPE boundtype)
Definition: prop_vbounds.c:274
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)
static SCIP_RETCODE catchEvents(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_vbounds.c:348
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17667
#define PROP_PRIORITY
Definition: prop_vbounds.c:105
SCIP_EXPORT SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
Definition: var.c:17881
#define getOtherBoundIndex(idx)
Definition: prop_vbounds.c:167
public methods for message output
SCIP_EXPORT SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
Definition: var.c:17891
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
#define SCIP_Real
Definition: def.h:163
#define getBoundtypeString(type)
Definition: prop_vbounds.c:165
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:133
static SCIP_DECL_PROPPRESOL(propPresolVbounds)
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:43
#define DEFAULT_USEVBOUNDS
Definition: prop_vbounds.c:134
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for message handling
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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:6322
SCIP_EXPORT SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17977
public methods for propagator plugins
static SCIP_RETCODE propagateVbounds(SCIP *scip, SCIP_PROP *prop, SCIP_Bool force, SCIP_RESULT *result)
#define DEFAULT_DETECTCYCLES
Definition: prop_vbounds.c:137
static SCIP_DECL_SORTPTRCOMP(compVarboundIndices)
Definition: prop_vbounds.c:504
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2031
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: scip_var.c:1791
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:345
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
Definition: event.c:1044
SCIP_EXPORT int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17360
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
Definition: implics.c:3341
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:122
static SCIP_DECL_PROPRESPROP(propRespropVbounds)
SCIP_EXPORT int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18019
#define SCIP_EVENTTYPE_GUBCHANGED
Definition: type_event.h:67
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:8375
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
#define SCIPABORT()
Definition: def.h:342
public methods for global and local (sub)problems
SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb)
Definition: scip_var.c:4607
SCIP_EXPORT SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
Definition: var.c:17933
SCIP_Bool SCIPisPropagatedVbounds(SCIP *scip)
SCIP_EXPORT SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition: var.c:17913
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6202
SCIP_EXPORT int SCIPvarGetNVlbs(SCIP_VAR *var)
Definition: var.c:17859
public methods for propagators
static SCIP_RETCODE topologicalSort(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool *infeasible)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
uint64_t SCIP_EVENTTYPE
Definition: type_event.h:142
#define getUbIndex(idx)
Definition: prop_vbounds.c:160
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1335
memory allocation routines
static SCIP_DECL_PROPFREE(propFreeVbounds)