# 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 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file prop_vbounds.c
17  * @brief variable upper and lower bound propagator
18  * @author Stefan Heinz
19  * @author Jens Schulz
20  * @author Gerald Gamrath
21  *
22  * This propagator uses global bound information provided by SCIP to deduce global and local bound changes.
23  * It can take into account
24  * - implications (bound change following from specific value of a binary variable)
25  * - cliques (set of binary variables, each with a corresponding value, of which at most one variable can get the value)
26  * - variable lower/upper bounds (bounds of arbitrary variables that depend linearly on the value of another variable)
27  *
28  * The propagator does not look at a variable in whole, but at one point in time only handles one specific bound (lower
29  * or upper) of a variable and deduces changes for lower or upper bounds of other variables. The concept is as follows:
30  *
31  * 1) Extract variable bound data
32  *
33  * Implications and cliques are stored in a way such that given a variable and its new value, we can access all bound
34  * changes that can be deduced from setting the variable to that value. However, for variable bounds, this currently
35  * does not hold, they are only stored in the other direction, i.e. for a bound of a given variable, we have a list
36  * of all other bounds of variables that directly influence the bound of the given variable and a linear function
37  * describing how they do this.
38  * For the propagation, we need the other direction, thus we store it in the propagator data when the branch-and-bound
39  * solving process is about to begin.
40  *
41  * 2) Topological sorting of bounds of variable
42  *
43  * We compute a topological order of the bounds of variables. This is needed to define an order in which we will
44  * regard bounds of variables in the propagation process in order to avoid unneccessarily regarding the same variable
45  * bound multiple times because it was changed in the meantime when propagating another bound of a variable.
46  * Therefore, we implictly regard a directed graph, in which each node corresponds to a bound of a variable and there
47  * exists a directed edge from one node to another, if the bound corresponding to the former node influences the
48  * bound corresponding to the latter node. This is done by iteratively running a DFS until all nodes were visited.
49  * Note that there might be cycles in the graph, which are randomly broken, so the order is only almost topological.
50  *
51  * 3) Collecting bound changes
52  *
53  * For each bound of a variable, which can trigger bound changes of other variables, the propagator catches all
54  * events informing about a global change of the bound or a local tightening of the bound. The event handler
55  * then adds the bound of the variable to a priority queue, with the key in the priority queue corresponding
56  * to the position of the bound in the topological sort.
57  *
58  * 4) Propagating Bounds
59  *
60  * As long as there are bounds contained in the priority queue, the propagator pops one bound from the queue, which
61  * is the one most at the beginning of the topological sort, so it should not be influenced by propagating other
62  * bounds currently contained in the queue. Starting at this bound, all implication, clique, and variable bound
63  * information is used to deduce tigther bounds for other variables and change the bounds, if a tighter one is found.
64  * These bound changes trigger an event that will lead to adding the corresponding bound to the priority queue,
65  * if it is not contained, yet. The process is iterated until the priority queue contains no more bounds.
66  */
67
68 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
69
70 #include <assert.h>
71 #include <string.h>
72
73 #include "scip/prop_vbounds.h"
74
75 /**@name Propagator properties
76  *
77  * @{
78  */
79
80 #define PROP_NAME "vbounds"
81 #define PROP_DESC "propagates variable upper and lower bounds"
82 #define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_AFTERLPLOOP
83 #define PROP_PRIORITY 3000000 /**< propagator priority */
84 #define PROP_FREQ 1 /**< propagator frequency */
85 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
86
87 /**@} */
88
89 /**@name Event handler properties
90  *
91  * @{
92  */
93
94 #define EVENTHDLR_NAME "vbounds"
95 #define EVENTHDLR_DESC "bound change event handler for for vbounds propagator"
96
97 /**@} */
98
99 /**@name Default parameter values
100  *
101  * @{
102  */
103
104 #define DEFAULT_USEBDWIDENING TRUE /**< should bound widening be used to initialize conflict analysis? */
105 #define DEFAULT_USEIMPLICS FALSE /**< should implications be propagated? */
106 #define DEFAULT_USECLIQUES FALSE /**< should cliques be propagated? */
107 #define DEFAULT_USEVBOUNDS TRUE /**< should variable bounds be propagated? */
108 #define DEFAULT_DOTOPOSORT TRUE /**< should the bounds be topologically sorted in advance? */
109 #define DEFAULT_SORTCLIQUES FALSE /**< should cliques be regarded for the topological sort? */
110 #define DEFAULT_DETECTCYCLES FALSE /**< should cycles in the variable bound graph be identified? */
111
112 /**@} */
113
114 /**@name Propagator defines
115  *
116  * @{
117  *
118  * The propagator works on indices representing a bound of a variable. This index will be called bound index in the
119  * following. For a given active variable with problem index i (note that active variables have problem indices
120  * between 0 and nactivevariable - 1), the bound index of its lower bound is 2*i, the bound index of its upper
121  * bound is 2*i + 1. The other way around, a given bound index i corresponds to the variable with problem index
122  * i/2 (rounded down), and to the lower bound, if i is even, to the upper bound if i is odd.
123  * The following macros can be used to convert bound index into variable problem index and boundtype and vice versa.
124  */
125 #define getLbIndex(idx) (2*(idx))
126 #define getUbIndex(idx) (2*(idx)+1)
127 #define getVarIndex(idx) ((idx)/2)
128 #define getBoundtype(idx) (((idx) % 2 == 0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER)
129 #define isIndexLowerbound(idx) ((idx) % 2 == 0)
130 #define getBoundString(lower) ((lower) ? "lb" : "ub")
131 #define getBoundtypeString(type) ((type) == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper")
132 #define indexGetBoundString(idx) (getBoundString(isIndexLowerbound(idx)))
133 #define getOtherBoundIndex(idx) (((idx) % 2 == 0) ? (idx) + 1 : (idx) - 1)
134
135 /**@} */
136
137 /*
138  * Data structures
139  */
140
141 /** propagator data */
142 struct SCIP_PropData
143 {
144  SCIP_EVENTHDLR* eventhdlr; /**< event handler for catching bound changes */
145  SCIP_VAR** vars; /**< array containing all variable which are considered within the propagator */
146  SCIP_HASHMAP* varhashmap; /**< hashmap mapping from variable to index in the vars array */
147  int* topoorder; /**< array mapping on the bounds of variables in topological order;
148  * or -1, if the bound that should be at that position has no outgoing
149  * implications, cliques, or vbounds;
150  * i.e., for i < j and topoorder[i] != -1 != topoorder[j], the variable
151  * and boundtype represented by index topoorder[i] are earlier in the
152  * topological order than those represented by index topoorder[j]
153  */
154  int** vboundboundedidx; /**< array storing for each bound index the bound indices of all bounds
155  * influenced by this bound through variable bounds */
156  SCIP_Real** vboundcoefs; /**< array storing for each bound index the coefficients in the variable
157  * bounds influencing the corresponding bound index stored in
158  * vboundboundedidx */
159  SCIP_Real** vboundconstants; /**< array storing for each bound index the constants in the variable
160  * bounds influencing the corresponding bound index stored in
161  * vboundboundedidx */
162  int* nvbounds; /**< array storing for each bound index the number of vbounds stored */
163  int* vboundsize; /**< array with sizes of vbound arrays for the nodes */
164  int nbounds; /**< number of bounds of variables regarded (two times number of active variables) */
165  SCIP_PQUEUE* propqueue; /**< priority queue to handle the bounds of variables that were changed and have to be propagated */
166  SCIP_Bool* inqueue; /**< boolean array to store whether a bound of a variable is already contained in propqueue */
167  SCIP_Bool initialized; /**< was the data for propagation already initialized? */
168  SCIP_Bool usebdwidening; /**< should bound widening be used to initialize conflict analysis? */
169  SCIP_Bool useimplics; /**< should implications be propagated? */
170  SCIP_Bool usecliques; /**< should cliques be propagated? */
171  SCIP_Bool usevbounds; /**< should variable bounds be propagated? */
172  SCIP_Bool dotoposort; /**< should the bounds be topologically sorted in advance? */
173  SCIP_Bool sortcliques; /**< should cliques be regarded for the topological sort? */
174  SCIP_Bool detectcycles; /**< should cycles in the variable bound graph be identified? */
175 };
176
177 /** inference information */
178 struct InferInfo
179 {
180  union
181  {
182  struct
183  {
184  unsigned int pos:31; /**< position of the variable which forced that propagation */
185  unsigned int boundtype:1; /**< bound type which was the reason (0: lower, 1: upper) */
186  } asbits;
187  int asint; /**< inference information as a single int value */
188  } val;
189 };
190 typedef struct InferInfo INFERINFO;
191
192 /** converts an integer into an inference information */
193 static
195  int i /**< integer to convert */
196  )
197 {
198  INFERINFO inferinfo;
199
200  inferinfo.val.asint = i;
201
202  return inferinfo;
203 }
204
205 /** converts an inference information into an int */
206 static
208  INFERINFO inferinfo /**< inference information to convert */
209  )
210 {
211  return inferinfo.val.asint;
212 }
213
214 /** returns the propagation rule stored in the inference information */
215 static
217  INFERINFO inferinfo /**< inference information to convert */
218  )
219 {
220  assert((SCIP_BOUNDTYPE)inferinfo.val.asbits.boundtype == SCIP_BOUNDTYPE_LOWER
221  || (SCIP_BOUNDTYPE)inferinfo.val.asbits.boundtype == SCIP_BOUNDTYPE_UPPER);
222  return (SCIP_BOUNDTYPE)inferinfo.val.asbits.boundtype;
223 }
224
225 /** returns the position stored in the inference information */
226 static
228  INFERINFO inferinfo /**< inference information to convert */
229  )
230 {
231  return (int) inferinfo.val.asbits.pos;
232 }
233
234 /** constructs an inference information out of a position of a variable and a boundtype */
235 static
237  int pos, /**< position of the variable which forced that propagation */
238  SCIP_BOUNDTYPE boundtype /**< propagation rule that deduced the value */
239  )
240 {
241  INFERINFO inferinfo;
242
243  assert(boundtype == SCIP_BOUNDTYPE_LOWER || boundtype == SCIP_BOUNDTYPE_UPPER);
244  assert((int)boundtype >= 0 && (int)boundtype <= 1); /*lint !e685 !e568q*/
245  assert(pos >= 0);
246
247  inferinfo.val.asbits.pos = (unsigned int) pos; /*lint !e732*/
248  inferinfo.val.asbits.boundtype = (unsigned int) boundtype; /*lint !e641*/
249
250  return inferinfo;
251 }
252
253 /*
254  * Local methods
255  */
256
257 /* returns the lower bound index of a variable */
258 static
260  SCIP_PROPDATA* propdata, /**< propagator data */
261  SCIP_VAR* var /**< variable to get the index for */
262  )
263 {
264  assert(SCIPhashmapExists(propdata->varhashmap, var) == ((size_t)SCIPhashmapGetImage(propdata->varhashmap, var) > 0));
265
266  return getLbIndex((int)(size_t)SCIPhashmapGetImage(propdata->varhashmap, var) - 1);
267 }
268
269 /* returns the upper bound index of a variable */
270 static
272  SCIP_PROPDATA* propdata, /**< propagator data */
273  SCIP_VAR* var /**< variable to get the index for */
274  )
275 {
276  assert(SCIPhashmapExists(propdata->varhashmap, var) == ((size_t)SCIPhashmapGetImage(propdata->varhashmap, var) > 0));
277
278  return getUbIndex((int)(size_t)SCIPhashmapGetImage(propdata->varhashmap, var) - 1);
279 }
280
281 /** reset propagation data */
282 static
284  SCIP_PROPDATA* propdata /**< propagator data */
285  )
286 {
287  propdata->vars = NULL;
288  propdata->varhashmap = NULL;
289  propdata->topoorder = NULL;
290  propdata->vboundboundedidx = NULL;
291  propdata->vboundcoefs = NULL;
292  propdata->vboundconstants = NULL;
293  propdata->nvbounds = NULL;
294  propdata->vboundsize = NULL;
295  propdata->nbounds = 0;
296  propdata->initialized = FALSE;
297 }
298
299 /** catches events for variables */
300 static
302  SCIP* scip, /**< SCIP data structure */
303  SCIP_PROPDATA* propdata /**< propagator data */
304  )
305 {
306  SCIP_EVENTHDLR* eventhdlr;
307  SCIP_EVENTTYPE eventtype;
308  SCIP_VAR** vars;
309  SCIP_VAR* var;
310  SCIP_Bool lower;
311  int nbounds;
312  int v;
313  int idx;
314
315  assert(scip != NULL);
316  assert(propdata != NULL);
317  assert(propdata->vars != NULL);
318  assert(propdata->topoorder != NULL);
319
320  /* catch variable events according to computed eventtypes */
321  eventhdlr = propdata->eventhdlr;
322  assert(eventhdlr != NULL);
323
324  vars = propdata->vars;
325  nbounds = propdata->nbounds;
326
327  /* setup events */
328  for( v = 0; v < nbounds; ++v )
329  {
330  idx = propdata->topoorder[v];
331  assert(idx >= 0 && idx < nbounds);
332
333  var = vars[getVarIndex(idx)];
334  lower = isIndexLowerbound(idx);
335
336  /* if the bound does not influence another bound by implications, cliques, or vbounds,
337  * we do not create an event and do not catch changes of the bound;
338  * we mark this by setting the value in topoorder to -1
339  */
340  if( propdata->nvbounds[idx] == 0 && SCIPvarGetNImpls(var, lower) == 0 && SCIPvarGetNCliques(var, lower) == 0 )
341  {
342  propdata->topoorder[v] = -1;
343  continue;
344  }
345
346  /* determine eventtype that we want to catch depending on boundtype of variable */
347  if( lower )
349  else
351
352  SCIP_CALL( SCIPcatchVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*) (size_t) v, NULL) ); /*lint !e571*/
353  }
354
355  return SCIP_OKAY;
356 }
357
358 /** drops events for variables */
359 static
361  SCIP* scip, /**< SCIP data structure */
362  SCIP_PROPDATA* propdata /**< propagator data */
363  )
364 {
365  SCIP_EVENTHDLR* eventhdlr;
366  SCIP_EVENTTYPE eventtype;
367  SCIP_VAR** vars;
368  SCIP_VAR* var;
369  SCIP_Bool lower;
370  int nbounds;
371  int v;
372  int idx;
373
374  assert(propdata != NULL);
375
376  eventhdlr = propdata->eventhdlr;
377  assert(eventhdlr != NULL);
378
379  vars = propdata->vars;
380  nbounds = propdata->nbounds;
381
382  for( v = 0; v < nbounds; ++v )
383  {
384  idx = propdata->topoorder[v];
385
386  if( idx == -1 )
387  continue;
388
389  assert(idx >= 0 && idx < nbounds);
390
391  var = vars[getVarIndex(idx)];
392  lower = isIndexLowerbound(idx);
393
394  /* determine eventtype that we catch and now want to drop depending on boundtype of variable */
395  if( lower )
397  else
399
400  SCIP_CALL( SCIPdropVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*) (size_t) v, -1) ); /*lint !e571*/
401  }
402
403  return SCIP_OKAY;
404 }
405
406 #define INITMEMSIZE 5
407
408 /* adds a vbound to the propagator data to store it internally and allow forward propagation */
409 static
411  SCIP* scip, /**< SCIP data structure */
412  SCIP_PROPDATA* propdata, /**< propagator data */
413  int startidx, /**< index of bound of variable influencing the other variable */
414  int endidx, /**< index of bound of variable which is influenced */
415  SCIP_Real coef, /**< coefficient in the variable bound */
416  SCIP_Real constant /**< constant in the variable bound */
417  )
418 {
419  int nvbounds;
420
421  assert(scip != NULL);
422  assert(propdata != NULL);
423
424  if( propdata->vboundsize[startidx] == 0 )
425  {
426  /* allocate memory for storing vbounds */
427  propdata->vboundsize[startidx] = INITMEMSIZE;
428
429  SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundboundedidx[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
430  SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundcoefs[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
431  SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundconstants[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
432  }
433  else if( propdata->nvbounds[startidx] >= propdata->vboundsize[startidx] )
434  {
435  /* reallocate memory for storing vbounds */
436  propdata->vboundsize[startidx] = SCIPcalcMemGrowSize(scip, propdata->nvbounds[startidx] + 1);
437  assert(propdata->nvbounds[startidx] < propdata->vboundsize[startidx]);
438
439  SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundboundedidx[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
440  SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundcoefs[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
441  SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundconstants[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
442  }
443
444  nvbounds = propdata->nvbounds[startidx];
445  propdata->vboundboundedidx[startidx][nvbounds] = endidx;
446  propdata->vboundcoefs[startidx][nvbounds] = coef;
447  propdata->vboundconstants[startidx][nvbounds] = constant;
448  (propdata->nvbounds[startidx])++;
449
450  return SCIP_OKAY;
451 }
452
453 /** comparison method for two indices in the topoorder array, preferring higher indices because the order is reverse
454  * topological
455  */
456 static
457 SCIP_DECL_SORTPTRCOMP(compVarboundIndices)
458 {
459  int idx1 = (int)(size_t)elem1;
460  int idx2 = (int)(size_t)elem2;
461
462  return idx2 - idx1;
463 }
464
465 /* extract bound changes or infeasibility information from a cycle in the variable bound graph detected during
466  * depth-first search
467  */
468 static
470  SCIP* scip, /**< SCIP data structure */
471  SCIP_PROPDATA* propdata, /**< propagator data */
472  int* dfsstack, /**< array of size number of nodes to store the stack;
473  * only needed for performance reasons */
474  int* stacknextedge, /**< array storing the next edge to be visited in dfs for all nodes on the
475  * stack/in the current path; negative numbers represent a clique,
476  * positive numbers an implication (smaller numbers) or a variable bound */
477  int stacksize, /**< current stack size */
478  SCIP_Bool samebound, /**< does the cycle contain the same bound twice or both bounds of the same variable? */
479  SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
480
481  )
482 {
483  SCIP_VAR** vars;
484  SCIP_VAR* currvar;
485  SCIP_Bool currlower;
486
487  SCIP_Real coef = 1.0;
488  SCIP_Real constant = 0.0;
489  SCIP_Bool islower;
490  SCIP_Real newbound;
491  int cycleidx;
492  int startidx;
493  int ntmpimpls;
494  int j;
495  int k;
496
497  assert(scip != NULL);
498  assert(propdata != NULL);
499
500  vars = propdata->vars;
501
502  /* the last element on the stack is the end-point of the cycle */
503  cycleidx = dfsstack[stacksize - 1];
504
505  /* the same bound of the variable was visited already earlier on the current path, so the start-point of the cycle
506  * has the same index
507  */
508  if( samebound )
509  startidx = cycleidx;
510  /* the other bound of the variable was visited earlier on the current path, so the start-point of the cycle
511  * has the index of the other bound
512  */
513  else
514  startidx = getOtherBoundIndex(cycleidx);
515
516  /* search for the start-point of the cycle; since the endpoint is at position stacksize - 1 we start at stacksize - 2
517  * and go backwards
518  */
519  for( j = stacksize - 2; dfsstack[j] != startidx && j >= 0; --j ){};
520  assert(j >= 0);
521
522  for( ; j < stacksize - 1; ++j )
523  {
524  currvar = vars[getVarIndex(dfsstack[j])];
525  currlower = isIndexLowerbound(dfsstack[j]);
526
527  /* if we do not use implications, we assume the number of implications to be 0 (as we did before) */
528  ntmpimpls = (propdata->useimplics ? SCIPvarGetNImpls(currvar, currlower) : 0);
529
530  /* stacknextedge[j] <= 0 --> the last outgoing edge traversed during dfs starting from node dfsstack[j] was given
531  * by a clique
532  */
533  if( stacknextedge[j] <= 0 )
534  {
535  SCIP_Bool nextlower = isIndexLowerbound(dfsstack[j+1]);
536 #if defined(SCIP_DEBUG) || defined(SCIP_MORE_DEBUG)
537  SCIP_CLIQUE** tmpcliques = SCIPvarGetCliques(currvar, currlower);
538  SCIP_VAR** cliquevars;
539  SCIP_Bool* cliquevals;
540  int ntmpcliques = SCIPvarGetNCliques(currvar, currlower);
541  int ncliquevars;
542  int v;
543 #endif
544  /* there are four cases:
545  * a) lb(x) -> ub(y) ==> clique(x,y,...) ==> y <= 1 - x
546  * b) lb(x) -> lb(y) ==> clique(x,~y,...) ==> y >= x
547  * c) ub(x) -> ub(y) ==> clique(~x,y,...) ==> y <= x
548  * d) ub(x) -> lb(y) ==> clique(~x,~y,...) ==> y >= 1 - x
549  *
550  * in cases b) and c), coef=1.0 and constant=0.0; these are the cases where both nodes represent
551  * the same type of bound
552  * in cases a) and d), coef=-1.0 and constant=1.0; both nodes represent different types of bounds
553  *
554  * we do not need to change the overall coef and constant in cases b) and c), but for the others
555  */
556  if( currlower != nextlower )
557  {
558  coef = -coef;
559  constant = -constant + 1.0;
560  }
561
562  /* since the coefficient and constant only depend on the type of bounds of the two nodes (see below), we do not
563  * need to search for the variable in the clique; however, if debug output is enabled, we want to print the
564  * clique, if more debugging is enabled, we explicitly check that the variable and bound we expect are in the
565  * clique
566  */
567 #if defined(SCIP_DEBUG) || defined(SCIP_MORE_DEBUG)
568  if( stacknextedge[j] == 0 )
569  {
570  k = ntmpcliques - 1;
571  }
572  else
573  {
574  /* we processed at least one edge, so the next one should be -2 or smaller (we have a -1 offset) */
575  assert(stacknextedge[j] <= -2);
576
577  k = -stacknextedge[j] - 2;
578
579  assert(k < ntmpcliques);
580  }
581
582  cliquevars = SCIPcliqueGetVars(tmpcliques[k]);
583  cliquevals = SCIPcliqueGetValues(tmpcliques[k]);
584  ncliquevars = SCIPcliqueGetNVars(tmpcliques[k]);
585 #ifdef SCIP_DEBUG
586  SCIPdebugMsg(scip, "clique: ");
587  for( v = 0; v < ncliquevars; ++v )
588  {
589  SCIPdebugMsg(scip, "%s%s ", cliquevals[v] ? "" : "~", SCIPvarGetName(cliquevars[v]));
590  }
591  SCIPdebugMsg(scip, "(equation:%d)\n", SCIPcliqueIsEquation(tmpcliques[k]));
592 #endif
593 #ifdef SCIP_MORE_DEBUG
594  for( v = 0; v < ncliquevars; ++v )
595  {
596  if( cliquevars[v] == vars[getVarIndex(dfsstack[j+1])] && cliquevals[v] == !nextlower )
597  break;
598  }
599  assert(v < ncliquevars);
600 #endif
601
602  SCIPdebugMsg(scip, "%s(%s) -- (*%g + %g)[clique(<%s%s>,<%s%s>,...)] --> %s(%s)\n",
603  indexGetBoundString(dfsstack[j]), SCIPvarGetName(currvar),
604  (currlower != nextlower ? -1.0 : 1.0),
605  (currlower != nextlower ? 1.0 : 0.0),
606  (currlower ? "" : "~"), SCIPvarGetName(currvar),
607  (nextlower ? "~" : ""), SCIPvarGetName(vars[getVarIndex(dfsstack[j+1])]),
608  indexGetBoundString(dfsstack[j+1]), SCIPvarGetName(currvar));
609 #endif
610  }
611  /* stacknextedge[j] > 0 --> the last outgoing edge traversed during dfs starting from node dfsstack[j] was given
612  * by an implication or vbound. Implications are looked at first, so if stacknextedge[j] <= ntmpimpls, it comes
613  * from an implication
614  */
615  else if( stacknextedge[j] <= ntmpimpls )
616  {
617 #ifndef NDEBUG
618  SCIP_VAR** implvars = SCIPvarGetImplVars(currvar, currlower);
619 #endif
620  SCIP_BOUNDTYPE* impltypes = SCIPvarGetImplTypes(currvar, currlower);
621  SCIP_Real* implbounds = SCIPvarGetImplBounds(currvar, currlower);
622  SCIP_VAR* nextvar = vars[getVarIndex(dfsstack[j+1])];
623  SCIP_Real newconstant;
624  SCIP_Real newcoef;
625
626  k = stacknextedge[j] - 1;
627
628  assert(dfsstack[j+1] == (impltypes[k] == SCIP_BOUNDTYPE_LOWER ?
629  varGetLbIndex(propdata, implvars[k]) : varGetUbIndex(propdata, implvars[k])));
630
631  if( impltypes[k] == SCIP_BOUNDTYPE_LOWER )
632  {
633  newcoef = implbounds[k] - SCIPvarGetLbLocal(nextvar);
634
635  if( currlower )
636  {
637  newconstant = SCIPvarGetLbLocal(nextvar);
638  }
639  else
640  {
641  newconstant = implbounds[k];
642  newcoef *= -1.0;
643  }
644  }
645  else
646  {
647  assert(impltypes[k] == SCIP_BOUNDTYPE_UPPER);
648
649  newcoef = SCIPvarGetUbLocal(nextvar) - implbounds[k];
650
651  if( currlower )
652  {
653  newconstant = SCIPvarGetUbLocal(nextvar);
654  newcoef *= -1.0;
655  }
656  else
657  {
658  newconstant = implbounds[k];
659  }
660  }
661
662  coef = coef * newcoef;
663  constant = constant * newcoef + newconstant;
664
665  SCIPdebugMsg(scip, "%s(%s) -- (*%g + %g) --> %s(%s)\n",
666  indexGetBoundString(dfsstack[j]), SCIPvarGetName(vars[getVarIndex(dfsstack[j])]),
667  newcoef, newconstant,
668  indexGetBoundString(dfsstack[j+1]), SCIPvarGetName(vars[getVarIndex(dfsstack[j+1])]));
669  }
670  /* the edge was given by a variable bound relation */
671  else
672  {
673  assert(stacknextedge[j] > ntmpimpls);
674
675  k = stacknextedge[j] - ntmpimpls - 1;
676  assert(k < propdata->nvbounds[dfsstack[j]]);
677  assert(propdata->vboundboundedidx[dfsstack[j]][k] == dfsstack[j+1]);
678
679  SCIPdebugMsg(scip, "%s(%s) -- (*%g + %g) --> %s(%s)\n",
680  indexGetBoundString(dfsstack[j]), SCIPvarGetName(vars[getVarIndex(dfsstack[j])]),
681  propdata->vboundcoefs[dfsstack[j]][k], propdata->vboundconstants[dfsstack[j]][k],
682  indexGetBoundString(dfsstack[j+1]), SCIPvarGetName(vars[getVarIndex(dfsstack[j+1])]));
683
684  coef = coef * propdata->vboundcoefs[dfsstack[j]][k];
685  constant = constant * propdata->vboundcoefs[dfsstack[j]][k] + propdata->vboundconstants[dfsstack[j]][k];
686  }
687  }
688
689  SCIPdebugMsg(scip, "==> %s(%s) -- (*%g + %g) --> %s(%s)\n",
690  indexGetBoundString(startidx), SCIPvarGetName(vars[getVarIndex(startidx)]),
691  coef, constant,
692  indexGetBoundString(cycleidx), SCIPvarGetName(vars[getVarIndex(cycleidx)]));
693
694  islower = isIndexLowerbound(cycleidx);
695
696  /* we have a relation x <=/>= coef * x + constant now
697  * (the relation depends on islower, i.e., whether the last node in the cycle is a lower or upper bound)
698  * case 1) coef is 1.0 --> x cancels out and we have a statement 0 <=/>= constant.
699  * if we have a >= relation and constant is positive, we have a contradiction 0 >= constant
700  * if we have a <= relation and constant is negative, we have a contradiction 0 <= constant
701  * case 2) coef != 1.0 --> we have a relation x - coef * x <=/>= constant
702  * <=> (1 - coef) * x <=/>= constant
703  * if coef < 1.0 this gives us x >= constant / (1 - coef) (if islower=TRUE)
704  * or x <= constant / (1 - coef) (if islower=FALSE)
705  * if coef > 1.0, the relation signs need to be switched.
706  */
707  if( SCIPisEQ(scip, coef, 1.0) )
708  {
709  if( islower && SCIPisFeasPositive(scip, constant) )
710  {
711  SCIPdebugMsg(scip, "-> infeasible aggregated variable bound relation 0 >= %g\n", constant);
712  *infeasible = TRUE;
713  }
714  else if( !islower && SCIPisFeasNegative(scip, constant) )
715  {
716  SCIPdebugMsg(scip, "-> infeasible aggregated variable bound relation 0 <= %g\n", constant);
717  *infeasible = TRUE;
718  }
719  }
720  else
721  {
722  SCIP_Bool tightened;
723
724  newbound = constant / (1.0 - coef);
725
726  if( SCIPisGT(scip, coef, 1.0) )
727  islower = !islower;
728
729  if( islower )
730  {
731  SCIPdebugMsg(scip, "-> found new lower bound: <%s>[%g,%g] >= %g\n", SCIPvarGetName(vars[getVarIndex(cycleidx)]),
732  SCIPvarGetLbLocal(vars[getVarIndex(cycleidx)]), SCIPvarGetUbLocal(vars[getVarIndex(cycleidx)]), newbound);
733  SCIP_CALL( SCIPtightenVarLb(scip, vars[getVarIndex(cycleidx)], newbound, FALSE, infeasible, &tightened) );
734  }
735  else
736  {
737  SCIPdebugMsg(scip, "-> found new upper bound: <%s>[%g,%g] <= %g\n", SCIPvarGetName(vars[getVarIndex(cycleidx)]),
738  SCIPvarGetLbLocal(vars[getVarIndex(cycleidx)]), SCIPvarGetUbLocal(vars[getVarIndex(cycleidx)]), newbound);
739  SCIP_CALL( SCIPtightenVarUb(scip, vars[getVarIndex(cycleidx)], newbound, FALSE, infeasible, &tightened) );
740  }
741
742  if( tightened )
743  SCIPdebugMsg(scip, "---> applied new bound\n");
744  }
745
746  return SCIP_OKAY;
747 }
748
749 #define VISITED 1
750 #define ACTIVE 2
751 /** performs depth-first-search in the implicitly given directed graph from the given start index */
752 static
754  SCIP* scip, /**< SCIP data structure */
755  SCIP_PROPDATA* propdata, /**< propagator data */
756  int startnode, /**< node to start the depth-first-search */
757  int* visited, /**< array to store for each node, whether it was already visited */
758  int* dfsstack, /**< array of size number of nodes to store the stack;
759  * only needed for performance reasons */
760  int* stacknextedge, /**< array of size number of nodes to store the next edge to be visited in
761  * dfs for all nodes on the stack/in the current path; only needed for
762  * performance reasons */
763  int* dfsnodes, /**< array of nodes that can be reached starting at startnode, in reverse
764  * dfs order */
765  int* ndfsnodes, /**< pointer to store number of nodes that can be reached starting at
766  * startnode */
767  SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
768  )
769 {
770  SCIP_VAR** vars;
771  SCIP_VAR* startvar;
772  SCIP_Bool lower;
773  int stacksize;
774  int curridx;
775  int nimpls;
776  int idx;
777  /* for cycle detection, we need to mark currently active nodes, otherwise we just mark them as visited */
778  int visitedflag = (propdata->detectcycles ? ACTIVE : VISITED);
779
780  assert(startnode >= 0);
781  assert(startnode < propdata->nbounds);
782  assert(visited != NULL);
783  assert(visited[startnode] == 0);
784  assert(dfsstack != NULL);
785  assert(dfsnodes != NULL);
786  assert(ndfsnodes != NULL);
787  assert(infeasible != NULL);
788
789  *infeasible = FALSE;
790
791  vars = propdata->vars;
792
793  /* put start node on the stack */
794  dfsstack[0] = startnode;
795  stacknextedge[0] = 0;
796  stacksize = 1;
797  idx = -1;
798
799  /* we run until no more bounds indices are on the stack, i.e. all changed bounds were propagated */
800  while( stacksize > 0 )
801  {
802  /* get next node from stack */
803  curridx = dfsstack[stacksize - 1];
804
805  /* mark current node as visited */
806  assert((visited[curridx] != 0) == (stacknextedge[stacksize - 1] != 0));
807  visited[curridx] = visitedflag;
808
809  startvar = vars[getVarIndex(curridx)];
810  lower = isIndexLowerbound(curridx);
811
812  /* if the variable was fixed in the meantime, it is a loose end in the variable bound graph */
813  if( SCIPisFeasGE(scip, SCIPvarGetLbGlobal(startvar), SCIPvarGetUbGlobal(startvar)) )
814  goto REMOVE;
815
816  nimpls = 0;
817
818  if( propdata->sortcliques && propdata->usecliques && stacknextedge[stacksize - 1] == 0 )
819  stacknextedge[stacksize - 1] = -1;
820
821  /* stacknextedge is negative, if the last visited edge from the current node belongs to a clique;
822  * the index of the clique in the variable's clique list equals abs(stacknextedge) - 1
823  */
824  if( propdata->sortcliques && propdata->usecliques && stacknextedge[stacksize - 1] < 0 )
825  {
826  SCIP_CLIQUE** cliques;
827  int ncliques;
828  int j;
829  int i;
830  SCIP_Bool found;
831
832  ncliques = SCIPvarGetNCliques(startvar, lower);
833  cliques = SCIPvarGetCliques(startvar, lower);
834  found = FALSE;
835
836  assert(stacknextedge[stacksize - 1] == -1 || -stacknextedge[stacksize - 1] - 1 <= ncliques);
837
838  /* iterate over all not yet handled cliques and search for an unvisited node */
839  for( j = -stacknextedge[stacksize - 1] - 1; j < ncliques; ++j )
840  {
841  SCIP_VAR** cliquevars;
842  SCIP_Bool* cliquevals;
843  int ncliquevars;
844
845  cliquevars = SCIPcliqueGetVars(cliques[j]);
846  cliquevals = SCIPcliqueGetValues(cliques[j]);
847  ncliquevars = SCIPcliqueGetNVars(cliques[j]);
848
849  for( i = 0; i < ncliquevars; ++i )
850  {
851  if( cliquevars[i] == startvar )
852  continue;
853
854  if( cliquevals[i] )
855  idx = varGetUbIndex(propdata, cliquevars[i]);
856  else
857  idx = varGetLbIndex(propdata, cliquevars[i]);
858
859  /* we reached a variable that was already visited on the active path, so we have a cycle in the variable
860  * bound graph and try to extract valid bound changes from it or detect infeasibility
861  */
862  if( idx >= 0 && (visited[idx] == ACTIVE || visited[getOtherBoundIndex(idx)] == ACTIVE)
863  && !SCIPisFeasGE(scip, SCIPvarGetLbGlobal(cliquevars[i]), SCIPvarGetUbGlobal(cliquevars[i])) )
864  {
865  SCIPdebugMsg(scip, "found cycle\n");
866
867  dfsstack[stacksize] = idx;
868  stacknextedge[stacksize - 1] = -j - 2;
869
870  SCIP_CALL( extractCycle(scip, propdata, dfsstack, stacknextedge, stacksize + 1,
871  visited[idx] == ACTIVE, infeasible) );
872
873  if( *infeasible )
874  break;
875  }
876
877  /* break when the first unvisited node is reached */
878  if( idx >= 0 && !visited[idx] )
879  {
880  found = TRUE;
881  break;
882  }
883  }
884  if( found )
885  break;
886  }
887
888  /* we stopped because we found an unhandled node and not because we reached the end of the list */
889  if( found )
890  {
891  assert(idx >= 0);
892  assert(!visited[idx]);
893  assert(j < ncliques);
894
895  SCIPdebugMsg(scip, "clique: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
897
898  /* put the adjacent node onto the stack */
899  dfsstack[stacksize] = idx;
900  stacknextedge[stacksize] = 0;
901  stacknextedge[stacksize - 1] = -j - 2;
902  stacksize++;
903  assert(stacksize <= propdata->nbounds);
904
905  /* restart while loop, get next index from stack */
906  continue;
907  }
908  else
909  {
910  /* we did not find an edge to an unhandled node given by a clique */
911  stacknextedge[stacksize - 1] = 0;
912  }
913  }
914  assert(stacknextedge[stacksize - 1] >= 0);
915
916  /* go over edges given by implications */
917  if( propdata->useimplics )
918  {
919  nimpls = SCIPvarGetNImpls(startvar, lower);
920
921  if( stacknextedge[stacksize - 1] < nimpls )
922  {
923  SCIP_VAR** implvars;
924  SCIP_BOUNDTYPE* impltypes;
925  int* implids;
926  int i;
927
928  implvars = SCIPvarGetImplVars(startvar, lower);
929  impltypes = SCIPvarGetImplTypes(startvar, lower);
930  implids = SCIPvarGetImplIds(startvar, lower);
931
932  for( i = stacknextedge[stacksize - 1]; i < nimpls; ++i )
933  {
934  /* it might happen that implications point to inactive variables (normally, those are removed when a
935  * variable becomes inactive, but in some cases, it cannot be done), we have to ignore these variables
936  */
937  if( !SCIPvarIsActive(implvars[i]) )
938  continue;
939
940  /* implication is just a shortcut, so we dont regard it now, because will later go the long way, anyway;
941  * however, if we do regard cliques for the topological order, we use them to get a better order
942  */
943  if( propdata->usecliques && !propdata->sortcliques && implids[i] < 0 )
944  continue;
945
946  idx = (impltypes[i] == SCIP_BOUNDTYPE_LOWER ?
947  varGetLbIndex(propdata, implvars[i]) : varGetUbIndex(propdata, implvars[i]));
948
949  /* we reached a variable that was already visited on the active path, so we have a cycle in the variable
950  * bound graph and try to extract valid bound changes from it or detect infeasibility
951  */
952  if( idx >= 0 && (visited[idx] == ACTIVE || visited[getOtherBoundIndex(idx)] == ACTIVE)
953  && !SCIPisFeasGE(scip, SCIPvarGetLbGlobal(implvars[i]), SCIPvarGetUbGlobal(implvars[i])) )
954  {
955  SCIPdebugMsg(scip, "found cycle\n");
956
957  dfsstack[stacksize] = idx;
958  stacknextedge[stacksize - 1] = i + 1;
959
960  SCIP_CALL( extractCycle(scip, propdata, dfsstack, stacknextedge, stacksize + 1,
961  visited[idx] == ACTIVE, infeasible) );
962
963  if( *infeasible )
964  break;
965  }
966
967  /* break when the first unvisited node is reached */
968  if( idx >= 0 && !visited[idx] )
969  break;
970  }
971
972  /* we stopped because we found an unhandled node and not because we reached the end of the list */
973  if( i < nimpls )
974  {
975  assert(!visited[idx]);
976
977  SCIPdebugMsg(scip, "impl: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
979
980  /* put the adjacent node onto the stack */
981  dfsstack[stacksize] = idx;
982  stacknextedge[stacksize] = 0;
983  stacknextedge[stacksize - 1] = i + 1;
984  stacksize++;
985  assert(stacksize <= propdata->nbounds);
986
987  /* restart while loop, get next index from stack */
988  continue;
989  }
990  else
991  {
992  stacknextedge[stacksize - 1] = nimpls;
993  }
994  }
995  }
996  assert(stacknextedge[stacksize - 1] >= nimpls);
997
998  /* go over edges corresponding to varbounds */
999  if( propdata->usevbounds )
1000  {
1001  int nvbounds;
1002  int* vboundidx;
1003  int i;
1004
1005  nvbounds = propdata->nvbounds[curridx];
1006  vboundidx = propdata->vboundboundedidx[curridx];
1007
1008  /* iterate over all vbounds for the given bound */
1009  for( i = stacknextedge[stacksize - 1] - nimpls; i < nvbounds; ++i )
1010  {
1011  idx = vboundidx[i];
1012  assert(idx >= 0);
1013
1014  if( (visited[idx] == ACTIVE || visited[getOtherBoundIndex(idx)] == ACTIVE)
1015  && !SCIPisFeasGE(scip, SCIPvarGetLbGlobal(vars[getVarIndex(idx)]), SCIPvarGetUbGlobal(vars[getVarIndex(idx)])) )
1016  {
1017  SCIPdebugMsg(scip, "found cycle\n");
1018
1019  dfsstack[stacksize] = idx;
1020  stacknextedge[stacksize - 1] = nimpls + i + 1;
1021
1022  /* we reached a variable that was already visited on the active path, so we have a cycle in the variable
1023  * bound graph and try to extract valid bound changes from it or detect infeasibility
1024  */
1025  SCIP_CALL( extractCycle(scip, propdata, dfsstack, stacknextedge, stacksize + 1,
1026  visited[idx] == ACTIVE, infeasible) );
1027
1028  if( *infeasible )
1029  break;
1030  }
1031
1032  /* break when the first unvisited node is reached */
1033  if( !visited[idx] )
1034  break;
1035  }
1036
1037  if( *infeasible )
1038  break;
1039
1040  /* we stopped because we found an unhandled node and not because we reached the end of the list */
1041  if( i < nvbounds )
1042  {
1043  assert(!visited[idx]);
1044
1045  SCIPdebugMsg(scip, "vbound: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
1046  indexGetBoundString(idx), SCIPvarGetName(vars[getVarIndex(idx)]));
1047
1048  /* put the adjacent node onto the stack */
1049  dfsstack[stacksize] = idx;
1050  stacknextedge[stacksize] = 0;
1051  stacknextedge[stacksize - 1] = nimpls + i + 1;
1052  stacksize++;
1053  assert(stacksize <= propdata->nbounds);
1054
1055  /* restart while loop, get next index from stack */
1056  continue;
1057  }
1058
1059  }
1060  REMOVE:
1061  /* the current node was completely handled, remove it from stack */
1062  stacksize--;
1063
1064  SCIPdebugMsg(scip, "topoorder[%d] = %s(%s)\n", *ndfsnodes, getBoundString(lower), SCIPvarGetName(startvar));
1065
1066  /* store node in the sorted nodes array */
1067  dfsnodes[(*ndfsnodes)] = curridx;
1068  assert(visited[curridx] == visitedflag);
1069  visited[curridx] = VISITED;
1070  (*ndfsnodes)++;
1071  }
1072
1073  return SCIP_OKAY;
1074 }
1075
1076 /** sort the bounds of variables topologically */
1077 static
1079  SCIP* scip, /**< SCIP data structure */
1080  SCIP_PROPDATA* propdata, /**< propagator data */
1081  SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
1082  )
1083 {
1084  int* dfsstack;
1085  int* stacknextedge;
1086  int* visited;
1087  int nsortednodes;
1088  int nbounds;
1089  int i;
1090
1091  assert(scip != NULL);
1092  assert(propdata != NULL);
1093  assert(infeasible != NULL);
1094
1095  nbounds = propdata->nbounds;
1096
1097  SCIP_CALL( SCIPallocBufferArray(scip, &dfsstack, nbounds) );
1098  SCIP_CALL( SCIPallocBufferArray(scip, &stacknextedge, nbounds) );
1099  SCIP_CALL( SCIPallocClearBufferArray(scip, &visited, nbounds) );
1100
1101  nsortednodes = 0;
1102
1103  /* while there are unvisited nodes, run dfs starting from one of these nodes; the dfs orders are stored in the
1104  * topoorder array, later dfs calls are just appended after the stacks of previous dfs calls, which gives us a
1105  * reverse topological order
1106  */
1107  for( i = 0; i < nbounds && !(*infeasible); ++i )
1108  {
1109  if( !visited[i] )
1110  {
1111  SCIP_CALL( dfs(scip, propdata, i, visited, dfsstack, stacknextedge, propdata->topoorder, &nsortednodes, infeasible) );
1112  }
1113  }
1114  assert((nsortednodes == nbounds) || (*infeasible));
1115
1116  SCIPfreeBufferArray(scip, &visited);
1117  SCIPfreeBufferArray(scip, &stacknextedge);
1118  SCIPfreeBufferArray(scip, &dfsstack);
1119
1120  return SCIP_OKAY;
1121 }
1122
1123 /** initializes the internal data for the variable bounds propagator */
1124 static
1126  SCIP* scip, /**< SCIP data structure */
1127  SCIP_PROP* prop, /**< vbounds propagator */
1128  SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
1129  )
1130 {
1131  SCIP_PROPDATA* propdata;
1132  SCIP_VAR** vars;
1133  int nvars;
1134  int nbounds;
1135  int startidx;
1136  int v;
1137  int n;
1138
1139  assert(scip != NULL);
1140  assert(prop != NULL);
1141  assert(infeasible != NULL);
1142
1143  /* get propagator data */
1144  propdata = SCIPpropGetData(prop);
1145  assert(propdata != NULL);
1146  assert(!propdata->initialized);
1147
1148  SCIPdebugMsg(scip, "initialize vbounds propagator for problem <%s>\n", SCIPgetProbName(scip));
1149
1150  vars = SCIPgetVars(scip);
1151  nvars = SCIPgetNVars(scip);
1152  nbounds = 2 * nvars;
1153
1154  *infeasible = FALSE;
1155
1156  /* store size of the bounds of variables array */
1157  propdata->nbounds = nbounds;
1158
1159  if( nbounds == 0 )
1160  return SCIP_OKAY;
1161
1162  propdata->initialized = TRUE;
1163
1164  /* prepare priority queue structure */
1165  SCIP_CALL( SCIPpqueueCreate(&propdata->propqueue, nvars, 2.0, compVarboundIndices) );
1166  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->inqueue, nbounds) );
1167  BMSclearMemoryArray(propdata->inqueue, nbounds);
1168
1169  /* we need to copy the variable since this array is the basis of the propagator and the corresponding variable array
1170  * within SCIP might change during the search
1171  */
1172  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &propdata->vars, vars, nvars) );
1173  SCIP_CALL( SCIPhashmapCreate(&propdata->varhashmap, SCIPblkmem(scip), nvars) );
1174
1175  for( v = 0; v < nvars; ++v )
1176  {
1177  SCIP_CALL( SCIPhashmapInsert(propdata->varhashmap, propdata->vars[v], (void*)(size_t)(v + 1)) );
1178  }
1179
1180  /* allocate memory for the arrays of the propdata */
1181  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->topoorder, nbounds) );
1182  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->vboundboundedidx, nbounds) );
1183  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->vboundcoefs, nbounds) );
1184  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->vboundconstants, nbounds) );
1185  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->nvbounds, nbounds) );
1186  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->vboundsize, nbounds) );
1187  BMSclearMemoryArray(propdata->vboundboundedidx, nbounds);
1188  BMSclearMemoryArray(propdata->vboundcoefs, nbounds);
1189  BMSclearMemoryArray(propdata->vboundconstants, nbounds);
1190  BMSclearMemoryArray(propdata->nvbounds, nbounds);
1191  BMSclearMemoryArray(propdata->vboundsize, nbounds);
1192
1193  for( v = 0; v < nbounds; ++v )
1194  {
1195  propdata->topoorder[v] = v;
1196  propdata->vboundboundedidx[v] = NULL;
1197  propdata->vboundcoefs[v] = NULL;
1198  propdata->vboundconstants[v] = NULL;
1199  propdata->nvbounds[v] = 0;
1200  propdata->vboundsize[v] = 0;
1201  }
1202
1203  /* collect information about varbounds */
1204  for( v = 0; v < nbounds; ++v )
1205  {
1206  SCIP_VAR** vbvars;
1207  SCIP_VAR* var;
1208  SCIP_Real* coefs;
1209  SCIP_Real* constants;
1210  SCIP_Bool lower;
1211  int nvbvars;
1212
1213  var = vars[getVarIndex(v)];
1214  lower = isIndexLowerbound(v);
1215
1216  /* get the variable bound informations for the current variable */
1217  if( lower )
1218  {
1219  vbvars = SCIPvarGetVlbVars(var);
1220  coefs = SCIPvarGetVlbCoefs(var);
1221  constants = SCIPvarGetVlbConstants(var);
1222  nvbvars = SCIPvarGetNVlbs(var);
1223  }
1224  else
1225  {
1226  vbvars = SCIPvarGetVubVars(var);
1227  coefs = SCIPvarGetVubCoefs(var);
1228  constants = SCIPvarGetVubConstants(var);
1229  nvbvars = SCIPvarGetNVubs(var);
1230  }
1231
1232  /* loop over all variable bounds; a variable lower bound has the form: x >= b*y + d,
1233  * a variable upper bound the form x <= b*y + d */
1234  for( n = 0; n < nvbvars; ++n )
1235  {
1236  SCIP_VAR* vbvar;
1237  SCIP_Real coef;
1238  SCIP_Real constant;
1239
1240  vbvar = vbvars[n];
1241  coef = coefs[n];
1242  constant = constants[n];
1243  assert(vbvar != NULL);
1244
1245  /* transform variable bound variable to an active variable, if possible */
1246  SCIP_CALL( SCIPgetProbvarSum(scip, &vbvar, &coef, &constant) );
1247  assert(vbvar != NULL);
1248
1249  if( !SCIPvarIsActive(vbvar) )
1250  continue;
1251
1252  /* if the coefficient is positive, the type of bound is the same for the bounded and the bounding variable */
1253  if( SCIPisPositive(scip, coef) )
1254  startidx = (lower ? varGetLbIndex(propdata, vbvar) : varGetUbIndex(propdata, vbvar));
1255  else
1256  startidx = (lower ? varGetUbIndex(propdata, vbvar) : varGetLbIndex(propdata, vbvar));
1257  assert(startidx >= 0);
1258
1259  /* If the vbvar is binary, the vbound should be stored as an implication already.
1260  * However, it might happen that vbvar was integer when the variable bound was added, but was converted
1261  * to a binary variable later during presolving when its upper bound was changed to 1. In this case,
1262  * the implication might not have been created.
1263  */
1264  if( SCIPvarGetType(vbvar) == SCIP_VARTYPE_BINARY
1265  && SCIPvarHasImplic(vbvar, isIndexLowerbound(startidx), var, getBoundtype(v)) )
1266  {
1267  SCIPdebugMsg(scip, "varbound <%s> %s %g * <%s> + %g not added to propagator data due to reverse implication\n",
1268  SCIPvarGetName(var), (lower ? ">=" : "<="), coef,
1269  SCIPvarGetName(vbvar), constant);
1270  }
1271  else
1272  {
1273  SCIP_CALL( addVbound(scip, propdata, startidx, v, coef, constant) );
1274
1275  SCIPdebugMsg(scip, "varbound <%s> %s %g * <%s> + %g added to propagator data\n",
1276  SCIPvarGetName(var), (lower ? ">=" : "<="), coef,
1277  SCIPvarGetName(vbvar), constant);
1278
1279  }
1280  }
1281  }
1282
1283  /* sort the bounds topologically */
1284  if( propdata->dotoposort )
1285  {
1286  SCIP_CALL( topologicalSort(scip, propdata, infeasible) );
1287  }
1288
1289  /* catch variable events */
1290  SCIP_CALL( catchEvents(scip, propdata) );
1291
1292  return SCIP_OKAY;
1293 }
1294
1295 /** resolves a propagation by adding the variable which implied that bound change */
1296 static
1298  SCIP* scip, /**< SCIP data structure */
1299  SCIP_PROPDATA* propdata, /**< propagator data */
1300  SCIP_VAR* var, /**< variable to be reported */
1301  SCIP_BOUNDTYPE boundtype, /**< bound to be reported */
1302  SCIP_BDCHGIDX* bdchgidx /**< the index of the bound change, representing the point of time where
1303  * the change took place, or NULL for the current local bounds */
1304  )
1305 {
1306  assert(propdata != NULL);
1307  assert(boundtype == SCIP_BOUNDTYPE_LOWER || boundtype == SCIP_BOUNDTYPE_UPPER);
1308
1309  SCIPdebugMsg(scip, " -> add %s bound of variable <%s> as reason\n",
1310  getBoundtypeString(boundtype), SCIPvarGetName(var));
1311
1312  switch( boundtype )
1313  {
1314  case SCIP_BOUNDTYPE_LOWER:
1315  SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) );
1316  break;
1317  case SCIP_BOUNDTYPE_UPPER:
1318  SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) );
1319  break;
1320  default:
1321  SCIPerrorMessage("invalid bound type <%d>\n", boundtype);
1322  SCIPABORT();
1323  return SCIP_INVALIDDATA; /*lint !e527*/
1324  }
1325
1326  return SCIP_OKAY;
1327 }
1328
1329 /** relaxes bound of give variable as long as the given inference bound still leads to a cutoff and add that bound
1330  * change to the conflict set
1331  */
1332 static
1334  SCIP* scip, /**< SCIP data structure */
1335  SCIP_VAR* var, /**< variable for which the upper bound should be relaxed */
1336  SCIP_BOUNDTYPE boundtype, /**< boundtype used for the variable bound variable */
1337  SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where
1338  * the change took place, or NULL for the current local bounds */
1339  SCIP_Real relaxedbd /**< relaxed bound */
1340  )
1341 {
1342  if( boundtype == SCIP_BOUNDTYPE_LOWER )
1343  {
1344  SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, relaxedbd) );
1345  }
1346  else
1347  {
1348  assert(boundtype == SCIP_BOUNDTYPE_UPPER);
1349  SCIP_CALL( SCIPaddConflictRelaxedUb(scip, var, bdchgidx, relaxedbd) );
1350  }
1351
1352  return SCIP_OKAY;
1353 }
1354
1355 /** compute the relaxed bound which is sufficient to propagate the inference lower bound of given variable */
1356 static
1358  SCIP* scip, /**< SCIP data structure */
1359  SCIP_VAR* var, /**< variable which was propagated */
1360  SCIP_Real inferlb, /**< inference lower bound */
1361  SCIP_Real coef, /**< inference variable bound coefficient used */
1362  SCIP_Real constant /**< inference variable bound constant used */
1363  )
1364 {
1365  SCIP_Real relaxedbd;
1366
1367  if( SCIPvarIsIntegral(var) )
1368  relaxedbd = (inferlb - 1.0 + 2*SCIPfeastol(scip) - constant) / coef;
1369  else
1370  relaxedbd = (inferlb - constant) / coef;
1371
1372  /* check the computed relaxed lower/upper bound is a proper reason for the inference bound which has to be explained */
1373  assert(SCIPisEQ(scip, inferlb, SCIPadjustedVarLb(scip, var, relaxedbd * coef + constant)));
1374
1375  return relaxedbd;
1376 }
1377
1378 /** analyzes an infeasibility which was reached by updating the lower bound of the inference variable above its upper
1379  * bound
1380  */
1381 static
1383  SCIP* scip, /**< SCIP data structure */
1384  SCIP_PROPDATA* propdata, /**< propagator data */
1385  SCIP_VAR* infervar, /**< variable which led to a cutoff */
1386  SCIP_Real inferlb, /**< lower bound which led to infeasibility */
1387  SCIP_VAR* vbdvar, /**< variable which is the reason for the lower bound change */
1388  SCIP_BOUNDTYPE boundtype, /**< bound which is the reason for the lower bound change */
1389  SCIP_Real coef, /**< inference variable bound coefficient used */
1390  SCIP_Real constant, /**< inference variable bound constant used */
1391  SCIP_Bool canwide /**< can bound widening be used (for vbounds) or not
1392  * (for implications or cliques) */
1393  )
1394 {
1395  assert(scip != NULL);
1396  assert(propdata != NULL);
1397  assert(infervar != NULL);
1398  assert(SCIPisEQ(scip, SCIPvarGetUbLocal(infervar), SCIPgetVarUbAtIndex(scip, infervar, NULL, FALSE)));
1399  assert(SCIPisEQ(scip, SCIPgetVarUbAtIndex(scip, infervar, NULL, TRUE), SCIPgetVarUbAtIndex(scip, infervar, NULL, FALSE)));
1400  assert(SCIPisGT(scip, inferlb, SCIPvarGetUbLocal(infervar)));
1401  assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING);
1402
1403  /* check if conflict analysis is applicable */
1405  return SCIP_OKAY;
1406
1407  if( canwide && propdata->usebdwidening )
1408  {
1409  SCIP_Real relaxedbd;
1410  SCIP_Real relaxedub;
1411
1412  SCIPdebugMsg(scip, "try to create conflict using bound widening order: inference variable, variable bound variable\n");
1413
1414  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1416
1417  /* adjust lower bound */
1418  inferlb = SCIPadjustedVarLb(scip, infervar, inferlb);
1419
1420  /* compute a relaxed upper bound which would be sufficient to be still infeasible */
1421  if( SCIPvarIsIntegral(infervar) )
1422  relaxedub = inferlb - 1.0;
1423  else
1424  relaxedub = inferlb - 2*SCIPfeastol(scip);
1425
1426  /* try to relax inference variable upper bound such that the infeasibility is still given */
1427  SCIP_CALL( SCIPaddConflictRelaxedUb(scip, infervar, NULL, relaxedub) );
1428
1429  /* collect the upper bound which is reported to the conflict analysis */
1430  relaxedub = SCIPgetConflictVarUb(scip, infervar);
1431
1432  /* adjust inference bound with respect to the upper bound reported to the conflict analysis */
1433  if( SCIPvarIsIntegral(infervar) )
1434  relaxedub = relaxedub + 1.0;
1435  else
1436  relaxedub = relaxedub + 2*SCIPfeastol(scip);
1437
1438  /* compute the relaxed bound which is sufficient to propagate the inference lower bound of given variable */
1439  relaxedbd = computeRelaxedLowerbound(scip, infervar, relaxedub, coef, constant);
1440
1441  /* try to relax variable bound variable */
1442  SCIP_CALL( relaxVbdvar(scip, vbdvar, boundtype, NULL, relaxedbd) );
1443
1444  /* analyze the conflict */
1445  SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
1446  }
1447  else
1448  {
1449  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1451
1452  /* add upper bound of the variable for which we tried to change the lower bound */
1453  SCIP_CALL( SCIPaddConflictUb(scip, infervar, NULL) );
1454
1455  /* add (correct) bound of the variable which let to the new lower bound */
1456  SCIP_CALL( resolvePropagation(scip, propdata, vbdvar, boundtype, NULL) );
1457
1458  /* analyze the conflict */
1459  SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
1460  }
1461
1462  return SCIP_OKAY;
1463 }
1464
1465 /** compute the relaxed bound which is sufficient to propagate the inference upper bound of given variable */
1466 static
1468  SCIP* scip, /**< SCIP data structure */
1469  SCIP_VAR* var, /**< variable which was propagated */
1470  SCIP_Real inferub, /**< inference upper bound */
1471  SCIP_Real coef, /**< inference variable bound coefficient used */
1472  SCIP_Real constant /**< inference variable bound constant used */
1473  )
1474 {
1475  SCIP_Real relaxedbd;
1476
1477  if( SCIPvarIsIntegral(var) )
1478  relaxedbd = (inferub + 1.0 - 2*SCIPfeastol(scip) - constant) / coef;
1479  else
1480  relaxedbd = (inferub - constant) / coef;
1481
1482  /* check the computed relaxed lower/upper bound is a proper reason for the inference bound which has to be explained */
1483  assert(SCIPisEQ(scip, inferub, SCIPadjustedVarUb(scip, var, relaxedbd * coef + constant)));
1484
1485  return relaxedbd;
1486 }
1487
1488 /** analyzes an infeasibility which was reached by updating the upper bound of the inference variable below its lower
1489  * bound
1490  */
1491 static
1493  SCIP* scip, /**< SCIP data structure */
1494  SCIP_PROPDATA* propdata, /**< propagator data */
1495  SCIP_VAR* infervar, /**< variable which led to a cutoff */
1496  SCIP_Real inferub, /**< upper bound which led to infeasibility */
1497  SCIP_VAR* vbdvar, /**< variable which is the reason for the upper bound change */
1498  SCIP_BOUNDTYPE boundtype, /**< bound which is the reason for the upper bound change */
1499  SCIP_Real coef, /**< inference variable bound coefficient used */
1500  SCIP_Real constant, /**< inference variable bound constant used */
1501  SCIP_Bool canwide /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1502  )
1503 {
1504  assert(scip != NULL);
1505  assert(propdata != NULL);
1506  assert(infervar != NULL);
1507  assert(SCIPisEQ(scip, SCIPvarGetLbLocal(infervar), SCIPgetVarLbAtIndex(scip, infervar, NULL, FALSE)));
1508  assert(SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, infervar, NULL, TRUE), SCIPgetVarLbAtIndex(scip, infervar, NULL, FALSE)));
1509  assert(SCIPisLT(scip, inferub, SCIPvarGetLbLocal(infervar)));
1510  assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING);
1511
1512  /* check if conflict analysis is applicable */
1514  return SCIP_OKAY;
1515
1516  if( canwide && propdata->usebdwidening )
1517  {
1518  SCIP_Real relaxedbd;
1519  SCIP_Real relaxedlb;
1520
1521  SCIPdebugMsg(scip, "try to create conflict using bound widening order: inference variable, variable bound variable\n");
1522
1523  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1525
1526  /* adjust upper bound */
1527  inferub = SCIPadjustedVarUb(scip, infervar, inferub);
1528
1529  /* compute a relaxed lower bound which would be sufficient to be still infeasible */
1530  if( SCIPvarIsIntegral(infervar) )
1531  relaxedlb = inferub + 1.0;
1532  else
1533  relaxedlb = inferub + 2*SCIPfeastol(scip);
1534
1535  /* try to relax inference variable lower bound such that the infeasibility is still given */
1536  SCIP_CALL( SCIPaddConflictRelaxedLb(scip, infervar, NULL, relaxedlb) );
1537
1538  /* collect the lower bound which is reported to the conflict analysis */
1539  relaxedlb = SCIPgetConflictVarLb(scip, infervar);
1540
1541  /* adjust inference bound with respect to the upper bound reported to the conflict analysis */
1542  if( SCIPvarIsIntegral(infervar) )
1543  relaxedlb = relaxedlb - 1.0;
1544  else
1545  relaxedlb = relaxedlb - 2*SCIPfeastol(scip);
1546
1547  /* compute the relaxed bound which is sufficient to propagate the inference upper bound of given variable */
1548  relaxedbd = computeRelaxedUpperbound(scip, infervar, relaxedlb, coef, constant);
1549
1550  /* try to relax variable bound variable */
1551  SCIP_CALL( relaxVbdvar(scip, vbdvar, boundtype, NULL, relaxedbd) );
1552
1553  /* analyze the conflict */
1554  SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
1555  }
1556  else
1557  {
1558  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1560
1561  /* add lower bound of the variable for which we tried to change the upper bound */
1562  SCIP_CALL( SCIPaddConflictLb(scip, infervar, NULL) );
1563
1564  /* add (correct) bound of the variable which let to the new upper bound */
1565  SCIP_CALL( resolvePropagation(scip, propdata, vbdvar, boundtype, NULL) );
1566
1567  /* analyze the conflict */
1568  SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
1569  }
1570
1571  return SCIP_OKAY;
1572 }
1573
1574 /* tries to tighten the (global) lower bound of the given variable to the given new bound */
1575 static
1577  SCIP* scip, /**< SCIP data structure */
1578  SCIP_PROP* prop, /**< vbounds propagator */
1579  SCIP_PROPDATA* propdata, /**< propagator data */
1580  SCIP_VAR* var, /**< variable whose lower bound should be tightened */
1581  SCIP_Real newlb, /**< new lower bound for the variable */
1582  SCIP_Bool global, /**< is the bound globally valid? */
1583  SCIP_VAR* vbdvar, /**< variable which is the reason for the lower bound change */
1584  SCIP_BOUNDTYPE boundtype, /**< bound which is the reason for the lower bound change */
1585  SCIP_Bool force, /**< should domain changes for continuous variables be forced */
1586  SCIP_Real coef, /**< coefficient in vbound constraint causing the propagation;
1587  * or 0.0 if propagation is caused by clique or implication */
1588  SCIP_Real constant, /**< constant in vbound constraint causing the propagation;
1589  * or 0.0 if propagation is caused by clique or implication */
1590  SCIP_Bool canwide, /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1591  int* nchgbds, /**< pointer to increase, if a bound was changed */
1592  SCIP_RESULT* result /**< pointer to store the result of the propagation */
1593  )
1594 {
1595  INFERINFO inferinfo;
1596  SCIP_Real lb;
1597  SCIP_Bool tightened;
1598  SCIP_Bool infeasible;
1599
1600  assert(scip != NULL);
1601  assert(prop != NULL);
1602  assert(propdata != NULL);
1603  assert(var != NULL);
1604  assert(nchgbds != NULL);
1605  assert(result != NULL);
1606
1607  lb = SCIPvarGetLbLocal(var);
1608
1609  /* check that the new upper bound is better */
1610  if( (SCIPvarIsIntegral(var) && newlb - lb > 0.5) || (force && SCIPisGT(scip, newlb, lb)) )
1611  force = TRUE;
1612  else
1613  force = FALSE;
1614
1615  /* try to tighten the lower bound */
1616  if( global )
1617  {
1618  SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, newlb, force, &infeasible, &tightened) );
1619  }
1620  else
1621  {
1622  inferinfo = getInferInfo(boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, vbdvar) : varGetUbIndex(propdata, vbdvar), boundtype);
1623
1624  SCIP_CALL( SCIPinferVarLbProp(scip, var, newlb, prop, inferInfoToInt(inferinfo), force, &infeasible, &tightened) );
1625  }
1626
1627  if( infeasible )
1628  {
1629  /* the infeasible results comes from the fact that the new lower bound lies above the current upper bound */
1630  assert(SCIPisGT(scip, newlb, SCIPvarGetUbLocal(var)));
1631  assert(!global || SCIPisGT(scip, newlb, SCIPvarGetUbGlobal(var)));
1632
1633  SCIPdebugMsg(scip, "tightening%s lower bound of variable <%s> to %g due the %s bound of variable <%s> led to infeasibility\n",
1634  (global ? " global" : ""), SCIPvarGetName(var), newlb, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1635
1636  if( global )
1637  {
1638  /* cutoff the root node */
1639  SCIP_CALL( SCIPcutoffNode(scip, SCIPgetRootNode(scip)) );
1640  }
1641  else
1642  {
1643  /* analyzes a infeasibility via conflict analysis */
1644  SCIP_CALL( analyzeConflictLowerbound(scip, propdata, var, newlb, vbdvar, boundtype, coef, constant, canwide) );
1645  }
1646  *result = SCIP_CUTOFF;
1647  }
1648  else if( tightened )
1649  {
1650  SCIPdebugMsg(scip, "tightened%s lower bound of variable <%s> to %g due the %s bound of variable <%s>\n",
1651  (global ? " global" : ""), SCIPvarGetName(var), newlb, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1652  (*nchgbds)++;
1653  }
1654
1655  return SCIP_OKAY;
1656 }
1657
1658 /* tries to tighten the (global) upper bound of the given variable to the given new bound */
1659 static
1661  SCIP* scip, /**< SCIP data structure */
1662  SCIP_PROP* prop, /**< vbounds propagator */
1663  SCIP_PROPDATA* propdata, /**< propagator data */
1664  SCIP_VAR* var, /**< variable whose upper bound should be tightened */
1665  SCIP_Real newub, /**< new upper bound of the variable */
1666  SCIP_Bool global, /**< is the bound globally valid? */
1667  SCIP_VAR* vbdvar, /**< variable which is the reason for the upper bound change */
1668  SCIP_BOUNDTYPE boundtype, /**< bound which is the reason for the upper bound change */
1669  SCIP_Bool force, /**< should domain changes for continuous variables be forced */
1670  SCIP_Real coef, /**< coefficient in vbound constraint causing the propagation;
1671  * or 0.0 if propagation is caused by clique or implication */
1672  SCIP_Real constant, /**< constant in vbound constraint causing the propagation;
1673  * or 0.0 if propagation is caused by clique or implication */
1674  SCIP_Bool canwide, /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1675  int* nchgbds, /**< pointer to increase, if a bound was changed */
1676  SCIP_RESULT* result /**< pointer to store the result of the propagation */
1677  )
1678 {
1679  INFERINFO inferinfo;
1680  SCIP_Real ub;
1681  SCIP_Bool tightened;
1682  SCIP_Bool infeasible;
1683
1684  assert(scip != NULL);
1685  assert(prop != NULL);
1686  assert(propdata != NULL);
1687  assert(var != NULL);
1688  assert(nchgbds != NULL);
1689  assert(result != NULL);
1690
1691  ub = SCIPvarGetUbLocal(var);
1692
1693  /* check that the new upper bound is better */
1694  if( (SCIPvarIsIntegral(var) && ub - newub > 0.5) || (force && SCIPisLT(scip, newub, ub)) )
1695  force = TRUE;
1696  else
1697  force = FALSE;
1698
1699  /* try to tighten the upper bound */
1700  if( global )
1701  {
1702  SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, newub, force, &infeasible, &tightened) );
1703  }
1704  else
1705  {
1706  inferinfo = getInferInfo(boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, vbdvar) : varGetUbIndex(propdata, vbdvar), boundtype);
1707
1708  SCIP_CALL( SCIPinferVarUbProp(scip, var, newub, prop, inferInfoToInt(inferinfo), force, &infeasible, &tightened) );
1709  }
1710
1711  if( infeasible )
1712  {
1713  /* the infeasible results comes from the fact that the new upper bound lies below the current lower bound */
1714  assert(SCIPisLT(scip, newub, SCIPvarGetLbLocal(var)));
1715  assert(!global || SCIPisLT(scip, newub, SCIPvarGetLbGlobal(var)));
1716
1717  SCIPdebugMsg(scip, "tightening%s upper bound of variable <%s> to %g due the %s bound of variable <%s> led to infeasibility\n",
1718  (global ? " global" : ""), SCIPvarGetName(var), newub, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1719
1720  if( global )
1721  {
1722  /* cutoff the root node */
1723  SCIP_CALL( SCIPcutoffNode(scip, SCIPgetRootNode(scip)) );
1724  }
1725  else
1726  {
1727  /* analyzes a infeasibility via conflict analysis */
1728  SCIP_CALL( analyzeConflictUpperbound(scip, propdata, var, newub, vbdvar, boundtype, coef, constant, canwide) );
1729  }
1730  *result = SCIP_CUTOFF;
1731  }
1732  else if( tightened )
1733  {
1734  SCIPdebugMsg(scip, "tightened%s upper bound of variable <%s> to %g due the %s bound of variable <%s>\n",
1735  (global ? " global" : ""), SCIPvarGetName(var), newub, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1736  (*nchgbds)++;
1737  }
1738
1739  return SCIP_OKAY;
1740 }
1741
1742 /** performs propagation of variables lower and upper bounds, implications, and cliques */
1743 static
1745  SCIP* scip, /**< SCIP data structure */
1746  SCIP_PROP* prop, /**< vbounds propagator */
1747  SCIP_Bool force, /**< should domain changes for continuous variables be forced */
1748  SCIP_RESULT* result /**< pointer to store the result of the propagation */
1749  )
1750 {
1751  SCIP_PROPDATA* propdata;
1752  SCIP_VAR** vars;
1753  SCIP_VAR* startvar;
1754  SCIP_BOUNDTYPE starttype;
1755  SCIP_Real startbound;
1756  SCIP_Real globalbound;
1757  int startpos;
1758  int topopos;
1759  int v;
1760  int n;
1761  int nchgbds;
1762  int nbounds;
1763  SCIP_Bool lower;
1764  SCIP_Bool global;
1765
1766  assert(scip != NULL);
1767  assert(prop != NULL);
1768  assert(result != NULL);
1769
1770  (*result) = SCIP_DIDNOTRUN;
1771
1772  /* we do not run the propagator in presolving, because we want to avoid doing the expensive creation of the graph twice */
1773  if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING )
1774  return SCIP_OKAY;
1775
1776  propdata = SCIPpropGetData(prop);
1777  assert(propdata != NULL);
1778
1779  /* initialize propagator data needed for propagation, if not done yet */
1780  if( !propdata->initialized )
1781  {
1782  SCIP_Bool infeasible;
1783
1784  SCIP_CALL( initData(scip, prop, &infeasible) );
1785
1786  if( infeasible )
1787  {
1788  *result = SCIP_CUTOFF;
1789  return SCIP_OKAY;
1790  }
1791  }
1792  assert(propdata->nbounds == 0 || propdata->propqueue != NULL);
1793
1794  vars = propdata->vars;
1795  nbounds = propdata->nbounds;
1796
1797  if( nbounds == 0 )
1798  return SCIP_OKAY;
1799
1800  /* propagate all variables if we are in repropagation */
1801  if( SCIPinRepropagation(scip) )
1802  {
1803  SCIP_VAR* var;
1804  int idx;
1805
1806  for( v = nbounds - 1; v >= 0; --v )
1807  {
1808  idx = propdata->topoorder[v];
1809  if( idx != -1 && !propdata->inqueue[v] )
1810  {
1811  var = vars[getVarIndex(idx)];
1812  lower = isIndexLowerbound(idx);
1813  if( !SCIPvarIsBinary(var) || (lower && SCIPvarGetLbLocal(var) > 0.5)
1814  || (!lower && SCIPvarGetUbLocal(var) < 0.5) )
1815  {
1816  SCIP_CALL( SCIPpqueueInsert(propdata->propqueue, (void*)(size_t)(v + 1)) ); /*lint !e571 !e776*/
1817  propdata->inqueue[v] = TRUE;
1818  }
1819  }
1820  }
1821  }
1822
1823  /* return if no bound changes are in the priority queue (no changed bounds to handle since last propagation) */
1824  if( SCIPpqueueNElems(propdata->propqueue) == 0 )
1825  {
1826  (*result) = SCIP_DIDNOTFIND;
1827  return SCIP_OKAY;
1828  }
1829
1830  nchgbds = 0;
1831
1832  SCIPdebugMsg(scip, "varbound propagator: %d elements in the propagation queue\n", SCIPpqueueNElems(propdata->propqueue));
1833
1834  /* get variable bound of highest priority from priority queue and try to deduce bound changes for other variables;
1835  * the priority queue is ordered w.r.t the topological sort of the varbound graph
1836  */
1837  while( SCIPpqueueNElems(propdata->propqueue) > 0 )
1838  {
1839  topopos = ((int)(size_t)SCIPpqueueRemove(propdata->propqueue)) - 1;
1840  assert(propdata->inqueue[topopos]);
1841  startpos = propdata->topoorder[topopos];
1842  assert(startpos >= 0);
1843  propdata->inqueue[topopos] = FALSE;
1844
1845  startvar = vars[getVarIndex(startpos)];
1846  starttype = getBoundtype(startpos);
1847  lower = (starttype == SCIP_BOUNDTYPE_LOWER);
1848  startbound = ( lower ? SCIPvarGetLbLocal(startvar) : SCIPvarGetUbLocal(startvar) );
1849  globalbound = ( lower ? SCIPvarGetLbGlobal(startvar) : SCIPvarGetUbGlobal(startvar));
1850  global = SCIPisEQ(scip, startbound, globalbound);
1851
1852  SCIPdebugMsg(scip, "propagate new %s bound of %g of variable <%s>:\n",
1853  getBoundtypeString(starttype), startbound, SCIPvarGetName(startvar));
1854
1855  /* there should be neither implications nor cliques for non-binary variables */
1856  assert(SCIPvarIsBinary(startvar) || SCIPvarGetNImpls(startvar, lower) == 0);
1857  assert(SCIPvarIsBinary(startvar) || SCIPvarGetNCliques(startvar, lower) == 0);
1858
1859  if( SCIPvarIsBinary(startvar) )
1860  {
1861  /* we only propagate binary variables if the lower bound changed to 1.0 or the upper bound changed to 0.0 */
1862  if( lower != (startbound > 0.5) )
1863  continue;
1864
1865  /* propagate implications */
1866  if( propdata->useimplics )
1867  {
1868  int nimplvars;
1869
1870  /* if the lower bound of the startvar was changed, it was fixed to 1.0, otherwise it was fixed to 0.0;
1871  * get all implications for this varfixing
1872  */
1873  nimplvars = SCIPvarGetNImpls(startvar, lower);
1874
1875  /* if there are implications for the varfixing, propagate them */
1876  if( nimplvars > 0 )
1877  {
1878  SCIP_VAR** implvars;
1879  SCIP_BOUNDTYPE* impltypes;
1880  SCIP_Real* implbounds;
1881  int* implids;
1882
1883  implvars = SCIPvarGetImplVars(startvar, lower);
1884  impltypes = SCIPvarGetImplTypes(startvar, lower);
1885  implbounds = SCIPvarGetImplBounds(startvar, lower);
1886  implids = SCIPvarGetImplIds(startvar, lower);
1887
1888  for( n = 0; n < nimplvars; ++n )
1889  {
1890  /* implication is just a shortcut, so we do not propagate it now,
1891  * because we will propagate the longer way, anyway
1892  */
1893  if( implids[n] < 0 )
1894  continue;
1895
1896  /* it might happen that implications point to inactive variables (normally, those are removed when a
1897  * variable becomes inactive, but in some cases, it cannot be done), we have to ignore these variables
1898  */
1899  if( !SCIPvarIsActive(implvars[n]) )
1900  continue;
1901
1902  if( impltypes[n] == SCIP_BOUNDTYPE_LOWER )
1903  {
1904  SCIP_CALL( tightenVarLb(scip, prop, propdata, implvars[n], implbounds[n], global, startvar,
1905  starttype, force, 0.0, 0.0, FALSE, &nchgbds, result) );
1906  }
1907  else
1908  {
1909  SCIP_CALL( tightenVarUb(scip, prop, propdata, implvars[n], implbounds[n], global, startvar,
1910  starttype, force, 0.0, 0.0, FALSE, &nchgbds, result) );
1911  }
1912
1913  if( *result == SCIP_CUTOFF )
1914  return SCIP_OKAY;
1915  }
1916  }
1917  }
1918
1919  /* propagate cliques */
1920  if( propdata->usecliques )
1921  {
1922  int ncliques;
1923
1924  /* if the lower bound of the startvar was changed, it was fixed to 1.0, otherwise it was fixed to 0.0;
1925  * get all cliques for this varfixing
1926  */
1927  ncliques = SCIPvarGetNCliques(startvar, lower);
1928
1929  /* if there are cliques for the varfixing, propagate them */
1930  if( ncliques > 0 )
1931  {
1932  SCIP_CLIQUE** cliques;
1933  int j;
1934
1935  cliques = SCIPvarGetCliques(startvar, lower);
1936
1937  for( j = 0; j < ncliques; ++j )
1938  {
1939  SCIP_VAR** cliquevars;
1940  SCIP_Bool* cliquevals;
1941  int ncliquevars;
1942
1943  cliquevars = SCIPcliqueGetVars(cliques[j]);
1944  cliquevals = SCIPcliqueGetValues(cliques[j]);
1945  ncliquevars = SCIPcliqueGetNVars(cliques[j]);
1946
1947  /* fix all variables except for the startvar to the value which is not in the clique */
1948  for( n = 0; n < ncliquevars; ++n )
1949  {
1950  if( cliquevars[n] == startvar )
1951  continue;
1952
1953  /* try to tighten the bound */
1954  if( cliquevals[n] )
1955  {
1956  /* unnegated variable is in clique, so it has to be fixed to 0.0 */
1957  SCIP_CALL( tightenVarUb(scip, prop, propdata, cliquevars[n], 0.0, global, startvar, starttype,
1958  force, 0.0, 0.0, FALSE, &nchgbds, result) );
1959  }
1960  else
1961  {
1962  /* negated variable is in clique, so it has to be fixed to 1.0 */
1963  SCIP_CALL( tightenVarLb(scip, prop, propdata, cliquevars[n], 1.0, global, startvar, starttype,
1964  force, 0.0, 0.0, FALSE, &nchgbds, result) );
1965  }
1966  if( *result == SCIP_CUTOFF )
1967  return SCIP_OKAY;
1968  }
1969  }
1970  }
1971  }
1972  }
1973
1974  /* propagate vbounds */
1975  if( propdata->usevbounds )
1976  {
1977  SCIP_VAR* boundedvar;
1978  SCIP_Real newbound;
1979  SCIP_Real coef;
1980  SCIP_Real constant;
1981
1982  /* iterate over all vbounds for the given bound */
1983  for( n = 0; n < propdata->nvbounds[startpos]; ++n )
1984  {
1985  boundedvar = vars[getVarIndex(propdata->vboundboundedidx[startpos][n])];
1986  coef = propdata->vboundcoefs[startpos][n];
1987  constant = propdata->vboundconstants[startpos][n];
1988
1989  /* compute new bound */
1990  newbound = startbound * coef + constant;
1991
1992  /* try to tighten the bound */
1993  if( isIndexLowerbound(propdata->vboundboundedidx[startpos][n]) )
1994  {
1995  SCIP_CALL( tightenVarLb(scip, prop, propdata, boundedvar, newbound, global, startvar, starttype, force,
1996  coef, constant, TRUE, &nchgbds, result) );
1997  }
1998  else
1999  {
2000  SCIP_CALL( tightenVarUb(scip, prop, propdata, boundedvar, newbound, global, startvar, starttype, force,
2001  coef, constant, TRUE, &nchgbds, result) );
2002  }
2003
2004  if( *result == SCIP_CUTOFF )
2005  return SCIP_OKAY;
2006  }
2007  }
2008  }
2009
2010  SCIPdebugMsg(scip, "tightened %d variable bounds\n", nchgbds);
2011
2012  /* set the result depending on whether bound changes were found or not */
2013  if( nchgbds > 0 )
2014  (*result) = SCIP_REDUCEDDOM;
2015  else
2016  (*result) = SCIP_DIDNOTFIND;
2017
2018  return SCIP_OKAY;
2019 }
2020
2021 /**@name Callback methods of propagator
2022  *
2023  * @{
2024  */
2025
2026 /** copy method for propagator plugins (called when SCIP copies plugins) */
2027 static
2028 SCIP_DECL_PROPCOPY(propCopyVbounds)
2029 { /*lint --e{715}*/
2030  assert(scip != NULL);
2031  assert(prop != NULL);
2032  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2033
2034  /* call inclusion method of propagator */
2036
2037  return SCIP_OKAY;
2038 }
2039
2040 /** destructor of propagator to free user data (called when SCIP is exiting) */
2041 static
2042 SCIP_DECL_PROPFREE(propFreeVbounds)
2043 { /*lint --e{715}*/
2044  SCIP_PROPDATA* propdata;
2045
2046  /* free propagator data */
2047  propdata = SCIPpropGetData(prop);
2048
2049  SCIPfreeBlockMemory(scip, &propdata);
2050  SCIPpropSetData(prop, NULL);
2051
2052  return SCIP_OKAY;
2053 }
2054
2055 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
2056 static
2057 SCIP_DECL_PROPEXITSOL(propExitsolVbounds)
2058 { /*lint --e{715}*/
2059  SCIP_PROPDATA* propdata;
2060  int v;
2061
2062  propdata = SCIPpropGetData(prop);
2063  assert(propdata != NULL);
2064
2065  /* free data stored for propagation */
2066  if( propdata->initialized )
2067  {
2068  /* drop all variable events */
2069  SCIP_CALL( dropEvents(scip, propdata) );
2070
2071  /* release all variables */
2072  for( v = 0; v < propdata->nbounds; ++v )
2073  {
2074  /* free vbound data */
2075  if( propdata->vboundsize[v] > 0 )
2076  {
2077  SCIPfreeMemoryArray(scip, &propdata->vboundboundedidx[v]);
2078  SCIPfreeMemoryArray(scip, &propdata->vboundcoefs[v]);
2079  SCIPfreeMemoryArray(scip, &propdata->vboundconstants[v]);
2080  }
2081  }
2082
2083  /* free priority queue */
2084  SCIPpqueueFree(&propdata->propqueue);
2085
2086  /* free arrays */
2087  SCIPfreeBlockMemoryArray(scip, &propdata->vboundsize, propdata->nbounds);
2088  SCIPfreeBlockMemoryArray(scip, &propdata->nvbounds, propdata->nbounds);
2089  SCIPfreeBlockMemoryArray(scip, &propdata->vboundconstants, propdata->nbounds);
2090  SCIPfreeBlockMemoryArray(scip, &propdata->vboundcoefs, propdata->nbounds);
2091  SCIPfreeBlockMemoryArray(scip, &propdata->vboundboundedidx, propdata->nbounds);
2092  SCIPfreeBlockMemoryArray(scip, &propdata->inqueue, propdata->nbounds);
2093  SCIPfreeBlockMemoryArray(scip, &propdata->topoorder, propdata->nbounds);
2094
2095  /* free variable array and hashmap */
2096  SCIPhashmapFree(&propdata->varhashmap);
2097  SCIPfreeBlockMemoryArray(scip, &propdata->vars, propdata->nbounds / 2);
2098  }
2099
2100  /* reset propagation data */
2101  resetPropdata(propdata);
2102
2103  return SCIP_OKAY;
2104 }
2105
2106 /** execution method of propagator */
2107 static
2108 SCIP_DECL_PROPEXEC(propExecVbounds)
2109 { /*lint --e{715}*/
2110
2111  *result = SCIP_DIDNOTRUN;
2112
2113  /* perform variable lower and upper bound propagation */
2114  SCIP_CALL( propagateVbounds(scip, prop, FALSE, result) );
2115
2116  assert((*result) == SCIP_CUTOFF || (*result) == SCIP_DIDNOTRUN
2117  || (*result) == SCIP_DIDNOTFIND || (*result) == SCIP_REDUCEDDOM);
2118
2119  return SCIP_OKAY;
2120 }
2121
2122 /** propagation conflict resolving method of propagator */
2123 static
2124 SCIP_DECL_PROPRESPROP(propRespropVbounds)
2125 { /*lint --e{715}*/
2126  SCIP_PROPDATA* propdata;
2127  SCIP_VAR** vars;
2128  SCIP_VAR* startvar;
2129  SCIP_BOUNDTYPE starttype;
2130  int pos;
2131
2132  propdata = SCIPpropGetData(prop);
2133  assert(propdata != NULL);
2134
2135  starttype = inferInfoGetBoundtype(intToInferInfo(inferinfo));
2136  pos = inferInfoGetPos(intToInferInfo(inferinfo));
2137  assert(pos >= 0);
2138  assert(pos < propdata->nbounds);
2139
2140  vars = propdata->vars;
2141  assert(vars != NULL);
2142  startvar = vars[getVarIndex(pos)];
2143  assert(startvar != NULL);
2144  assert(startvar != infervar);
2145
2146  SCIPdebugMsg(scip, "explain %s bound change of variable <%s>\n",
2147  getBoundtypeString(boundtype), SCIPvarGetName(infervar));
2148
2149  if( !SCIPvarIsBinary(startvar) && propdata->usebdwidening )
2150  {
2151  int* vboundboundedidx;
2152  SCIP_Real constant;
2153  SCIP_Real coef;
2154  int inferidx;
2155  int nvbounds;
2156  int b;
2157
2158  nvbounds = propdata->nvbounds[pos];
2159  vboundboundedidx = propdata->vboundboundedidx[pos];
2160
2161  inferidx = boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, infervar) : varGetUbIndex(propdata, infervar);
2162  assert(inferidx >= 0);
2163
2164  for( b = 0; b < nvbounds; ++b )
2165  {
2166  if( vboundboundedidx[b] == inferidx )
2167  break;
2168  }
2169  assert(b < nvbounds);
2170
2171  coef = propdata->vboundcoefs[pos][b];
2172  constant = propdata->vboundconstants[pos][b];
2173  assert(!SCIPisZero(scip, coef));
2174
2175  /* compute the relaxed bound which is sufficient to propagate the inference bound of given variable */
2176  if( boundtype == SCIP_BOUNDTYPE_LOWER )
2177  relaxedbd = computeRelaxedLowerbound(scip, infervar, relaxedbd, coef, constant);
2178  else
2179  relaxedbd = computeRelaxedUpperbound(scip, infervar, relaxedbd, coef, constant);
2180
2181  /* try to relax variable bound variable */
2182  SCIP_CALL( relaxVbdvar(scip, startvar, starttype, bdchgidx, relaxedbd) );
2183  }
2184  else
2185  {
2186  SCIP_CALL( resolvePropagation(scip, propdata, startvar, starttype, bdchgidx) );
2187  }
2188
2189  (*result) = SCIP_SUCCESS;
2190
2191  return SCIP_OKAY;
2192 }
2193
2194 /**@} */
2195
2196 /**@name Callback methods of event handler
2197  *
2198  * @{
2199  */
2200
2201 /** execution method of bound change event handler */
2202 static
2203 SCIP_DECL_EVENTEXEC(eventExecVbound)
2204 { /*lint --e{715}*/
2205  SCIP_PROPDATA* propdata;
2206  int idx;
2207
2208  assert(eventhdlr != NULL);
2209
2210  propdata = (SCIP_PROPDATA*)SCIPeventhdlrGetData(eventhdlr);
2211  assert(propdata != NULL);
2212
2213  idx = (int) (size_t) eventdata;
2214  assert(idx >= 0);
2215
2216  SCIPdebugMsg(scip, "eventexec (type=%llu): try to add sort index %d: %s(%s) to priority queue\n", SCIPeventGetType(event),
2217  idx, indexGetBoundString(propdata->topoorder[idx]),
2218  SCIPvarGetName(propdata->vars[getVarIndex(propdata->topoorder[idx])]));
2219
2221  && SCIPeventGetNewbound(event) > 0.5 )
2222  return SCIP_OKAY;
2223
2225  && SCIPeventGetNewbound(event) < 0.5 )
2226  return SCIP_OKAY;
2227
2228  assert(getVarIndex(propdata->topoorder[idx]) < SCIPgetNVars(scip));
2229  assert(SCIPvarGetType(propdata->vars[getVarIndex(propdata->topoorder[idx])]) != SCIP_VARTYPE_BINARY
2230  || (isIndexLowerbound(propdata->topoorder[idx]) == (SCIPeventGetNewbound(event) > 0.5)));
2231
2232  /* add the bound change to the propagation queue, if it is not already contained */
2233  if( !propdata->inqueue[idx] )
2234  {
2235  SCIP_CALL( SCIPpqueueInsert(propdata->propqueue, (void*)(size_t)(idx + 1)) ); /*lint !e571 !e776*/
2236  propdata->inqueue[idx] = TRUE;
2237  }
2238  assert(SCIPpqueueNElems(propdata->propqueue) > 0);
2239
2240  return SCIP_OKAY;
2241 }
2242
2243 /**@} */
2244
2245 /**@name Interface methods
2246  *
2247  * @{
2248  */
2249
2250 /** creates the vbounds propagator and includes it in SCIP */
2252  SCIP* scip /**< SCIP data structure */
2253  )
2254 {
2255  SCIP_PROPDATA* propdata;
2256  SCIP_PROP* prop;
2257
2258  /* create vbounds propagator data */
2259  SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
2260
2261  /* reset propagation data */
2262  resetPropdata(propdata);
2263
2264  /* include propagator */
2266  propExecVbounds, propdata) );
2267  assert(prop != NULL);
2268
2269  /* set optional callbacks via setter functions */
2270  SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyVbounds) );
2271  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeVbounds) );
2272  SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolVbounds) );
2273  SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropVbounds) );
2274
2275  /* include event handler for bound change events */
2276  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &propdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
2277  eventExecVbound, (SCIP_EVENTHDLRDATA*)propdata) );
2278
2280  "propagating/" PROP_NAME "/usebdwidening", "should bound widening be used to initialize conflict analysis?",
2281  &propdata->usebdwidening, FALSE, DEFAULT_USEBDWIDENING, NULL, NULL) );
2283  "propagating/" PROP_NAME "/useimplics", "should implications be propagated?",
2284  &propdata->useimplics, TRUE, DEFAULT_USEIMPLICS, NULL, NULL) );
2286  "propagating/" PROP_NAME "/usecliques", "should cliques be propagated?",
2287  &propdata->usecliques, TRUE, DEFAULT_USECLIQUES, NULL, NULL) );
2289  "propagating/" PROP_NAME "/usevbounds", "should vbounds be propagated?",
2290  &propdata->usevbounds, TRUE, DEFAULT_USEVBOUNDS, NULL, NULL) );
2292  "propagating/" PROP_NAME "/dotoposort", "should the bounds be topologically sorted in advance?",
2293  &propdata->dotoposort, FALSE, DEFAULT_DOTOPOSORT, NULL, NULL) );
2295  "propagating/" PROP_NAME "/sortcliques", "should cliques be regarded for the topological sort?",
2296  &propdata->sortcliques, TRUE, DEFAULT_SORTCLIQUES, NULL, NULL) );
2298  "propagating/" PROP_NAME "/detectcycles", "should cycles in the variable bound graph be identified?",
2299  &propdata->detectcycles, FALSE, DEFAULT_DETECTCYCLES, NULL, NULL) );
2300
2301  return SCIP_OKAY;
2302 }
2303
2304 /** returns TRUE if the propagator has the status that all variable lower and upper bounds are propgated */
2306  SCIP* scip /**< SCIP data structure */
2307  )
2308 {
2309  SCIP_PROP* prop;
2310  SCIP_PROPDATA* propdata;
2311
2312  prop = SCIPfindProp(scip, PROP_NAME);
2313  assert(prop != NULL);
2314
2315  propdata = SCIPpropGetData(prop);
2316  assert(propdata != NULL);
2317
2318  return (SCIPpqueueNElems(propdata->propqueue) == 0);
2319 }
2320
2321 /** performs propagation of variables lower and upper bounds */
2323  SCIP* scip, /**< SCIP data structure */
2324  SCIP_Bool force, /**< should domain changes for continuous variables be forced */
2325  SCIP_RESULT* result /**< pointer to store result */
2326  )
2327 {
2328  SCIP_PROP* prop;
2329
2330  prop = SCIPfindProp(scip, PROP_NAME);
2331  assert(prop != NULL);
2332
2333  /* perform variable lower and upper bound propagation */
2334  SCIP_CALL( propagateVbounds(scip, prop, force, result) );
2335
2336  assert((*result) == SCIP_CUTOFF || (*result) == SCIP_DIDNOTRUN
2337  || (*result) == SCIP_DIDNOTFIND || (*result) == SCIP_REDUCEDDOM);
2338
2339  return SCIP_OKAY;
2340 }
2341
2342 /**@} */
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
static void resetPropdata(SCIP_PROPDATA *propdata)
Definition: prop_vbounds.c:283
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21909
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
int SCIPpqueueNElems(SCIP_PQUEUE *pqueue)
Definition: misc.c:1263
struct InferInfo INFERINFO
#define PROP_FREQ
Definition: prop_vbounds.c:84
static SCIP_RETCODE addVbound(SCIP *scip, SCIP_PROPDATA *propdata, int startidx, int endidx, SCIP_Real coef, SCIP_Real constant)
Definition: prop_vbounds.c:410
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip.c:40508
#define getVarIndex(idx)
Definition: prop_vbounds.c:127
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
Definition: var.c:17380
#define DEFAULT_USEBDWIDENING
Definition: prop_vbounds.c:104
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx)
SCIP_Real SCIPfeastol(SCIP *scip)
Definition: scip.c:45274
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
Definition: implics.c:3305
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21892
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22118
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip.c:19263
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:814
static SCIP_Real computeRelaxedLowerbound(SCIP *scip, SCIP_VAR *var, SCIP_Real inferlb, SCIP_Real coef, SCIP_Real constant)
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip.c:19123
static SCIP_RETCODE dropEvents(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_vbounds.c:360
#define DEFAULT_USECLIQUES
Definition: prop_vbounds.c:106
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)
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip.c:40275
int SCIPvarGetNVlbs(SCIP_VAR *var)
Definition: var.c:17358
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip.h:21927
SCIP_PROP * SCIPfindProp(SCIP *scip, const char *name)
Definition: scip.c:7788
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17166
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip.c:45601
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:45876
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17222
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17529
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.c:22806
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip.c:8526
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16732
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
Definition: type_event.h:138
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:46175
#define getLbIndex(idx)
Definition: prop_vbounds.c:125
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46138
#define FALSE
Definition: def.h:64
SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub)
Definition: scip.c:21580
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2765
#define DEFAULT_SORTCLIQUES
Definition: prop_vbounds.c:109
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip.c:40796
#define TRUE
Definition: def.h:63
SCIP_Bool SCIPvarHasImplic(SCIP_VAR *var, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype)
Definition: var.c:10456
SCIP_Real SCIPgetConflictVarUb(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:27036
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_Bool SCIPcliqueIsEquation(SCIP_CLIQUE *clique)
Definition: implics.c:3347
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip.c:26813
int SCIPvarGetNVubs(SCIP_VAR *var)
Definition: var.c:17400
#define SCIP_EVENTTYPE_GLBCHANGED
Definition: type_event.h:61
SCIP_RETCODE SCIPaddConflictRelaxedLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedlb)
Definition: scip.c:26780
static SCIP_DECL_PROPCOPY(propCopyVbounds)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition: scip.c:26717
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22234
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21907
void SCIPpqueueFree(SCIP_PQUEUE **pqueue)
Definition: misc.c:1160
static SCIP_BOUNDTYPE inferInfoGetBoundtype(INFERINFO inferinfo)
Definition: prop_vbounds.c:216
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
Definition: var.c:17370
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)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2903
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45751
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb)
Definition: scip.c:21548
#define isIndexLowerbound(idx)
Definition: prop_vbounds.c:129
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip.c:40472
static int inferInfoToInt(INFERINFO inferinfo)
Definition: prop_vbounds.c:207
#define SCIPdebugMsg
Definition: scip.h:451
#define VISITED
Definition: prop_vbounds.c:749
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17518
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip.c:26746
SCIP_RETCODE SCIPincludePropVbounds(SCIP *scip)
int * SCIPvarGetImplIds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17506
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)
#define DEFAULT_USEIMPLICS
Definition: prop_vbounds.c:105
const char * SCIPgetProbName(SCIP *scip)
Definition: scip.c:10724
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2997
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
Definition: scip.c:26695
static SCIP_Real computeRelaxedUpperbound(SCIP *scip, SCIP_VAR *var, SCIP_Real inferub, SCIP_Real coef, SCIP_Real constant)
variable upper and lower bound propagator
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17176
#define PROP_DESC
Definition: prop_vbounds.c:81
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip.h:21904
SCIP_Real SCIPeventGetNewbound(SCIP_EVENT *event)
Definition: event.c:1162
#define SCIPerrorMessage
Definition: pub_message.h:45
static SCIP_DECL_EVENTEXEC(eventExecVbound)
#define indexGetBoundString(idx)
Definition: prop_vbounds.c:132
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45764
SCIP_RETCODE SCIPexecPropVbounds(SCIP *scip, SCIP_Bool force, SCIP_RESULT *result)
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: scip.c:18929
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45519
#define INITMEMSIZE
Definition: prop_vbounds.c:406
SCIP_Real SCIPgetConflictVarLb(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:27012
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
Definition: var.c:17432
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:155
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2798
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:23135
#define NULL
Definition: lpi_spx1.cpp:137
static int varGetUbIndex(SCIP_PROPDATA *propdata, SCIP_VAR *var)
Definition: prop_vbounds.c:271
#define PROP_NAME
Definition: prop_vbounds.c:80
#define SCIP_CALL(x)
Definition: def.h:306
#define SCIP_EVENTTYPE_LBTIGHTENED
Definition: type_event.h:63
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
Definition: var.c:17390
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.c:22919
static INFERINFO intToInferInfo(int i)
Definition: prop_vbounds.c:194
#define DEFAULT_DOTOPOSORT
Definition: prop_vbounds.c:108
#define PROP_TIMING
Definition: prop_vbounds.c:82
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition: var.c:17422
static SCIP_DECL_PROPEXEC(propExecVbounds)
void * SCIPpqueueRemove(SCIP_PQUEUE *pqueue)
Definition: misc.c:1208
static SCIP_DECL_PROPEXITSOL(propExitsolVbounds)
static SCIP_RETCODE initData(SCIP *scip, SCIP_PROP *prop, SCIP_Bool *infeasible)
static int inferInfoGetPos(INFERINFO inferinfo)
Definition: prop_vbounds.c:227
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17476
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
Definition: event.c:982
#define SCIP_Bool
Definition: def.h:61
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:959
#define EVENTHDLR_NAME
Definition: prop_vbounds.c:94
#define getBoundtype(idx)
Definition: prop_vbounds.c:128
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17444
SCIP_RETCODE SCIPaddConflictRelaxedUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedub)
Definition: scip.c:26848
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
Definition: implics.c:3317
#define EVENTHDLR_DESC
Definition: prop_vbounds.c:95
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:753
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip.c:7610
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip.c:40321
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:469
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip.h:21874
#define SCIPreallocMemoryArray(scip, ptr, newnum)
Definition: scip.h:21864
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition: type_event.h:65
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17490
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip.c:7690
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:887
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11631
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:130
#define PROP_DELAY
Definition: prop_vbounds.c:85
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17461
static int varGetLbIndex(SCIP_PROPDATA *propdata, SCIP_VAR *var)
Definition: prop_vbounds.c:259
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip.c:7771
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45790
#define ACTIVE
Definition: prop_vbounds.c:750
static INFERINFO getInferInfo(int pos, SCIP_BOUNDTYPE boundtype)
Definition: prop_vbounds.c:236
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1181
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:301
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)))
Definition: misc.c:1135
#define PROP_PRIORITY
Definition: prop_vbounds.c:83
#define getOtherBoundIndex(idx)
Definition: prop_vbounds.c:133
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:46163
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11586
#define SCIP_Real
Definition: def.h:135
#define getBoundtypeString(type)
Definition: prop_vbounds.c:131
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:38
#define DEFAULT_USEVBOUNDS
Definition: prop_vbounds.c:107
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip.c:7626
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition: var.c:17412
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:735
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
Definition: prop.c:745
static SCIP_RETCODE propagateVbounds(SCIP *scip, SCIP_PROP *prop, SCIP_Bool force, SCIP_RESULT *result)
#define DEFAULT_DETECTCYCLES
Definition: prop_vbounds.c:110
static SCIP_DECL_SORTPTRCOMP(compVarboundIndices)
Definition: prop_vbounds.c:457
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16717
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:45864
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17232
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
Definition: implics.c:3295
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:23255
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:2846
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:85
static SCIP_DECL_PROPRESPROP(propRespropVbounds)
#define SCIP_EVENTTYPE_GUBCHANGED
Definition: type_event.h:62
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:288
#define SCIPABORT()
Definition: def.h:278
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16743
SCIP_Bool SCIPisPropagatedVbounds(SCIP *scip)
SCIP_RETCODE SCIPanalyzeConflict(SCIP *scip, int validdepth, SCIP_Bool *success)
Definition: scip.c:27066
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.c:4176
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16839
static SCIP_RETCODE topologicalSort(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool *infeasible)
uint64_t SCIP_EVENTTYPE
Definition: type_event.h:134
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.c:7573
#define getUbIndex(idx)
Definition: prop_vbounds.c:126
static SCIP_DECL_PROPFREE(propFreeVbounds)