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