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  {
2219  SCIPerrorMessage("expected value: %s.\n", str);
2220  return SCIP_READERROR;
2221  }
2222  }
2223 
2224  return SCIP_OKAY;
2225 }
2226 
2227 /** parse the characters as bounds */
2228 static
2230  SCIP_SET* set, /**< global SCIP settings */
2231  const char* str, /**< string to parse */
2232  char* type, /**< bound type (global, local, or lazy) */
2233  SCIP_Real* lb, /**< pointer to store the lower bound */
2234  SCIP_Real* ub, /**< pointer to store the upper bound */
2235  char** endptr /**< pointer to store the final string position if successfully parsed (or NULL if an error occured) */
2236  )
2237 {
2238  char token[SCIP_MAXSTRLEN];
2239  char* tmpend;
2240 
2241  SCIPsetDebugMsg(set, "parsing bounds: '%s'\n", str);
2242 
2243  /* get bound type */
2244  SCIPstrCopySection(str, ' ', ' ', type, SCIP_MAXSTRLEN, endptr);
2245  if ( strncmp(type, "original", 8) != 0 && strncmp(type, "global", 6) != 0 && strncmp(type, "local", 5) != 0 && strncmp(type, "lazy", 4) != 0 )
2246  {
2247  SCIPsetDebugMsg(set, "unkown bound type <%s>\n", type);
2248  *endptr = NULL;
2249  return SCIP_OKAY;
2250  }
2251 
2252  SCIPsetDebugMsg(set, "parsed bound type <%s>\n", type);
2253 
2254  /* get lower bound */
2255  SCIPstrCopySection(str, '[', ',', token, SCIP_MAXSTRLEN, endptr);
2256  str = *endptr;
2257  SCIP_CALL( parseValue(set, token, lb, &tmpend) );
2258 
2259  /* get upper bound */
2260  SCIP_CALL( parseValue(set, str, ub, endptr) );
2261 
2262  SCIPsetDebugMsg(set, "parsed bounds: [%g,%g]\n", *lb, *ub);
2263 
2264  /* skip end of bounds */
2265  while ( **endptr != '\0' && (**endptr == ']' || **endptr == ',') )
2266  ++(*endptr);
2267 
2268  return SCIP_OKAY;
2269 }
2270 
2271 /** parses a given string for a variable informations */
2272 static
2274  SCIP_SET* set, /**< global SCIP settings */
2275  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2276  const char* str, /**< string to parse */
2277  char* name, /**< pointer to store the variable name */
2278  SCIP_Real* lb, /**< pointer to store the lower bound */
2279  SCIP_Real* ub, /**< pointer to store the upper bound */
2280  SCIP_Real* obj, /**< pointer to store the objective coefficient */
2281  SCIP_VARTYPE* vartype, /**< pointer to store the variable type */
2282  SCIP_Real* lazylb, /**< pointer to store if the lower bound is lazy */
2283  SCIP_Real* lazyub, /**< pointer to store if the upper bound is lazy */
2284  SCIP_Bool local, /**< should the local bound be applied */
2285  char** endptr, /**< pointer to store the final string position if successfully */
2286  SCIP_Bool* success /**< pointer store if the paring process was successful */
2287  )
2288 {
2289  SCIP_Real parsedlb;
2290  SCIP_Real parsedub;
2291  char token[SCIP_MAXSTRLEN];
2292  char* strptr;
2293  int i;
2294 
2295  assert(lb != NULL);
2296  assert(ub != NULL);
2297  assert(obj != NULL);
2298  assert(vartype != NULL);
2299  assert(lazylb != NULL);
2300  assert(lazyub != NULL);
2301  assert(success != NULL);
2302 
2303  (*success) = TRUE;
2304 
2305  /* copy variable type */
2306  SCIPstrCopySection(str, '[', ']', token, SCIP_MAXSTRLEN, endptr);
2307  assert(str != *endptr);
2308  SCIPsetDebugMsg(set, "parsed variable type <%s>\n", token);
2309 
2310  /* get variable type */
2311  if( strncmp(token, "binary", 3) == 0 )
2312  (*vartype) = SCIP_VARTYPE_BINARY;
2313  else if( strncmp(token, "integer", 3) == 0 )
2314  (*vartype) = SCIP_VARTYPE_INTEGER;
2315  else if( strncmp(token, "implicit", 3) == 0 )
2316  (*vartype) = SCIP_VARTYPE_IMPLINT;
2317  else if( strncmp(token, "continuous", 3) == 0 )
2318  (*vartype) = SCIP_VARTYPE_CONTINUOUS;
2319  else
2320  {
2321  SCIPmessagePrintWarning(messagehdlr, "unknown variable type\n");
2322  (*success) = FALSE;
2323  return SCIP_OKAY;
2324  }
2325 
2326  /* move string pointer behind variable type */
2327  str = *endptr;
2328 
2329  /* get variable name */
2330  SCIPstrCopySection(str, '<', '>', name, SCIP_MAXSTRLEN, endptr);
2331  assert(endptr != NULL);
2332  SCIPsetDebugMsg(set, "parsed variable name <%s>\n", name);
2333 
2334  /* move string pointer behind variable name */
2335  str = *endptr;
2336 
2337  /* cut out objective coefficient */
2338  SCIPstrCopySection(str, '=', ',', token, SCIP_MAXSTRLEN, endptr);
2339 
2340  /* move string pointer behind objective coefficient */
2341  str = *endptr;
2342 
2343  /* get objective coefficient */
2344  if( !SCIPstrToRealValue(token, obj, endptr) )
2345  {
2346  *endptr = NULL;
2347  return SCIP_READERROR;
2348  }
2349 
2350  SCIPsetDebugMsg(set, "parsed objective coefficient <%g>\n", *obj);
2351 
2352  /* parse global/original bounds */
2353  SCIP_CALL( parseBounds(set, str, token, lb, ub, endptr) );
2354  if ( *endptr == NULL )
2355  {
2356  SCIPerrorMessage("Expected bound type: %s.\n", token);
2357  return SCIP_READERROR;
2358  }
2359  assert(strncmp(token, "global", 6) == 0 || strncmp(token, "original", 8) == 0);
2360 
2361  /* initialize the lazy bound */
2362  *lazylb = -SCIPsetInfinity(set);
2363  *lazyub = SCIPsetInfinity(set);
2364 
2365  /* store pointer */
2366  strptr = *endptr;
2367 
2368  /* possibly parse optional local and lazy bounds */
2369  for( i = 0; i < 2 && *endptr != NULL && **endptr != '\0'; ++i )
2370  {
2371  /* start after previous bounds */
2372  strptr = *endptr;
2373 
2374  /* parse global bounds */
2375  SCIP_CALL( parseBounds(set, strptr, token, &parsedlb, &parsedub, endptr) );
2376 
2377  /* stop if parsing of bounds failed */
2378  if( *endptr == NULL )
2379  break;
2380 
2381  if( strncmp(token, "local", 5) == 0 && local )
2382  {
2383  *lb = parsedlb;
2384  *ub = parsedub;
2385  }
2386  else if( strncmp(token, "lazy", 4) == 0 )
2387  {
2388  *lazylb = parsedlb;
2389  *lazyub = parsedub;
2390  }
2391  }
2392 
2393  /* restore pointer */
2394  if ( *endptr == NULL )
2395  *endptr = strptr;
2396 
2397  /* check bounds for binary variables */
2398  if ( (*vartype) == SCIP_VARTYPE_BINARY )
2399  {
2400  if ( SCIPsetIsLT(set, *lb, 0.0) || SCIPsetIsGT(set, *ub, 1.0) )
2401  {
2402  SCIPerrorMessage("Parsed invalid bounds for binary variable <%s>: [%f, %f].\n", name, *lb, *ub);
2403  return SCIP_READERROR;
2404  }
2405  if ( !SCIPsetIsInfinity(set, -(*lazylb)) && !SCIPsetIsInfinity(set, *lazyub) &&
2406  ( SCIPsetIsLT(set, *lazylb, 0.0) || SCIPsetIsGT(set, *lazyub, 1.0) ) )
2407  {
2408  SCIPerrorMessage("Parsed invalid lazy bounds for binary variable <%s>: [%f, %f].\n", name, *lazylb, *lazyub);
2409  return SCIP_READERROR;
2410  }
2411  }
2412 
2413  return SCIP_OKAY;
2414 }
2415 
2416 /** parses variable information (in cip format) out of a string; if the parsing process was successful an original
2417  * variable is created and captured; if variable is of integral type, fractional bounds are automatically rounded; an
2418  * integer variable with bounds zero and one is automatically converted into a binary variable
2419  */
2421  SCIP_VAR** var, /**< pointer to variable data */
2422  BMS_BLKMEM* blkmem, /**< block memory */
2423  SCIP_SET* set, /**< global SCIP settings */
2424  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2425  SCIP_STAT* stat, /**< problem statistics */
2426  const char* str, /**< string to parse */
2427  SCIP_Bool initial, /**< should var's column be present in the initial root LP? */
2428  SCIP_Bool removable, /**< is var's column removable from the LP (due to aging or cleanup)? */
2429  SCIP_DECL_VARCOPY ((*varcopy)), /**< copies variable data if wanted to subscip, or NULL */
2430  SCIP_DECL_VARDELORIG ((*vardelorig)), /**< frees user data of original variable */
2431  SCIP_DECL_VARTRANS ((*vartrans)), /**< creates transformed user data by transforming original user data */
2432  SCIP_DECL_VARDELTRANS ((*vardeltrans)), /**< frees user data of transformed variable */
2433  SCIP_VARDATA* vardata, /**< user data for this specific variable */
2434  char** endptr, /**< pointer to store the final string position if successfully */
2435  SCIP_Bool* success /**< pointer store if the paring process was successful */
2436  )
2437 {
2438  char name[SCIP_MAXSTRLEN];
2439  SCIP_Real lb;
2440  SCIP_Real ub;
2441  SCIP_Real obj;
2442  SCIP_VARTYPE vartype;
2443  SCIP_Real lazylb;
2444  SCIP_Real lazyub;
2445 
2446  assert(var != NULL);
2447  assert(blkmem != NULL);
2448  assert(stat != NULL);
2449  assert(endptr != NULL);
2450  assert(success != NULL);
2451 
2452  /* parse string in cip format for variable information */
2453  SCIP_CALL( varParse(set, messagehdlr, str, name, &lb, &ub, &obj, &vartype, &lazylb, &lazyub, FALSE, endptr, success) );
2454 
2455  if( *success )
2456  {
2457  /* create variable */
2458  SCIP_CALL( varCreate(var, blkmem, set, stat, name, lb, ub, obj, vartype, initial, removable,
2459  varcopy, vardelorig, vartrans, vardeltrans, vardata) );
2460 
2461  /* set variable status and data */
2462  (*var)->varstatus = SCIP_VARSTATUS_ORIGINAL; /*lint !e641*/
2463  (*var)->data.original.origdom.holelist = NULL;
2464  (*var)->data.original.origdom.lb = lb;
2465  (*var)->data.original.origdom.ub = ub;
2466  (*var)->data.original.transvar = NULL;
2467 
2468  /* set lazy status of variable bounds */
2469  (*var)->lazylb = lazylb;
2470  (*var)->lazyub = lazyub;
2471 
2472  /* capture variable */
2473  SCIPvarCapture(*var);
2474  }
2475 
2476  return SCIP_OKAY;
2477 }
2478 
2479 /** parses variable information (in cip format) out of a string; if the parsing process was successful a loose variable
2480  * belonging to the transformed problem is created and captured; if variable is of integral type, fractional bounds are
2481  * automatically rounded; an integer variable with bounds zero and one is automatically converted into a binary
2482  * variable
2483  */
2485  SCIP_VAR** var, /**< pointer to variable data */
2486  BMS_BLKMEM* blkmem, /**< block memory */
2487  SCIP_SET* set, /**< global SCIP settings */
2488  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2489  SCIP_STAT* stat, /**< problem statistics */
2490  const char* str, /**< string to parse */
2491  SCIP_Bool initial, /**< should var's column be present in the initial root LP? */
2492  SCIP_Bool removable, /**< is var's column removable from the LP (due to aging or cleanup)? */
2493  SCIP_DECL_VARCOPY ((*varcopy)), /**< copies variable data if wanted to subscip, or NULL */
2494  SCIP_DECL_VARDELORIG ((*vardelorig)), /**< frees user data of original variable */
2495  SCIP_DECL_VARTRANS ((*vartrans)), /**< creates transformed user data by transforming original user data */
2496  SCIP_DECL_VARDELTRANS ((*vardeltrans)), /**< frees user data of transformed variable */
2497  SCIP_VARDATA* vardata, /**< user data for this specific variable */
2498  char** endptr, /**< pointer to store the final string position if successfully */
2499  SCIP_Bool* success /**< pointer store if the paring process was successful */
2500  )
2501 {
2502  char name[SCIP_MAXSTRLEN];
2503  SCIP_Real lb;
2504  SCIP_Real ub;
2505  SCIP_Real obj;
2506  SCIP_VARTYPE vartype;
2507  SCIP_Real lazylb;
2508  SCIP_Real lazyub;
2509 
2510  assert(var != NULL);
2511  assert(blkmem != NULL);
2512  assert(endptr != NULL);
2513  assert(success != NULL);
2514 
2515  /* parse string in cip format for variable information */
2516  SCIP_CALL( varParse(set, messagehdlr, str, name, &lb, &ub, &obj, &vartype, &lazylb, &lazyub, TRUE, endptr, success) );
2517 
2518  if( *success )
2519  {
2520  /* create variable */
2521  SCIP_CALL( varCreate(var, blkmem, set, stat, name, lb, ub, obj, vartype, initial, removable,
2522  varcopy, vardelorig, vartrans, vardeltrans, vardata) );
2523 
2524  /* create event filter for transformed variable */
2525  SCIP_CALL( SCIPeventfilterCreate(&(*var)->eventfilter, blkmem) );
2526 
2527  /* set variable status and data */
2528  (*var)->varstatus = SCIP_VARSTATUS_LOOSE; /*lint !e641*/
2529 
2530  /* set lazy status of variable bounds */
2531  (*var)->lazylb = lazylb;
2532  (*var)->lazyub = lazyub;
2533 
2534  /* capture variable */
2535  SCIPvarCapture(*var);
2536  }
2537 
2538  return SCIP_OKAY;
2539 }
2540 
2541 /** ensures, that parentvars array of var can store at least num entries */
2542 static
2544  SCIP_VAR* var, /**< problem variable */
2545  BMS_BLKMEM* blkmem, /**< block memory */
2546  SCIP_SET* set, /**< global SCIP settings */
2547  int num /**< minimum number of entries to store */
2548  )
2549 {
2550  assert(var->nparentvars <= var->parentvarssize);
2551 
2552  if( num > var->parentvarssize )
2553  {
2554  int newsize;
2555 
2556  newsize = SCIPsetCalcMemGrowSize(set, num);
2557  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &var->parentvars, var->parentvarssize, newsize) );
2558  var->parentvarssize = newsize;
2559  }
2560  assert(num <= var->parentvarssize);
2561 
2562  return SCIP_OKAY;
2563 }
2564 
2565 /** adds variable to parent list of a variable and captures parent variable */
2566 static
2568  SCIP_VAR* var, /**< variable to add parent to */
2569  BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
2570  SCIP_SET* set, /**< global SCIP settings */
2571  SCIP_VAR* parentvar /**< parent variable to add */
2572  )
2573 {
2574  assert(var != NULL);
2575  assert(parentvar != NULL);
2576 
2577  /* the direct original counterpart must be stored as first parent */
2578  assert(var->nparentvars == 0 || SCIPvarGetStatus(parentvar) != SCIP_VARSTATUS_ORIGINAL);
2579 
2580  SCIPsetDebugMsg(set, "adding parent <%s>[%p] to variable <%s>[%p] in slot %d\n",
2581  parentvar->name, (void*)parentvar, var->name, (void*)var, var->nparentvars);
2582 
2583  SCIP_CALL( varEnsureParentvarsSize(var, blkmem, set, var->nparentvars+1) );
2584 
2585  var->parentvars[var->nparentvars] = parentvar;
2586  var->nparentvars++;
2587 
2588  SCIPvarCapture(parentvar);
2589 
2590  return SCIP_OKAY;
2591 }
2592 
2593 /** deletes and releases all variables from the parent list of a variable, frees the memory of parents array */
2594 static
2596  SCIP_VAR** var, /**< pointer to variable */
2597  BMS_BLKMEM* blkmem, /**< block memory */
2598  SCIP_SET* set, /**< global SCIP settings */
2599  SCIP_EVENTQUEUE* eventqueue, /**< event queue (or NULL, if it's an original variable) */
2600  SCIP_LP* lp /**< current LP data (or NULL, if it's an original variable) */
2601  )
2602 {
2603  SCIP_VAR* parentvar;
2604  int i;
2605 
2606  SCIPsetDebugMsg(set, "free parents of <%s>\n", (*var)->name);
2607 
2608  /* release the parent variables and remove the link from the parent variable to the child */
2609  for( i = 0; i < (*var)->nparentvars; ++i )
2610  {
2611  assert((*var)->parentvars != NULL);
2612  parentvar = (*var)->parentvars[i];
2613  assert(parentvar != NULL);
2614 
2615  switch( SCIPvarGetStatus(parentvar) )
2616  {
2618  assert(parentvar->data.original.transvar == *var);
2619  assert(&parentvar->data.original.transvar != var);
2620  parentvar->data.original.transvar = NULL;
2621  break;
2622 
2624  assert(parentvar->data.aggregate.var == *var);
2625  assert(&parentvar->data.aggregate.var != var);
2626  parentvar->data.aggregate.var = NULL;
2627  break;
2628 
2629 #if 0
2630  /* The following code is unclear: should the current variable be removed from its parents? */
2632  assert(parentvar->data.multaggr.vars != NULL);
2633  for( v = 0; v < parentvar->data.multaggr.nvars && parentvar->data.multaggr.vars[v] != *var; ++v )
2634  {}
2635  assert(v < parentvar->data.multaggr.nvars && parentvar->data.multaggr.vars[v] == *var);
2636  if( v < parentvar->data.multaggr.nvars-1 )
2637  {
2638  parentvar->data.multaggr.vars[v] = parentvar->data.multaggr.vars[parentvar->data.multaggr.nvars-1];
2639  parentvar->data.multaggr.scalars[v] = parentvar->data.multaggr.scalars[parentvar->data.multaggr.nvars-1];
2640  }
2641  parentvar->data.multaggr.nvars--;
2642  break;
2643 #endif
2644 
2646  assert(parentvar->negatedvar == *var);
2647  assert((*var)->negatedvar == parentvar);
2648  parentvar->negatedvar = NULL;
2649  (*var)->negatedvar = NULL;
2650  break;
2651 
2652  default:
2653  SCIPerrorMessage("parent variable is neither ORIGINAL, AGGREGATED nor NEGATED\n");
2654  return SCIP_INVALIDDATA;
2655  } /*lint !e788*/
2656 
2657  SCIP_CALL( SCIPvarRelease(&(*var)->parentvars[i], blkmem, set, eventqueue, lp) );
2658  }
2659 
2660  /* free parentvars array */
2661  BMSfreeBlockMemoryArrayNull(blkmem, &(*var)->parentvars, (*var)->parentvarssize);
2662 
2663  return SCIP_OKAY;
2664 }
2665 
2666 /** frees a variable */
2667 static
2669  SCIP_VAR** var, /**< pointer to variable */
2670  BMS_BLKMEM* blkmem, /**< block memory */
2671  SCIP_SET* set, /**< global SCIP settings */
2672  SCIP_EVENTQUEUE* eventqueue, /**< event queue (may be NULL, if it's not a column variable) */
2673  SCIP_LP* lp /**< current LP data (may be NULL, if it's not a column variable) */
2674  )
2675 {
2676  assert(var != NULL);
2677  assert(*var != NULL);
2678  assert(SCIPvarGetStatus(*var) != SCIP_VARSTATUS_COLUMN || &(*var)->data.col->var != var);
2679  assert((*var)->nuses == 0);
2680  assert((*var)->probindex == -1);
2681 
2682  SCIPsetDebugMsg(set, "free variable <%s> with status=%d\n", (*var)->name, SCIPvarGetStatus(*var));
2683 
2684  switch( SCIPvarGetStatus(*var) )
2685  {
2687  assert((*var)->data.original.transvar == NULL); /* cannot free variable, if transformed variable is still existing */
2688  holelistFree(&(*var)->data.original.origdom.holelist, blkmem);
2689  assert((*var)->data.original.origdom.holelist == NULL);
2690  break;
2691  case SCIP_VARSTATUS_LOOSE:
2692  break;
2693  case SCIP_VARSTATUS_COLUMN:
2694  SCIP_CALL( SCIPcolFree(&(*var)->data.col, blkmem, set, eventqueue, lp) ); /* free corresponding LP column */
2695  break;
2696  case SCIP_VARSTATUS_FIXED:
2698  break;
2700  BMSfreeBlockMemoryArray(blkmem, &(*var)->data.multaggr.vars, (*var)->data.multaggr.varssize);
2701  BMSfreeBlockMemoryArray(blkmem, &(*var)->data.multaggr.scalars, (*var)->data.multaggr.varssize);
2702  break;
2704  break;
2705  default:
2706  SCIPerrorMessage("unknown variable status\n");
2707  return SCIP_INVALIDDATA;
2708  }
2709 
2710  /* release all parent variables and free the parentvars array */
2711  SCIP_CALL( varFreeParents(var, blkmem, set, eventqueue, lp) );
2712 
2713  /* free user data */
2715  {
2716  if( (*var)->vardelorig != NULL )
2717  {
2718  SCIP_CALL( (*var)->vardelorig(set->scip, *var, &(*var)->vardata) );
2719  }
2720  }
2721  else
2722  {
2723  if( (*var)->vardeltrans != NULL )
2724  {
2725  SCIP_CALL( (*var)->vardeltrans(set->scip, *var, &(*var)->vardata) );
2726  }
2727  }
2728 
2729  /* free event filter */
2730  if( (*var)->eventfilter != NULL )
2731  {
2732  SCIP_CALL( SCIPeventfilterFree(&(*var)->eventfilter, blkmem, set) );
2733  }
2734  assert((*var)->eventfilter == NULL);
2735 
2736  /* free hole lists */
2737  holelistFree(&(*var)->glbdom.holelist, blkmem);
2738  holelistFree(&(*var)->locdom.holelist, blkmem);
2739  assert((*var)->glbdom.holelist == NULL);
2740  assert((*var)->locdom.holelist == NULL);
2741 
2742  /* free variable bounds data structures */
2743  SCIPvboundsFree(&(*var)->vlbs, blkmem);
2744  SCIPvboundsFree(&(*var)->vubs, blkmem);
2745 
2746  /* free implications data structures */
2747  SCIPimplicsFree(&(*var)->implics, blkmem);
2748 
2749  /* free clique list data structures */
2750  SCIPcliquelistFree(&(*var)->cliquelist, blkmem);
2751 
2752  /* free bound change information arrays */
2753  BMSfreeBlockMemoryArrayNull(blkmem, &(*var)->lbchginfos, (*var)->lbchginfossize);
2754  BMSfreeBlockMemoryArrayNull(blkmem, &(*var)->ubchginfos, (*var)->ubchginfossize);
2755 
2756  /* free branching and inference history entries */
2757  SCIPhistoryFree(&(*var)->history, blkmem);
2758  SCIPhistoryFree(&(*var)->historycrun, blkmem);
2759  SCIPvaluehistoryFree(&(*var)->valuehistory, blkmem);
2760 
2761  /* free variable data structure */
2762  BMSfreeBlockMemoryArray(blkmem, &(*var)->name, strlen((*var)->name)+1);
2763  BMSfreeBlockMemory(blkmem, var);
2764 
2765  return SCIP_OKAY;
2766 }
2767 
2768 /** increases usage counter of variable */
2769 void SCIPvarCapture(
2770  SCIP_VAR* var /**< variable */
2771  )
2772 {
2773  assert(var != NULL);
2774  assert(var->nuses >= 0);
2775 
2776  SCIPdebugMessage("capture variable <%s> with nuses=%d\n", var->name, var->nuses);
2777  var->nuses++;
2778 }
2779 
2780 /** decreases usage counter of variable, and frees memory if necessary */
2782  SCIP_VAR** var, /**< pointer to variable */
2783  BMS_BLKMEM* blkmem, /**< block memory */
2784  SCIP_SET* set, /**< global SCIP settings */
2785  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2786  SCIP_LP* lp /**< current LP data (or NULL, if it's an original variable) */
2787  )
2788 {
2789  assert(var != NULL);
2790  assert(*var != NULL);
2791  assert((*var)->nuses >= 1);
2792  assert(blkmem != NULL);
2793  assert((*var)->scip == set->scip);
2794 
2795  SCIPsetDebugMsg(set, "release variable <%s> with nuses=%d\n", (*var)->name, (*var)->nuses);
2796  (*var)->nuses--;
2797  if( (*var)->nuses == 0 )
2798  {
2799  SCIP_CALL( varFree(var, blkmem, set, eventqueue, lp) );
2800  }
2801 
2802  *var = NULL;
2803 
2804  return SCIP_OKAY;
2805 }
2806 
2807 /** change variable name */
2809  SCIP_VAR* var, /**< problem variable */
2810  BMS_BLKMEM* blkmem, /**< block memory */
2811  const char* name /**< name of variable */
2812  )
2813 {
2814  assert(name != NULL);
2815 
2816  /* remove old variable name */
2817  BMSfreeBlockMemoryArray(blkmem, &var->name, strlen(var->name)+1);
2818 
2819  /* set new variable name */
2820  SCIP_CALL( varSetName(var, blkmem, NULL, name) );
2821 
2822  return SCIP_OKAY;
2823 }
2824 
2825 /** initializes variable data structure for solving */
2826 void SCIPvarInitSolve(
2827  SCIP_VAR* var /**< problem variable */
2828  )
2829 {
2830  assert(var != NULL);
2831 
2833  var->conflictlbcount = 0;
2834  var->conflictubcount = 0;
2835 }
2836 
2837 /** outputs the given bounds into the file stream */
2838 static
2839 void printBounds(
2840  SCIP_SET* set, /**< global SCIP settings */
2841  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2842  FILE* file, /**< output file (or NULL for standard output) */
2843  SCIP_Real lb, /**< lower bound */
2844  SCIP_Real ub, /**< upper bound */
2845  const char* name /**< bound type name */
2846  )
2847 {
2848  assert(set != NULL);
2849 
2850  SCIPmessageFPrintInfo(messagehdlr, file, ", %s=", name);
2851  if( SCIPsetIsInfinity(set, lb) )
2852  SCIPmessageFPrintInfo(messagehdlr, file, "[+inf,");
2853  else if( SCIPsetIsInfinity(set, -lb) )
2854  SCIPmessageFPrintInfo(messagehdlr, file, "[-inf,");
2855  else
2856  SCIPmessageFPrintInfo(messagehdlr, file, "[%.15g,", lb);
2857  if( SCIPsetIsInfinity(set, ub) )
2858  SCIPmessageFPrintInfo(messagehdlr, file, "+inf]");
2859  else if( SCIPsetIsInfinity(set, -ub) )
2860  SCIPmessageFPrintInfo(messagehdlr, file, "-inf]");
2861  else
2862  SCIPmessageFPrintInfo(messagehdlr, file, "%.15g]", ub);
2863 }
2864 
2865 /** prints hole list to file stream */
2866 static
2867 void printHolelist(
2868  SCIP_SET* set, /**< global SCIP settings */
2869  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2870  FILE* file, /**< output file (or NULL for standard output) */
2871  SCIP_HOLELIST* holelist, /**< hole list pointer to hole of interest */
2872  const char* name /**< hole type name */
2873  )
2874 { /*lint --e{715}*/
2875  SCIP_Real left;
2876  SCIP_Real right;
2877 
2878  if( holelist == NULL )
2879  return;
2880 
2881  left = SCIPholelistGetLeft(holelist);
2882  right = SCIPholelistGetRight(holelist);
2883 
2884  /* display first hole */
2885  SCIPmessageFPrintInfo(messagehdlr, file, ", %s=(%g,%g)", name, left, right);
2886  holelist = SCIPholelistGetNext(holelist);
2887 
2888  while(holelist != NULL )
2889  {
2890  left = SCIPholelistGetLeft(holelist);
2891  right = SCIPholelistGetRight(holelist);
2892 
2893  /* display hole */
2894  SCIPmessageFPrintInfo(messagehdlr, file, "(%g,%g)", left, right);
2895 
2896  /* get next hole */
2897  holelist = SCIPholelistGetNext(holelist);
2898  }
2899 }
2900 
2901 /** outputs variable information into file stream */
2903  SCIP_VAR* var, /**< problem variable */
2904  SCIP_SET* set, /**< global SCIP settings */
2905  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2906  FILE* file /**< output file (or NULL for standard output) */
2907  )
2908 {
2909  SCIP_HOLELIST* holelist;
2910  SCIP_Real lb;
2911  SCIP_Real ub;
2912  int i;
2913 
2914  assert(var != NULL);
2915  assert(var->scip == set->scip);
2916 
2917  /* type of variable */
2918  switch( SCIPvarGetType(var) )
2919  {
2920  case SCIP_VARTYPE_BINARY:
2921  SCIPmessageFPrintInfo(messagehdlr, file, " [binary]");
2922  break;
2923  case SCIP_VARTYPE_INTEGER:
2924  SCIPmessageFPrintInfo(messagehdlr, file, " [integer]");
2925  break;
2926  case SCIP_VARTYPE_IMPLINT:
2927  SCIPmessageFPrintInfo(messagehdlr, file, " [implicit]");
2928  break;
2930  SCIPmessageFPrintInfo(messagehdlr, file, " [continuous]");
2931  break;
2932  default:
2933  SCIPerrorMessage("unknown variable type\n");
2934  SCIPABORT();
2935  return SCIP_ERROR; /*lint !e527*/
2936  }
2937 
2938  /* name */
2939  SCIPmessageFPrintInfo(messagehdlr, file, " <%s>:", var->name);
2940 
2941  /* objective value */
2942  SCIPmessageFPrintInfo(messagehdlr, file, " obj=%.15g", var->obj);
2943 
2944  /* bounds (global bounds for transformed variables, original bounds for original variables) */
2945  if( !SCIPvarIsTransformed(var) )
2946  {
2947  /* output original bound */
2948  lb = SCIPvarGetLbOriginal(var);
2949  ub = SCIPvarGetUbOriginal(var);
2950  printBounds(set, messagehdlr, file, lb, ub, "original bounds");
2951 
2952  /* output lazy bound */
2953  lb = SCIPvarGetLbLazy(var);
2954  ub = SCIPvarGetUbLazy(var);
2955 
2956  /* only display the lazy bounds if they are different from [-infinity,infinity] */
2957  if( !SCIPsetIsInfinity(set, -lb) || !SCIPsetIsInfinity(set, ub) )
2958  printBounds(set, messagehdlr, file, lb, ub, "lazy bounds");
2959 
2960  holelist = SCIPvarGetHolelistOriginal(var);
2961  printHolelist(set, messagehdlr, file, holelist, "original holes");
2962  }
2963  else
2964  {
2965  /* output global bound */
2966  lb = SCIPvarGetLbGlobal(var);
2967  ub = SCIPvarGetUbGlobal(var);
2968  printBounds(set, messagehdlr, file, lb, ub, "global bounds");
2969 
2970  /* output local bound */
2971  lb = SCIPvarGetLbLocal(var);
2972  ub = SCIPvarGetUbLocal(var);
2973  printBounds(set, messagehdlr, file, lb, ub, "local bounds");
2974 
2975  /* output lazy bound */
2976  lb = SCIPvarGetLbLazy(var);
2977  ub = SCIPvarGetUbLazy(var);
2978 
2979  /* only display the lazy bounds if they are different from [-infinity,infinity] */
2980  if( !SCIPsetIsInfinity(set, -lb) || !SCIPsetIsInfinity(set, ub) )
2981  printBounds(set, messagehdlr, file, lb, ub, "lazy bounds");
2982 
2983  /* global hole list */
2984  holelist = SCIPvarGetHolelistGlobal(var);
2985  printHolelist(set, messagehdlr, file, holelist, "global holes");
2986 
2987  /* local hole list */
2988  holelist = SCIPvarGetHolelistLocal(var);
2989  printHolelist(set, messagehdlr, file, holelist, "local holes");
2990  }
2991 
2992  /* fixings and aggregations */
2993  switch( SCIPvarGetStatus(var) )
2994  {
2996  case SCIP_VARSTATUS_LOOSE:
2997  case SCIP_VARSTATUS_COLUMN:
2998  break;
2999 
3000  case SCIP_VARSTATUS_FIXED:
3001  SCIPmessageFPrintInfo(messagehdlr, file, ", fixed:");
3002  if( SCIPsetIsInfinity(set, var->glbdom.lb) )
3003  SCIPmessageFPrintInfo(messagehdlr, file, "+inf");
3004  else if( SCIPsetIsInfinity(set, -var->glbdom.lb) )
3005  SCIPmessageFPrintInfo(messagehdlr, file, "-inf");
3006  else
3007  SCIPmessageFPrintInfo(messagehdlr, file, "%.15g", var->glbdom.lb);
3008  break;
3009 
3011  SCIPmessageFPrintInfo(messagehdlr, file, ", aggregated:");
3012  if( !SCIPsetIsZero(set, var->data.aggregate.constant) )
3013  SCIPmessageFPrintInfo(messagehdlr, file, " %.15g", var->data.aggregate.constant);
3014  SCIPmessageFPrintInfo(messagehdlr, file, " %+.15g<%s>", var->data.aggregate.scalar, SCIPvarGetName(var->data.aggregate.var));
3015  break;
3016 
3018  SCIPmessageFPrintInfo(messagehdlr, file, ", aggregated:");
3019  if( var->data.multaggr.nvars == 0 || !SCIPsetIsZero(set, var->data.multaggr.constant) )
3020  SCIPmessageFPrintInfo(messagehdlr, file, " %.15g", var->data.multaggr.constant);
3021  for( i = 0; i < var->data.multaggr.nvars; ++i )
3022  SCIPmessageFPrintInfo(messagehdlr, file, " %+.15g<%s>", var->data.multaggr.scalars[i], SCIPvarGetName(var->data.multaggr.vars[i]));
3023  break;
3024 
3026  SCIPmessageFPrintInfo(messagehdlr, file, ", negated: %.15g - <%s>", var->data.negate.constant, SCIPvarGetName(var->negatedvar));
3027  break;
3028 
3029  default:
3030  SCIPerrorMessage("unknown variable status\n");
3031  SCIPABORT();
3032  return SCIP_ERROR; /*lint !e527*/
3033  }
3034 
3035  SCIPmessageFPrintInfo(messagehdlr, file, "\n");
3036 
3037  return SCIP_OKAY;
3038 }
3039 
3040 /** issues a VARUNLOCKED event on the given variable */
3041 static
3043  SCIP_VAR* var, /**< problem variable to change */
3044  BMS_BLKMEM* blkmem, /**< block memory */
3045  SCIP_SET* set, /**< global SCIP settings */
3046  SCIP_EVENTQUEUE* eventqueue /**< event queue */
3047  )
3048 {
3049  SCIP_EVENT* event;
3050 
3051  assert(var != NULL);
3052  assert(var->nlocksdown[SCIP_LOCKTYPE_MODEL] <= 1 && var->nlocksup[SCIP_LOCKTYPE_MODEL] <= 1);
3053  assert(var->scip == set->scip);
3054 
3055  /* issue VARUNLOCKED event on variable */
3056  SCIP_CALL( SCIPeventCreateVarUnlocked(&event, blkmem, var) );
3057  SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, NULL, &event) );
3058 
3059  return SCIP_OKAY;
3060 }
3061 
3062 /** modifies lock numbers for rounding */
3064  SCIP_VAR* var, /**< problem variable */
3065  BMS_BLKMEM* blkmem, /**< block memory */
3066  SCIP_SET* set, /**< global SCIP settings */
3067  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3068  SCIP_LOCKTYPE locktype, /**< type of the variable locks */
3069  int addnlocksdown, /**< increase in number of rounding down locks */
3070  int addnlocksup /**< increase in number of rounding up locks */
3071  )
3072 {
3073  SCIP_VAR* lockvar;
3074 
3075  assert(var != NULL);
3076  assert((int)locktype >= 0 && (int)locktype < (int)NLOCKTYPES); /*lint !e685 !e568q*/
3077  assert(var->nlocksup[locktype] >= 0);
3078  assert(var->nlocksdown[locktype] >= 0);
3079  assert(var->scip == set->scip);
3080 
3081  if( addnlocksdown == 0 && addnlocksup == 0 )
3082  return SCIP_OKAY;
3083 
3084 #ifdef SCIP_DEBUG
3085  SCIPsetDebugMsg(set, "add rounding locks %d/%d to variable <%s> (locks=%d/%d, type=%u)\n",
3086  addnlocksdown, addnlocksup, var->name, var->nlocksdown[locktype], var->nlocksup[locktype], locktype);
3087 #endif
3088 
3089  lockvar = var;
3090 
3091  while( TRUE ) /*lint !e716 */
3092  {
3093  assert(lockvar != NULL);
3094 
3095  switch( SCIPvarGetStatus(lockvar) )
3096  {
3098  if( lockvar->data.original.transvar != NULL )
3099  {
3100  lockvar = lockvar->data.original.transvar;
3101  break;
3102  }
3103  else
3104  {
3105  lockvar->nlocksdown[locktype] += addnlocksdown;
3106  lockvar->nlocksup[locktype] += addnlocksup;
3107 
3108  assert(lockvar->nlocksdown[locktype] >= 0);
3109  assert(lockvar->nlocksup[locktype] >= 0);
3110 
3111  return SCIP_OKAY;
3112  }
3113  case SCIP_VARSTATUS_LOOSE:
3114  case SCIP_VARSTATUS_COLUMN:
3115  case SCIP_VARSTATUS_FIXED:
3116  lockvar->nlocksdown[locktype] += addnlocksdown;
3117  lockvar->nlocksup[locktype] += addnlocksup;
3118 
3119  assert(lockvar->nlocksdown[locktype] >= 0);
3120  assert(lockvar->nlocksup[locktype] >= 0);
3121 
3122  if( locktype == SCIP_LOCKTYPE_MODEL && lockvar->nlocksdown[locktype] <= 1
3123  && lockvar->nlocksup[locktype] <= 1 )
3124  {
3125  SCIP_CALL( varEventVarUnlocked(lockvar, blkmem, set, eventqueue) );
3126  }
3127 
3128  return SCIP_OKAY;
3130  if( lockvar->data.aggregate.scalar < 0.0 )
3131  {
3132  int tmp = addnlocksup;
3133 
3134  addnlocksup = addnlocksdown;
3135  addnlocksdown = tmp;
3136  }
3137 
3138  lockvar = lockvar->data.aggregate.var;
3139  break;
3141  {
3142  int v;
3143 
3144  assert(!lockvar->donotmultaggr);
3145 
3146  for( v = lockvar->data.multaggr.nvars - 1; v >= 0; --v )
3147  {
3148  if( lockvar->data.multaggr.scalars[v] > 0.0 )
3149  {
3150  SCIP_CALL( SCIPvarAddLocks(lockvar->data.multaggr.vars[v], blkmem, set, eventqueue, locktype, addnlocksdown,
3151  addnlocksup) );
3152  }
3153  else
3154  {
3155  SCIP_CALL( SCIPvarAddLocks(lockvar->data.multaggr.vars[v], blkmem, set, eventqueue, locktype, addnlocksup,
3156  addnlocksdown) );
3157  }
3158  }
3159  return SCIP_OKAY;
3160  }
3162  {
3163  int tmp = addnlocksup;
3164 
3165  assert(lockvar->negatedvar != NULL);
3166  assert(SCIPvarGetStatus(lockvar->negatedvar) != SCIP_VARSTATUS_NEGATED);
3167  assert(lockvar->negatedvar->negatedvar == lockvar);
3168 
3169  addnlocksup = addnlocksdown;
3170  addnlocksdown = tmp;
3171 
3172  lockvar = lockvar->negatedvar;
3173  break;
3174  }
3175  default:
3176  SCIPerrorMessage("unknown variable status\n");
3177  return SCIP_INVALIDDATA;
3178  }
3179  }
3180 }
3181 
3182 /** gets number of locks for rounding down of a special type */
3184  SCIP_VAR* var, /**< problem variable */
3185  SCIP_LOCKTYPE locktype /**< type of variable locks */
3186  )
3187 {
3188  int nlocks;
3189  int i;
3190 
3191  assert(var != NULL);
3192  assert((int)locktype >= 0 && (int)locktype < (int)NLOCKTYPES); /*lint !e685 !e568q*/
3193  assert(var->nlocksdown[locktype] >= 0);
3194 
3195  switch( SCIPvarGetStatus(var) )
3196  {
3198  if( var->data.original.transvar != NULL )
3199  return SCIPvarGetNLocksDownType(var->data.original.transvar, locktype);
3200  else
3201  return var->nlocksdown[locktype];
3202 
3203  case SCIP_VARSTATUS_LOOSE:
3204  case SCIP_VARSTATUS_COLUMN:
3205  case SCIP_VARSTATUS_FIXED:
3206  return var->nlocksdown[locktype];
3207 
3209  if( var->data.aggregate.scalar > 0.0 )
3210  return SCIPvarGetNLocksDownType(var->data.aggregate.var, locktype);
3211  else
3212  return SCIPvarGetNLocksUpType(var->data.aggregate.var, locktype);
3213 
3215  assert(!var->donotmultaggr);
3216  nlocks = 0;
3217  for( i = 0; i < var->data.multaggr.nvars; ++i )
3218  {
3219  if( var->data.multaggr.scalars[i] > 0.0 )
3220  nlocks += SCIPvarGetNLocksDownType(var->data.multaggr.vars[i], locktype);
3221  else
3222  nlocks += SCIPvarGetNLocksUpType(var->data.multaggr.vars[i], locktype);
3223  }
3224  return nlocks;
3225 
3227  assert(var->negatedvar != NULL);
3229  assert(var->negatedvar->negatedvar == var);
3230  return SCIPvarGetNLocksUpType(var->negatedvar, locktype);
3231 
3232  default:
3233  SCIPerrorMessage("unknown variable status\n");
3234  SCIPABORT();
3235  return INT_MAX; /*lint !e527*/
3236  }
3237 }
3238 
3239 /** gets number of locks for rounding up of a special type */
3241  SCIP_VAR* var, /**< problem variable */
3242  SCIP_LOCKTYPE locktype /**< type of variable locks */
3243  )
3244 {
3245  int nlocks;
3246  int i;
3247 
3248  assert(var != NULL);
3249  assert((int)locktype >= 0 && (int)locktype < (int)NLOCKTYPES); /*lint !e685 !e568q*/
3250  assert(var->nlocksup[locktype] >= 0);
3251 
3252  switch( SCIPvarGetStatus(var) )
3253  {
3255  if( var->data.original.transvar != NULL )
3256  return SCIPvarGetNLocksUpType(var->data.original.transvar, locktype);
3257  else
3258  return var->nlocksup[locktype];
3259 
3260  case SCIP_VARSTATUS_LOOSE:
3261  case SCIP_VARSTATUS_COLUMN:
3262  case SCIP_VARSTATUS_FIXED:
3263  return var->nlocksup[locktype];
3264 
3266  if( var->data.aggregate.scalar > 0.0 )
3267  return SCIPvarGetNLocksUpType(var->data.aggregate.var, locktype);
3268  else
3269  return SCIPvarGetNLocksDownType(var->data.aggregate.var, locktype);
3270 
3272  assert(!var->donotmultaggr);
3273  nlocks = 0;
3274  for( i = 0; i < var->data.multaggr.nvars; ++i )
3275  {
3276  if( var->data.multaggr.scalars[i] > 0.0 )
3277  nlocks += SCIPvarGetNLocksUpType(var->data.multaggr.vars[i], locktype);
3278  else
3279  nlocks += SCIPvarGetNLocksDownType(var->data.multaggr.vars[i], locktype);
3280  }
3281  return nlocks;
3282 
3284  assert(var->negatedvar != NULL);
3286  assert(var->negatedvar->negatedvar == var);
3287  return SCIPvarGetNLocksDownType(var->negatedvar, locktype);
3288 
3289  default:
3290  SCIPerrorMessage("unknown variable status\n");
3291  SCIPABORT();
3292  return INT_MAX; /*lint !e527*/
3293  }
3294 }
3295 
3296 /** gets number of locks for rounding down
3297  *
3298  * @note This method will always return variable locks of type model
3299  *
3300  * @note It is recommented to use SCIPvarGetNLocksDownType()
3301  */
3303  SCIP_VAR* var /**< problem variable */
3304  )
3305 {
3307 }
3308 
3309 /** gets number of locks for rounding up
3310  *
3311  * @note This method will always return variable locks of type model
3312  *
3313  * @note It is recommented to use SCIPvarGetNLocksUpType()
3314  */
3315 int SCIPvarGetNLocksUp(
3316  SCIP_VAR* var /**< problem variable */
3317  )
3318 {
3320 }
3321 
3322 /** is it possible, to round variable down and stay feasible?
3323  *
3324  * @note This method will always check w.r.t variable locks of type model
3325  */
3327  SCIP_VAR* var /**< problem variable */
3328  )
3329 {
3330  return (SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == 0);
3331 }
3332 
3333 /** is it possible, to round variable up and stay feasible?
3334  *
3335  * @note This method will always check w.r.t. variable locks of type model
3336  */
3338  SCIP_VAR* var /**< problem variable */
3339  )
3340 {
3341  return (SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == 0);
3342 }
3343 
3344 /** gets and captures transformed variable of a given variable; if the variable is not yet transformed,
3345  * a new transformed variable for this variable is created
3346  */
3348  SCIP_VAR* origvar, /**< original problem variable */
3349  BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
3350  SCIP_SET* set, /**< global SCIP settings */
3351  SCIP_STAT* stat, /**< problem statistics */
3352  SCIP_OBJSENSE objsense, /**< objective sense of original problem; transformed is always MINIMIZE */
3353  SCIP_VAR** transvar /**< pointer to store the transformed variable */
3354  )
3355 {
3356  char name[SCIP_MAXSTRLEN];
3357 
3358  assert(origvar != NULL);
3359  assert(origvar->scip == set->scip);
3360  assert(SCIPvarGetStatus(origvar) == SCIP_VARSTATUS_ORIGINAL);
3361  assert(SCIPsetIsEQ(set, origvar->glbdom.lb, origvar->locdom.lb));
3362  assert(SCIPsetIsEQ(set, origvar->glbdom.ub, origvar->locdom.ub));
3363  assert(origvar->vlbs == NULL);
3364  assert(origvar->vubs == NULL);
3365  assert(transvar != NULL);
3366 
3367  /* check if variable is already transformed */
3368  if( origvar->data.original.transvar != NULL )
3369  {
3370  *transvar = origvar->data.original.transvar;
3371  SCIPvarCapture(*transvar);
3372  }
3373  else
3374  {
3375  int i;
3376 
3377  /* create transformed variable */
3378  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "t_%s", origvar->name);
3379  SCIP_CALL( SCIPvarCreateTransformed(transvar, blkmem, set, stat, name,
3380  origvar->glbdom.lb, origvar->glbdom.ub, (SCIP_Real)objsense * origvar->obj,
3381  SCIPvarGetType(origvar), origvar->initial, origvar->removable,
3382  origvar->vardelorig, origvar->vartrans, origvar->vardeltrans, origvar->varcopy, NULL) );
3383 
3384  /* copy the branch factor and priority */
3385  (*transvar)->branchfactor = origvar->branchfactor;
3386  (*transvar)->branchpriority = origvar->branchpriority;
3387  (*transvar)->branchdirection = origvar->branchdirection; /*lint !e732*/
3388 
3389  /* duplicate hole lists */
3390  SCIP_CALL( holelistDuplicate(&(*transvar)->glbdom.holelist, blkmem, set, origvar->glbdom.holelist) );
3391  SCIP_CALL( holelistDuplicate(&(*transvar)->locdom.holelist, blkmem, set, origvar->locdom.holelist) );
3392 
3393  /* link original and transformed variable */
3394  origvar->data.original.transvar = *transvar;
3395  SCIP_CALL( varAddParent(*transvar, blkmem, set, origvar) );
3396 
3397  /* copy rounding locks */
3398  for( i = 0; i < NLOCKTYPES; i++ )
3399  {
3400  (*transvar)->nlocksdown[i] = origvar->nlocksdown[i];
3401  (*transvar)->nlocksup[i] = origvar->nlocksup[i];
3402  assert((*transvar)->nlocksdown[i] >= 0);
3403  assert((*transvar)->nlocksup[i] >= 0);
3404  }
3405 
3406  /* copy doNotMultiaggr status */
3407  (*transvar)->donotmultaggr = origvar->donotmultaggr;
3408 
3409  /* copy lazy bounds */
3410  (*transvar)->lazylb = origvar->lazylb;
3411  (*transvar)->lazyub = origvar->lazyub;
3412 
3413  /* transfer eventual variable statistics; do not update global statistics, because this has been done
3414  * when original variable was created
3415  */
3416  SCIPhistoryUnite((*transvar)->history, origvar->history, FALSE);
3417 
3418  /* transform user data */
3419  if( origvar->vartrans != NULL )
3420  {
3421  SCIP_CALL( origvar->vartrans(set->scip, origvar, origvar->vardata, *transvar, &(*transvar)->vardata) );
3422  }
3423  else
3424  (*transvar)->vardata = origvar->vardata;
3425  }
3426 
3427  SCIPsetDebugMsg(set, "transformed variable: <%s>[%p] -> <%s>[%p]\n", origvar->name, (void*)origvar, (*transvar)->name, (void*)*transvar);
3428 
3429  return SCIP_OKAY;
3430 }
3431 
3432 /** gets corresponding transformed variable of an original or negated original variable */
3434  SCIP_VAR* origvar, /**< original problem variable */
3435  BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
3436  SCIP_SET* set, /**< global SCIP settings */
3437  SCIP_STAT* stat, /**< problem statistics */
3438  SCIP_VAR** transvar /**< pointer to store the transformed variable, or NULL if not existing yet */
3439  )
3440 {
3441  assert(origvar != NULL);
3443  assert(origvar->scip == set->scip);
3444 
3445  if( SCIPvarGetStatus(origvar) == SCIP_VARSTATUS_NEGATED )
3446  {
3447  assert(origvar->negatedvar != NULL);
3449 
3450  if( origvar->negatedvar->data.original.transvar == NULL )
3451  *transvar = NULL;
3452  else
3453  {
3454  SCIP_CALL( SCIPvarNegate(origvar->negatedvar->data.original.transvar, blkmem, set, stat, transvar) );
3455  }
3456  }
3457  else
3458  *transvar = origvar->data.original.transvar;
3459 
3460  return SCIP_OKAY;
3461 }
3462 
3463 /** converts loose transformed variable into column variable, creates LP column */
3465  SCIP_VAR* var, /**< problem variable */
3466  BMS_BLKMEM* blkmem, /**< block memory */
3467  SCIP_SET* set, /**< global SCIP settings */
3468  SCIP_STAT* stat, /**< problem statistics */
3469  SCIP_PROB* prob, /**< problem data */
3470  SCIP_LP* lp /**< current LP data */
3471  )
3472 {
3473  assert(var != NULL);
3474  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
3475  assert(var->scip == set->scip);
3476 
3477  SCIPsetDebugMsg(set, "creating column for variable <%s>\n", var->name);
3478 
3479  /* switch variable status */
3480  var->varstatus = SCIP_VARSTATUS_COLUMN; /*lint !e641*/
3481 
3482  /* create column of variable */
3483  SCIP_CALL( SCIPcolCreate(&var->data.col, blkmem, set, stat, var, 0, NULL, NULL, var->removable) );
3484 
3485  if( var->probindex != -1 )
3486  {
3487  /* inform problem about the variable's status change */
3488  SCIP_CALL( SCIPprobVarChangedStatus(prob, blkmem, set, NULL, NULL, var) );
3489 
3490  /* inform LP, that problem variable is now a column variable and no longer loose */
3491  SCIP_CALL( SCIPlpUpdateVarColumn(lp, set, var) );
3492  }
3493 
3494  return SCIP_OKAY;
3495 }
3496 
3497 /** converts column transformed variable back into loose variable, frees LP column */
3499  SCIP_VAR* var, /**< problem variable */
3500  BMS_BLKMEM* blkmem, /**< block memory */
3501  SCIP_SET* set, /**< global SCIP settings */
3502  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3503  SCIP_PROB* prob, /**< problem data */
3504  SCIP_LP* lp /**< current LP data */
3505  )
3506 {
3507  assert(var != NULL);
3508  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
3509  assert(var->scip == set->scip);
3510  assert(var->data.col != NULL);
3511  assert(var->data.col->lppos == -1);
3512  assert(var->data.col->lpipos == -1);
3513 
3514  SCIPsetDebugMsg(set, "deleting column for variable <%s>\n", var->name);
3515 
3516  /* free column of variable */
3517  SCIP_CALL( SCIPcolFree(&var->data.col, blkmem, set, eventqueue, lp) );
3518 
3519  /* switch variable status */
3520  var->varstatus = SCIP_VARSTATUS_LOOSE; /*lint !e641*/
3521 
3522  if( var->probindex != -1 )
3523  {
3524  /* inform problem about the variable's status change */
3525  SCIP_CALL( SCIPprobVarChangedStatus(prob, blkmem, set, NULL, NULL, var) );
3526 
3527  /* inform LP, that problem variable is now a loose variable and no longer a column */
3528  SCIP_CALL( SCIPlpUpdateVarLoose(lp, set, var) );
3529  }
3530 
3531  return SCIP_OKAY;
3532 }
3533 
3534 /** issues a VARFIXED event on the given variable and all its parents (except ORIGINAL parents);
3535  * the event issuing on the parents is necessary, because unlike with bound changes, the parent variables
3536  * are not informed about a fixing of an active variable they are pointing to
3537  */
3538 static
3540  SCIP_VAR* var, /**< problem variable to change */
3541  BMS_BLKMEM* blkmem, /**< block memory */
3542  SCIP_SET* set, /**< global SCIP settings */
3543  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3544  int fixeventtype /**< is this event a fixation(0), an aggregation(1), or a
3545  * multi-aggregation(2)
3546  */
3547  )
3548 {
3549  SCIP_EVENT* event;
3550  SCIP_VARSTATUS varstatus;
3551  int i;
3552 
3553  assert(var != NULL);
3554  assert(var->scip == set->scip);
3555  assert(0 <= fixeventtype && fixeventtype <= 2);
3556 
3557  /* issue VARFIXED event on variable */
3558  SCIP_CALL( SCIPeventCreateVarFixed(&event, blkmem, var) );
3559  SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, NULL, &event) );
3560 
3561 #ifndef NDEBUG
3562  for( i = var->nparentvars -1; i >= 0; --i )
3563  {
3565  }
3566 #endif
3567 
3568  switch( fixeventtype )
3569  {
3570  case 0:
3571  /* process all parents of a fixed variable */
3572  for( i = var->nparentvars - 1; i >= 0; --i )
3573  {
3574  varstatus = SCIPvarGetStatus(var->parentvars[i]);
3575 
3576  assert(varstatus != SCIP_VARSTATUS_FIXED);
3577 
3578  /* issue event on all not yet fixed parent variables, (that should already issued this event) except the original
3579  * one
3580  */
3581  if( varstatus != SCIP_VARSTATUS_ORIGINAL )
3582  {
3583  SCIP_CALL( varEventVarFixed(var->parentvars[i], blkmem, set, eventqueue, fixeventtype) );
3584  }
3585  }
3586  break;
3587  case 1:
3588  /* process all parents of a aggregated variable */
3589  for( i = var->nparentvars - 1; i >= 0; --i )
3590  {
3591  varstatus = SCIPvarGetStatus(var->parentvars[i]);
3592 
3593  assert(varstatus != SCIP_VARSTATUS_FIXED);
3594 
3595  /* issue event for not aggregated parent variable, because for these and its parents the var event was already
3596  * issued(, except the original one)
3597  *
3598  * @note that even before an aggregated parent variable, there might be variables, for which the vent was not
3599  * yet issued
3600  */
3601  if( varstatus == SCIP_VARSTATUS_AGGREGATED )
3602  continue;
3603 
3604  if( varstatus != SCIP_VARSTATUS_ORIGINAL )
3605  {
3606  SCIP_CALL( varEventVarFixed(var->parentvars[i], blkmem, set, eventqueue, fixeventtype) );
3607  }
3608  }
3609  break;
3610  case 2:
3611  /* process all parents of a aggregated variable */
3612  for( i = var->nparentvars - 1; i >= 0; --i )
3613  {
3614  varstatus = SCIPvarGetStatus(var->parentvars[i]);
3615 
3616  assert(varstatus != SCIP_VARSTATUS_FIXED);
3617 
3618  /* issue event on all parent variables except the original one */
3619  if( varstatus != SCIP_VARSTATUS_ORIGINAL )
3620  {
3621  SCIP_CALL( varEventVarFixed(var->parentvars[i], blkmem, set, eventqueue, fixeventtype) );
3622  }
3623  }
3624  break;
3625  default:
3626  SCIPerrorMessage("unknown variable fixation event origin\n");
3627  return SCIP_INVALIDDATA;
3628  }
3629 
3630  return SCIP_OKAY;
3631 }
3632 
3633 /** converts variable into fixed variable */
3635  SCIP_VAR* var, /**< problem variable */
3636  BMS_BLKMEM* blkmem, /**< block memory */
3637  SCIP_SET* set, /**< global SCIP settings */
3638  SCIP_STAT* stat, /**< problem statistics */
3639  SCIP_PROB* transprob, /**< tranformed problem data */
3640  SCIP_PROB* origprob, /**< original problem data */
3641  SCIP_PRIMAL* primal, /**< primal data */
3642  SCIP_TREE* tree, /**< branch and bound tree */
3643  SCIP_REOPT* reopt, /**< reoptimization data structure */
3644  SCIP_LP* lp, /**< current LP data */
3645  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3646  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3647  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3648  SCIP_Real fixedval, /**< value to fix variable at */
3649  SCIP_Bool* infeasible, /**< pointer to store whether the fixing is infeasible */
3650  SCIP_Bool* fixed /**< pointer to store whether the fixing was performed (variable was unfixed) */
3651  )
3652 {
3653  SCIP_Real obj;
3654  SCIP_Real childfixedval;
3655 
3656  assert(var != NULL);
3657  assert(var->scip == set->scip);
3658  assert(SCIPsetIsEQ(set, var->glbdom.lb, var->locdom.lb));
3659  assert(SCIPsetIsEQ(set, var->glbdom.ub, var->locdom.ub));
3660  assert(infeasible != NULL);
3661  assert(fixed != NULL);
3662 
3663  SCIPsetDebugMsg(set, "fix variable <%s>[%g,%g] to %g\n", var->name, var->glbdom.lb, var->glbdom.ub, fixedval);
3664 
3665  *infeasible = FALSE;
3666  *fixed = FALSE;
3667 
3669  {
3670  *infeasible = !SCIPsetIsFeasEQ(set, fixedval, var->locdom.lb);
3671  SCIPsetDebugMsg(set, " -> variable already fixed to %g (fixedval=%g): infeasible=%u\n", var->locdom.lb, fixedval, *infeasible);
3672  return SCIP_OKAY;
3673  }
3674  else if( (SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS && !SCIPsetIsFeasIntegral(set, fixedval))
3675  || SCIPsetIsFeasLT(set, fixedval, var->locdom.lb)
3676  || SCIPsetIsFeasGT(set, fixedval, var->locdom.ub) )
3677  {
3678  SCIPsetDebugMsg(set, " -> fixing infeasible: locdom=[%g,%g], fixedval=%g\n", var->locdom.lb, var->locdom.ub, fixedval);
3679  *infeasible = TRUE;
3680  return SCIP_OKAY;
3681  }
3682 
3683  switch( SCIPvarGetStatus(var) )
3684  {
3686  if( var->data.original.transvar == NULL )
3687  {
3688  SCIPerrorMessage("cannot fix an untransformed original variable\n");
3689  return SCIP_INVALIDDATA;
3690  }
3691  SCIP_CALL( SCIPvarFix(var->data.original.transvar, blkmem, set, stat, transprob, origprob, primal, tree, reopt,
3692  lp, branchcand, eventqueue, cliquetable, fixedval, infeasible, fixed) );
3693  break;
3694 
3695  case SCIP_VARSTATUS_LOOSE:
3696  assert(!SCIPeventqueueIsDelayed(eventqueue)); /* otherwise, the pseudo objective value update gets confused */
3697 
3698  /* set the fixed variable's objective value to 0.0 */
3699  obj = var->obj;
3700  SCIP_CALL( SCIPvarChgObj(var, blkmem, set, transprob, primal, lp, eventqueue, 0.0) );
3701 
3702  /* since we change the variable type form loose to fixed, we have to adjust the number of loose
3703  * variables in the LP data structure; the loose objective value (looseobjval) in the LP data structure, however,
3704  * gets adjusted automatically, due to the event SCIP_EVENTTYPE_OBJCHANGED which dropped in the moment where the
3705  * objective of this variable is set to zero
3706  */
3707  SCIPlpDecNLoosevars(lp);
3708 
3709  /* change variable's bounds to fixed value (thereby removing redundant implications and variable bounds) */
3710  holelistFree(&var->glbdom.holelist, blkmem);
3711  holelistFree(&var->locdom.holelist, blkmem);
3712  SCIP_CALL( SCIPvarChgLbGlobal(var, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, fixedval) );
3713  SCIP_CALL( SCIPvarChgUbGlobal(var, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, fixedval) );
3714 
3715  /* explicitly set variable's bounds, even if the fixed value is in epsilon range of the old bound */
3716  var->glbdom.lb = fixedval;
3717  var->glbdom.ub = fixedval;
3718  var->locdom.lb = fixedval;
3719  var->locdom.ub = fixedval;
3720 
3721  /* delete implications and variable bounds information */
3722  SCIP_CALL( SCIPvarRemoveCliquesImplicsVbs(var, blkmem, cliquetable, set, FALSE, FALSE, TRUE) );
3723  assert(var->vlbs == NULL);
3724  assert(var->vubs == NULL);
3725  assert(var->implics == NULL);
3726  assert(var->cliquelist == NULL);
3727 
3728  /* clear the history of the variable */
3729  SCIPhistoryReset(var->history);
3731 
3732  /* convert variable into fixed variable */
3733  var->varstatus = SCIP_VARSTATUS_FIXED; /*lint !e641*/
3734 
3735  /* inform problem about the variable's status change */
3736  if( var->probindex != -1 )
3737  {
3738  SCIP_CALL( SCIPprobVarChangedStatus(transprob, blkmem, set, branchcand, cliquetable, var) );
3739  }
3740 
3741  /* reset the objective value of the fixed variable, thus adjusting the problem's objective offset */
3742  SCIP_CALL( SCIPvarAddObj(var, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, eventqueue, obj) );
3743 
3744  /* issue VARFIXED event */
3745  SCIP_CALL( varEventVarFixed(var, blkmem, set, eventqueue, 0) );
3746 
3747  *fixed = TRUE;
3748  break;
3749 
3750  case SCIP_VARSTATUS_COLUMN:
3751  SCIPerrorMessage("cannot fix a column variable\n");
3752  return SCIP_INVALIDDATA;
3753 
3754  case SCIP_VARSTATUS_FIXED:
3755  SCIPerrorMessage("cannot fix a fixed variable again\n"); /*lint !e527*/
3756  SCIPABORT(); /* case is already handled in earlier if condition */
3757  return SCIP_INVALIDDATA; /*lint !e527*/
3758 
3760  /* fix aggregation variable y in x = a*y + c, instead of fixing x directly */
3761  assert(SCIPsetIsZero(set, var->obj));
3762  assert(!SCIPsetIsZero(set, var->data.aggregate.scalar));
3763  if( SCIPsetIsInfinity(set, fixedval) || SCIPsetIsInfinity(set, -fixedval) )
3764  childfixedval = (var->data.aggregate.scalar < 0.0 ? -fixedval : fixedval);
3765  else
3766  childfixedval = (fixedval - var->data.aggregate.constant)/var->data.aggregate.scalar;
3767  SCIP_CALL( SCIPvarFix(var->data.aggregate.var, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp,
3768  branchcand, eventqueue, cliquetable, childfixedval, infeasible, fixed) );
3769  break;
3770 
3772  SCIPerrorMessage("cannot fix a multiple aggregated variable\n");
3773  SCIPABORT();
3774  return SCIP_INVALIDDATA; /*lint !e527*/
3775 
3777  /* fix negation variable x in x' = offset - x, instead of fixing x' directly */
3778  assert(SCIPsetIsZero(set, var->obj));
3779  assert(var->negatedvar != NULL);
3781  assert(var->negatedvar->negatedvar == var);
3782  SCIP_CALL( SCIPvarFix(var->negatedvar, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp,
3783  branchcand, eventqueue, cliquetable, var->data.negate.constant - fixedval, infeasible, fixed) );
3784  break;
3785 
3786  default:
3787  SCIPerrorMessage("unknown variable status\n");
3788  return SCIP_INVALIDDATA;
3789  }
3790 
3791  return SCIP_OKAY;
3792 }
3793 
3794 /** transforms given variables, scalars and constant to the corresponding active variables, scalars and constant
3795  *
3796  * If the number of needed active variables is greater than the available slots in the variable array, nothing happens except
3797  * that the required size is stored in the corresponding variable; hence, if afterwards the required size is greater than the
3798  * available slots (varssize), nothing happens; otherwise, the active variable representation is stored in the arrays.
3799  *
3800  * The reason for this approach is that we cannot reallocate memory, since we do not know how the
3801  * memory has been allocated (e.g., by a C++ 'new' or SCIP functions).
3802  */
3804  SCIP_SET* set, /**< global SCIP settings */
3805  SCIP_VAR** vars, /**< variable array to get active variables */
3806  SCIP_Real* scalars, /**< scalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c */
3807  int* nvars, /**< pointer to number of variables and values in vars and scalars array */
3808  int varssize, /**< available slots in vars and scalars array */
3809  SCIP_Real* constant, /**< pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c */
3810  int* requiredsize, /**< pointer to store the required array size for the active variables */
3811  SCIP_Bool mergemultiples /**< should multiple occurrences of a var be replaced by a single coeff? */
3812  )
3813 {
3814  SCIP_VAR** activevars;
3815  SCIP_Real* activescalars;
3816  int nactivevars;
3817  SCIP_Real activeconstant;
3818  SCIP_Bool activeconstantinf;
3819  int activevarssize;
3820 
3821  SCIP_VAR* var;
3822  SCIP_Real scalar;
3823  int v;
3824  int k;
3825 
3826  SCIP_VAR** tmpvars;
3827  SCIP_VAR** multvars;
3828  SCIP_Real* tmpscalars;
3829  SCIP_Real* multscalars;
3830  int tmpvarssize;
3831  int ntmpvars;
3832  int nmultvars;
3833 
3834  SCIP_VAR* multvar;
3835  SCIP_Real multscalar;
3836  SCIP_Real multconstant;
3837  int pos;
3838 
3839  int noldtmpvars;
3840 
3841  SCIP_VAR** tmpvars2;
3842  SCIP_Real* tmpscalars2;
3843  int tmpvarssize2;
3844  int ntmpvars2;
3845 
3846  SCIP_Bool sortagain = FALSE;
3847 
3848  assert(set != NULL);
3849  assert(nvars != NULL);
3850  assert(scalars != NULL || *nvars == 0);
3851  assert(constant != NULL);
3852  assert(requiredsize != NULL);
3853  assert(*nvars <= varssize);
3854 
3855  *requiredsize = 0;
3856 
3857  if( *nvars == 0 )
3858  return SCIP_OKAY;
3859 
3860  assert(vars != NULL);
3861 
3862  /* handle the "easy" case of just one variable and avoid memory allocation if the variable is already active */
3863  if( *nvars == 1 && (vars[0]->varstatus == ((int) SCIP_VARSTATUS_COLUMN) || vars[0]->varstatus == ((int) SCIP_VARSTATUS_LOOSE)) )
3864  {
3865  *requiredsize = 1;
3866 
3867  return SCIP_OKAY;
3868  }
3869 
3870  nactivevars = 0;
3871  activeconstant = 0.0;
3872  activeconstantinf = FALSE;
3873  activevarssize = (*nvars) * 2;
3874  ntmpvars = *nvars;
3875  tmpvarssize = *nvars;
3876 
3877  tmpvarssize2 = 1;
3878 
3879  /* allocate temporary memory */
3880  SCIP_CALL( SCIPsetAllocBufferArray(set, &tmpvars2, tmpvarssize2) );
3881  SCIP_CALL( SCIPsetAllocBufferArray(set, &tmpscalars2, tmpvarssize2) );
3882  SCIP_CALL( SCIPsetAllocBufferArray(set, &activevars, activevarssize) );
3883  SCIP_CALL( SCIPsetAllocBufferArray(set, &activescalars, activevarssize) );
3884  SCIP_CALL( SCIPsetDuplicateBufferArray(set, &tmpvars, vars, ntmpvars) );
3885  SCIP_CALL( SCIPsetDuplicateBufferArray(set, &tmpscalars, scalars, ntmpvars) );
3886 
3887  /* to avoid unnecessary expanding of variable arrays while disaggregating several variables multiple times combine same variables
3888  * first, first get all corresponding variables with status loose, column, multaggr or fixed
3889  */
3890  for( v = ntmpvars - 1; v >= 0; --v )
3891  {
3892  var = tmpvars[v];
3893  scalar = tmpscalars[v];
3894 
3895  assert(var != NULL);
3896  /* transforms given variable, scalar and constant to the corresponding active, fixed, or
3897  * multi-aggregated variable, scalar and constant; if the variable resolves to a fixed
3898  * variable, "scalar" will be 0.0 and the value of the sum will be stored in "constant".
3899  */
3900  SCIP_CALL( SCIPvarGetProbvarSum(&var, set, &scalar, &activeconstant) );
3901  assert(var != NULL);
3902 
3903  assert(SCIPsetIsInfinity(set, activeconstant) == (activeconstant == SCIPsetInfinity(set))); /*lint !e777*/
3904  assert(SCIPsetIsInfinity(set, -activeconstant) == (activeconstant == -SCIPsetInfinity(set))); /*lint !e777*/
3905 
3906  activeconstantinf = SCIPsetIsInfinity(set, activeconstant) || SCIPsetIsInfinity(set, -activeconstant);
3907 
3908  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE
3909  || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN
3912 
3913  tmpvars[v] = var;
3914  tmpscalars[v] = scalar;
3915  }
3916  noldtmpvars = ntmpvars;
3917 
3918  /* sort all variables to combine equal variables easily */
3919  SCIPsortPtrReal((void**)tmpvars, tmpscalars, SCIPvarComp, noldtmpvars);
3920  ntmpvars = 0;
3921  for( v = 1; v < noldtmpvars; ++v )
3922  {
3923  /* combine same variables */
3924  if( SCIPvarCompare(tmpvars[v], tmpvars[ntmpvars]) == 0 )
3925  {
3926  tmpscalars[ntmpvars] += tmpscalars[v];
3927  }
3928  else
3929  {
3930  ++ntmpvars;
3931  if( v > ntmpvars )
3932  {
3933  tmpscalars[ntmpvars] = tmpscalars[v];
3934  tmpvars[ntmpvars] = tmpvars[v];
3935  }
3936  }
3937  }
3938  ++ntmpvars;
3939 
3940 #ifdef SCIP_MORE_DEBUG
3941  for( v = 1; v < ntmpvars; ++v )
3942  assert(SCIPvarCompare(tmpvars[v], tmpvars[v-1]) > 0);
3943 #endif
3944 
3945  /* collect for each variable the representation in active variables */
3946  while( ntmpvars >= 1 )
3947  {
3948  --ntmpvars;
3949  ntmpvars2 = 0;
3950  var = tmpvars[ntmpvars];
3951  scalar = tmpscalars[ntmpvars];
3952 
3953  assert(var != NULL);
3954 
3955  /* TODO: maybe we should test here on SCIPsetIsZero() instead of 0.0 */
3956  if( scalar == 0.0 )
3957  continue;
3958 
3959  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE
3960  || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN
3963 
3964  switch( SCIPvarGetStatus(var) )
3965  {
3966  case SCIP_VARSTATUS_LOOSE:
3967  case SCIP_VARSTATUS_COLUMN:
3968  /* x = a*y + c */
3969  if( nactivevars >= activevarssize )
3970  {
3971  activevarssize *= 2;
3972  SCIP_CALL( SCIPsetReallocBufferArray(set, &activevars, activevarssize) );
3973  SCIP_CALL( SCIPsetReallocBufferArray(set, &activescalars, activevarssize) );
3974  assert(nactivevars < activevarssize);
3975  }
3976  activevars[nactivevars] = var;
3977  activescalars[nactivevars] = scalar;
3978  nactivevars++;
3979  break;
3980 
3982  /* x = a_1*y_1 + ... + a_n*y_n + c */
3983  nmultvars = var->data.multaggr.nvars;
3984  multvars = var->data.multaggr.vars;
3985  multscalars = var->data.multaggr.scalars;
3986  sortagain = TRUE;
3987 
3988  if( nmultvars + ntmpvars > tmpvarssize )
3989  {
3990  while( nmultvars + ntmpvars > tmpvarssize )
3991  tmpvarssize *= 2;
3992  SCIP_CALL( SCIPsetReallocBufferArray(set, &tmpvars, tmpvarssize) );
3993  SCIP_CALL( SCIPsetReallocBufferArray(set, &tmpscalars, tmpvarssize) );
3994  assert(nmultvars + ntmpvars <= tmpvarssize);
3995  }
3996 
3997  if( nmultvars > tmpvarssize2 )
3998  {
3999  while( nmultvars > tmpvarssize2 )
4000  tmpvarssize2 *= 2;
4001  SCIP_CALL( SCIPsetReallocBufferArray(set, &tmpvars2, tmpvarssize2) );
4002  SCIP_CALL( SCIPsetReallocBufferArray(set, &tmpscalars2, tmpvarssize2) );
4003  assert(nmultvars <= tmpvarssize2);
4004  }
4005 
4006  --nmultvars;
4007 
4008  for( ; nmultvars >= 0; --nmultvars )
4009  {
4010  multvar = multvars[nmultvars];
4011  multscalar = multscalars[nmultvars];
4012  multconstant = 0;
4013 
4014  assert(multvar != NULL);
4015  SCIP_CALL( SCIPvarGetProbvarSum(&multvar, set, &multscalar, &multconstant) );
4016  assert(multvar != NULL);
4017 
4018  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE
4019  || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN
4022 
4023  if( !activeconstantinf )
4024  {
4025  assert(!SCIPsetIsInfinity(set, scalar) && !SCIPsetIsInfinity(set, -scalar));
4026 
4027  if( SCIPsetIsInfinity(set, multconstant) || SCIPsetIsInfinity(set, -multconstant) )
4028  {
4029  assert(scalar != 0.0);
4030  if( scalar * multconstant > 0.0 )
4031  {
4032  activeconstant = SCIPsetInfinity(set);
4033  activeconstantinf = TRUE;
4034  }
4035  else
4036  {
4037  activeconstant = -SCIPsetInfinity(set);
4038  activeconstantinf = TRUE;
4039  }
4040  }
4041  else
4042  activeconstant += scalar * multconstant;
4043  }
4044 #ifndef NDEBUG
4045  else
4046  {
4047  assert(!SCIPsetIsInfinity(set, activeconstant) || !(scalar * multconstant < 0.0 &&
4048  (SCIPsetIsInfinity(set, multconstant) || SCIPsetIsInfinity(set, -multconstant))));
4049  assert(!SCIPsetIsInfinity(set, -activeconstant) || !(scalar * multconstant > 0.0 &&
4050  (SCIPsetIsInfinity(set, multconstant) || SCIPsetIsInfinity(set, -multconstant))));
4051  }
4052 #endif
4053 
4054  if( SCIPsortedvecFindPtr((void**)tmpvars, SCIPvarComp, multvar, ntmpvars, &pos) )
4055  {
4056  assert(SCIPvarCompare(tmpvars[pos], multvar) == 0);
4057  tmpscalars[pos] += scalar * multscalar;
4058  }
4059  else
4060  {
4061  tmpvars2[ntmpvars2] = multvar;
4062  tmpscalars2[ntmpvars2] = scalar * multscalar;
4063  ++(ntmpvars2);
4064  assert(ntmpvars2 <= tmpvarssize2);
4065  }
4066  }
4067 
4068  if( ntmpvars2 > 0 )
4069  {
4070  /* sort all variables to combine equal variables easily */
4071  SCIPsortPtrReal((void**)tmpvars2, tmpscalars2, SCIPvarComp, ntmpvars2);
4072  pos = 0;
4073  for( v = 1; v < ntmpvars2; ++v )
4074  {
4075  /* combine same variables */
4076  if( SCIPvarCompare(tmpvars2[v], tmpvars2[pos]) == 0 )
4077  {
4078  tmpscalars2[pos] += tmpscalars2[v];
4079  }
4080  else
4081  {
4082  ++pos;
4083  if( v > pos )
4084  {
4085  tmpscalars2[pos] = tmpscalars2[v];
4086  tmpvars2[pos] = tmpvars2[v];
4087  }
4088  }
4089  }
4090  ntmpvars2 = pos + 1;
4091 #ifdef SCIP_MORE_DEBUG
4092  for( v = 1; v < ntmpvars2; ++v )
4093  {
4094  assert(SCIPvarCompare(tmpvars2[v], tmpvars2[v-1]) > 0);
4095  }
4096  for( v = 1; v < ntmpvars; ++v )
4097  {
4098  assert(SCIPvarCompare(tmpvars[v], tmpvars[v-1]) > 0);
4099  }
4100 #endif
4101  v = ntmpvars - 1;
4102  k = ntmpvars2 - 1;
4103  pos = ntmpvars + ntmpvars2 - 1;
4104  ntmpvars += ntmpvars2;
4105 
4106  while( v >= 0 && k >= 0 )
4107  {
4108  assert(pos >= 0);
4109  assert(SCIPvarCompare(tmpvars[v], tmpvars2[k]) != 0);
4110  if( SCIPvarCompare(tmpvars[v], tmpvars2[k]) >= 0 )
4111  {
4112  tmpvars[pos] = tmpvars[v];
4113  tmpscalars[pos] = tmpscalars[v];
4114  --v;
4115  }
4116  else
4117  {
4118  tmpvars[pos] = tmpvars2[k];
4119  tmpscalars[pos] = tmpscalars2[k];
4120  --k;
4121  }
4122  --pos;
4123  assert(pos >= 0);
4124  }
4125  while( v >= 0 )
4126  {
4127  assert(pos >= 0);
4128  tmpvars[pos] = tmpvars[v];
4129  tmpscalars[pos] = tmpscalars[v];
4130  --v;
4131  --pos;
4132  }
4133  while( k >= 0 )
4134  {
4135  assert(pos >= 0);
4136  tmpvars[pos] = tmpvars2[k];
4137  tmpscalars[pos] = tmpscalars2[k];
4138  --k;
4139  --pos;
4140  }
4141  }
4142 #ifdef SCIP_MORE_DEBUG
4143  for( v = 1; v < ntmpvars; ++v )
4144  {
4145  assert(SCIPvarCompare(tmpvars[v], tmpvars[v-1]) > 0);
4146  }
4147 #endif
4148 
4149  if( !activeconstantinf )
4150  {
4151  assert(!SCIPsetIsInfinity(set, scalar) && !SCIPsetIsInfinity(set, -scalar));
4152 
4153  multconstant = SCIPvarGetMultaggrConstant(var);
4154 
4155  if( SCIPsetIsInfinity(set, multconstant) || SCIPsetIsInfinity(set, -multconstant) )
4156  {
4157  assert(scalar != 0.0);
4158  if( scalar * multconstant > 0.0 )
4159  {
4160  activeconstant = SCIPsetInfinity(set);
4161  activeconstantinf = TRUE;
4162  }
4163  else
4164  {
4165  activeconstant = -SCIPsetInfinity(set);
4166  activeconstantinf = TRUE;
4167  }
4168  }
4169  else
4170  activeconstant += scalar * multconstant;
4171  }
4172 #ifndef NDEBUG
4173  else
4174  {
4175  multconstant = SCIPvarGetMultaggrConstant(var);
4176  assert(!SCIPsetIsInfinity(set, activeconstant) || !(scalar * multconstant < 0.0 &&
4177  (SCIPsetIsInfinity(set, multconstant) || SCIPsetIsInfinity(set, -multconstant))));
4178  assert(!SCIPsetIsInfinity(set, -activeconstant) || !(scalar * multconstant > 0.0 &&
4179  (SCIPsetIsInfinity(set, multconstant) || SCIPsetIsInfinity(set, -multconstant))));
4180  }
4181 #endif
4182  break;
4183 
4184  case SCIP_VARSTATUS_FIXED:
4188  default:
4189  /* case x = c, but actually we should not be here, since SCIPvarGetProbvarSum() returns a scalar of 0.0 for
4190  * fixed variables and is handled already
4191  */
4192  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED);
4193  assert(SCIPsetIsZero(set, var->glbdom.lb) && SCIPsetIsEQ(set, var->glbdom.lb, var->glbdom.ub));
4194  }
4195  }
4196 
4197  if( mergemultiples )
4198  {
4199  if( sortagain )
4200  {
4201  /* sort variable and scalar array by variable index */
4202  SCIPsortPtrReal((void**)activevars, activescalars, SCIPvarComp, nactivevars);
4203 
4204  /* eliminate duplicates and count required size */
4205  v = nactivevars - 1;
4206  while( v > 0 )
4207  {
4208  /* combine both variable since they are the same */
4209  if( SCIPvarCompare(activevars[v - 1], activevars[v]) == 0 )
4210  {
4211  if( activescalars[v - 1] + activescalars[v] != 0.0 )
4212  {
4213  activescalars[v - 1] += activescalars[v];
4214  --nactivevars;
4215  activevars[v] = activevars[nactivevars];
4216  activescalars[v] = activescalars[nactivevars];
4217  }
4218  else
4219  {
4220  --nactivevars;
4221  activevars[v] = activevars[nactivevars];
4222  activescalars[v] = activescalars[nactivevars];
4223  --nactivevars;
4224  --v;
4225  activevars[v] = activevars[nactivevars];
4226  activescalars[v] = activescalars[nactivevars];
4227  }
4228  }
4229  --v;
4230  }
4231  }
4232  /* the variables were added in reverse order, we revert the order now;
4233  * this should not be necessary, but not doing this changes the behavior sometimes
4234  */
4235  else
4236  {
4237  SCIP_VAR* tmpvar;
4238  SCIP_Real tmpscalar;
4239 
4240  for( v = 0; v < nactivevars / 2; ++v )
4241  {
4242  tmpvar = activevars[v];
4243  tmpscalar = activescalars[v];
4244  activevars[v] = activevars[nactivevars - 1 - v];
4245  activescalars[v] = activescalars[nactivevars - 1 - v];
4246  activevars[nactivevars - 1 - v] = tmpvar;
4247  activescalars[nactivevars - 1 - v] = tmpscalar;
4248  }
4249  }
4250  }
4251  *requiredsize = nactivevars;
4252 
4253  if( varssize >= *requiredsize )
4254  {
4255  assert(vars != NULL);
4256 
4257  *nvars = *requiredsize;
4258 
4259  if( !SCIPsetIsInfinity(set, *constant) && !SCIPsetIsInfinity(set, -(*constant)) )
4260  {
4261  /* if the activeconstant is infinite, the constant pointer gets the same value, otherwise add the value */
4262  if( activeconstantinf )
4263  (*constant) = activeconstant;
4264  else
4265  (*constant) += activeconstant;
4266  }
4267 #ifndef NDEBUG
4268  else
4269  {
4270  assert(!SCIPsetIsInfinity(set, (*constant)) || !SCIPsetIsInfinity(set, -activeconstant));
4271  assert(!SCIPsetIsInfinity(set, -(*constant)) || !SCIPsetIsInfinity(set, activeconstant));
4272  }
4273 #endif
4274 
4275  /* copy active variable and scalar array to the given arrays */
4276  for( v = 0; v < *nvars; ++v )
4277  {
4278  vars[v] = activevars[v];
4279  scalars[v] = activescalars[v]; /*lint !e613*/
4280  }
4281  }
4282 
4283  assert(SCIPsetIsInfinity(set, *constant) == ((*constant) == SCIPsetInfinity(set))); /*lint !e777*/
4284  assert(SCIPsetIsInfinity(set, -(*constant)) == ((*constant) == -SCIPsetInfinity(set))); /*lint !e777*/
4285 
4286  SCIPsetFreeBufferArray(set, &tmpscalars);
4287  SCIPsetFreeBufferArray(set, &tmpvars);
4288  SCIPsetFreeBufferArray(set, &activescalars);
4289  SCIPsetFreeBufferArray(set, &activevars);
4290  SCIPsetFreeBufferArray(set, &tmpscalars2);
4291  SCIPsetFreeBufferArray(set, &tmpvars2);
4292 
4293  return SCIP_OKAY;
4294 }
4295 
4296 
4297 /** flattens aggregation graph of multi-aggregated variable in order to avoid exponential recursion later on */
4299  SCIP_VAR* var, /**< problem variable */
4300  BMS_BLKMEM* blkmem, /**< block memory */
4301  SCIP_SET* set /**< global SCIP settings */
4302  )
4303 {
4304  SCIP_Real multconstant;
4305  int multvarssize;
4306  int nmultvars;
4307  int multrequiredsize;
4308 
4309  assert( var != NULL );
4310  assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR );
4311  assert(var->scip == set->scip);
4312 
4313  multconstant = var->data.multaggr.constant;
4314  nmultvars = var->data.multaggr.nvars;
4315  multvarssize = var->data.multaggr.varssize;
4316 
4317  SCIP_CALL( SCIPvarGetActiveRepresentatives(set, var->data.multaggr.vars, var->data.multaggr.scalars, &nmultvars, multvarssize, &multconstant, &multrequiredsize, TRUE) );
4318 
4319  if( multrequiredsize > multvarssize )
4320  {
4321  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(var->data.multaggr.vars), multvarssize, multrequiredsize) );
4322  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(var->data.multaggr.scalars), multvarssize, multrequiredsize) );
4323  multvarssize = multrequiredsize;
4324  SCIP_CALL( SCIPvarGetActiveRepresentatives(set, var->data.multaggr.vars, var->data.multaggr.scalars, &nmultvars, multvarssize, &multconstant, &multrequiredsize, TRUE) );
4325  assert( multrequiredsize <= multvarssize );
4326  }
4327  /**@note After the flattening the multi aggregation might resolve to be in fact an aggregation (or even a fixing?).
4328  * This issue is not resolved right now, since var->data.multaggr.nvars < 2 should not cause troubles. However, one
4329  * may loose performance hereby, since aggregated variables are easier to handle.
4330  *
4331  * Note, that there are two cases where SCIPvarFlattenAggregationGraph() is called: The easier one is that it is
4332  * called while installing the multi-aggregation. in principle, the described issue could be handled straightforward
4333  * in this case by aggregating or fixing the variable instead. The more complicated case is the one, when the
4334  * multi-aggregation is used, e.g., in linear presolving (and the variable is already declared to be multi-aggregated).
4335  *
4336  * By now, it is not allowed to fix or aggregate multi-aggregated variables which would be necessary in this case.
4337  *
4338  * The same issue appears in the SCIPvarGetProbvar...() methods.
4339  */
4340 
4341  var->data.multaggr.constant = multconstant;
4342  var->data.multaggr.nvars = nmultvars;
4343  var->data.multaggr.varssize = multvarssize;
4344 
4345  return SCIP_OKAY;
4346 }
4347 
4348 /** merge two variable histories together; a typical use case is that \p othervar is an image of the target variable
4349  * in a SCIP copy. Method should be applied with care, especially because no internal checks are performed whether
4350  * the history merge is reasonable
4351  *
4352  * @note Do not use this method if the two variables originate from two SCIP's with different objective functions, since
4353  * this corrupts the variable pseudo costs
4354  * @note Apply with care; no internal checks are performed if the two variables should be merged
4355  */
4357  SCIP_VAR* targetvar, /**< the variable that should contain both histories afterwards */
4358  SCIP_VAR* othervar, /**< the variable whose history is to be merged with that of the target variable */
4359  SCIP_STAT* stat /**< problem statistics */
4360  )
4361 {
4362  /* merge only the history of the current run into the target history */
4363  SCIPhistoryUnite(targetvar->history, othervar->historycrun, FALSE);
4364 
4365  /* apply the changes also to the global history */
4366  SCIPhistoryUnite(stat->glbhistory, othervar->historycrun, FALSE);
4367 }
4368 
4369 /** sets the history of a variable; this method is typically used within reoptimization to keep and update the variable
4370  * history over several iterations
4371  */
4372 void SCIPvarSetHistory(
4373  SCIP_VAR* var, /**< variable */
4374  SCIP_HISTORY* history, /**< the history which is to set */
4375  SCIP_STAT* stat /**< problem statistics */
4376  )
4377 {
4378  /* merge only the history of the current run into the target history */
4379  SCIPhistoryUnite(var->history, history, FALSE);
4380 
4381  /* apply the changes also to the global history */
4382  SCIPhistoryUnite(stat->glbhistory, history, FALSE);
4383 }
4384 
4385 /** tightens the bounds of both variables in aggregation x = a*y + c */
4386 static
4388  SCIP_VAR* var, /**< problem variable */
4389  BMS_BLKMEM* blkmem, /**< block memory */
4390  SCIP_SET* set, /**< global SCIP settings */
4391  SCIP_STAT* stat, /**< problem statistics */
4392  SCIP_PROB* transprob, /**< tranformed problem data */
4393  SCIP_PROB* origprob, /**< original problem data */
4394  SCIP_PRIMAL* primal, /**< primal data */
4395  SCIP_TREE* tree, /**< branch and bound tree */
4396  SCIP_REOPT* reopt, /**< reoptimization data structure */
4397  SCIP_LP* lp, /**< current LP data */
4398  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4399  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4400  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
4401  SCIP_VAR* aggvar, /**< variable y in aggregation x = a*y + c */
4402  SCIP_Real scalar, /**< multiplier a in aggregation x = a*y + c */
4403  SCIP_Real constant, /**< constant shift c in aggregation x = a*y + c */
4404  SCIP_Bool* infeasible, /**< pointer to store whether the aggregation is infeasible */
4405  SCIP_Bool* fixed /**< pointer to store whether the variables were fixed */
4406  )
4407 {
4408  SCIP_Real varlb;
4409  SCIP_Real varub;
4410  SCIP_Real aggvarlb;
4411  SCIP_Real aggvarub;
4412  SCIP_Bool aggvarbdschanged;
4413 
4414  assert(var != NULL);
4415  assert(var->scip == set->scip);
4416  assert(aggvar != NULL);
4417  assert(!SCIPsetIsZero(set, scalar));
4418  assert(infeasible != NULL);
4419  assert(fixed != NULL);
4420 
4421  *infeasible = FALSE;
4422  *fixed = FALSE;
4423 
4424  SCIPsetDebugMsg(set, "updating bounds of variables in aggregation <%s> == %g*<%s> %+g\n", var->name, scalar, aggvar->name, constant);
4425  SCIPsetDebugMsg(set, " old bounds: <%s> [%g,%g] <%s> [%g,%g]\n",
4426  var->name, var->glbdom.lb, var->glbdom.ub, aggvar->name, aggvar->glbdom.lb, aggvar->glbdom.ub);
4427 
4428  /* loop as long additional changes may be found */
4429  do
4430  {
4431  aggvarbdschanged = FALSE;
4432 
4433  /* update the bounds of the aggregated variable x in x = a*y + c */
4434  if( scalar > 0.0 )
4435  {
4436  if( SCIPsetIsInfinity(set, -aggvar->glbdom.lb) )
4437  varlb = -SCIPsetInfinity(set);
4438  else
4439  varlb = aggvar->glbdom.lb * scalar + constant;
4440  if( SCIPsetIsInfinity(set, aggvar->glbdom.ub) )
4441  varub = SCIPsetInfinity(set);
4442  else
4443  varub = aggvar->glbdom.ub * scalar + constant;
4444  }
4445  else
4446  {
4447  if( SCIPsetIsInfinity(set, -aggvar->glbdom.lb) )
4448  varub = SCIPsetInfinity(set);
4449  else
4450  varub = aggvar->glbdom.lb * scalar + constant;
4451  if( SCIPsetIsInfinity(set, aggvar->glbdom.ub) )
4452  varlb = -SCIPsetInfinity(set);
4453  else
4454  varlb = aggvar->glbdom.ub * scalar + constant;
4455  }
4456  varlb = MAX(varlb, var->glbdom.lb);
4457  varub = MIN(varub, var->glbdom.ub);
4458  SCIPvarAdjustLb(var, set, &varlb);
4459  SCIPvarAdjustUb(var, set, &varub);
4460 
4461  /* check the new bounds */
4462  if( SCIPsetIsGT(set, varlb, varub) )
4463  {
4464  /* the aggregation is infeasible */
4465  *infeasible = TRUE;
4466  return SCIP_OKAY;
4467  }
4468  else if( SCIPsetIsEQ(set, varlb, varub) )
4469  {
4470  /* the aggregated variable is fixed -> fix both variables */
4471  SCIP_CALL( SCIPvarFix(var, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
4472  eventqueue, cliquetable, varlb, infeasible, fixed) );
4473  if( !(*infeasible) )
4474  {
4475  SCIP_Bool aggfixed;
4476 
4477  SCIP_CALL( SCIPvarFix(aggvar, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
4478  eventqueue, cliquetable, (varlb-constant)/scalar, infeasible, &aggfixed) );
4479  assert(*fixed == aggfixed);
4480  }
4481  return SCIP_OKAY;
4482  }
4483  else
4484  {
4485  if( SCIPsetIsGT(set, varlb, var->glbdom.lb) )
4486  {
4487  SCIP_CALL( SCIPvarChgLbGlobal(var, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, varlb) );
4488  }
4489  if( SCIPsetIsLT(set, varub, var->glbdom.ub) )
4490  {
4491  SCIP_CALL( SCIPvarChgUbGlobal(var, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, varub) );
4492  }
4493 
4494  /* update the hole list of the aggregation variable */
4495  /**@todo update hole list of aggregation variable */
4496  }
4497 
4498  /* update the bounds of the aggregation variable y in x = a*y + c -> y = (x-c)/a */
4499  if( scalar > 0.0 )
4500  {
4501  if( SCIPsetIsInfinity(set, -var->glbdom.lb) )
4502  aggvarlb = -SCIPsetInfinity(set);
4503  else
4504  aggvarlb = (var->glbdom.lb - constant) / scalar;
4505  if( SCIPsetIsInfinity(set, var->glbdom.ub) )
4506  aggvarub = SCIPsetInfinity(set);
4507  else
4508  aggvarub = (var->glbdom.ub - constant) / scalar;
4509  }
4510  else
4511  {
4512  if( SCIPsetIsInfinity(set, -var->glbdom.lb) )
4513  aggvarub = SCIPsetInfinity(set);
4514  else
4515  aggvarub = (var->glbdom.lb - constant) / scalar;
4516  if( SCIPsetIsInfinity(set, var->glbdom.ub) )
4517  aggvarlb = -SCIPsetInfinity(set);
4518  else
4519  aggvarlb = (var->glbdom.ub - constant) / scalar;
4520  }
4521  aggvarlb = MAX(aggvarlb, aggvar->glbdom.lb);
4522  aggvarub = MIN(aggvarub, aggvar->glbdom.ub);
4523  SCIPvarAdjustLb(aggvar, set, &aggvarlb);
4524  SCIPvarAdjustUb(aggvar, set, &aggvarub);
4525 
4526  /* check the new bounds */
4527  if( SCIPsetIsGT(set, aggvarlb, aggvarub) )
4528  {
4529  /* the aggregation is infeasible */
4530  *infeasible = TRUE;
4531  return SCIP_OKAY;
4532  }
4533  else if( SCIPsetIsEQ(set, aggvarlb, aggvarub) )
4534  {
4535  /* the aggregation variable is fixed -> fix both variables */
4536  SCIP_CALL( SCIPvarFix(aggvar, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
4537  eventqueue, cliquetable, aggvarlb, infeasible, fixed) );
4538  if( !(*infeasible) )
4539  {
4540  SCIP_Bool varfixed;
4541 
4542  SCIP_CALL( SCIPvarFix(var, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
4543  eventqueue, cliquetable, aggvarlb * scalar + constant, infeasible, &varfixed) );
4544  assert(*fixed == varfixed);
4545  }
4546  return SCIP_OKAY;
4547  }
4548  else
4549  {
4550  SCIP_Real oldbd;
4551  if( SCIPsetIsGT(set, aggvarlb, aggvar->glbdom.lb) )
4552  {
4553  oldbd = aggvar->glbdom.lb;
4554  SCIP_CALL( SCIPvarChgLbGlobal(aggvar, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, aggvarlb) );
4555  aggvarbdschanged = !SCIPsetIsEQ(set, oldbd, aggvar->glbdom.lb);
4556  }
4557  if( SCIPsetIsLT(set, aggvarub, aggvar->glbdom.ub) )
4558  {
4559  oldbd = aggvar->glbdom.ub;
4560  SCIP_CALL( SCIPvarChgUbGlobal(aggvar, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, aggvarub) );
4561  aggvarbdschanged = aggvarbdschanged || !SCIPsetIsEQ(set, oldbd, aggvar->glbdom.ub);
4562  }
4563 
4564  /* update the hole list of the aggregation variable */
4565  /**@todo update hole list of aggregation variable */
4566  }
4567  }
4568  while( aggvarbdschanged );
4569 
4570  SCIPsetDebugMsg(set, " new bounds: <%s> [%g,%g] <%s> [%g,%g]\n",
4571  var->name, var->glbdom.lb, var->glbdom.ub, aggvar->name, aggvar->glbdom.lb, aggvar->glbdom.ub);
4572 
4573  return SCIP_OKAY;
4574 }
4575 
4576 /** converts loose variable into aggregated variable */
4578  SCIP_VAR* var, /**< loose problem variable */
4579  BMS_BLKMEM* blkmem, /**< block memory */
4580  SCIP_SET* set, /**< global SCIP settings */
4581  SCIP_STAT* stat, /**< problem statistics */
4582  SCIP_PROB* transprob, /**< tranformed problem data */
4583  SCIP_PROB* origprob, /**< original problem data */
4584  SCIP_PRIMAL* primal, /**< primal data */
4585  SCIP_TREE* tree, /**< branch and bound tree */
4586  SCIP_REOPT* reopt, /**< reoptimization data structure */
4587  SCIP_LP* lp, /**< current LP data */
4588  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
4589  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4590  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4591  SCIP_VAR* aggvar, /**< loose variable y in aggregation x = a*y + c */
4592  SCIP_Real scalar, /**< multiplier a in aggregation x = a*y + c */
4593  SCIP_Real constant, /**< constant shift c in aggregation x = a*y + c */
4594  SCIP_Bool* infeasible, /**< pointer to store whether the aggregation is infeasible */
4595  SCIP_Bool* aggregated /**< pointer to store whether the aggregation was successful */
4596  )
4597 {
4598  SCIP_VAR** vars;
4599  SCIP_Real* coefs;
4600  SCIP_Real* constants;
4601  SCIP_Real obj;
4602  SCIP_Real branchfactor;
4603  SCIP_Bool fixed;
4604  int branchpriority;
4605  int nlocksdown[NLOCKTYPES];
4606  int nlocksup[NLOCKTYPES];
4607  int nvbds;
4608  int i;
4609  int j;
4610 
4611  assert(var != NULL);
4612  assert(aggvar != NULL);
4613  assert(var->scip == set->scip);
4614  assert(var->glbdom.lb == var->locdom.lb); /*lint !e777*/
4615  assert(var->glbdom.ub == var->locdom.ub); /*lint !e777*/
4616  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
4617  assert(!SCIPeventqueueIsDelayed(eventqueue)); /* otherwise, the pseudo objective value update gets confused */
4618  assert(infeasible != NULL);
4619  assert(aggregated != NULL);
4620 
4621  /* check aggregation on debugging solution */
4622  SCIP_CALL( SCIPdebugCheckAggregation(set, var, &aggvar, &scalar, constant, 1) ); /*lint !e506 !e774*/
4623 
4624  *infeasible = FALSE;
4625  *aggregated = FALSE;
4626 
4627  /* get active problem variable of aggregation variable */
4628  SCIP_CALL( SCIPvarGetProbvarSum(&aggvar, set, &scalar, &constant) );
4629 
4630  /* aggregation is a fixing, if the scalar is zero */
4631  if( SCIPsetIsZero(set, scalar) )
4632  {
4633  SCIP_CALL( SCIPvarFix(var, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue,
4634  cliquetable, constant, infeasible, aggregated) );
4635  return SCIP_OKAY;
4636  }
4637 
4638  /* don't perform the aggregation if the aggregation variable is multi-aggregated itself */
4639  if( SCIPvarGetStatus(aggvar) == SCIP_VARSTATUS_MULTAGGR )
4640  return SCIP_OKAY;
4641 
4642  /**@todo currently we don't perform the aggregation if the aggregation variable has a non-empty hole list; this
4643  * should be changed in the future
4644  */
4645  if( SCIPvarGetHolelistGlobal(var) != NULL )
4646  return SCIP_OKAY;
4647 
4648  assert(aggvar->glbdom.lb == aggvar->locdom.lb); /*lint !e777*/
4649  assert(aggvar->glbdom.ub == aggvar->locdom.ub); /*lint !e777*/
4650  assert(SCIPvarGetStatus(aggvar) == SCIP_VARSTATUS_LOOSE);
4651 
4652  SCIPsetDebugMsg(set, "aggregate variable <%s>[%g,%g] == %g*<%s>[%g,%g] %+g\n", var->name, var->glbdom.lb, var->glbdom.ub,
4653  scalar, aggvar->name, aggvar->glbdom.lb, aggvar->glbdom.ub, constant);
4654 
4655  /* if variable and aggregation variable are equal, the variable can be fixed: x == a*x + c => x == c/(1-a) */
4656  if( var == aggvar )
4657  {
4658  if( SCIPsetIsEQ(set, scalar, 1.0) )
4659  *infeasible = !SCIPsetIsZero(set, constant);
4660  else
4661  {
4662  SCIP_CALL( SCIPvarFix(var, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
4663  eventqueue, cliquetable, constant/(1.0-scalar), infeasible, aggregated) );
4664  }
4665  return SCIP_OKAY;
4666  }
4667 
4668  /* tighten the bounds of aggregated and aggregation variable */
4669  SCIP_CALL( varUpdateAggregationBounds(var, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp,
4670  branchcand, eventqueue, cliquetable, aggvar, scalar, constant, infeasible, &fixed) );
4671  if( *infeasible || fixed )
4672  {
4673  *aggregated = fixed;
4674  return SCIP_OKAY;
4675  }
4676 
4677  /* delete implications and variable bounds of the aggregated variable from other variables, but keep them in the
4678  * aggregated variable
4679  */
4680  SCIP_CALL( SCIPvarRemoveCliquesImplicsVbs(var, blkmem, cliquetable, set, FALSE, FALSE, FALSE) );
4681  assert(var->cliquelist == NULL);
4682 
4683  /* set the aggregated variable's objective value to 0.0 */
4684  obj = var->obj;
4685  SCIP_CALL( SCIPvarChgObj(var, blkmem, set, transprob, primal, lp, eventqueue, 0.0) );
4686 
4687  /* unlock all locks */
4688  for( i = 0; i < NLOCKTYPES; i++ )
4689  {
4690  nlocksdown[i] = var->nlocksdown[i];
4691  nlocksup[i] = var->nlocksup[i];
4692 
4693  var->nlocksdown[i] = 0;
4694  var->nlocksup[i] = 0;
4695  }
4696 
4697  /* check, if variable should be used as NEGATED variable of the aggregation variable */
4698  if( SCIPvarIsBinary(var) && SCIPvarIsBinary(aggvar)
4699  && var->negatedvar == NULL && aggvar->negatedvar == NULL
4700  && SCIPsetIsEQ(set, scalar, -1.0) && SCIPsetIsEQ(set, constant, 1.0) )
4701  {
4702  /* link both variables as negation pair */
4703  var->varstatus = SCIP_VARSTATUS_NEGATED; /*lint !e641*/
4704  var->data.negate.constant = 1.0;
4705  var->negatedvar = aggvar;
4706  aggvar->negatedvar = var;
4707 
4708  /* copy doNotMultiaggr status */
4709  aggvar->donotmultaggr |= var->donotmultaggr;
4710 
4711  /* mark both variables to be non-deletable */
4713  SCIPvarMarkNotDeletable(aggvar);
4714  }
4715  else
4716  {
4717  /* convert variable into aggregated variable */
4718  var->varstatus = SCIP_VARSTATUS_AGGREGATED; /*lint !e641*/
4719  var->data.aggregate.var = aggvar;
4720  var->data.aggregate.scalar = scalar;
4721  var->data.aggregate.constant = constant;
4722 
4723  /* copy doNotMultiaggr status */
4724  aggvar->donotmultaggr |= var->donotmultaggr;
4725 
4726  /* mark both variables to be non-deletable */
4728  SCIPvarMarkNotDeletable(aggvar);
4729  }
4730 
4731  /* make aggregated variable a parent of the aggregation variable */
4732  SCIP_CALL( varAddParent(aggvar, blkmem, set, var) );
4733 
4734  /* relock the variable, thus increasing the locks of the aggregation variable */
4735  for( i = 0; i < NLOCKTYPES; i++ )
4736  {
4737  SCIP_CALL( SCIPvarAddLocks(var, blkmem, set, eventqueue, (SCIP_LOCKTYPE) i, nlocksdown[i], nlocksup[i]) );
4738  }
4739 
4740  /* move the variable bounds to the aggregation variable:
4741  * - add all variable bounds again to the variable, thus adding it to the aggregation variable
4742  * - free the variable bounds data structures
4743  */
4744  if( var->vlbs != NULL )
4745  {
4746  nvbds = SCIPvboundsGetNVbds(var->vlbs);
4747  vars = SCIPvboundsGetVars(var->vlbs);
4748  coefs = SCIPvboundsGetCoefs(var->vlbs);
4749  constants = SCIPvboundsGetConstants(var->vlbs);
4750  for( i = 0; i < nvbds && !(*infeasible); ++i )
4751  {
4752  SCIP_CALL( SCIPvarAddVlb(var, blkmem, set, stat, transprob, origprob, tree, reopt, lp, cliquetable, branchcand,
4753  eventqueue, vars[i], coefs[i], constants[i], FALSE, infeasible, NULL) );
4754  }
4755  }
4756  if( var->vubs != NULL )
4757  {
4758  nvbds = SCIPvboundsGetNVbds(var->vubs);
4759  vars = SCIPvboundsGetVars(var->vubs);
4760  coefs = SCIPvboundsGetCoefs(var->vubs);
4761  constants = SCIPvboundsGetConstants(var->vubs);
4762  for( i = 0; i < nvbds && !(*infeasible); ++i )
4763  {
4764  SCIP_CALL( SCIPvarAddVub(var, blkmem, set, stat, transprob, origprob, tree, reopt, lp, cliquetable, branchcand,
4765  eventqueue, vars[i], coefs[i], constants[i], FALSE, infeasible, NULL) );
4766  }
4767  }
4768  SCIPvboundsFree(&var->vlbs, blkmem);
4769  SCIPvboundsFree(&var->vubs, blkmem);
4770 
4771  /* move the implications to the aggregation variable:
4772  * - add all implications again to the variable, thus adding it to the aggregation variable
4773  * - free the implications data structures
4774  */
4775  if( var->implics != NULL && SCIPvarGetType(aggvar) == SCIP_VARTYPE_BINARY )
4776  {
4777  assert(SCIPvarIsBinary(var));
4778  for( i = 0; i < 2; ++i )
4779  {
4780  SCIP_VAR** implvars;
4781  SCIP_BOUNDTYPE* impltypes;
4782  SCIP_Real* implbounds;
4783  int nimpls;
4784 
4785  nimpls = SCIPimplicsGetNImpls(var->implics, (SCIP_Bool)i);
4786  implvars = SCIPimplicsGetVars(var->implics, (SCIP_Bool)i);
4787  impltypes = SCIPimplicsGetTypes(var->implics, (SCIP_Bool)i);
4788  implbounds = SCIPimplicsGetBounds(var->implics, (SCIP_Bool)i);
4789 
4790  for( j = 0; j < nimpls && !(*infeasible); ++j )
4791  {
4792  /* @todo can't we omit transitive closure, because it should already have been done when adding the
4793  * implication to the aggregated variable?
4794  */
4795  SCIP_CALL( SCIPvarAddImplic(var, blkmem, set, stat, transprob, origprob, tree, reopt, lp, cliquetable,
4796  branchcand, eventqueue, (SCIP_Bool)i, implvars[j], impltypes[j], implbounds[j], FALSE, infeasible,
4797  NULL) );
4798  assert(nimpls == SCIPimplicsGetNImpls(var->implics, (SCIP_Bool)i));
4799  }
4800  }
4801  }
4802  SCIPimplicsFree(&var->implics, blkmem);
4803 
4804  /* add the history entries to the aggregation variable and clear the history of the aggregated variable */
4805  SCIPhistoryUnite(aggvar->history, var->history, scalar < 0.0);
4806  SCIPhistoryUnite(aggvar->historycrun, var->historycrun, scalar < 0.0);
4807  SCIPhistoryReset(var->history);
4809 
4810  /* update flags of aggregation variable */
4811  aggvar->removable &= var->removable;
4812 
4813  /* update branching factors and priorities of both variables to be the maximum of both variables */
4814  branchfactor = MAX(aggvar->branchfactor, var->branchfactor);
4815  branchpriority = MAX(aggvar->branchpriority, var->branchpriority);
4816  SCIP_CALL( SCIPvarChgBranchFactor(aggvar, set, branchfactor) );
4817  SCIP_CALL( SCIPvarChgBranchPriority(aggvar, branchpriority) );
4818  SCIP_CALL( SCIPvarChgBranchFactor(var, set, branchfactor) );
4819  SCIP_CALL( SCIPvarChgBranchPriority(var, branchpriority) );
4820 
4821  /* update branching direction of both variables to agree to a single direction */
4822  if( scalar >= 0.0 )
4823  {
4825  {
4827  }
4828  else if( (SCIP_BRANCHDIR)aggvar->branchdirection == SCIP_BRANCHDIR_AUTO )
4829  {
4831  }
4832  else if( var->branchdirection != aggvar->branchdirection )
4833  {
4835  }
4836  }
4837  else
4838  {
4840  {
4842  }
4843  else if( (SCIP_BRANCHDIR)aggvar->branchdirection == SCIP_BRANCHDIR_AUTO )
4844  {
4846  }
4847  else if( var->branchdirection != aggvar->branchdirection )
4848  {
4850  }
4851  }
4852 
4853  if( var->probindex != -1 )
4854  {
4855  /* inform problem about the variable's status change */
4856  SCIP_CALL( SCIPprobVarChangedStatus(transprob, blkmem, set, branchcand, cliquetable, var) );
4857  }
4858 
4859  /* reset the objective value of the aggregated variable, thus adjusting the objective value of the aggregation
4860  * variable and the problem's objective offset
4861  */
4862  SCIP_CALL( SCIPvarAddObj(var, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, eventqueue, obj) );
4863 
4864  /* issue VARFIXED event */
4865  SCIP_CALL( varEventVarFixed(var, blkmem, set, eventqueue, 1) );
4866 
4867  *aggregated = TRUE;
4868 
4869  return SCIP_OKAY;
4870 }
4871 
4872 /** Tries to aggregate an equality a*x + b*y == c consisting of two (implicit) integral active problem variables x and
4873  * y. An integer aggregation (i.e. integral coefficients a' and b', such that a'*x + b'*y == c') is searched.
4874  *
4875  * This can lead to the detection of infeasibility (e.g. if c' is fractional), or to a rejection of the aggregation
4876  * (denoted by aggregated == FALSE), if the resulting integer coefficients are too large and thus numerically instable.
4877  */
4878 static
4880  SCIP_SET* set, /**< global SCIP settings */
4881  BMS_BLKMEM* blkmem, /**< block memory */
4882  SCIP_STAT* stat, /**< problem statistics */
4883  SCIP_PROB* transprob, /**< tranformed problem data */
4884  SCIP_PROB* origprob, /**< original problem data */
4885  SCIP_PRIMAL* primal, /**< primal data */
4886  SCIP_TREE* tree, /**< branch and bound tree */
4887  SCIP_REOPT* reopt, /**< reoptimization data structure */
4888  SCIP_LP* lp, /**< current LP data */
4889  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
4890  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4891  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4892  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4893  SCIP_VAR* varx, /**< integral variable x in equality a*x + b*y == c */
4894  SCIP_VAR* vary, /**< integral variable y in equality a*x + b*y == c */
4895  SCIP_Real scalarx, /**< multiplier a in equality a*x + b*y == c */
4896  SCIP_Real scalary, /**< multiplier b in equality a*x + b*y == c */
4897  SCIP_Real rhs, /**< right hand side c in equality a*x + b*y == c */
4898  SCIP_Bool* infeasible, /**< pointer to store whether the aggregation is infeasible */
4899  SCIP_Bool* aggregated /**< pointer to store whether the aggregation was successful */
4900  )
4901 {
4902  SCIP_VAR* aggvar;
4903  char aggvarname[SCIP_MAXSTRLEN];
4904  SCIP_Longint scalarxn = 0;
4905  SCIP_Longint scalarxd = 0;
4906  SCIP_Longint scalaryn = 0;
4907  SCIP_Longint scalaryd = 0;
4908  SCIP_Longint a;
4909  SCIP_Longint b;
4910  SCIP_Longint c;
4911  SCIP_Longint scm;
4912  SCIP_Longint gcd;
4913  SCIP_Longint currentclass;
4914  SCIP_Longint classstep;
4915  SCIP_Longint xsol;
4916  SCIP_Longint ysol;
4917  SCIP_Bool success;
4918  SCIP_VARTYPE vartype;
4919 
4920 #define MAXDNOM 1000000LL
4921 
4922  assert(set != NULL);
4923  assert(blkmem != NULL);
4924  assert(stat != NULL);
4925  assert(transprob != NULL);
4926  assert(origprob != NULL);
4927  assert(tree != NULL);
4928  assert(lp != NULL);
4929  assert(cliquetable != NULL);
4930  assert(branchcand != NULL);
4931  assert(eventqueue != NULL);
4932  assert(varx != NULL);
4933  assert(vary != NULL);
4934  assert(varx != vary);
4935  assert(infeasible != NULL);
4936  assert(aggregated != NULL);
4937  assert(SCIPsetGetStage(set) == SCIP_STAGE_PRESOLVING);
4938  assert(SCIPvarGetStatus(varx) == SCIP_VARSTATUS_LOOSE);
4940  assert(SCIPvarGetStatus(vary) == SCIP_VARSTATUS_LOOSE);
4942  assert(!SCIPsetIsZero(set, scalarx));
4943  assert(!SCIPsetIsZero(set, scalary));
4944 
4945  *infeasible = FALSE;
4946  *aggregated = FALSE;
4947 
4948  /* get rational representation of coefficients */
4949  success = SCIPrealToRational(scalarx, -SCIPsetEpsilon(set), SCIPsetEpsilon(set), MAXDNOM, &scalarxn, &scalarxd);
4950  if( success )
4951  success = SCIPrealToRational(scalary, -SCIPsetEpsilon(set), SCIPsetEpsilon(set), MAXDNOM, &scalaryn, &scalaryd);
4952  if( !success )
4953  return SCIP_OKAY;
4954  assert(scalarxd >= 1);
4955  assert(scalaryd >= 1);
4956 
4957  /* multiply equality with smallest common denominator */
4958  scm = SCIPcalcSmaComMul(scalarxd, scalaryd);
4959  a = (scm/scalarxd)*scalarxn;
4960  b = (scm/scalaryd)*scalaryn;
4961  rhs *= scm;
4962 
4963  /* divide equality by the greatest common divisor of a and b */
4964  gcd = SCIPcalcGreComDiv(ABS(a), ABS(b));
4965  a /= gcd;
4966  b /= gcd;
4967  rhs /= gcd;
4968  assert(a != 0);
4969  assert(b != 0);
4970 
4971  /* check, if right hand side is integral */
4972  if( !SCIPsetIsFeasIntegral(set, rhs) )
4973  {
4974  *infeasible = TRUE;
4975  return SCIP_OKAY;
4976  }
4977  c = (SCIP_Longint)(SCIPsetFeasFloor(set, rhs));
4978 
4979  if( REALABS((SCIP_Real)(c/a)) > SCIPsetGetHugeValue(set) * SCIPsetFeastol(set) ) /*lint !e653*/
4980  return SCIP_OKAY;
4981 
4982  /* check, if we are in an easy case with either |a| = 1 or |b| = 1 */
4983  if( (a == 1 || a == -1) && SCIPvarGetType(vary) == SCIP_VARTYPE_INTEGER )
4984  {
4985  /* aggregate x = - b/a*y + c/a */
4986  /*lint --e{653}*/
4987  SCIP_CALL( SCIPvarAggregate(varx, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, cliquetable,
4988  branchcand, eventqueue, vary, (SCIP_Real)(-b/a), (SCIP_Real)(c/a), infeasible, aggregated) );
4989  assert(*aggregated);
4990  return SCIP_OKAY;
4991  }
4992  if( (b == 1 || b == -1) && SCIPvarGetType(varx) == SCIP_VARTYPE_INTEGER )
4993  {
4994  /* aggregate y = - a/b*x + c/b */
4995  /*lint --e{653}*/
4996  SCIP_CALL( SCIPvarAggregate(vary, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, cliquetable,
4997  branchcand, eventqueue, varx, (SCIP_Real)(-a/b), (SCIP_Real)(c/b), infeasible, aggregated) );
4998  assert(*aggregated);
4999  return SCIP_OKAY;
5000  }
5001 
5002  /* Both variables are integers, their coefficients are not multiples of each other, and they don't have any
5003  * common divisor. Let (x',y') be a solution of the equality
5004  * a*x + b*y == c -> a*x == c - b*y
5005  * Then x = -b*z + x', y = a*z + y' with z integral gives all solutions to the equality.
5006  */
5007 
5008  /* find initial solution (x',y'):
5009  * - find y' such that c - b*y' is a multiple of a
5010  * - start in equivalence class c%a
5011  * - step through classes, where each step increases class number by (-b)%a, until class 0 is visited
5012  * - if equivalence class 0 is visited, we are done: y' equals the number of steps taken
5013  * - 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
5014  * - calculate x' with x' = (c - b*y')/a (which must be integral)
5015  *
5016  * Algorithm works for a > 0 only.
5017  */
5018  if( a < 0 )
5019  {
5020  a = -a;
5021  b = -b;
5022  c = -c;
5023  }
5024  assert(0 <= a);
5025 
5026  /* search upwards from ysol = 0 */
5027  ysol = 0;
5028  currentclass = c%a;
5029  if( currentclass < 0 )
5030  currentclass += a;
5031  assert(0 <= currentclass && currentclass < a);
5032 
5033  classstep = (-b)%a;
5034 
5035  if( classstep < 0 )
5036  classstep += a;
5037  assert(0 <= classstep && classstep < a);
5038 
5039  while( currentclass != 0 )
5040  {
5041  assert(0 <= currentclass && currentclass < a);
5042  currentclass += classstep;
5043  if( currentclass >= a )
5044  currentclass -= a;
5045  ysol++;
5046  }
5047  assert(ysol < a);
5048  assert(((c - b*ysol)%a) == 0);
5049 
5050  xsol = (c - b*ysol)/a;
5051 
5052  /* determine variable type for new artificial variable:
5053  *
5054  * if both variables are implicit integer the new variable can be implicit too, because the integer implication on
5055  * these both variables should be enforced by some other variables, otherwise the new variable needs to be of
5056  * integral type
5057  */
5060 
5061  /* feasible solutions are (x,y) = (x',y') + z*(-b,a)
5062  * - create new integer variable z with infinite bounds
5063  * - aggregate variable x = -b*z + x'
5064  * - aggregate variable y = a*z + y'
5065  * - the bounds of z are calculated automatically during aggregation
5066  */
5067  (void) SCIPsnprintf(aggvarname, SCIP_MAXSTRLEN, "agg%d", stat->nvaridx);
5068  SCIP_CALL( SCIPvarCreateTransformed(&aggvar, blkmem, set, stat,
5069  aggvarname, -SCIPsetInfinity(set), SCIPsetInfinity(set), 0.0, vartype,
5071  NULL, NULL, NULL, NULL, NULL) );
5072 
5073  SCIP_CALL( SCIPprobAddVar(transprob, blkmem, set, lp, branchcand, eventfilter, eventqueue, aggvar) );
5074 
5075  SCIP_CALL( SCIPvarAggregate(varx, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, cliquetable,
5076  branchcand, eventqueue, aggvar, (SCIP_Real)(-b), (SCIP_Real)xsol, infeasible, aggregated) );
5077  assert(*aggregated || *infeasible);
5078 
5079  if( !(*infeasible) )
5080  {
5081  SCIP_CALL( SCIPvarAggregate(vary, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, cliquetable,
5082  branchcand, eventqueue, aggvar, (SCIP_Real)a, (SCIP_Real)ysol, infeasible, aggregated) );
5083  assert(*aggregated || *infeasible);
5084  }
5085 
5086  /* release z */
5087  SCIP_CALL( SCIPvarRelease(&aggvar, blkmem, set, eventqueue, lp) );
5088 
5089  return SCIP_OKAY;
5090 }
5091 
5092 /** performs second step of SCIPaggregateVars():
5093  * the variable to be aggregated is chosen among active problem variables x' and y', preferring a less strict variable
5094  * type as aggregation variable (i.e. continuous variables are preferred over implicit integers, implicit integers
5095  * or integers over binaries). If none of the variables is continuous, it is tried to find an integer
5096  * aggregation (i.e. integral coefficients a'' and b'', such that a''*x' + b''*y' == c''). This can lead to
5097  * the detection of infeasibility (e.g. if c'' is fractional), or to a rejection of the aggregation (denoted by
5098  * aggregated == FALSE), if the resulting integer coefficients are too large and thus numerically instable.
5099  *
5100  * @todo check for fixings, infeasibility, bound changes, or domain holes:
5101  * a) if there is no easy aggregation and we have one binary variable and another integer/implicit/binary variable
5102  * b) for implicit integer variables with fractional aggregation scalar (we cannot (for technical reasons) and do
5103  * not want to aggregate implicit integer variables, since we loose the corresponding divisibility property)
5104  */
5106  SCIP_SET* set, /**< global SCIP settings */
5107  BMS_BLKMEM* blkmem, /**< block memory */
5108  SCIP_STAT* stat, /**< problem statistics */
5109  SCIP_PROB* transprob, /**< tranformed problem data */
5110  SCIP_PROB* origprob, /**< original problem data */
5111  SCIP_PRIMAL* primal, /**< primal data */
5112  SCIP_TREE* tree, /**< branch and bound tree */
5113  SCIP_REOPT* reopt, /**< reoptimization data structure */
5114  SCIP_LP* lp, /**< current LP data */
5115  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
5116  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
5117  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
5118  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
5119  SCIP_VAR* varx, /**< variable x in equality a*x + b*y == c */
5120  SCIP_VAR* vary, /**< variable y in equality a*x + b*y == c */
5121  SCIP_Real scalarx, /**< multiplier a in equality a*x + b*y == c */
5122  SCIP_Real scalary, /**< multiplier b in equality a*x + b*y == c */
5123  SCIP_Real rhs,