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