Scippy

SCIP

Solving Constraint Integer Programs

var.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file var.c
17  * @brief methods for problem variables
18  * @author Tobias Achterberg
19  * @author Timo Berthold
20  * @author Gerald Gamrath
21  * @author Stefan Heinz
22  * @author Marc Pfetsch
23  * @author Michael Winkler
24  * @author Kati Wolter
25  * @author Stefan Vigerske
26  *
27  * @todo Possibly implement the access of bounds of multi-aggregated variables by accessing the
28  * corresponding linear constraint if it exists. This seems to require some work, since the linear
29  * constraint has to be stored. Moreover, it has even to be created in case the original constraint
30  * was deleted after multi-aggregation, but the bounds of the multi-aggregated variable should be
31  * changed. This has to be done with care in order to not loose the performance gains of
32  * multi-aggregation.
33  */
34 
35 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
36 
37 #include <stdlib.h>
38 #include <assert.h>
39 #include <string.h>
40 
41 #include "scip/def.h"
42 #include "scip/prop.h"
43 #include "scip/relax.h"
44 #include "scip/var.h"
45 #include "scip/cons.h"
46 #include "scip/event.h"
47 #include "scip/history.h"
48 #include "scip/implics.h"
49 #include "scip/lp.h"
50 #include "scip/primal.h"
51 #include "scip/prob.h"
52 #include "scip/set.h"
53 #include "scip/sol.h"
54 #include "scip/stat.h"
55 #include "scip/tree.h"
56 #include "scip/reopt.h"
57 
58 #include "scip/debug.h"
59 
60 #include "scip/pub_message.h"
61 #include "scip/pub_history.h"
62 
63 #define MAXIMPLSCLOSURE 100 /**< maximal number of descendants of implied variable for building closure
64  * in implication graph */
65 #define MAXABSVBCOEF 1e+5 /**< maximal absolute coefficient in variable bounds added due to implications */
66 
67 /*
68  * hole, holelist, and domain methods
69  */
70 
71 /** creates a new holelist element */
72 static
74  SCIP_HOLELIST** holelist, /**< pointer to holelist to create */
75  BMS_BLKMEM* blkmem, /**< block memory for target holelist */
76  SCIP_SET* set, /**< global SCIP settings */
77  SCIP_Real left, /**< left bound of open interval in new hole */
78  SCIP_Real right /**< right bound of open interval in new hole */
79  )
80 {
81  assert(holelist != NULL);
82  assert(blkmem != NULL);
83  assert(SCIPsetIsLT(set, left, right));
84 
85  SCIPsetDebugMsg(set, "create hole list element (%.15g,%.15g) in blkmem %p\n", left, right, (void*)blkmem);
86 
87  SCIP_ALLOC( BMSallocBlockMemory(blkmem, holelist) );
88  (*holelist)->hole.left = left;
89  (*holelist)->hole.right = right;
90  (*holelist)->next = NULL;
91 
92  return SCIP_OKAY;
93 }
94 
95 /** frees all elements in the holelist */
96 static
97 void holelistFree(
98  SCIP_HOLELIST** holelist, /**< pointer to holelist to free */
99  BMS_BLKMEM* blkmem /**< block memory for target holelist */
100  )
101 {
102  assert(holelist != NULL);
103  assert(blkmem != NULL);
104 
105  while( *holelist != NULL )
106  {
107  SCIP_HOLELIST* next;
108 
109  SCIPdebugMessage("free hole list element (%.15g,%.15g) in blkmem %p\n",
110  (*holelist)->hole.left, (*holelist)->hole.right, (void*)blkmem);
111 
112  next = (*holelist)->next;
113  BMSfreeBlockMemory(blkmem, holelist);
114  assert(*holelist == NULL);
115 
116  *holelist = next;
117  }
118  assert(*holelist == NULL);
119 }
120 
121 /** duplicates a list of holes */
122 static
124  SCIP_HOLELIST** target, /**< pointer to target holelist */
125  BMS_BLKMEM* blkmem, /**< block memory for target holelist */
126  SCIP_SET* set, /**< global SCIP settings */
127  SCIP_HOLELIST* source /**< holelist to duplicate */
128  )
129 {
130  assert(target != NULL);
131 
132  while( source != NULL )
133  {
134  assert(source->next == NULL || SCIPsetIsGE(set, source->next->hole.left, source->hole.right));
135  SCIP_CALL( holelistCreate(target, blkmem, set, source->hole.left, source->hole.right) );
136  source = source->next;
137  target = &(*target)->next;
138  }
139 
140  return SCIP_OKAY;
141 }
142 
143 /** adds a hole to the domain */
144 static
146  SCIP_DOM* dom, /**< domain to add hole to */
147  BMS_BLKMEM* blkmem, /**< block memory */
148  SCIP_SET* set, /**< global SCIP settings */
149  SCIP_Real left, /**< left bound of open interval in new hole */
150  SCIP_Real right, /**< right bound of open interval in new hole */
151  SCIP_Bool* added /**< pointer to store whether the hole was added (variable didn't had that hole before), or NULL */
152  )
153 {
154  SCIP_HOLELIST** insertpos;
155  SCIP_HOLELIST* next;
156 
157  assert(dom != NULL);
158  assert(added != NULL);
159 
160  /* search for the position of the new hole */
161  insertpos = &dom->holelist;
162  while( *insertpos != NULL && (*insertpos)->hole.left < left )
163  insertpos = &(*insertpos)->next;
164 
165  /* check if new hole already exists in the hole list or is a sub hole of an existing one */
166  if( *insertpos != NULL && (*insertpos)->hole.left == left && (*insertpos)->hole.right >= right ) /*lint !e777 */
167  {
168  SCIPsetDebugMsg(set, "new hole (%.15g,%.15g) is redundant through known hole (%.15g,%.15g)\n",
169  left, right, (*insertpos)->hole.left, (*insertpos)->hole.right);
170  *added = FALSE;
171  return SCIP_OKAY;
172  }
173 
174  /* add hole */
175  *added = TRUE;
176 
177  next = *insertpos;
178  SCIP_CALL( holelistCreate(insertpos, blkmem, set, left, right) );
179  (*insertpos)->next = next;
180 
181  return SCIP_OKAY;
182 }
183 
184 /** merges overlapping holes into single holes, computes and moves lower and upper bound, respectively */
185 /**@todo the domMerge() method is currently called if a lower or an upper bound locally or globally changed; this could
186  * be more efficient if performed with the knowledge if it was a lower or an upper bound which triggered this
187  * merge */
188 static
189 void domMerge(
190  SCIP_DOM* dom, /**< domain to merge */
191  BMS_BLKMEM* blkmem, /**< block memory */
192  SCIP_SET* set, /**< global SCIP settings */
193  SCIP_Real* newlb, /**< pointer to store new lower bound */
194  SCIP_Real* newub /**< pointer to store new upper bound */
195  )
196 {
197  SCIP_HOLELIST** holelistptr;
198  SCIP_HOLELIST** lastnextptr;
199  SCIP_Real* lastrightptr;
200 
201  assert(dom != NULL);
202  assert(SCIPsetIsLE(set, dom->lb, dom->ub));
203 
204 #ifndef NDEBUG
205  {
206  /* check if the holelist is sorted w.r.t. to the left interval bounds */
207  SCIP_Real lastleft;
208 
209  holelistptr = &dom->holelist;
210 
211  lastleft = -SCIPsetInfinity(set);
212 
213  while( *holelistptr != NULL )
214  {
215  if( (*holelistptr)->next != NULL )
216  {
217  assert( SCIPsetIsLE(set, lastleft, (*holelistptr)->hole.left) );
218  lastleft = (*holelistptr)->hole.left;
219  }
220 
221  holelistptr = &(*holelistptr)->next;
222  }
223  }
224 #endif
225 
226  SCIPsetDebugMsg(set, "merge hole list\n");
227 
228  holelistptr = &dom->holelist;
229  lastrightptr = &dom->lb; /* lower bound is the right bound of the hole (-infinity,lb) */
230  lastnextptr = holelistptr;
231 
232  while( *holelistptr != NULL )
233  {
234  SCIPsetDebugMsg(set, "check hole (%.15g,%.15g) last right interval was <%.15g>\n", (*holelistptr)->hole.left, (*holelistptr)->hole.right, *lastrightptr);
235 
236  /* check that the hole is not empty */
237  assert(SCIPsetIsLT(set, (*holelistptr)->hole.left, (*holelistptr)->hole.right));
238 
239  if( SCIPsetIsGE(set, (*holelistptr)->hole.left, dom->ub) )
240  {
241  /* the remaining holes start behind the upper bound: remove them */
242  SCIPsetDebugMsg(set, "remove remaining hole since upper bound <%.15g> is less then the left hand side of the current hole\n", dom->ub);
243  holelistFree(holelistptr, blkmem);
244  assert(*holelistptr == NULL);
245 
246  /* unlink this hole from the previous hole */
247  *lastnextptr = NULL;
248  }
249  else if( SCIPsetIsGT(set, (*holelistptr)->hole.right, dom->ub) )
250  {
251  /* the hole overlaps the upper bound: decrease upper bound, remove this hole and all remaining holes */
252  SCIPsetDebugMsg(set, "upper bound <%.15g> lays in current hole; store new upper bound and remove this and all remaining holes\n", dom->ub);
253 
254  assert(SCIPsetIsLT(set, (*holelistptr)->hole.left, dom->ub));
255 
256  /* adjust upper bound */
257  dom->ub = (*holelistptr)->hole.left;
258 
259  if(newub != NULL )
260  *newub = (*holelistptr)->hole.left;
261 
262  /* remove remaining hole list */
263  holelistFree(holelistptr, blkmem);
264  assert(*holelistptr == NULL);
265 
266  /* unlink this hole from the previous hole */
267  *lastnextptr = NULL;
268  }
269  else if( SCIPsetIsGT(set, *lastrightptr, (*holelistptr)->hole.left) )
270  {
271  /* the right bound of the last hole is greater than the left bound of this hole: increase the right bound of
272  * the last hole, delete this hole */
273  SCIP_HOLELIST* nextholelist;
274 
275  if( SCIPsetIsEQ(set, *lastrightptr, dom->lb ) )
276  {
277  /* the reason for the overlap results from the lower bound hole (-infinity,lb); therefore, we can increase
278  * the lower bound */
279  SCIPsetDebugMsg(set, "lower bound <%.15g> lays in current hole; store new lower bound and remove hole\n", dom->lb);
280  *lastrightptr = MAX(*lastrightptr, (*holelistptr)->hole.right);
281 
282  /* adjust lower bound */
283  dom->lb = *lastrightptr;
284 
285  if(newlb != NULL )
286  *newlb = *lastrightptr;
287  }
288  else
289  {
290  SCIPsetDebugMsg(set, "current hole overlaps with the previous one (...,%.15g); merge to (...,%.15g)\n",
291  *lastrightptr, MAX(*lastrightptr, (*holelistptr)->hole.right) );
292  *lastrightptr = MAX(*lastrightptr, (*holelistptr)->hole.right);
293  }
294  nextholelist = (*holelistptr)->next;
295  (*holelistptr)->next = NULL;
296  holelistFree(holelistptr, blkmem);
297 
298  /* connect the linked list after removing the hole */
299  *lastnextptr = nextholelist;
300 
301  /* get next hole */
302  *holelistptr = nextholelist;
303  }
304  else
305  {
306  /* the holes do not overlap: update lastholelist and lastrightptr */
307  lastrightptr = &(*holelistptr)->hole.right;
308  lastnextptr = &(*holelistptr)->next;
309 
310  /* get next hole */
311  holelistptr = &(*holelistptr)->next;
312  }
313  }
314 
315 #ifndef NDEBUG
316  {
317  /* check that holes are merged */
318  SCIP_Real lastright;
319 
320  lastright = dom->lb; /* lower bound is the right bound of the hole (-infinity,lb) */
321  holelistptr = &dom->holelist;
322 
323  while( *holelistptr != NULL )
324  {
325  /* check the the last right interval is smaller or equal to the current left interval (none overlapping) */
326  assert( SCIPsetIsLE(set, lastright, (*holelistptr)->hole.left) );
327 
328  /* check the hole property (check that the hole is not empty) */
329  assert( SCIPsetIsLT(set, (*holelistptr)->hole.left, (*holelistptr)->hole.right) );
330  lastright = (*holelistptr)->hole.right;
331 
332  /* get next hole */
333  holelistptr = &(*holelistptr)->next;
334  }
335 
336  /* check the the last right interval is smaller or equal to the upper bound (none overlapping) */
337  assert( SCIPsetIsLE(set, lastright, dom->ub) );
338  }
339 #endif
340 }
341 
342 /*
343  * domain change methods
344  */
345 
346 /** ensures, that bound change info array for lower bound changes can store at least num entries */
347 static
349  SCIP_VAR* var, /**< problem variable */
350  BMS_BLKMEM* blkmem, /**< block memory */
351  SCIP_SET* set, /**< global SCIP settings */
352  int num /**< minimum number of entries to store */
353  )
354 {
355  assert(var != NULL);
356  assert(var->nlbchginfos <= var->lbchginfossize);
357  assert(SCIPvarIsTransformed(var));
358 
359  if( num > var->lbchginfossize )
360  {
361  int newsize;
362 
363  newsize = SCIPsetCalcMemGrowSize(set, num);
364  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &var->lbchginfos, var->lbchginfossize, newsize) );
365  var->lbchginfossize = newsize;
366  }
367  assert(num <= var->lbchginfossize);
368 
369  return SCIP_OKAY;
370 }
371 
372 /** ensures, that bound change info array for upper bound changes can store at least num entries */
373 static
375  SCIP_VAR* var, /**< problem variable */
376  BMS_BLKMEM* blkmem, /**< block memory */
377  SCIP_SET* set, /**< global SCIP settings */
378  int num /**< minimum number of entries to store */
379  )
380 {
381  assert(var != NULL);
382  assert(var->nubchginfos <= var->ubchginfossize);
383  assert(SCIPvarIsTransformed(var));
384 
385  if( num > var->ubchginfossize )
386  {
387  int newsize;
388 
389  newsize = SCIPsetCalcMemGrowSize(set, num);
390  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &var->ubchginfos, var->ubchginfossize, newsize) );
391  var->ubchginfossize = newsize;
392  }
393  assert(num <= var->ubchginfossize);
394 
395  return SCIP_OKAY;
396 }
397 
398 /** adds domain change info to the variable's lower bound change info array */
399 static
401  SCIP_VAR* var, /**< problem variable */
402  BMS_BLKMEM* blkmem, /**< block memory */
403  SCIP_SET* set, /**< global SCIP settings */
404  SCIP_Real oldbound, /**< old value for bound */
405  SCIP_Real newbound, /**< new value for bound */
406  int depth, /**< depth in the tree, where the bound change takes place */
407  int pos, /**< position of the bound change in its bound change array */
408  SCIP_VAR* infervar, /**< variable that was changed (parent of var, or var itself) */
409  SCIP_CONS* infercons, /**< constraint that infered this bound change, or NULL */
410  SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
411  int inferinfo, /**< user information for inference to help resolving the conflict */
412  SCIP_BOUNDTYPE inferboundtype, /**< type of bound for inference var: lower or upper bound */
413  SCIP_BOUNDCHGTYPE boundchgtype /**< bound change type: branching decision or infered bound change */
414  )
415 {
416  assert(var != NULL);
417  assert(SCIPsetIsLT(set, oldbound, newbound));
418  assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPsetIsFeasIntegral(set, oldbound));
419  assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPsetIsFeasIntegral(set, newbound));
420  assert(!SCIPvarIsBinary(var) || SCIPsetIsEQ(set, oldbound, 0.0));
421  assert(!SCIPvarIsBinary(var) || SCIPsetIsEQ(set, newbound, 1.0));
422  assert(boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING || infervar != NULL);
423  assert((boundchgtype == SCIP_BOUNDCHGTYPE_CONSINFER) == (infercons != NULL));
424  assert(boundchgtype == SCIP_BOUNDCHGTYPE_PROPINFER || inferprop == NULL);
425 
426  SCIPsetDebugMsg(set, "adding lower bound change info to var <%s>[%g,%g]: depth=%d, pos=%d, infer%s=<%s>, inferinfo=%d, %g -> %g\n",
427  SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, depth, pos, infercons != NULL ? "cons" : "prop",
428  infercons != NULL ? SCIPconsGetName(infercons) : (inferprop != NULL ? SCIPpropGetName(inferprop) : "-"), inferinfo,
429  oldbound, newbound);
430 
431  SCIP_CALL( varEnsureLbchginfosSize(var, blkmem, set, var->nlbchginfos+1) );
432  var->lbchginfos[var->nlbchginfos].oldbound = oldbound;
433  var->lbchginfos[var->nlbchginfos].newbound = newbound;
434  var->lbchginfos[var->nlbchginfos].var = var;
435  var->lbchginfos[var->nlbchginfos].bdchgidx.depth = depth;
436  var->lbchginfos[var->nlbchginfos].bdchgidx.pos = pos;
437  var->lbchginfos[var->nlbchginfos].pos = var->nlbchginfos; /*lint !e732*/
438  var->lbchginfos[var->nlbchginfos].boundchgtype = boundchgtype; /*lint !e641*/
439  var->lbchginfos[var->nlbchginfos].boundtype = SCIP_BOUNDTYPE_LOWER; /*lint !e641*/
440  var->lbchginfos[var->nlbchginfos].redundant = FALSE;
441  var->lbchginfos[var->nlbchginfos].inferboundtype = inferboundtype; /*lint !e641*/
442  var->lbchginfos[var->nlbchginfos].inferencedata.var = infervar;
443  var->lbchginfos[var->nlbchginfos].inferencedata.info = inferinfo;
444 
445  /**@note The "pos" data member of the bound change info has a size of 27 bits */
446  assert(var->nlbchginfos < 1 << 27);
447 
448  switch( boundchgtype )
449  {
451  break;
453  assert(infercons != NULL);
454  var->lbchginfos[var->nlbchginfos].inferencedata.reason.cons = infercons;
455  break;
457  var->lbchginfos[var->nlbchginfos].inferencedata.reason.prop = inferprop;
458  break;
459  default:
460  SCIPerrorMessage("invalid bound change type %d\n", boundchgtype);
461  return SCIP_INVALIDDATA;
462  }
463 
464  var->nlbchginfos++;
465 
466  assert(var->nlbchginfos < 2
468  &var->lbchginfos[var->nlbchginfos-1].bdchgidx));
469 
470  return SCIP_OKAY;
471 }
472 
473 /** adds domain change info to the variable's upper bound change info array */
474 static
476  SCIP_VAR* var, /**< problem variable */
477  BMS_BLKMEM* blkmem, /**< block memory */
478  SCIP_SET* set, /**< global SCIP settings */
479  SCIP_Real oldbound, /**< old value for bound */
480  SCIP_Real newbound, /**< new value for bound */
481  int depth, /**< depth in the tree, where the bound change takes place */
482  int pos, /**< position of the bound change in its bound change array */
483  SCIP_VAR* infervar, /**< variable that was changed (parent of var, or var itself) */
484  SCIP_CONS* infercons, /**< constraint that infered this bound change, or NULL */
485  SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
486  int inferinfo, /**< user information for inference to help resolving the conflict */
487  SCIP_BOUNDTYPE inferboundtype, /**< type of bound for inference var: lower or upper bound */
488  SCIP_BOUNDCHGTYPE boundchgtype /**< bound change type: branching decision or infered bound change */
489  )
490 {
491  assert(var != NULL);
492  assert(SCIPsetIsGT(set, oldbound, newbound));
493  assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPsetIsFeasIntegral(set, oldbound));
494  assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPsetIsFeasIntegral(set, newbound));
495  assert(!SCIPvarIsBinary(var) || SCIPsetIsEQ(set, oldbound, 1.0));
496  assert(!SCIPvarIsBinary(var) || SCIPsetIsEQ(set, newbound, 0.0));
497  assert(boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING || infervar != NULL);
498  assert((boundchgtype == SCIP_BOUNDCHGTYPE_CONSINFER) == (infercons != NULL));
499  assert(boundchgtype == SCIP_BOUNDCHGTYPE_PROPINFER || inferprop == NULL);
500 
501  SCIPsetDebugMsg(set, "adding upper bound change info to var <%s>[%g,%g]: depth=%d, pos=%d, infer%s=<%s>, inferinfo=%d, %g -> %g\n",
502  SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, depth, pos, infercons != NULL ? "cons" : "prop",
503  infercons != NULL ? SCIPconsGetName(infercons) : (inferprop != NULL ? SCIPpropGetName(inferprop) : "-"), inferinfo,
504  oldbound, newbound);
505 
506  SCIP_CALL( varEnsureUbchginfosSize(var, blkmem, set, var->nubchginfos+1) );
507  var->ubchginfos[var->nubchginfos].oldbound = oldbound;
508  var->ubchginfos[var->nubchginfos].newbound = newbound;
509  var->ubchginfos[var->nubchginfos].var = var;
510  var->ubchginfos[var->nubchginfos].bdchgidx.depth = depth;
511  var->ubchginfos[var->nubchginfos].bdchgidx.pos = pos;
512  var->ubchginfos[var->nubchginfos].pos = var->nubchginfos; /*lint !e732*/
513  var->ubchginfos[var->nubchginfos].boundchgtype = boundchgtype; /*lint !e641*/
514  var->ubchginfos[var->nubchginfos].boundtype = SCIP_BOUNDTYPE_UPPER; /*lint !e641*/
515  var->ubchginfos[var->nubchginfos].redundant = FALSE;
516  var->ubchginfos[var->nubchginfos].inferboundtype = inferboundtype; /*lint !e641*/
517  var->ubchginfos[var->nubchginfos].inferencedata.var = infervar;
518  var->ubchginfos[var->nubchginfos].inferencedata.info = inferinfo;
519 
520  /**@note The "pos" data member of the bound change info has a size of 27 bits */
521  assert(var->nubchginfos < 1 << 27);
522 
523  switch( boundchgtype )
524  {
526  break;
528  assert(infercons != NULL);
529  var->ubchginfos[var->nubchginfos].inferencedata.reason.cons = infercons;
530  break;
532  var->ubchginfos[var->nubchginfos].inferencedata.reason.prop = inferprop;
533  break;
534  default:
535  SCIPerrorMessage("invalid bound change type %d\n", boundchgtype);
536  return SCIP_INVALIDDATA;
537  }
538 
539  var->nubchginfos++;
540 
541  assert(var->nubchginfos < 2
543  &var->ubchginfos[var->nubchginfos-1].bdchgidx));
544 
545  return SCIP_OKAY;
546 }
547 
548 /** applies single bound change */
550  SCIP_BOUNDCHG* boundchg, /**< bound change to apply */
551  BMS_BLKMEM* blkmem, /**< block memory */
552  SCIP_SET* set, /**< global SCIP settings */
553  SCIP_STAT* stat, /**< problem statistics */
554  SCIP_LP* lp, /**< current LP data */
555  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
556  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
557  int depth, /**< depth in the tree, where the bound change takes place */
558  int pos, /**< position of the bound change in its bound change array */
559  SCIP_Bool* cutoff /**< pointer to store whether an infeasible bound change was detected */
560  )
561 {
562  SCIP_VAR* var;
563 
564  assert(boundchg != NULL);
565  assert(stat != NULL);
566  assert(depth > 0);
567  assert(pos >= 0);
568  assert(cutoff != NULL);
569 
570  *cutoff = FALSE;
571 
572  /* ignore redundant bound changes */
573  if( boundchg->redundant )
574  return SCIP_OKAY;
575 
576  var = boundchg->var;
577  assert(var != NULL);
579  assert(!SCIPvarIsIntegral(var) || SCIPsetIsIntegral(set, boundchg->newbound));
580 
581  /* apply bound change */
582  switch( boundchg->boundtype )
583  {
585  /* check, if the bound change is still active (could be replaced by inference due to repropagation of higher node) */
586  if( SCIPsetIsGT(set, boundchg->newbound, var->locdom.lb) )
587  {
588  if( SCIPsetIsLE(set, boundchg->newbound, var->locdom.ub) )
589  {
590  /* add the bound change info to the variable's bound change info array */
591  switch( boundchg->boundchgtype )
592  {
594  SCIPsetDebugMsg(set, " -> branching: new lower bound of <%s>[%g,%g]: %g\n",
595  SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, boundchg->newbound);
596  SCIP_CALL( varAddLbchginfo(var, blkmem, set, var->locdom.lb, boundchg->newbound, depth, pos,
598  stat->lastbranchvar = var;
600  stat->lastbranchvalue = boundchg->newbound;
601  break;
602 
604  assert(boundchg->data.inferencedata.reason.cons != NULL);
605  SCIPsetDebugMsg(set, " -> constraint <%s> inference: new lower bound of <%s>[%g,%g]: %g\n",
606  SCIPconsGetName(boundchg->data.inferencedata.reason.cons),
607  SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, boundchg->newbound);
608  SCIP_CALL( varAddLbchginfo(var, blkmem, set, var->locdom.lb, boundchg->newbound, depth, pos,
609  boundchg->data.inferencedata.var, boundchg->data.inferencedata.reason.cons, NULL,
610  boundchg->data.inferencedata.info,
612  break;
613 
615  SCIPsetDebugMsg(set, " -> propagator <%s> inference: new lower bound of <%s>[%g,%g]: %g\n",
616  boundchg->data.inferencedata.reason.prop != NULL
617  ? SCIPpropGetName(boundchg->data.inferencedata.reason.prop) : "-",
618  SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, boundchg->newbound);
619  SCIP_CALL( varAddLbchginfo(var, blkmem, set, var->locdom.lb, boundchg->newbound, depth, pos,
620  boundchg->data.inferencedata.var, NULL, boundchg->data.inferencedata.reason.prop,
621  boundchg->data.inferencedata.info,
623  break;
624 
625  default:
626  SCIPerrorMessage("invalid bound change type %d\n", boundchg->boundchgtype);
627  return SCIP_INVALIDDATA;
628  }
629 
630  /* change local bound of variable */
631  SCIP_CALL( SCIPvarChgLbLocal(var, blkmem, set, stat, lp, branchcand, eventqueue, boundchg->newbound) );
632  }
633  else
634  {
635  SCIPsetDebugMsg(set, " -> cutoff: new lower bound of <%s>[%g,%g]: %g\n",
636  SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, boundchg->newbound);
637  *cutoff = TRUE;
638  boundchg->redundant = TRUE; /* bound change has not entered the lbchginfos array of the variable! */
639  }
640  }
641  else
642  {
643  /* mark bound change to be inactive */
644  SCIPsetDebugMsg(set, " -> inactive %s: new lower bound of <%s>[%g,%g]: %g\n",
645  (SCIP_BOUNDCHGTYPE)boundchg->boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING ? "branching" : "inference",
646  SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, boundchg->newbound);
647  boundchg->redundant = TRUE;
648  }
649  break;
650 
652  /* check, if the bound change is still active (could be replaced by inference due to repropagation of higher node) */
653  if( SCIPsetIsLT(set, boundchg->newbound, var->locdom.ub) )
654  {
655  if( SCIPsetIsGE(set, boundchg->newbound, var->locdom.lb) )
656  {
657  /* add the bound change info to the variable's bound change info array */
658  switch( boundchg->boundchgtype )
659  {
661  SCIPsetDebugMsg(set, " -> branching: new upper bound of <%s>[%g,%g]: %g\n",
662  SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, boundchg->newbound);
663  SCIP_CALL( varAddUbchginfo(var, blkmem, set, var->locdom.ub, boundchg->newbound, depth, pos,
665  stat->lastbranchvar = var;
667  stat->lastbranchvalue = boundchg->newbound;
668  break;
669 
671  assert(boundchg->data.inferencedata.reason.cons != NULL);
672  SCIPsetDebugMsg(set, " -> constraint <%s> inference: new upper bound of <%s>[%g,%g]: %g\n",
673  SCIPconsGetName(boundchg->data.inferencedata.reason.cons),
674  SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, boundchg->newbound);
675  SCIP_CALL( varAddUbchginfo(var, blkmem, set, var->locdom.ub, boundchg->newbound, depth, pos,
676  boundchg->data.inferencedata.var, boundchg->data.inferencedata.reason.cons, NULL,
677  boundchg->data.inferencedata.info,
679  break;
680 
682  SCIPsetDebugMsg(set, " -> propagator <%s> inference: new upper bound of <%s>[%g,%g]: %g\n",
683  boundchg->data.inferencedata.reason.prop != NULL
684  ? SCIPpropGetName(boundchg->data.inferencedata.reason.prop) : "-",
685  SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, boundchg->newbound);
686  SCIP_CALL( varAddUbchginfo(var, blkmem, set, var->locdom.ub, boundchg->newbound, depth, pos,
687  boundchg->data.inferencedata.var, NULL, boundchg->data.inferencedata.reason.prop,
688  boundchg->data.inferencedata.info,
690  break;
691 
692  default:
693  SCIPerrorMessage("invalid bound change type %d\n", boundchg->boundchgtype);
694  return SCIP_INVALIDDATA;
695  }
696 
697  /* change local bound of variable */
698  SCIP_CALL( SCIPvarChgUbLocal(var, blkmem, set, stat, lp, branchcand, eventqueue, boundchg->newbound) );
699  }
700  else
701  {
702  SCIPsetDebugMsg(set, " -> cutoff: new upper bound of <%s>[%g,%g]: %g\n",
703  SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, boundchg->newbound);
704  *cutoff = TRUE;
705  boundchg->redundant = TRUE; /* bound change has not entered the ubchginfos array of the variable! */
706  }
707  }
708  else
709  {
710  /* mark bound change to be inactive */
711  SCIPsetDebugMsg(set, " -> inactive %s: new upper bound of <%s>[%g,%g]: %g\n",
712  (SCIP_BOUNDCHGTYPE)boundchg->boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING ? "branching" : "inference",
713  SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, boundchg->newbound);
714  boundchg->redundant = TRUE;
715  }
716  break;
717 
718  default:
719  SCIPerrorMessage("unknown bound type\n");
720  return SCIP_INVALIDDATA;
721  }
722 
723  /* update the branching and inference history */
724  if( !boundchg->applied && !boundchg->redundant )
725  {
726  assert(var == boundchg->var);
727 
729  {
730  SCIP_CALL( SCIPvarIncNBranchings(var, blkmem, set, stat,
733  }
734  else if( stat->lastbranchvar != NULL )
735  {
736  /**@todo if last branching variable is unknown, retrieve it from the nodes' boundchg arrays */
737  SCIP_CALL( SCIPvarIncInferenceSum(stat->lastbranchvar, blkmem, set, stat, stat->lastbranchdir, stat->lastbranchvalue, 1.0) );
738  }
739  boundchg->applied = TRUE;
740  }
741 
742  return SCIP_OKAY;
743 }
744 
745 /** undoes single bound change */
747  SCIP_BOUNDCHG* boundchg, /**< bound change to remove */
748  BMS_BLKMEM* blkmem, /**< block memory */
749  SCIP_SET* set, /**< global SCIP settings */
750  SCIP_STAT* stat, /**< problem statistics */
751  SCIP_LP* lp, /**< current LP data */
752  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
753  SCIP_EVENTQUEUE* eventqueue /**< event queue */
754  )
755 {
756  SCIP_VAR* var;
757 
758  assert(boundchg != NULL);
759  assert(stat != NULL);
760 
761  /* ignore redundant bound changes */
762  if( boundchg->redundant )
763  return SCIP_OKAY;
764 
765  var = boundchg->var;
766  assert(var != NULL);
768 
769  /* undo bound change: apply the previous bound change of variable */
770  switch( boundchg->boundtype )
771  {
773  var->nlbchginfos--;
774  assert(var->nlbchginfos >= 0);
775  assert(var->lbchginfos != NULL);
776  assert( SCIPsetIsFeasEQ(set, var->lbchginfos[var->nlbchginfos].newbound, var->locdom.lb) ); /*lint !e777*/
777  assert( SCIPsetIsFeasLE(set, boundchg->newbound, var->locdom.lb) ); /* current lb might be larger to intermediate global bound change */
778 
779  SCIPsetDebugMsg(set, "removed lower bound change info of var <%s>[%g,%g]: depth=%d, pos=%d, %g -> %g\n",
780  SCIPvarGetName(var), var->locdom.lb, var->locdom.ub,
783 
784  /* reinstall the previous local bound */
785  SCIP_CALL( SCIPvarChgLbLocal(boundchg->var, blkmem, set, stat, lp, branchcand, eventqueue,
786  var->lbchginfos[var->nlbchginfos].oldbound) );
787 
788  /* in case all bound changes are removed the local bound should match the global bound */
789  assert(var->nlbchginfos > 0 || SCIPsetIsFeasEQ(set, var->locdom.lb, var->glbdom.lb));
790 
791  break;
792 
794  var->nubchginfos--;
795  assert(var->nubchginfos >= 0);
796  assert(var->ubchginfos != NULL);
797  assert( SCIPsetIsFeasEQ(set, var->ubchginfos[var->nubchginfos].newbound, var->locdom.ub) ); /*lint !e777*/
798  assert( SCIPsetIsFeasGE(set, boundchg->newbound, var->locdom.ub) ); /* current ub might be smaller to intermediate global bound change */
799 
800  SCIPsetDebugMsg(set, "removed upper bound change info of var <%s>[%g,%g]: depth=%d, pos=%d, %g -> %g\n",
801  SCIPvarGetName(var), var->locdom.lb, var->locdom.ub,
804 
805  /* reinstall the previous local bound */
806  SCIP_CALL( SCIPvarChgUbLocal(boundchg->var, blkmem, set, stat, lp, branchcand, eventqueue,
807  var->ubchginfos[var->nubchginfos].oldbound) );
808 
809  /* in case all bound changes are removed the local bound should match the global bound */
810  assert(var->nubchginfos > 0 || SCIPsetIsFeasEQ(set, var->locdom.ub, var->glbdom.ub));
811 
812  break;
813 
814  default:
815  SCIPerrorMessage("unknown bound type\n");
816  return SCIP_INVALIDDATA;
817  }
818 
819  /* update last branching variable */
821  {
822  stat->lastbranchvar = NULL;
824  }
825 
826  return SCIP_OKAY;
827 }
828 
829 /** applies single bound change to the global problem by changing the global bound of the corresponding variable */
830 static
832  SCIP_BOUNDCHG* boundchg, /**< bound change to apply */
833  BMS_BLKMEM* blkmem, /**< block memory */
834  SCIP_SET* set, /**< global SCIP settings */
835  SCIP_STAT* stat, /**< problem statistics */
836  SCIP_LP* lp, /**< current LP data */
837  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
838  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
839  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
840  SCIP_Bool* cutoff /**< pointer to store whether an infeasible bound change was detected */
841  )
842 {
843  SCIP_VAR* var;
844  SCIP_Real newbound;
845  SCIP_BOUNDTYPE boundtype;
846 
847  assert(boundchg != NULL);
848  assert(cutoff != NULL);
849 
850  *cutoff = FALSE;
851 
852  /* ignore redundant bound changes */
853  if( boundchg->redundant )
854  return SCIP_OKAY;
855 
856  var = SCIPboundchgGetVar(boundchg);
857  newbound = SCIPboundchgGetNewbound(boundchg);
858  boundtype = SCIPboundchgGetBoundtype(boundchg);
859 
860  /* check if the bound change is redundant which can happen due to a (better) global bound change which was performed
861  * after that bound change was applied
862  *
863  * @note a global bound change is not captured by the redundant member of the bound change data structure
864  */
865  if( (boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsFeasLE(set, newbound, SCIPvarGetLbGlobal(var)))
866  || (boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsFeasGE(set, newbound, SCIPvarGetUbGlobal(var))) )
867  {
868  return SCIP_OKAY;
869  }
870 
871  SCIPsetDebugMsg(set, "applying global bound change: <%s>[%g,%g] %s %g\n",
873  boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", newbound);
874 
875  /* check for cutoff */
876  if( (boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsFeasGT(set, newbound, SCIPvarGetUbGlobal(var)))
877  || (boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsFeasLT(set, newbound, SCIPvarGetLbGlobal(var))) )
878  {
879  *cutoff = TRUE;
880  return SCIP_OKAY;
881  }
882 
883  /* apply bound change */
884  SCIP_CALL( SCIPvarChgBdGlobal(var, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, newbound, boundtype) );
885 
886  return SCIP_OKAY;
887 }
888 
889 /** captures branching and inference data of bound change */
890 static
892  SCIP_BOUNDCHG* boundchg /**< bound change to remove */
893  )
894 {
895  assert(boundchg != NULL);
896 
897  /* capture variable associated with the bound change */
898  assert(boundchg->var != NULL);
899  SCIPvarCapture(boundchg->var);
900 
901  switch( boundchg->boundchgtype )
902  {
905  break;
906 
908  assert(boundchg->data.inferencedata.var != NULL);
909  assert(boundchg->data.inferencedata.reason.cons != NULL);
910  SCIPconsCapture(boundchg->data.inferencedata.reason.cons);
911  break;
912 
913  default:
914  SCIPerrorMessage("invalid bound change type\n");
915  return SCIP_INVALIDDATA;
916  }
917 
918  return SCIP_OKAY;
919 }
920 
921 /** releases branching and inference data of bound change */
922 static
924  SCIP_BOUNDCHG* boundchg, /**< bound change to remove */
925  BMS_BLKMEM* blkmem, /**< block memory */
926  SCIP_SET* set, /**< global SCIP settings */
927  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
928  SCIP_LP* lp /**< current LP data */
929 
930  )
931 {
932  assert(boundchg != NULL);
933 
934  switch( boundchg->boundchgtype )
935  {
938  break;
939 
941  assert(boundchg->data.inferencedata.var != NULL);
942  assert(boundchg->data.inferencedata.reason.cons != NULL);
943  SCIP_CALL( SCIPconsRelease(&boundchg->data.inferencedata.reason.cons, blkmem, set) );
944  break;
945 
946  default:
947  SCIPerrorMessage("invalid bound change type\n");
948  return SCIP_INVALIDDATA;
949  }
950 
951  /* release variable */
952  assert(boundchg->var != NULL);
953  SCIP_CALL( SCIPvarRelease(&boundchg->var, blkmem, set, eventqueue, lp) );
954 
955 
956  return SCIP_OKAY;
957 }
958 
959 /** creates empty domain change data with dynamic arrays */
960 static
962  SCIP_DOMCHG** domchg, /**< pointer to domain change data */
963  BMS_BLKMEM* blkmem /**< block memory */
964  )
965 {
966  assert(domchg != NULL);
967  assert(blkmem != NULL);
968 
969  SCIP_ALLOC( BMSallocBlockMemorySize(blkmem, domchg, sizeof(SCIP_DOMCHGDYN)) );
970  (*domchg)->domchgdyn.domchgtype = SCIP_DOMCHGTYPE_DYNAMIC; /*lint !e641*/
971  (*domchg)->domchgdyn.nboundchgs = 0;
972  (*domchg)->domchgdyn.boundchgs = NULL;
973  (*domchg)->domchgdyn.nholechgs = 0;
974  (*domchg)->domchgdyn.holechgs = NULL;
975  (*domchg)->domchgdyn.boundchgssize = 0;
976  (*domchg)->domchgdyn.holechgssize = 0;
977 
978  return SCIP_OKAY;
979 }
980 
981 /** frees domain change data */
983  SCIP_DOMCHG** domchg, /**< pointer to domain change */
984  BMS_BLKMEM* blkmem, /**< block memory */
985  SCIP_SET* set, /**< global SCIP settings */
986  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
987  SCIP_LP* lp /**< current LP data */
988  )
989 {
990  assert(domchg != NULL);
991  assert(blkmem != NULL);
992 
993  if( *domchg != NULL )
994  {
995  int i;
996 
997  /* release variables, branching and inference data associated with the bound changes */
998  for( i = 0; i < (int)(*domchg)->domchgbound.nboundchgs; ++i )
999  {
1000  SCIP_CALL( boundchgReleaseData(&(*domchg)->domchgbound.boundchgs[i], blkmem, set, eventqueue, lp) );
1001  }
1002 
1003  /* free memory for bound and hole changes */
1004  switch( (*domchg)->domchgdyn.domchgtype )
1005  {
1006  case SCIP_DOMCHGTYPE_BOUND:
1007  BMSfreeBlockMemoryArrayNull(blkmem, &(*domchg)->domchgbound.boundchgs, (*domchg)->domchgbound.nboundchgs);
1008  BMSfreeBlockMemorySize(blkmem, domchg, sizeof(SCIP_DOMCHGBOUND));
1009  break;
1010  case SCIP_DOMCHGTYPE_BOTH:
1011  BMSfreeBlockMemoryArrayNull(blkmem, &(*domchg)->domchgboth.boundchgs, (*domchg)->domchgboth.nboundchgs);
1012  BMSfreeBlockMemoryArrayNull(blkmem, &(*domchg)->domchgboth.holechgs, (*domchg)->domchgboth.nholechgs);
1013  BMSfreeBlockMemorySize(blkmem, domchg, sizeof(SCIP_DOMCHGBOTH));
1014  break;
1016  BMSfreeBlockMemoryArrayNull(blkmem, &(*domchg)->domchgdyn.boundchgs, (*domchg)->domchgdyn.boundchgssize);
1017  BMSfreeBlockMemoryArrayNull(blkmem, &(*domchg)->domchgdyn.holechgs, (*domchg)->domchgdyn.holechgssize);
1018  BMSfreeBlockMemorySize(blkmem, domchg, sizeof(SCIP_DOMCHGDYN));
1019  break;
1020  default:
1021  SCIPerrorMessage("invalid domain change type\n");
1022  return SCIP_INVALIDDATA;
1023  }
1024  }
1025 
1026  return SCIP_OKAY;
1027 }
1028 
1029 /** converts a static domain change data into a dynamic one */
1030 static
1032  SCIP_DOMCHG** domchg, /**< pointer to domain change data */
1033  BMS_BLKMEM* blkmem /**< block memory */
1034  )
1035 {
1036  assert(domchg != NULL);
1037  assert(blkmem != NULL);
1038 
1039  SCIPdebugMessage("making domain change data %p pointing to %p dynamic\n", (void*)domchg, (void*)*domchg);
1040 
1041  if( *domchg == NULL )
1042  {
1043  SCIP_CALL( domchgCreate(domchg, blkmem) );
1044  }
1045  else
1046  {
1047  switch( (*domchg)->domchgdyn.domchgtype )
1048  {
1049  case SCIP_DOMCHGTYPE_BOUND:
1050  SCIP_ALLOC( BMSreallocBlockMemorySize(blkmem, domchg, sizeof(SCIP_DOMCHGBOUND), sizeof(SCIP_DOMCHGDYN)) );
1051  (*domchg)->domchgdyn.nholechgs = 0;
1052  (*domchg)->domchgdyn.holechgs = NULL;
1053  (*domchg)->domchgdyn.boundchgssize = (*domchg)->domchgdyn.nboundchgs;
1054  (*domchg)->domchgdyn.holechgssize = 0;
1055  (*domchg)->domchgdyn.domchgtype = SCIP_DOMCHGTYPE_DYNAMIC; /*lint !e641*/
1056  break;
1057  case SCIP_DOMCHGTYPE_BOTH:
1058  SCIP_ALLOC( BMSreallocBlockMemorySize(blkmem, domchg, sizeof(SCIP_DOMCHGBOTH), sizeof(SCIP_DOMCHGDYN)) );
1059  (*domchg)->domchgdyn.boundchgssize = (*domchg)->domchgdyn.nboundchgs;
1060  (*domchg)->domchgdyn.holechgssize = (*domchg)->domchgdyn.nholechgs;
1061  (*domchg)->domchgdyn.domchgtype = SCIP_DOMCHGTYPE_DYNAMIC; /*lint !e641*/
1062  break;
1064  break;
1065  default:
1066  SCIPerrorMessage("invalid domain change type\n");
1067  return SCIP_INVALIDDATA;
1068  }
1069  }
1070 #ifndef NDEBUG
1071  {
1072  int i;
1073  for( i = 0; i < (int)(*domchg)->domchgbound.nboundchgs; ++i )
1074  assert(SCIPvarGetType((*domchg)->domchgbound.boundchgs[i].var) == SCIP_VARTYPE_CONTINUOUS
1075  || EPSISINT((*domchg)->domchgbound.boundchgs[i].newbound, 1e-06));
1076  }
1077 #endif
1078 
1079  return SCIP_OKAY;
1080 }
1081 
1082 /** converts a dynamic domain change data into a static one, using less memory than for a dynamic one */
1084  SCIP_DOMCHG** domchg, /**< pointer to domain change data */
1085  BMS_BLKMEM* blkmem, /**< block memory */
1086  SCIP_SET* set, /**< global SCIP settings */
1087  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1088  SCIP_LP* lp /**< current LP data */
1089  )
1090 {
1091  assert(domchg != NULL);
1092  assert(blkmem != NULL);
1093 
1094  SCIPsetDebugMsg(set, "making domain change data %p pointing to %p static\n", (void*)domchg, (void*)*domchg);
1095 
1096  if( *domchg != NULL )
1097  {
1098  switch( (*domchg)->domchgdyn.domchgtype )
1099  {
1100  case SCIP_DOMCHGTYPE_BOUND:
1101  if( (*domchg)->domchgbound.nboundchgs == 0 )
1102  {
1103  SCIP_CALL( SCIPdomchgFree(domchg, blkmem, set, eventqueue, lp) );
1104  }
1105  break;
1106  case SCIP_DOMCHGTYPE_BOTH:
1107  if( (*domchg)->domchgboth.nholechgs == 0 )
1108  {
1109  if( (*domchg)->domchgbound.nboundchgs == 0 )
1110  {
1111  SCIP_CALL( SCIPdomchgFree(domchg, blkmem, set, eventqueue, lp) );
1112  }
1113  else
1114  {
1115  SCIP_ALLOC( BMSreallocBlockMemorySize(blkmem, domchg, sizeof(SCIP_DOMCHGBOTH), sizeof(SCIP_DOMCHGBOUND)) );
1116  (*domchg)->domchgdyn.domchgtype = SCIP_DOMCHGTYPE_BOUND; /*lint !e641*/
1117  }
1118  }
1119  break;
1121  if( (*domchg)->domchgboth.nholechgs == 0 )
1122  {
1123  if( (*domchg)->domchgbound.nboundchgs == 0 )
1124  {
1125  SCIP_CALL( SCIPdomchgFree(domchg, blkmem, set, eventqueue, lp) );
1126  }
1127  else
1128  {
1129  /* shrink dynamic size arrays to their minimal sizes */
1130  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*domchg)->domchgdyn.boundchgs,
1131  (*domchg)->domchgdyn.boundchgssize, (*domchg)->domchgdyn.nboundchgs) ); /*lint !e571*/
1132  BMSfreeBlockMemoryArrayNull(blkmem, &(*domchg)->domchgdyn.holechgs, (*domchg)->domchgdyn.holechgssize);
1133 
1134  /* convert into static domain change */
1135  SCIP_ALLOC( BMSreallocBlockMemorySize(blkmem, domchg, sizeof(SCIP_DOMCHGDYN), sizeof(SCIP_DOMCHGBOUND)) );
1136  (*domchg)->domchgdyn.domchgtype = SCIP_DOMCHGTYPE_BOUND; /*lint !e641*/
1137  }
1138  }
1139  else
1140  {
1141  /* shrink dynamic size arrays to their minimal sizes */
1142  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*domchg)->domchgdyn.boundchgs,
1143  (*domchg)->domchgdyn.boundchgssize, (*domchg)->domchgdyn.nboundchgs) ); /*lint !e571*/
1144  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*domchg)->domchgdyn.holechgs,
1145  (*domchg)->domchgdyn.holechgssize, (*domchg)->domchgdyn.nholechgs) );
1146 
1147  /* convert into static domain change */
1148  SCIP_ALLOC( BMSreallocBlockMemorySize(blkmem, domchg, sizeof(SCIP_DOMCHGDYN), sizeof(SCIP_DOMCHGBOTH)) );
1149  (*domchg)->domchgdyn.domchgtype = SCIP_DOMCHGTYPE_BOTH; /*lint !e641*/
1150  }
1151  break;
1152  default:
1153  SCIPerrorMessage("invalid domain change type\n");
1154  return SCIP_INVALIDDATA;
1155  }
1156 #ifndef NDEBUG
1157  if( *domchg != NULL )
1158  {
1159  int i;
1160  for( i = 0; i < (int)(*domchg)->domchgbound.nboundchgs; ++i )
1161  assert(SCIPvarGetType((*domchg)->domchgbound.boundchgs[i].var) == SCIP_VARTYPE_CONTINUOUS
1162  || SCIPsetIsFeasIntegral(set, (*domchg)->domchgbound.boundchgs[i].newbound));
1163  }
1164 #endif
1165  }
1166 
1167  return SCIP_OKAY;
1168 }
1169 
1170 /** ensures, that boundchgs array can store at least num entries */
1171 static
1173  SCIP_DOMCHG* domchg, /**< domain change data structure */
1174  BMS_BLKMEM* blkmem, /**< block memory */
1175  SCIP_SET* set, /**< global SCIP settings */
1176  int num /**< minimum number of entries to store */
1177  )
1178 {
1179  assert(domchg != NULL);
1180  assert(domchg->domchgdyn.domchgtype == SCIP_DOMCHGTYPE_DYNAMIC); /*lint !e641*/
1181 
1182  if( num > domchg->domchgdyn.boundchgssize )
1183  {
1184  int newsize;
1185 
1186  newsize = SCIPsetCalcMemGrowSize(set, num);
1187  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &domchg->domchgdyn.boundchgs, domchg->domchgdyn.boundchgssize, newsize) );
1188  domchg->domchgdyn.boundchgssize = newsize;
1189  }
1190  assert(num <= domchg->domchgdyn.boundchgssize);
1191 
1192  return SCIP_OKAY;
1193 }
1194 
1195 /** ensures, that holechgs array can store at least num additional entries */
1196 static
1198  SCIP_DOMCHG* domchg, /**< domain change data structure */
1199  BMS_BLKMEM* blkmem, /**< block memory */
1200  SCIP_SET* set, /**< global SCIP settings */
1201  int num /**< minimum number of additional entries to store */
1202  )
1203 {
1204  assert(domchg != NULL);
1205  assert(domchg->domchgdyn.domchgtype == SCIP_DOMCHGTYPE_DYNAMIC); /*lint !e641*/
1206 
1207  if( num > domchg->domchgdyn.holechgssize )
1208  {
1209  int newsize;
1210 
1211  newsize = SCIPsetCalcMemGrowSize(set, num);
1212  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &domchg->domchgdyn.holechgs, domchg->domchgdyn.holechgssize, newsize) );
1213  domchg->domchgdyn.holechgssize = newsize;
1214  }
1215  assert(num <= domchg->domchgdyn.holechgssize);
1216 
1217  return SCIP_OKAY;
1218 }
1219 
1220 /** applies domain change */
1222  SCIP_DOMCHG* domchg, /**< domain change to apply */
1223  BMS_BLKMEM* blkmem, /**< block memory */
1224  SCIP_SET* set, /**< global SCIP settings */
1225  SCIP_STAT* stat, /**< problem statistics */
1226  SCIP_LP* lp, /**< current LP data */
1227  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1228  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1229  int depth, /**< depth in the tree, where the domain change takes place */
1230  SCIP_Bool* cutoff /**< pointer to store whether an infeasible domain change was detected */
1231  )
1232 {
1233  int i;
1234 
1235  assert(cutoff != NULL);
1236 
1237  *cutoff = FALSE;
1238 
1239  SCIPsetDebugMsg(set, "applying domain changes at %p in depth %d\n", (void*)domchg, depth);
1240 
1241  if( domchg == NULL )
1242  return SCIP_OKAY;
1243 
1244  /* apply bound changes */
1245  for( i = 0; i < (int)domchg->domchgbound.nboundchgs; ++i )
1246  {
1247  SCIP_CALL( SCIPboundchgApply(&domchg->domchgbound.boundchgs[i], blkmem, set, stat, lp,
1248  branchcand, eventqueue, depth, i, cutoff) );
1249  if( *cutoff )
1250  break;
1251  }
1252  SCIPsetDebugMsg(set, " -> %u bound changes (cutoff %u)\n", domchg->domchgbound.nboundchgs, *cutoff);
1253 
1254  /* mark all bound changes after a cutoff redundant */
1255  for( ; i < (int)domchg->domchgbound.nboundchgs; ++i )
1256  domchg->domchgbound.boundchgs[i].redundant = TRUE;
1257 
1258  /* apply holelist changes */
1259  if( domchg->domchgdyn.domchgtype != SCIP_DOMCHGTYPE_BOUND ) /*lint !e641*/
1260  {
1261  for( i = 0; i < domchg->domchgboth.nholechgs; ++i )
1262  *(domchg->domchgboth.holechgs[i].ptr) = domchg->domchgboth.holechgs[i].newlist;
1263  SCIPsetDebugMsg(set, " -> %d hole changes\n", domchg->domchgboth.nholechgs);
1264  }
1265 
1266  return SCIP_OKAY;
1267 }
1268 
1269 /** undoes domain change */
1271  SCIP_DOMCHG* domchg, /**< domain change to remove */
1272  BMS_BLKMEM* blkmem, /**< block memory */
1273  SCIP_SET* set, /**< global SCIP settings */
1274  SCIP_STAT* stat, /**< problem statistics */
1275  SCIP_LP* lp, /**< current LP data */
1276  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1277  SCIP_EVENTQUEUE* eventqueue /**< event queue */
1278  )
1279 {
1280  int i;
1281 
1282  SCIPsetDebugMsg(set, "undoing domain changes at %p\n", (void*)domchg);
1283  if( domchg == NULL )
1284  return SCIP_OKAY;
1285 
1286  /* undo holelist changes */
1287  if( domchg->domchgdyn.domchgtype != SCIP_DOMCHGTYPE_BOUND ) /*lint !e641*/
1288  {
1289  for( i = domchg->domchgboth.nholechgs-1; i >= 0; --i )
1290  *(domchg->domchgboth.holechgs[i].ptr) = domchg->domchgboth.holechgs[i].oldlist;
1291  SCIPsetDebugMsg(set, " -> %d hole changes\n", domchg->domchgboth.nholechgs);
1292  }
1293 
1294  /* undo bound changes */
1295  for( i = domchg->domchgbound.nboundchgs-1; i >= 0; --i )
1296  {
1297  SCIP_CALL( SCIPboundchgUndo(&domchg->domchgbound.boundchgs[i], blkmem, set, stat, lp, branchcand, eventqueue) );
1298  }
1299  SCIPsetDebugMsg(set, " -> %u bound changes\n", domchg->domchgbound.nboundchgs);
1300 
1301  return SCIP_OKAY;
1302 }
1303 
1304 /** applies domain change to the global problem */
1306  SCIP_DOMCHG* domchg, /**< domain change to apply */
1307  BMS_BLKMEM* blkmem, /**< block memory */
1308  SCIP_SET* set, /**< global SCIP settings */
1309  SCIP_STAT* stat, /**< problem statistics */
1310  SCIP_LP* lp, /**< current LP data */
1311  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1312  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1313  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1314  SCIP_Bool* cutoff /**< pointer to store whether an infeasible domain change was detected */
1315  )
1316 {
1317  int i;
1318 
1319  assert(cutoff != NULL);
1320 
1321  *cutoff = FALSE;
1322 
1323  if( domchg == NULL )
1324  return SCIP_OKAY;
1325 
1326  SCIPsetDebugMsg(set, "applying domain changes at %p to the global problem\n", (void*)domchg);
1327 
1328  /* apply bound changes */
1329  for( i = 0; i < (int)domchg->domchgbound.nboundchgs; ++i )
1330  {
1331  SCIP_CALL( boundchgApplyGlobal(&domchg->domchgbound.boundchgs[i], blkmem, set, stat, lp,
1332  branchcand, eventqueue, cliquetable, cutoff) );
1333  if( *cutoff )
1334  break;
1335  }
1336  SCIPsetDebugMsg(set, " -> %u global bound changes\n", domchg->domchgbound.nboundchgs);
1337 
1338  /**@todo globally apply holelist changes - how can this be done without confusing pointer updates? */
1339 
1340  return SCIP_OKAY;
1341 }
1342 
1343 /** adds bound change to domain changes */
1345  SCIP_DOMCHG** domchg, /**< pointer to domain change data structure */
1346  BMS_BLKMEM* blkmem, /**< block memory */
1347  SCIP_SET* set, /**< global SCIP settings */
1348  SCIP_VAR* var, /**< variable to change the bounds for */
1349  SCIP_Real newbound, /**< new value for bound */
1350  SCIP_BOUNDTYPE boundtype, /**< type of bound for var: lower or upper bound */
1351  SCIP_BOUNDCHGTYPE boundchgtype, /**< type of bound change: branching decision or inference */
1352  SCIP_Real lpsolval, /**< solval of variable in last LP on path to node, or SCIP_INVALID if unknown */
1353  SCIP_VAR* infervar, /**< variable that was changed (parent of var, or var itself), or NULL */
1354  SCIP_CONS* infercons, /**< constraint that deduced the bound change, or NULL */
1355  SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
1356  int inferinfo, /**< user information for inference to help resolving the conflict */
1357  SCIP_BOUNDTYPE inferboundtype /**< type of bound for inference var: lower or upper bound */
1358  )
1359 {
1360  SCIP_BOUNDCHG* boundchg;
1361 
1362  assert(domchg != NULL);
1363  assert(var != NULL);
1365  assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPsetIsFeasIntegral(set, newbound));
1366  assert(!SCIPvarIsBinary(var) || SCIPsetIsEQ(set, newbound, boundtype == SCIP_BOUNDTYPE_LOWER ? 1.0 : 0.0));
1367  assert(boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING || infervar != NULL);
1368  assert((boundchgtype == SCIP_BOUNDCHGTYPE_CONSINFER) == (infercons != NULL));
1369  assert(boundchgtype == SCIP_BOUNDCHGTYPE_PROPINFER || inferprop == NULL);
1370 
1371  SCIPsetDebugMsg(set, "adding %s bound change <%s: %g> of variable <%s> to domain change at %p pointing to %p\n",
1372  boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING ? "branching" : "inference",
1373  newbound, var->name, (void*)domchg, (void*)*domchg);
1374 
1375  /* if domain change data doesn't exist, create it;
1376  * if domain change is static, convert it into dynamic change
1377  */
1378  if( *domchg == NULL )
1379  {
1380  SCIP_CALL( domchgCreate(domchg, blkmem) );
1381  }
1382  else if( (*domchg)->domchgdyn.domchgtype != SCIP_DOMCHGTYPE_DYNAMIC ) /*lint !e641*/
1383  {
1384  SCIP_CALL( domchgMakeDynamic(domchg, blkmem) );
1385  }
1386  assert(*domchg != NULL && (*domchg)->domchgdyn.domchgtype == SCIP_DOMCHGTYPE_DYNAMIC); /*lint !e641*/
1387 
1388  /* get memory for additional bound change */
1389  SCIP_CALL( domchgEnsureBoundchgsSize(*domchg, blkmem, set, (*domchg)->domchgdyn.nboundchgs+1) );
1390 
1391  /* fill in the bound change data */
1392  boundchg = &(*domchg)->domchgdyn.boundchgs[(*domchg)->domchgdyn.nboundchgs];
1393  boundchg->var = var;
1394  switch( boundchgtype )
1395  {
1397  boundchg->data.branchingdata.lpsolval = lpsolval;
1398  break;
1400  assert(infercons != NULL);
1401  boundchg->data.inferencedata.var = infervar;
1402  boundchg->data.inferencedata.reason.cons = infercons;
1403  boundchg->data.inferencedata.info = inferinfo;
1404  break;
1406  boundchg->data.inferencedata.var = infervar;
1407  boundchg->data.inferencedata.reason.prop = inferprop;
1408  boundchg->data.inferencedata.info = inferinfo;
1409  break;
1410  default:
1411  SCIPerrorMessage("invalid bound change type %d\n", boundchgtype);
1412  return SCIP_INVALIDDATA;
1413  }
1414 
1415  boundchg->newbound = newbound;
1416  boundchg->boundchgtype = boundchgtype; /*lint !e641*/
1417  boundchg->boundtype = boundtype; /*lint !e641*/
1418  boundchg->inferboundtype = inferboundtype; /*lint !e641*/
1419  boundchg->applied = FALSE;
1420  boundchg->redundant = FALSE;
1421  (*domchg)->domchgdyn.nboundchgs++;
1422 
1423  /* capture branching and inference data associated with the bound changes */
1424  SCIP_CALL( boundchgCaptureData(boundchg) );
1425 
1426 #ifdef SCIP_DISABLED_CODE /* expensive debug check */
1427 #ifdef SCIP_MORE_DEBUG
1428  {
1429  int i;
1430  for( i = 0; i < (int)(*domchg)->domchgbound.nboundchgs; ++i )
1431  assert(SCIPvarGetType((*domchg)->domchgbound.boundchgs[i].var) == SCIP_VARTYPE_CONTINUOUS
1432  || SCIPsetIsFeasIntegral(set, (*domchg)->domchgbound.boundchgs[i].newbound));
1433  }
1434 #endif
1435 #endif
1436 
1437  return SCIP_OKAY;
1438 }
1439 
1440 /** adds hole change to domain changes */
1442  SCIP_DOMCHG** domchg, /**< pointer to domain change data structure */
1443  BMS_BLKMEM* blkmem, /**< block memory */
1444  SCIP_SET* set, /**< global SCIP settings */
1445  SCIP_HOLELIST** ptr, /**< changed list pointer */
1446  SCIP_HOLELIST* newlist, /**< new value of list pointer */
1447  SCIP_HOLELIST* oldlist /**< old value of list pointer */
1448  )
1449 {
1450  SCIP_HOLECHG* holechg;
1451 
1452  assert(domchg != NULL);
1453  assert(ptr != NULL);
1454 
1455  /* if domain change data doesn't exist, create it;
1456  * if domain change is static, convert it into dynamic change
1457  */
1458  if( *domchg == NULL )
1459  {
1460  SCIP_CALL( domchgCreate(domchg, blkmem) );
1461  }
1462  else if( (*domchg)->domchgdyn.domchgtype != SCIP_DOMCHGTYPE_DYNAMIC ) /*lint !e641*/
1463  {
1464  SCIP_CALL( domchgMakeDynamic(domchg, blkmem) );
1465  }
1466  assert(*domchg != NULL && (*domchg)->domchgdyn.domchgtype == SCIP_DOMCHGTYPE_DYNAMIC); /*lint !e641*/
1467 
1468  /* get memory for additional hole change */
1469  SCIP_CALL( domchgEnsureHolechgsSize(*domchg, blkmem, set, (*domchg)->domchgdyn.nholechgs+1) );
1470 
1471  /* fill in the hole change data */
1472  holechg = &(*domchg)->domchgdyn.holechgs[(*domchg)->domchgdyn.nholechgs];
1473  holechg->ptr = ptr;
1474  holechg->newlist = newlist;
1475  holechg->oldlist = oldlist;
1476  (*domchg)->domchgdyn.nholechgs++;
1477 
1478  return SCIP_OKAY;
1479 }
1480 
1481 
1482 
1483 
1484 /*
1485  * methods for variables
1486  */
1487 
1488 /** returns adjusted lower bound value, which is rounded for integral variable types */
1489 static
1491  SCIP_SET* set, /**< global SCIP settings */
1492  SCIP_VARTYPE vartype, /**< type of variable */
1493  SCIP_Real lb /**< lower bound to adjust */
1494  )
1495 {
1496  if( lb < 0 && SCIPsetIsInfinity(set, -lb) )
1497  return -SCIPsetInfinity(set);
1498  else if( lb > 0 && SCIPsetIsInfinity(set, lb) )
1499  return SCIPsetInfinity(set);
1500  else if( vartype != SCIP_VARTYPE_CONTINUOUS )
1501  return SCIPsetFeasCeil(set, lb);
1502  else if( SCIPsetIsZero(set, lb) )
1503  return 0.0;
1504  else
1505  return lb;
1506 }
1507 
1508 /** returns adjusted upper bound value, which is rounded for integral variable types */
1509 static
1511  SCIP_SET* set, /**< global SCIP settings */
1512  SCIP_VARTYPE vartype, /**< type of variable */
1513  SCIP_Real ub /**< upper bound to adjust */
1514  )
1515 {
1516  if( ub > 0 && SCIPsetIsInfinity(set, ub) )
1517  return SCIPsetInfinity(set);
1518  else if( ub < 0 && SCIPsetIsInfinity(set, -ub) )
1519  return -SCIPsetInfinity(set);
1520  else if( vartype != SCIP_VARTYPE_CONTINUOUS )
1521  return SCIPsetFeasFloor(set, ub);
1522  else if( SCIPsetIsZero(set, ub) )
1523  return 0.0;
1524  else
1525  return ub;
1526 }
1527 
1528 /** removes (redundant) cliques, implications and variable bounds of variable from all other variables' implications and variable
1529  * bounds arrays, and optionally removes them also from the variable itself
1530  */
1532  SCIP_VAR* var, /**< problem variable */
1533  BMS_BLKMEM* blkmem, /**< block memory */
1534  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1535  SCIP_SET* set, /**< global SCIP settings */
1536  SCIP_Bool irrelevantvar, /**< has the variable become irrelevant? */
1537  SCIP_Bool onlyredundant, /**< should only the redundant implications and variable bounds be removed? */
1538  SCIP_Bool removefromvar /**< should the implications and variable bounds be removed from the var itself? */
1539  )
1540 {
1541  SCIP_Real lb;
1542  SCIP_Real ub;
1543 
1544  assert(var != NULL);
1546  assert(SCIPvarIsActive(var) || SCIPvarGetType(var) != SCIP_VARTYPE_BINARY);
1547 
1548  lb = SCIPvarGetLbGlobal(var);
1549  ub = SCIPvarGetUbGlobal(var);
1550 
1551  SCIPsetDebugMsg(set, "removing %s implications and vbounds of %s<%s>[%g,%g]\n",
1552  onlyredundant ? "redundant" : "all", irrelevantvar ? "irrelevant " : "", SCIPvarGetName(var), lb, ub);
1553 
1554  /* remove implications of (fixed) binary variable */
1555  if( var->implics != NULL && (!onlyredundant || lb > 0.5 || ub < 0.5) )
1556  {
1557  SCIP_Bool varfixing;
1558 
1559  assert(SCIPvarIsBinary(var));
1560 
1561  varfixing = FALSE;
1562  do
1563  {
1564  SCIP_VAR** implvars;
1565  SCIP_BOUNDTYPE* impltypes;
1566  int nimpls;
1567  int i;
1568 
1569  nimpls = SCIPimplicsGetNImpls(var->implics, varfixing);
1570  implvars = SCIPimplicsGetVars(var->implics, varfixing);
1571  impltypes = SCIPimplicsGetTypes(var->implics, varfixing);
1572 
1573  for( i = 0; i < nimpls; i++ )
1574  {
1575  SCIP_VAR* implvar;
1576  SCIP_BOUNDTYPE impltype;
1577 
1578  implvar = implvars[i];
1579  impltype = impltypes[i];
1580  assert(implvar != var);
1581 
1582  /* remove for all implications z == 0 / 1 ==> x <= p / x >= p (x not binary)
1583  * the following variable bound from x's variable bounds
1584  * x <= b*z+d (z in vubs of x) , for z == 0 / 1 ==> x <= p
1585  * x >= b*z+d (z in vlbs of x) , for z == 0 / 1 ==> x >= p
1586  */
1587  if( impltype == SCIP_BOUNDTYPE_UPPER )
1588  {
1589  if( implvar->vubs != NULL ) /* implvar may have been aggregated in the mean time */
1590  {
1591  SCIPsetDebugMsg(set, "deleting variable bound: <%s> == %u ==> <%s> <= %g\n",
1592  SCIPvarGetName(var), varfixing, SCIPvarGetName(implvar),
1593  SCIPimplicsGetBounds(var->implics, varfixing)[i]);
1594  SCIP_CALL( SCIPvboundsDel(&implvar->vubs, blkmem, var, varfixing) );
1595  implvar->closestvblpcount = -1;
1596  var->closestvblpcount = -1;
1597  }
1598  }
1599  else
1600  {
1601  if( implvar->vlbs != NULL ) /* implvar may have been aggregated in the mean time */
1602  {
1603  SCIPsetDebugMsg(set, "deleting variable bound: <%s> == %u ==> <%s> >= %g\n",
1604  SCIPvarGetName(var), varfixing, SCIPvarGetName(implvar),
1605  SCIPimplicsGetBounds(var->implics, varfixing)[i]);
1606  SCIP_CALL( SCIPvboundsDel(&implvar->vlbs, blkmem, var, !varfixing) );
1607  implvar->closestvblpcount = -1;
1608  var->closestvblpcount = -1;
1609  }
1610  }
1611  }
1612  varfixing = !varfixing;
1613  }
1614  while( varfixing == TRUE );
1615 
1616  if( removefromvar )
1617  {
1618  /* free the implications data structures */
1619  SCIPimplicsFree(&var->implics, blkmem);
1620  }
1621  }
1622 
1623  /* remove the (redundant) variable lower bounds */
1624  if( var->vlbs != NULL )
1625  {
1626  SCIP_VAR** vars;
1627  SCIP_Real* coefs;
1628  SCIP_Real* constants;
1629  int nvbds;
1630  int newnvbds;
1631  int i;
1632 
1633  nvbds = SCIPvboundsGetNVbds(var->vlbs);
1634  vars = SCIPvboundsGetVars(var->vlbs);
1635  coefs = SCIPvboundsGetCoefs(var->vlbs);
1636  constants = SCIPvboundsGetConstants(var->vlbs);
1637 
1638  /* remove for all variable bounds x >= b*z+d the following implication from z's implications
1639  * z == ub ==> x >= b*ub + d , if b > 0
1640  * z == lb ==> x >= b*lb + d , if b < 0
1641  */
1642  newnvbds = 0;
1643  for( i = 0; i < nvbds; i++ )
1644  {
1645  SCIP_VAR* implvar;
1646  SCIP_Real coef;
1647 
1648  assert(newnvbds <= i);
1649 
1650  implvar = vars[i];
1651  assert(implvar != NULL);
1652 
1653  coef = coefs[i];
1654  assert(!SCIPsetIsZero(set, coef));
1655 
1656  /* check, if we want to remove the variable bound */
1657  if( onlyredundant )
1658  {
1659  SCIP_Real vbound;
1660 
1661  vbound = MAX(coef * SCIPvarGetUbGlobal(implvar), coef * SCIPvarGetLbGlobal(implvar)) + constants[i]; /*lint !e666*/
1662  if( SCIPsetIsFeasGT(set, vbound, lb) )
1663  {
1664  /* the variable bound is not redundant: keep it */
1665  if( removefromvar )
1666  {
1667  if( newnvbds < i )
1668  {
1669  vars[newnvbds] = implvar;
1670  coefs[newnvbds] = coef;
1671  constants[newnvbds] = constants[i];
1672  }
1673  newnvbds++;
1674  }
1675  continue;
1676  }
1677  }
1678 
1679  /* remove the corresponding implication */
1680  if( implvar->implics != NULL ) /* variable may have been aggregated in the mean time */
1681  {
1682  SCIPsetDebugMsg(set, "deleting implication: <%s> == %d ==> <%s> >= %g\n",
1683  SCIPvarGetName(implvar), (coef > 0.0), SCIPvarGetName(var), MAX(coef, 0.0) + constants[i]);
1684  SCIP_CALL( SCIPimplicsDel(&implvar->implics, blkmem, set, (coef > 0.0), var, SCIP_BOUNDTYPE_LOWER) );
1685  }
1686  if( coef > 0.0 && implvar->vubs != NULL ) /* implvar may have been aggregated in the mean time */
1687  {
1688  SCIPsetDebugMsg(set, "deleting variable upper bound from <%s> involving variable %s\n",
1689  SCIPvarGetName(implvar), SCIPvarGetName(var));
1690  SCIP_CALL( SCIPvboundsDel(&implvar->vubs, blkmem, var, FALSE) );
1691  implvar->closestvblpcount = -1;
1692  var->closestvblpcount = -1;
1693  }
1694  else if( coef < 0.0 && implvar->vlbs != NULL ) /* implvar may have been aggregated in the mean time */
1695  {
1696  SCIPsetDebugMsg(set, "deleting variable lower bound from <%s> involving variable %s\n",
1697  SCIPvarGetName(implvar), SCIPvarGetName(var));
1698  SCIP_CALL( SCIPvboundsDel(&implvar->vlbs, blkmem, var, TRUE) );
1699  implvar->closestvblpcount = -1;
1700  var->closestvblpcount = -1;
1701  }
1702  }
1703 
1704  if( removefromvar )
1705  {
1706  /* update the number of variable bounds */
1707  SCIPvboundsShrink(&var->vlbs, blkmem, newnvbds);
1708  var->closestvblpcount = -1;
1709  }
1710  }
1711 
1712  /**@todo in general, variable bounds like x >= b*z + d corresponding to an implication like z = ub ==> x >= b*ub + d
1713  * might be missing because we only add variable bounds with reasonably small value of b. thus, we currently
1714  * cannot remove such variables x from z's implications.
1715  */
1716 
1717  /* remove the (redundant) variable upper bounds */
1718  if( var->vubs != NULL )
1719  {
1720  SCIP_VAR** vars;
1721  SCIP_Real* coefs;
1722  SCIP_Real* constants;
1723  int nvbds;
1724  int newnvbds;
1725  int i;
1726 
1727  nvbds = SCIPvboundsGetNVbds(var->vubs);
1728  vars = SCIPvboundsGetVars(var->vubs);
1729  coefs = SCIPvboundsGetCoefs(var->vubs);
1730  constants = SCIPvboundsGetConstants(var->vubs);
1731 
1732  /* remove for all variable bounds x <= b*z+d the following implication from z's implications
1733  * z == lb ==> x <= b*lb + d , if b > 0
1734  * z == ub ==> x <= b*ub + d , if b < 0
1735  */
1736  newnvbds = 0;
1737  for( i = 0; i < nvbds; i++ )
1738  {
1739  SCIP_VAR* implvar;
1740  SCIP_Real coef;
1741 
1742  assert(newnvbds <= i);
1743 
1744  implvar = vars[i];
1745  assert(implvar != NULL);
1746 
1747  coef = coefs[i];
1748  assert(!SCIPsetIsZero(set, coef));
1749 
1750  /* check, if we want to remove the variable bound */
1751  if( onlyredundant )
1752  {
1753  SCIP_Real vbound;
1754 
1755  vbound = MIN(coef * SCIPvarGetUbGlobal(implvar), coef * SCIPvarGetLbGlobal(implvar)) + constants[i]; /*lint !e666*/
1756  if( SCIPsetIsFeasLT(set, vbound, ub) )
1757  {
1758  /* the variable bound is not redundant: keep it */
1759  if( removefromvar )
1760  {
1761  if( newnvbds < i )
1762  {
1763  vars[newnvbds] = implvar;
1764  coefs[newnvbds] = coefs[i];
1765  constants[newnvbds] = constants[i];
1766  }
1767  newnvbds++;
1768  }
1769  continue;
1770  }
1771  }
1772 
1773  /* remove the corresponding implication */
1774  if( implvar->implics != NULL ) /* variable may have been aggregated in the mean time */
1775  {
1776  SCIPsetDebugMsg(set, "deleting implication: <%s> == %d ==> <%s> <= %g\n",
1777  SCIPvarGetName(implvar), (coef < 0.0), SCIPvarGetName(var), MIN(coef, 0.0) + constants[i]);
1778  SCIP_CALL( SCIPimplicsDel(&implvar->implics, blkmem, set, (coef < 0.0), var, SCIP_BOUNDTYPE_UPPER) );
1779  }
1780  if( coef < 0.0 && implvar->vubs != NULL ) /* implvar may have been aggregated in the mean time */
1781  {
1782  SCIPsetDebugMsg(set, "deleting variable upper bound from <%s> involving variable %s\n",
1783  SCIPvarGetName(implvar), SCIPvarGetName(var));
1784  SCIP_CALL( SCIPvboundsDel(&implvar->vubs, blkmem, var, TRUE) );
1785  implvar->closestvblpcount = -1;
1786  var->closestvblpcount = -1;
1787  }
1788  else if( coef > 0.0 && implvar->vlbs != NULL ) /* implvar may have been aggregated in the mean time */
1789  {
1790  SCIPsetDebugMsg(set, "deleting variable lower bound from <%s> involving variable %s\n",
1791  SCIPvarGetName(implvar), SCIPvarGetName(var));
1792  SCIP_CALL( SCIPvboundsDel(&implvar->vlbs, blkmem, var, FALSE) );
1793  implvar->closestvblpcount = -1;
1794  var->closestvblpcount = -1;
1795  }
1796  }
1797 
1798  if( removefromvar )
1799  {
1800  /* update the number of variable bounds */
1801  SCIPvboundsShrink(&var->vubs, blkmem, newnvbds);
1802  var->closestvblpcount = -1;
1803  }
1804  }
1805 
1806  /* remove the variable from all cliques */
1807  if( SCIPvarIsBinary(var) )
1808  {
1809  SCIPcliquelistRemoveFromCliques(var->cliquelist, cliquetable, var, irrelevantvar);
1810  SCIPcliquelistFree(&var->cliquelist, blkmem);
1811  }
1812 
1813  /**@todo variable bounds like x <= b*z + d with z general integer are not removed from x's vbd arrays, because
1814  * z has no link (like in the binary case) to x
1815  */
1816 
1817  return SCIP_OKAY;
1818 }
1819 
1820 /** sets the variable name */
1821 static
1823  SCIP_VAR* var, /**< problem variable */
1824  BMS_BLKMEM* blkmem, /**< block memory */
1825  SCIP_STAT* stat, /**< problem statistics, or NULL */
1826  const char* name /**< name of variable, or NULL for automatic name creation */
1827  )
1828 {
1829  assert(blkmem != NULL);
1830  assert(var != NULL);
1831 
1832  if( name == NULL )
1833  {
1834  char s[SCIP_MAXSTRLEN];
1835 
1836  assert(stat != NULL);
1837 
1838  (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "_var%d_", stat->nvaridx);
1839  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &var->name, s, strlen(s)+1) );
1840  }
1841  else
1842  {
1843  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &var->name, name, strlen(name)+1) );
1844  }
1845 
1846  return SCIP_OKAY;
1847 }
1848 
1849 
1850 /** creates variable; if variable is of integral type, fractional bounds are automatically rounded; an integer variable
1851  * with bounds zero and one is automatically converted into a binary variable
1852  */
1853 static
1855  SCIP_VAR** var, /**< pointer to variable data */
1856  BMS_BLKMEM* blkmem, /**< block memory */
1857  SCIP_SET* set, /**< global SCIP settings */
1858  SCIP_STAT* stat, /**< problem statistics */
1859  const char* name, /**< name of variable, or NULL for automatic name creation */
1860  SCIP_Real lb, /**< lower bound of variable */
1861  SCIP_Real ub, /**< upper bound of variable */
1862  SCIP_Real obj, /**< objective function value */
1863  SCIP_VARTYPE vartype, /**< type of variable */
1864  SCIP_Bool initial, /**< should var's column be present in the initial root LP? */
1865  SCIP_Bool removable, /**< is var's column removable from the LP (due to aging or cleanup)? */
1866  SCIP_DECL_VARCOPY ((*varcopy)), /**< copies variable data if wanted to subscip, or NULL */
1867  SCIP_DECL_VARDELORIG ((*vardelorig)), /**< frees user data of original variable, or NULL */
1868  SCIP_DECL_VARTRANS ((*vartrans)), /**< creates transformed user data by transforming original user data, or NULL */
1869  SCIP_DECL_VARDELTRANS ((*vardeltrans)), /**< frees user data of transformed variable, or NULL */
1870  SCIP_VARDATA* vardata /**< user data for this specific variable */
1871  )
1872 {
1873  assert(var != NULL);
1874  assert(blkmem != NULL);
1875  assert(stat != NULL);
1876 
1877  /* adjust bounds of variable */
1878  lb = adjustedLb(set, vartype, lb);
1879  ub = adjustedUb(set, vartype, ub);
1880 
1881  /* convert [0,1]-integers into binary variables and check that binary variables have correct bounds */
1882  if( (SCIPsetIsEQ(set, lb, 0.0) || SCIPsetIsEQ(set, lb, 1.0))
1883  && (SCIPsetIsEQ(set, ub, 0.0) || SCIPsetIsEQ(set, ub, 1.0)) )
1884  {
1885  if( vartype == SCIP_VARTYPE_INTEGER )
1886  vartype = SCIP_VARTYPE_BINARY;
1887  }
1888  else
1889  {
1890  if( vartype == SCIP_VARTYPE_BINARY )
1891  {
1892  SCIPerrorMessage("invalid bounds [%.2g,%.2g] for binary variable <%s>\n", lb, ub, name);
1893  return SCIP_INVALIDDATA;
1894  }
1895  }
1896 
1897  assert(vartype != SCIP_VARTYPE_BINARY || SCIPsetIsEQ(set, lb, 0.0) || SCIPsetIsEQ(set, lb, 1.0));
1898  assert(vartype != SCIP_VARTYPE_BINARY || SCIPsetIsEQ(set, ub, 0.0) || SCIPsetIsEQ(set, ub, 1.0));
1899 
1900  SCIP_ALLOC( BMSallocBlockMemory(blkmem, var) );
1901 
1902  /* set variable's name */
1903  SCIP_CALL( varSetName(*var, blkmem, stat, name) );
1904 
1905 #ifndef NDEBUG
1906  (*var)->scip = set->scip;
1907 #endif
1908  (*var)->obj = obj;
1909  (*var)->unchangedobj = obj;
1910  (*var)->branchfactor = 1.0;
1911  (*var)->rootsol = 0.0;
1912  (*var)->bestrootsol = 0.0;
1913  (*var)->bestrootredcost = 0.0;
1914  (*var)->bestrootlpobjval = SCIP_INVALID;
1915  (*var)->relaxsol = 0.0;
1916  (*var)->nlpsol = 0.0;
1917  (*var)->primsolavg = 0.5 * (lb + ub);
1918  (*var)->conflictlb = SCIP_REAL_MIN;
1919  (*var)->conflictub = SCIP_REAL_MAX;
1920  (*var)->conflictrelaxedlb = (*var)->conflictlb;
1921  (*var)->conflictrelaxedub = (*var)->conflictub;
1922  (*var)->lazylb = -SCIPsetInfinity(set);
1923  (*var)->lazyub = SCIPsetInfinity(set);
1924  (*var)->glbdom.holelist = NULL;
1925  (*var)->glbdom.lb = lb;
1926  (*var)->glbdom.ub = ub;
1927  (*var)->locdom.holelist = NULL;
1928  (*var)->locdom.lb = lb;
1929  (*var)->locdom.ub = ub;
1930  (*var)->varcopy = varcopy;
1931  (*var)->vardelorig = vardelorig;
1932  (*var)->vartrans = vartrans;
1933  (*var)->vardeltrans = vardeltrans;
1934  (*var)->vardata = vardata;
1935  (*var)->parentvars = NULL;
1936  (*var)->negatedvar = NULL;
1937  (*var)->vlbs = NULL;
1938  (*var)->vubs = NULL;
1939  (*var)->implics = NULL;
1940  (*var)->cliquelist = NULL;
1941  (*var)->eventfilter = NULL;
1942  (*var)->lbchginfos = NULL;
1943  (*var)->ubchginfos = NULL;
1944  (*var)->index = stat->nvaridx;
1945  (*var)->probindex = -1;
1946  (*var)->pseudocandindex = -1;
1947  (*var)->eventqueueindexobj = -1;
1948  (*var)->eventqueueindexlb = -1;
1949  (*var)->eventqueueindexub = -1;
1950  (*var)->parentvarssize = 0;
1951  (*var)->nparentvars = 0;
1952  (*var)->nuses = 0;
1953  (*var)->nlocksdown = 0;
1954  (*var)->nlocksup = 0;
1955  (*var)->branchpriority = 0;
1956  (*var)->branchdirection = SCIP_BRANCHDIR_AUTO; /*lint !e641*/
1957  (*var)->lbchginfossize = 0;
1958  (*var)->nlbchginfos = 0;
1959  (*var)->ubchginfossize = 0;
1960  (*var)->nubchginfos = 0;
1961  (*var)->conflictlbcount = 0;
1962  (*var)->conflictubcount = 0;
1963  (*var)->closestvlbidx = -1;
1964  (*var)->closestvubidx = -1;
1965  (*var)->closestvblpcount = -1;
1966  (*var)->initial = initial;
1967  (*var)->removable = removable;
1968  (*var)->deleted = FALSE;
1969  (*var)->donotmultaggr = FALSE;
1970  (*var)->vartype = vartype; /*lint !e641*/
1971  (*var)->pseudocostflag = FALSE;
1972  (*var)->eventqueueimpl = FALSE;
1973  (*var)->deletable = FALSE;
1974  (*var)->delglobalstructs = FALSE;
1975  (*var)->clqcomponentidx = -1;
1976 
1977  stat->nvaridx++;
1978 
1979  /* create branching and inference history entries */
1980  SCIP_CALL( SCIPhistoryCreate(&(*var)->history, blkmem) );
1981  SCIP_CALL( SCIPhistoryCreate(&(*var)->historycrun, blkmem) );
1982 
1983  /* the value based history is only created on demand */
1984  (*var)->valuehistory = NULL;
1985 
1986  return SCIP_OKAY;
1987 }
1988 
1989 /** creates and captures an original problem variable; an integer variable with bounds
1990  * zero and one is automatically converted into a binary variable
1991  */
1993  SCIP_VAR** var, /**< pointer to variable data */
1994  BMS_BLKMEM* blkmem, /**< block memory */
1995  SCIP_SET* set, /**< global SCIP settings */
1996  SCIP_STAT* stat, /**< problem statistics */
1997  const char* name, /**< name of variable, or NULL for automatic name creation */
1998  SCIP_Real lb, /**< lower bound of variable */
1999  SCIP_Real ub, /**< upper bound of variable */
2000  SCIP_Real obj, /**< objective function value */
2001  SCIP_VARTYPE vartype, /**< type of variable */
2002  SCIP_Bool initial, /**< should var's column be present in the initial root LP? */
2003  SCIP_Bool removable, /**< is var's column removable from the LP (due to aging or cleanup)? */
2004  SCIP_DECL_VARDELORIG ((*vardelorig)), /**< frees user data of original variable, or NULL */
2005  SCIP_DECL_VARTRANS ((*vartrans)), /**< creates transformed user data by transforming original user data, or NULL */
2006  SCIP_DECL_VARDELTRANS ((*vardeltrans)), /**< frees user data of transformed variable, or NULL */
2007  SCIP_DECL_VARCOPY ((*varcopy)), /**< copies variable data if wanted to subscip, or NULL */
2008  SCIP_VARDATA* vardata /**< user data for this specific variable */
2009  )
2010 {
2011  assert(var != NULL);
2012  assert(blkmem != NULL);
2013  assert(stat != NULL);
2014 
2015  /* create variable */
2016  SCIP_CALL( varCreate(var, blkmem, set, stat, name, lb, ub, obj, vartype, initial, removable,
2017  varcopy, vardelorig, vartrans, vardeltrans, vardata) );
2018 
2019  /* set variable status and data */
2020  (*var)->varstatus = SCIP_VARSTATUS_ORIGINAL; /*lint !e641*/
2021  (*var)->data.original.origdom.holelist = NULL;
2022  (*var)->data.original.origdom.lb = lb;
2023  (*var)->data.original.origdom.ub = ub;
2024  (*var)->data.original.transvar = NULL;
2025 
2026  /* capture variable */
2027  SCIPvarCapture(*var);
2028 
2029  return SCIP_OKAY;
2030 }
2031 
2032 /** creates and captures a loose variable belonging to the transformed problem; an integer variable with bounds
2033  * zero and one is automatically converted into a binary variable
2034  */
2036  SCIP_VAR** var, /**< pointer to variable data */
2037  BMS_BLKMEM* blkmem, /**< block memory */
2038  SCIP_SET* set, /**< global SCIP settings */
2039  SCIP_STAT* stat, /**< problem statistics */
2040  const char* name, /**< name of variable, or NULL for automatic name creation */
2041  SCIP_Real lb, /**< lower bound of variable */
2042  SCIP_Real ub, /**< upper bound of variable */
2043  SCIP_Real obj, /**< objective function value */
2044  SCIP_VARTYPE vartype, /**< type of variable */
2045  SCIP_Bool initial, /**< should var's column be present in the initial root LP? */
2046  SCIP_Bool removable, /**< is var's column removable from the LP (due to aging or cleanup)? */
2047  SCIP_DECL_VARDELORIG ((*vardelorig)), /**< frees user data of original variable, or NULL */
2048  SCIP_DECL_VARTRANS ((*vartrans)), /**< creates transformed user data by transforming original user data, or NULL */
2049  SCIP_DECL_VARDELTRANS ((*vardeltrans)), /**< frees user data of transformed variable, or NULL */
2050  SCIP_DECL_VARCOPY ((*varcopy)), /**< copies variable data if wanted to subscip, or NULL */
2051  SCIP_VARDATA* vardata /**< user data for this specific variable */
2052  )
2053 {
2054  assert(var != NULL);
2055  assert(blkmem != NULL);
2056 
2057  /* create variable */
2058  SCIP_CALL( varCreate(var, blkmem, set, stat, name, lb, ub, obj, vartype, initial, removable,
2059  varcopy, vardelorig, vartrans, vardeltrans, vardata) );
2060 
2061  /* create event filter for transformed variable */
2062  SCIP_CALL( SCIPeventfilterCreate(&(*var)->eventfilter, blkmem) );
2063 
2064  /* set variable status and data */
2065  (*var)->varstatus = SCIP_VARSTATUS_LOOSE; /*lint !e641*/
2066 
2067  /* capture variable */
2068  SCIPvarCapture(*var);
2069 
2070  return SCIP_OKAY;
2071 }
2072 
2073 /** copies and captures a variable from source to target SCIP; an integer variable with bounds zero and one is
2074  * automatically converted into a binary variable; in case the variable data cannot be copied the variable is not
2075  * copied at all
2076  */
2078  SCIP_VAR** var, /**< pointer to store the target variable */
2079  BMS_BLKMEM* blkmem, /**< block memory */
2080  SCIP_SET* set, /**< global SCIP settings */
2081  SCIP_STAT* stat, /**< problem statistics */
2082  SCIP* sourcescip, /**< source SCIP data structure */
2083  SCIP_VAR* sourcevar, /**< source variable */
2084  SCIP_HASHMAP* varmap, /**< a hashmap to store the mapping of source variables corresponding
2085  * target variables */
2086  SCIP_HASHMAP* consmap, /**< a hashmap to store the mapping of source constraints to the corresponding
2087  * target constraints */
2088  SCIP_Bool global /**< should global or local bounds be used? */
2089  )
2090 {
2091  SCIP_VARDATA* targetdata;
2092  SCIP_RESULT result;
2093  SCIP_Real lb;
2094  SCIP_Real ub;
2095 
2096  assert(set != NULL);
2097  assert(blkmem != NULL);
2098  assert(stat != NULL);
2099  assert(sourcescip != NULL);
2100  assert(sourcevar != NULL);
2101  assert(var != NULL);
2102  assert(set->stage == SCIP_STAGE_PROBLEM);
2103  assert(varmap != NULL);
2104  assert(consmap != NULL);
2105 
2106  /** @todo copy hole lists */
2107  assert(global || SCIPvarGetHolelistLocal(sourcevar) == NULL);
2108  assert(!global || SCIPvarGetHolelistGlobal(sourcevar) == NULL);
2109 
2110  result = SCIP_DIDNOTRUN;
2111  targetdata = NULL;
2112 
2113  if( SCIPvarGetStatus(sourcevar) == SCIP_VARSTATUS_ORIGINAL )
2114  {
2115  lb = SCIPvarGetLbOriginal(sourcevar);
2116  ub = SCIPvarGetUbOriginal(sourcevar);
2117  }
2118  else
2119  {
2120  lb = global ? SCIPvarGetLbGlobal(sourcevar) : SCIPvarGetLbLocal(sourcevar);
2121  ub = global ? SCIPvarGetUbGlobal(sourcevar) : SCIPvarGetUbLocal(sourcevar);
2122  }
2123 
2124  /* creates and captures the variable in the target SCIP and initialize callback methods and variable data to NULL */
2125  SCIP_CALL( SCIPvarCreateOriginal(var, blkmem, set, stat, SCIPvarGetName(sourcevar),
2126  lb, ub, SCIPvarGetObj(sourcevar), SCIPvarGetType(sourcevar),
2127  SCIPvarIsInitial(sourcevar), SCIPvarIsRemovable(sourcevar),
2128  NULL, NULL, NULL, NULL, NULL) );
2129  assert(*var != NULL);
2130 
2131  /* directly copy donotmultaggr flag */
2132  (*var)->donotmultaggr = sourcevar->donotmultaggr;
2133 
2134  /* insert variable into mapping between source SCIP and the target SCIP */
2135  assert(!SCIPhashmapExists(varmap, sourcevar));
2136  SCIP_CALL( SCIPhashmapInsert(varmap, sourcevar, *var) );
2137 
2138  /* in case there exists variable data and the variable data copy callback, try to copy variable data */
2139  if( sourcevar->vardata != NULL && sourcevar->varcopy != NULL )
2140  {
2141  SCIP_CALL( sourcevar->varcopy(set->scip, sourcescip, sourcevar, sourcevar->vardata,
2142  varmap, consmap, (*var), &targetdata, &result) );
2143 
2144  /* evaluate result */
2145  if( result != SCIP_DIDNOTRUN && result != SCIP_SUCCESS )
2146  {
2147  SCIPerrorMessage("variable data copying method returned invalid result <%d>\n", result);
2148  return SCIP_INVALIDRESULT;
2149  }
2150 
2151  assert(targetdata == NULL || result == SCIP_SUCCESS);
2152 
2153  /* if copying was successful, add the created variable data to the variable as well as all callback methods */
2154  if( result == SCIP_SUCCESS )
2155  {
2156  (*var)->varcopy = sourcevar->varcopy;
2157  (*var)->vardelorig = sourcevar->vardelorig;
2158  (*var)->vartrans = sourcevar->vartrans;
2159  (*var)->vardeltrans = sourcevar->vardeltrans;
2160  (*var)->vardata = targetdata;
2161  }
2162  }
2163 
2164  /* we initialize histories of the variables by copying the source variable-information */
2165  if( set->history_allowtransfer )
2166  {
2167  SCIPvarMergeHistories((*var), sourcevar, stat);
2168  }
2169 
2170  /* in case the copying was successfully, add the created variable data to the variable as well as all callback
2171  * methods
2172  */
2173  if( result == SCIP_SUCCESS )
2174  {
2175  (*var)->varcopy = sourcevar->varcopy;
2176  (*var)->vardelorig = sourcevar->vardelorig;
2177  (*var)->vartrans = sourcevar->vartrans;
2178  (*var)->vardeltrans = sourcevar->vardeltrans;
2179  (*var)->vardata = targetdata;
2180  }
2181 
2182  SCIPsetDebugMsg(set, "created copy <%s> of variable <%s>\n", SCIPvarGetName(*var), SCIPvarGetName(sourcevar));
2183 
2184  return SCIP_OKAY;
2185 }
2186 
2187 /** parse given string for a SCIP_Real bound */
2188 static
2190  SCIP_SET* set, /**< global SCIP settings */
2191  const char* str, /**< string to parse */
2192  SCIP_Real* value, /**< pointer to store the parsed value */
2193  char** endptr /**< pointer to store the final string position if successfully parsed */
2194  )
2195 {
2196  /* first check for infinity value */
2197  if( strncmp(str, "+inf", 4) == 0 )
2198  {
2199  *value = SCIPsetInfinity(set);
2200  (*endptr) = (char*)str + 4;
2201  }
2202  else if( strncmp(str, "-inf", 4) == 0 )
2203  {
2204  *value = -SCIPsetInfinity(set);
2205  (*endptr) = (char*)str + 4;
2206  }
2207  else
2208  {
2209  if( !SCIPstrToRealValue(str, value, endptr) )
2210  return SCIP_READERROR;
2211  }
2212 
2213  return SCIP_OKAY;
2214 }
2215 
2216 /** parse the characters as bounds */
2217 static
2219  SCIP_SET* set, /**< global SCIP settings */
2220  const char* str, /**< string to parse */
2221  char* type, /**< bound type (global, local, or lazy) */
2222  SCIP_Real* lb, /**< pointer to store the lower bound */
2223  SCIP_Real* ub, /**< pointer to store the upper bound */
2224  char** endptr /**< pointer to store the final string position if successfully parsed (or NULL if an error occured) */
2225  )
2226 {
2227  char token[SCIP_MAXSTRLEN];
2228 
2229  SCIPsetDebugMsg(set, "parsing bounds: '%s'\n", str);
2230 
2231  /* get bound type */
2232  SCIPstrCopySection(str, ' ', ' ', type, SCIP_MAXSTRLEN, endptr);
2233  if ( strncmp(type, "original", 8) != 0 && strncmp(type, "global", 6) != 0 && strncmp(type, "local", 5) != 0 && strncmp(type, "lazy", 4) != 0 )
2234  {
2235  SCIPsetDebugMsg(set, "unkown bound type <%s>\n", type);
2236  *endptr = NULL;
2237  return SCIP_OKAY;
2238  }
2239 
2240  SCIPsetDebugMsg(set, "parsed bound type <%s>\n", type);
2241 
2242  /* get lower bound */
2243  SCIPstrCopySection(str, '[', ',', token, SCIP_MAXSTRLEN, endptr);
2244  str = *endptr;
2245  SCIP_CALL( parseValue(set, token, lb, endptr) );
2246 
2247  /* get upper bound */
2248  SCIP_CALL( parseValue(set, str, ub, endptr) );
2249 
2250  SCIPsetDebugMsg(set, "parsed bounds: [%g,%g]\n", *lb, *ub);
2251 
2252  /* skip end of bounds */
2253  while ( **endptr != '\0' && (**endptr == ']' || **endptr == ',') )
2254  ++(*endptr);
2255 
2256  return SCIP_OKAY;
2257 }
2258 
2259 /** parses a given string for a variable informations */
2260 static
2262  SCIP_SET* set, /**< global SCIP settings */
2263  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2264  const char* str, /**< string to parse */
2265  char* name, /**< pointer to store the variable name */
2266  SCIP_Real* lb, /**< pointer to store the lower bound */
2267  SCIP_Real* ub, /**< pointer to store the upper bound */
2268  SCIP_Real* obj, /**< pointer to store the objective coefficient */
2269  SCIP_VARTYPE* vartype, /**< pointer to store the variable type */
2270  SCIP_Real* lazylb, /**< pointer to store if the lower bound is lazy */
2271  SCIP_Real* lazyub, /**< pointer to store if the upper bound is lazy */
2272  SCIP_Bool local, /**< should the local bound be applied */
2273  char** endptr, /**< pointer to store the final string position if successfully */
2274  SCIP_Bool* success /**< pointer store if the paring process was successful */
2275  )
2276 {
2277  SCIP_Real parsedlb;
2278  SCIP_Real parsedub;
2279  char token[SCIP_MAXSTRLEN];
2280  char* strptr;
2281  int i;
2282 
2283  assert(lb != NULL);
2284  assert(ub != NULL);
2285  assert(obj != NULL);
2286  assert(vartype != NULL);
2287  assert(lazylb != NULL);
2288  assert(lazyub != NULL);
2289  assert(success != NULL);
2290 
2291  (*success) = TRUE;
2292 
2293  /* copy variable type */
2294  SCIPstrCopySection(str, '[', ']', token, SCIP_MAXSTRLEN, endptr);
2295  assert(str != *endptr);
2296  SCIPsetDebugMsg(set, "parsed variable type <%s>\n", token);
2297 
2298  /* get variable type */
2299  if( strncmp(token, "binary", 3) == 0 )
2300  (*vartype) = SCIP_VARTYPE_BINARY;
2301  else if( strncmp(token, "integer", 3) == 0 )
2302  (*vartype) = SCIP_VARTYPE_INTEGER;
2303  else if( strncmp(token, "implicit", 3) == 0 )
2304  (*vartype) = SCIP_VARTYPE_IMPLINT;
2305  else if( strncmp(token, "continuous", 3) == 0 )
2306  (*vartype) = SCIP_VARTYPE_CONTINUOUS;
2307  else
2308  {
2309  SCIPmessagePrintWarning(messagehdlr, "unknown variable type\n");
2310  (*success) = FALSE;
2311  return SCIP_OKAY;
2312  }
2313 
2314  /* move string pointer behind variable type */
2315  str = *endptr;
2316 
2317  /* get variable name */
2318  SCIPstrCopySection(str, '<', '>', name, SCIP_MAXSTRLEN, endptr);
2319  assert(endptr != NULL);
2320  SCIPsetDebugMsg(set, "parsed variable name <%s>\n", name);
2321 
2322  /* move string pointer behind variable name */
2323  str = *endptr;
2324 
2325  /* cut out objective coefficient */
2326  SCIPstrCopySection(str, '=', ',', token, SCIP_MAXSTRLEN, endptr);
2327 
2328  /* move string pointer behind objective coefficient */
2329  str = *endptr;
2330 
2331  /* get objective coefficient */
2332  if( !SCIPstrToRealValue(token, obj, endptr) )
2333  {
2334  *endptr = NULL;
2335  return SCIP_READERROR;
2336  }
2337 
2338  SCIPsetDebugMsg(set, "parsed objective coefficient <%g>\n", *obj);
2339 
2340  /* parse global/original bounds */
2341  SCIP_CALL( parseBounds(set, str, token, lb, ub, endptr) );
2342  assert(strncmp(token, "global", 6) == 0 || strncmp(token, "original", 8) == 0);
2343 
2344  /* initialize the lazy bound */
2345  *lazylb = -SCIPsetInfinity(set);
2346  *lazyub = SCIPsetInfinity(set);
2347 
2348  /* store pointer */
2349  strptr = *endptr;
2350 
2351  /* possibly parse optional local and lazy bounds */
2352  for( i = 0; i < 2 && *endptr != NULL && **endptr != '\0'; ++i )
2353  {
2354  /* start after previous bounds */
2355  strptr = *endptr;
2356 
2357  /* parse global bounds */
2358  SCIP_CALL( parseBounds(set, strptr, token, &parsedlb, &parsedub, endptr) );
2359 
2360  /* stop if parsing of bounds failed */
2361  if( *endptr == NULL )
2362  break;
2363 
2364  if( strncmp(token, "local", 5) == 0 && local )
2365  {
2366  *lb = parsedlb;
2367  *ub = parsedub;
2368  }
2369  else if( strncmp(token, "lazy", 4) == 0 )
2370  {
2371  *lazylb = parsedlb;
2372  *lazyub = parsedub;
2373  }
2374  }
2375 
2376  /* restore pointer */
2377  if ( *endptr == NULL )
2378  *endptr = strptr;
2379 
2380  /* check bounds for binary variables */
2381  if ( (*vartype) == SCIP_VARTYPE_BINARY )
2382  {
2383  if ( SCIPsetIsLT(set, *lb, 0.0) || SCIPsetIsGT(set, *ub, 1.0) )
2384  {
2385  SCIPerrorMessage("Parsed invalid bounds for binary variable <%s>: [%f, %f].\n", name, *lb, *ub);
2386  return SCIP_READERROR;
2387  }
2388  if ( !SCIPsetIsInfinity(set, -(*lazylb)) && !SCIPsetIsInfinity(set, *lazyub) &&
2389  ( SCIPsetIsLT(set, *lazylb, 0.0) || SCIPsetIsGT(set, *lazyub, 1.0) ) )
2390  {
2391  SCIPerrorMessage("Parsed invalid lazy bounds for binary variable <%s>: [%f, %f].\n", name, *lazylb, *lazyub);
2392  return SCIP_READERROR;
2393  }
2394  }
2395 
2396  return SCIP_OKAY;
2397 }
2398 
2399 /** parses variable information (in cip format) out of a string; if the parsing process was successful an original
2400  * variable is created and captured; if variable is of integral type, fractional bounds are automatically rounded; an
2401  * integer variable with bounds zero and one is automatically converted into a binary variable
2402  */
2404  SCIP_VAR** var, /**< pointer to variable data */
2405  BMS_BLKMEM* blkmem, /**< block memory */
2406  SCIP_SET* set, /**< global SCIP settings */
2407  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2408  SCIP_STAT* stat, /**< problem statistics */
2409  const char* str, /**< string to parse */
2410  SCIP_Bool initial, /**< should var's column be present in the initial root LP? */
2411  SCIP_Bool removable, /**< is var's column removable from the LP (due to aging or cleanup)? */
2412  SCIP_DECL_VARCOPY ((*varcopy)), /**< copies variable data if wanted to subscip, or NULL */
2413  SCIP_DECL_VARDELORIG ((*vardelorig)), /**< frees user data of original variable */
2414  SCIP_DECL_VARTRANS ((*vartrans)), /**< creates transformed user data by transforming original user data */
2415  SCIP_DECL_VARDELTRANS ((*vardeltrans)), /**< frees user data of transformed variable */
2416  SCIP_VARDATA* vardata, /**< user data for this specific variable */
2417  char** endptr, /**< pointer to store the final string position if successfully */
2418  SCIP_Bool* success /**< pointer store if the paring process was successful */
2419  )
2420 {
2421  char name[SCIP_MAXSTRLEN];
2422  SCIP_Real lb;
2423  SCIP_Real ub;
2424  SCIP_Real obj;
2425  SCIP_VARTYPE vartype;
2426  SCIP_Real lazylb;
2427  SCIP_Real lazyub;
2428 
2429  assert(var != NULL);
2430  assert(blkmem != NULL);
2431  assert(stat != NULL);
2432  assert(endptr != NULL);
2433  assert(success != NULL);
2434 
2435  /* parse string in cip format for variable information */
2436  SCIP_CALL( varParse(set, messagehdlr, str, name, &lb, &ub, &obj, &vartype, &lazylb, &lazyub, FALSE, endptr, success) );
2437 
2438  if( *success )
2439  {
2440  /* create variable */
2441  SCIP_CALL( varCreate(var, blkmem, set, stat, name, lb, ub, obj, vartype, initial, removable,
2442  varcopy, vardelorig, vartrans, vardeltrans, vardata) );
2443 
2444  /* set variable status and data */
2445  (*var)->varstatus = SCIP_VARSTATUS_ORIGINAL; /*lint !e641*/
2446  (*var)->data.original.origdom.holelist = NULL;
2447  (*var)->data.original.origdom.lb = lb;
2448  (*var)->data.original.origdom.ub = ub;
2449  (*var)->data.original.transvar = NULL;
2450 
2451  /* set lazy status of variable bounds */
2452  (*var)->lazylb = lazylb;
2453  (*var)->lazyub = lazyub;
2454 
2455  /* capture variable */
2456  SCIPvarCapture(*var);
2457  }
2458 
2459  return SCIP_OKAY;
2460 }
2461 
2462 /** parses variable information (in cip format) out of a string; if the parsing process was successful a loose variable
2463  * belonging to the transformed problem is created and captured; if variable is of integral type, fractional bounds are
2464  * automatically rounded; an integer variable with bounds zero and one is automatically converted into a binary
2465  * variable
2466  */
2468  SCIP_VAR** var, /**< pointer to variable data */
2469  BMS_BLKMEM* blkmem, /**< block memory */
2470  SCIP_SET* set, /**< global SCIP settings */
2471  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2472  SCIP_STAT* stat, /**< problem statistics */
2473  const char* str, /**< string to parse */
2474  SCIP_Bool initial, /**< should var's column be present in the initial root LP? */
2475  SCIP_Bool removable, /**< is var's column removable from the LP (due to aging or cleanup)? */
2476  SCIP_DECL_VARCOPY ((*varcopy)), /**< copies variable data if wanted to subscip, or NULL */
2477  SCIP_DECL_VARDELORIG ((*vardelorig)), /**< frees user data of original variable */
2478  SCIP_DECL_VARTRANS ((*vartrans)), /**< creates transformed user data by transforming original user data */
2479  SCIP_DECL_VARDELTRANS ((*vardeltrans)), /**< frees user data of transformed variable */
2480  SCIP_VARDATA* vardata, /**< user data for this specific variable */
2481  char** endptr, /**< pointer to store the final string position if successfully */
2482  SCIP_Bool* success /**< pointer store if the paring process was successful */
2483  )
2484 {
2485  char name[SCIP_MAXSTRLEN];
2486  SCIP_Real lb;
2487  SCIP_Real ub;
2488  SCIP_Real obj;
2489  SCIP_VARTYPE vartype;
2490  SCIP_Real lazylb;
2491  SCIP_Real lazyub;
2492 
2493  assert(var != NULL);
2494  assert(blkmem != NULL);
2495  assert(endptr != NULL);
2496  assert(success != NULL);
2497 
2498  /* parse string in cip format for variable information */
2499  SCIP_CALL( varParse(set, messagehdlr, str, name, &lb, &ub, &obj, &vartype, &lazylb, &lazyub, TRUE, endptr, success) );
2500 
2501  if( *success )
2502  {
2503  /* create variable */
2504  SCIP_CALL( varCreate(var, blkmem, set, stat, name, lb, ub, obj, vartype, initial, removable,
2505  varcopy, vardelorig, vartrans, vardeltrans, vardata) );
2506 
2507  /* create event filter for transformed variable */
2508  SCIP_CALL( SCIPeventfilterCreate(&(*var)->eventfilter, blkmem) );
2509 
2510  /* set variable status and data */
2511  (*var)->varstatus = SCIP_VARSTATUS_LOOSE; /*lint !e641*/
2512 
2513  /* set lazy status of variable bounds */
2514  (*var)->lazylb = lazylb;
2515  (*var)->lazyub = lazyub;
2516 
2517  /* capture variable */
2518  SCIPvarCapture(*var);
2519  }
2520 
2521  return SCIP_OKAY;
2522 }
2523 
2524 /** ensures, that parentvars array of var can store at least num entries */
2525 static
2527  SCIP_VAR* var, /**< problem variable */
2528  BMS_BLKMEM* blkmem, /**< block memory */
2529  SCIP_SET* set, /**< global SCIP settings */
2530  int num /**< minimum number of entries to store */
2531  )
2532 {
2533  assert(var->nparentvars <= var->parentvarssize);
2534 
2535  if( num > var->parentvarssize )
2536  {
2537  int newsize;
2538 
2539  newsize = SCIPsetCalcMemGrowSize(set, num);
2540  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &var->parentvars, var->parentvarssize, newsize) );
2541  var->parentvarssize = newsize;
2542  }
2543  assert(num <= var->parentvarssize);
2544 
2545  return SCIP_OKAY;
2546 }
2547 
2548 /** adds variable to parent list of a variable and captures parent variable */
2549 static
2551  SCIP_VAR* var, /**< variable to add parent to */
2552  BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
2553  SCIP_SET* set, /**< global SCIP settings */
2554  SCIP_VAR* parentvar /**< parent variable to add */
2555  )
2556 {
2557  assert(var != NULL);
2558  assert(parentvar != NULL);
2559 
2560  /* the direct original counterpart must be stored as first parent */
2561  assert(var->nparentvars == 0 || SCIPvarGetStatus(parentvar) != SCIP_VARSTATUS_ORIGINAL);
2562 
2563  SCIPsetDebugMsg(set, "adding parent <%s>[%p] to variable <%s>[%p] in slot %d\n",
2564  parentvar->name, (void*)parentvar, var->name, (void*)var, var->nparentvars);
2565 
2566  SCIP_CALL( varEnsureParentvarsSize(var, blkmem, set, var->nparentvars+1) );
2567 
2568  var->parentvars[var->nparentvars] = parentvar;
2569  var->nparentvars++;
2570 
2571  SCIPvarCapture(parentvar);
2572 
2573  return SCIP_OKAY;
2574 }
2575 
2576 /** deletes and releases all variables from the parent list of a variable, frees the memory of parents array */
2577 static
2579  SCIP_VAR** var, /**< pointer to variable */
2580  BMS_BLKMEM* blkmem, /**< block memory */
2581  SCIP_SET* set, /**< global SCIP settings */
2582  SCIP_EVENTQUEUE* eventqueue, /**< event queue (or NULL, if it's an original variable) */
2583  SCIP_LP* lp /**< current LP data (or NULL, if it's an original variable) */
2584  )
2585 {
2586  SCIP_VAR* parentvar;
2587  int i;
2588 
2589  SCIPsetDebugMsg(set, "free parents of <%s>\n", (*var)->name);
2590 
2591  /* release the parent variables and remove the link from the parent variable to the child */
2592  for( i = 0; i < (*var)->nparentvars; ++i )
2593  {
2594  assert((*var)->parentvars != NULL);
2595  parentvar = (*var)->parentvars[i];
2596  assert(parentvar != NULL);
2597 
2598  switch( SCIPvarGetStatus(parentvar) )
2599  {
2601  assert(parentvar->data.original.transvar == *var);
2602  assert(&parentvar->data.original.transvar != var);
2603  parentvar->data.original.transvar = NULL;
2604  break;
2605 
2607  assert(parentvar->data.aggregate.var == *var);
2608  assert(&parentvar->data.aggregate.var != var);
2609  parentvar->data.aggregate.var = NULL;
2610  break;
2611 
2612 #if 0
2613  /* The following code is unclear: should the current variable be removed from its parents? */
2615  assert(parentvar->data.multaggr.vars != NULL);
2616  for( v = 0; v < parentvar->data.multaggr.nvars && parentvar->data.multaggr.vars[v] != *var; ++v )
2617  {}
2618  assert(v < parentvar->data.multaggr.nvars && parentvar->data.multaggr.vars[v] == *var);
2619  if( v < parentvar->data.multaggr.nvars-1 )
2620  {
2621  parentvar->data.multaggr.vars[v] = parentvar->data.multaggr.vars[parentvar->data.multaggr.nvars-1];
2622  parentvar->data.multaggr.scalars[v] = parentvar->data.multaggr.scalars[parentvar->data.multaggr.nvars-1];
2623  }
2624  parentvar->data.multaggr.nvars--;
2625  break;
2626 #endif
2627 
2629  assert(parentvar->negatedvar == *var);
2630  assert((*var)->negatedvar == parentvar);
2631  parentvar->negatedvar = NULL;
2632  (*var)->negatedvar = NULL;
2633  break;
2634 
2635  default:
2636  SCIPerrorMessage("parent variable is neither ORIGINAL, AGGREGATED nor NEGATED\n");
2637  return SCIP_INVALIDDATA;
2638  } /*lint !e788*/
2639 
2640  SCIP_CALL( SCIPvarRelease(&(*var)->parentvars[i], blkmem, set, eventqueue, lp) );
2641  }
2642 
2643  /* free parentvars array */
2644  BMSfreeBlockMemoryArrayNull(blkmem, &(*var)->parentvars, (*var)->parentvarssize);
2645 
2646  return SCIP_OKAY;
2647 }
2648 
2649 /** frees a variable */
2650 static
2652  SCIP_VAR** var, /**< pointer to variable */
2653  BMS_BLKMEM* blkmem, /**< block memory */
2654  SCIP_SET* set, /**< global SCIP settings */
2655  SCIP_EVENTQUEUE* eventqueue, /**< event queue (may be NULL, if it's not a column variable) */
2656  SCIP_LP* lp /**< current LP data (may be NULL, if it's not a column variable) */
2657  )
2658 {
2659  assert(var != NULL);
2660  assert(*var != NULL);
2661  assert(SCIPvarGetStatus(*var) != SCIP_VARSTATUS_COLUMN || &(*var)->data.col->var != var);
2662  assert((*var)->nuses == 0);
2663  assert((*var)->probindex == -1);
2664 
2665  SCIPsetDebugMsg(set, "free variable <%s> with status=%d\n", (*var)->name, SCIPvarGetStatus(*var));
2666 
2667  switch( SCIPvarGetStatus(*var) )
2668  {
2670  assert((*var)->data.original.transvar == NULL); /* cannot free variable, if transformed variable is still existing */
2671  holelistFree(&(*var)->data.original.origdom.holelist, blkmem);
2672  assert((*var)->data.original.origdom.holelist == NULL);
2673  break;
2674  case SCIP_VARSTATUS_LOOSE:
2675  break;
2676  case SCIP_VARSTATUS_COLUMN:
2677  SCIP_CALL( SCIPcolFree(&(*var)->data.col, blkmem, set, eventqueue, lp) ); /* free corresponding LP column */
2678  break;
2679  case SCIP_VARSTATUS_FIXED:
2681  break;
2683  BMSfreeBlockMemoryArray(blkmem, &(*var)->data.multaggr.vars, (*var)->data.multaggr.varssize);
2684  BMSfreeBlockMemoryArray(blkmem, &(*var)->data.multaggr.scalars, (*var)->data.multaggr.varssize);
2685  break;
2687  break;
2688  default:
2689  SCIPerrorMessage("unknown variable status\n");
2690  return SCIP_INVALIDDATA;
2691  }
2692 
2693  /* release all parent variables and free the parentvars array */
2694  SCIP_CALL( varFreeParents(var, blkmem, set, eventqueue, lp) );
2695 
2696  /* free user data */
2698  {
2699  if( (*var)->vardelorig != NULL )
2700  {
2701  SCIP_CALL( (*var)->vardelorig(set->scip, *var, &(*var)->vardata) );
2702  }
2703  }
2704  else
2705  {
2706  if( (*var)->vardeltrans != NULL )
2707  {
2708  SCIP_CALL( (*var)->vardeltrans(set->scip, *var, &(*var)->vardata) );
2709  }
2710  }
2711 
2712  /* free event filter */
2713  if( (*var)->eventfilter != NULL )
2714  {
2715  SCIP_CALL( SCIPeventfilterFree(&(*var)->eventfilter, blkmem, set) );
2716  }
2717  assert((*var)->eventfilter == NULL);
2718 
2719  /* free hole lists */
2720  holelistFree(&(*var)->glbdom.holelist, blkmem);
2721  holelistFree(&(*var)->locdom.holelist, blkmem);
2722  assert((*var)->glbdom.holelist == NULL);
2723  assert((*var)->locdom.holelist == NULL);
2724 
2725  /* free variable bounds data structures */
2726  SCIPvboundsFree(&(*var)->vlbs, blkmem);
2727  SCIPvboundsFree(&(*var)->vubs, blkmem);
2728 
2729  /* free implications data structures */
2730  SCIPimplicsFree(&(*var)->implics, blkmem);
2731 
2732  /* free clique list data structures */
2733  SCIPcliquelistFree(&(*var)->cliquelist, blkmem);
2734 
2735  /* free bound change information arrays */
2736  BMSfreeBlockMemoryArrayNull(blkmem, &(*var)->lbchginfos, (*var)->lbchginfossize);
2737  BMSfreeBlockMemoryArrayNull(blkmem, &(*var)->ubchginfos, (*var)->ubchginfossize);
2738 
2739  /* free branching and inference history entries */
2740  SCIPhistoryFree(&(*var)->history, blkmem);
2741  SCIPhistoryFree(&(*var)->historycrun, blkmem);
2742  SCIPvaluehistoryFree(&(*var)->valuehistory, blkmem);
2743 
2744  /* free variable data structure */
2745  BMSfreeBlockMemoryArray(blkmem, &(*var)->name, strlen((*var)->name)+1);
2746  BMSfreeBlockMemory(blkmem, var);
2747 
2748  return SCIP_OKAY;
2749 }
2750 
2751 /** increases usage counter of variable */
2752 void SCIPvarCapture(
2753  SCIP_VAR* var /**< variable */
2754  )
2755 {
2756  assert(var != NULL);
2757  assert(var->nuses >= 0);
2758 
2759  SCIPdebugMessage("capture variable <%s> with nuses=%d\n", var->name, var->nuses);
2760  var->nuses++;
2761 }
2762 
2763 /** decreases usage counter of variable, and frees memory if necessary */
2765  SCIP_VAR** var, /**< pointer to variable */
2766  BMS_BLKMEM* blkmem, /**< block memory */
2767  SCIP_SET* set, /**< global SCIP settings */
2768  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2769  SCIP_LP* lp /**< current LP data (or NULL, if it's an original variable) */
2770  )
2771 {
2772  assert(var != NULL);
2773  assert(*var != NULL);
2774  assert((*var)->nuses >= 1);
2775  assert(blkmem != NULL);
2776  assert((*var)->scip == set->scip);
2777 
2778  SCIPsetDebugMsg(set, "release variable <%s> with nuses=%d\n", (*var)->name, (*var)->nuses);
2779  (*var)->nuses--;
2780  if( (*var)->nuses == 0 )
2781  {
2782  SCIP_CALL( varFree(var, blkmem, set, eventqueue, lp) );
2783  }
2784 
2785  *var = NULL;
2786 
2787  return SCIP_OKAY;
2788 }
2789 
2790 /** change variable name */
2792  SCIP_VAR* var, /**< problem variable */
2793  BMS_BLKMEM* blkmem, /**< block memory */
2794  const char* name /**< name of variable */
2795  )
2796 {
2797  assert(name != NULL);
2798 
2799  /* remove old variable name */
2800  BMSfreeBlockMemoryArray(blkmem, &var->name, strlen(var->name)+1);
2801 
2802  /* set new variable name */
2803  SCIP_CALL( varSetName(var, blkmem, NULL, name) );
2804 
2805  return SCIP_OKAY;
2806 }
2807 
2808 /** initializes variable data structure for solving */
2809 void SCIPvarInitSolve(
2810  SCIP_VAR* var /**< problem variable */
2811  )
2812 {
2813  assert(var != NULL);
2814 
2816  var->conflictlbcount = 0;
2817  var->conflictubcount = 0;
2818 }
2819 
2820 /** outputs the given bounds into the file stream */
2821 static
2822 void printBounds(
2823  SCIP_SET* set, /**< global SCIP settings */
2824  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2825  FILE* file, /**< output file (or NULL for standard output) */
2826  SCIP_Real lb, /**< lower bound */
2827  SCIP_Real ub, /**< upper bound */
2828  const char* name /**< bound type name */
2829  )
2830 {
2831  assert(set != NULL);
2832 
2833  SCIPmessageFPrintInfo(messagehdlr, file, ", %s=", name);
2834  if( SCIPsetIsInfinity(set, lb) )
2835  SCIPmessageFPrintInfo(messagehdlr, file, "[+inf,");
2836  else if( SCIPsetIsInfinity(set, -lb) )
2837  SCIPmessageFPrintInfo(messagehdlr, file, "[-inf,");
2838  else
2839  SCIPmessageFPrintInfo(messagehdlr, file, "[%.15g,", lb);
2840  if( SCIPsetIsInfinity(set, ub) )
2841  SCIPmessageFPrintInfo(messagehdlr, file, "+inf]");
2842  else if( SCIPsetIsInfinity(set, -ub) )
2843  SCIPmessageFPrintInfo(messagehdlr, file, "-inf]");
2844  else
2845  SCIPmessageFPrintInfo(messagehdlr, file, "%.15g]", ub);
2846 }
2847 
2848 /** prints hole list to file stream */
2849 static
2850 void printHolelist(
2851  SCIP_SET* set, /**< global SCIP settings */
2852  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2853  FILE* file, /**< output file (or NULL for standard output) */
2854  SCIP_HOLELIST* holelist, /**< hole list pointer to hole of interest */
2855  const char* name /**< hole type name */
2856  )
2857 { /*lint --e{715}*/
2858  SCIP_Real left;
2859  SCIP_Real right;
2860 
2861  if( holelist == NULL )
2862  return;
2863 
2864  left = SCIPholelistGetLeft(holelist);
2865  right = SCIPholelistGetRight(holelist);
2866 
2867  /* display first hole */
2868  SCIPmessageFPrintInfo(messagehdlr, file, ", %s=(%g,%g)", name, left, right);
2869  holelist = SCIPholelistGetNext(holelist);
2870 
2871  while(holelist != NULL )
2872  {
2873  left = SCIPholelistGetLeft(holelist);
2874  right = SCIPholelistGetRight(holelist);
2875 
2876  /* display hole */
2877  SCIPmessageFPrintInfo(messagehdlr, file, "(%g,%g)", left, right);
2878 
2879  /* get next hole */
2880  holelist = SCIPholelistGetNext(holelist);
2881  }
2882 }
2883 
2884 /** outputs variable information into file stream */
2886  SCIP_VAR* var, /**< problem variable */
2887  SCIP_SET* set, /**< global SCIP settings */
2888  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2889  FILE* file /**< output file (or NULL for standard output) */
2890  )
2891 {
2892  SCIP_HOLELIST* holelist;
2893  SCIP_Real lb;
2894  SCIP_Real ub;
2895  int i;
2896 
2897  assert(var != NULL);
2898  assert(var->scip == set->scip);
2899 
2900  /* type of variable */
2901  switch( SCIPvarGetType(var) )
2902  {
2903  case SCIP_VARTYPE_BINARY:
2904  SCIPmessageFPrintInfo(messagehdlr, file, " [binary]");
2905  break;
2906  case SCIP_VARTYPE_INTEGER:
2907  SCIPmessageFPrintInfo(messagehdlr, file, " [integer]");
2908  break;
2909  case SCIP_VARTYPE_IMPLINT:
2910  SCIPmessageFPrintInfo(messagehdlr, file, " [implicit]");
2911  break;
2913  SCIPmessageFPrintInfo(messagehdlr, file, " [continuous]");
2914  break;
2915  default:
2916  SCIPerrorMessage("unknown variable type\n");
2917  SCIPABORT();
2918  return SCIP_ERROR; /*lint !e527*/
2919  }
2920 
2921  /* name */
2922  SCIPmessageFPrintInfo(messagehdlr, file, " <%s>:", var->name);
2923 
2924  /* objective value */
2925  SCIPmessageFPrintInfo(messagehdlr, file, " obj=%.15g", var->obj);
2926 
2927  /* bounds (global bounds for transformed variables, original bounds for original variables) */
2928  if( !SCIPvarIsTransformed(var) )
2929  {
2930  /* output original bound */
2931  lb = SCIPvarGetLbOriginal(var);
2932  ub = SCIPvarGetUbOriginal(var);
2933  printBounds(set, messagehdlr, file, lb, ub, "original bounds");
2934 
2935  /* output lazy bound */
2936  lb = SCIPvarGetLbLazy(var);
2937  ub = SCIPvarGetUbLazy(var);
2938 
2939  /* only display the lazy bounds if they are different from [-infinity,infinity] */
2940  if( !SCIPsetIsInfinity(set, -lb) || !SCIPsetIsInfinity(set, ub) )
2941  printBounds(set, messagehdlr, file, lb, ub, "lazy bounds");
2942 
2943  holelist = SCIPvarGetHolelistOriginal(var);
2944  printHolelist(set, messagehdlr, file, holelist, "original holes");
2945  }
2946  else
2947  {
2948  /* output global bound */
2949  lb = SCIPvarGetLbGlobal(var);
2950  ub = SCIPvarGetUbGlobal(var);
2951  printBounds(set, messagehdlr, file, lb, ub, "global bounds");
2952 
2953  /* output local bound */
2954  lb = SCIPvarGetLbLocal(var);
2955  ub = SCIPvarGetUbLocal(var);
2956  printBounds(set, messagehdlr, file, lb, ub, "local bounds");
2957 
2958  /* output lazy bound */
2959  lb = SCIPvarGetLbLazy(var);
2960  ub = SCIPvarGetUbLazy(var);
2961 
2962  /* only display the lazy bounds if they are different from [-infinity,infinity] */
2963  if( !SCIPsetIsInfinity(set, -lb) || !SCIPsetIsInfinity(set, ub) )
2964  printBounds(set, messagehdlr, file, lb, ub, "lazy bounds");
2965 
2966  /* global hole list */
2967  holelist = SCIPvarGetHolelistGlobal(var);
2968  printHolelist(set, messagehdlr, file, holelist, "global holes");
2969 
2970  /* local hole list */
2971  holelist = SCIPvarGetHolelistLocal(var);
2972  printHolelist(set, messagehdlr, file, holelist, "local holes");
2973  }
2974 
2975  /* fixings and aggregations */
2976  switch( SCIPvarGetStatus(var) )
2977  {
2979  case SCIP_VARSTATUS_LOOSE:
2980  case SCIP_VARSTATUS_COLUMN:
2981  break;
2982 
2983  case SCIP_VARSTATUS_FIXED:
2984  SCIPmessageFPrintInfo(messagehdlr, file, ", fixed:");
2985  if( SCIPsetIsInfinity(set, var->glbdom.lb) )
2986  SCIPmessageFPrintInfo(messagehdlr, file, "+inf");
2987  else if( SCIPsetIsInfinity(set, -var->glbdom.lb) )
2988  SCIPmessageFPrintInfo(messagehdlr, file, "-inf");
2989  else
2990  SCIPmessageFPrintInfo(messagehdlr, file, "%.15g", var->glbdom.lb);
2991  break;
2992 
2994  SCIPmessageFPrintInfo(messagehdlr, file, ", aggregated:");
2995  if( !SCIPsetIsZero(set, var->data.aggregate.constant) )
2996  SCIPmessageFPrintInfo(messagehdlr, file, " %.15g", var->data.aggregate.constant);
2997  SCIPmessageFPrintInfo(messagehdlr, file, " %+.15g<%s>", var->data.aggregate.scalar, SCIPvarGetName(var->data.aggregate.var));
2998  break;
2999 
3001  SCIPmessageFPrintInfo(messagehdlr, file, ", aggregated:");
3002  if( var->data.multaggr.nvars == 0 || !SCIPsetIsZero(set, var->data.multaggr.constant) )
3003  SCIPmessageFPrintInfo(messagehdlr, file, " %.15g", var->data.multaggr.constant);
3004  for( i = 0; i < var->data.multaggr.nvars; ++i )
3005  SCIPmessageFPrintInfo(messagehdlr, file, " %+.15g<%s>", var->data.multaggr.scalars[i], SCIPvarGetName(var->data.multaggr.vars[i]));
3006  break;
3007 
3009  SCIPmessageFPrintInfo(messagehdlr, file, ", negated: %.15g - <%s>", var->data.negate.constant, SCIPvarGetName(var->negatedvar));
3010  break;
3011 
3012  default:
3013  SCIPerrorMessage("unknown variable status\n");
3014  SCIPABORT();
3015  return SCIP_ERROR; /*lint !e527*/
3016  }
3017 
3018  SCIPmessageFPrintInfo(messagehdlr, file, "\n");
3019 
3020  return SCIP_OKAY;
3021 }
3022 
3023 /** issues a VARUNLOCKED event on the given variable */
3024 static
3026  SCIP_VAR* var, /**< problem variable to change */
3027  BMS_BLKMEM* blkmem, /**< block memory */
3028  SCIP_SET* set, /**< global SCIP settings */
3029  SCIP_EVENTQUEUE* eventqueue /**< event queue */
3030  )
3031 {
3032  SCIP_EVENT* event;
3033 
3034  assert(var != NULL);
3035  assert(var->nlocksdown <= 1 && var->nlocksup <= 1);
3036  assert(var->scip == set->scip);
3037 
3038  /* issue VARUNLOCKED event on variable */
3039  SCIP_CALL( SCIPeventCreateVarUnlocked(&event, blkmem, var) );
3040  SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, NULL, &event) );
3041 
3042  return SCIP_OKAY;
3043 }
3044 
3045 /** modifies lock numbers for rounding */
3047  SCIP_VAR* var, /**< problem variable */
3048  BMS_BLKMEM* blkmem, /**< block memory */
3049  SCIP_SET* set, /**< global SCIP settings */
3050  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3051  int addnlocksdown, /**< increase in number of rounding down locks */
3052  int addnlocksup /**< increase in number of rounding up locks */
3053  )
3054 {
3055  SCIP_VAR* lockvar;
3056 
3057  assert(var != NULL);
3058  assert(var->nlocksup >= 0);
3059  assert(var->nlocksdown >= 0);
3060  assert(var->scip == set->scip);
3061 
3062  if( addnlocksdown == 0 && addnlocksup == 0 )
3063  return SCIP_OKAY;
3064 
3065  SCIPsetDebugMsg(set, "add rounding locks %d/%d to variable <%s> (locks=%d/%d)\n",
3066  addnlocksdown, addnlocksup, var->name, var->nlocksdown, var->nlocksup);
3067 
3068  lockvar = var;
3069 
3070  while( TRUE ) /*lint !e716 */
3071  {
3072  assert(lockvar != NULL);
3073 
3074  switch( SCIPvarGetStatus(lockvar) )
3075  {
3077  if( lockvar->data.original.transvar != NULL )
3078  {
3079  lockvar = lockvar->data.original.transvar;
3080  break;
3081  }
3082  else
3083  {
3084  lockvar->nlocksdown += addnlocksdown;
3085  lockvar->nlocksup += addnlocksup;
3086 
3087  assert(lockvar->nlocksdown >= 0);
3088  assert(lockvar->nlocksup >= 0);
3089 
3090  return SCIP_OKAY;
3091  }
3092  case SCIP_VARSTATUS_LOOSE:
3093  case SCIP_VARSTATUS_COLUMN:
3094  case SCIP_VARSTATUS_FIXED:
3095  lockvar->nlocksdown += addnlocksdown;
3096  lockvar->nlocksup += addnlocksup;
3097 
3098  assert(lockvar->nlocksdown >= 0);
3099  assert(lockvar->nlocksup >= 0);
3100 
3101  if( lockvar->nlocksdown <= 1 && lockvar->nlocksup <= 1 )
3102  {
3103  SCIP_CALL( varEventVarUnlocked(lockvar, blkmem, set, eventqueue) );
3104  }
3105 
3106  return SCIP_OKAY;
3108  if( lockvar->data.aggregate.scalar < 0.0 )
3109  {
3110  int tmp = addnlocksup;
3111 
3112  addnlocksup = addnlocksdown;
3113  addnlocksdown = tmp;
3114  }
3115 
3116  lockvar = lockvar->data.aggregate.var;
3117  break;
3119  {
3120  int v;
3121 
3122  assert(!lockvar->donotmultaggr);
3123 
3124  for( v = lockvar->data.multaggr.nvars - 1; v >= 0; --v )
3125  {
3126  if( lockvar->data.multaggr.scalars[v] > 0.0 )
3127  {
3128  SCIP_CALL( SCIPvarAddLocks(lockvar->data.multaggr.vars[v], blkmem, set, eventqueue, addnlocksdown,
3129  addnlocksup) );
3130  }
3131  else
3132  {
3133  SCIP_CALL( SCIPvarAddLocks(lockvar->data.multaggr.vars[v], blkmem, set, eventqueue, addnlocksup,
3134  addnlocksdown) );
3135  }
3136  }
3137  return SCIP_OKAY;
3138  }
3140  {
3141  int tmp = addnlocksup;
3142 
3143  assert(lockvar->negatedvar != NULL);
3144  assert(SCIPvarGetStatus(lockvar->negatedvar) != SCIP_VARSTATUS_NEGATED);
3145  assert(lockvar->negatedvar->negatedvar == lockvar);
3146 
3147  addnlocksup = addnlocksdown;
3148  addnlocksdown = tmp;
3149 
3150  lockvar = lockvar->negatedvar;
3151  break;
3152  }
3153  default:
3154  SCIPerrorMessage("unknown variable status\n");
3155  return SCIP_INVALIDDATA;
3156  }
3157  }
3158 }
3159 
3160 /** gets number of locks for rounding down */
3162  SCIP_VAR* var /**< problem variable */
3163  )
3164 {
3165  int nlocks;
3166  int i;
3167 
3168  assert(var != NULL);
3169  assert(var->nlocksdown >= 0);
3170 
3171  switch( SCIPvarGetStatus(var) )
3172  {
3174  if( var->data.original.transvar != NULL )
3176  else
3177  return var->nlocksdown;
3178 
3179  case SCIP_VARSTATUS_LOOSE:
3180  case SCIP_VARSTATUS_COLUMN:
3181  case SCIP_VARSTATUS_FIXED:
3182  return var->nlocksdown;
3183 
3185  if( var->data.aggregate.scalar > 0.0 )
3186  return SCIPvarGetNLocksDown(var->data.aggregate.var);
3187  else
3188  return SCIPvarGetNLocksUp(var->data.aggregate.var);
3189 
3191  assert(!var->donotmultaggr);
3192  nlocks = 0;
3193  for( i = 0; i < var->data.multaggr.nvars; ++i )
3194  {
3195  if( var->data.multaggr.scalars[i] > 0.0 )
3196  nlocks += SCIPvarGetNLocksDown(var->data.multaggr.vars[i]);
3197  else
3198  nlocks += SCIPvarGetNLocksUp(var->data.multaggr.vars[i]);
3199  }
3200  return nlocks;
3201 
3203  assert(var->negatedvar != NULL);
3205  assert(var->negatedvar->negatedvar == var);
3206  return SCIPvarGetNLocksUp(var->negatedvar);
3207 
3208  default:
3209  SCIPerrorMessage("unknown variable status\n");
3210  SCIPABORT();
3211  return INT_MAX; /*lint !e527*/
3212  }
3213 }
3214 
3215 /** gets number of locks for rounding up */
3216 int SCIPvarGetNLocksUp(
3217  SCIP_VAR* var /**< problem variable */
3218  )
3219 {
3220  int nlocks;
3221  int i;
3222 
3223  assert(var != NULL);
3224  assert(var->nlocksup >= 0);
3225 
3226  switch( SCIPvarGetStatus(var) )
3227  {
3229  if( var->data.original.transvar != NULL )
3231  else
3232  return var->nlocksup;
3233 
3234  case SCIP_VARSTATUS_LOOSE:
3235  case SCIP_VARSTATUS_COLUMN:
3236  case SCIP_VARSTATUS_FIXED:
3237  return var->nlocksup;
3238 
3240  if( var->data.aggregate.scalar > 0.0 )
3241  return SCIPvarGetNLocksUp(var->data.aggregate.var);
3242  else
3243  return SCIPvarGetNLocksDown(var->data.aggregate.var);
3244 
3246  assert(!var->donotmultaggr);
3247  nlocks = 0;
3248  for( i = 0; i < var->data.multaggr.nvars; ++i )
3249  {
3250  if( var->data.multaggr.scalars[i] > 0.0 )
3251  nlocks += SCIPvarGetNLocksUp(var->data.multaggr.vars[i]);
3252  else
3253  nlocks += SCIPvarGetNLocksDown(var->data.multaggr.vars[i]);
3254  }
3255  return nlocks;
3256 
3258  assert(var->negatedvar != NULL);
3260  assert(var->negatedvar->negatedvar == var);
3261  return SCIPvarGetNLocksDown(var->negatedvar);
3262 
3263  default:
3264  SCIPerrorMessage("unknown variable status\n");
3265  SCIPABORT();
3266  return INT_MAX; /*lint !e527*/
3267  }
3268 }
3269 
3270 /** is it possible, to round variable down and stay feasible? */
3272  SCIP_VAR* var /**< problem variable */
3273  )
3274 {
3275  return (SCIPvarGetNLocksDown(var) == 0);
3276 }
3277 
3278 /** is it possible, to round variable up and stay feasible? */
3280  SCIP_VAR* var /**< problem variable */
3281  )
3282 {
3283  return (SCIPvarGetNLocksUp(var) == 0);
3284 }
3285 
3286 /** gets and captures transformed variable of a given variable; if the variable is not yet transformed,
3287  * a new transformed variable for this variable is created
3288  */
3290  SCIP_VAR* origvar, /**< original problem variable */
3291  BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
3292  SCIP_SET* set, /**< global SCIP settings */
3293  SCIP_STAT* stat, /**< problem statistics */
3294  SCIP_OBJSENSE objsense, /**< objective sense of original problem; transformed is always MINIMIZE */
3295  SCIP_VAR** transvar /**< pointer to store the transformed variable */
3296  )
3297 {
3298  char name[SCIP_MAXSTRLEN];
3299 
3300  assert(origvar != NULL);
3301  assert(origvar->scip == set->scip);
3302  assert(SCIPvarGetStatus(origvar) == SCIP_VARSTATUS_ORIGINAL);
3303  assert(SCIPsetIsEQ(set, origvar->glbdom.lb, origvar->locdom.lb));
3304  assert(SCIPsetIsEQ(set, origvar->glbdom.ub, origvar->locdom.ub));
3305  assert(origvar->vlbs == NULL);
3306  assert(origvar->vubs == NULL);
3307  assert(transvar != NULL);
3308 
3309  /* check if variable is already transformed */
3310  if( origvar->data.original.transvar != NULL )
3311  {
3312  *transvar = origvar->data.original.transvar;
3313  SCIPvarCapture(*transvar);
3314  }
3315  else
3316  {
3317  /* create transformed variable */
3318  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "t_%s", origvar->name);
3319  SCIP_CALL( SCIPvarCreateTransformed(transvar, blkmem, set, stat, name,
3320  origvar->glbdom.lb, origvar->glbdom.ub, (SCIP_Real)objsense * origvar->obj,
3321  SCIPvarGetType(origvar), origvar->initial, origvar->removable,
3322  origvar->vardelorig, origvar->vartrans, origvar->vardeltrans, origvar->varcopy, NULL) );
3323 
3324  /* copy the branch factor and priority */
3325  (*transvar)->branchfactor = origvar->branchfactor;
3326  (*transvar)->branchpriority = origvar->branchpriority;
3327  (*transvar)->branchdirection = origvar->branchdirection; /*lint !e732*/
3328 
3329  /* duplicate hole lists */
3330  SCIP_CALL( holelistDuplicate(&(*transvar)->glbdom.holelist, blkmem, set, origvar->glbdom.holelist) );
3331  SCIP_CALL( holelistDuplicate(&(*transvar)->locdom.holelist, blkmem, set, origvar->locdom.holelist) );
3332 
3333  /* link original and transformed variable */
3334  origvar->data.original.transvar = *transvar;
3335  SCIP_CALL( varAddParent(*transvar, blkmem, set, origvar) );
3336 
3337  /* copy rounding locks */
3338  (*transvar)->nlocksdown = origvar->nlocksdown;
3339  (*transvar)->nlocksup = origvar->nlocksup;
3340  assert((*transvar)->nlocksdown >= 0);
3341  assert((*transvar)->nlocksup >= 0);
3342 
3343  /* copy doNotMultiaggr status */
3344  (*transvar)->donotmultaggr = origvar->donotmultaggr;
3345 
3346  /* copy lazy bounds */
3347  (*transvar)->lazylb = origvar->lazylb;
3348  (*transvar)->lazyub = origvar->lazyub;
3349 
3350  /* transfer eventual variable statistics; do not update global statistics, because this has been done
3351  * when original variable was created
3352  */
3353  SCIPhistoryUnite((*transvar)->history, origvar->history, FALSE);
3354 
3355  /* transform user data */
3356  if( origvar->vartrans != NULL )
3357  {
3358  SCIP_CALL( origvar->vartrans(set->scip, origvar, origvar->vardata, *transvar, &(*transvar)->vardata) );
3359  }
3360  else
3361  (*transvar)->vardata = origvar->vardata;
3362  }
3363 
3364  SCIPsetDebugMsg(set, "transformed variable: <%s>[%p] -> <%s>[%p]\n", origvar->name, (void*)origvar, (*transvar)->name, (void*)*transvar);
3365 
3366  return SCIP_OKAY;
3367 }
3368 
3369 /** gets corresponding transformed variable of an original or negated original variable */
3371  SCIP_VAR* origvar, /**< original problem variable */
3372  BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
3373  SCIP_SET* set, /**< global SCIP settings */
3374  SCIP_STAT* stat, /**< problem statistics */
3375  SCIP_VAR** transvar /**< pointer to store the transformed variable, or NULL if not existing yet */
3376  )
3377 {
3378  assert(origvar != NULL);
3380  assert(origvar->scip == set->scip);
3381 
3382  if( SCIPvarGetStatus(origvar) == SCIP_VARSTATUS_NEGATED )
3383  {
3384  assert(origvar->negatedvar != NULL);
3386 
3387  if( origvar->negatedvar->data.original.transvar == NULL )
3388  *transvar = NULL;
3389  else
3390  {
3391  SCIP_CALL( SCIPvarNegate(origvar->negatedvar->data.original.transvar, blkmem, set, stat, transvar) );
3392  }
3393  }
3394  else
3395  *transvar = origvar->data.original.transvar;
3396 
3397  return SCIP_OKAY;
3398 }
3399 
3400 /** converts loose transformed variable into column variable, creates LP column */
3402  SCIP_VAR* var, /**< problem variable */
3403  BMS_BLKMEM* blkmem, /**< block memory */
3404  SCIP_SET* set, /**< global SCIP settings */
3405  SCIP_STAT* stat, /**< problem statistics */
3406  SCIP_PROB* prob, /**< problem data */
3407  SCIP_LP* lp /**< current LP data */
3408  )
3409 {
3410  assert(var != NULL);
3411  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
3412  assert(var->scip == set->scip);
3413 
3414  SCIPsetDebugMsg(set, "creating column for variable <%s>\n", var->name);
3415 
3416  /* switch variable status */
3417  var->varstatus = SCIP_VARSTATUS_COLUMN; /*lint !e641*/
3418 
3419  /* create column of variable */
3420  SCIP_CALL( SCIPcolCreate(&var->data.col, blkmem, set, stat, var, 0, NULL, NULL, var->removable) );
3421 
3422  if( var->probindex != -1 )
3423  {
3424  /* inform problem about the variable's status change */
3425  SCIP_CALL( SCIPprobVarChangedStatus(prob, blkmem, set, NULL, NULL, var) );
3426 
3427  /* inform LP, that problem variable is now a column variable and no longer loose */
3428  SCIP_CALL( SCIPlpUpdateVarColumn(lp, set, var) );
3429  }
3430 
3431  return SCIP_OKAY;
3432 }
3433 
3434 /** converts column transformed variable back into loose variable, frees LP column */
3436  SCIP_VAR* var, /**< problem variable */
3437  BMS_BLKMEM* blkmem, /**< block memory */
3438  SCIP_SET* set, /**< global SCIP settings */
3439  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3440  SCIP_PROB* prob, /**< problem data */
3441  SCIP_LP* lp /**< current LP data */
3442  )
3443 {
3444  assert(var != NULL);
3445  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
3446  assert(var->scip == set->scip);
3447  assert(var->data.col != NULL);
3448  assert(var->data.col->lppos == -1);
3449  assert(var->data.col->lpipos == -1);
3450 
3451  SCIPsetDebugMsg(set, "deleting column for variable <%s>\n", var->name);
3452 
3453  /* free column of variable */
3454  SCIP_CALL( SCIPcolFree(&var->data.col, blkmem, set, eventqueue, lp) );
3455 
3456  /* switch variable status */
3457  var->varstatus = SCIP_VARSTATUS_LOOSE; /*lint !e641*/
3458 
3459  if( var->probindex != -1 )
3460  {
3461  /* inform problem about the variable's status change */
3462  SCIP_CALL( SCIPprobVarChangedStatus(prob, blkmem, set, NULL, NULL, var) );
3463 
3464  /* inform LP, that problem variable is now a loose variable and no longer a column */
3465  SCIP_CALL( SCIPlpUpdateVarLoose(lp, set, var) );
3466  }
3467 
3468  return SCIP_OKAY;
3469 }
3470 
3471 /** issues a VARFIXED event on the given variable and all its parents (except ORIGINAL parents);
3472  * the event issuing on the parents is necessary, because unlike with bound changes, the parent variables
3473  * are not informed about a fixing of an active variable they are pointing to
3474  */
3475 static
3477  SCIP_VAR* var, /**< problem variable to change */
3478  BMS_BLKMEM* blkmem, /**< block memory */
3479  SCIP_SET* set, /**< global SCIP settings */
3480  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3481  int fixeventtype /**< is this event a fixation(0), an aggregation(1), or a
3482  * multi-aggregation(2)
3483  */
3484  )
3485 {
3486  SCIP_EVENT* event;
3487  SCIP_VARSTATUS varstatus;
3488  int i;
3489 
3490  assert(var != NULL);
3491  assert(var->scip == set->scip);
3492  assert(0 <= fixeventtype && fixeventtype <= 2);
3493 
3494  /* issue VARFIXED event on variable */
3495  SCIP_CALL( SCIPeventCreateVarFixed(&event, blkmem, var) );
3496  SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, NULL, &event) );
3497 
3498 #ifndef NDEBUG
3499  for( i = var->nparentvars -1; i >= 0; --i )
3500  {
3502  }
3503 #endif
3504 
3505  switch( fixeventtype )
3506  {
3507  case 0:
3508  /* process all parents of a fixed variable */
3509  for( i = var->nparentvars - 1; i >= 0; --i )
3510  {
3511  varstatus = SCIPvarGetStatus(var->parentvars[i]);
3512 
3513  assert(varstatus != SCIP_VARSTATUS_FIXED);
3514 
3515  /* issue event on all not yet fixed parent variables, (that should already issued this event) except the original
3516  * one
3517  */
3518  if( varstatus != SCIP_VARSTATUS_ORIGINAL )
3519  {
3520  SCIP_CALL( varEventVarFixed(var->parentvars[i], blkmem, set, eventqueue, fixeventtype) );
3521  }
3522  }
3523  break;
3524  case 1:
3525  /* process all parents of a aggregated variable */
3526  for( i = var->nparentvars - 1; i >= 0; --i )
3527  {
3528  varstatus = SCIPvarGetStatus(var->parentvars[i]);
3529 
3530  assert(varstatus != SCIP_VARSTATUS_FIXED);
3531 
3532  /* issue event for not aggregated parent variable, because for these and its parents the var event was already
3533  * issued(, except the original one)
3534  *
3535  * @note that even before an aggregated parent variable, there might be variables, for which the vent was not
3536  * yet issued
3537  */
3538  if( varstatus == SCIP_VARSTATUS_AGGREGATED )
3539  continue;
3540 
3541  if( varstatus != SCIP_VARSTATUS_ORIGINAL )
3542  {
3543  SCIP_CALL( varEventVarFixed(var->parentvars[i], blkmem, set, eventqueue, fixeventtype) );
3544  }
3545  }
3546  break;
3547  case 2:
3548  /* process all parents of a aggregated variable */
3549  for( i = var->nparentvars - 1; i >= 0; --i )
3550  {
3551  varstatus = SCIPvarGetStatus(var->parentvars[i]);
3552 
3553  assert(varstatus != SCIP_VARSTATUS_FIXED);
3554 
3555  /* issue event on all parent variables except the original one */
3556  if( varstatus != SCIP_VARSTATUS_ORIGINAL )
3557  {
3558  SCIP_CALL( varEventVarFixed(var->parentvars[i], blkmem, set, eventqueue, fixeventtype) );
3559  }
3560  }
3561  break;
3562  default:
3563  SCIPerrorMessage("unknown variable fixation event origin\n");
3564  return SCIP_INVALIDDATA;
3565  }
3566 
3567  return SCIP_OKAY;
3568 }
3569 
3570 /** converts variable into fixed variable */
3572  SCIP_VAR* var, /**< problem variable */
3573  BMS_BLKMEM* blkmem, /**< block memory */
3574  SCIP_SET* set, /**< global SCIP settings */
3575  SCIP_STAT* stat, /**< problem statistics */
3576  SCIP_PROB* transprob, /**< tranformed problem data */
3577  SCIP_PROB* origprob, /**< original problem data */
3578  SCIP_PRIMAL* primal, /**< primal data */
3579  SCIP_TREE* tree, /**< branch and bound tree */
3580  SCIP_REOPT* reopt, /**< reoptimization data structure */
3581  SCIP_LP* lp, /**< current LP data */
3582  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3583  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3584  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3585  SCIP_Real fixedval, /**< value to fix variable at */
3586  SCIP_Bool* infeasible, /**< pointer to store whether the fixing is infeasible */
3587  SCIP_Bool* fixed /**< pointer to store whether the fixing was performed (variable was unfixed) */
3588  )
3589 {
3590  SCIP_Real obj;
3591  SCIP_Real childfixedval;
3592 
3593  assert(var != NULL);
3594  assert(var->scip == set->scip);
3595  assert(SCIPsetIsEQ(set, var->glbdom.lb, var->locdom.lb));
3596  assert(SCIPsetIsEQ(set, var->glbdom.ub, var->locdom.ub));
3597  assert(infeasible != NULL);
3598  assert(fixed != NULL);
3599 
3600  SCIPsetDebugMsg(set, "fix variable <%s>[%g,%g] to %g\n", var->name, var->glbdom.lb, var->glbdom.ub, fixedval);
3601 
3602  *infeasible = FALSE;
3603  *fixed = FALSE;
3604 
3606  {
3607  *infeasible = !SCIPsetIsFeasEQ(set, fixedval, var->locdom.lb);
3608  SCIPsetDebugMsg(set, " -> variable already fixed to %g (fixedval=%g): infeasible=%u\n", var->locdom.lb, fixedval, *infeasible);
3609  return SCIP_OKAY;
3610  }
3611  else if( (SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS && !SCIPsetIsFeasIntegral(set, fixedval))
3612  || SCIPsetIsFeasLT(set, fixedval, var->locdom.lb)
3613  || SCIPsetIsFeasGT(set, fixedval, var->locdom.ub) )
3614  {
3615  SCIPsetDebugMsg(set, " -> fixing infeasible: locdom=[%g,%g], fixedval=%g\n", var->locdom.lb, var->locdom.ub, fixedval);
3616  *infeasible = TRUE;
3617  return SCIP_OKAY;
3618  }
3619 
3620  switch( SCIPvarGetStatus(var) )
3621  {
3623  if( var->data.original.transvar == NULL )
3624  {
3625  SCIPerrorMessage("cannot fix an untransformed original variable\n");
3626  return SCIP_INVALIDDATA;
3627  }
3628  SCIP_CALL( SCIPvarFix(var->data.original.transvar, blkmem, set, stat, transprob, origprob, primal, tree, reopt,
3629  lp, branchcand, eventqueue, cliquetable, fixedval, infeasible, fixed) );
3630  break;
3631 
3632  case SCIP_VARSTATUS_LOOSE:
3633  assert(!SCIPeventqueueIsDelayed(eventqueue)); /* otherwise, the pseudo objective value update gets confused */
3634 
3635  /* set the fixed variable's objective value to 0.0 */
3636  obj = var->obj;
3637  SCIP_CALL( SCIPvarChgObj(var, blkmem, set, transprob, primal, lp, eventqueue, 0.0) );
3638 
3639  /* since we change the variable type form loose to fixed, we have to adjust the number of loose
3640  * variables in the LP data structure; the loose objective value (looseobjval) in the LP data structure, however,
3641  * gets adjusted automatically, due to the event SCIP_EVENTTYPE_OBJCHANGED which dropped in the moment where the
3642  * objective of this variable is set to zero
3643  */
3644  SCIPlpDecNLoosevars(lp);
3645 
3646  /* change variable's bounds to fixed value (thereby removing redundant implications and variable bounds) */
3647  holelistFree(&var->glbdom.holelist, blkmem);
3648  holelistFree(&var->locdom.holelist, blkmem);
3649  SCIP_CALL( SCIPvarChgLbGlobal(var, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, fixedval) );
3650  SCIP_CALL( SCIPvarChgUbGlobal(var, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, fixedval) );
3651 
3652  /* explicitly set variable's bounds, even if the fixed value is in epsilon range of the old bound */
3653  var->glbdom.lb = fixedval;
3654  var->glbdom.ub = fixedval;
3655  var->locdom.lb = fixedval;
3656  var->locdom.ub = fixedval;
3657 
3658  /* delete implications and variable bounds information */
3659  SCIP_CALL( SCIPvarRemoveCliquesImplicsVbs(var, blkmem, cliquetable, set, FALSE, FALSE, TRUE) );
3660  assert(var->vlbs == NULL);
3661  assert(var->vubs == NULL);
3662  assert(var->implics == NULL);
3663  assert(var->cliquelist == NULL);
3664 
3665  /* clear the history of the variable */
3666  SCIPhistoryReset(var->history);
3668 
3669  /* convert variable into fixed variable */
3670  var->varstatus = SCIP_VARSTATUS_FIXED; /*lint !e641*/
3671 
3672  /* inform problem about the variable's status change */
3673  if( var->probindex != -1 )
3674  {
3675  SCIP_CALL( SCIPprobVarChangedStatus(transprob, blkmem, set, branchcand, cliquetable, var) );
3676  }
3677 
3678  /* reset the objective value of the fixed variable, thus adjusting the problem's objective offset */
3679  SCIP_CALL( SCIPvarAddObj(var, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, eventqueue, obj) );
3680 
3681  /* issue VARFIXED event */
3682  SCIP_CALL( varEventVarFixed(var, blkmem, set, eventqueue, 0) );
3683 
3684  *fixed = TRUE;
3685  break;
3686 
3687  case SCIP_VARSTATUS_COLUMN:
3688  SCIPerrorMessage("cannot fix a column variable\n");
3689  return SCIP_INVALIDDATA;
3690 
3691  case SCIP_VARSTATUS_FIXED:
3692  SCIPerrorMessage("cannot fix a fixed variable again\n"); /*lint !e527*/
3693  SCIPABORT(); /* case is already handled in earlier if condition */
3694  return SCIP_INVALIDDATA; /*lint !e527*/
3695 
3697  /* fix aggregation variable y in x = a*y + c, instead of fixing x directly */
3698  assert(SCIPsetIsZero(set, var->obj));
3699  assert(!SCIPsetIsZero(set, var->data.aggregate.scalar));
3700  if( SCIPsetIsInfinity(set, fixedval) || SCIPsetIsInfinity(set, -fixedval) )
3701  childfixedval = (var->data.aggregate.scalar < 0.0 ? -fixedval : fixedval);
3702  else
3703  childfixedval = (fixedval - var->data.aggregate.constant)/var->data.aggregate.scalar;
3704  SCIP_CALL( SCIPvarFix(var->data.aggregate.var, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp,
3705  branchcand, eventqueue, cliquetable, childfixedval, infeasible, fixed) );
3706  break;
3707 
3709  SCIPerrorMessage("cannot fix a multiple aggregated variable\n");
3710  SCIPABORT();
3711  return SCIP_INVALIDDATA; /*lint !e527*/
3712 
3714  /* fix negation variable x in x' = offset - x, instead of fixing x' directly */
3715  assert(SCIPsetIsZero(set, var->obj));
3716  assert(var->negatedvar != NULL);
3718  assert(var->negatedvar->negatedvar == var);
3719  SCIP_CALL( SCIPvarFix(var->negatedvar, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp,
3720  branchcand, eventqueue, cliquetable, var->data.negate.constant - fixedval, infeasible, fixed) );
3721  break;
3722 
3723  default:
3724  SCIPerrorMessage("unknown variable status\n");
3725  return SCIP_INVALIDDATA;
3726  }
3727 
3728  return SCIP_OKAY;
3729 }
3730 
3731 /** transforms given variables, scalars and constant to the corresponding active variables, scalars and constant
3732  *
3733  * If the number of needed active variables is greater than the available slots in the variable array, nothing happens except
3734  * that the required size is stored in the corresponding variable; hence, if afterwards the required size is greater than the
3735  * available slots (varssize), nothing happens; otherwise, the active variable representation is stored in the arrays.
3736  *
3737  * The reason for this approach is that we cannot reallocate memory, since we do not know how the
3738  * memory has been allocated (e.g., by a C++ 'new' or SCIP functions).
3739  */
3741  SCIP_SET* set, /**< global SCIP settings */
3742  SCIP_VAR** vars, /**< variable array to get active variables */
3743  SCIP_Real* scalars, /**< scalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c */
3744  int* nvars, /**< pointer to number of variables and values in vars and scalars array */
3745  int varssize, /**< available slots in vars and scalars array */
3746  SCIP_Real* constant, /**< pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c */
3747  int* requiredsize, /**< pointer to store the required array size for the active variables */
3748  SCIP_Bool mergemultiples /**< should multiple occurrences of a var be replaced by a single coeff? */
3749  )
3750 {
3751  SCIP_VAR** activevars;
3752  SCIP_Real* activescalars;
3753  int nactivevars;
3754  SCIP_Real activeconstant;
3755  SCIP_Bool activeconstantinf;
3756  int activevarssize;
3757 
3758  SCIP_VAR* var;
3759  SCIP_Real scalar;
3760  int v;
3761 
3762  SCIP_VAR** tmpvars;
3763  SCIP_VAR** multvars;
3764  SCIP_Real* tmpscalars;
3765  SCIP_Real* multscalars;
3766  int tmpvarssize;
3767  int ntmpvars;
3768  int nmultvars;
3769 
3770  SCIP_VAR* multvar;
3771  SCIP_Real multscalar;
3772  SCIP_Real multconstant;
3773  int pos;
3774 
3775  int noldtmpvars;
3776 
3777  SCIP_VAR** tmpvars2;
3778  SCIP_Real* tmpscalars2;
3779  int tmpvarssize2;
3780  int ntmpvars2;
3781 
3782  assert(set != NULL);
3783  assert(nvars != NULL);
3784  assert(scalars != NULL || *nvars == 0);
3785  assert(constant != NULL);
3786  assert(requiredsize != NULL);
3787  assert(*nvars <= varssize);
3788 
3789  *requiredsize = 0;
3790 
3791  if( *nvars == 0 )
3792  return SCIP_OKAY;
3793 
3794  assert(vars != NULL);
3795 
3796  /* handle the "easy" case of just one variable and avoid memory allocation if the variable is already active */
3797  if( *nvars == 1 && (vars[0]->varstatus == ((int) SCIP_VARSTATUS_COLUMN) || vars[0]->varstatus == ((int) SCIP_VARSTATUS_LOOSE)) )
3798  {
3799  *requiredsize = 1;
3800 
3801  return SCIP_OKAY;
3802  }
3803 
3804  nactivevars = 0;
3805  activeconstant = 0.0;
3806  activeconstantinf = FALSE;
3807  activevarssize = (*nvars) * 2;
3808  ntmpvars = *nvars;
3809  tmpvarssize = *nvars;
3810 
3811  tmpvarssize2 = 1;
3812 
3813  /* allocate temporary memory */
3814  SCIP_CALL( SCIPsetAllocBufferArray(set, &tmpvars2, tmpvarssize2) );
3815  SCIP_CALL( SCIPsetAllocBufferArray(set, &tmpscalars2, tmpvarssize2) );
3816  SCIP_CALL( SCIPsetAllocBufferArray(set, &activevars, activevarssize) );
3817  SCIP_CALL( SCIPsetAllocBufferArray(set, &activescalars, activevarssize) );
3818  SCIP_CALL( SCIPsetDuplicateBufferArray(set, &tmpvars, vars, ntmpvars) );
3819  SCIP_CALL( SCIPsetDuplicateBufferArray(set, &tmpscalars, scalars, ntmpvars) );
3820 
3821  /* to avoid unnecessary expanding of variable arrays while disaggregating several variables multiple times combine same variables
3822  * first, first get all corresponding variables with status loose, column, multaggr or fixed
3823  */
3824  for( v = ntmpvars - 1; v >= 0; --v )
3825  {
3826  var = tmpvars[v];
3827  scalar = tmpscalars[v];
3828 
3829  assert(var != NULL);
3830  /* transforms given variable, scalar and constant to the corresponding active, fixed, or
3831  * multi-aggregated variable, scalar and constant; if the variable resolves to a fixed
3832  * variable, "scalar" will be 0.0 and the value of the sum will be stored in "constant".
3833  */
3834  SCIP_CALL( SCIPvarGetProbvarSum(&var, set, &scalar, &activeconstant) );
3835  assert(var != NULL);
3836 
3837  assert(SCIPsetIsInfinity(set, activeconstant) == (activeconstant == SCIPsetInfinity(set))); /*lint !e777*/
3838  assert(SCIPsetIsInfinity(set, -activeconstant) == (activeconstant == -SCIPsetInfinity(set))); /*lint !e777*/
3839 
3840  activeconstantinf = SCIPsetIsInfinity(set, activeconstant) || SCIPsetIsInfinity(set, -activeconstant);
3841 
3842  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE
3843  || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN
3846 
3847  tmpvars[v] = var;
3848  tmpscalars[v] = scalar;
3849  }
3850  noldtmpvars = ntmpvars;
3851 
3852  /* sort all variables to combine equal variables easily */
3853  SCIPsortPtrReal((void**)tmpvars, tmpscalars, SCIPvarComp, ntmpvars);
3854  for( v = ntmpvars - 1; v > 0; --v )
3855  {
3856  /* combine same variables */
3857  if( SCIPvarCompare(tmpvars[v], tmpvars[v - 1]) == 0 )
3858  {
3859  tmpscalars[v - 1] += tmpscalars[v];
3860  --ntmpvars;
3861  tmpvars[v] = tmpvars[ntmpvars];
3862  tmpscalars[v] = tmpscalars[ntmpvars];
3863  }
3864  }
3865  /* sort all variables again to combine equal variables later on */
3866  if( noldtmpvars > ntmpvars )
3867  SCIPsortPtrReal((void**)tmpvars, tmpscalars, SCIPvarComp, ntmpvars);
3868 
3869  /* collect for each variable the representation in active variables */
3870  while( ntmpvars >= 1 )
3871  {
3872  --ntmpvars;
3873  ntmpvars2 = 0;
3874  var = tmpvars[ntmpvars];
3875  scalar = tmpscalars[ntmpvars];
3876 
3877  assert(var != NULL);
3878 
3879  /* TODO: maybe we should test here on SCIPsetIsZero() instead of 0.0 */
3880  if( scalar == 0.0 )
3881  continue;
3882 
3883  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE
3884  || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN
3887 
3888  switch( SCIPvarGetStatus(var) )
3889  {
3890  case SCIP_VARSTATUS_LOOSE:
3891  case SCIP_VARSTATUS_COLUMN:
3892  /* x = a*y + c */
3893  if( nactivevars >= activevarssize )
3894  {
3895  activevarssize *= 2;
3896  SCIP_CALL( SCIPsetReallocBufferArray(set, &activevars, activevarssize) );
3897  SCIP_CALL( SCIPsetReallocBufferArray(set, &activescalars, activevarssize) );
3898  assert(nactivevars < activevarssize);
3899  }
3900  activevars[nactivevars] = var;
3901  activescalars[nactivevars] = scalar;
3902  nactivevars++;
3903  break;
3904 
3906  /* x = a_1*y_1 + ... + a_n*y_n + c */
3907  nmultvars = var->data.multaggr.nvars;
3908  multvars = var->data.multaggr.vars;
3909  multscalars = var->data.multaggr.scalars;
3910 
3911  if( nmultvars + ntmpvars > tmpvarssize )
3912  {
3913  while( nmultvars + ntmpvars > tmpvarssize )
3914  tmpvarssize *= 2;
3915  SCIP_CALL( SCIPsetReallocBufferArray(set, &tmpvars, tmpvarssize) );
3916  SCIP_CALL( SCIPsetReallocBufferArray(set, &tmpscalars, tmpvarssize) );
3917  assert(nmultvars + ntmpvars <= tmpvarssize);
3918  }
3919 
3920  if( nmultvars > tmpvarssize2 )
3921  {
3922  while( nmultvars > tmpvarssize2 )
3923  tmpvarssize2 *= 2;
3924  SCIP_CALL( SCIPsetReallocBufferArray(set, &tmpvars2, tmpvarssize2) );
3925  SCIP_CALL( SCIPsetReallocBufferArray(set, &tmpscalars2, tmpvarssize2) );
3926  assert(nmultvars <= tmpvarssize2);
3927  }
3928 
3929  --nmultvars;
3930 
3931  for( ; nmultvars >= 0; --nmultvars )
3932  {
3933  multvar = multvars[nmultvars];
3934  multscalar = multscalars[nmultvars];
3935  multconstant = 0;
3936 
3937  assert(multvar != NULL);
3938  SCIP_CALL( SCIPvarGetProbvarSum(&multvar, set, &multscalar, &multconstant) );
3939  assert(multvar != NULL);
3940 
3941  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE
3942  || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN
3945 
3946  if( !activeconstantinf )
3947  {
3948  assert(!SCIPsetIsInfinity(set, scalar) && !SCIPsetIsInfinity(set, -scalar));
3949 
3950  if( SCIPsetIsInfinity(set, multconstant) || SCIPsetIsInfinity(set, -multconstant) )
3951  {
3952  assert(scalar != 0.0);
3953  if( scalar * multconstant > 0.0 )
3954  {
3955  activeconstant = SCIPsetInfinity(set);
3956  activeconstantinf = TRUE;
3957  }
3958  else
3959  {
3960  activeconstant = -SCIPsetInfinity(set);
3961  activeconstantinf = TRUE;
3962  }
3963  }
3964  else
3965  activeconstant += scalar * multconstant;
3966  }
3967 #ifndef NDEBUG
3968  else
3969  {
3970  assert(!SCIPsetIsInfinity(set, activeconstant) || !(scalar * multconstant < 0.0 &&
3971  (SCIPsetIsInfinity(set, multconstant) || SCIPsetIsInfinity(set, -multconstant))));
3972  assert(!SCIPsetIsInfinity(set, -activeconstant) || !(scalar * multconstant > 0.0 &&
3973  (SCIPsetIsInfinity(set, multconstant) || SCIPsetIsInfinity(set, -multconstant))));
3974  }
3975 #endif
3976 
3977  if( SCIPsortedvecFindPtr((void**)tmpvars, SCIPvarComp, multvar, ntmpvars, &pos) )
3978  {
3979  assert(SCIPvarCompare(tmpvars[pos], multvar) == 0);
3980  tmpscalars[pos] += scalar * multscalar;
3981  }
3982  else
3983  {
3984  tmpvars2[ntmpvars2] = multvar;
3985  tmpscalars2[ntmpvars2] = scalar * multscalar;
3986  ++(ntmpvars2);
3987  assert(ntmpvars2 <= tmpvarssize2);
3988  }
3989  }
3990 
3991  /* sort all variables to combine equal variables easily */
3992  SCIPsortPtrReal((void**)tmpvars2, tmpscalars2, SCIPvarComp, ntmpvars2);
3993  for( v = ntmpvars2 - 1; v > 0; --v )
3994  {
3995  /* combine same variables */
3996  if( SCIPvarCompare(tmpvars2[v], tmpvars2[v - 1]) == 0 )
3997  {
3998  tmpscalars2[v - 1] += tmpscalars2[v];
3999  --ntmpvars2;
4000  tmpvars2[v] = tmpvars2[ntmpvars2];
4001  tmpscalars2[v] = tmpscalars2[ntmpvars2];
4002  }
4003  }
4004 
4005  for( v = 0; v < ntmpvars2; ++v )
4006  {
4007  tmpvars[ntmpvars] = tmpvars2[v];
4008  tmpscalars[ntmpvars] = tmpscalars2[v];
4009  ++(ntmpvars);
4010  assert(ntmpvars <= tmpvarssize);
4011  }
4012  SCIPsortPtrReal((void**)tmpvars, tmpscalars, SCIPvarComp, ntmpvars);
4013 
4014  if( !activeconstantinf )
4015  {
4016  assert(!SCIPsetIsInfinity(set, scalar) && !SCIPsetIsInfinity(set, -scalar));
4017 
4018  multconstant = SCIPvarGetMultaggrConstant(var);
4019 
4020  if( SCIPsetIsInfinity(set, multconstant) || SCIPsetIsInfinity(set, -multconstant) )
4021  {
4022  assert(scalar != 0.0);
4023  if( scalar * multconstant > 0.0 )
4024  {
4025  activeconstant = SCIPsetInfinity(set);
4026  activeconstantinf = TRUE;
4027  }
4028  else
4029  {
4030  activeconstant = -SCIPsetInfinity(set);
4031  activeconstantinf = TRUE;
4032  }
4033  }
4034  else
4035  activeconstant += scalar * multconstant;
4036  }
4037 #ifndef NDEBUG
4038  else
4039  {
4040  multconstant = SCIPvarGetMultaggrConstant(var);
4041  assert(!SCIPsetIsInfinity(set, activeconstant) || !(scalar * multconstant < 0.0 &&
4042  (SCIPsetIsInfinity(set, multconstant) || SCIPsetIsInfinity(set, -multconstant))));
4043  assert(!SCIPsetIsInfinity(set, -activeconstant) || !(scalar * multconstant > 0.0 &&
4044  (SCIPsetIsInfinity(set, multconstant) || SCIPsetIsInfinity(set, -multconstant))));
4045  }
4046 #endif
4047  break;
4048 
4049  case SCIP_VARSTATUS_FIXED:
4053  default:
4054  /* case x = c, but actually we should not be here, since SCIPvarGetProbvarSum() returns a scalar of 0.0 for
4055  * fixed variables and is handled already
4056  */
4057  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED);
4058  assert(SCIPsetIsZero(set, var->glbdom.lb) && SCIPsetIsEQ(set, var->glbdom.lb, var->glbdom.ub));
4059  }
4060  }
4061 
4062  if( mergemultiples )
4063  {
4064  /* sort variable and scalar array by variable index */
4065  SCIPsortPtrReal((void**)activevars, activescalars, SCIPvarComp, nactivevars);
4066 
4067  /* eliminate duplicates and count required size */
4068  v = nactivevars - 1;
4069  while( v > 0 )
4070  {
4071  /* combine both variable since they are the same */
4072  if( SCIPvarCompare(activevars[v - 1], activevars[v]) == 0 )
4073  {
4074  if( activescalars[v - 1] + activescalars[v] != 0.0 )
4075  {
4076  activescalars[v - 1] += activescalars[v];
4077  --nactivevars;
4078  activevars[v] = activevars[nactivevars];
4079  activescalars[v] = activescalars[nactivevars];
4080  }
4081  else
4082  {
4083  --nactivevars;
4084  activevars[v] = activevars[nactivevars];
4085  activescalars[v] = activescalars[nactivevars];
4086  --nactivevars;
4087  --v;
4088  activevars[v] = activevars[nactivevars];
4089  activescalars[v] = activescalars[nactivevars];
4090  }
4091  }
4092  --v;
4093  }
4094  }
4095  *requiredsize = nactivevars;
4096 
4097  if( varssize >= *requiredsize )
4098  {
4099  assert(vars != NULL);
4100 
4101  *nvars = *requiredsize;
4102 
4103  if( !SCIPsetIsInfinity(set, *constant) && !SCIPsetIsInfinity(set, -(*constant)) )
4104  {
4105  /* if the activeconstant is infinite, the constant pointer gets the same value, otherwise add the value */
4106  if( activeconstantinf )
4107  (*constant) = activeconstant;
4108  else
4109  (*constant) += activeconstant;
4110  }
4111 #ifndef NDEBUG
4112  else
4113  {
4114  assert(!SCIPsetIsInfinity(set, (*constant)) || !SCIPsetIsInfinity(set, -activeconstant));
4115  assert(!SCIPsetIsInfinity(set, -(*constant)) || !SCIPsetIsInfinity(set, activeconstant));
4116  }
4117 #endif
4118 
4119  /* copy active variable and scalar array to the given arrays */
4120  for( v = 0; v < *nvars; ++v )
4121  {
4122  vars[v] = activevars[v];
4123  scalars[v] = activescalars[v]; /*lint !e613*/
4124  }
4125  }
4126 
4127  assert(SCIPsetIsInfinity(set, *constant) == ((*constant) == SCIPsetInfinity(set))); /*lint !e777*/
4128  assert(SCIPsetIsInfinity(set, -(*constant)) == ((*constant) == -SCIPsetInfinity(set))); /*lint !e777*/
4129 
4130  SCIPsetFreeBufferArray(set, &tmpscalars);
4131  SCIPsetFreeBufferArray(set, &tmpvars);
4132  SCIPsetFreeBufferArray(set, &activescalars);
4133  SCIPsetFreeBufferArray(set, &activevars);
4134  SCIPsetFreeBufferArray(set, &tmpscalars2);
4135  SCIPsetFreeBufferArray(set, &tmpvars2);
4136 
4137  return SCIP_OKAY;
4138 }
4139 
4140 
4141 /** flattens aggregation graph of multi-aggregated variable in order to avoid exponential recursion later on */
4143  SCIP_VAR* var, /**< problem variable */
4144  BMS_BLKMEM* blkmem, /**< block memory */
4145  SCIP_SET* set /**< global SCIP settings */
4146  )
4147 {
4148  SCIP_Real multconstant;
4149  int multvarssize;
4150  int nmultvars;
4151  int multrequiredsize;
4152 
4153  assert( var != NULL );
4154  assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR );
4155  assert(var->scip == set->scip);
4156 
4157  multconstant = var->data.multaggr.constant;
4158  nmultvars = var->data.multaggr.nvars;
4159  multvarssize = var->data.multaggr.varssize;
4160 
4161  SCIP_CALL( SCIPvarGetActiveRepresentatives(set, var->data.multaggr.vars, var->data.multaggr.scalars, &nmultvars, multvarssize, &multconstant, &multrequiredsize, TRUE) );
4162 
4163  if( multrequiredsize > multvarssize )
4164  {
4165  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(var->data.multaggr.vars), multvarssize, multrequiredsize) );
4166  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(var->data.multaggr.scalars), multvarssize, multrequiredsize) );
4167  multvarssize = multrequiredsize;
4168  SCIP_CALL( SCIPvarGetActiveRepresentatives(set, var->data.multaggr.vars, var->data.multaggr.scalars, &nmultvars, multvarssize, &multconstant, &multrequiredsize, TRUE) );
4169  assert( multrequiredsize <= multvarssize );
4170  }
4171  /**@note After the flattening the multi aggregation might resolve to be in fact an aggregation (or even a fixing?).
4172  * This issue is not resolved right now, since var->data.multaggr.nvars < 2 should not cause troubles. However, one
4173  * may loose performance hereby, since aggregated variables are easier to handle.
4174  *
4175  * Note, that there are two cases where SCIPvarFlattenAggregationGraph() is called: The easier one is that it is
4176  * called while installing the multi-aggregation. in principle, the described issue could be handled straightforward
4177  * in this case by aggregating or fixing the variable instead. The more complicated case is the one, when the
4178  * multi-aggregation is used, e.g., in linear presolving (and the variable is already declared to be multi-aggregated).
4179  *
4180  * By now, it is not allowed to fix or aggregate multi-aggregated variables which would be necessary in this case.
4181  *
4182  * The same issue appears in the SCIPvarGetProbvar...() methods.
4183  */
4184 
4185  var->data.multaggr.constant = multconstant;
4186  var->data.multaggr.nvars = nmultvars;
4187  var->data.multaggr.varssize = multvarssize;
4188 
4189  return SCIP_OKAY;
4190 }
4191 
4192 /** merge two variable histories together; a typical use case is that \p othervar is an image of the target variable
4193  * in a SCIP copy. Method should be applied with care, especially because no internal checks are performed whether
4194  * the history merge is reasonable
4195  *
4196  * @note Do not use this method if the two variables originate from two SCIP's with different objective functions, since
4197  * this corrupts the variable pseudo costs
4198  * @note Apply with care; no internal checks are performed if the two variables should be merged
4199  */
4201  SCIP_VAR* targetvar, /**< the variable that should contain both histories afterwards */
4202  SCIP_VAR* othervar, /**< the variable whose history is to be merged with that of the target variable */
4203  SCIP_STAT* stat /**< problem statistics */
4204  )
4205 {
4206  /* merge only the history of the current run into the target history */
4207  SCIPhistoryUnite(targetvar->history, othervar->historycrun, FALSE);
4208 
4209  /* apply the changes also to the global history */
4210  SCIPhistoryUnite(stat->glbhistory, othervar->historycrun, FALSE);
4211 }
4212 
4213 /** sets the history of a variable; this method is typically used within reoptimization to keep and update the variable
4214  * history over several iterations
4215  */
4216 void SCIPvarSetHistory(
4217  SCIP_VAR* var, /**< variable */
4218  SCIP_HISTORY* history, /**< the history which is to set */
4219  SCIP_STAT* stat /**< problem statistics */
4220  )
4221 {
4222  /* merge only the history of the current run into the target history */
4223  SCIPhistoryUnite(var->history, history, FALSE);
4224 
4225  /* apply the changes also to the global history */
4226  SCIPhistoryUnite(stat->glbhistory, history, FALSE);
4227 }
4228 
4229 /** tightens the bounds of both variables in aggregation x = a*y + c */
4230 static
4232  SCIP_VAR* var, /**< problem variable */
4233  BMS_BLKMEM* blkmem, /**< block memory */
4234  SCIP_SET* set, /**< global SCIP settings */
4235  SCIP_STAT* stat, /**< problem statistics */
4236  SCIP_PROB* transprob, /**< tranformed problem data */
4237  SCIP_PROB* origprob, /**< original problem data */
4238  SCIP_PRIMAL* primal, /**< primal data */
4239  SCIP_TREE* tree, /**< branch and bound tree */
4240  SCIP_REOPT* reopt, /**< reoptimization data structure */
4241  SCIP_LP* lp, /**< current LP data */
4242  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4243  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4244  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
4245  SCIP_VAR* aggvar, /**< variable y in aggregation x = a*y + c */
4246  SCIP_Real scalar, /**< multiplier a in aggregation x = a*y + c */
4247  SCIP_Real constant, /**< constant shift c in aggregation x = a*y + c */
4248  SCIP_Bool* infeasible, /**< pointer to store whether the aggregation is infeasible */
4249  SCIP_Bool* fixed /**< pointer to store whether the variables were fixed */
4250  )
4251 {
4252  SCIP_Real varlb;
4253  SCIP_Real varub;
4254  SCIP_Real aggvarlb;
4255  SCIP_Real aggvarub;
4256  SCIP_Bool aggvarbdschanged;
4257 
4258  assert(var != NULL);
4259  assert(var->scip == set->scip);
4260  assert(aggvar != NULL);
4261  assert(!SCIPsetIsZero(set, scalar));
4262  assert(infeasible != NULL);
4263  assert(fixed != NULL);
4264 
4265  *infeasible = FALSE;
4266  *fixed = FALSE;
4267 
4268  SCIPsetDebugMsg(set, "updating bounds of variables in aggregation <%s> == %g*<%s> %+g\n", var->name, scalar, aggvar->name, constant);
4269  SCIPsetDebugMsg(set, " old bounds: <%s> [%g,%g] <%s> [%g,%g]\n",
4270  var->name, var->glbdom.lb, var->glbdom.ub, aggvar->name, aggvar->glbdom.lb, aggvar->glbdom.ub);
4271 
4272  /* loop as long additional changes may be found */
4273  do
4274  {
4275  aggvarbdschanged = FALSE;
4276 
4277  /* update the bounds of the aggregated variable x in x = a*y + c */
4278  if( scalar > 0.0 )
4279  {
4280  if( SCIPsetIsInfinity(set, -aggvar->glbdom.lb) )
4281  varlb = -SCIPsetInfinity(set);
4282  else
4283  varlb = aggvar->glbdom.lb * scalar + constant;
4284  if( SCIPsetIsInfinity(set, aggvar->glbdom.ub) )
4285  varub = SCIPsetInfinity(set);
4286  else
4287  varub = aggvar->glbdom.ub * scalar + constant;
4288  }
4289  else
4290  {
4291  if( SCIPsetIsInfinity(set, -aggvar->glbdom.lb) )
4292  varub = SCIPsetInfinity(set);
4293  else
4294  varub = aggvar->glbdom.lb * scalar + constant;
4295  if( SCIPsetIsInfinity(set, aggvar->glbdom.ub) )
4296  varlb = -SCIPsetInfinity(set);
4297  else
4298  varlb = aggvar->glbdom.ub * scalar + constant;
4299  }
4300  varlb = MAX(varlb, var->glbdom.lb);
4301  varub = MIN(varub, var->glbdom.ub);
4302  SCIPvarAdjustLb(var, set, &varlb);
4303  SCIPvarAdjustUb(var, set, &varub);
4304 
4305  /* check the new bounds */
4306  if( SCIPsetIsGT(set, varlb, varub) )
4307  {
4308  /* the aggregation is infeasible */
4309  *infeasible = TRUE;
4310  return SCIP_OKAY;
4311  }
4312  else if( SCIPsetIsEQ(set, varlb, varub) )
4313  {
4314  /* the aggregated variable is fixed -> fix both variables */
4315  SCIP_CALL( SCIPvarFix(var, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
4316  eventqueue, cliquetable, varlb, infeasible, fixed) );
4317  if( !(*infeasible) )
4318  {
4319  SCIP_Bool aggfixed;
4320 
4321  SCIP_CALL( SCIPvarFix(aggvar, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
4322  eventqueue, cliquetable, (varlb-constant)/scalar, infeasible, &aggfixed) );
4323  assert(*fixed == aggfixed);
4324  }
4325  return SCIP_OKAY;
4326  }
4327  else
4328  {
4329  if( SCIPsetIsGT(set, varlb, var->glbdom.lb) )
4330  {
4331  SCIP_CALL( SCIPvarChgLbGlobal(var, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, varlb) );
4332  }
4333  if( SCIPsetIsLT(set, varub, var->glbdom.ub) )
4334  {
4335  SCIP_CALL( SCIPvarChgUbGlobal(var, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, varub) );
4336  }
4337 
4338  /* update the hole list of the aggregation variable */
4339  /**@todo update hole list of aggregation variable */
4340  }
4341 
4342  /* update the bounds of the aggregation variable y in x = a*y + c -> y = (x-c)/a */
4343  if( scalar > 0.0 )
4344  {
4345  if( SCIPsetIsInfinity(set, -var->glbdom.lb) )
4346  aggvarlb = -SCIPsetInfinity(set);
4347  else
4348  aggvarlb = (var->glbdom.lb - constant) / scalar;
4349  if( SCIPsetIsInfinity(set, var->glbdom.ub) )
4350  aggvarub = SCIPsetInfinity(set);
4351  else
4352  aggvarub = (var->glbdom.ub - constant) / scalar;
4353  }
4354  else
4355  {
4356  if( SCIPsetIsInfinity(set, -var->glbdom.lb) )
4357  aggvarub = SCIPsetInfinity(set);
4358  else
4359  aggvarub = (var->glbdom.lb - constant) / scalar;
4360  if( SCIPsetIsInfinity(set, var->glbdom.ub) )
4361  aggvarlb = -SCIPsetInfinity(set);
4362  else
4363  aggvarlb = (var->glbdom.ub - constant) / scalar;
4364  }
4365  aggvarlb = MAX(aggvarlb, aggvar->glbdom.lb);
4366  aggvarub = MIN(aggvarub, aggvar->glbdom.ub);
4367  SCIPvarAdjustLb(aggvar, set, &aggvarlb);
4368  SCIPvarAdjustUb(aggvar, set, &aggvarub);
4369 
4370  /* check the new bounds */
4371  if( SCIPsetIsGT(set, aggvarlb, aggvarub) )
4372  {
4373  /* the aggregation is infeasible */
4374  *infeasible = TRUE;
4375  return SCIP_OKAY;
4376  }
4377  else if( SCIPsetIsEQ(set, aggvarlb, aggvarub) )
4378  {
4379  /* the aggregation variable is fixed -> fix both variables */
4380  SCIP_CALL( SCIPvarFix(aggvar, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
4381  eventqueue, cliquetable, aggvarlb, infeasible, fixed) );
4382  if( !(*infeasible) )
4383  {
4384  SCIP_Bool varfixed;
4385 
4386  SCIP_CALL( SCIPvarFix(var, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
4387  eventqueue, cliquetable, aggvarlb * scalar + constant, infeasible, &varfixed) );
4388  assert(*fixed == varfixed);
4389  }
4390  return SCIP_OKAY;
4391  }
4392  else
4393  {
4394  SCIP_Real oldbd;
4395  if( SCIPsetIsGT(set, aggvarlb, aggvar->glbdom.lb) )
4396  {
4397  oldbd = aggvar->glbdom.lb;
4398  SCIP_CALL( SCIPvarChgLbGlobal(aggvar, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, aggvarlb) );
4399  aggvarbdschanged = !SCIPsetIsEQ(set, oldbd, aggvar->glbdom.lb);
4400  }
4401  if( SCIPsetIsLT(set, aggvarub, aggvar->glbdom.ub) )
4402  {
4403  oldbd = aggvar->glbdom.ub;
4404  SCIP_CALL( SCIPvarChgUbGlobal(aggvar, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, aggvarub) );
4405  aggvarbdschanged = aggvarbdschanged || !SCIPsetIsEQ(set, oldbd, aggvar->glbdom.ub);
4406  }
4407 
4408  /* update the hole list of the aggregation variable */
4409  /**@todo update hole list of aggregation variable */
4410  }
4411  }
4412  while( aggvarbdschanged );
4413 
4414  SCIPsetDebugMsg(set, " new bounds: <%s> [%g,%g] <%s> [%g,%g]\n",
4415  var->name, var->glbdom.lb, var->glbdom.ub, aggvar->name, aggvar->glbdom.lb, aggvar->glbdom.ub);
4416 
4417  return SCIP_OKAY;
4418 }
4419 
4420 /** converts loose variable into aggregated variable */
4422  SCIP_VAR* var, /**< loose problem variable */
4423  BMS_BLKMEM* blkmem, /**< block memory */
4424  SCIP_SET* set, /**< global SCIP settings */
4425  SCIP_STAT* stat, /**< problem statistics */
4426  SCIP_PROB* transprob, /**< tranformed problem data */
4427  SCIP_PROB* origprob, /**< original problem data */
4428  SCIP_PRIMAL* primal, /**< primal data */
4429  SCIP_TREE* tree, /**< branch and bound tree */
4430  SCIP_REOPT* reopt, /**< reoptimization data structure */
4431  SCIP_LP* lp, /**< current LP data */
4432  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
4433  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4434  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4435  SCIP_VAR* aggvar, /**< loose variable y in aggregation x = a*y + c */
4436  SCIP_Real scalar, /**< multiplier a in aggregation x = a*y + c */
4437  SCIP_Real constant, /**< constant shift c in aggregation x = a*y + c */
4438  SCIP_Bool* infeasible, /**< pointer to store whether the aggregation is infeasible */
4439  SCIP_Bool* aggregated /**< pointer to store whether the aggregation was successful */
4440  )
4441 {
4442  SCIP_VAR** vars;
4443  SCIP_Real* coefs;
4444  SCIP_Real* constants;
4445  SCIP_Real obj;
4446  SCIP_Real branchfactor;
4447  SCIP_Bool fixed;
4448  int branchpriority;
4449  int nlocksdown;
4450  int nlocksup;
4451  int nvbds;
4452  int i;
4453  int j;
4454 
4455  assert(var != NULL);
4456  assert(aggvar != NULL);
4457  assert(var->scip == set->scip);
4458  assert(var->glbdom.lb == var->locdom.lb); /*lint !e777*/
4459  assert(var->glbdom.ub == var->locdom.ub); /*lint !e777*/
4460  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
4461  assert(!SCIPeventqueueIsDelayed(eventqueue)); /* otherwise, the pseudo objective value update gets confused */
4462  assert(infeasible != NULL);
4463  assert(aggregated != NULL);
4464 
4465  *infeasible = FALSE;
4466  *aggregated = FALSE;
4467 
4468  /* get active problem variable of aggregation variable */
4469  SCIP_CALL( SCIPvarGetProbvarSum(&aggvar, set, &scalar, &constant) );
4470 
4471  /* aggregation is a fixing, if the scalar is zero */
4472  if( SCIPsetIsZero(set, scalar) )
4473  {
4474  SCIP_CALL( SCIPvarFix(var, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue,
4475  cliquetable, constant, infeasible, aggregated) );
4476  return SCIP_OKAY;
4477  }
4478 
4479  /* don't perform the aggregation if the aggregation variable is multi-aggregated itself */
4480  if( SCIPvarGetStatus(aggvar) == SCIP_VARSTATUS_MULTAGGR )
4481  return SCIP_OKAY;
4482 
4483  /**@todo currently we don't perform the aggregation if the aggregation variable has a non-empty hole list; this
4484  * should be changed in the future
4485  */
4486  if( SCIPvarGetHolelistGlobal(var) != NULL )
4487  return SCIP_OKAY;
4488 
4489  assert(aggvar->glbdom.lb == aggvar->locdom.lb); /*lint !e777*/
4490  assert(aggvar->glbdom.ub == aggvar->locdom.ub); /*lint !e777*/
4491  assert(SCIPvarGetStatus(aggvar) == SCIP_VARSTATUS_LOOSE);
4492 
4493  SCIPsetDebugMsg(set, "aggregate variable <%s>[%g,%g] == %g*<%s>[%g,%g] %+g\n", var->name, var->glbdom.lb, var->glbdom.ub,
4494  scalar, aggvar->name, aggvar->glbdom.lb, aggvar->glbdom.ub, constant);
4495 
4496  /* if variable and aggregation variable are equal, the variable can be fixed: x == a*x + c => x == c/(1-a) */
4497  if( var == aggvar )
4498  {
4499  if( SCIPsetIsEQ(set, scalar, 1.0) )
4500  *infeasible = !SCIPsetIsZero(set, constant);
4501  else
4502  {
4503  SCIP_CALL( SCIPvarFix(var, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
4504  eventqueue, cliquetable, constant/(1.0-scalar), infeasible, aggregated) );
4505  }
4506  return SCIP_OKAY;
4507  }
4508 
4509  /* tighten the bounds of aggregated and aggregation variable */
4510  SCIP_CALL( varUpdateAggregationBounds(var, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp,
4511  branchcand, eventqueue, cliquetable, aggvar, scalar, constant, infeasible, &fixed) );
4512  if( *infeasible || fixed )
4513  {
4514  *aggregated = fixed;
4515  return SCIP_OKAY;
4516  }
4517 
4518  /* delete implications and variable bounds of the aggregated variable from other variables, but keep them in the
4519  * aggregated variable
4520  */
4521  SCIP_CALL( SCIPvarRemoveCliquesImplicsVbs(var, blkmem, cliquetable, set, FALSE, FALSE, FALSE) );
4522  assert(var->cliquelist == NULL);
4523 
4524  /* set the aggregated variable's objective value to 0.0 */
4525  obj = var->obj;
4526  SCIP_CALL( SCIPvarChgObj(var, blkmem, set, transprob, primal, lp, eventqueue, 0.0) );
4527 
4528  /* unlock all rounding locks */
4529  nlocksdown = var->nlocksdown;
4530  nlocksup = var->nlocksup;
4531  var->nlocksdown = 0;
4532  var->nlocksup = 0;
4533 
4534  /* check, if variable should be used as NEGATED variable of the aggregation variable */
4535  if( SCIPvarIsBinary(var) && SCIPvarIsBinary(aggvar)
4536  && var->negatedvar == NULL && aggvar->negatedvar == NULL
4537  && SCIPsetIsEQ(set, scalar, -1.0) && SCIPsetIsEQ(set, constant, 1.0) )
4538  {
4539  /* link both variables as negation pair */
4540  var->varstatus = SCIP_VARSTATUS_NEGATED; /*lint !e641*/
4541  var->data.negate.constant = 1.0;
4542  var->negatedvar = aggvar;
4543  aggvar->negatedvar = var;
4544 
4545  /* copy doNotMultiaggr status */
4546  aggvar->donotmultaggr |= var->donotmultaggr;
4547 
4548  /* mark both variables to be non-deletable */
4550  SCIPvarMarkNotDeletable(aggvar);
4551  }
4552  else
4553  {
4554  /* convert variable into aggregated variable */
4555  var->varstatus = SCIP_VARSTATUS_AGGREGATED; /*lint !e641*/
4556  var->data.aggregate.var = aggvar;
4557  var->data.aggregate.scalar = scalar;
4558  var->data.aggregate.constant = constant;
4559 
4560  /* copy doNotMultiaggr status */
4561  aggvar->donotmultaggr |= var->donotmultaggr;
4562 
4563  /* mark both variables to be non-deletable */
4565  SCIPvarMarkNotDeletable(aggvar);
4566  }
4567 
4568  /* make aggregated variable a parent of the aggregation variable */
4569  SCIP_CALL( varAddParent(aggvar, blkmem, set, var) );
4570 
4571  /* relock the rounding locks of the variable, thus increasing the locks of the aggregation variable */
4572  SCIP_CALL( SCIPvarAddLocks(var, blkmem, set, eventqueue, nlocksdown, nlocksup) );
4573 
4574  /* move the variable bounds to the aggregation variable:
4575  * - add all variable bounds again to the variable, thus adding it to the aggregation variable
4576  * - free the variable bounds data structures
4577  */
4578  if( var->vlbs != NULL )
4579  {
4580  nvbds = SCIPvboundsGetNVbds(var->vlbs);
4581  vars = SCIPvboundsGetVars(var->vlbs);
4582  coefs = SCIPvboundsGetCoefs(var->vlbs);
4583  constants = SCIPvboundsGetConstants(var->vlbs);
4584  for( i = 0; i < nvbds && !(*infeasible); ++i )
4585  {
4586  SCIP_CALL( SCIPvarAddVlb(var, blkmem, set, stat, transprob, origprob, tree, reopt, lp, cliquetable, branchcand,
4587  eventqueue, vars[i], coefs[i], constants[i], FALSE, infeasible, NULL) );
4588  }
4589  }
4590  if( var->vubs != NULL )
4591  {
4592  nvbds = SCIPvboundsGetNVbds(var->vubs);
4593  vars = SCIPvboundsGetVars(var->vubs);
4594  coefs = SCIPvboundsGetCoefs(var->vubs);
4595  constants = SCIPvboundsGetConstants(var->vubs);
4596  for( i = 0; i < nvbds && !(*infeasible); ++i )
4597  {
4598  SCIP_CALL( SCIPvarAddVub(var, blkmem, set, stat, transprob, origprob, tree, reopt, lp, cliquetable, branchcand,
4599  eventqueue, vars[i], coefs[i], constants[i], FALSE, infeasible, NULL) );
4600  }
4601  }
4602  SCIPvboundsFree(&var->vlbs, blkmem);
4603  SCIPvboundsFree(&var->vubs, blkmem);
4604 
4605  /* move the implications to the aggregation variable:
4606  * - add all implications again to the variable, thus adding it to the aggregation variable
4607  * - free the implications data structures
4608  */
4609  if( var->implics != NULL && SCIPvarGetType(aggvar) == SCIP_VARTYPE_BINARY )
4610  {
4611  assert(SCIPvarIsBinary(var));
4612  for( i = 0; i < 2; ++i )
4613  {
4614  SCIP_VAR** implvars;
4615  SCIP_BOUNDTYPE* impltypes;
4616  SCIP_Real* implbounds;
4617  int nimpls;
4618 
4619  nimpls = SCIPimplicsGetNImpls(var->implics, (SCIP_Bool)i);
4620  implvars = SCIPimplicsGetVars(var->implics, (SCIP_Bool)i);
4621  impltypes = SCIPimplicsGetTypes(var->implics, (SCIP_Bool)i);
4622  implbounds = SCIPimplicsGetBounds(var->implics, (SCIP_Bool)i);
4623 
4624  for( j = 0; j < nimpls && !(*infeasible); ++j )
4625  {
4626  /* @todo can't we omit transitive closure, because it should already have been done when adding the
4627  * implication to the aggregated variable?
4628  */
4629  SCIP_CALL( SCIPvarAddImplic(var, blkmem, set, stat, transprob, origprob, tree, reopt, lp, cliquetable,
4630  branchcand, eventqueue, (SCIP_Bool)i, implvars[j], impltypes[j], implbounds[j], FALSE, infeasible,
4631  NULL) );
4632  assert(nimpls == SCIPimplicsGetNImpls(var->implics, (SCIP_Bool)i));
4633  }
4634  }
4635  }
4636  SCIPimplicsFree(&var->implics, blkmem);
4637 
4638  /* add the history entries to the aggregation variable and clear the history of the aggregated variable */
4639  SCIPhistoryUnite(aggvar->history, var->history, scalar < 0.0);
4640  SCIPhistoryUnite(aggvar->historycrun, var->historycrun, scalar < 0.0);
4641  SCIPhistoryReset(var->history);
4643 
4644  /* update flags of aggregation variable */
4645  aggvar->removable &= var->removable;
4646 
4647  /* update branching factors and priorities of both variables to be the maximum of both variables */
4648  branchfactor = MAX(aggvar->branchfactor, var->branchfactor);
4649  branchpriority = MAX(aggvar->branchpriority, var->branchpriority);
4650  SCIP_CALL( SCIPvarChgBranchFactor(aggvar, set, branchfactor) );
4651  SCIP_CALL( SCIPvarChgBranchPriority(aggvar, branchpriority) );
4652  SCIP_CALL( SCIPvarChgBranchFactor(var, set, branchfactor) );
4653  SCIP_CALL( SCIPvarChgBranchPriority(var, branchpriority) );
4654 
4655  /* update branching direction of both variables to agree to a single direction */
4656  if( scalar >= 0.0 )
4657  {
4659  {
4661  }
4662  else if( (SCIP_BRANCHDIR)aggvar->branchdirection == SCIP_BRANCHDIR_AUTO )
4663  {
4665  }
4666  else if( var->branchdirection != aggvar->branchdirection )
4667  {
4669  }
4670  }
4671  else
4672  {
4674  {
4676  }
4677  else if( (SCIP_BRANCHDIR)aggvar->branchdirection == SCIP_BRANCHDIR_AUTO )
4678  {
4680  }
4681  else if( var->branchdirection != aggvar->branchdirection )
4682  {
4684  }
4685  }
4686 
4687  if( var->probindex != -1 )
4688  {
4689  /* inform problem about the variable's status change */
4690  SCIP_CALL( SCIPprobVarChangedStatus(transprob, blkmem, set, branchcand, cliquetable, var) );
4691  }
4692 
4693  /* reset the objective value of the aggregated variable, thus adjusting the objective value of the aggregation
4694  * variable and the problem's objective offset
4695  */
4696  SCIP_CALL( SCIPvarAddObj(var, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, eventqueue, obj) );
4697 
4698  /* issue VARFIXED event */
4699  SCIP_CALL( varEventVarFixed(var, blkmem, set, eventqueue, 1) );
4700 
4701  *aggregated = TRUE;
4702 
4703  return SCIP_OKAY;
4704 }
4705 
4706 /** Tries to aggregate an equality a*x + b*y == c consisting of two (implicit) integral active problem variables x and
4707  * y. An integer aggregation (i.e. integral coefficients a' and b', such that a'*x + b'*y == c') is searched.
4708  *
4709  * This can lead to the detection of infeasibility (e.g. if c' is fractional), or to a rejection of the aggregation
4710  * (denoted by aggregated == FALSE), if the resulting integer coefficients are too large and thus numerically instable.
4711  */
4712 static
4714  SCIP_SET* set, /**< global SCIP settings */
4715  BMS_BLKMEM* blkmem, /**< block memory */
4716  SCIP_STAT* stat, /**< problem statistics */
4717  SCIP_PROB* transprob, /**< tranformed problem data */
4718  SCIP_PROB* origprob, /**< original problem data */
4719  SCIP_PRIMAL* primal, /**< primal data */
4720  SCIP_TREE* tree, /**< branch and bound tree */
4721  SCIP_REOPT* reopt, /**< reoptimization data structure */
4722  SCIP_LP* lp, /**< current LP data */
4723  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
4724  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4725  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4726  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4727  SCIP_VAR* varx, /**< integral variable x in equality a*x + b*y == c */
4728  SCIP_VAR* vary, /**< integral variable y in equality a*x + b*y == c */
4729  SCIP_Real scalarx, /**< multiplier a in equality a*x + b*y == c */
4730  SCIP_Real scalary, /**< multiplier b in equality a*x + b*y == c */
4731  SCIP_Real rhs, /**< right hand side c in equality a*x + b*y == c */
4732  SCIP_Bool* infeasible, /**< pointer to store whether the aggregation is infeasible */
4733  SCIP_Bool* aggregated /**< pointer to store whether the aggregation was successful */
4734  )
4735 {
4736  SCIP_VAR* aggvar;
4737  char aggvarname[SCIP_MAXSTRLEN];
4738  SCIP_Longint scalarxn = 0;
4739  SCIP_Longint scalarxd = 0;
4740  SCIP_Longint scalaryn = 0;
4741  SCIP_Longint scalaryd = 0;
4742  SCIP_Longint a;
4743  SCIP_Longint b;
4744  SCIP_Longint c;
4745  SCIP_Longint scm;
4746  SCIP_Longint gcd;
4747  SCIP_Longint currentclass;
4748  SCIP_Longint classstep;
4749  SCIP_Longint xsol;
4750  SCIP_Longint ysol;
4751  SCIP_Bool success;
4752  SCIP_VARTYPE vartype;
4753 
4754 #define MAXDNOM 1000000LL
4755 
4756  assert(set != NULL);
4757  assert(blkmem != NULL);
4758  assert(stat != NULL);
4759  assert(transprob != NULL);
4760  assert(origprob != NULL);
4761  assert(tree != NULL);
4762  assert(lp != NULL);
4763  assert(cliquetable != NULL);
4764  assert(branchcand != NULL);
4765  assert(eventqueue != NULL);
4766  assert(varx != NULL);
4767  assert(vary != NULL);
4768  assert(varx != vary);
4769  assert(infeasible != NULL);
4770  assert(aggregated != NULL);
4771  assert(SCIPsetGetStage(set) == SCIP_STAGE_PRESOLVING);
4772  assert(SCIPvarGetStatus(varx) == SCIP_VARSTATUS_LOOSE);
4774  assert(SCIPvarGetStatus(vary) == SCIP_VARSTATUS_LOOSE);
4776  assert(!SCIPsetIsZero(set, scalarx));
4777  assert(!SCIPsetIsZero(set, scalary));
4778 
4779  *infeasible = FALSE;
4780  *aggregated = FALSE;
4781 
4782  /* get rational representation of coefficients */
4783  success = SCIPrealToRational(scalarx, -SCIPsetEpsilon(set), SCIPsetEpsilon(set), MAXDNOM, &scalarxn, &scalarxd);
4784  if( success )
4785  success = SCIPrealToRational(scalary, -SCIPsetEpsilon(set), SCIPsetEpsilon(set), MAXDNOM, &scalaryn, &scalaryd);
4786  if( !success )
4787  return SCIP_OKAY;
4788  assert(scalarxd >= 1);
4789  assert(scalaryd >= 1);
4790 
4791  /* multiply equality with smallest common denominator */
4792  scm = SCIPcalcSmaComMul(scalarxd, scalaryd);
4793  a = (scm/scalarxd)*scalarxn;
4794  b = (scm/scalaryd)*scalaryn;
4795  rhs *= scm;
4796 
4797  /* divide equality by the greatest common divisor of a and b */
4798  gcd = SCIPcalcGreComDiv(ABS(a), ABS(b));
4799  a /= gcd;
4800  b /= gcd;
4801  rhs /= gcd;
4802  assert(a != 0);
4803  assert(b != 0);
4804 
4805  /* check, if right hand side is integral */
4806  if( !SCIPsetIsFeasIntegral(set, rhs) )
4807  {
4808  *infeasible = TRUE;
4809  return SCIP_OKAY;
4810  }
4811  c = (SCIP_Longint)(SCIPsetFeasFloor(set, rhs));
4812 
4813  /* check, if we are in an easy case with either |a| = 1 or |b| = 1 */
4814  if( (a == 1 || a == -1) && SCIPvarGetType(vary) == SCIP_VARTYPE_INTEGER )
4815  {
4816  /* aggregate x = - b/a*y + c/a */
4817  /*lint --e{653}*/
4818  SCIP_CALL( SCIPvarAggregate(varx, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, cliquetable,
4819  branchcand, eventqueue, vary, (SCIP_Real)(-b/a), (SCIP_Real)(c/a), infeasible, aggregated) );
4820  assert(*aggregated);
4821  return SCIP_OKAY;
4822  }
4823  if( (b == 1 || b == -1) && SCIPvarGetType(varx) == SCIP_VARTYPE_INTEGER )
4824  {
4825  /* aggregate y = - a/b*x + c/b */
4826  /*lint --e{653}*/
4827  SCIP_CALL( SCIPvarAggregate(vary, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, cliquetable,
4828  branchcand, eventqueue, varx, (SCIP_Real)(-a/b), (SCIP_Real)(c/b), infeasible, aggregated) );
4829  assert(*aggregated);
4830  return SCIP_OKAY;
4831  }
4832 
4833  /* Both variables are integers, their coefficients are not multiples of each other, and they don't have any
4834  * common divisor. Let (x',y') be a solution of the equality
4835  * a*x + b*y == c -> a*x == c - b*y
4836  * Then x = -b*z + x', y = a*z + y' with z integral gives all solutions to the equality.
4837  */
4838 
4839  /* find initial solution (x',y'):
4840  * - find y' such that c - b*y' is a multiple of a
4841  * - start in equivalence class c%a
4842  * - step through classes, where each step increases class number by (-b)%a, until class 0 is visited
4843  * - if equivalence class 0 is visited, we are done: y' equals the number of steps taken
4844  * - because a and b don't have a common divisor, each class is visited at most once, and at most a-1 steps are needed
4845  * - calculate x' with x' = (c - b*y')/a (which must be integral)
4846  *
4847  * Algorithm works for a > 0 only.
4848  */
4849  if( a < 0 )
4850  {
4851  a = -a;
4852  b = -b;
4853  c = -c;
4854  }
4855  assert(0 <= a);
4856 
4857  /* search upwards from ysol = 0 */
4858  ysol = 0;
4859  currentclass = c%a;
4860  if( currentclass < 0 )
4861  currentclass += a;
4862  assert(0 <= currentclass && currentclass < a);
4863 
4864  classstep = (-b)%a;
4865 
4866  if( classstep < 0 )
4867  classstep += a;
4868  assert(0 <= classstep && classstep < a);
4869 
4870  while( currentclass != 0 )
4871  {
4872  assert(0 <= currentclass && currentclass < a);
4873  currentclass += classstep;
4874  if( currentclass >= a )
4875  currentclass -= a;
4876  ysol++;
4877  }
4878  assert(ysol < a);
4879  assert(((c - b*ysol)%a) == 0);
4880 
4881  xsol = (c - b*ysol)/a;
4882 
4883  /* determine variable type for new artificial variable:
4884  *
4885  * if both variables are implicit integer the new variable can be implicit too, because the integer implication on
4886  * these both variables should be enforced by some other variables, otherwise the new variable needs to be of
4887  * integral type
4888  */
4891 
4892  /* feasible solutions are (x,y) = (x',y') + z*(-b,a)
4893  * - create new integer variable z with infinite bounds
4894  * - aggregate variable x = -b*z + x'
4895  * - aggregate variable y = a*z + y'
4896  * - the bounds of z are calculated automatically during aggregation
4897  */
4898  (void) SCIPsnprintf(aggvarname, SCIP_MAXSTRLEN, "agg%d", stat->nvaridx);
4899  SCIP_CALL( SCIPvarCreateTransformed(&aggvar, blkmem, set, stat,
4900  aggvarname, -SCIPsetInfinity(set), SCIPsetInfinity(set), 0.0, vartype,
4902  NULL, NULL, NULL, NULL, NULL) );
4903 
4904  SCIP_CALL( SCIPprobAddVar(transprob, blkmem, set, lp, branchcand, eventfilter, eventqueue, aggvar) );
4905 
4906  SCIP_CALL( SCIPvarAggregate(varx, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, cliquetable,
4907  branchcand, eventqueue, aggvar, (SCIP_Real)(-b), (SCIP_Real)xsol, infeasible, aggregated) );
4908  assert(*aggregated || *infeasible);
4909 
4910  if( !(*infeasible) )
4911  {
4912  SCIP_CALL( SCIPvarAggregate(vary, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, cliquetable,
4913  branchcand, eventqueue, aggvar, (SCIP_Real)a, (SCIP_Real)ysol, infeasible, aggregated) );
4914  assert(*aggregated || *infeasible);
4915  }
4916 
4917  /* release z */
4918  SCIP_CALL( SCIPvarRelease(&aggvar, blkmem, set, eventqueue, lp) );
4919 
4920  return SCIP_OKAY;
4921 }
4922 
4923 /** performs second step of SCIPaggregateVars():
4924  * the variable to be aggregated is chosen among active problem variables x' and y', preferring a less strict variable
4925  * type as aggregation variable (i.e. continuous variables are preferred over implicit integers, implicit integers
4926  * or integers over binaries). If none of the variables is continuous, it is tried to find an integer
4927  * aggregation (i.e. integral coefficients a'' and b'', such that a''*x' + b''*y' == c''). This can lead to
4928  * the detection of infeasibility (e.g. if c'' is fractional), or to a rejection of the aggregation (denoted by
4929  * aggregated == FALSE), if the resulting integer coefficients are too large and thus numerically instable.
4930  *
4931  * @todo check for fixings, infeasibility, bound changes, or domain holes:
4932  * a) if there is no easy aggregation and we have one binary variable and another integer/implicit/binary variable
4933  * b) for implicit integer variables with fractional aggregation scalar (we cannot (for technical reasons) and do
4934  * not want to aggregate implicit integer variables, since we loose the corresponding divisibility property)
4935  */
4937  SCIP_SET* set, /**< global SCIP settings */
4938  BMS_BLKMEM* blkmem, /**< block memory */
4939  SCIP_STAT* stat, /**< problem statistics */
4940  SCIP_PROB* transprob, /**< tranformed problem data */
4941  SCIP_PROB* origprob, /**< original problem data */
4942  SCIP_PRIMAL* primal, /**< primal data */
4943  SCIP_TREE* tree, /**< branch and bound tree */
4944  SCIP_REOPT* reopt, /**< reoptimization data structure */
4945  SCIP_LP* lp, /**< current LP data */
4946  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
4947  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4948  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4949  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4950  SCIP_VAR* varx, /**< variable x in equality a*x + b*y == c */
4951  SCIP_VAR* vary, /**< variable y in equality a*x + b*y == c */
4952  SCIP_Real scalarx, /**< multiplier a in equality a*x + b*y == c */
4953  SCIP_Real scalary, /**< multiplier b in equality a*x + b*y == c */
4954  SCIP_Real rhs, /**< right hand side c in equality a*x + b*y == c */
4955  SCIP_Bool* infeasible, /**< pointer to store whether the aggregation is infeasible */
4956  SCIP_Bool* aggregated /**< pointer to store whether the aggregation was successful */
4957  )
4958 {
4959  SCIP_Bool easyaggr;
4960  SCIP_Real maxscalar;
4961  SCIP_Real absquot;
4962 
4963  assert(set != NULL);
4964  assert(blkmem != NULL);
4965  assert(stat != NULL);
4966  assert(transprob != NULL);
4967  assert(origprob != NULL);
4968  assert(tree != NULL);
4969  assert(lp != NULL);
4970  assert(cliquetable != NULL);
4971  assert(branchcand != NULL);
4972  assert(eventqueue != NULL);
4973  assert(varx != NULL);
4974  assert(vary != NULL);
4975  assert(varx != vary);
4976  assert(infeasible != NULL);
4977  assert(aggregated != NULL);
4978  assert(SCIPsetGetStage(set) == SCIP_STAGE_PRESOLVING);
4979  assert(SCIPvarGetStatus(varx) == SCIP_VARSTATUS_LOOSE);
4980  assert(SCIPvarGetStatus(vary) == SCIP_VARSTATUS_LOOSE);
4981  assert(!SCIPsetIsZero(set, scalarx));
4982  assert(!SCIPsetIsZero(set, scalary));
4983 
4984  *infeasible = FALSE;
4985  *aggregated = FALSE;
4986 
4987  absquot = REALABS(scalarx / scalary);
4988  maxscalar = SCIPsetFeastol(set) / SCIPsetEpsilon(set);
4989  maxscalar = MAX(maxscalar, 1.0);
4990 
4991  if( absquot > maxscalar || absquot < 1 / maxscalar )
4992  return SCIP_OKAY;
4993 
4994  /* prefer aggregating the variable of more general type (preferred aggregation variable is varx) */
4995  if( SCIPvarGetType(vary) > SCIPvarGetType(varx) ||
4996  (SCIPvarGetType(vary) == SCIPvarGetType(varx) && !SCIPvarIsBinary(vary) && SCIPvarIsBinary(varx)) )
4997  {
4998  SCIP_VAR* var;
4999  SCIP_Real scalar;
5000 
5001  /* switch the variables, such that varx is the variable of more general type (cont > implint > int > bin) */
5002  var = vary;
5003  vary = varx;
5004  varx = var;
5005  scalar = scalary;
5006  scalary = scalarx;
5007  scalarx = scalar;
5008  }
5009 
5010  /* don't aggregate if the aggregation would lead to a binary variable aggregated to a non-binary variable */
5011  if( SCIPvarIsBinary(varx) && !SCIPvarIsBinary(vary) )
5012  return SCIP_OKAY;
5013 
5014  assert(SCIPvarGetType(varx) >= SCIPvarGetType(vary));
5015 
5016  /* figure out, which variable should be aggregated */
5017  easyaggr = FALSE;
5018 
5019  /* check if it is an easy aggregation that means:
5020  *
5021  * a*x + b*y == c -> x == -b/a * y + c/a iff |b/a| > feastol and |a/b| > feastol
5022  */
5023  if( !SCIPsetIsFeasZero(set, scalary/scalarx) && !SCIPsetIsFeasZero(set, scalarx/scalary) )
5024  {
5026  {
5027  easyaggr = TRUE;
5028  }
5029  else if( SCIPsetIsFeasIntegral(set, scalary/scalarx) )
5030  {
5031  easyaggr = TRUE;
5032  }
5033  else if( SCIPsetIsFeasIntegral(set, scalarx/scalary) && SCIPvarGetType(vary) == SCIPvarGetType(varx) )
5034  {
5035  /* we have an easy aggregation if we flip the variables x and y */
5036  SCIP_VAR* var;
5037  SCIP_Real scalar;
5038 
5039  /* switch the variables, such that varx is the aggregated variable */
5040  var = vary;
5041  vary = varx;
5042  varx = var;
5043  scalar = scalary;
5044  scalary = scalarx;
5045  scalarx = scalar;
5046  easyaggr = TRUE;
5047  }
5048  else if( SCIPvarGetType(varx) == SCIP_VARTYPE_CONTINUOUS )
5049  {
5050  /* the aggregation is still easy if both variables are continuous */
5051  assert(SCIPvarGetType(vary) == SCIP_VARTYPE_CONTINUOUS); /* otherwise we are in the first case */
5052  easyaggr = TRUE;
5053  }
5054  }
5055 
5056  /* did we find an "easy" aggregation? */
5057  if( easyaggr )
5058  {
5059  SCIP_Real scalar;
5060  SCIP_Real constant;
5061 
5062  assert(SCIPvarGetType(varx) >= SCIPvarGetType(vary));
5063 
5064  /* calculate aggregation scalar and constant: a*x + b*y == c => x == -b/a * y + c/a */
5065  scalar = -scalary/scalarx;
5066  constant = rhs/scalarx;
5067 
5068  /* check aggregation for integer feasibility */
5071  && SCIPsetIsFeasIntegral(set, scalar) && !SCIPsetIsFeasIntegral(set, constant) )
5072  {
5073  *infeasible = TRUE;
5074  return SCIP_OKAY;
5075  }
5076 
5077  /* if the aggregation scalar is fractional, we cannot (for technical reasons) and do not want to aggregate implicit integer variables,
5078  * since then we would loose the corresponding divisibility property
5079  */
5080  assert(SCIPvarGetType(varx) != SCIP_VARTYPE_IMPLINT || SCIPsetIsFeasIntegral(set, scalar));
5081 
5082  /* aggregate the variable */
5083  SCIP_CALL( SCIPvarAggregate(varx, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, cliquetable,
5084  branchcand, eventqueue, vary, scalar, constant, infeasible, aggregated) );
5085  assert(*aggregated || *infeasible);
5086  }
5089  {
5090  /* the variables are both integral: we have to try to find an integer aggregation */
5091  SCIP_CALL( tryAggregateIntVars(set, blkmem, stat, transprob, origprob, primal, tree, reopt, lp, cliquetable,
5092  branchcand, eventfilter, eventqueue, varx, vary, scalarx, scalary, rhs, infeasible, aggregated) );
5093  }
5094 
5095  return SCIP_OKAY;
5096 }
5097 
5098 /** converts variable into multi-aggregated variable */
5100  SCIP_VAR* var, /**< problem variable */
5101  BMS_BLKMEM* blkmem, /**< block memory */
5102  SCIP_SET* set, /**< global SCIP settings */
5103  SCIP_STAT* stat, /**< problem statistics */
5104  SCIP_PROB* transprob, /**< tranformed problem data */
5105  SCIP_PROB* origprob, /**< original problem data */
5106  SCIP_PRIMAL* primal, /**< primal data */
5107  SCIP_TREE* tree, /**< branch and bound tree */
5108  SCIP_REOPT* reopt, /**< reoptimization data structure */
5109  SCIP_LP* lp, /**< current LP data */
5110  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
5111