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