Scippy

SCIP

Solving Constraint Integer Programs

prop_vbounds.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2014 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not 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 toghtening 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 
111 /**@} */
112 
113 /**@name Propagator defines
114  *
115  * @{
116  *
117  * The propagator works on indices representing a bound of a variable. This index will be called bound index in the
118  * following. For a given active variable with problem index i (note that active variables have problem indices
119  * between 0 and nactivevariable - 1), the bound index of its lower bound is 2*i, the bound index of its upper
120  * bound is 2*i + 1. The other way around, a given bound index i corresponds to the variable with problem index
121  * i/2 (rounded down), and to the lower bound, if i is even, to the upper bound if i is odd.
122  * The following macros can be used to convert bound index into variable problem index and boundtype and vice versa.
123  */
124 #define getLbIndex(idx) (2*(idx))
125 #define getUbIndex(idx) (2*(idx)+1)
126 #define getVarIndex(idx) ((idx)/2)
127 #define getBoundtype(idx) (((idx) % 2 == 0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER)
128 #define isIndexLowerbound(idx) ((idx) % 2 == 0)
129 #define getBoundString(lower) ((lower) ? "lb" : "ub")
130 #define getBoundtypeString(type) ((type) == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper")
131 #define indexGetBoundString(idx) (getBoundString(isIndexLowerbound(idx)))
132 
133 /**@} */
134 
135 /*
136  * Data structures
137  */
138 
139 /** propagator data */
140 struct SCIP_PropData
141 {
142  SCIP_EVENTHDLR* eventhdlr; /**< event handler for catching bound changes */
143  SCIP_VAR** vars; /**< array containing all variable which are considered within the propagator */
144  SCIP_HASHMAP* varhashmap; /**< hashmap mapping from variable to index in the vars array */
145  int* topoorder; /**< array mapping on the bounds of variables in topological order;
146  * or -1, if the bound that should be at that position has no outgoing
147  * implications, cliques, or vbounds;
148  * i.e., for i < j and topoorder[i] != -1 != topoorder[j], the variable
149  * and boundtype represented by index topoorder[i] are earlier in the
150  * topological order than those represented by index topoorder[j]
151  */
152  int** vboundboundedidx; /**< array storing for each bound index the bound indices of all bounds
153  * influenced by this bound through variable bounds */
154  SCIP_Real** vboundcoefs; /**< array storing for each bound index the coefficients in the variable
155  * bounds influencing the corresponding bound index stored in
156  * vboundboundedidx */
157  SCIP_Real** vboundconstants; /**< array storing for each bound index the constants in the variable
158  * bounds influencing the corresponding bound index stored in
159  * vboundboundedidx */
160  int* nvbounds; /**< array storing for each bound index the number of vbounds stored */
161  int* vboundsize; /**< array with sizes of vbound arrays for the nodes */
162  int nbounds; /**< number of bounds of variables regarded (two times number of active variables) */
163  SCIP_PQUEUE* propqueue; /**< priority queue to handle the bounds of variables that were changed and have to be propagated */
164  SCIP_Bool* inqueue; /**< boolean array to store whether a bound of a variable is already contained in propqueue */
165  SCIP_Bool initialized; /**< was the data for propagation already initialized? */
166  SCIP_Bool usebdwidening; /**< should bound widening be used to initialize conflict analysis? */
167  SCIP_Bool useimplics; /**< should implications be propagated? */
168  SCIP_Bool usecliques; /**< should cliques be propagated? */
169  SCIP_Bool usevbounds; /**< should variable bounds be propagated? */
170  SCIP_Bool dotoposort; /**< should the bounds be topologically sorted in advance? */
171  SCIP_Bool sortcliques; /**< should cliques be regarded for the topological sort? */
172 };
173 
174 /** inference information */
175 struct InferInfo
176 {
177  union
178  {
179  struct
180  {
181  unsigned int pos:31; /**< position of the variable which forced that propagation */
182  unsigned int boundtype:1; /**< bound type which was the reason (0: lower, 1: upper) */
183  } asbits;
184  int asint; /**< inference information as a single int value */
185  } val;
186 };
187 typedef struct InferInfo INFERINFO;
188 
189 /** converts an integer into an inference information */
190 static
191 INFERINFO intToInferInfo(
192  int i /**< integer to convert */
193  )
194 {
195  INFERINFO inferinfo;
196 
197  inferinfo.val.asint = i;
198 
199  return inferinfo;
200 }
201 
202 /** converts an inference information into an int */
203 static
204 int inferInfoToInt(
205  INFERINFO inferinfo /**< inference information to convert */
206  )
207 {
208  return inferinfo.val.asint;
209 }
210 
211 /** returns the propagation rule stored in the inference information */
212 static
213 SCIP_BOUNDTYPE inferInfoGetBoundtype(
214  INFERINFO inferinfo /**< inference information to convert */
215  )
216 {
217  assert((SCIP_BOUNDTYPE)inferinfo.val.asbits.boundtype == SCIP_BOUNDTYPE_LOWER
218  || (SCIP_BOUNDTYPE)inferinfo.val.asbits.boundtype == SCIP_BOUNDTYPE_UPPER);
219  return (SCIP_BOUNDTYPE)inferinfo.val.asbits.boundtype;
220 }
221 
222 /** returns the position stored in the inference information */
223 static
224 int inferInfoGetPos(
225  INFERINFO inferinfo /**< inference information to convert */
226  )
227 {
228  return (int) inferinfo.val.asbits.pos;
229 }
230 
231 /** constructs an inference information out of a position of a variable and a boundtype */
232 static
233 INFERINFO getInferInfo(
234  int pos, /**< position of the variable which forced that propagation */
235  SCIP_BOUNDTYPE boundtype /**< propagation rule that deduced the value */
236  )
237 {
238  INFERINFO inferinfo;
239 
240  assert(boundtype == SCIP_BOUNDTYPE_LOWER || boundtype == SCIP_BOUNDTYPE_UPPER);
241  assert((int)boundtype >= 0 && (int)boundtype <= 1); /*lint !e685 !e568q*/
242  assert(pos >= 0);
243 
244  inferinfo.val.asbits.pos = (unsigned int) pos; /*lint !e732*/
245  inferinfo.val.asbits.boundtype = (unsigned int) boundtype; /*lint !e641*/
246 
247  return inferinfo;
248 }
249 
250 /*
251  * Local methods
252  */
253 
254 /* returns the lower bound index of a variable */
255 static
256 int varGetLbIndex(
257  SCIP_PROPDATA* propdata, /**< propagator data */
258  SCIP_VAR* var /**< variable to get the index for */
259  )
260 {
261  assert(SCIPhashmapExists(propdata->varhashmap, var) == ((size_t)SCIPhashmapGetImage(propdata->varhashmap, var) > 0));
262 
263  return getLbIndex((int)(size_t)SCIPhashmapGetImage(propdata->varhashmap, var) - 1);
264 }
265 
266 /* returns the upper bound index of a variable */
267 static
268 int varGetUbIndex(
269  SCIP_PROPDATA* propdata, /**< propagator data */
270  SCIP_VAR* var /**< variable to get the index for */
271  )
272 {
273  assert(SCIPhashmapExists(propdata->varhashmap, var) == ((size_t)SCIPhashmapGetImage(propdata->varhashmap, var) > 0));
274 
275  return getUbIndex((int)(size_t)SCIPhashmapGetImage(propdata->varhashmap, var) - 1);
276 }
277 
278 /** reset propagation data */
279 static
280 void resetPropdata(
281  SCIP_PROPDATA* propdata /**< propagator data */
282  )
283 {
284  propdata->vars = NULL;
285  propdata->varhashmap = NULL;
286  propdata->topoorder = NULL;
287  propdata->vboundboundedidx = NULL;
288  propdata->vboundcoefs = NULL;
289  propdata->vboundconstants = NULL;
290  propdata->nvbounds = NULL;
291  propdata->vboundsize = NULL;
292  propdata->nbounds = 0;
293  propdata->initialized = FALSE;
294 }
295 
296 /** catches events for variables */
297 static
298 SCIP_RETCODE catchEvents(
299  SCIP* scip, /**< SCIP data structure */
300  SCIP_PROPDATA* propdata /**< propagator data */
301  )
302 {
303  SCIP_EVENTHDLR* eventhdlr;
304  SCIP_EVENTTYPE eventtype;
305  SCIP_VAR** vars;
306  SCIP_VAR* var;
307  SCIP_Bool lower;
308  int nbounds;
309  int v;
310  int idx;
311 
312  assert(scip != NULL);
313  assert(propdata != NULL);
314  assert(propdata->vars != NULL);
315  assert(propdata->topoorder != NULL);
316 
317  /* catch variable events according to computed eventtypes */
318  eventhdlr = propdata->eventhdlr;
319  assert(eventhdlr != NULL);
320 
321  vars = propdata->vars;
322  nbounds = propdata->nbounds;
323 
324  /* setup events */
325  for( v = 0; v < nbounds; ++v )
326  {
327  idx = propdata->topoorder[v];
328  assert(idx >= 0 && idx < nbounds);
329 
330  var = vars[getVarIndex(idx)];
331  lower = isIndexLowerbound(idx);
332 
333  /* if the bound does not influence another bound by implications, cliques, or vbounds,
334  * we do not create an event and do not catch changes of the bound;
335  * we mark this by setting the value in topoorder to -1
336  */
337  if( propdata->nvbounds[idx] == 0 && SCIPvarGetNImpls(var, lower) == 0 && SCIPvarGetNCliques(var, lower) == 0 )
338  {
339  propdata->topoorder[v] = -1;
340  continue;
341  }
342 
343  /* determine eventtype that we want to catch depending on boundtype of variable */
344  if( lower )
345  eventtype = SCIP_EVENTTYPE_LBTIGHTENED | SCIP_EVENTTYPE_GLBCHANGED;
346  else
347  eventtype = SCIP_EVENTTYPE_UBTIGHTENED | SCIP_EVENTTYPE_GUBCHANGED;
348 
349  SCIP_CALL( SCIPcatchVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*) (size_t) v, NULL) );
350  }
351 
352  return SCIP_OKAY;
353 }
354 
355 
356 /** drops events for variables */
357 static
358 SCIP_RETCODE dropEvents(
359  SCIP* scip, /**< SCIP data structure */
360  SCIP_PROPDATA* propdata /**< propagator data */
361  )
362 {
363  SCIP_EVENTHDLR* eventhdlr;
364  SCIP_EVENTTYPE eventtype;
365  SCIP_VAR** vars;
366  SCIP_VAR* var;
367  SCIP_Bool lower;
368  int nbounds;
369  int v;
370  int idx;
371 
372  assert(propdata != NULL);
373 
374  eventhdlr = propdata->eventhdlr;
375  assert(eventhdlr != NULL);
376 
377  vars = propdata->vars;
378  nbounds = propdata->nbounds;
379 
380  for( v = 0; v < nbounds; ++v )
381  {
382  idx = propdata->topoorder[v];
383 
384  if( idx == -1 )
385  continue;
386 
387  assert(idx >= 0 && idx < nbounds);
388 
389  var = vars[getVarIndex(idx)];
390  lower = isIndexLowerbound(idx);
391 
392  /* determine eventtype that we catch and now want to drop depending on boundtype of variable */
393  if( lower )
394  eventtype = SCIP_EVENTTYPE_LBTIGHTENED | SCIP_EVENTTYPE_GLBCHANGED;
395  else
396  eventtype = SCIP_EVENTTYPE_UBTIGHTENED | SCIP_EVENTTYPE_GUBCHANGED;
397 
398  SCIP_CALL( SCIPdropVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*) (size_t) v, -1) );
399  }
400 
401  return SCIP_OKAY;
402 }
403 
404 #define INITMEMSIZE 5
405 
406 /* adds a vbound to the propagator data to store it internally and allow forward propagation */
407 static
408 SCIP_RETCODE addVbound(
409  SCIP* scip, /**< SCIP data structure */
410  SCIP_PROPDATA* propdata, /**< propagator data */
411  int startidx, /**< index of bound of variable influencing the other variable */
412  int endidx, /**< index of bound of variable which is influenced */
413  SCIP_Real coef, /**< coefficient in the variable bound */
414  SCIP_Real constant /**< constant in the variable bound */
415  )
416 {
417  int nvbounds;
418 
419  assert(scip != NULL);
420  assert(propdata != NULL);
421 
422  if( propdata->vboundsize[startidx] == 0 )
423  {
424  /* allocate memory for storing vbounds */
425  propdata->vboundsize[startidx] = INITMEMSIZE;
426 
427  SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundboundedidx[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
428  SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundcoefs[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
429  SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundconstants[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
430  }
431  else if( propdata->nvbounds[startidx] >= propdata->vboundsize[startidx] )
432  {
433  /* reallocate memory for storing vbounds */
434  propdata->vboundsize[startidx] = SCIPcalcMemGrowSize(scip, propdata->nvbounds[startidx] + 1);
435  assert(propdata->nvbounds[startidx] < propdata->vboundsize[startidx]);
436 
437  SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundboundedidx[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
438  SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundcoefs[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
439  SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundconstants[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
440  }
441 
442  nvbounds = propdata->nvbounds[startidx];
443  propdata->vboundboundedidx[startidx][nvbounds] = endidx;
444  propdata->vboundcoefs[startidx][nvbounds] = coef;
445  propdata->vboundconstants[startidx][nvbounds] = constant;
446  (propdata->nvbounds[startidx])++;
447 
448  return SCIP_OKAY;
449 }
450 
451 
452 /** comparison method for two indices in the topoorder array, preferring higher indices because the order is reverse
453  * topological
454  */
455 static
456 SCIP_DECL_SORTPTRCOMP(compVarboundIndices)
457 {
458  int idx1 = (int)(size_t)elem1;
459  int idx2 = (int)(size_t)elem2;
460 
461  return idx2 - idx1;
462 }
463 
464 /** performs depth-first-search in the implicitly given directed graph from the given start index */
465 static
466 SCIP_RETCODE dfs(
467  SCIP* scip, /**< SCIP data structure */
468  SCIP_PROPDATA* propdata, /**< propagator data */
469  int startnode, /**< node to start the depth-first-search */
470  SCIP_Bool* visited, /**< array to store for each node, whether it was already visited */
471  int* dfsstack, /**< array of size number of nodes to store the stack;
472  * only needed for performance reasons */
473  int* stacknextedge, /**< array of size number of nodes to store the number of adjacent nodes
474  * already visited for each node on the stack; only needed for
475  * performance reasons */
476  int* dfsnodes, /**< array of nodes that can be reached starting at startnode, in reverse
477  * dfs order */
478  int* ndfsnodes /**< pointer to store number of nodes that can be reached starting at
479  * startnode */
480  )
481 {
482  SCIP_VAR** vars;
483  SCIP_VAR* startvar;
484  SCIP_Bool lower;
485  int stacksize;
486  int curridx;
487  int nimpls;
488  int idx;
489 
490  assert(startnode >= 0);
491  assert(startnode < propdata->nbounds);
492  assert(visited != NULL);
493  assert(visited[startnode] == FALSE);
494  assert(dfsstack != NULL);
495  assert(dfsnodes != NULL);
496  assert(ndfsnodes != NULL);
497 
498  vars = propdata->vars;
499 
500  /* put start node on the stack */
501  dfsstack[0] = startnode;
502  stacknextedge[0] = 0;
503  stacksize = 1;
504  idx = -1;
505 
506  /* we run until no more bounds indices are on the stack, i.e. all changed bounds were propagated */
507  while( stacksize > 0 )
508  {
509  /* get next node from stack */
510  curridx = dfsstack[stacksize - 1];
511 
512  /* mark current node as visited */
513  assert(visited[curridx] == (stacknextedge[stacksize - 1] != 0));
514  visited[curridx] = TRUE;
515 
516  startvar = vars[getVarIndex(curridx)];
517  lower = isIndexLowerbound(curridx);
518 
519  nimpls = 0;
520 
521  if( propdata->sortcliques && propdata->usecliques && stacknextedge[stacksize - 1] == 0 )
522  stacknextedge[stacksize - 1] = -1;
523 
524  /* stacknextedge is negative, if the last visited edge from the current node belongs to a clique;
525  * the index of the clique in the variable's clique list equals abs(stacknextedge) - 1
526  */
527  if( propdata->sortcliques && propdata->usecliques && stacknextedge[stacksize - 1] < 0 )
528  {
529  SCIP_CLIQUE** cliques;
530  int ncliques;
531  int j;
532  int i;
533  SCIP_Bool found;
534 
535  ncliques = SCIPvarGetNCliques(startvar, lower);
536  cliques = SCIPvarGetCliques(startvar, lower);
537  found = FALSE;
538 
539  assert(stacknextedge[stacksize - 1] == -1 || -stacknextedge[stacksize - 1] - 1 < ncliques);
540 
541  /* iterate over all not yet handled cliques and search for an unvisited node */
542  for( j = -stacknextedge[stacksize - 1] - 1; j < ncliques; ++j )
543  {
544  SCIP_VAR** cliquevars;
545  SCIP_Bool* cliquevals;
546  int ncliquevars;
547 
548  cliquevars = SCIPcliqueGetVars(cliques[j]);
549  cliquevals = SCIPcliqueGetValues(cliques[j]);
550  ncliquevars = SCIPcliqueGetNVars(cliques[j]);
551 
552  for( i = 0; i < ncliquevars; ++i )
553  {
554  if( cliquevars[i] == startvar )
555  continue;
556 
557  if( cliquevals[i] )
558  idx = varGetUbIndex(propdata, cliquevars[i]);
559  else
560  idx = varGetLbIndex(propdata, cliquevars[i]);
561 
562  /* break when the first unvisited node is reached */
563  if( idx >= 0 && !visited[idx] )
564  {
565  found = TRUE;
566  break;
567  }
568  }
569  if( found )
570  break;
571  }
572 
573  /* we stopped because we found an unhandled node and not because we reached the end of the list */
574  if( found )
575  {
576  assert(idx >= 0);
577  assert(!visited[idx]);
578  assert(j < ncliques);
579 
580  SCIPdebugMessage("clique: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
581  indexGetBoundString(idx), SCIPvarGetName(vars[getVarIndex(idx)]));
582 
583  /* put the adjacent node onto the stack */
584  dfsstack[stacksize] = idx;
585  stacknextedge[stacksize] = 0;
586  stacknextedge[stacksize - 1] = -j - 1;
587  stacksize++;
588  assert(stacksize <= propdata->nbounds);
589 
590  /* restart while loop, get next index from stack */
591  continue;
592  }
593  else
594  {
595  /* we did not find an edge to an unhandled node given by a clique */
596  stacknextedge[stacksize - 1] = 0;
597  }
598  }
599  assert(stacknextedge[stacksize - 1] >= 0);
600 
601  /* go over edges given by implications */
602  if( propdata->useimplics )
603  {
604  nimpls = SCIPvarGetNImpls(startvar, lower);
605 
606  if( stacknextedge[stacksize - 1] < nimpls )
607  {
608  SCIP_VAR** implvars;
609  SCIP_BOUNDTYPE* impltypes;
610  int* implids;
611  int i;
612 
613  implvars = SCIPvarGetImplVars(startvar, lower);
614  impltypes = SCIPvarGetImplTypes(startvar, lower);
615  implids = SCIPvarGetImplIds(startvar, lower);
616 
617  for( i = stacknextedge[stacksize - 1]; i < nimpls; ++i )
618  {
619  /* it might happen that implications point to inactive variables (normally, those are removed when a
620  * variable becomes inactive, but in some cases, it cannot be done), we have to ignore these variables
621  */
622  if( !SCIPvarIsActive(implvars[i]) )
623  continue;
624 
625  /* implication is just a shortcut, so we dont regard it now, because will later go the long way, anyway;
626  * however, if we do regard cliques for the topological order, we use them to get a better order
627  */
628  if( propdata->usecliques && !propdata->sortcliques && implids[i] < 0 )
629  continue;
630 
631  idx = (impltypes[i] == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, implvars[i]) : varGetUbIndex(propdata, implvars[i]));
632 
633  /* break when the first unvisited node is reached */
634  if( idx >= 0 && !visited[idx] )
635  break;
636  }
637 
638  /* we stopped because we found an unhandled node and not because we reached the end of the list */
639  if( i < nimpls )
640  {
641  assert(!visited[idx]);
642 
643  SCIPdebugMessage("impl: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
644  indexGetBoundString(idx), SCIPvarGetName(vars[getVarIndex(idx)]));
645 
646 
647  /* put the adjacent node onto the stack */
648  dfsstack[stacksize] = idx;
649  stacknextedge[stacksize] = 0;
650  stacknextedge[stacksize - 1] = i + 1;
651  stacksize++;
652  assert(stacksize <= propdata->nbounds);
653 
654  /* restart while loop, get next index from stack */
655  continue;
656  }
657  else
658  {
659  stacknextedge[stacksize - 1] = nimpls;
660  }
661  }
662  }
663  assert(stacknextedge[stacksize - 1] >= nimpls);
664 
665  /* go over edges corresponding by varbounds */
666  if( propdata->usevbounds )
667  {
668  int nvbounds;
669  int* vboundidx;
670  int i;
671 
672  nvbounds = propdata->nvbounds[curridx];
673  vboundidx = propdata->vboundboundedidx[curridx];
674 
675  /* iterate over all vbounds for the given bound */
676  for( i = 0; i < nvbounds; ++i )
677  {
678  idx = vboundidx[i];
679  assert(idx >= 0);
680 
681  /* break when the first unvisited node is reached */
682  if( !visited[idx] )
683  break;
684  }
685 
686  /* we stopped because we found an unhandled node and not because we reached the end of the list */
687  if( i < nvbounds )
688  {
689  assert(!visited[idx]);
690 
691  SCIPdebugMessage("vbound: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
692  indexGetBoundString(idx), SCIPvarGetName(vars[getVarIndex(idx)]));
693 
694  /* put the adjacent node onto the stack */
695  dfsstack[stacksize] = idx;
696  stacknextedge[stacksize] = 0;
697  stacknextedge[stacksize - 1] = nimpls + i + 1;
698  stacksize++;
699  assert(stacksize <= propdata->nbounds);
700 
701  /* restart while loop, get next index from stack */
702  continue;
703  }
704 
705  }
706 
707  /* the current node was completely handled, remove it from stack */
708  stacksize--;
709 
710  SCIPdebugMessage("topoorder[%d] = %s(%s)\n", *ndfsnodes, getBoundString(lower), SCIPvarGetName(startvar));
711 
712  /* store node in the sorted nodes array */
713  dfsnodes[(*ndfsnodes)] = curridx;
714  (*ndfsnodes)++;
715  }
716 
717  return SCIP_OKAY;
718 }
719 
720 
721 /** sort the bounds of variables topologically */
722 static
723 SCIP_RETCODE topologicalSort(
724  SCIP* scip, /**< SCIP data structure */
725  SCIP_PROPDATA* propdata /**< propagator data */
726  )
727 {
728  int* dfsstack;
729  int* stacknextedge;
730  int nsortednodes;
731  int nbounds;
732  int i;
733 
734  assert(scip != NULL);
735  assert(propdata != NULL);
736 
737  nbounds = propdata->nbounds;
738 
739  SCIP_CALL( SCIPallocBufferArray(scip, &dfsstack, nbounds) );
740  SCIP_CALL( SCIPallocBufferArray(scip, &stacknextedge, nbounds) );
741 
742  nsortednodes = 0;
743 
744 #ifndef NDEBUG
745  for( i = 0; i < nbounds; ++i )
746  assert(!propdata->inqueue[i]);
747 #endif
748 
749  /* while there are unvisited nodes, run dfs starting from one of these nodes; the dfs orders are stored in the
750  * topoorder array, later dfs calls are just appended after the stacks of previous dfs calls, which gives us a
751  * reverse topological order
752  */
753  for( i = 0; i < nbounds; ++i )
754  {
755  if( !propdata->inqueue[i] )
756  {
757  SCIP_CALL( dfs(scip, propdata, i, propdata->inqueue, dfsstack, stacknextedge, propdata->topoorder, &nsortednodes) );
758  }
759  }
760  assert(nsortednodes == nbounds);
761 
762  BMSclearMemoryArray(propdata->inqueue, nbounds);
763 
764  SCIPfreeBufferArray(scip, &stacknextedge);
765  SCIPfreeBufferArray(scip, &dfsstack);
766 
767  return SCIP_OKAY;
768 }
769 
770 /** initializes the internal data for the variable bounds propagator */
771 static
772 SCIP_RETCODE initData(
773  SCIP* scip, /**< SCIP data structure */
774  SCIP_PROP* prop /**< vbounds propagator */
775  )
776 {
777  SCIP_PROPDATA* propdata;
778  SCIP_VAR** vars;
779  int nvars;
780  int nbounds;
781  int startidx;
782  int v;
783  int n;
784 
785  assert(scip != NULL);
786  assert(prop != NULL);
787 
788  /* get propagator data */
789  propdata = SCIPpropGetData(prop);
790  assert(propdata != NULL);
791  assert(!propdata->initialized);
792 
793  SCIPdebugMessage("initialize vbounds propagator for problem <%s>\n", SCIPgetProbName(scip));
794 
795  vars = SCIPgetVars(scip);
796  nvars = SCIPgetNVars(scip);
797  nbounds = 2 * nvars;
798 
799  /* store size of the bounds of variables array */
800  propdata->nbounds = nbounds;
801 
802  if( nbounds == 0 )
803  return SCIP_OKAY;
804 
805  propdata->initialized = TRUE;
806 
807  /* prepare priority queue structure */
808  SCIP_CALL( SCIPpqueueCreate(&propdata->propqueue, nvars, 2.0, compVarboundIndices) );
809  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->inqueue, nbounds) );
810  BMSclearMemoryArray(propdata->inqueue, nbounds);
811 
812  /* we need to copy the variable since this array is the basis of the propagator and the corresponding variable array
813  * within SCIP might change during the search
814  */
815  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &propdata->vars, vars, nvars) );
816  SCIP_CALL( SCIPhashmapCreate(&propdata->varhashmap, SCIPblkmem(scip), SCIPcalcHashtableSize(5 * nvars)) );
817 
818  for( v = 0; v < nvars; ++v )
819  {
820  SCIP_CALL( SCIPhashmapInsert(propdata->varhashmap, propdata->vars[v], (void*)(size_t)(v + 1)) );
821  }
822 
823  /* allocate memory for the arrays of the propdata */
824  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->topoorder, nbounds) );
825  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->vboundboundedidx, nbounds) );
826  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->vboundcoefs, nbounds) );
827  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->vboundconstants, nbounds) );
828  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->nvbounds, nbounds) );
829  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->vboundsize, nbounds) );
830  BMSclearMemoryArray(propdata->vboundboundedidx, nbounds);
831  BMSclearMemoryArray(propdata->vboundcoefs, nbounds);
832  BMSclearMemoryArray(propdata->vboundconstants, nbounds);
833  BMSclearMemoryArray(propdata->nvbounds, nbounds);
834  BMSclearMemoryArray(propdata->vboundsize, nbounds);
835 
836  for( v = 0; v < nbounds; ++v )
837  {
838  propdata->topoorder[v] = v;
839  propdata->vboundboundedidx[v] = NULL;
840  propdata->vboundcoefs[v] = NULL;
841  propdata->vboundconstants[v] = NULL;
842  propdata->nvbounds[v] = 0;
843  propdata->vboundsize[v] = 0;
844  }
845 
846  /* collect information about varbounds */
847  for( v = 0; v < nbounds; ++v )
848  {
849  SCIP_VAR** vbvars;
850  SCIP_VAR* var;
851  SCIP_Real* coefs;
852  SCIP_Real* constants;
853  SCIP_Bool lower;
854  int nvbvars;
855 
856  var = vars[getVarIndex(v)];
857  lower = isIndexLowerbound(v);
858 
859  /* get the variable bound informations for the current variable */
860  if( lower )
861  {
862  vbvars = SCIPvarGetVlbVars(var);
863  coefs = SCIPvarGetVlbCoefs(var);
864  constants = SCIPvarGetVlbConstants(var);
865  nvbvars = SCIPvarGetNVlbs(var);
866  }
867  else
868  {
869  vbvars = SCIPvarGetVubVars(var);
870  coefs = SCIPvarGetVubCoefs(var);
871  constants = SCIPvarGetVubConstants(var);
872  nvbvars = SCIPvarGetNVubs(var);
873  }
874 
875  /* loop over all variable lower bounds; a variable lower bound has the form: x >= b*y + d,
876  * a variable upper bound the form x <= b*y + d */
877  for( n = 0; n < nvbvars; ++n )
878  {
879  SCIP_VAR* vbvar;
880  SCIP_Real coef;
881  SCIP_Real constant;
882 
883  vbvar = vbvars[n];
884  coef = coefs[n];
885  constant = constants[n];
886  assert(vbvar != NULL);
887 
888  /* transform variable bound variable to an active variable, if possible */
889  SCIP_CALL( SCIPgetProbvarSum(scip, &vbvar, &coef, &constant) );
890  assert(vbvar != NULL);
891 
892  if( !SCIPvarIsActive(vbvar) )
893  continue;
894 
895  /* if the coefficient is positive, the type of bound is the same for the bounded and the bounding variable */
896  if( SCIPisPositive(scip, coef) )
897  startidx = (lower ? varGetLbIndex(propdata, vbvar) : varGetUbIndex(propdata, vbvar));
898  else
899  startidx = (lower ? varGetUbIndex(propdata, vbvar) : varGetLbIndex(propdata, vbvar));
900  assert(startidx >= 0);
901 
902  /* If the vbvar is binary, the vbound should be stored as an implication already.
903  * However, it might happen that vbvar was integer when the variable bound was added, but was converted
904  * to a binary variable later during presolving when its upper bound was changed to 1. In this case,
905  */
906  if( SCIPvarGetType(vbvar) == SCIP_VARTYPE_BINARY
907  && SCIPvarHasImplic(vbvar, isIndexLowerbound(startidx), var, getBoundtype(v)) )
908  {
909 #if 0
910  SCIP_VAR** implvars;
911  SCIP_Real* implbounds;
912  SCIP_BOUNDTYPE* impltypes;
913  int nimplvars;
914  int j;
915  SCIP_Bool startlower;
916 
917  startlower = isIndexLowerbound(startidx);
918 
919  implvars = SCIPvarGetImplVars(vbvar, startlower);
920  impltypes = SCIPvarGetImplTypes(vbvar, startlower);
921  implbounds = SCIPvarGetImplBounds(vbvar, startlower);
922  nimplvars = SCIPvarGetNImpls(vbvar, startlower);
923 
924  for( j = 0; j < nimplvars; ++j )
925  {
926  if( (implvars[j] == var) && (lower == (impltypes[j] == SCIP_BOUNDTYPE_LOWER)) )
927  {
928  if( lower )
929  assert(SCIPisGE(scip, implbounds[j], (startlower ? coef : 0.0) + constant));
930  else
931  assert(SCIPisLE(scip, implbounds[j], (startlower ? coef : 0.0) + constant));
932  break;
933  }
934  }
935  assert(j < nimplvars);
936 #endif
937  SCIPdebugMessage("varbound <%s> %s %g * <%s> + %g not added to propagator data due to reverse implication\n",
938  SCIPvarGetName(var), (lower ? ">=" : "<="), coef,
939  SCIPvarGetName(vbvar), constant);
940  }
941  else
942  {
943  SCIP_CALL( addVbound(scip, propdata, startidx, v, coef, constant) );
944 
945  SCIPdebugMessage("varbound <%s> %s %g * <%s> + %g added to propagator data\n",
946  SCIPvarGetName(var), (lower ? ">=" : "<="), coef,
947  SCIPvarGetName(vbvar), constant);
948 
949  }
950  }
951  }
952 
953  /* sort the bounds topologically */
954  if( propdata->dotoposort )
955  {
956  SCIP_CALL( topologicalSort(scip, propdata) );
957  }
958 
959  /* catch variable events */
960  SCIP_CALL( catchEvents(scip, propdata) );
961 
962  return SCIP_OKAY;
963 }
964 
965 
966 /** resolves a propagation by adding the variable which implied that bound change */
967 static
968 SCIP_RETCODE resolvePropagation(
969  SCIP* scip, /**< SCIP data structure */
970  SCIP_PROPDATA* propdata, /**< propagator data */
971  SCIP_VAR* var, /**< variable to be reported */
972  SCIP_BOUNDTYPE boundtype, /**< bound to be reported */
973  SCIP_BDCHGIDX* bdchgidx /**< the index of the bound change, representing the point of time where the change took place, or NULL for the current local bounds */
974  )
975 {
976  assert(propdata != NULL);
977  assert(boundtype == SCIP_BOUNDTYPE_LOWER || boundtype == SCIP_BOUNDTYPE_UPPER);
978 
979  SCIPdebugMessage(" -> add %s bound of variable <%s> as reason\n",
980  getBoundtypeString(boundtype), SCIPvarGetName(var));
981 
982  switch( boundtype )
983  {
984  case SCIP_BOUNDTYPE_LOWER:
985  SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) );
986  break;
987  case SCIP_BOUNDTYPE_UPPER:
988  SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) );
989  break;
990  default:
991  SCIPerrorMessage("invalid bound type <%d>\n", boundtype);
992  SCIPABORT();
993  return SCIP_INVALIDDATA; /*lint !e527*/
994  }
995 
996  return SCIP_OKAY;
997 }
998 
999 /** relaxes bound of give variable as long as the given inference bound still leads to a cutoff and add that bound
1000  * change to the conflict set
1001  */
1002 static
1003 SCIP_RETCODE relaxVbdvar(
1004  SCIP* scip, /**< SCIP data structure */
1005  SCIP_VAR* var, /**< variable for which the upper bound should be relaxed */
1006  SCIP_BOUNDTYPE boundtype, /**< boundtype used for the variable bound variable */
1007  SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place, or NULL for the current local bounds */
1008  SCIP_Real relaxedbd /**< relaxed bound */
1009  )
1010 {
1011  if( boundtype == SCIP_BOUNDTYPE_LOWER )
1012  {
1013  SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, relaxedbd) );
1014  }
1015  else
1016  {
1017  assert(boundtype == SCIP_BOUNDTYPE_UPPER);
1018  SCIP_CALL( SCIPaddConflictRelaxedUb(scip, var, bdchgidx, relaxedbd) );
1019  }
1020 
1021  return SCIP_OKAY;
1022 }
1023 
1024 /** compute the relaxed bound which is sufficient to propagate the inference lower bound of given variable */
1025 static
1026 SCIP_Real computeRelaxedLowerbound(
1027  SCIP* scip, /**< SCIP data structure */
1028  SCIP_VAR* var, /**< variable which was propagated */
1029  SCIP_Real inferlb, /**< inference lower bound */
1030  SCIP_Real coef, /**< inference variable bound coefficient used */
1031  SCIP_Real constant /**< inference variable bound constant used */
1032  )
1033 {
1034  SCIP_Real relaxedbd;
1035 
1036  if( SCIPvarIsIntegral(var) )
1037  relaxedbd = (inferlb - 1.0 + 2*SCIPfeastol(scip) - constant) / coef;
1038  else
1039  relaxedbd = (inferlb - constant) / coef;
1040 
1041  /* check the computed relaxed lower/upper bound is a proper reason for the inference bound which has to be explained */
1042  assert(SCIPisEQ(scip, inferlb, SCIPadjustedVarLb(scip, var, relaxedbd * coef + constant)));
1043 
1044  return relaxedbd;
1045 }
1046 
1047 
1048 /** analyzes an infeasibility which was reached by updating the lower bound of the inference variable above its upper
1049  * bound
1050  */
1051 static
1052 SCIP_RETCODE analyzeConflictLowerbound(
1053  SCIP* scip, /**< SCIP data structure */
1054  SCIP_PROPDATA* propdata, /**< propagator data */
1055  SCIP_VAR* infervar, /**< variable which led to a cutoff */
1056  SCIP_Real inferlb, /**< lower bound which led to infeasibility */
1057  SCIP_VAR* vbdvar, /**< variable which is the reason for the lower bound change */
1058  SCIP_BOUNDTYPE boundtype, /**< bound which is the reason for the lower bound change */
1059  SCIP_Real coef, /**< inference variable bound coefficient used */
1060  SCIP_Real constant, /**< inference variable bound constant used */
1061  SCIP_Bool canwide /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1062  )
1063 {
1064  assert(scip != NULL);
1065  assert(propdata != NULL);
1066  assert(infervar != NULL);
1067  assert(SCIPisEQ(scip, SCIPvarGetUbLocal(infervar), SCIPvarGetUbAtIndex(infervar, NULL, FALSE)));
1068  assert(SCIPisEQ(scip, SCIPvarGetUbAtIndex(infervar, NULL, TRUE), SCIPvarGetUbAtIndex(infervar, NULL, FALSE)));
1069  assert(SCIPisGT(scip, inferlb, SCIPvarGetUbLocal(infervar)));
1070  assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING);
1071 
1072  /* check if conflict analysis is applicable */
1073  if( !SCIPisConflictAnalysisApplicable(scip) )
1074  return SCIP_OKAY;
1075 
1076  if( canwide && propdata->usebdwidening )
1077  {
1078  SCIP_Real relaxedbd;
1079  SCIP_Real relaxedub;
1080 
1081  SCIPdebugMessage("try to create conflict using bound widening order: inference variable, variable bound variable\n");
1082 
1083  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1084  SCIP_CALL( SCIPinitConflictAnalysis(scip) );
1085 
1086  /* adjust lower bound */
1087  inferlb = SCIPadjustedVarLb(scip, infervar, inferlb);
1088 
1089  /* compute a relaxed upper bound which would be sufficient to be still infeasible */
1090  if( SCIPvarIsIntegral(infervar) )
1091  relaxedub = inferlb - 1.0;
1092  else
1093  relaxedub = inferlb - 2*SCIPfeastol(scip);
1094 
1095  /* try to relax inference variable upper bound such that the infeasibility is still given */
1096  SCIP_CALL( SCIPaddConflictRelaxedUb(scip, infervar, NULL, relaxedub) );
1097 
1098  /* collect the upper bound which is reported to the conflict analysis */
1099  relaxedub = SCIPgetConflictVarUb(scip, infervar);
1100 
1101  /* adjust inference bound with respect to the upper bound reported to the conflict analysis */
1102  if( SCIPvarIsIntegral(infervar) )
1103  relaxedub = relaxedub + 1.0;
1104  else
1105  relaxedub = relaxedub + 2*SCIPfeastol(scip);
1106 
1107  /* compute the relaxed bound which is sufficient to propagate the inference lower bound of given variable */
1108  relaxedbd = computeRelaxedLowerbound(scip, infervar, relaxedub, coef, constant);
1109 
1110  /* try to relax variable bound variable */
1111  SCIP_CALL( relaxVbdvar(scip, vbdvar, boundtype, NULL, relaxedbd) );
1112 
1113  /* analyze the conflict */
1114  SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
1115  }
1116  else
1117  {
1118  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1119  SCIP_CALL( SCIPinitConflictAnalysis(scip) );
1120 
1121  /* add upper bound of the variable for which we tried to change the lower bound */
1122  SCIP_CALL( SCIPaddConflictUb(scip, infervar, NULL) );
1123 
1124  /* add (correct) bound of the variable which let to the new lower bound */
1125  SCIP_CALL( resolvePropagation(scip, propdata, vbdvar, boundtype, NULL) );
1126 
1127  /* analyze the conflict */
1128  SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
1129  }
1130 
1131  return SCIP_OKAY;
1132 }
1133 
1134 /** compute the relaxed bound which is sufficient to propagate the inference upper bound of given variable */
1135 static
1136 SCIP_Real computeRelaxedUpperbound(
1137  SCIP* scip, /**< SCIP data structure */
1138  SCIP_VAR* var, /**< variable which was propagated */
1139  SCIP_Real inferub, /**< inference upper bound */
1140  SCIP_Real coef, /**< inference variable bound coefficient used */
1141  SCIP_Real constant /**< inference variable bound constant used */
1142  )
1143 {
1144  SCIP_Real relaxedbd;
1145 
1146  if( SCIPvarIsIntegral(var) )
1147  relaxedbd = (inferub + 1.0 - 2*SCIPfeastol(scip) - constant) / coef;
1148  else
1149  relaxedbd = (inferub - constant) / coef;
1150 
1151  /* check the computed relaxed lower/upper bound is a proper reason for the inference bound which has to be explained */
1152  assert(SCIPisEQ(scip, inferub, SCIPadjustedVarUb(scip, var, relaxedbd * coef + constant)));
1153 
1154  return relaxedbd;
1155 }
1156 
1157 /** analyzes an infeasibility which was reached by updating the upper bound of the inference variable below its lower
1158  * bound
1159  */
1160 static
1161 SCIP_RETCODE analyzeConflictUpperbound(
1162  SCIP* scip, /**< SCIP data structure */
1163  SCIP_PROPDATA* propdata, /**< propagator data */
1164  SCIP_VAR* infervar, /**< variable which led to a cutoff */
1165  SCIP_Real inferub, /**< upper bound which led to infeasibility */
1166  SCIP_VAR* vbdvar, /**< variable which is the reason for the upper bound change */
1167  SCIP_BOUNDTYPE boundtype, /**< bound which is the reason for the upper bound change */
1168  SCIP_Real coef, /**< inference variable bound coefficient used */
1169  SCIP_Real constant, /**< inference variable bound constant used */
1170  SCIP_Bool canwide /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1171  )
1172 {
1173  assert(scip != NULL);
1174  assert(propdata != NULL);
1175  assert(infervar != NULL);
1176  assert(SCIPisEQ(scip, SCIPvarGetLbLocal(infervar), SCIPvarGetLbAtIndex(infervar, NULL, FALSE)));
1177  assert(SCIPisEQ(scip, SCIPvarGetLbAtIndex(infervar, NULL, TRUE), SCIPvarGetLbAtIndex(infervar, NULL, FALSE)));
1178  assert(SCIPisLT(scip, inferub, SCIPvarGetLbLocal(infervar)));
1179  assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING);
1180 
1181  /* check if conflict analysis is applicable */
1182  if( !SCIPisConflictAnalysisApplicable(scip) )
1183  return SCIP_OKAY;
1184 
1185  if( canwide && propdata->usebdwidening )
1186  {
1187  SCIP_Real relaxedbd;
1188  SCIP_Real relaxedlb;
1189 
1190  SCIPdebugMessage("try to create conflict using bound widening order: inference variable, variable bound variable\n");
1191 
1192  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1193  SCIP_CALL( SCIPinitConflictAnalysis(scip) );
1194 
1195  /* adjust upper bound */
1196  inferub = SCIPadjustedVarUb(scip, infervar, inferub);
1197 
1198  /* compute a relaxed lower bound which would be sufficient to be still infeasible */
1199  if( SCIPvarIsIntegral(infervar) )
1200  relaxedlb = inferub + 1.0;
1201  else
1202  relaxedlb = inferub + 2*SCIPfeastol(scip);
1203 
1204  /* try to relax inference variable lower bound such that the infeasibility is still given */
1205  SCIP_CALL( SCIPaddConflictRelaxedLb(scip, infervar, NULL, relaxedlb) );
1206 
1207  /* collect the lower bound which is reported to the conflict analysis */
1208  relaxedlb = SCIPgetConflictVarLb(scip, infervar);
1209 
1210  /* adjust inference bound with respect to the upper bound reported to the conflict analysis */
1211  if( SCIPvarIsIntegral(infervar) )
1212  relaxedlb = relaxedlb - 1.0;
1213  else
1214  relaxedlb = relaxedlb - 2*SCIPfeastol(scip);
1215 
1216  /* compute the relaxed bound which is sufficient to propagate the inference upper bound of given variable */
1217  relaxedbd = computeRelaxedUpperbound(scip, infervar, relaxedlb, coef, constant);
1218 
1219  /* try to relax variable bound variable */
1220  SCIP_CALL( relaxVbdvar(scip, vbdvar, boundtype, NULL, relaxedbd) );
1221 
1222  /* analyze the conflict */
1223  SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
1224  }
1225  else
1226  {
1227  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1228  SCIP_CALL( SCIPinitConflictAnalysis(scip) );
1229 
1230  /* add lower bound of the variable for which we tried to change the upper bound */
1231  SCIP_CALL( SCIPaddConflictLb(scip, infervar, NULL) );
1232 
1233  /* add (correct) bound of the variable which let to the new upper bound */
1234  SCIP_CALL( resolvePropagation(scip, propdata, vbdvar, boundtype, NULL) );
1235 
1236  /* analyze the conflict */
1237  SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
1238  }
1239 
1240  return SCIP_OKAY;
1241 }
1242 
1243 
1244 /* tries to tighten the (global) lower bound of the given variable to the given new bound */
1245 static
1246 SCIP_RETCODE tightenVarLb(
1247  SCIP* scip, /**< SCIP data structure */
1248  SCIP_PROP* prop, /**< vbounds propagator */
1249  SCIP_PROPDATA* propdata, /**< propagator data */
1250  SCIP_VAR* var, /**< variable whose lower bound should be tightened */
1251  SCIP_Real newlb, /**< new lower bound for the variable */
1252  SCIP_Bool global, /**< is the bound globally valid? */
1253  SCIP_VAR* vbdvar, /**< variable which is the reason for the lower bound change */
1254  SCIP_BOUNDTYPE boundtype, /**< bound which is the reason for the lower bound change */
1255  SCIP_Bool force, /**< should domain changes for continuous variables be forced */
1256  SCIP_Real coef, /**< coefficient in vbound constraint causing the propagation;
1257  * or 0.0 if propagation is caused by clique or implication */
1258  SCIP_Real constant, /**< constant in vbound constraint causing the propagation;
1259  * or 0.0 if propagation is caused by clique or implication */
1260  SCIP_Bool canwide, /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1261  int* nchgbds, /**< pointer to increase, if a bound was changed */
1262  SCIP_RESULT* result /**< pointer to store the result of the propagation */
1263  )
1264 {
1265  INFERINFO inferinfo;
1266  SCIP_Real lb;
1267  SCIP_Bool tightened;
1268  SCIP_Bool infeasible;
1269 
1270  assert(scip != NULL);
1271  assert(prop != NULL);
1272  assert(propdata != NULL);
1273  assert(var != NULL);
1274  assert(nchgbds != NULL);
1275  assert(result != NULL);
1276 
1277  lb = SCIPvarGetLbLocal(var);
1278 
1279  /* check that the new upper bound is better */
1280  if( (SCIPvarIsIntegral(var) && newlb - lb > 0.5) || (force && SCIPisGT(scip, newlb, lb)) )
1281  force = TRUE;
1282  else
1283  force = FALSE;
1284 
1285  /* try to tighten the lower bound */
1286  if( global )
1287  {
1288  SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, newlb, force, &infeasible, &tightened) );
1289  }
1290  else
1291  {
1292  inferinfo = getInferInfo(boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, vbdvar) : varGetUbIndex(propdata, vbdvar), boundtype);
1293 
1294  SCIP_CALL( SCIPinferVarLbProp(scip, var, newlb, prop, inferInfoToInt(inferinfo), force, &infeasible, &tightened) );
1295  }
1296 
1297  if( infeasible )
1298  {
1299  /* the infeasible results comes from the fact that the new lower bound lies above the current upper bound */
1300  assert(SCIPisGT(scip, newlb, SCIPvarGetUbLocal(var)));
1301  assert(!global || SCIPisGT(scip, newlb, SCIPvarGetUbGlobal(var)));
1302 
1303  SCIPdebugMessage("tightening%s lower bound of variable <%s> to %g due the %s bound of variable <%s> led to infeasibility\n",
1304  (global ? " global" : ""), SCIPvarGetName(var), newlb, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1305 
1306  if( global )
1307  {
1308  /* cutoff the root node */
1309  SCIP_CALL( SCIPcutoffNode(scip, SCIPgetRootNode(scip)) );
1310  }
1311  else
1312  {
1313  /* analyzes a infeasibility via conflict analysis */
1314  SCIP_CALL( analyzeConflictLowerbound(scip, propdata, var, newlb, vbdvar, boundtype, coef, constant, canwide) );
1315  }
1316  *result = SCIP_CUTOFF;
1317  }
1318  else if( tightened )
1319  {
1320  SCIPdebugMessage("tightened%s lower bound of variable <%s> to %g due the %s bound of variable <%s>\n",
1321  (global ? " global" : ""), SCIPvarGetName(var), newlb, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1322  (*nchgbds)++;
1323  }
1324 
1325  return SCIP_OKAY;
1326 }
1327 
1328 /* tries to tighten the (global) upper bound of the given variable to the given new bound */
1329 static
1330 SCIP_RETCODE tightenVarUb(
1331  SCIP* scip, /**< SCIP data structure */
1332  SCIP_PROP* prop, /**< vbounds propagator */
1333  SCIP_PROPDATA* propdata, /**< propagator data */
1334  SCIP_VAR* var, /**< variable whose upper bound should be tightened */
1335  SCIP_Real newub, /**< new upper bound of the variable */
1336  SCIP_Bool global, /**< is the bound globally valid? */
1337  SCIP_VAR* vbdvar, /**< variable which is the reason for the upper bound change */
1338  SCIP_BOUNDTYPE boundtype, /**< bound which is the reason for the upper bound change */
1339  SCIP_Bool force, /**< should domain changes for continuous variables be forced */
1340  SCIP_Real coef, /**< coefficient in vbound constraint causing the propagation;
1341  * or 0.0 if propagation is caused by clique or implication */
1342  SCIP_Real constant, /**< constant in vbound constraint causing the propagation;
1343  * or 0.0 if propagation is caused by clique or implication */
1344  SCIP_Bool canwide, /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1345  int* nchgbds, /**< pointer to increase, if a bound was changed */
1346  SCIP_RESULT* result /**< pointer to store the result of the propagation */
1347  )
1348 {
1349  INFERINFO inferinfo;
1350  SCIP_Real ub;
1351  SCIP_Bool tightened;
1352  SCIP_Bool infeasible;
1353 
1354  assert(scip != NULL);
1355  assert(prop != NULL);
1356  assert(propdata != NULL);
1357  assert(var != NULL);
1358  assert(nchgbds != NULL);
1359  assert(result != NULL);
1360 
1361  ub = SCIPvarGetUbLocal(var);
1362 
1363  /* check that the new upper bound is better */
1364  if( (SCIPvarIsIntegral(var) && ub - newub > 0.5) || (force && SCIPisLT(scip, newub, ub)) )
1365  force = TRUE;
1366  else
1367  force = FALSE;
1368 
1369  /* try to tighten the upper bound */
1370  if( global )
1371  {
1372  SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, newub, force, &infeasible, &tightened) );
1373  }
1374  else
1375  {
1376  inferinfo = getInferInfo(boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, vbdvar) : varGetUbIndex(propdata, vbdvar), boundtype);
1377 
1378  SCIP_CALL( SCIPinferVarUbProp(scip, var, newub, prop, inferInfoToInt(inferinfo), force, &infeasible, &tightened) );
1379  }
1380 
1381  if( infeasible )
1382  {
1383  /* the infeasible results comes from the fact that the new upper bound lies below the current lower bound */
1384  assert(SCIPisLT(scip, newub, SCIPvarGetLbLocal(var)));
1385  assert(!global || SCIPisLT(scip, newub, SCIPvarGetLbGlobal(var)));
1386 
1387  SCIPdebugMessage("tightening%s upper bound of variable <%s> to %g due the %s bound of variable <%s> led to infeasibility\n",
1388  (global ? " global" : ""), SCIPvarGetName(var), newub, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1389 
1390  if( global )
1391  {
1392  /* cutoff the root node */
1393  SCIP_CALL( SCIPcutoffNode(scip, SCIPgetRootNode(scip)) );
1394  }
1395  else
1396  {
1397  /* analyzes a infeasibility via conflict analysis */
1398  SCIP_CALL( analyzeConflictUpperbound(scip, propdata, var, newub, vbdvar, boundtype, coef, constant, canwide) );
1399  }
1400  *result = SCIP_CUTOFF;
1401  }
1402  else if( tightened )
1403  {
1404  SCIPdebugMessage("tightened%s upper bound of variable <%s> to %g due the %s bound of variable <%s>\n",
1405  (global ? " global" : ""), SCIPvarGetName(var), newub, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1406  (*nchgbds)++;
1407  }
1408 
1409  return SCIP_OKAY;
1410 }
1411 
1412 /** performs propagation of variables lower and upper bounds, implications, and cliques */
1413 static
1414 SCIP_RETCODE propagateVbounds(
1415  SCIP* scip, /**< SCIP data structure */
1416  SCIP_PROP* prop, /**< vbounds propagator */
1417  SCIP_Bool force, /**< should domain changes for continuous variables be forced */
1418  SCIP_RESULT* result /**< pointer to store the result of the propagation */
1419  )
1420 {
1421  SCIP_PROPDATA* propdata;
1422  SCIP_VAR** vars;
1423  SCIP_VAR* startvar;
1424  SCIP_BOUNDTYPE starttype;
1425  SCIP_Real startbound;
1426  SCIP_Real globalbound;
1427  int startpos;
1428  int topopos;
1429  int v;
1430  int n;
1431  int nchgbds;
1432  int nbounds;
1433  SCIP_Bool lower;
1434  SCIP_Bool global;
1435 
1436  assert(scip != NULL);
1437  assert(prop != NULL);
1438  assert(result != NULL);
1439 
1440  (*result) = SCIP_DIDNOTRUN;
1441 
1442  /* we do not run the propagator in presolving, because we want to avoid doing the expensive creation of the graph twice */
1443  if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING )
1444  return SCIP_OKAY;
1445 
1446  propdata = SCIPpropGetData(prop);
1447  assert(propdata != NULL);
1448 
1449  /* initialize propagator data needed for propagation, if not done yet */
1450  if( !propdata->initialized )
1451  {
1452  SCIP_CALL( initData(scip, prop) );
1453  }
1454  assert(propdata->nbounds == 0 || propdata->propqueue != NULL);
1455 
1456  vars = propdata->vars;
1457  nbounds = propdata->nbounds;
1458 
1459  if( nbounds == 0 )
1460  return SCIP_OKAY;
1461 
1462  /* propagate all variables if we are in repropagation */
1463  if( SCIPinRepropagation(scip) )
1464  {
1465  SCIP_VAR* var;
1466  int idx;
1467 
1468  for( v = nbounds - 1; v >= 0; --v )
1469  {
1470  idx = propdata->topoorder[v];
1471  if( idx != -1 && !propdata->inqueue[v] )
1472  {
1473  var = vars[getVarIndex(idx)];
1474  lower = isIndexLowerbound(idx);
1475  if( !SCIPvarIsBinary(var) || (lower && SCIPvarGetLbLocal(var) > 0.5)
1476  || (!lower && SCIPvarGetUbLocal(var) < 0.5) )
1477  {
1478  SCIP_CALL( SCIPpqueueInsert(propdata->propqueue, (void*)(size_t)(v + 1)) );
1479  propdata->inqueue[v] = TRUE;
1480  }
1481  }
1482  }
1483  }
1484 
1485  /* return if no bound changes are in the priority queue (no changed bounds to handle since last propagation) */
1486  if( SCIPpqueueNElems(propdata->propqueue) == 0 )
1487  {
1488  (*result) = SCIP_DIDNOTFIND;
1489  return SCIP_OKAY;
1490  }
1491 
1492  nchgbds = 0;
1493 
1494  SCIPdebugMessage("varbound propagator: %d elements in the propagation queue\n", SCIPpqueueNElems(propdata->propqueue));
1495 
1496  /* get variable bound of highest priority from priority queue and try to deduce bound changes for other variables;
1497  * the priority queue is ordered w.r.t the topological sort of the varbound graph
1498  */
1499  while( SCIPpqueueNElems(propdata->propqueue) > 0 )
1500  {
1501  topopos = ((int)(size_t)SCIPpqueueRemove(propdata->propqueue)) - 1;
1502  assert(propdata->inqueue[topopos]);
1503  startpos = propdata->topoorder[topopos];
1504  assert(startpos >= 0);
1505  propdata->inqueue[topopos] = FALSE;
1506 
1507  startvar = vars[getVarIndex(startpos)];
1508  starttype = getBoundtype(startpos);
1509  lower = (starttype == SCIP_BOUNDTYPE_LOWER);
1510  startbound = ( lower ? SCIPvarGetLbLocal(startvar) : SCIPvarGetUbLocal(startvar) );
1511  globalbound = ( lower ? SCIPvarGetLbGlobal(startvar) : SCIPvarGetUbGlobal(startvar));
1512  global = SCIPisEQ(scip, startbound, globalbound);
1513 
1514  SCIPdebugMessage("propagate new %s bound of %g of variable <%s>:\n",
1515  getBoundtypeString(starttype), startbound, SCIPvarGetName(startvar));
1516 
1517  /* there should be neither implications nor cliques for non-binary variables */
1518  assert(SCIPvarIsBinary(startvar) || SCIPvarGetNImpls(startvar, lower) == 0);
1519  assert(SCIPvarIsBinary(startvar) || SCIPvarGetNCliques(startvar, lower) == 0);
1520 
1521  if( SCIPvarIsBinary(startvar) )
1522  {
1523  /* we only propagate binary variables if the lower bound changed to 1.0 or the upper bound changed to 0.0 */
1524  if( lower != (startbound > 0.5) )
1525  continue;
1526 
1527  /* propagate implications */
1528  if( propdata->useimplics )
1529  {
1530  int nimplvars;
1531 
1532  /* if the lower bound of the startvar was changed, it was fixed to 1.0, otherwise it was fixed to 0.0;
1533  * get all implications for this varfixing
1534  */
1535  nimplvars = SCIPvarGetNImpls(startvar, lower);
1536 
1537  /* if there are implications for the varfixing, propagate them */
1538  if( nimplvars > 0 )
1539  {
1540  SCIP_VAR** implvars;
1541  SCIP_BOUNDTYPE* impltypes;
1542  SCIP_Real* implbounds;
1543  int* implids;
1544 
1545  implvars = SCIPvarGetImplVars(startvar, lower);
1546  impltypes = SCIPvarGetImplTypes(startvar, lower);
1547  implbounds = SCIPvarGetImplBounds(startvar, lower);
1548  implids = SCIPvarGetImplIds(startvar, lower);
1549 
1550  for( n = 0; n < nimplvars; ++n )
1551  {
1552  /* implication is just a shortcut, so we do not propagate it now,
1553  * because we will propagate the longer way, anyway
1554  */
1555  if( implids[n] < 0 )
1556  continue;
1557 
1558  /* it might happen that implications point to inactive variables (normally, those are removed when a
1559  * variable becomes inactive, but in some cases, it cannot be done), we have to ignore these variables
1560  */
1561  if( !SCIPvarIsActive(implvars[n]) )
1562  continue;
1563 
1564  if( impltypes[n] == SCIP_BOUNDTYPE_LOWER )
1565  {
1566  SCIP_CALL( tightenVarLb(scip, prop, propdata, implvars[n], implbounds[n], global, startvar,
1567  starttype, force, 0.0, 0.0, FALSE, &nchgbds, result) );
1568  }
1569  else
1570  {
1571  SCIP_CALL( tightenVarUb(scip, prop, propdata, implvars[n], implbounds[n], global, startvar,
1572  starttype, force, 0.0, 0.0, FALSE, &nchgbds, result) );
1573  }
1574 
1575  if( *result == SCIP_CUTOFF )
1576  return SCIP_OKAY;
1577  }
1578  }
1579  }
1580 
1581  /* propagate cliques */
1582  if( propdata->usecliques )
1583  {
1584  int ncliques;
1585 
1586  /* if the lower bound of the startvar was changed, it was fixed to 1.0, otherwise it was fixed to 0.0;
1587  * get all cliques for this varfixing
1588  */
1589  ncliques = SCIPvarGetNCliques(startvar, lower);
1590 
1591  /* if there are cliques for the varfixing, propagate them */
1592  if( ncliques > 0 )
1593  {
1594  SCIP_CLIQUE** cliques;
1595  int j;
1596 
1597  cliques = SCIPvarGetCliques(startvar, lower);
1598 
1599  for( j = 0; j < ncliques; ++j )
1600  {
1601  SCIP_VAR** cliquevars;
1602  SCIP_Bool* cliquevals;
1603  int ncliquevars;
1604 
1605  cliquevars = SCIPcliqueGetVars(cliques[j]);
1606  cliquevals = SCIPcliqueGetValues(cliques[j]);
1607  ncliquevars = SCIPcliqueGetNVars(cliques[j]);
1608 
1609  /* fix all variables except for the startvar to the value which is not in the clique */
1610  for( n = 0; n < ncliquevars; ++n )
1611  {
1612  if( cliquevars[n] == startvar )
1613  continue;
1614 
1615  /* try to tighten the bound */
1616  if( cliquevals[n] )
1617  {
1618  /* unnegated variable is in clique, so it has to be fixed to 0.0 */
1619  SCIP_CALL( tightenVarUb(scip, prop, propdata, cliquevars[n], 0.0, global, startvar, starttype,
1620  force, 0.0, 0.0, FALSE, &nchgbds, result) );
1621  }
1622  else
1623  {
1624  /* negated variable is in clique, so it has to be fixed to 1.0 */
1625  SCIP_CALL( tightenVarLb(scip, prop, propdata, cliquevars[n], 1.0, global, startvar, starttype,
1626  force, 0.0, 0.0, FALSE, &nchgbds, result) );
1627  }
1628  if( *result == SCIP_CUTOFF )
1629  return SCIP_OKAY;
1630  }
1631  }
1632  }
1633  }
1634  }
1635 
1636  /* propagate vbounds */
1637  if( propdata->usevbounds )
1638  {
1639  SCIP_VAR* boundedvar;
1640  SCIP_Real newbound;
1641  SCIP_Real coef;
1642  SCIP_Real constant;
1643 
1644  /* iterate over all vbounds for the given bound */
1645  for( n = 0; n < propdata->nvbounds[startpos]; ++n )
1646  {
1647  boundedvar = vars[getVarIndex(propdata->vboundboundedidx[startpos][n])];
1648  coef = propdata->vboundcoefs[startpos][n];
1649  constant = propdata->vboundconstants[startpos][n];
1650 
1651  /* compute new bound */
1652  newbound = startbound * coef + constant;
1653 
1654  /* try to tighten the bound */
1655  if( isIndexLowerbound(propdata->vboundboundedidx[startpos][n]) )
1656  {
1657  SCIP_CALL( tightenVarLb(scip, prop, propdata, boundedvar, newbound, global, startvar, starttype, force,
1658  coef, constant, TRUE, &nchgbds, result) );
1659  }
1660  else
1661  {
1662  SCIP_CALL( tightenVarUb(scip, prop, propdata, boundedvar, newbound, global, startvar, starttype, force,
1663  coef, constant, TRUE, &nchgbds, result) );
1664  }
1665 
1666  if( *result == SCIP_CUTOFF )
1667  return SCIP_OKAY;
1668  }
1669  }
1670  }
1671 
1672  SCIPdebugMessage("tightened %d variable bounds\n", nchgbds);
1673 
1674  /* set the result depending on whether bound changes were found or not */
1675  if( nchgbds > 0 )
1676  (*result) = SCIP_REDUCEDDOM;
1677  else
1678  (*result) = SCIP_DIDNOTFIND;
1679 
1680  return SCIP_OKAY;
1681 }
1682 
1683 /**@name Callback methods of propagator
1684  *
1685  * @{
1686  */
1687 
1688 /** copy method for propagator plugins (called when SCIP copies plugins) */
1689 static
1690 SCIP_DECL_PROPCOPY(propCopyVbounds)
1691 { /*lint --e{715}*/
1692  assert(scip != NULL);
1693  assert(prop != NULL);
1694  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
1695 
1696  /* call inclusion method of propagator */
1697  SCIP_CALL( SCIPincludePropVbounds(scip) );
1698 
1699  return SCIP_OKAY;
1700 }
1701 
1702 /** destructor of propagator to free user data (called when SCIP is exiting) */
1703 static
1704 SCIP_DECL_PROPFREE(propFreeVbounds)
1705 { /*lint --e{715}*/
1706  SCIP_PROPDATA* propdata;
1707 
1708  /* free propagator data */
1709  propdata = SCIPpropGetData(prop);
1710 
1711  SCIPfreeMemory(scip, &propdata);
1712  SCIPpropSetData(prop, NULL);
1713 
1714  return SCIP_OKAY;
1715 }
1716 
1717 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
1718 static
1719 SCIP_DECL_PROPEXITSOL(propExitsolVbounds)
1720 { /*lint --e{715}*/
1721  SCIP_PROPDATA* propdata;
1722  int v;
1723 
1724  propdata = SCIPpropGetData(prop);
1725  assert(propdata != NULL);
1726 
1727  /* free data stored for propagation */
1728  if( propdata->initialized )
1729  {
1730  /* drop all variable events */
1731  SCIP_CALL( dropEvents(scip, propdata) );
1732 
1733  /* release all variables */
1734  for( v = 0; v < propdata->nbounds; ++v )
1735  {
1736  /* free vbound data */
1737  if( propdata->vboundsize[v] > 0 )
1738  {
1739  SCIPfreeMemoryArray(scip, &propdata->vboundboundedidx[v]);
1740  SCIPfreeMemoryArray(scip, &propdata->vboundcoefs[v]);
1741  SCIPfreeMemoryArray(scip, &propdata->vboundconstants[v]);
1742  }
1743  }
1744 
1745  /* free priority queue */
1746  SCIPpqueueFree(&propdata->propqueue);
1747 
1748  /* free arrays */
1749  SCIPfreeBlockMemoryArray(scip, &propdata->vboundsize, propdata->nbounds);
1750  SCIPfreeBlockMemoryArray(scip, &propdata->nvbounds, propdata->nbounds);
1751  SCIPfreeBlockMemoryArray(scip, &propdata->vboundconstants, propdata->nbounds);
1752  SCIPfreeBlockMemoryArray(scip, &propdata->vboundcoefs, propdata->nbounds);
1753  SCIPfreeBlockMemoryArray(scip, &propdata->vboundboundedidx, propdata->nbounds);
1754  SCIPfreeBlockMemoryArray(scip, &propdata->inqueue, propdata->nbounds);
1755  SCIPfreeBlockMemoryArray(scip, &propdata->topoorder, propdata->nbounds);
1756 
1757  /* free variable array and hashmap */
1758  SCIPhashmapFree(&propdata->varhashmap);
1759  SCIPfreeBlockMemoryArray(scip, &propdata->vars, propdata->nbounds / 2);
1760  }
1761 
1762  /* reset propagation data */
1763  resetPropdata(propdata);
1764 
1765  return SCIP_OKAY;
1766 }
1767 
1768 /** execution method of propagator */
1769 static
1770 SCIP_DECL_PROPEXEC(propExecVbounds)
1771 { /*lint --e{715}*/
1772 
1773  /* perform variable lower and upper bound propagation */
1774  SCIP_CALL( propagateVbounds(scip, prop, FALSE, result) );
1775 
1776  assert((*result) == SCIP_CUTOFF || (*result) == SCIP_DIDNOTRUN
1777  || (*result) == SCIP_DIDNOTFIND || (*result) == SCIP_REDUCEDDOM);
1778 
1779  return SCIP_OKAY;
1780 }
1781 
1782 
1783 /** propagation conflict resolving method of propagator */
1784 static
1785 SCIP_DECL_PROPRESPROP(propRespropVbounds)
1786 { /*lint --e{715}*/
1787  SCIP_PROPDATA* propdata;
1788  SCIP_VAR** vars;
1789  SCIP_VAR* startvar;
1790  SCIP_BOUNDTYPE starttype;
1791  int pos;
1792 
1793  propdata = SCIPpropGetData(prop);
1794  assert(propdata != NULL);
1795 
1796  starttype = inferInfoGetBoundtype(intToInferInfo(inferinfo));
1797  pos = inferInfoGetPos(intToInferInfo(inferinfo));
1798  assert(pos >= 0);
1799  assert(pos < propdata->nbounds);
1800 
1801  vars = propdata->vars;
1802  assert(vars != NULL);
1803  startvar = vars[getVarIndex(pos)];
1804  assert(startvar != NULL);
1805  assert(startvar != infervar);
1806 
1807  SCIPdebugMessage("explain %s bound change of variable <%s>\n",
1808  getBoundtypeString(boundtype), SCIPvarGetName(infervar));
1809 
1810  if( !SCIPvarIsBinary(startvar) && propdata->usebdwidening )
1811  {
1812  int* vboundboundedidx;
1813  SCIP_Real constant;
1814  SCIP_Real coef;
1815  int inferidx;
1816  int nvbounds;
1817  int b;
1818 
1819  nvbounds = propdata->nvbounds[pos];
1820  vboundboundedidx = propdata->vboundboundedidx[pos];
1821 
1822  inferidx = boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, infervar) : varGetUbIndex(propdata, infervar);
1823  assert(inferidx >= 0);
1824 
1825  for( b = 0; b < nvbounds; ++b )
1826  {
1827  if( vboundboundedidx[b] == inferidx )
1828  break;
1829  }
1830  assert(b < nvbounds);
1831 
1832  coef = propdata->vboundcoefs[pos][b];
1833  constant = propdata->vboundconstants[pos][b];
1834  assert(!SCIPisZero(scip, coef));
1835 
1836  /* compute the relaxed bound which is sufficient to propagate the inference bound of given variable */
1837  if( boundtype == SCIP_BOUNDTYPE_LOWER )
1838  relaxedbd = computeRelaxedLowerbound(scip, infervar, relaxedbd, coef, constant);
1839  else
1840  relaxedbd = computeRelaxedUpperbound(scip, infervar, relaxedbd, coef, constant);
1841 
1842  /* try to relax variable bound variable */
1843  SCIP_CALL( relaxVbdvar(scip, startvar, starttype, bdchgidx, relaxedbd) );
1844  }
1845  else
1846  {
1847  SCIP_CALL( resolvePropagation(scip, propdata, startvar, starttype, bdchgidx) );
1848  }
1849 
1850  (*result) = SCIP_SUCCESS;
1851 
1852  return SCIP_OKAY;
1853 }
1854 
1855 /**@} */
1856 
1857 /**@name Callback methods of event handler
1858  *
1859  * @{
1860  */
1861 
1862 /** execution method of bound change event handler */
1863 static
1864 SCIP_DECL_EVENTEXEC(eventExecVbound)
1865 { /*lint --e{715}*/
1866  SCIP_PROPDATA* propdata;
1867  int idx;
1868 
1869  assert(eventhdlr != NULL);
1870 
1871  propdata = (SCIP_PROPDATA*)SCIPeventhdlrGetData(eventhdlr);
1872  assert(propdata != NULL);
1873 
1874  idx = (int) (size_t) eventdata;
1875  assert(idx >= 0);
1876 
1877  SCIPdebugMessage("eventexec (type=%u): try to add sort index %d: %s(%s) to priority queue\n", SCIPeventGetType(event),
1878  idx, indexGetBoundString(propdata->topoorder[idx]),
1879  SCIPvarGetName(propdata->vars[getVarIndex(propdata->topoorder[idx])]));
1880 
1881  if( SCIPeventGetType(event) == SCIP_EVENTTYPE_GUBCHANGED && SCIPvarIsBinary(SCIPeventGetVar(event))
1882  && SCIPeventGetNewbound(event) > 0.5 )
1883  return SCIP_OKAY;
1884 
1885  if( SCIPeventGetType(event) == SCIP_EVENTTYPE_GLBCHANGED && SCIPvarIsBinary(SCIPeventGetVar(event))
1886  && SCIPeventGetNewbound(event) < 0.5 )
1887  return SCIP_OKAY;
1888 
1889  assert(getVarIndex(propdata->topoorder[idx]) < SCIPgetNVars(scip));
1890  assert(SCIPvarGetType(propdata->vars[getVarIndex(propdata->topoorder[idx])]) != SCIP_VARTYPE_BINARY
1891  || (isIndexLowerbound(propdata->topoorder[idx]) == (SCIPeventGetNewbound(event) > 0.5)));
1892 
1893  /* add the bound change to the propagation queue, if it is not already contained */
1894  if( !propdata->inqueue[idx] )
1895  {
1896  SCIP_CALL( SCIPpqueueInsert(propdata->propqueue, (void*)(size_t)(idx + 1)) );
1897  propdata->inqueue[idx] = TRUE;
1898  }
1899  assert(SCIPpqueueNElems(propdata->propqueue) > 0);
1900 
1901  return SCIP_OKAY;
1902 }
1903 
1904 /**@} */
1905 
1906 /**@name Interface methods
1907  *
1908  * @{
1909  */
1910 
1911 /** creates the vbounds propagator and includes it in SCIP */
1912 SCIP_RETCODE SCIPincludePropVbounds(
1913  SCIP* scip /**< SCIP data structure */
1914  )
1915 {
1916  SCIP_PROPDATA* propdata;
1917  SCIP_PROP* prop;
1918 
1919  /* create pseudoobj propagator data */
1920  SCIP_CALL( SCIPallocMemory(scip, &propdata) );
1921 
1922  /* reset propagation data */
1923  resetPropdata(propdata);
1924 
1925  /* include propagator */
1926  SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
1927  propExecVbounds, propdata) );
1928  assert(prop != NULL);
1929 
1930  /* set optional callbacks via setter functions */
1931  SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyVbounds) );
1932  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeVbounds) );
1933  SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolVbounds) );
1934  SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropVbounds) );
1935 
1936  /* include event handler for bound change events */
1937  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &propdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
1938  eventExecVbound, (SCIP_EVENTHDLRDATA*)propdata) );
1939 
1940  SCIP_CALL( SCIPaddBoolParam(scip,
1941  "propagating/"PROP_NAME"/usebdwidening", "should bound widening be used to initialize conflict analysis?",
1942  &propdata->usebdwidening, FALSE, DEFAULT_USEBDWIDENING, NULL, NULL) );
1943  SCIP_CALL( SCIPaddBoolParam(scip,
1944  "propagating/"PROP_NAME"/useimplics", "should implications be propagated?",
1945  &propdata->useimplics, FALSE, DEFAULT_USEIMPLICS, NULL, NULL) );
1946  SCIP_CALL( SCIPaddBoolParam(scip,
1947  "propagating/"PROP_NAME"/usecliques", "should cliques be propagated?",
1948  &propdata->usecliques, FALSE, DEFAULT_USECLIQUES, NULL, NULL) );
1949  SCIP_CALL( SCIPaddBoolParam(scip,
1950  "propagating/"PROP_NAME"/usevbounds", "should vbounds be propagated?",
1951  &propdata->usevbounds, FALSE, DEFAULT_USEVBOUNDS, NULL, NULL) );
1952  SCIP_CALL( SCIPaddBoolParam(scip,
1953  "propagating/"PROP_NAME"/dotoposort", "should the bounds be topologically sorted in advance?",
1954  &propdata->dotoposort, FALSE, DEFAULT_DOTOPOSORT, NULL, NULL) );
1955  SCIP_CALL( SCIPaddBoolParam(scip,
1956  "propagating/"PROP_NAME"/sortcliques", "should cliques be regarded for the topological sort?",
1957  &propdata->sortcliques, FALSE, DEFAULT_SORTCLIQUES, NULL, NULL) );
1958 
1959  return SCIP_OKAY;
1960 }
1961 
1962 /** returns TRUE if the propagator has the status that all variable lower and upper bounds are propgated */
1963 SCIP_Bool SCIPisPropagatedVbounds(
1964  SCIP* scip /**< SCIP data structure */
1965  )
1966 {
1967  SCIP_PROP* prop;
1968  SCIP_PROPDATA* propdata;
1969 
1970  prop = SCIPfindProp(scip, PROP_NAME);
1971  assert(prop != NULL);
1972 
1973  propdata = SCIPpropGetData(prop);
1974  assert(propdata != NULL);
1975 
1976  return (SCIPpqueueNElems(propdata->propqueue) == 0);
1977 }
1978 
1979 /** performs propagation of variables lower and upper bounds */
1980 SCIP_RETCODE SCIPexecPropVbounds(
1981  SCIP* scip, /**< SCIP data structure */
1982  SCIP_Bool force, /**< should domain changes for continuous variables be forced */
1983  SCIP_RESULT* result /**< pointer to store result */
1984  )
1985 {
1986  SCIP_PROP* prop;
1987 
1988  prop = SCIPfindProp(scip, PROP_NAME);
1989  assert(prop != NULL);
1990 
1991  /* perform variable lower and upper bound propagation */
1992  SCIP_CALL( propagateVbounds(scip, prop, force, result) );
1993 
1994  assert((*result) == SCIP_CUTOFF || (*result) == SCIP_DIDNOTRUN
1995  || (*result) == SCIP_DIDNOTFIND || (*result) == SCIP_REDUCEDDOM);
1996 
1997  return SCIP_OKAY;
1998 }
1999 
2000 /**@} */
2001