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