# SCIP

Solving Constraint Integer Programs

prop_vbounds.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not 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) == (SCIPhashmapGetImageInt(propdata->varhashmap, var) > 0));
298
299  return getLbIndex(SCIPhashmapGetImageInt(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) == (SCIPhashmapGetImageInt(propdata->varhashmap, var) > 0));
310
311  return getUbIndex(SCIPhashmapGetImageInt(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( SCIPhashmapInsertInt(propdata->varhashmap, propdata->vars[v], 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  /* coverity[pointer_conversion_loses_bits] */
1881  topopos = ((int)(size_t)SCIPpqueueRemove(propdata->propqueue)) - 1;
1882  assert(propdata->inqueue[topopos]);
1883  startpos = propdata->topoorder[topopos];
1884  assert(startpos >= 0);
1885  propdata->inqueue[topopos] = FALSE;
1886
1887  startvar = vars[getVarIndex(startpos)];
1888  starttype = getBoundtype(startpos);
1889  lower = (starttype == SCIP_BOUNDTYPE_LOWER);
1890  startbound = ( lower ? SCIPvarGetLbLocal(startvar) : SCIPvarGetUbLocal(startvar) );
1891  globalbound = ( lower ? SCIPvarGetLbGlobal(startvar) : SCIPvarGetUbGlobal(startvar));
1892  global = SCIPisEQ(scip, startbound, globalbound);
1893
1894  SCIPdebugMsg(scip, "propagate new %s bound of %g of variable <%s>:\n",
1895  getBoundtypeString(starttype), startbound, SCIPvarGetName(startvar));
1896
1897  /* there should be neither implications nor cliques for non-binary variables */
1898  assert(SCIPvarIsBinary(startvar) || SCIPvarGetNImpls(startvar, lower) == 0);
1899  assert(SCIPvarIsBinary(startvar) || SCIPvarGetNCliques(startvar, lower) == 0);
1900
1901  if( SCIPvarIsBinary(startvar) )
1902  {
1903  /* we only propagate binary variables if the lower bound changed to 1.0 or the upper bound changed to 0.0 */
1904  if( lower != (startbound > 0.5) )
1905  continue;
1906
1907  /* propagate implications */
1908  if( propdata->useimplics )
1909  {
1910  int nimplvars;
1911
1912  /* if the lower bound of the startvar was changed, it was fixed to 1.0, otherwise it was fixed to 0.0;
1913  * get all implications for this varfixing
1914  */
1915  nimplvars = SCIPvarGetNImpls(startvar, lower);
1916
1917  /* if there are implications for the varfixing, propagate them */
1918  if( nimplvars > 0 )
1919  {
1920  SCIP_VAR** implvars;
1921  SCIP_BOUNDTYPE* impltypes;
1922  SCIP_Real* implbounds;
1923  int* implids;
1924
1925  implvars = SCIPvarGetImplVars(startvar, lower);
1926  impltypes = SCIPvarGetImplTypes(startvar, lower);
1927  implbounds = SCIPvarGetImplBounds(startvar, lower);
1928  implids = SCIPvarGetImplIds(startvar, lower);
1929
1930  for( n = 0; n < nimplvars; ++n )
1931  {
1932  /* implication is just a shortcut, so we do not propagate it now,
1933  * because we will propagate the longer way, anyway
1934  */
1935  if( implids[n] < 0 )
1936  continue;
1937
1938  /* it might happen that implications point to inactive variables (normally, those are removed when a
1939  * variable becomes inactive, but in some cases, it cannot be done), we have to ignore these variables
1940  */
1941  if( !SCIPvarIsActive(implvars[n]) )
1942  continue;
1943
1944  if( impltypes[n] == SCIP_BOUNDTYPE_LOWER )
1945  {
1946  SCIP_CALL( tightenVarLb(scip, prop, propdata, implvars[n], implbounds[n], global, startvar,
1947  starttype, force, 0.0, 0.0, FALSE, &nchgbds, result) );
1948  }
1949  else
1950  {
1951  SCIP_CALL( tightenVarUb(scip, prop, propdata, implvars[n], implbounds[n], global, startvar,
1952  starttype, force, 0.0, 0.0, FALSE, &nchgbds, result) );
1953  }
1954
1955  if( *result == SCIP_CUTOFF )
1956  return SCIP_OKAY;
1957  }
1958  }
1959  }
1960
1961  /* propagate cliques */
1962  if( propdata->usecliques )
1963  {
1964  int ncliques;
1965
1966  /* if the lower bound of the startvar was changed, it was fixed to 1.0, otherwise it was fixed to 0.0;
1967  * get all cliques for this varfixing
1968  */
1969  ncliques = SCIPvarGetNCliques(startvar, lower);
1970
1971  /* if there are cliques for the varfixing, propagate them */
1972  if( ncliques > 0 )
1973  {
1974  SCIP_CLIQUE** cliques;
1975  int j;
1976
1977  cliques = SCIPvarGetCliques(startvar, lower);
1978
1979  for( j = 0; j < ncliques; ++j )
1980  {
1981  SCIP_VAR** cliquevars;
1982  SCIP_Bool* cliquevals;
1983  int ncliquevars;
1984
1985  cliquevars = SCIPcliqueGetVars(cliques[j]);
1986  cliquevals = SCIPcliqueGetValues(cliques[j]);
1987  ncliquevars = SCIPcliqueGetNVars(cliques[j]);
1988
1989  /* fix all variables except for the startvar to the value which is not in the clique */
1990  for( n = 0; n < ncliquevars; ++n )
1991  {
1992  if( cliquevars[n] == startvar )
1993  continue;
1994
1995  /* try to tighten the bound */
1996  if( cliquevals[n] )
1997  {
1998  /* unnegated variable is in clique, so it has to be fixed to 0.0 */
1999  SCIP_CALL( tightenVarUb(scip, prop, propdata, cliquevars[n], 0.0, global, startvar, starttype,
2000  force, 0.0, 0.0, FALSE, &nchgbds, result) );
2001  }
2002  else
2003  {
2004  /* negated variable is in clique, so it has to be fixed to 1.0 */
2005  SCIP_CALL( tightenVarLb(scip, prop, propdata, cliquevars[n], 1.0, global, startvar, starttype,
2006  force, 0.0, 0.0, FALSE, &nchgbds, result) );
2007  }
2008  if( *result == SCIP_CUTOFF )
2009  return SCIP_OKAY;
2010  }
2011  }
2012  }
2013  }
2014  }
2015
2016  /* propagate vbounds */
2017  if( propdata->usevbounds )
2018  {
2019  SCIP_VAR* boundedvar;
2020  SCIP_Real newbound;
2021  SCIP_Real coef;
2022  SCIP_Real constant;
2023
2024  /* iterate over all vbounds for the given bound */
2025  for( n = 0; n < propdata->nvbounds[startpos]; ++n )
2026  {
2027  boundedvar = vars[getVarIndex(propdata->vboundboundedidx[startpos][n])];
2028  coef = propdata->vboundcoefs[startpos][n];
2029  constant = propdata->vboundconstants[startpos][n];
2030
2031  /* compute new bound */
2032  newbound = startbound * coef + constant;
2033
2034  /* try to tighten the bound */
2035  if( isIndexLowerbound(propdata->vboundboundedidx[startpos][n]) )
2036  {
2037  SCIP_CALL( tightenVarLb(scip, prop, propdata, boundedvar, newbound, global, startvar, starttype, force,
2038  coef, constant, TRUE, &nchgbds, result) );
2039  }
2040  else
2041  {
2042  SCIP_CALL( tightenVarUb(scip, prop, propdata, boundedvar, newbound, global, startvar, starttype, force,
2043  coef, constant, TRUE, &nchgbds, result) );
2044  }
2045
2046  if( *result == SCIP_CUTOFF )
2047  return SCIP_OKAY;
2048  }
2049  }
2050  }
2051
2052  SCIPdebugMsg(scip, "tightened %d variable bounds\n", nchgbds);
2053
2054  /* set the result depending on whether bound changes were found or not */
2055  if( nchgbds > 0 )
2056  (*result) = SCIP_REDUCEDDOM;
2057  else
2058  (*result) = SCIP_DIDNOTFIND;
2059
2060  return SCIP_OKAY;
2061 }
2062
2063 /**@name Callback methods of propagator
2064  *
2065  * @{
2066  */
2067
2068 /** copy method for propagator plugins (called when SCIP copies plugins) */
2069 static
2070 SCIP_DECL_PROPCOPY(propCopyVbounds)
2071 { /*lint --e{715}*/
2072  assert(scip != NULL);
2073  assert(prop != NULL);
2074  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2075
2076  /* call inclusion method of propagator */
2078
2079  return SCIP_OKAY;
2080 }
2081
2082 /** destructor of propagator to free user data (called when SCIP is exiting) */
2083 static
2084 SCIP_DECL_PROPFREE(propFreeVbounds)
2085 { /*lint --e{715}*/
2086  SCIP_PROPDATA* propdata;
2088  /* free propagator data */
2089  propdata = SCIPpropGetData(prop);
2090
2091  SCIPfreeBlockMemory(scip, &propdata);
2092  SCIPpropSetData(prop, NULL);
2093
2094  return SCIP_OKAY;
2095 }
2096
2097 /** presolving initialization method of propagator (called when presolving is about to begin) */
2098 static
2099 SCIP_DECL_PROPINITPRE(propInitpreVbounds)
2100 { /*lint --e{715}*/
2101  SCIP_PROPDATA* propdata;
2103  propdata = SCIPpropGetData(prop);
2104  assert(propdata != NULL);
2105
2106  propdata->lastpresolncliques = 0;
2107
2108  return SCIP_OKAY;
2109 }
2110
2111 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
2112 static
2113 SCIP_DECL_PROPEXITSOL(propExitsolVbounds)
2114 { /*lint --e{715}*/
2115  SCIP_PROPDATA* propdata;
2116  int v;
2117
2118  propdata = SCIPpropGetData(prop);
2119  assert(propdata != NULL);
2120
2121  /* free data stored for propagation */
2122  if( propdata->initialized )
2123  {
2124  /* drop all variable events */
2125  SCIP_CALL( dropEvents(scip, propdata) );
2126
2127  /* release all variables */
2128  for( v = 0; v < propdata->nbounds; ++v )
2129  {
2130  /* free vbound data */
2131  if( propdata->vboundsize[v] > 0 )
2132  {
2133  SCIPfreeMemoryArray(scip, &propdata->vboundboundedidx[v]);
2134  SCIPfreeMemoryArray(scip, &propdata->vboundcoefs[v]);
2135  SCIPfreeMemoryArray(scip, &propdata->vboundconstants[v]);
2136  }
2137  }
2138
2139  /* free priority queue */
2140  SCIPpqueueFree(&propdata->propqueue);
2141
2142  /* free arrays */
2143  SCIPfreeBlockMemoryArray(scip, &propdata->vboundsize, propdata->nbounds);
2144  SCIPfreeBlockMemoryArray(scip, &propdata->nvbounds, propdata->nbounds);
2145  SCIPfreeBlockMemoryArray(scip, &propdata->vboundconstants, propdata->nbounds);
2146  SCIPfreeBlockMemoryArray(scip, &propdata->vboundcoefs, propdata->nbounds);
2147  SCIPfreeBlockMemoryArray(scip, &propdata->vboundboundedidx, propdata->nbounds);
2148  SCIPfreeBlockMemoryArray(scip, &propdata->inqueue, propdata->nbounds);
2149  SCIPfreeBlockMemoryArray(scip, &propdata->topoorder, propdata->nbounds);
2150
2151  /* free variable array and hashmap */
2152  SCIPhashmapFree(&propdata->varhashmap);
2153  SCIPfreeBlockMemoryArray(scip, &propdata->vars, propdata->nbounds / 2);
2154  }
2155
2156  /* reset propagation data */
2157  resetPropdata(propdata);
2158
2159  return SCIP_OKAY;
2160 }
2161
2162 /** performs Tarjan's algorithm for strongly connected components in the implicitly given directed implication graph
2163  * 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
2164  * where lb(x) means that the lower bound of x should be changed, i.e., that x is fixed to 1, and vice versa.
2165  *
2166  * The algorithm is an iterative version of Tarjans algorithm
2167  * (see https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm)
2168  * with some additional tweaks.
2169  * Each clique x_1 + ... + x_k <= 1 is represented by k(k-1) arcs (lb(x_i),ub(x_j)), j != i.
2170  * This quadratic number can blow up the running time of Tarjan's algorithm, which is linear in the number of
2171  * nodes and arcs of the graph. However, it suffices to consider only k of these arcs during the course of the algorithm.
2172  * 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,
2173  * 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
2174  * that the only arc pointing to an unvisited node is (lb(x_i'),ub(x_i)), all other edges can be disregarded.
2175  * After that, we can disregard the clique for the further search.
2176  * Additionally, we try to identify infeasible fixings for binary variables. Those can be given by a path
2177  * from x=1 to x=0 (or vice versa) or if x=0 (or 1) implies both y=0 and y=1.
2178  */
2179 static
2181  SCIP* scip, /**< SCIP data structure */
2182  int startnode, /**< node to start the depth-first-search */
2183  int* startindex, /**< next index to assign to a processed node */
2184  SCIP_Shortbool* nodeonstack, /**< array to store the whether a each node is on the stack */
2185  int* nodeindex, /**< array to store the dfs index for each node */
2186  int* nodelowlink, /**< array to store the lowlink for each node */
2187  SCIP_Shortbool* nodeinfeasible, /**< array to store whether the fixing of a node was detected to be infeasible */
2188  int* dfsstack, /**< array of size number of nodes to store the stack */
2189  int* predstackidx, /**< for each node on the stack: stack position of its predecessor in the Tarjan search */
2190  int* stacknextclique, /**< array of size number of nodes to store the next clique to be regarded in
2191  * the algorithm for all nodes on the stack */
2192  int* stacknextcliquevar, /**< array of size number of nodes to store the next variable in the next clique to be
2193  * regarded in the algorithm for all nodes on the stack */
2194  int* topoorder, /**< array with reverse (almost) topological ordering of the nodes */
2195  int* nordered, /**< number of ordered nodes (disconnected nodes are disregarded) */
2196  int* cliquefirstentry, /**< node from which a clique was entered for the first time; needed because when
2197  * entering the clique a second time, only the other bound corresponding to this node
2198  * remains to be processed */
2199  int* cliquecurrentexit, /**< for cliques which define an arc on the current path: target node of this arc */
2200  int* sccvars, /**< array with all nontrivial strongly connected components in the graph */
2201  int* sccstarts, /**< start indices of SCCs in sccvars array; one additional entry at the end
2202  * to give length of used part of sccvars array */
2203  int* nsccs, /**< pointer to store number of strongly connected components */
2204  int* infeasnodes, /**< sparse array with node indices of infeasible nodes */
2205  int* ninfeasnodes, /**< pointer to store the number of infeasible nodes */
2206  SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
2207  )
2208 {
2209  SCIP_VAR** vars;
2210  SCIP_VAR* startvar;
2211  SCIP_Bool lower;
2212  int label = *startindex;
2213  int stacksize;
2214  int currstackidx;
2215  int curridx;
2216  int idx;
2217
2218  assert(startnode >= 0);
2219  assert(startnode < 2 * (SCIPgetNVars(scip) - SCIPgetNContVars(scip)));
2220  assert(nodeindex != NULL);
2221  assert(nodeindex[startnode] == 0);
2224  assert(dfsstack != NULL);
2225  assert(stacknextclique != NULL);
2226  assert(infeasible != NULL);
2227
2228  *infeasible = FALSE;
2229
2230  vars = SCIPgetVars(scip);
2231
2232  /* put start node on the stack */
2233  dfsstack[0] = startnode;
2234  stacknextclique[0] = 0;
2235  stacknextcliquevar[0] = 0;
2236  predstackidx[0] = -1;
2237  stacksize = 1;
2238  idx = -1;
2239  currstackidx = 0;
2240 #ifdef DEBUG_TARJAN
2241  SCIPdebugMsg(scip, "put %s(%s) on stack[%d]\n", indexGetBoundString(dfsstack[stacksize-1]),
2242  SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize-1])]), stacksize-1);
2243 #endif
2244
2245  /* we run until no more bounds indices are on the stack, i.e., no further nodes are connected to the startnode */
2246  while( stacksize > 0 )
2247  {
2248  SCIP_CLIQUE** cliques;
2249  int ncliques;
2250  SCIP_Bool found;
2251  int clqidx = -1;
2252  int j;
2253  int i;
2254
2255  /* get next node from stack */
2256  curridx = dfsstack[currstackidx];
2258
2259  startvar = vars[getVarIndex(curridx)];
2260  lower = isIndexLowerbound(curridx);
2261
2263  if( nodeindex[curridx] == 0 )
2264  {
2265  assert(!nodeonstack[curridx]);
2266  assert(stacknextclique[currstackidx] == 0);
2267  assert(stacknextcliquevar[currstackidx] == 0);
2268  nodeonstack[curridx] = 1;
2269  nodeindex[curridx] = label;
2271  ++label;
2272
2273 #ifdef DEBUG_TARJAN
2274  {
2275  ncliques = SCIPvarGetNCliques(startvar, lower);
2276  cliques = SCIPvarGetCliques(startvar, lower);
2277
2278  SCIPdebugMsg(scip, "variable %s(%s) has %d cliques\n", indexGetBoundString(curridx), SCIPvarGetName(startvar),
2279  ncliques);
2280  for( j = 0; j < ncliques; ++j )
2281  {
2282  SCIP_VAR** cliquevars;
2283  SCIP_Bool* cliquevals;
2284  int ncliquevars;
2285
2286  clqidx = SCIPcliqueGetIndex(cliques[j]);
2287  cliquevars = SCIPcliqueGetVars(cliques[j]);
2288  cliquevals = SCIPcliqueGetValues(cliques[j]);
2289  ncliquevars = SCIPcliqueGetNVars(cliques[j]);
2290
2291  SCIPdebugMsg(scip, "clique %d [%d vars, stacksize: %d]...\n", clqidx, ncliquevars, stacksize);
2292  for( int v = 0; v < ncliquevars; ++v )
2293  SCIPdebugMsgPrint(scip, " %s<%s>", cliquevals[v] ? "" : "~", SCIPvarGetName(cliquevars[v]));
2294  SCIPdebugMsgPrint(scip, "\n");
2295  }
2296  }
2297 #endif
2298  }
2299  /* we just did a backtrack and still need to investigate some outgoing edges of the node;
2300  * however, we should have investigated some of the outgoing edges before
2301  */
2302  else
2303  {
2304  assert(stacknextclique[currstackidx] > 0 || stacknextcliquevar[currstackidx] > 0);
2305  assert(nodeindex[curridx] < label);
2306  }
2307  assert(stacknextclique[currstackidx] >= 0);
2308
2309  ncliques = SCIPvarGetNCliques(startvar, lower);
2310  cliques = SCIPvarGetCliques(startvar, lower);
2311  found = FALSE;
2312
2313  /* iterate over all not yet handled cliques and search for an unvisited node */
2314  for( j = stacknextclique[currstackidx]; j < ncliques; ++j )
2315  {
2316  SCIP_VAR** cliquevars;
2317  SCIP_Bool* cliquevals;
2318  int ncliquevars;
2319
2320  clqidx = SCIPcliqueGetIndex(cliques[j]);
2321  cliquevars = SCIPcliqueGetVars(cliques[j]);
2322  cliquevals = SCIPcliqueGetValues(cliques[j]);
2323  ncliquevars = SCIPcliqueGetNVars(cliques[j]);
2324
2325  /* we did not look at this clique before from the current node, i.e., we did not backtrack now from another
2326  * node which was reached via this clique
2327  */
2328  if( stacknextcliquevar[currstackidx] == 0 )
2329  {
2330 #ifdef DEBUG_TARJAN
2331  SCIPdebugMsg(scip, "clique %d [%d vars, stacksize: %d]...\n", clqidx, ncliquevars, stacksize);
2332  for( int v = 0; v < ncliquevars; ++v )
2333  SCIPdebugMsgPrint(scip, " %s<%s>", cliquevals[v] ? "" : "~", SCIPvarGetName(cliquevars[v]));
2334  SCIPdebugMsgPrint(scip, "\n");
2335 #endif
2336  /* the clique was not entered before, remember that we first entered it from curridx
2337  * (add 1 to distinguish it from 0 initialization)
2338  */
2339  if( cliquefirstentry[clqidx] == 0 )
2340  {
2341  cliquefirstentry[clqidx] = curridx + 1;
2342  }
2343  else
2344  {
2345  int cliquefirstentryidx = (cliquefirstentry[clqidx] > 0 ? cliquefirstentry[clqidx] : -cliquefirstentry[clqidx]) - 1;
2346  int infeasnode = -1;
2347  assert(cliquefirstentryidx != curridx);
2348
2349  /* The node by which we entered the clique the first time is still on the stack, so there is a
2350  * way from that node to the node by which we are entering the clique right now.
2351  * Since these two assignments together violate the clique and the second assignment is implied by the first,
2352  * the first one is infeasible
2353  */
2354  if( nodeonstack[cliquefirstentryidx] && !nodeinfeasible[cliquefirstentryidx] )
2355  {
2356  SCIPdebugMsg(scip, "infeasible assignment (1): %s(%s)\n", indexGetBoundString(cliquefirstentryidx),
2357  SCIPvarGetName(vars[getVarIndex(cliquefirstentryidx)]));
2358  infeasnode = cliquefirstentryidx;
2359  }
2360  /* the first entry point of the clique was also implied by the current startnode, so this node implies
2361  * two variables in the clique and is therefore infeasible
2362  */
2363  else if( nodeindex[cliquefirstentryidx] >= *startindex && !nodeinfeasible[startnode] )
2364  {
2365  SCIPdebugMsg(scip, "infeasible assignment (2): %s(%s)\n", indexGetBoundString(startnode),
2366  SCIPvarGetName(vars[getVarIndex(startnode)]));
2367  infeasnode = startnode;
2368  }
2369
2370  /* we identified an infeasibility */
2371  if( infeasnode >= 0 )
2372  {
2373  /* both values are invalid for the variable, the whole problem is infeasible */
2374  if( nodeinfeasible[getOtherBoundIndex(infeasnode)] )
2375  {
2376  *infeasible = TRUE;
2377  return SCIP_OKAY;
2378  }
2379  infeasnodes[*ninfeasnodes] = infeasnode;
2380  nodeinfeasible[infeasnode] = TRUE;
2381  ++(*ninfeasnodes);
2382
2383  /* the last node by which the clique was exited is not the negation of the current node and still on
2384  * the stack: update the lowlink of the current node
2385  */
2386  if( cliquecurrentexit[clqidx] > 0
2387  && curridx != getOtherBoundIndex(cliquecurrentexit[clqidx] - 1)
2388  && nodeonstack[cliquecurrentexit[clqidx] - 1]
2389  && nodeindex[cliquecurrentexit[clqidx] - 1] < nodelowlink[curridx] )
2390  {
2391  nodelowlink[curridx] = nodeindex[cliquecurrentexit[clqidx] - 1];
2392  }
2393  }
2394  /* clique is entered for the second time; there is only one edge left to investigate, namely the edge to
2395  * the negation of the first entry point
2396  */
2397  else if( cliquefirstentry[clqidx] > 0 )
2398  {
2399 #ifdef DEBUG_TARJAN
2400  SCIPdebugMsg(scip, "entering clique %d a second time\n", clqidx);
2401 #endif
2402  idx = getOtherBoundIndex(cliquefirstentry[clqidx] - 1);
2403
2404  /* node was not investigated yet, we found the next node to process */
2405  if( nodeindex[idx] == 0 )
2406  found = TRUE;
2407  /* update lowlink if the node is on the stack */
2408  else if( nodeonstack[idx] && nodeindex[idx] < nodelowlink[curridx] )
2410
2411  /* cliquefirstentry[clqidx] < 0 means that we entered the clique at least two times already */
2412  cliquefirstentry[clqidx] = -cliquefirstentry[clqidx];
2413  }
2414  else
2415  {
2416 #ifdef DEBUG_TARJAN
2417  SCIPdebugMsg(scip, "skip clique %d: visited more than twice already!\n", clqidx);
2418 #endif
2419  }
2420  stacknextcliquevar[currstackidx] = ncliquevars;
2421  }
2422  }
2423
2424  /* iterate over variables in the clique; start where we stopped last time */
2425  for( i = stacknextcliquevar[currstackidx]; i < ncliquevars; ++i )
2426  {
2427  if( cliquevars[i] == startvar )
2428  continue;
2429
2430  if( !SCIPvarIsActive(cliquevars[i]) )
2431  continue;
2432
2433  if( cliquevals[i] )
2434  idx = getUbIndex(SCIPvarGetProbindex(cliquevars[i]));
2435  else
2436  idx = getLbIndex(SCIPvarGetProbindex(cliquevars[i]));
2437  assert(idx >= 0);
2438
2439  /* break when the first unvisited node is reached */
2440  if( nodeindex[idx] == 0 )
2441  {
2442  assert(!nodeonstack[idx]);
2443  stacknextcliquevar[currstackidx] = i + 1;
2444  found = TRUE;
2445  break;
2446  }
2447  else if( nodeonstack[idx] && nodeindex[idx] < nodelowlink[curridx] )
2448  {
2450  }
2451  }
2452  if( found )
2453  {
2454  if( stacknextcliquevar[currstackidx] < ncliquevars )
2455  stacknextclique[currstackidx] = j;
2456  else
2457  {
2458  stacknextclique[currstackidx] = j + 1;
2459  stacknextcliquevar[currstackidx] = 0;
2460  }
2461  break;
2462  }
2463  else
2464  {
2465  assert(i == ncliquevars);
2466  stacknextclique[currstackidx] = j + 1;
2467  stacknextcliquevar[currstackidx] = 0;
2468  }
2469  }
2470  assert(found || j == ncliques);
2471  assert(found || stacknextclique[currstackidx] == ncliques);
2472
2473  /* we stopped because we found an unhandled node and not because we reached the end of the list */
2474  if( found )
2475  {
2476  int otheridx = getOtherBoundIndex(idx);
2477  int infeasnode = -1;
2478
2479  assert(idx >= 0);
2480  assert(!nodeonstack[idx]);
2481  assert(j < ncliques);
2482  assert(clqidx >= 0);
2483
2484  /* the negated node corresponding to the next node is already on the stack -> the negated assignment is
2485  * infeasible
2486  */
2487  if( nodeonstack[otheridx] && !nodeinfeasible[otheridx] )
2488  {
2489  SCIPdebugMsg(scip, "infeasible assignment (3): %s(%s)\n", indexGetBoundString(otheridx),
2490  SCIPvarGetName(vars[getVarIndex(otheridx)]));
2491  infeasnode = otheridx;
2492  }
2493  /* the negated node corresponding to the next node was reached from the same startnode -> the startnode is
2494  * infeasible
2495  */
2496  else if( nodeindex[otheridx] >= *startindex && !nodeinfeasible[startnode] )
2497  {
2498  SCIPdebugMsg(scip, "infeasible assignment (4): %s(%s)\n", indexGetBoundString(startnode),
2499  SCIPvarGetName(vars[getVarIndex(startnode)]));
2500  infeasnode = startnode;
2501  }
2502  /* treat infeasible case */
2503  if( infeasnode >= 0 )
2504  {
2505  if( nodeinfeasible[getOtherBoundIndex(infeasnode)] )
2506  {
2507  *infeasible = TRUE;
2508  return SCIP_OKAY;
2509  }
2510  infeasnodes[*ninfeasnodes] = infeasnode;
2511  nodeinfeasible[infeasnode] = TRUE;
2512  ++(*ninfeasnodes);
2513  }
2514
2515  SCIPdebugMsg(scip, "clique: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
2516  indexGetBoundString(idx), SCIPvarGetName(vars[getVarIndex(idx)]));
2517
2518  /* put the adjacent node onto the stack */
2519  dfsstack[stacksize] = idx;
2520  stacknextclique[stacksize] = 0;
2521  stacknextcliquevar[stacksize] = 0;
2522  cliquecurrentexit[clqidx] = idx + 1;
2523  predstackidx[stacksize] = currstackidx;
2524  currstackidx = stacksize;
2525  stacksize++;
2526  assert(stacksize <= 2 * (SCIPgetNVars(scip) - SCIPgetNContVars(scip)));
2527
2528 #ifdef DEBUG_TARJAN
2529  SCIPdebugMsg(scip, "put %s(%s) on stack[%d]\n", indexGetBoundString(dfsstack[stacksize-1]), SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize-1])]), stacksize-1);
2530 #endif
2531  /* restart while loop, get next index from stack */
2532  continue;
2533  }
2534  assert(stacknextclique[currstackidx] == ncliques);
2535
2536  /* no node with a smaller index can be reached from this node -> it is the root of a SCC,
2537  * consisting of all nodes above it on the stack, including the node itself
2538  */
2539  if( nodelowlink[curridx] == nodeindex[curridx] )
2540  {
2541  /* we are only interested in SCCs with more than one node */
2542  if( dfsstack[stacksize-1] != curridx )
2543  {
2544  int sccvarspos = sccstarts[*nsccs];
2545
2546  SCIPdebugMsg(scip, "SCC:");
2547
2548  /* store the SCC in sccvars */
2549  do{
2550  stacksize--;
2551  idx = dfsstack[stacksize];
2552  nodeonstack[idx] = 0;
2553  sccvars[sccvarspos] = idx;
2554  ++sccvarspos;
2555  SCIPdebugMsgPrint(scip, " %s(%s)", indexGetBoundString(idx), SCIPvarGetName(vars[getVarIndex(idx)]));
2556 #ifdef DEBUG_TARJAN
2557  SCIPdebugMsg(scip, "remove %s(%s) from stack[%d]\n", indexGetBoundString(dfsstack[stacksize]), SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize])]), stacksize);
2558 #endif
2559  }
2560  while( idx != curridx );
2561  SCIPdebugMsgPrint(scip, "\n");
2562  ++(*nsccs);
2563  sccstarts[*nsccs] = sccvarspos;
2564  }
2565  /* trivial SCC: remove the single node from the stack, but don't store it as a SCC */
2566  else
2567  {
2568  stacksize--;
2569 #ifdef DEBUG_TARJAN
2570  SCIPdebugMsg(scip, "remove %s(%s) from stack[%d]\n", indexGetBoundString(dfsstack[stacksize]), SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize])]), stacksize);
2571 #endif
2572  idx = dfsstack[stacksize];
2573  nodeonstack[idx] = 0;
2574  assert(nodeindex[idx] > 0);
2575  }
2576  }
2577  /* in a pure dfs, the node would now leave the stack, add it to the array of nodes in reverse topological order */
2578  if( topoorder != NULL && (stacksize > 0 || label > *startindex + 1) )
2579  {
2580  topoorder[*nordered] = curridx;
2581  ++(*nordered);
2582  }
2583
2584  /* the current node was handled, backtrack */
2585  if( stacksize > 0 )
2586  {
2587  idx = dfsstack[predstackidx[currstackidx]];
2589  currstackidx = predstackidx[currstackidx];
2590  }
2591  }
2592
2593  *startindex = label;
2594
2595  return SCIP_OKAY;
2596 }
2597
2598
2599 /** apply fixings and aggregations found by the clique graph analysis */
2600 static
2602  SCIP* scip, /**< SCIP data structure */
2603  SCIP_VAR** vars, /**< array of active variables */
2604  int* infeasnodes, /**< sparse array with node indices of infeasible nodes */
2605  int ninfeasnodes, /**< pointer to store the number of infeasible nodes */
2606  SCIP_Shortbool* nodeinfeasible, /**< array to store whether the fixing of a node was detected to be infeasible */
2607  int* sccvars, /**< array with all nontrivial strongly connected components in the graph */
2608  int* sccstarts, /**< start indices of SCCs in sccvars array; one additional entry at the end
2609  * to give length of used part of sccvars array */
2610  int nsccs, /**< pointer to store number of strongly connected components */
2611  SCIP_Bool* infeasible, /**< pointer to store whether an infeasibility was detected */
2612  int* nfixedvars, /**< pointer to number of fixed variables, increment when fixing another one */
2613  int* naggrvars, /**< pointer to number of aggregated variables, increment when aggregating another one */
2614  SCIP_RESULT* result /**< pointer to store result of the call */
2615  )
2616 {
2617  int i = 0;
2618
2619  assert(scip != NULL);
2620  assert(vars != NULL);
2621  assert(infeasible != NULL);
2622
2623  /* for all infeasible node: fix variable to the other bound */
2624  if( !(*infeasible) && ninfeasnodes > 0 )
2625  {
2626  for( i = 0; i < ninfeasnodes; ++i )
2627  {
2628  SCIP_VAR* var = vars[getVarIndex(infeasnodes[i])];
2629  SCIP_Bool lower = isIndexLowerbound(infeasnodes[i]);
2630  SCIP_Bool fixed;
2631
2632  assert(nodeinfeasible[infeasnodes[i]]);
2633  nodeinfeasible[infeasnodes[i]] = FALSE;
2634
2635  SCIP_CALL( SCIPfixVar(scip, var, lower ? 0.0 : 1.0, infeasible, &fixed) );
2636
2637  SCIPdebugMsg(scip, "fix <%s>[%d] to %g: inf=%d, fixed=%d\n",
2638  SCIPvarGetName(var), infeasnodes[i], lower ? 0.0 : 1.0, *infeasible, fixed);
2639
2640  /* fixing was infeasible */
2641  if( *infeasible )
2642  break;
2643
2644  /* increase fixing counter and update result pointer */
2645  if( fixed )
2646  {
2647  *result = SCIP_SUCCESS;
2648  ++(*nfixedvars);
2649  }
2650  }
2651  }
2652  assert((*infeasible) || i == ninfeasnodes);
2653
2654  /* clear clean buffer array (if we did not enter the block above or stopped early due to an infeasibility) */
2655  for( ; i < ninfeasnodes; ++i )
2656  {
2657  assert(nodeinfeasible[infeasnodes[i]]);
2658  nodeinfeasible[infeasnodes[i]] = FALSE;
2659  }
2660
2661  if( !(*infeasible) && nsccs > 0 )
2662  {
2663  /* for each strongly connected component: aggregate all variables to the first one */
2664  for( i = 0; i < nsccs; ++i )
2665  {
2666  SCIP_VAR* startvar;
2667  SCIP_Bool lower;
2668  SCIP_Bool aggregated;
2669  SCIP_Bool redundant;
2670  int v;
2671
2672  assert(sccstarts[i] < sccstarts[i+1] - 1);
2673
2674  /* get variable and boundtype for first node of the SCC */
2675  startvar = vars[getVarIndex(sccvars[sccstarts[i]])];
2676  lower = isIndexLowerbound(sccvars[sccstarts[i]]);
2677
2678  for( v = sccstarts[i] + 1; v < sccstarts[i+1]; ++v )
2679  {
2680  /* aggregate variables: if both nodes represent the same bound, we have x=1 <=> y=1,
2681  * and thus aggregate x - y = 0; if both represent different bounds we have
2682  * x=1 <=> y=0, so we aggregate x + y = 1
2683  */
2684  SCIP_CALL( SCIPaggregateVars(scip, startvar, vars[getVarIndex(sccvars[v])], 1.0,
2685  lower == isIndexLowerbound(sccvars[v]) ? -1.0 : 1.0,
2686  lower == isIndexLowerbound(sccvars[v]) ? 0.0 : 1.0,
2687  infeasible, &redundant, &aggregated) );
2688
2689  SCIPdebugMsg(scip, "aggregate <%s> + %g <%s> = %g: inf=%d, red=%d, aggr=%d\n",
2690  SCIPvarGetName(startvar), lower == isIndexLowerbound(sccvars[v]) ? -1.0 : 1.0,
2691  SCIPvarGetName(vars[getVarIndex(sccvars[v])]), lower == isIndexLowerbound(sccvars[v]) ? 0.0 : 1.0,
2692  *infeasible, redundant, aggregated);
2693
2694  /* aggregation was infeasible */
2695  if( *infeasible )
2696  break;
2697
2698  /* increase aggregation counter and update result pointer */
2699  if( aggregated )
2700  {
2701  ++(*naggrvars);
2702  *result = SCIP_SUCCESS;
2703  }
2704  }
2705  }
2706  }
2707
2708  return SCIP_OKAY;
2709 }
2710
2711
2712
2713 /** presolving method of propagator: search for strongly connected components in the implication graph and
2714  * aggregate all variables within a component; additionally, identifies infeasible variable assignments
2715  * 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
2716  * The identification of such assignments depends on the order in which variable bounds are processed;
2717  * therefore, we are doing a second run with the bounds processed in (almost) topological order.
2718  */
2719 static
2720 SCIP_DECL_PROPPRESOL(propPresolVbounds)
2721 { /*lint --e{715}*/
2722  SCIP_PROPDATA* propdata;
2723  SCIP_VAR** tmpvars;
2724  SCIP_VAR** vars;
2725  int* dfsstack;
2726  int* stacknextclique;
2727  int* stacknextcliquevar;
2728  int* nodeindex;
2730  int* predstackidx;
2731  int* cliquefirstentry;
2732  int* cliquecurrentexit;
2733  int* topoorder;
2734  int* sccvars;
2735  int* sccstarts;
2736  int* infeasnodes;
2737  SCIP_Shortbool* nodeonstack;
2738  SCIP_Shortbool* nodeinfeasible;
2739  int ninfeasnodes;
2740  int nsccs;
2741  int nbounds;
2742  int nbinvars;
2743  int ncliques;
2744  int startindex = 1;
2745  int nordered = 0;
2746  int i;
2747  SCIP_Bool infeasible = FALSE;
2748
2749  assert(scip != NULL);
2750
2751  propdata = SCIPpropGetData(prop);
2752  assert(propdata != NULL);
2753
2754  ncliques = SCIPgetNCliques(scip);
2755
2756  *result = SCIP_DIDNOTRUN;
2757
2758  if( ncliques < 2 )
2759  return SCIP_OKAY;
2760
2761  /* too many cliques for medium presolving */
2762  if( presoltiming == SCIP_PRESOLTIMING_MEDIUM && ncliques > propdata->maxcliquesmedium * SCIPgetNBinVars(scip) )
2763  return SCIP_OKAY;
2764
2765  /* too many cliques for exhaustive presolving */
2766  if( ncliques > propdata->maxcliquesexhaustive * SCIPgetNBinVars(scip) )
2767  return SCIP_OKAY;
2768
2769  /* only run if enough new cliques were created since the last successful call */
2770  if( SCIPgetNCliquesCreated(scip) < (1.0 + propdata->minnewcliques) * propdata->lastpresolncliques )
2771  return SCIP_OKAY;
2772
2773  *result = SCIP_DIDNOTFIND;
2774
2775  nbinvars = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
2776  nbounds = 2 * nbinvars;
2777
2778  /* cleanup cliques, stop if this proved infeasibility already */
2779  SCIP_CALL( SCIPcleanupCliques(scip, &infeasible) );
2780
2781  if( infeasible )
2782  {
2783  *result = SCIP_CUTOFF;
2784  return SCIP_OKAY;
2785  }
2786
2787  tmpvars = SCIPgetVars(scip);
2788
2789  /* duplicate variable array; needed to get the fixings right later */
2790  SCIP_CALL( SCIPduplicateBufferArray(scip, &vars, tmpvars, nbinvars) );
2791
2792  SCIP_CALL( SCIPallocBufferArray(scip, &dfsstack, nbounds) );
2793  SCIP_CALL( SCIPallocBufferArray(scip, &stacknextclique, nbounds) );
2794  SCIP_CALL( SCIPallocBufferArray(scip, &stacknextcliquevar, nbounds) );
2795  SCIP_CALL( SCIPallocBufferArray(scip, &predstackidx, nbounds) );
2796  SCIP_CALL( SCIPallocBufferArray(scip, &topoorder, nbounds) );
2797  SCIP_CALL( SCIPallocBufferArray(scip, &sccvars, nbounds) );
2798  SCIP_CALL( SCIPallocBufferArray(scip, &sccstarts, nbinvars + 1) );
2799  SCIP_CALL( SCIPallocBufferArray(scip, &infeasnodes, nbounds) );
2800  SCIP_CALL( SCIPallocClearBufferArray(scip, &nodeindex, nbounds) );
2801  SCIP_CALL( SCIPallocClearBufferArray(scip, &nodelowlink, nbounds) );
2802  SCIP_CALL( SCIPallocClearBufferArray(scip, &cliquefirstentry, ncliques) );
2803  SCIP_CALL( SCIPallocClearBufferArray(scip, &cliquecurrentexit, ncliques) );
2804  SCIP_CALL( SCIPallocClearBufferArray(scip, &nodeonstack, nbounds) );
2805  SCIP_CALL( SCIPallocCleanBufferArray(scip, &nodeinfeasible, nbounds) );
2806  sccstarts[0] = 0;
2807  nsccs = 0;
2808  ninfeasnodes = 0;
2809
2810  /* while there are unvisited nodes, run Tarjan's algorithm starting from one of these nodes */
2811  for( i = 0; i < nbounds && !infeasible; ++i )
2812  {
2813  if( nodeindex[i] == 0 )
2814  {
2815  SCIP_CALL( tarjan(scip, i, &startindex, nodeonstack, nodeindex, nodelowlink, nodeinfeasible,
2816  dfsstack, predstackidx, stacknextclique, stacknextcliquevar, topoorder, &nordered,
2817  cliquefirstentry, cliquecurrentexit, sccvars, sccstarts, &nsccs,
2818  infeasnodes, &ninfeasnodes, &infeasible) );
2819  }
2820  }
2821  assert(nordered <= nbounds);
2822
2823  /* aggregate all variables within a SCC and fix all variables for which one bounds was proven infeasible */
2824  if( ninfeasnodes > 0 || nsccs > 0 )
2825  {
2826  SCIP_CALL( applyFixingsAndAggregations(scip, vars, infeasnodes, ninfeasnodes, nodeinfeasible,
2827  sccvars, sccstarts, nsccs, &infeasible, nfixedvars, naggrvars, result) );
2828  }
2829
2830  /* second round, now with topological order! */
2831  if( !infeasible && nordered > 0 )
2832  {
2833  SCIP_VAR** vars2;
2834  int nbounds2;
2835
2836  assert(nordered > 1);
2837
2838  /* we already fixed or aggregated some variables in the first run, so we better clean up the cliques */
2839  if( *result == SCIP_SUCCESS )
2840  {
2841  SCIP_CALL( SCIPcleanupCliques(scip, &infeasible) );
2842
2843  if( infeasible )
2844  goto TERMINATE;
2845  }
2846
2847  nbounds2 = 2 * (SCIPgetNVars(scip) - SCIPgetNContVars(scip));
2848  ncliques = SCIPgetNCliques(scip);
2849
2850  SCIP_CALL( SCIPduplicateBufferArray(scip, &vars2, tmpvars, nbounds2/2) );
2851
2852  /* clear arrays that should be initialized to 0 */
2853  BMSclearMemoryArray(nodeonstack, nbounds2);
2854  BMSclearMemoryArray(nodeindex, nbounds2);
2856  BMSclearMemoryArray(cliquefirstentry, ncliques);
2857  BMSclearMemoryArray(cliquecurrentexit, ncliques);
2858  sccstarts[0] = 0;
2859  nsccs = 0;
2860  ninfeasnodes = 0;
2861  startindex = 1;
2862
2863  /* while there are unvisited nodes, run Tarjan's algorithm starting from one of these nodes */
2864  for( i = nordered - 1; i >= 0 && !infeasible; --i )
2865  {
2866  int varindex;
2867  int startpos;
2868  assert(topoorder[i] < nbounds);
2869
2870  /* variable of next node in topological order */
2871  varindex = SCIPvarGetProbindex(vars[getVarIndex(topoorder[i])]);
2872
2873  /* variable was not fixed after the first run */
2874  if( varindex >= 0 )
2875  {
2876  startpos = isIndexLowerbound(topoorder[i]) ? getLbIndex(varindex) : getUbIndex(varindex);
2877  if( nodeindex[startpos] == 0 )
2878  {
2879  SCIP_CALL( tarjan(scip, startpos, &startindex, nodeonstack, nodeindex, nodelowlink, nodeinfeasible,
2880  dfsstack, predstackidx, stacknextclique, stacknextcliquevar, NULL, NULL,
2881  cliquefirstentry, cliquecurrentexit, sccvars, sccstarts, &nsccs,
2882  infeasnodes, &ninfeasnodes, &infeasible) );
2883  }
2884  }
2885  }
2886
2887  /* aggregate all variables within a SCC and fix all variables for which one bounds was proven infeasible */
2888  if( ninfeasnodes > 0 || nsccs > 0 )
2889  {
2890  SCIP_CALL( applyFixingsAndAggregations(scip, vars2, infeasnodes, ninfeasnodes, nodeinfeasible,
2891  sccvars, sccstarts, nsccs, &infeasible, nfixedvars, naggrvars, result) );
2892  }
2893
2894  SCIPfreeBufferArray(scip, &vars2);
2895  }
2896
2897  TERMINATE:
2898  if( infeasible )
2899  *result = SCIP_CUTOFF;
2900 #ifndef NDEBUG
2901  for( i = 0; i < nbounds; ++i )
2902  {
2903  assert(nodeinfeasible[i] == FALSE);
2904  }
2905 #endif
2906  SCIPfreeCleanBufferArray(scip, &nodeinfeasible);
2907  SCIPfreeBufferArray(scip, &nodeonstack);
2908  SCIPfreeBufferArray(scip, &cliquecurrentexit);
2909  SCIPfreeBufferArray(scip, &cliquefirstentry);
2911  SCIPfreeBufferArray(scip, &nodeindex);
2912  SCIPfreeBufferArray(scip, &infeasnodes);
2913  SCIPfreeBufferArray(scip, &sccstarts);
2914  SCIPfreeBufferArray(scip, &sccvars);
2915  SCIPfreeBufferArray(scip, &topoorder);
2916  SCIPfreeBufferArray(scip, &predstackidx);
2917  SCIPfreeBufferArray(scip, &stacknextcliquevar);
2918  SCIPfreeBufferArray(scip, &stacknextclique);
2919  SCIPfreeBufferArray(scip, &dfsstack);
2920  SCIPfreeBufferArray(scip, &vars);
2921
2922  propdata->lastpresolncliques = SCIPgetNCliquesCreated(scip);
2923
2924  return SCIP_OKAY;
2925 }
2926
2927
2928
2929 /** execution method of propagator */
2930 static
2931 SCIP_DECL_PROPEXEC(propExecVbounds)
2932 { /*lint --e{715}*/
2933  *result = SCIP_DIDNOTRUN;
2935  /* perform variable lower and upper bound propagation */
2936  SCIP_CALL( propagateVbounds(scip, prop, FALSE, result) );
2937
2938  assert((*result) == SCIP_CUTOFF || (*result) == SCIP_DIDNOTRUN
2939  || (*result) == SCIP_DIDNOTFIND || (*result) == SCIP_REDUCEDDOM);
2940
2941  return SCIP_OKAY;
2942 }
2943
2944 /** propagation conflict resolving method of propagator */
2945 static
2946 SCIP_DECL_PROPRESPROP(propRespropVbounds)
2947 { /*lint --e{715}*/
2948  SCIP_PROPDATA* propdata;
2949  SCIP_VAR** vars;
2950  SCIP_VAR* startvar;
2951  SCIP_BOUNDTYPE starttype;
2952  int pos;
2953
2954  propdata = SCIPpropGetData(prop);
2955  assert(propdata != NULL);
2956
2957  starttype = inferInfoGetBoundtype(intToInferInfo(inferinfo));
2958  pos = inferInfoGetPos(intToInferInfo(inferinfo));
2959  assert(pos >= 0);
2960  assert(pos < propdata->nbounds);
2961
2962  vars = propdata->vars;
2963  assert(vars != NULL);
2964  startvar = vars[getVarIndex(pos)];
2965  assert(startvar != NULL);
2966  assert(startvar != infervar);
2967
2968  SCIPdebugMsg(scip, "explain %s bound change of variable <%s>\n",
2969  getBoundtypeString(boundtype), SCIPvarGetName(infervar));
2970
2971  if( !SCIPvarIsBinary(startvar) && propdata->usebdwidening )
2972  {
2973  int* vboundboundedidx;
2974  SCIP_Real constant;
2975  SCIP_Real coef;
2976  int inferidx;
2977  int nvbounds;
2978  int b;
2979
2980  nvbounds = propdata->nvbounds[pos];
2981  vboundboundedidx = propdata->vboundboundedidx[pos];
2982
2983  inferidx = boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, infervar) : varGetUbIndex(propdata, infervar);
2984  assert(inferidx >= 0);
2985
2986  for( b = 0; b < nvbounds; ++b )
2987  {
2988  if( vboundboundedidx[b] == inferidx )
2989  break;
2990  }
2991  assert(b < nvbounds);
2992
2993  coef = propdata->vboundcoefs[pos][b];
2994  constant = propdata->vboundconstants[pos][b];
2995  assert(!SCIPisZero(scip, coef));
2996
2997  /* compute the relaxed bound which is sufficient to propagate the inference bound of given variable */
2998  if( boundtype == SCIP_BOUNDTYPE_LOWER )
2999  relaxedbd = computeRelaxedLowerbound(scip, infervar, relaxedbd, coef, constant);
3000  else
3001  relaxedbd = computeRelaxedUpperbound(scip, infervar, relaxedbd, coef, constant);
3002
3003  /* try to relax variable bound variable */
3004  SCIP_CALL( relaxVbdvar(scip, startvar, starttype, bdchgidx, relaxedbd) );
3005  }
3006  else
3007  {
3008  SCIP_CALL( resolvePropagation(scip, propdata, startvar, starttype, bdchgidx) );
3009  }
3010
3011  (*result) = SCIP_SUCCESS;
3012
3013  return SCIP_OKAY;
3014 }
3015
3016 /**@} */
3017
3018 /**@name Callback methods of event handler
3019  *
3020  * @{
3021  */
3022
3023 /** execution method of bound change event handler */
3024 static
3025 SCIP_DECL_EVENTEXEC(eventExecVbound)
3026 { /*lint --e{715}*/
3027  SCIP_PROPDATA* propdata;
3028  int idx;
3029
3030  assert(eventhdlr != NULL);
3031
3032  propdata = (SCIP_PROPDATA*)SCIPeventhdlrGetData(eventhdlr);
3033  assert(propdata != NULL);
3034
3035  /* coverity[pointer_conversion_loses_bits] */
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_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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:97
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
void * SCIPpqueueRemove(SCIP_PQUEUE *pqueue)
Definition: misc.c:1307
SCIP_Real SCIPfeastol(SCIP *scip)
#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
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2167
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
#define getVarIndex(idx)
Definition: prop_vbounds.c:159
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
#define NULL
Definition: def.h:253
#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)
void SCIPpqueueFree(SCIP_PQUEUE **pqueue)
Definition: misc.c:1259
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
Definition: implics.c:3343
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
public methods for SCIP parameter handling
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1994
SCIP_RETCODE SCIPsetPropInitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITPRE((*propinitpre)))
Definition: scip_prop.c:237
SCIP_RETCODE SCIPcleanupCliques(SCIP *scip, SCIP_Bool *infeasible)
Definition: scip_var.c:7442
static SCIP_Real computeRelaxedLowerbound(SCIP *scip, SCIP_VAR *var, SCIP_Real inferlb, SCIP_Real coef, SCIP_Real constant)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5121
static SCIP_RETCODE dropEvents(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_vbounds.c:396
#define DEFAULT_USECLIQUES
Definition: prop_vbounds.c:131
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:5809
static SCIP_RETCODE analyzeConflictUpperbound(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *infervar, SCIP_Real inferub, SCIP_VAR *vbdvar, SCIP_BOUNDTYPE boundtype, SCIP_Real coef, SCIP_Real constant, SCIP_Bool canwide)
public methods for memory management
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:113
public methods for implications, variable bounds, and cliques
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:69
#define PROP_PRESOLTIMING
Definition: prop_vbounds.c:108
public methods for conflict handler plugins and conflict analysis
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5237
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
Definition: type_event.h:138
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3009
#define getLbIndex(idx)
Definition: prop_vbounds.c:157
SCIP_EXPORT SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16918
SCIP_EXPORT SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17647
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1987
int SCIPcliqueGetIndex(SCIP_CLIQUE *clique)
Definition: implics.c:3379
#define FALSE
Definition: def.h:73
#define DEFAULT_SORTCLIQUES
Definition: prop_vbounds.c:134
#define DEFAULT_MAXCLIQUESMEDIUM
Definition: prop_vbounds.c:137
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:5923
SCIP_EXPORT SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16903
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_Bool SCIPcliqueIsEquation(SCIP_CLIQUE *clique)
Definition: implics.c:3399
int SCIPpqueueNElems(SCIP_PQUEUE *pqueue)
Definition: misc.c:1362
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:423
#define SCIP_EVENTTYPE_GLBCHANGED
Definition: type_event.h:61
static SCIP_DECL_PROPINITPRE(propInitpreVbounds)
SCIP_EXPORT SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17025
public methods for problem variables
SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub)
Definition: scip_var.c:4583
static SCIP_DECL_PROPCOPY(propCopyVbounds)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:47
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_EXPORT SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17676
static SCIP_BOUNDTYPE inferInfoGetBoundtype(INFERINFO inferinfo)
Definition: prop_vbounds.c:252
SCIP_RETCODE SCIPanalyzeConflict(SCIP *scip, int validdepth, SCIP_Bool *success)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:119
static SCIP_RETCODE analyzeConflictLowerbound(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *infervar, SCIP_Real inferlb, SCIP_VAR *vbdvar, SCIP_BOUNDTYPE boundtype, SCIP_Real coef, SCIP_Real constant, SCIP_Bool canwide)
SCIP_RETCODE SCIPaddConflictRelaxedLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedlb)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:135
#define isIndexLowerbound(idx)
Definition: prop_vbounds.c:161
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
Definition: prop.c:789
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
public methods for SCIP variables
static int inferInfoToInt(INFERINFO inferinfo)
Definition: prop_vbounds.c:243
#define SCIPdebugMsgPrint
Definition: scip_message.h:70
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Real SCIPgetConflictVarUb(SCIP *scip, SCIP_VAR *var)
#define VISITED
Definition: prop_vbounds.c:785
SCIP_EXPORT SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
Definition: var.c:17556
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:141
static SCIP_RETCODE tightenVarLb(SCIP *scip, SCIP_PROP *prop, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_Real newlb, SCIP_Bool global, SCIP_VAR *vbdvar, SCIP_BOUNDTYPE boundtype, SCIP_Bool force, SCIP_Real coef, SCIP_Real constant, SCIP_Bool canwide, int *nchgbds, SCIP_RESULT *result)
public methods for numerical tolerances
SCIP_RETCODE SCIPincludePropVbounds(SCIP *scip)
#define DEFAULT_USEIMPLICS
Definition: prop_vbounds.c:130
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3098
public methods for the branch-and-bound tree
static SCIP_Real computeRelaxedUpperbound(SCIP *scip, SCIP_VAR *var, SCIP_Real inferub, SCIP_Real coef, SCIP_Real constant)
SCIP_Real SCIPgetConflictVarLb(SCIP *scip, SCIP_VAR *var)
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:324
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:129
variable upper and lower bound propagator
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3240
#define PROP_DESC
Definition: prop_vbounds.c:101
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:92
#define SCIP_PRESOLTIMING_MEDIUM
Definition: type_timing.h:44
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16738
SCIP_EXPORT SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16929
SCIP_EXPORT int * SCIPvarGetImplIds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17692
#define SCIPerrorMessage
Definition: pub_message.h:45
static SCIP_DECL_EVENTEXEC(eventExecVbound)
#define indexGetBoundString(idx)
Definition: prop_vbounds.c:164
SCIP_EXPORT int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17630
public methods for event handler plugins and event handlers
SCIP_RETCODE SCIPexecPropVbounds(SCIP *scip, SCIP_Bool force, SCIP_RESULT *result)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1942
SCIP_Real SCIPgetHugeValue(SCIP *scip)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:47
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip_tree.c:99
#define INITMEMSIZE
Definition: prop_vbounds.c:442
SCIP_EXPORT SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition: var.c:17608
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:931
#define SCIPreallocMemoryArray(scip, ptr, newnum)
Definition: scip_mem.h:59
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:155
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:157
int SCIPgetNCliques(SCIP *scip)
Definition: scip_var.c:7485
#define SCIP_Shortbool
Definition: def.h:78
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:365
SCIP_EXPORT int SCIPvarGetNVubs(SCIP_VAR *var)
Definition: var.c:17586
#define SCIP_EVENTTYPE_LBTIGHTENED
Definition: type_event.h:63
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip_prop.c:221
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:995
static INFERINFO intToInferInfo(int i)
Definition: prop_vbounds.c:230
SCIP_Real SCIPeventGetNewbound(SCIP_EVENT *event)
Definition: event.c:1198
#define DEFAULT_DOTOPOSORT
Definition: prop_vbounds.c:133
#define PROP_TIMING
Definition: prop_vbounds.c:102
static SCIP_DECL_PROPEXEC(propExecVbounds)
static SCIP_DECL_PROPEXITSOL(propExitsolVbounds)
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)))
Definition: misc.c:1234
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:111
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:129
public data structures and miscellaneous methods
SCIP_EXPORT SCIP_Bool SCIPvarHasImplic(SCIP_VAR *var, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype)
Definition: var.c:10643
#define SCIP_Bool
Definition: def.h:70
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:390
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1066
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2891
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17362
#define EVENTHDLR_NAME
Definition: prop_vbounds.c:119
#define getBoundtype(idx)
Definition: prop_vbounds.c:160
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:223
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
Definition: implics.c:3355
SCIP_PROP * SCIPfindProp(SCIP *scip, const char *name)
Definition: scip_prop.c:319
#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
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 SCIPaddConflictRelaxedUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedub)
int SCIPgetNCliquesCreated(SCIP *scip)
Definition: scip_var.c:7512
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8180
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition: type_event.h:65
SCIP_EXPORT SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17715
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17408
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:94
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:129
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2130
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip_prop.c:302
#define SCIP_REAL_MAX
Definition: def.h:165
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
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17418
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:779
#define PROP_DELAY
Definition: prop_vbounds.c:105
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
#define ACTIVE
Definition: prop_vbounds.c:786
static INFERINFO getInferInfo(int pos, SCIP_BOUNDTYPE boundtype)
Definition: prop_vbounds.c:272
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_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17352
#define PROP_PRIORITY
Definition: prop_vbounds.c:103
SCIP_EXPORT SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
Definition: var.c:17566
#define getOtherBoundIndex(idx)
Definition: prop_vbounds.c:165
public methods for message output
SCIP_EXPORT SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
Definition: var.c:17576
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2925
#define SCIP_Real
Definition: def.h:164
#define getBoundtypeString(type)
Definition: prop_vbounds.c:163
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:133
static SCIP_DECL_PROPPRESOL(propPresolVbounds)
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:38
#define DEFAULT_USEVBOUNDS
Definition: prop_vbounds.c:132
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for message handling
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_prop.c:269
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6260
SCIP_EXPORT SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17662
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
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2032
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: scip_var.c:1796
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:344
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
Definition: event.c:1018
SCIP_EXPORT int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17045
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
Definition: implics.c:3333
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:120
static SCIP_DECL_PROPRESPROP(propRespropVbounds)
SCIP_EXPORT int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17704
#define SCIP_EVENTTYPE_GUBCHANGED
Definition: type_event.h:62
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:104
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:8305
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:355
#define SCIPABORT()
Definition: def.h:337
public methods for global and local (sub)problems
SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb)
Definition: scip_var.c:4551
SCIP_EXPORT SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
Definition: var.c:17618
SCIP_Bool SCIPisPropagatedVbounds(SCIP *scip)
SCIP_EXPORT SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition: var.c:17598
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6140
SCIP_EXPORT int SCIPvarGetNVlbs(SCIP_VAR *var)
Definition: var.c:17544
public methods for propagators
static SCIP_RETCODE topologicalSort(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool *infeasible)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
uint64_t SCIP_EVENTTYPE
Definition: type_event.h:134
#define getUbIndex(idx)
Definition: prop_vbounds.c:158
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1280
memory allocation routines
static SCIP_DECL_PROPFREE(propFreeVbounds)