Scippy

SCIP

Solving Constraint Integer Programs

reopt.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-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file reopt.c
17  * @ingroup OTHER_CFILES
18  * @brief data structures and methods for collecting reoptimization information
19  * @author Jakob Witzig
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 #include <assert.h>
24 #include <string.h>
25 
26 #include "scip/def.h"
27 #include "scip/mem.h"
28 #include "scip/event.h"
29 #include "scip/scip.h"
30 #include "scip/set.h"
31 #include "scip/sol.h"
32 #include "scip/var.h"
33 #include "scip/lp.h"
34 #include "scip/misc.h"
35 #include "scip/reopt.h"
36 #include "scip/tree.h"
37 #include "scip/primal.h"
38 #include "scip/sepastore.h"
39 #include "scip/cutpool.h"
40 #include "scip/prob.h"
41 #include "scip/cons.h"
43 #include "scip/cons_linear.h"
44 #include "scip/cons_logicor.h"
45 #include "scip/cons_setppc.h"
46 #include "scip/cons_linear.h"
47 #include "scip/clock.h"
48 #include "scip/history.h"
49 #include "blockmemshell/memory.h"
50 
51 #define DEFAULT_MEM_VARAFTERDUAL 10
52 #define DEFAULT_MEM_VAR 10
53 #define DEFAULT_MEM_NODES 1000
54 #define DEFAULT_MEM_RUN 200
55 #define DEFAULT_MEM_DUALCONS 10
56 
57 #define DEFAULT_RANDSEED 67
58 
59 /* event handler properties */
60 #define EVENTHDLR_NAME "Reopt"
61 #define EVENTHDLR_DESC "node event handler for reoptimization"
62 
63 /* ---------------- Callback methods of event handler ---------------- */
64 
65 /** exec the event handler */
66 static
67 SCIP_DECL_EVENTEXEC(eventExecReopt)
68 { /*lint --e{715}*/
69  SCIP_NODE* eventnode;
70  SCIP_Real oldbound;
71  SCIP_Real newbound;
72 
73  assert(scip != NULL);
74  assert(eventhdlr != NULL);
75  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
77 
79  return SCIP_OKAY;
80 
81  eventnode = SCIPgetCurrentNode(scip);
82  oldbound = SCIPeventGetOldbound(event);
83  newbound = SCIPeventGetNewbound(event);
84 
85  /* if we are called from the last node in the tree that is cut off, eventnode will be NULL and we do not have to store the bound changes */
86  if( eventnode == NULL )
87  return SCIP_OKAY;
88 
89  /* skip if the node is not the focus node */
91  return SCIP_OKAY;
92 
93  SCIPdebugMsg(scip, "catch event for node %lld: <%s>: %g -> %g\n", SCIPnodeGetNumber(eventnode),
95 
96  assert(SCIPisFeasLT(scip, newbound, oldbound) || SCIPisFeasGT(scip, newbound, oldbound));
97 
98  SCIP_CALL( SCIPaddReoptDualBndchg(scip, eventnode, SCIPeventGetVar(event), newbound, oldbound) );
99 
100  return SCIP_OKAY;
101 }
102 
103 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */
104 static
105 SCIP_DECL_EVENTINITSOL(eventInitsolReopt)
106 {
107  SCIP_VAR** vars;
108  int varnr;
109 
110  assert(scip != NULL);
111  assert(eventhdlr != NULL);
112  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
113 
114  if( !SCIPisReoptEnabled(scip) )
115  return SCIP_OKAY;
116 
117  vars = SCIPgetVars(scip);
118  for(varnr = 0; varnr < SCIPgetNVars(scip); ++varnr)
119  {
120  if( SCIPvarGetType(vars[varnr]) != SCIP_VARTYPE_CONTINUOUS )
121  {
122  SCIP_CALL(SCIPcatchVarEvent(scip, vars[varnr], SCIP_EVENTTYPE_GBDCHANGED, eventhdlr, NULL, NULL));
123  }
124  }
125 
126  return SCIP_OKAY;
127 }
128 
129 /** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
130 static
131 SCIP_DECL_EVENTEXITSOL(eventExitsolReopt)
132 {
133  SCIP_VAR** vars;
134  int varnr;
135  assert(scip != NULL);
136 
137  assert(eventhdlr != NULL);
138  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
139 
140  if( !SCIPisReoptEnabled(scip) )
141  return SCIP_OKAY;
142 
143  vars = SCIPgetVars(scip);
144 
145  for(varnr = 0; varnr < SCIPgetNVars(scip); ++varnr)
146  {
147  if( SCIPvarGetType(vars[varnr]) == SCIP_VARTYPE_BINARY )
148  {
149  SCIP_CALL(SCIPdropVarEvent(scip, vars[varnr], SCIP_EVENTTYPE_GBDCHANGED , eventhdlr, NULL, -1));
150  }
151  }
152  return SCIP_OKAY;
153 }
154 
155 /* ---------------- Callback methods of reoptimization methods ---------------- */
156 
157 /*
158  * memory growing methods for dynamically allocated arrays
159  */
160 
161 /** ensures size for activeconss */
162 static
164  SCIP_REOPT* reopt, /**< reoptimization data structure */
165  SCIP_SET* set, /**< global SCIP settings */
166  BMS_BLKMEM* blkmem, /**< block memory */
167  int num /**< minimum number of entries to store */
168  )
169 {
170  if( reopt->nmaxactiveconss < num )
171  {
172  int newsize = SCIPsetCalcMemGrowSize(set, num + 1);
173 
174  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->activeconss, reopt->nmaxactiveconss, newsize) );
175  reopt->nmaxactiveconss = newsize;
176  }
177  assert(num <= reopt->nmaxactiveconss);
178 
179  return SCIP_OKAY;
180 }
181 
182 /** ensures, that sols[pos] array can store at least num entries */
183 static
185  SCIP_REOPT* reopt, /**< reoptimization data structure */
186  SCIP_SET* set, /**< global SCIP settings */
187  BMS_BLKMEM* blkmem, /**< block memory */
188  int num, /**< minimum number of entries to store */
189  int runidx /**< run index for which the memory should checked */
190  )
191 {
192  assert(runidx >= 0);
193  assert(runidx <= reopt->runsize);
194 
195  if( num > reopt->soltree->solssize[runidx] )
196  {
197  int newsize = SCIPsetCalcMemGrowSize(set, num + 1);
198 
199  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->soltree->sols[runidx],
200  reopt->soltree->solssize[runidx], newsize) ); /*lint !e866 */
201 
202  reopt->soltree->solssize[runidx] = newsize;
203  }
204  assert(num <= reopt->soltree->solssize[runidx]);
205 
206  return SCIP_OKAY;
207 }
208 
209 /** ensures, that sols array can store at least num entries */
210 static
212  SCIP_REOPT* reopt, /**< reoptimization data structure */
213  SCIP_SET* set, /**< gloabl SCIP settings */
214  int num, /**< minimum number of entries to store */
215  BMS_BLKMEM* blkmem /**< block memory */
216  )
217 {
218  if( num >= reopt->runsize )
219  {
220  int s;
221  int newsize = SCIPsetCalcMemGrowSize(set, num+1);
222  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->soltree->sols, reopt->runsize, newsize) );
223  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->soltree->nsols, reopt->runsize, newsize) );
224  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->soltree->solssize, reopt->runsize, newsize) );
225  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->prevbestsols, reopt->runsize, newsize) );
226  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->varhistory, reopt->runsize, newsize) );
227  SCIP_ALLOC( BMSreallocMemoryArray(&reopt->objs, newsize) );
228 
229  for(s = reopt->runsize; s < newsize; s++)
230  {
231  reopt->varhistory[s] = NULL;
232  reopt->prevbestsols[s] = NULL;
233  reopt->objs[s] = NULL;
234  reopt->soltree->solssize[s] = 0;
235  reopt->soltree->nsols[s] = 0;
236  reopt->soltree->sols[s] = NULL;
237  }
238 
239  reopt->runsize = newsize;
240  }
241  assert(num < reopt->runsize);
242 
243  return SCIP_OKAY;
244 }
245 
246 /** check the memory of the reoptimization tree and if necessary reallocate */
247 static
249  SCIP_REOPTTREE* reopttree, /**< reoptimization tree */
250  SCIP_SET* set, /**< global SCIP settings */
251  BMS_BLKMEM* blkmem /**< block memory */
252  )
253 {
254  assert(reopttree != NULL);
255  assert(blkmem != NULL);
256 
257  if( SCIPqueueIsEmpty(reopttree->openids) )
258  {
259  int newsize;
260  unsigned int id;
261 
262  assert(reopttree->nreoptnodes == (int)(reopttree->reoptnodessize));
263 
264  newsize = SCIPsetCalcMemGrowSize(set, (int)reopttree->reoptnodessize+1);
265  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopttree->reoptnodes, reopttree->reoptnodessize, newsize) ); /*lint !e647*/
266 
267  for( id = reopttree->reoptnodessize; id < (unsigned int)newsize; id++ )
268  {
269  SCIP_CALL( SCIPqueueInsertUInt(reopttree->openids, id) );
270  reopttree->reoptnodes[id] = NULL;
271  }
272 
273  reopttree->reoptnodessize = (unsigned int)newsize;
274  }
275 
276  return SCIP_OKAY;
277 }
278 
279 /** check allocated memory of a node within the reoptimization tree and if necessary reallocate */
280 static
282  SCIP_REOPTNODE* reoptnode, /**< node of the reoptimization tree */
283  SCIP_SET* set, /**< global SCIP settings */
284  BMS_BLKMEM* blkmem, /**< block memory */
285  int var_mem, /**< memory for variables */
286  int child_mem, /**< memory for child nodes */
287  int conss_mem /**< memory for constraints */
288  )
289 {
290  int newsize;
291 
292  assert(reoptnode != NULL);
293  assert(blkmem != NULL);
294  assert(var_mem >= 0);
295  assert(child_mem >= 0);
296  assert(conss_mem >= 0);
297 
298  /* check allocated memory for variable and bound information */
299  if( var_mem > 0 )
300  {
301  if( reoptnode->varssize == 0 )
302  {
303  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reoptnode->vars, var_mem) );
304  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reoptnode->varbounds, var_mem) );
305  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reoptnode->varboundtypes, var_mem) );
306  reoptnode->varssize = var_mem;
307  }
308  else if( reoptnode->varssize < var_mem )
309  {
310  newsize = SCIPsetCalcMemGrowSize(set, var_mem+1);
311  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reoptnode->vars, reoptnode->varssize, newsize) );
312  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reoptnode->varbounds, reoptnode->varssize, newsize) );
313  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reoptnode->varboundtypes, reoptnode->varssize, newsize) );
314  reoptnode->varssize = newsize;
315  }
316  }
317 
318  /* check allocated memory for child node information */
319  if( child_mem > 0 )
320  {
321  if( reoptnode->allocchildmem == 0 )
322  {
323  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reoptnode->childids, child_mem) );
324  reoptnode->nchilds = 0;
325  reoptnode->allocchildmem = child_mem;
326  }
327  else if( reoptnode->allocchildmem < child_mem )
328  {
329  newsize = SCIPsetCalcMemGrowSize(set, child_mem+1);
330  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reoptnode->childids, reoptnode->allocchildmem, newsize) );
331  reoptnode->allocchildmem = newsize;
332  }
333  }
334 
335  /* check allocated memory for add constraints */
336  if( conss_mem > 0 )
337  {
338  if( reoptnode->consssize == 0 )
339  {
340  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reoptnode->conss, conss_mem) );
341  reoptnode->nconss = 0;
342  reoptnode->consssize = conss_mem;
343  }
344  else if( reoptnode->consssize < conss_mem )
345  {
346  newsize = SCIPsetCalcMemGrowSize(set, conss_mem);
347  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reoptnode->conss, reoptnode->consssize, newsize) );
348  reoptnode->consssize = newsize;
349  }
350  }
351 
352  return SCIP_OKAY;
353 }
354 
355 /*
356  * local methods
357  */
358 
359 /** returns the number of stored solutions in the subtree induced by @p solnode */
360 static
362  SCIP_SOLNODE* solnode /**< node within the solution tree */
363  )
364 {
365  SCIP_SOLNODE* sibling;
366  int nsols;
367 
368  assert(solnode != NULL);
369 
370  if( solnode->child == NULL && solnode->sol == NULL )
371  return 0;
372  if( solnode->child == NULL && solnode->sol != NULL )
373  return 1;
374 
375  nsols = 0;
376  sibling = solnode->child;
377 
378  /* traverse through the list */
379  while( sibling != NULL )
380  {
381  nsols += soltreeNInducedSols(sibling);
382  sibling = sibling->sibling;
383  }
384 
385  return nsols;
386 }
387 
388 /** returns the similarity of the objective functions of two given iterations */
389 static
391  SCIP_REOPT* reopt, /**< reoptimization data */
392  SCIP_SET* set, /**< global SCIP settings */
393  int obj1_id, /**< id of one objective function */
394  int obj2_id, /**< id of the other objective function */
395  SCIP_VAR** vars, /**< problem variables */
396  int nvars /**< number of problem variables */
397  )
398 {
399  SCIP_Real similarity;
400  SCIP_Real norm_obj1;
401  SCIP_Real norm_obj2;
402  int v;
403 
404  assert(reopt != NULL);
405  assert(vars != NULL);
406  assert(nvars >= 0);
407 
408  similarity = 0.0;
409  norm_obj1 = 0.0;
410  norm_obj2 = 0.0;
411 
412  /* calculate similarity */
413  for( v = 0; v < nvars; v++ )
414  {
415  SCIP_VAR* origvar;
416  SCIP_VAR* transvar;
417  SCIP_Real c1;
418  SCIP_Real c2;
419  SCIP_Real lb;
420  SCIP_Real ub;
421 
422  origvar = vars[v];
423 
424  /* get the original variable */
425  if( !SCIPvarIsOriginal(origvar) )
426  {
427  SCIP_RETCODE retcode;
428  SCIP_Real constant = 0.0;
429  SCIP_Real scalar = 1.0;
430 
431  retcode = SCIPvarGetOrigvarSum(&origvar, &scalar, &constant);
432 
433  if( retcode != SCIP_OKAY )
434  return SCIP_INVALID;
435  }
436  assert(origvar != NULL && SCIPvarIsOriginal(origvar));
437 
438  /* get the transformed variable, we skip globally fixed variables */
439  transvar = SCIPvarGetTransVar(origvar);
440  assert(transvar != NULL);
441 
442  lb = SCIPvarGetLbLocal(transvar);
443  ub = SCIPvarGetUbLocal(transvar);
444 
445  if( SCIPsetIsFeasLT(set, lb, ub) )
446  {
447  int probidx;
448 
449  probidx = SCIPvarGetIndex(origvar);
450  assert(0 <= probidx && probidx < reopt->nobjvars);
451 
452  c1 = reopt->objs[obj1_id][probidx];
453  c2 = reopt->objs[obj2_id][probidx];
454 
455  /* vector product */
456  similarity += c1*c2;
457  norm_obj1 += SQR(c1);
458  norm_obj2 += SQR(c2);
459  }
460  }
461 
462  /* divide similarity by norms of the objective vectors */
463  norm_obj1 = SQRT(norm_obj1);
464  norm_obj2 = SQRT(norm_obj2);
465 
466  if( !SCIPsetIsZero(set, norm_obj1) && !SCIPsetIsZero(set, norm_obj2) )
467  similarity /= (norm_obj1 * norm_obj2);
468 
469  /* make sure that we are between -1.0 und +1.0 */
470  similarity = MAX(similarity, -1.0);
471  similarity = MIN(similarity, 1.0);
472 
473  return similarity;
474 }
475 
476 /** delete the given reoptimization node */
477 static
479  SCIP_REOPTNODE** reoptnode, /**< node of the reoptimization tree */
480  BMS_BLKMEM* blkmem /**< block memory */
481  )
482 {
483  assert((*reoptnode) != NULL );
484  assert(blkmem != NULL );
485 
486  /* delete data for constraints */
487  if( (*reoptnode)->consssize > 0 )
488  {
489  int c;
490 
491  assert((*reoptnode)->conss != NULL);
492 
493  for( c = 0; c < (*reoptnode)->nconss; c++ )
494  {
495  assert((*reoptnode)->conss[c] != NULL);
496  assert((*reoptnode)->conss[c]->vals != NULL);
497  assert((*reoptnode)->conss[c]->vars != NULL);
498 
499  BMSfreeBlockMemoryArrayNull(blkmem, &(*reoptnode)->conss[c]->boundtypes, (*reoptnode)->conss[c]->varssize);
500  BMSfreeBlockMemoryArrayNull(blkmem, &(*reoptnode)->conss[c]->vals, (*reoptnode)->conss[c]->varssize);
501  BMSfreeBlockMemoryArrayNull(blkmem, &(*reoptnode)->conss[c]->vars, (*reoptnode)->conss[c]->varssize);
502  BMSfreeBlockMemory(blkmem, &(*reoptnode)->conss[c]); /*lint !e866*/
503  }
504  BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->conss, (*reoptnode)->consssize);
505  (*reoptnode)->nconss = 0;
506  (*reoptnode)->consssize = 0;
507  (*reoptnode)->conss = NULL;
508  }
509 
510  /* free list of children */
511  if( (*reoptnode)->childids != NULL )
512  {
513  BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->childids, (*reoptnode)->allocchildmem);
514  (*reoptnode)->nchilds = 0;
515  (*reoptnode)->allocchildmem = 0;
516  (*reoptnode)->childids = NULL;
517  }
518 
519  /* delete dual constraint */
520  if( (*reoptnode)->dualredscur != NULL )
521  {
522  assert((*reoptnode)->dualredscur->varssize > 0);
523  BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->dualredscur->boundtypes, (*reoptnode)->dualredscur->varssize);
524  BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->dualredscur->vals, (*reoptnode)->dualredscur->varssize);
525  BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->dualredscur->vars, (*reoptnode)->dualredscur->varssize);
526  BMSfreeBlockMemory(blkmem, &(*reoptnode)->dualredscur);
527  (*reoptnode)->dualredscur = NULL;
528  }
529 
530  /* delete dual constraint */
531  if( (*reoptnode)->dualredsnex != NULL )
532  {
533  assert((*reoptnode)->dualredsnex->varssize > 0);
534  BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->dualredsnex->boundtypes, (*reoptnode)->dualredsnex->varssize);
535  BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->dualredsnex->vals, (*reoptnode)->dualredsnex->varssize);
536  BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->dualredsnex->vars, (*reoptnode)->dualredsnex->varssize);
537  BMSfreeBlockMemory(blkmem, &(*reoptnode)->dualredsnex);
538  (*reoptnode)->dualredsnex = NULL;
539  }
540 
541  /* free boundtypes */
542  if ((*reoptnode)->varboundtypes != NULL )
543  {
544  assert((*reoptnode)->varssize > 0);
545  BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->varboundtypes, (*reoptnode)->varssize);
546  (*reoptnode)->varboundtypes = NULL;
547  }
548 
549  /* free bounds */
550  if ((*reoptnode)->varbounds != NULL )
551  {
552  assert((*reoptnode)->varssize > 0);
553  BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->varbounds, (*reoptnode)->varssize);
554  (*reoptnode)->varbounds = NULL;
555  }
556 
557  /* free variables */
558  if ((*reoptnode)->vars != NULL )
559  {
560  assert((*reoptnode)->varssize > 0);
561  BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->vars, (*reoptnode)->varssize);
562  (*reoptnode)->vars = NULL;
563  }
564 
565  (*reoptnode)->varssize = 0;
566 
567  /* free afterdual-boundtypes */
568  if ((*reoptnode)->afterdualvarboundtypes != NULL )
569  {
570  assert((*reoptnode)->afterdualvarssize > 0);
571  BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->afterdualvarboundtypes, (*reoptnode)->afterdualvarssize);
572  (*reoptnode)->afterdualvarboundtypes = NULL;
573  }
574 
575  /* free afterdual-bounds */
576  if ((*reoptnode)->afterdualvarbounds != NULL )
577  {
578  assert((*reoptnode)->afterdualvarssize > 0);
579  BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->afterdualvarbounds, (*reoptnode)->afterdualvarssize);
580  (*reoptnode)->afterdualvarbounds = NULL;
581  }
582 
583  /* free afterdual-variables */
584  if ((*reoptnode)->afterdualvars != NULL )
585  {
586  assert((*reoptnode)->afterdualvarssize > 0);
587  BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->afterdualvars, (*reoptnode)->afterdualvarssize);
588  (*reoptnode)->afterdualvars = NULL;
589  }
590 
591  (*reoptnode)->afterdualvarssize = 0;
592 
593  BMSfreeBlockMemory(blkmem, reoptnode);
594  (*reoptnode) = NULL;
595 
596  return SCIP_OKAY;
597 }
598 
599 /** reset the given reoptimization node */
600 static
602  SCIP_REOPTNODE* reoptnode, /**< reoptimization node */
603  SCIP_SET* set, /**< global SCIP settings */
604  BMS_BLKMEM* blkmem /**< block memory */
605  )
606 {
607  assert(reoptnode != NULL);
608  assert(set != NULL);
609  assert(blkmem != NULL);
610 
611  /* remove and delete all constraints */
612  if( reoptnode->nconss > 0 )
613  {
614  int c;
615 
616  assert(reoptnode->conss != NULL);
617  assert(reoptnode->consssize > 0);
618 
619  for( c = 0; c < reoptnode->nconss; c++ )
620  {
621  if( !reoptnode->conss[c]->linear )
622  {
623  assert(reoptnode->conss[c]->boundtypes != NULL);
624  BMSfreeBlockMemoryArray(blkmem, &reoptnode->conss[c]->boundtypes, reoptnode->conss[c]->varssize);
625  }
626  BMSfreeBlockMemoryArray(blkmem, &reoptnode->conss[c]->vals, reoptnode->conss[c]->varssize);
627  BMSfreeBlockMemoryArray(blkmem, &reoptnode->conss[c]->vars, reoptnode->conss[c]->varssize);
628  BMSfreeBlockMemory(blkmem, &reoptnode->conss[c]); /*lint !e866 */
629  }
630  reoptnode->nconss = 0;
631  }
632 
633  /* remove all children */
634  if( reoptnode->childids != NULL )
635  reoptnode->nchilds = 0;
636 
637  /* delete dual constraint */
638  if( reoptnode->dualredscur != NULL )
639  {
640  assert(reoptnode->dualredscur->varssize > 0);
641  if( !reoptnode->dualredscur->linear )
642  {
643  assert(reoptnode->dualredscur->boundtypes != NULL);
644  BMSfreeBlockMemoryArray(blkmem, &reoptnode->dualredscur->boundtypes, reoptnode->dualredscur->varssize);
645  }
646  BMSfreeBlockMemoryArray(blkmem, &reoptnode->dualredscur->vals, reoptnode->dualredscur->varssize);
647  BMSfreeBlockMemoryArray(blkmem, &reoptnode->dualredscur->vars, reoptnode->dualredscur->varssize);
648  BMSfreeBlockMemory(blkmem, &reoptnode->dualredscur);
649  reoptnode->dualredscur = NULL;
650  }
651 
652  /* delete dual constraint */
653  if( reoptnode->dualredsnex != NULL )
654  {
655  assert(reoptnode->dualredsnex->varssize > 0);
656  if( !reoptnode->dualredsnex->linear )
657  {
658  assert(reoptnode->dualredsnex->boundtypes != NULL);
659  BMSfreeBlockMemoryArray(blkmem, &reoptnode->dualredsnex->boundtypes, reoptnode->dualredsnex->varssize);
660  }
661  BMSfreeBlockMemoryArray(blkmem, &reoptnode->dualredsnex->vals, reoptnode->dualredsnex->varssize);
662  BMSfreeBlockMemoryArray(blkmem, &reoptnode->dualredsnex->vars, reoptnode->dualredsnex->varssize);
663  BMSfreeBlockMemory(blkmem, &reoptnode->dualredsnex);
664  reoptnode->dualredsnex = NULL;
665  }
666 
667  reoptnode->parentID = 0;
668  reoptnode->nvars = 0;
669  reoptnode->nafterdualvars = 0;
670  reoptnode->dualreds = FALSE;
671  reoptnode->reopttype = (unsigned int)SCIP_REOPTTYPE_NONE;
672  reoptnode->lowerbound = -SCIPsetInfinity(set);
673 
674  return SCIP_OKAY;
675 }
676 
677 /** delete the node stored at position @p nodeID of the reoptimization tree */
678 static
680  SCIP_REOPTTREE* reopttree, /**< reoptimization tree */
681  SCIP_SET* set, /**< global SCIP settings */
682  BMS_BLKMEM* blkmem, /**< block memory */
683  unsigned int id, /**< id of a node */
684  SCIP_Bool softreset /**< delete at the end of the solving process */
685  )
686 {
687  assert(reopttree != NULL );
688  assert(id < reopttree->reoptnodessize);
689  assert(reopttree->reoptnodes[id] != NULL );
690 
691  if( softreset )
692  {
693  SCIP_CALL( reoptnodeReset(reopttree->reoptnodes[id], set, blkmem) );
694  }
695  else
696  {
697  SCIP_CALL( reoptnodeDelete(&reopttree->reoptnodes[id], blkmem) );
698  }
699 
700  assert(softreset || reopttree->reoptnodes[id] == NULL);
701  assert(reopttree->reoptnodes[id] == NULL || reopttree->reoptnodes[id]->conss == NULL || reopttree->reoptnodes[id]->nconss == 0);
702  assert(reopttree->reoptnodes[id] == NULL || reopttree->reoptnodes[id]->childids == NULL || reopttree->reoptnodes[id]->nchilds == 0);
703 
704  --reopttree->nreoptnodes;
705 
706  return SCIP_OKAY;
707 }
708 
709 /** constructor of the solution tree */
710 static
712  SCIP_SOLTREE* soltree, /**< solution tree */
713  BMS_BLKMEM* blkmem /**< block memory */
714  )
715 {
716  int s;
717 
718  assert(soltree != NULL);
719 
723 
724  for( s = 0; s < DEFAULT_MEM_RUN; s++ )
725  {
726  soltree->nsols[s] = 0;
727  soltree->solssize[s] = 0;
728  soltree->sols[s] = NULL;
729  }
730 
731  /* allocate the root node */
732  SCIP_ALLOC( BMSallocBlockMemory(blkmem, &soltree->root) );
733  soltree->root->sol = NULL;
734  soltree->root->value = SCIP_INVALID;
735  soltree->root->updated = FALSE;
736  soltree->root->father = NULL;
737  soltree->root->child = NULL;
738  soltree->root->sibling = NULL;
739 
740  return SCIP_OKAY;
741 }
742 
743 /** free the given solution node */
744 static
746  SCIP_REOPT* reopt, /**< reoptimization data */
747  SCIP_SET* set, /**< global SCIP settings */
748  SCIP_PRIMAL* primal, /**< the primal */
749  BMS_BLKMEM* blkmem, /**< block memory */
750  SCIP_SOLNODE** solnode /**< node within the solution tree */
751  )
752 {
753  SCIP_SOLNODE* child;
754  SCIP_SOLNODE* sibling;
755 
756  assert(reopt != NULL);
757  assert(set != NULL);
758  assert(primal != NULL || set->stage == SCIP_STAGE_INIT);
759  assert(solnode != NULL);
760  assert(blkmem != NULL);
761 
762  child = (*solnode)->child;
763 
764  /* traverse through the list and free recursive all subtree */
765  while( child != NULL )
766  {
767  SCIP_CALL( soltreefreeNode(reopt, set, primal, blkmem, &child) );
768  assert(child != NULL);
769 
770  sibling = child->sibling;
771  BMSfreeBlockMemoryNull(blkmem, &child);
772  child = sibling;
773  }
774 
775  if( (*solnode)->sol != NULL )
776  {
777  assert(set->stage == SCIP_STAGE_PROBLEM);
778 
779  SCIP_CALL( SCIPsolFree(&(*solnode)->sol, blkmem, primal) );
780  }
781 
782  return SCIP_OKAY;
783 }
784 
785 /** free the solution tree */
786 static
788  SCIP_REOPT* reopt, /**< reoptimization data */
789  SCIP_SET* set, /**< global SCIP settings */
790  SCIP_PRIMAL* origprimal, /**< the origprimal */
791  BMS_BLKMEM* blkmem /**< block memory */
792  )
793 {
794  assert(reopt != NULL);
795  assert(reopt->soltree != NULL);
796  assert(reopt->soltree->root != NULL);
797  assert(set != NULL);
798  assert(blkmem != NULL);
799 
800  /* free all nodes recursive */
801  SCIP_CALL( soltreefreeNode(reopt, set, origprimal, blkmem, &reopt->soltree->root) );
802  BMSfreeBlockMemoryNull(blkmem, &reopt->soltree->root);
803 
804  BMSfreeBlockMemoryArray(blkmem, &reopt->soltree->sols, reopt->runsize);
805  BMSfreeBlockMemoryArray(blkmem, &reopt->soltree->nsols, reopt->runsize);
806  BMSfreeBlockMemoryArray(blkmem, &reopt->soltree->solssize, reopt->runsize);
807 
808  BMSfreeMemory(&reopt->soltree);
809 
810  return SCIP_OKAY;
811 }
812 
813 /** creates and adds a solution node to the solution tree */
814 static
816  SCIP_SET* set, /**< global SCIP settings */
817  BMS_BLKMEM* blkmem, /**< block memory */
818  SCIP_SOLNODE* curnode, /**< current node in the solution tree */
819  SCIP_SOLNODE** child, /**< pointer to store the node representing the solution value */
820  SCIP_VAR* var, /**< variable represented by this node */
821  SCIP_Real val, /**< value the child shell represent */
822  SCIP_Bool* added /**< TRUE iff we created a new node, i.e, we have not seen this solution so far */
823  )
824 {
825  SCIP_SOLNODE* solnode;
826 
827  assert(set != NULL);
828  assert(blkmem != NULL);
829  assert(curnode != NULL);
830  assert(child != NULL && *child == NULL);
831  assert(!SCIPsetIsInfinity(set, -val) && !SCIPsetIsInfinity(set, val));
832 
833  /* get the first node of the child node list */
834  *child = curnode->child;
835 
836  /* this is the first solution in the subtree induced by the current node */
837  if( *child == NULL )
838  {
839  assert(soltreeNInducedSols(curnode) == 0);
840 
841  SCIP_ALLOC( BMSallocBlockMemory(blkmem, &solnode) );
842  solnode->sol = NULL;
843  solnode->updated = FALSE;
844  solnode->father = curnode;
845  solnode->child = NULL;
846  solnode->sibling = NULL;
847  solnode->value = val;
848 #ifndef NDEBUG
849  assert(var != NULL);
850  solnode->var = var;
851 #endif
852 
853  *added = TRUE;
854  *child = solnode;
855 
856  curnode->child = *child;
857 
858 #ifdef SCIP_MORE_DEBUG
859  SCIPsetDebugMsg(set, "-> create new node %p: value=%g, sibling=%p\n", (void*) solnode, solnode->value,
860  (void*) solnode->sibling);
861 #endif
862  }
863  else
864  {
865  /* we traverse through all children */
866  while( *child != NULL )
867  {
868 #ifdef SCIP_MORE_DEBUG
869  SCIPsetDebugMsg(set, "-> check %p: father=%p, value=%g, sibling=%p\n", (void*) *child, (void*) (*child)->father,
870  (*child)->value, (void*) (*child)->sibling);
871 #endif
872  /* we found a node repesenting this solution value */
873  if( SCIPsetIsEQ(set, val, (*child)->value) )
874  break;
875 
876  /* we are at the end of the list */
877  if( (*child)->sibling == NULL )
878  {
879  /* create a new solnode */
880  SCIP_ALLOC( BMSallocBlockMemory(blkmem, &solnode) );
881  solnode->sol = NULL;
882  solnode->updated = FALSE;
883  solnode->father = curnode;
884  solnode->child = NULL;
885  solnode->value = val;
886 #ifndef NDEBUG
887  assert(var != NULL);
888  solnode->var = var;
889 #endif
890  *added = TRUE;
891 
892  /* we have to append the new node at the end of the list. but we have to check whether the insertion before
893  * the current node would be correct. in that case, we switch the values, the child pointer, and the
894  * solution
895  */
896  solnode->sibling = NULL;
897  (*child)->sibling = solnode;
898 
899 #ifdef SCIP_MORE_DEBUG
900  SCIPsetDebugMsg(set, "-> create new node %p: value=%g, sibling=%p\n", (void*) solnode, solnode->value,
901  (void*) solnode->sibling);
902 #endif
903  /* the given value is lower than the current, insertion before the current node would be correct
904  * in this case we do not have to change the child pointer
905  */
906  if( SCIPsetIsLT(set, val, (*child)->value) )
907  {
908 #ifdef SCIP_MORE_DEBUG
909  SCIPsetDebugMsg(set, "-> need to switch:\n");
910  SCIPsetDebugMsg(set, " before switching: node %p witch child=%p, sibling=%p, sol=%p, value=%g\n",
911  (void*) (*child), (void*) (*child)->child, (void*) (*child)->sibling, (void*) (*child)->sol,
912  (*child)->value);
913  SCIPsetDebugMsg(set, " node %p witch child=%p, sibling=%p, sol=%p, value=%g\n",
914  (void*) solnode, (void*) solnode->child, (void*) solnode->sibling, (void*) solnode->sol,
915  solnode->value);
916 #endif
917  /* switch child pointer */
918  solnode->child = (*child)->child;
919  (*child)->child = NULL;
920 
921  /* switch solution values */
922  solnode->value = (*child)->value;
923  (*child)->value = val;
924  assert(SCIPsetIsLT(set, (*child)->value, solnode->value));
925 
926  /* switch solution pointer */
927  solnode->sol = (*child)->sol;
928  (*child)->sol = NULL;
929 #ifdef SCIP_MORE_DEBUG
930  SCIPsetDebugMsg(set, " after switching: node %p witch child=%p, sibling=%p, sol=%p, value=%g\n",
931  (void*) (*child), (void*) (*child)->child, (void*) (*child)->sibling, (void*) (*child)->sol,
932  (*child)->value);
933  SCIPsetDebugMsg(set, " node %p witch child=%p, sibling=%p, sol=%p, value=%g\n",
934  (void*) solnode, (void*) solnode->child, (void*) solnode->sibling, (void*) solnode->sol,
935  solnode->value);
936 #endif
937  }
938  /* set the child pointer to the new created solnode */
939  else
940  (*child) = solnode;
941 
942  break;
943  }
944 
945  /* the next sibling represents a solution value of larger size.
946  * we insert a new node between the current child and the next sibling.
947  */
948  if( SCIPsetIsLT(set, val, (*child)->sibling->value) )
949  {
950  /* create a new solnode that points to the sibling of the current child */
951  SCIP_ALLOC( BMSallocBlockMemory(blkmem, &solnode) );
952  solnode->sol = NULL;
953  solnode->updated = FALSE;
954  solnode->father = curnode;
955  solnode->child = NULL;
956  solnode->sibling = (*child)->sibling;
957  solnode->value = val;
958 #ifndef NDEBUG
959  assert(var != NULL);
960  solnode->var = var;
961 #endif
962  *added = TRUE;
963 
964  /* change the poiter of the next sibling to the new node */
965  (*child)->sibling = solnode;
966 
967  *child = solnode;
968 #ifdef SCIP_MORE_DEBUG
969  SCIPsetDebugMsg(set, "-> create new node %p: value=%g, sibling=%p\n", (void*) solnode, solnode->value,
970  (void*) solnode->sibling);
971 #endif
972  break;
973  }
974 
975  /* go to the next sibling */
976  *child = (*child)->sibling;
977  }
978 
979 #ifdef SCIP_DEBUG
980  /* check whether the insert was correct and the list is increasing */
981  solnode = curnode->child;
982  assert(solnode != NULL);
983 
984  while( solnode->sibling != NULL )
985  {
986  assert(SCIPsetIsLT(set, solnode->value, solnode->sibling->value));
987  solnode = solnode->sibling;
988  }
989 #endif
990  }
991  return SCIP_OKAY;
992 }
993 
994 /** add a solution to the solution tree */
995 static
997  SCIP_REOPT* reopt, /**< reoptimization data */
998  SCIP_SET* set, /**< global SCIP settings */
999  SCIP_STAT* stat, /**< dynamic problem statistics */
1000  SCIP_PRIMAL* origprimal, /**< orig primal */
1001  BMS_BLKMEM* blkmem, /**< block memory */
1002  SCIP_VAR** vars, /**< array of original variables */
1003  SCIP_SOL* sol, /**< solution to add */
1004  SCIP_SOLNODE** solnode, /**< current solution node */
1005  int nvars, /**< number of variables */
1006  SCIP_Bool bestsol, /**< is the solution an optimal (best found) solution */
1007  SCIP_Bool* added /**< pointer to store the result */
1008  )
1009 {
1010  SCIP_SOLNODE* cursolnode;
1011  SCIP_Bool purelp;
1012  int varid;
1013 
1014  assert(reopt != NULL);
1015  assert(set != NULL);
1016  assert(stat != NULL);
1017  assert(origprimal != NULL);
1018  assert(blkmem != NULL);
1019  assert(vars != NULL);
1020  assert(sol != NULL);
1021  assert(solnode != NULL);
1022 
1023  cursolnode = reopt->soltree->root;
1024  *added = FALSE;
1025  purelp = TRUE;
1026 
1027  if( set->reopt_savesols > 0 )
1028  {
1029 #ifdef MORE_DEBUG
1030  SCIPsetDebugMsg(set, "try to add solution found by <%s>\n", (SCIPsolGetHeur(sol) == NULL ?
1031  "relaxation" : SCIPheurGetName(SCIPsolGetHeur(sol))));
1032 #endif
1033 
1034  for( varid = 0; varid < nvars; varid++ )
1035  {
1036  if( SCIPvarGetType(vars[varid]) != SCIP_VARTYPE_CONTINUOUS )
1037  {
1038  SCIP_SOLNODE* child;
1039 
1040  purelp = FALSE;
1041  child = NULL;
1042  SCIP_CALL( solnodeAddChild(set, blkmem, cursolnode, &child, vars[varid],
1043  SCIPsolGetVal(sol, set, stat, vars[varid]), added) );
1044  assert(child != NULL);
1045  cursolnode = child;
1046  }
1047  }
1048 
1049  /* the solution was added or is an optimal solution */
1050  if( (*added || bestsol) && !purelp )
1051  {
1052  SCIP_SOL* copysol;
1053 
1054  assert(cursolnode->child == NULL);
1055 
1056  if( *added )
1057  {
1058  SCIP_CALL( SCIPsolCopy(&copysol, blkmem, set, stat, origprimal, sol) );
1059  cursolnode->sol = copysol;
1060  }
1061  else
1062  /* this is a pseudo add; we do not want to save this solution more than once, but we will link this solution
1063  * to the solution storage of this round
1064  */
1065  (*added) = TRUE;
1066 
1067  if( bestsol )
1068  {
1069  assert(reopt->prevbestsols != NULL);
1070  assert(cursolnode->sol != NULL);
1071 
1072  reopt->prevbestsols[reopt->run-1] = cursolnode->sol;
1073  }
1074 
1075  (*solnode) = cursolnode;
1076  }
1077  }
1078 
1079  return SCIP_OKAY;
1080 }
1081 
1082 /** reset all marks 'updated' to FALSE */
1083 static
1085  SCIP_SOLNODE* node /**< node within the solution tree */
1086  )
1087 {
1088  assert(node != NULL);
1089 
1090  if( node->child != NULL )
1091  {
1092  SCIP_SOLNODE* child;
1093 
1094  /* the node is no leaf */
1095  assert(node->sol == NULL);
1096  assert(!node->updated);
1097 
1098  child = node->child;
1099 
1100  /* traverse through the list of siblings */
1101  while( child != NULL )
1102  {
1103  soltreeResetMarks(child);
1104  child = child->sibling;
1105  }
1106  }
1107  else
1108  {
1109  /* the node is a leaf */
1110  assert(node->father != NULL);
1111  assert(node->sol != NULL);
1112  node->updated = FALSE;
1113  }
1114 }
1115 
1116 /** allocate memory for a node within the reoptimization tree */
1117 static
1119  SCIP_REOPTTREE* reopttree, /**< reoptimization tree */
1120  SCIP_SET* set, /**< global SCIP settings */
1121  BMS_BLKMEM* blkmem, /**< block memory */
1122  unsigned int id /**< id of the node to create */
1123  )
1124 {
1125  assert(reopttree != NULL );
1126  assert(id < reopttree->reoptnodessize);
1127 
1128  SCIPsetDebugMsg(set, "create a reoptnode at ID %u\n", id);
1129 
1130  if( reopttree->reoptnodes[id] == NULL )
1131  {
1132  SCIP_ALLOC( BMSallocBlockMemory(blkmem, &reopttree->reoptnodes[id]) ); /*lint !e866*/
1133 
1134  reopttree->reoptnodes[id]->conss = NULL;
1135  reopttree->reoptnodes[id]->nconss = 0;
1136  reopttree->reoptnodes[id]->consssize = 0;
1137  reopttree->reoptnodes[id]->childids = NULL;
1138  reopttree->reoptnodes[id]->allocchildmem = 0;
1139  reopttree->reoptnodes[id]->nchilds = 0;
1140  reopttree->reoptnodes[id]->nvars = 0;
1141  reopttree->reoptnodes[id]->nafterdualvars = 0;
1142  reopttree->reoptnodes[id]->parentID = 0;
1143  reopttree->reoptnodes[id]->dualreds = FALSE;
1144  reopttree->reoptnodes[id]->reopttype = (unsigned int)SCIP_REOPTTYPE_NONE;
1145  reopttree->reoptnodes[id]->varssize = 0;
1146  reopttree->reoptnodes[id]->afterdualvarssize = 0;
1147  reopttree->reoptnodes[id]->vars = NULL;
1148  reopttree->reoptnodes[id]->varbounds = NULL;
1149  reopttree->reoptnodes[id]->varboundtypes = NULL;
1150  reopttree->reoptnodes[id]->afterdualvars = NULL;
1151  reopttree->reoptnodes[id]->afterdualvarbounds = NULL;
1152  reopttree->reoptnodes[id]->afterdualvarboundtypes = NULL;
1153  reopttree->reoptnodes[id]->dualredscur = NULL;
1154  reopttree->reoptnodes[id]->dualredsnex = NULL;
1155  reopttree->reoptnodes[id]->lowerbound = -SCIPsetInfinity(set);
1156  }
1157  else
1158  {
1159  assert(reopttree->reoptnodes[id]->nvars == 0);
1160  assert(reopttree->reoptnodes[id]->nafterdualvars == 0);
1161  reopttree->reoptnodes[id]->reopttype = (unsigned int)SCIP_REOPTTYPE_NONE;
1162  reopttree->reoptnodes[id]->lowerbound = -SCIPsetInfinity(set);
1163  }
1164 
1165  /* increase the counter */
1166  ++reopttree->nreoptnodes;
1167 
1168  assert(reopttree->nreoptnodes + SCIPqueueNElems(reopttree->openids) == (int)reopttree->reoptnodessize);
1169 
1170  return SCIP_OKAY;
1171 }
1172 
1173 /** constructor of the reoptimization tree */
1174 static
1176  SCIP_REOPTTREE* reopttree, /**< pointer to the reoptimization tree */
1177  SCIP_SET* set, /**< global SCIP settings */
1178  BMS_BLKMEM* blkmem /**< block memory */
1179  )
1180 {
1181  unsigned int id;
1182 
1183  assert(reopttree != NULL);
1184  assert(set != NULL);
1185  assert(blkmem != NULL);
1186 
1187  /* allocate memory */
1188  reopttree->reoptnodessize = DEFAULT_MEM_NODES;
1189  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reopttree->reoptnodes, reopttree->reoptnodessize) );
1190 
1191  /* initialize the queue of open IDs */
1192  SCIP_CALL( SCIPqueueCreate(&reopttree->openids, (int)reopttree->reoptnodessize, 2.0) );
1193 
1194  /* fill the queue, but reserve the 0 for the root */
1195  for( id = 1; id < reopttree->reoptnodessize; id++ )
1196  {
1197  reopttree->reoptnodes[id] = NULL;
1198  SCIP_CALL( SCIPqueueInsertUInt(reopttree->openids, id) );
1199  }
1200  assert(SCIPqueueNElems(reopttree->openids) == (int)(reopttree->reoptnodessize)-1);
1201 
1202  reopttree->nreoptnodes = 0;
1203  reopttree->ntotalfeasnodes = 0;
1204  reopttree->nfeasnodes = 0;
1205  reopttree->ninfnodes = 0;
1206  reopttree->ntotalinfnodes= 0;
1207  reopttree->nprunednodes = 0;
1208  reopttree->ntotalprunednodes= 0;
1209  reopttree->ncutoffreoptnodes = 0;
1210  reopttree->ntotalcutoffreoptnodes = 0;
1211 
1212  /* initialize the root node */
1213  reopttree->reoptnodes[0] = NULL;
1214  SCIP_CALL( createReoptnode(reopttree, set, blkmem, 0) );
1215 
1216  return SCIP_OKAY;
1217 }
1218 
1219 /** clears the reopttree, e.g., to restart and solve the next problem from scratch */
1220 static
1222  SCIP_REOPTTREE* reopttree, /**< reoptimization tree */
1223  SCIP_SET* set, /**< global SCIP settings */
1224  BMS_BLKMEM* blkmem, /**< block memory */
1225  SCIP_Bool softreset /**< delete nodes before exit the solving process */
1226  )
1227 {
1228  unsigned int id;
1229 
1230  assert(reopttree != NULL );
1231 
1232  /* clear queue with open IDs */
1233  SCIPqueueClear(reopttree->openids);
1234  assert(SCIPqueueNElems(reopttree->openids) == 0);
1235 
1236  /* delete all data about nodes */
1237  for( id = 0; id < reopttree->reoptnodessize; id++ )
1238  {
1239  if( reopttree->reoptnodes[id] != NULL )
1240  {
1241  SCIP_CALL( reopttreeDeleteNode(reopttree, set, blkmem, id, softreset) );
1242  assert(reopttree->reoptnodes[id] == NULL || reopttree->reoptnodes[id]->nvars == 0);
1243  }
1244 
1245  if( id > 0 )
1246  {
1247  SCIP_CALL( SCIPqueueInsertUInt(reopttree->openids, id) );
1248  }
1249  }
1250  assert(SCIPqueueNElems(reopttree->openids) == (int)(reopttree->reoptnodessize)-1);
1251 
1252  reopttree->nreoptnodes = 0;
1253 
1254  return SCIP_OKAY;
1255 }
1256 
1257 /** free the reoptimization tree */
1258 static
1260  SCIP_REOPTTREE* reopttree, /**< reoptimization tree data */
1261  SCIP_SET* set, /**< global SCIP settings */
1262  BMS_BLKMEM* blkmem /**< block memory */
1263  )
1264 {
1265  assert(reopttree != NULL);
1266  assert(blkmem != NULL);
1267 
1268  /* free nodes */
1269  SCIP_CALL( clearReoptnodes(reopttree, set, blkmem, FALSE) );
1270 
1271  /* free the data */
1272  BMSfreeBlockMemoryArray(blkmem, &reopttree->reoptnodes, reopttree->reoptnodessize);
1273  SCIPqueueFree(&reopttree->openids);
1274 
1275  /* free the tree itself */
1276  BMSfreeMemory(&reopttree);
1277 
1278  return SCIP_OKAY;
1279 }
1280 
1281 /** check memory for the constraint to handle bound changes based on dual information */
1282 static
1284  SCIP_REOPT* reopt, /**< reoptimization data structure */
1285  SCIP_SET* set, /**< global SCIP settings */
1286  BMS_BLKMEM* blkmem, /**< block memory */
1287  int size /**< size which need to be allocated */
1288  )
1289 {
1290  assert(reopt != NULL);
1291  assert(blkmem != NULL);
1292  assert(size > 0);
1293 
1294  if( reopt->dualreds == NULL )
1295  {
1296  SCIP_ALLOC( BMSallocBlockMemory(blkmem, &reopt->dualreds) );
1297  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reopt->dualreds->vars, size) );
1298  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reopt->dualreds->vals, size) );
1299  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reopt->dualreds->boundtypes, size) );
1300  reopt->dualreds->varssize = size;
1301  reopt->dualreds->nvars = 0;
1302  }
1303  else if( reopt->dualreds->varssize < size )
1304  {
1305  int newsize = SCIPsetCalcMemGrowSize(set, size+1);
1306  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->dualreds->vars, reopt->dualreds->varssize, newsize) );
1307  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->dualreds->vals, reopt->dualreds->varssize, newsize) );
1308  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->dualreds->boundtypes, reopt->dualreds->varssize, newsize) );
1309  reopt->dualreds->varssize = newsize;
1310  }
1311 
1312  return SCIP_OKAY;
1313 }
1314 
1315 /** check the memory to store global constraints */
1316 static
1318  SCIP_REOPT* reopt, /**< reoptimization data structure */
1319  SCIP_SET* set, /**< global SCIP settings */
1320  BMS_BLKMEM* blkmem, /**< block memory */
1321  int mem /**< memory which has to be allocated */
1322  )
1323 {
1324  int c;
1325 
1326  assert(reopt != NULL);
1327  assert(blkmem != NULL);
1328  assert(mem > 0);
1329 
1330  if( mem > 0 ) /*lint !e774*/
1331  {
1332  if( reopt->glbconss == NULL )
1333  {
1334  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reopt->glbconss, mem) );
1335  reopt->nglbconss = 0;
1336  reopt->allocmemglbconss = mem;
1337 
1338  for( c = 0; c < reopt->allocmemglbconss; c++ )
1339  reopt->glbconss[c] = NULL;
1340  }
1341  else if( reopt->allocmemglbconss < mem )
1342  {
1343  int newsize = SCIPsetCalcMemGrowSize(set, mem+1);
1344 
1345  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->glbconss, reopt->allocmemglbconss, newsize) );
1346 
1347  for( c = reopt->allocmemglbconss; c < newsize; c++ )
1348  reopt->glbconss[c] = NULL;
1349 
1350  reopt->allocmemglbconss = newsize;
1351  }
1352  }
1353 
1354  return SCIP_OKAY;
1355 }
1356 
1357 /** reactivate globally valid constraints that were deactivated and necessary to ensure correctness */
1358 static
1360  SCIP_REOPT* reopt, /**< reoptimization data structure */
1361  SCIP_SET* set, /**< global SCIP settings */
1362  BMS_BLKMEM* blkmem /**< block memory */
1363  )
1364 {
1365  int i;
1366 
1367  assert(reopt != NULL);
1368 
1369  /* exit if there are no active constraints */
1370  if( reopt->nactiveconss == 0 )
1371  return SCIP_OKAY;
1372 
1373  SCIPsetDebugMsg(set, "Cleaning %d active conss.\n", reopt->nactiveconss);
1374  assert(reopt->activeconss != NULL);
1375  assert(reopt->activeconssset != NULL);
1376  assert(reopt->nactiveconss <= reopt->nmaxactiveconss);
1377 
1378  /* loop over all stored constraints and reactivate deactivated constraints */
1379  for( i = 0; i < reopt->nactiveconss; i++ )
1380  {
1381  assert(reopt->activeconss[i] != NULL);
1382  assert(SCIPhashsetExists(reopt->activeconssset, reopt->activeconss[i]));
1383  SCIP_CALL( SCIPconsRelease(&reopt->activeconss[i], blkmem, set) );
1384  }
1385 
1386  /* also clean up hashset */
1388  reopt->nactiveconss = 0;
1389 
1390  return SCIP_OKAY;
1391 }
1392 
1393 /** update the bound changes made by constraint propagations during current iteration; stop saving the bound changes if
1394  * we reach a branching decision based on a dual information.
1395  */
1396 static
1398  SCIP_REOPT* reopt, /**< reoptimization data structure */
1399  SCIP_SET* set, /**< global SCIP settings */
1400  BMS_BLKMEM* blkmem, /**< block memory */
1401  SCIP_NODE* node, /**< node of the search tree */
1402  unsigned int id, /**< id of the node */
1403  SCIP_Bool* transintoorig /**< transform variables into originals */
1404  )
1405 {
1406  int nvars;
1407  int nconsprops;
1408  int naddedbndchgs;
1409 
1410  assert(reopt != NULL);
1411  assert(blkmem != NULL);
1412  assert(node != NULL);
1413  assert(0 < id && id < reopt->reopttree->reoptnodessize);
1414  assert(reopt->reopttree->reoptnodes[id] != NULL );
1415 
1416  /* get the number of all stored constraint propagations */
1417  SCIPnodeGetNDomchg(node, NULL, &nconsprops, NULL);
1418  nvars = reopt->reopttree->reoptnodes[id]->nvars;
1419 
1420  if( nconsprops > 0 )
1421  {
1422  /* check the memory */
1423  SCIP_CALL( reoptnodeCheckMemory(reopt->reopttree->reoptnodes[id], set, blkmem, nvars + nconsprops, 0, 0) );
1424 
1425  SCIPnodeGetConsProps(node,
1426  &reopt->reopttree->reoptnodes[id]->vars[nvars],
1427  &reopt->reopttree->reoptnodes[id]->varbounds[nvars],
1428  &reopt->reopttree->reoptnodes[id]->varboundtypes[nvars],
1429  &naddedbndchgs,
1430  reopt->reopttree->reoptnodes[id]->varssize-nvars);
1431 
1432  assert(nvars + naddedbndchgs <= reopt->reopttree->reoptnodes[id]->varssize);
1433 
1434  reopt->reopttree->reoptnodes[id]->nvars += naddedbndchgs;
1435 
1436  *transintoorig = TRUE;
1437  }
1438 
1439  return SCIP_OKAY;
1440 }
1441 
1442 /** save bound changes made after the first bound change based on dual information, e.g., mode by strong branching
1443  *
1444  * This method can be used during reoptimization. If we want to reconstruct a node containing dual bound changes we
1445  * have to split the node into the original one and at least one node representing the pruned part. All bound changes,
1446  * i.e., (constraint) propagation, made after the first bound change based on dual information are still valid for
1447  * the original node after changing the objective function. thus, we can store them for the following iterations.
1448  *
1449  * It should be noted, that these bound changes will be found by (constraint) propagation methods anyway after changing
1450  * the objective function. do not saving these information and find them again might be useful for conflict analysis.
1451  */
1452 static
1454  SCIP_REOPT* reopt, /**< reoptimization data structure */
1455  SCIP_SET* set, /**< global SCIP settings */
1456  BMS_BLKMEM* blkmem, /**< block memory */
1457  SCIP_NODE* node, /**< node of the search tree */
1458  unsigned int id, /**< id of the node */
1459  SCIP_Bool* transintoorig /**< transform variables into originals */
1460  )
1461 {
1462  int nbranchvars;
1463 
1464  assert(reopt != NULL);
1465  assert(blkmem != NULL);
1466  assert(node != NULL);
1467  assert(0 < id && id < reopt->reopttree->reoptnodessize);
1468  assert(reopt->reopttree->reoptnodes[id] != NULL );
1469 
1470  nbranchvars = 0;
1471 
1472  /* allocate memory */
1473  if (reopt->reopttree->reoptnodes[id]->afterdualvarssize == 0)
1474  {
1475  assert(reopt->reopttree->reoptnodes[id]->afterdualvars == NULL );
1476  assert(reopt->reopttree->reoptnodes[id]->afterdualvarbounds == NULL );
1477  assert(reopt->reopttree->reoptnodes[id]->afterdualvarboundtypes == NULL );
1478 
1479  /* allocate block memory for node information */
1482  reopt->reopttree->reoptnodes[id]->afterdualvarssize) );
1484  reopt->reopttree->reoptnodes[id]->afterdualvarssize) );
1486  reopt->reopttree->reoptnodes[id]->afterdualvarssize) );
1487  }
1488 
1489  assert(reopt->reopttree->reoptnodes[id]->afterdualvarssize > 0);
1490  assert(reopt->reopttree->reoptnodes[id]->nafterdualvars >= 0);
1491 
1493  reopt->reopttree->reoptnodes[id]->afterdualvars,
1496  reopt->reopttree->reoptnodes[id]->nafterdualvars,
1497  &nbranchvars,
1498  reopt->reopttree->reoptnodes[id]->afterdualvarssize);
1499 
1500  if( nbranchvars > reopt->reopttree->reoptnodes[id]->afterdualvarssize )
1501  {
1502  int newsize = SCIPsetCalcMemGrowSize(set, nbranchvars+1);
1504  reopt->reopttree->reoptnodes[id]->afterdualvarssize, newsize) );
1506  reopt->reopttree->reoptnodes[id]->afterdualvarssize, newsize) );
1508  reopt->reopttree->reoptnodes[id]->afterdualvarssize, newsize) );
1509  reopt->reopttree->reoptnodes[id]->afterdualvarssize = newsize;
1510 
1512  reopt->reopttree->reoptnodes[id]->afterdualvars,
1515  reopt->reopttree->reoptnodes[id]->nafterdualvars,
1516  &nbranchvars,
1517  reopt->reopttree->reoptnodes[id]->afterdualvarssize);
1518  }
1519 
1520  /* the stored variables of this node need to be transformed into the original space */
1521  if( nbranchvars > 0 )
1522  *transintoorig = TRUE;
1523 
1524  SCIPsetDebugMsg(set, " -> save %d bound changes after dual reductions\n", nbranchvars);
1525 
1526  assert(nbranchvars <= reopt->reopttree->reoptnodes[id]->afterdualvarssize); /* this should be the case */
1527 
1528  reopt->reopttree->reoptnodes[id]->nafterdualvars = nbranchvars;
1529 
1530  return SCIP_OKAY;
1531 }
1532 
1533 /** store cuts that are active in the current LP */
1534 static
1536  SCIP_REOPT* reopt, /**< reoptimization data structure */
1537  SCIP_SET* set, /**< global SCIP settings */
1538  BMS_BLKMEM* blkmem, /**< block memory */
1539  SCIP_LP* lp, /**< current LP */
1540  unsigned int id /**< id in the reopttree */
1541  )
1542 {
1543  SCIP_ROW** lprows;
1544  int nlprows;
1545  int r;
1546 
1547  assert(reopt != NULL);
1548  assert(set != NULL);
1549  assert(lp != NULL);
1550  assert(blkmem != NULL);
1551 
1552  lprows = SCIPlpGetRows(lp);
1553  nlprows = SCIPlpGetNRows(lp);
1554 
1555  for( r = 0; r < nlprows; r++ )
1556  {
1557  /* we can break if we reach the first row that is not part of the current LP */
1558  if( SCIProwGetLPPos(lprows[r]) == -1 )
1559  break;
1560 
1561  /* currently we only want to store cuts generated by a seperator */
1562  if( SCIProwGetOrigintype(lprows[r]) == SCIP_ROWORIGINTYPE_SEPA && SCIProwGetAge(lprows[r]) <= set->reopt_maxcutage )
1563  {
1564  SCIP_VAR** cutvars;
1565  SCIP_COL** cols;
1566  SCIP_Real* cutvals;
1567  SCIP_Real lhs;
1568  SCIP_Real rhs;
1569  int ncutvars;
1570  int c;
1571  SCIP_Bool storecut;
1572 
1573  ncutvars = SCIProwGetNLPNonz(lprows[r]);
1574  lhs = SCIProwGetLhs(lprows[r]);
1575  rhs = SCIProwGetRhs(lprows[r]);
1576 
1577  /* subtract row constant */
1578  if( !SCIPsetIsInfinity(set, -lhs) )
1579  lhs -= SCIProwGetConstant(lprows[r]);
1580  if( !SCIPsetIsInfinity(set, rhs) )
1581  rhs -= SCIProwGetConstant(lprows[r]);
1582 
1583  cutvals = SCIProwGetVals(lprows[r]);
1584  cols = SCIProwGetCols(lprows[r]);
1585  storecut = TRUE;
1586 
1587  SCIP_CALL( SCIPsetAllocBufferArray(set, &cutvars, ncutvars) );
1588 
1589  for( c = 0; c < ncutvars; c++ )
1590  {
1591  SCIP_Real constant;
1592  SCIP_Real scalar;
1593 
1594  cutvars[c] = SCIPcolGetVar(cols[c]);
1595  assert(cutvars[c] != NULL);
1596 
1597  constant = 0.0;
1598  scalar = 1.0;
1599 
1600  SCIP_CALL( SCIPvarGetOrigvarSum(&cutvars[c], &scalar, &constant) );
1601 
1602  /* the cut contains an artificial variable that might not be present after modifying the problem */
1603  if( cutvars[c] != NULL )
1604  {
1605  storecut = FALSE;
1606  break;
1607  }
1608 
1609  assert(cutvars[c] != NULL);
1610  assert(!SCIPsetIsZero(set, scalar));
1611 
1612  /* subtract constant from sides */
1613  if( !SCIPsetIsZero(set, constant) && !SCIPsetIsInfinity(set, -lhs) )
1614  lhs -= constant;
1615  if( !SCIPsetIsZero(set, constant) && !SCIPsetIsInfinity(set, rhs) )
1616  rhs -= constant;
1617 
1618  cutvals[c] = cutvals[c]/scalar;
1619  }
1620 
1621  if( storecut )
1622  {
1623  /* add cut as a linear constraint */
1624  SCIP_CALL( SCIPreoptnodeAddCons(reopt->reopttree->reoptnodes[id], set, blkmem, cutvars, cutvals, NULL,
1625  lhs, rhs, ncutvars, REOPT_CONSTYPE_CUT, TRUE) );
1626  }
1627 
1628  SCIPsetFreeBufferArray(set, &cutvars);
1629  }
1630  }
1631 
1632  return SCIP_OKAY;
1633 }
1634 
1635 /** transform variable and bounds back to the original space */
1636 static
1638  SCIP_REOPT* reopt, /**< reoptimization data structure */
1639  unsigned int id /**< id of the node */
1640  )
1641 {
1642  int varnr;
1643 
1644  assert(reopt != NULL );
1645  assert(0 < id && id < reopt->reopttree->reoptnodessize);
1646  assert(reopt->reopttree->reoptnodes[id] != NULL );
1647 
1648  /* transform branching variables and bound changes applied before the first dual reduction */
1649  for( varnr = 0; varnr < reopt->reopttree->reoptnodes[id]->nvars; varnr++ )
1650  {
1651  SCIP_Real constant = 0.0;
1652  SCIP_Real scalar = 1.0;
1653 
1654  if( !SCIPvarIsOriginal(reopt->reopttree->reoptnodes[id]->vars[varnr]) )
1655  {
1656  SCIP_CALL( SCIPvarGetOrigvarSum(&reopt->reopttree->reoptnodes[id]->vars[varnr], &scalar, &constant)) ;
1657  reopt->reopttree->reoptnodes[id]->varbounds[varnr] = (reopt->reopttree->reoptnodes[id]->varbounds[varnr] - constant) / scalar;
1658  }
1659  assert(SCIPvarIsOriginal(reopt->reopttree->reoptnodes[id]->vars[varnr]));
1660  }
1661 
1662  /* transform bound changes affected by dual reduction */
1663  for( varnr = 0; varnr < reopt->reopttree->reoptnodes[id]->nafterdualvars; varnr++ )
1664  {
1665  SCIP_Real constant = 0.0;
1666  SCIP_Real scalar = 1.0;
1667 
1668  if( !SCIPvarIsOriginal(reopt->reopttree->reoptnodes[id]->afterdualvars[varnr]) )
1669  {
1670  SCIP_CALL( SCIPvarGetOrigvarSum(&reopt->reopttree->reoptnodes[id]->afterdualvars[varnr], &scalar, &constant)) ;
1671  reopt->reopttree->reoptnodes[id]->afterdualvarbounds[varnr]
1672  = (reopt->reopttree->reoptnodes[id]->afterdualvarbounds[varnr] - constant) / scalar;
1673  }
1674  assert(SCIPvarIsOriginal(reopt->reopttree->reoptnodes[id]->afterdualvars[varnr]));
1675  }
1676 
1677  return SCIP_OKAY;
1678 }
1679 
1680 /** search the next node along the root path that was saved by reoptimization */
1681 static
1683  SCIP_REOPT* reopt, /**< reoptimization data structure */
1684  SCIP_SET* set, /**< global SCIP settings */
1685  SCIP_NODE* node, /**< node of the search tree */
1686  SCIP_NODE** parent, /**< parent node within the search tree */
1687  unsigned int* parentid, /**< id of the parent node */
1688  int* nbndchgs /**< number of bound changes */
1689  )
1690 {
1691  assert(reopt != NULL);
1692  assert(reopt->reopttree != NULL);
1693  assert(reopt->reopttree->reoptnodes != NULL);
1694 
1695  (*nbndchgs) = 0;
1696  (*parent) = node;
1697 
1698  /* look for a saved parent along the root-path */
1699  while( SCIPnodeGetDepth(*parent) != 0 )
1700  {
1701  int nbranchings = 0;
1702  int nconsprop = 0;
1703 
1704  if( set->reopt_saveconsprop )
1705  SCIPnodeGetNDomchg((*parent), &nbranchings, &nconsprop, NULL);
1706  else
1707  SCIPnodeGetNDomchg((*parent), &nbranchings, NULL, NULL);
1708 
1709  (*nbndchgs) = (*nbndchgs) + nbranchings + nconsprop;
1710  (*parent) = SCIPnodeGetParent(*parent);
1711  (*parentid) = SCIPnodeGetReoptID(*parent);
1712 
1713  if( SCIPnodeGetDepth(*parent) == 0)
1714  {
1715  (*parentid) = 0;
1716  break;
1717  }
1718  else if( SCIPnodeGetReopttype((*parent)) >= SCIP_REOPTTYPE_TRANSIT )
1719  {
1720  /* this is a special case: due to re-propagation the node could be already deleted. We need to reset reoptid
1721  * and reopttype and continue upto we have found the last stored node
1722  */
1723  if( reopt->reopttree->reoptnodes[*parentid] == NULL )
1724  {
1725  SCIPnodeSetReoptID(*parent, 0);
1727  }
1728  else
1729  {
1730  assert(reopt->reopttree->reoptnodes[*parentid] != NULL);
1731  assert(SCIPnodeGetReoptID((*parent)) < reopt->reopttree->reoptnodessize);
1732  assert((*parentid) && (*parentid) < reopt->reopttree->reoptnodessize);
1733  break;
1734  }
1735  }
1736  }
1737 
1738  return SCIP_OKAY;
1739 }
1740 
1741 /** adds the id @p childid to the array of child nodes of @p parentid */
1742 static
1744  SCIP_REOPTTREE* reopttree, /**< reoptimization tree */
1745  SCIP_SET* set, /**< global SCIP settings */
1746  BMS_BLKMEM* blkmem, /**< block memory */
1747  unsigned int parentid, /**< id of the parent node */
1748  unsigned int childid /**< id of the child node */
1749  )
1750 {
1751  int nchilds;
1752 
1753  assert(reopttree != NULL);
1754  assert(blkmem != NULL);
1755  assert(parentid < (unsigned int)reopttree->reoptnodessize);
1756  assert(childid < (unsigned int)reopttree->reoptnodessize);
1757  assert(reopttree->reoptnodes[parentid] != NULL);
1758 
1759  nchilds = reopttree->reoptnodes[parentid]->nchilds;
1760 
1761  /* ensure that the array is large enough */
1762  SCIP_CALL( reoptnodeCheckMemory(reopttree->reoptnodes[parentid], set, blkmem, 0, nchilds+1, 0) );
1763  assert(reopttree->reoptnodes[parentid]->allocchildmem > nchilds);
1764 
1765  /* add the child */
1766  reopttree->reoptnodes[parentid]->childids[nchilds] = childid;
1767  ++reopttree->reoptnodes[parentid]->nchilds;
1768 
1769  SCIPsetDebugMsg(set, "add ID %u as a child of ID %u.\n", childid, parentid);
1770 
1771  return SCIP_OKAY;
1772 }
1773 
1774 /** move all children to the next node (along the root path) stored in the reoptimization tree */
1775 static
1777  SCIP_REOPT* reopt, /**< reoptimization data structure */
1778  SCIP_SET* set, /**< global SCIP settings */
1779  BMS_BLKMEM* blkmem, /**< block memory */
1780  unsigned int nodeid, /**< id of the node */
1781  unsigned int parentid /**< id of the parent node */
1782  )
1783 {
1784  unsigned int childid;
1785  int varnr;
1786  int nvars;
1787 
1788  assert(reopt != NULL);
1789  assert(blkmem != NULL);
1790  assert(0 < nodeid && nodeid < reopt->reopttree->reoptnodessize);
1791  assert(parentid < reopt->reopttree->reoptnodessize);
1792  assert(reopt->reopttree->reoptnodes[nodeid]->childids != NULL);
1793 
1794  /* ensure that enough memory at the parentID is available */
1795  SCIP_CALL( reoptnodeCheckMemory(reopt->reopttree->reoptnodes[parentid], set, blkmem, 0,
1796  reopt->reopttree->reoptnodes[parentid]->nchilds + reopt->reopttree->reoptnodes[nodeid]->nchilds, 0) );
1797 
1798  while( reopt->reopttree->reoptnodes[nodeid]->nchilds > 0 )
1799  {
1800  int nchilds;
1801 
1802  nchilds = reopt->reopttree->reoptnodes[nodeid]->nchilds;
1803  childid = reopt->reopttree->reoptnodes[nodeid]->childids[nchilds-1];
1804  assert(0 < childid && childid < reopt->reopttree->reoptnodessize);
1805 
1806  /* check the memory */
1807  SCIP_CALL( reoptnodeCheckMemory(reopt->reopttree->reoptnodes[childid], set, blkmem,
1808  reopt->reopttree->reoptnodes[childid]->nvars + reopt->reopttree->reoptnodes[nodeid]->nvars, 0, 0) );
1809  assert(reopt->reopttree->reoptnodes[childid]->varssize >= reopt->reopttree->reoptnodes[childid]->nvars
1810  + reopt->reopttree->reoptnodes[nodeid]->nvars);
1811 
1812  /* save branching information */
1813  for( varnr = 0; varnr < reopt->reopttree->reoptnodes[nodeid]->nvars; varnr++ )
1814  {
1815  nvars = reopt->reopttree->reoptnodes[childid]->nvars;
1816  reopt->reopttree->reoptnodes[childid]->vars[nvars] = reopt->reopttree->reoptnodes[nodeid]->vars[varnr];
1817  reopt->reopttree->reoptnodes[childid]->varbounds[nvars] = reopt->reopttree->reoptnodes[nodeid]->varbounds[varnr];
1818  reopt->reopttree->reoptnodes[childid]->varboundtypes[nvars] = reopt->reopttree->reoptnodes[nodeid]->varboundtypes[varnr];
1819  ++reopt->reopttree->reoptnodes[childid]->nvars;
1820  }
1821 
1822  /* update the ID of the parent node */
1823  reopt->reopttree->reoptnodes[childid]->parentID = parentid;
1824 
1825  /* insert the node as a child */
1826  SCIP_CALL( reoptAddChild(reopt->reopttree, set, blkmem, parentid, childid) );
1827 
1828  /* reduce the number of child nodes by 1 */
1829  --reopt->reopttree->reoptnodes[nodeid]->nchilds;
1830  }
1831 
1832  return SCIP_OKAY;
1833 }
1834 
1835 /** delete all nodes in the subtree induced by nodeID */
1836 static
1838  SCIP_REOPTTREE* reopttree, /**< reoptimization tree */
1839  SCIP_SET* set, /**< global SCIP settings */
1840  BMS_BLKMEM* blkmem, /**< block memory */
1841  unsigned int id, /**< id of the node */
1842  SCIP_Bool delnodeitself, /**< should the node be deleted after deleting the induced subtree? */
1843  SCIP_Bool exitsolve /**< will the solving process end after deletion */
1844  )
1845 {
1846  assert(reopttree != NULL );
1847  assert(blkmem != NULL);
1848  assert(id < reopttree->reoptnodessize);
1849  assert(reopttree->reoptnodes[id] != NULL);
1850 
1851  /* delete all children below */
1852  if( reopttree->reoptnodes[id]->childids != NULL && reopttree->reoptnodes[id]->nchilds > 0 )
1853  {
1854  SCIPsetDebugMsg(set, "-> delete subtree induced by ID %u (hard remove = %u)\n", id, exitsolve);
1855 
1856  while( reopttree->reoptnodes[id]->nchilds > 0 )
1857  {
1858  int nchilds;
1859  unsigned int childid;
1860 
1861  nchilds = reopttree->reoptnodes[id]->nchilds;
1862  childid = reopttree->reoptnodes[id]->childids[nchilds-1];
1863  assert(0 < childid && childid < reopttree->reoptnodessize);
1864 
1865  SCIP_CALL( deleteChildrenBelow(reopttree, set, blkmem, childid, TRUE, exitsolve) );
1866 
1867  --reopttree->reoptnodes[id]->nchilds;
1868  }
1869  }
1870 
1871  /* delete node data*/
1872  if( delnodeitself )
1873  {
1874  SCIP_CALL( reopttreeDeleteNode(reopttree, set, blkmem, id, exitsolve) );
1875  SCIP_CALL( SCIPqueueInsertUInt(reopttree->openids, id) );
1876  }
1877 
1878  return SCIP_OKAY;
1879 }
1880 
1881 /** replaces a reoptimization nodes by its stored child nodes */
1882 static
1884  SCIP_REOPT* reopt, /**< reoptimization data structure */
1885  SCIP_SET* set, /**< global SCIP settings */
1886  SCIP_NODE* node, /**< node of the search tree */
1887  unsigned int id, /**< id of the node */
1888  SCIP_Bool* shrank, /**< pointer to store if the node was shrank */
1889  BMS_BLKMEM* blkmem /**< block memory */
1890  )
1891 {
1892  SCIP_REOPTNODE** reoptnodes;
1893 
1894  assert(reopt != NULL);
1895  assert(node != NULL);
1896  assert(id < reopt->reopttree->reoptnodessize);
1897 
1898  reoptnodes = reopt->reopttree->reoptnodes;
1899  assert(reoptnodes != NULL);
1900  assert(reoptnodes[id] != NULL);
1901 
1902  if( reoptnodes[id]->childids != NULL && reoptnodes[id]->nchilds > 0 )
1903  {
1904  int ndomchgs = 0;
1905  unsigned int parentid = 0;
1906  SCIP_NODE* parent = NULL;
1907 
1908  SCIP_CALL( getLastSavedNode(reopt, set, node, &parent, &parentid, &ndomchgs) );
1909 
1910  assert(parentid != id);
1911  assert(reoptnodes[parentid] != NULL );
1912  assert(reoptnodes[parentid]->childids != NULL && reoptnodes[parentid]->nchilds);
1913 
1914  /* check if we want move all children to the next saved node above
1915  * we want to shrink the path if either
1916  * - the maximal number of bound changes fix and the number of bound changes is
1917  * less than the given threshold set->reopt_maxdiffofnodes
1918  * or
1919  * - the number is calculated dynamically and the number of bound changes
1920  * is less than log2(SCIPgetNBinVars - (#vars of parent))
1921  * */
1922  if( ndomchgs <= set->reopt_maxdiffofnodes )
1923  {
1924  int c;
1925 
1926  SCIPsetDebugMsg(set, " -> shrink node %lld at ID %u, replaced by %d child nodes.\n", SCIPnodeGetNumber(node),
1927  id, reoptnodes[id]->nchilds);
1928 
1929  /* copy the references of child nodes to the parent*/
1930  SCIP_CALL( moveChildrenUp(reopt, set, blkmem, id, parentid) );
1931 
1932  /* delete the current node */
1933  c = 0;
1934  while( reoptnodes[parentid]->childids[c] != id )
1935  {
1936  ++c;
1937  assert(c < reoptnodes[parentid]->nchilds);
1938  }
1939 
1940  assert(reoptnodes[parentid]->childids[c] == id);
1941 
1942  /* replace the childid at position c by the last one */
1943  reoptnodes[parentid]->childids[c] = reoptnodes[parentid]->childids[reoptnodes[parentid]->nchilds-1];
1944  --reoptnodes[parentid]->nchilds;
1945 
1946  SCIP_CALL( reopttreeDeleteNode(reopt->reopttree, set, blkmem, id, TRUE) );
1948 
1949  *shrank = TRUE;
1950 
1951  /* set the reopttype to none */
1953  }
1954  }
1955 
1956  return SCIP_OKAY;
1957 }
1958 
1959 /** change all reopttypes in the subtree induced by @p nodeID */
1960 static
1962  SCIP_REOPTTREE* reopttree, /**< reopttree */
1963  unsigned int id, /**< id of the node */
1964  SCIP_REOPTTYPE reopttype /**< reopttype */
1965  )
1966 {
1967  assert(reopttree != NULL);
1968  assert(id < reopttree->reoptnodessize);
1969  assert(reopttree->reoptnodes[id] != NULL);
1970 
1971  if( reopttree->reoptnodes[id]->childids != NULL && reopttree->reoptnodes[id]->nchilds > 0 )
1972  {
1973  unsigned int childid;
1974  int nchildids;
1975  int seenids = 0;
1976 
1977  nchildids = reopttree->reoptnodes[id]->nchilds;
1978 
1979  while( seenids < nchildids )
1980  {
1981  /* get childID */
1982  childid = reopttree->reoptnodes[id]->childids[seenids];
1983  assert(childid < reopttree->reoptnodessize);
1984  assert(reopttree->reoptnodes[childid] != NULL);
1985 
1986  /* change the reopttype of the node iff the node is neither infeasible nor induces an
1987  * infeasible subtree and if the node contains no bound changes based on dual decisions
1988  */
1989  if( reopttree->reoptnodes[childid]->reopttype != SCIP_REOPTTYPE_STRBRANCHED
1990  && reopttree->reoptnodes[childid]->reopttype != SCIP_REOPTTYPE_INFSUBTREE ) /*lint !e641*/
1991  reopttree->reoptnodes[childid]->reopttype = reopttype; /*lint !e641*/
1992 
1993  /* change reopttype of subtree */
1994  SCIP_CALL( changeReopttypeOfSubtree(reopttree, childid, reopttype) );
1995 
1996  ++seenids;
1997  }
1998  }
1999 
2000  return SCIP_OKAY;
2001 }
2002 
2003 /** delete the constraint handling dual information for the current iteration and replace it with the dual constraint
2004  * for the next iteration
2005  */
2006 static
2008  SCIP_REOPTNODE* reoptnode, /**< reoptimization node */
2009  BMS_BLKMEM* blkmem /**< block memory */
2010  )
2011 {
2012  assert(reoptnode != NULL);
2013  assert(blkmem != NULL);
2014 
2015  if( reoptnode->dualredscur != NULL )
2016  {
2017  SCIPdebugMessage("reset dual information (current run)\n");
2018 
2019  BMSfreeBlockMemoryArray(blkmem, &reoptnode->dualredscur->boundtypes, reoptnode->dualredscur->varssize);
2020  BMSfreeBlockMemoryArray(blkmem, &reoptnode->dualredscur->vals, reoptnode->dualredscur->varssize);
2021  BMSfreeBlockMemoryArray(blkmem, &reoptnode->dualredscur->vars, reoptnode->dualredscur->varssize);
2022  BMSfreeBlockMemory(blkmem, &reoptnode->dualredscur);
2023  reoptnode->dualredscur = NULL;
2024  }
2025 
2026  if( reoptnode->dualredsnex != NULL )
2027  {
2028  SCIPdebugMessage("set dual information of next run to current run\n");
2029  reoptnode->dualredscur = reoptnode->dualredsnex;
2030  reoptnode->dualredsnex = NULL;
2031  }
2032 
2033  reoptnode->dualreds = (reoptnode->dualredscur != NULL ? TRUE : FALSE);
2034 
2035  return SCIP_OKAY;
2036 }
2037 
2038 /** calculates a (local) similarity of a given node and returns if the subproblem should be solved from scratch */
2039 static
2041  SCIP_REOPT* reopt, /**< reoptimization data structure */
2042  SCIP_SET* set, /**< global SCIP settings */
2043  BMS_BLKMEM* blkmem, /**< block memory */
2044  SCIP_NODE* node, /**< node of the search tree */
2045  SCIP_VAR** transvars, /**< transformed variables */
2046  int ntransvars, /**< number of transformed variables */
2047  SCIP_Bool* localrestart /**< pointer to store if we want to restart solving the (sub)problem */
2048  )
2049 {
2050  unsigned int id;
2051 
2052  assert(reopt != NULL);
2053  assert(reopt->reopttree != NULL);
2054  assert(set != NULL);
2055  assert(blkmem != NULL);
2056  assert(node != NULL);
2057  assert(transvars != NULL);
2058 
2059  /* node == NULL is equivalent to node == root, this case should be handled by SCIPreoptCheckReopt */
2060  assert(node != NULL);
2061 
2062  *localrestart = FALSE;
2063 
2064  id = SCIPnodeGetReoptID(node);
2065  assert(id < reopt->reopttree->reoptnodessize);
2066 
2067  /* set the id to -1 if the node is not part of the reoptimization tree */
2068  if( SCIPnodeGetDepth(node) > 0 && id == 0 )
2069  return SCIP_OKAY;
2070 
2071  if( set->reopt_objsimdelay > -1 )
2072  {
2073  SCIP_Real sim = 0.0;
2074  SCIP_Real lb;
2075  SCIP_Real ub;
2076  SCIP_Real oldcoef;
2077  SCIP_Real newcoef;
2078  int v;
2079  int idx;
2080 
2081  if( id == 0 )
2082  reopt->nlocrestarts = 0;
2083 
2084  /* since the stored objective functions are already normalize the dot-product is equivalent to the similarity */
2085  for( v = 0; v < ntransvars; v++ )
2086  {
2087  lb = SCIPvarGetLbLocal(transvars[v]);
2088  ub = SCIPvarGetUbLocal(transvars[v]);
2089 
2090  /* skip already fixed variables */
2091  if( SCIPsetIsFeasLT(set, lb, ub) )
2092  {
2093  idx = SCIPvarGetProbindex(transvars[v]);
2094  assert(0 <= idx && idx < ntransvars);
2095 
2096  oldcoef = SCIPreoptGetOldObjCoef(reopt, reopt->run-1, idx);
2097  newcoef = SCIPreoptGetOldObjCoef(reopt, reopt->run, idx);
2098 
2099  sim += (oldcoef * newcoef);
2100  }
2101  }
2102 
2103  /* delete the stored subtree and information about bound changes
2104  * based on dual information */
2105  if( SCIPsetIsLT(set, sim, set->reopt_objsimdelay) )
2106  {
2107  /* set the flag */
2108  *localrestart = TRUE;
2109 
2110  ++reopt->nlocrestarts;
2111  ++reopt->ntotallocrestarts;
2112 
2113  /* delete the stored subtree */
2114  SCIP_CALL( deleteChildrenBelow(reopt->reopttree, set, blkmem, id, FALSE, FALSE) );
2115 
2116  /* delete the stored constraints; we do this twice in a row because we want to delete both constraints */
2117  SCIP_CALL( reoptnodeUpdateDualConss(reopt->reopttree->reoptnodes[id], blkmem) );
2118  SCIP_CALL( reoptnodeUpdateDualConss(reopt->reopttree->reoptnodes[id], blkmem) );
2119  }
2120 
2121  SCIPsetDebugMsg(set, " -> local similarity: %.4f%s\n", sim, *localrestart ? " (solve subproblem from scratch)" : "");
2122  }
2123 
2124  return SCIP_OKAY;
2125 }
2126 
2127 /** save ancestor branching information up to the next stored node */
2128 static
2130  SCIP_REOPTTREE* reopttree, /**< reoptimization tree */
2131  SCIP_SET* set, /**< global SCIP settings */
2132  BMS_BLKMEM* blkmem, /**< block memory */
2133  SCIP_NODE* node, /**< node of the branch and bound tree */
2134  SCIP_NODE* parent, /**< parent node */
2135  unsigned int id, /**< id of the node */
2136  unsigned int parentid /**< id of the parent node */
2137  )
2138 {
2139  int nbranchvars;
2140 
2141  assert(reopttree != NULL );
2142  assert(node != NULL );
2143  assert(parent != NULL );
2144  assert(1 <= id && id < reopttree->reoptnodessize);
2145  assert(reopttree->reoptnodes[id] != NULL );
2146  assert(parentid < reopttree->reoptnodessize);
2147  assert(parentid == 0 || reopttree->reoptnodes[parentid] != NULL ); /* if the root is the next saved node, the nodedata can be NULL */
2148 
2149  SCIPsetDebugMsg(set, " -> save ancestor branchings\n");
2150 
2151  /* allocate memory */
2152  if (reopttree->reoptnodes[id]->varssize == 0)
2153  {
2154  assert(reopttree->reoptnodes[id]->vars == NULL );
2155  assert(reopttree->reoptnodes[id]->varbounds == NULL );
2156  assert(reopttree->reoptnodes[id]->varboundtypes == NULL );
2157 
2158  /* allocate memory for node information */
2159  SCIP_CALL( reoptnodeCheckMemory(reopttree->reoptnodes[id], set, blkmem, DEFAULT_MEM_VAR, 0, 0) );
2160  }
2161 
2162  assert(reopttree->reoptnodes[id]->varssize > 0);
2163  assert(reopttree->reoptnodes[id]->nvars == 0);
2164 
2165  SCIPnodeGetAncestorBranchingsPart(node, parent,
2166  reopttree->reoptnodes[id]->vars,
2167  reopttree->reoptnodes[id]->varbounds,
2168  reopttree->reoptnodes[id]->varboundtypes,
2169  &nbranchvars,
2170  reopttree->reoptnodes[id]->varssize);
2171 
2172  if( nbranchvars > reopttree->reoptnodes[id]->varssize )
2173  {
2174  /* reallocate memory */
2175  SCIP_CALL( reoptnodeCheckMemory(reopttree->reoptnodes[id], set, blkmem, nbranchvars, 0, 0) );
2176 
2177  SCIPnodeGetAncestorBranchingsPart(node, parent,
2178  reopttree->reoptnodes[id]->vars,
2179  reopttree->reoptnodes[id]->varbounds,
2180  reopttree->reoptnodes[id]->varboundtypes,
2181  &nbranchvars,
2182  reopttree->reoptnodes[id]->varssize);
2183  }
2184 
2185  assert(nbranchvars <= reopttree->reoptnodes[id]->varssize); /* this should be the case */
2186 
2187  reopttree->reoptnodes[id]->nvars = nbranchvars;
2188 
2189  assert(nbranchvars <= reopttree->reoptnodes[id]->varssize);
2190  assert(reopttree->reoptnodes[id]->vars != NULL );
2191 
2192  return SCIP_OKAY;
2193 }
2194 
2195 
2196 /** transform a constraint with linear representation into reoptimization constraint data */
2197 static
2199  SCIP_REOPTCONSDATA* reoptconsdata, /**< reoptimization constraint data */
2200  SCIP_SET* set, /**< global SCIP settings */
2201  BMS_BLKMEM* blkmem, /**< block memory */
2202  SCIP_CONS* cons, /**< linear constraint that should be stored */
2203  SCIP_Bool* success /**< pointer to store the success */
2204  )
2205 {
2206  SCIP_VAR** vars;
2207  SCIP_Real* vals;
2208  SCIP_CONSHDLR* conshdlr;
2209  SCIP_Bool allocbuffervals;
2210  int v;
2211 
2212  assert(reoptconsdata != NULL);
2213  assert(cons != NULL);
2214 
2215  *success = FALSE;
2216  allocbuffervals = FALSE;
2217  reoptconsdata->linear = TRUE;
2218 
2219  vars = NULL;
2220  vals = NULL;
2221  SCIP_CALL( SCIPconsGetNVars(cons, set, &reoptconsdata->nvars, success) );
2222  assert(*success);
2223 
2224  /* allocate memory for variables and values; boundtypes are not needed */
2225  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reoptconsdata->vars, reoptconsdata->nvars) );
2226  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reoptconsdata->vals, reoptconsdata->nvars) );
2227  reoptconsdata->varssize = reoptconsdata->nvars;
2228 
2229  /* only needed for bounddisjuction constraints, thus we set them to NULL to avoid compiler warnings */
2230  reoptconsdata->boundtypes = NULL;
2231 
2232  conshdlr = SCIPconsGetHdlr(cons);
2233  assert(conshdlr != NULL);
2234 
2235  /* get all variables, values, and sides */
2236  if( strcmp(SCIPconshdlrGetName(conshdlr), "linear") == 0 )
2237  {
2238  vars = SCIPgetVarsLinear(set->scip, cons);
2239  vals = SCIPgetValsLinear(set->scip, cons);
2240  reoptconsdata->lhs = SCIPgetLhsLinear(set->scip, cons);
2241  reoptconsdata->rhs = SCIPgetRhsLinear(set->scip, cons);
2242  }
2243  else if( strcmp(SCIPconshdlrGetName(conshdlr), "logicor") == 0 )
2244  {
2245  vars = SCIPgetVarsLogicor(set->scip, cons);
2246 
2247  /* initialize values to 1.0 */
2248  SCIP_CALL( SCIPsetAllocBufferArray(set, &vals, reoptconsdata->nvars) );
2249  allocbuffervals = TRUE;
2250 
2251  for( v = 0; v < reoptconsdata->nvars; v++ )
2252  vals[v] = 1.0;
2253 
2254  reoptconsdata->lhs = 1.0;
2255  reoptconsdata->rhs = SCIPsetInfinity(set);
2256  }
2257  else if( strcmp(SCIPconshdlrGetName(conshdlr), "setppc") == 0 )
2258  {
2259  vars = SCIPgetVarsSetppc(set->scip, cons);
2260 
2261  /* initialize values to 1.0 */
2262  SCIP_CALL( SCIPsetAllocBufferArray(set, &vals, reoptconsdata->nvars) );
2263  allocbuffervals = TRUE;
2264 
2265  for( v = 0; v < reoptconsdata->nvars; v++ )
2266  vals[v] = 1.0;
2267 
2268  switch( SCIPgetTypeSetppc(set->scip, cons) ) {
2270  reoptconsdata->lhs = 1.0;
2271  reoptconsdata->rhs = 1.0;
2272  break;
2274  reoptconsdata->lhs = -SCIPsetInfinity(set);
2275  reoptconsdata->rhs = 1.0;
2276  break;
2278  reoptconsdata->lhs = 1.0;
2279  reoptconsdata->rhs = SCIPsetInfinity(set);
2280  break;
2281  default:
2282  *success = FALSE;
2283  return SCIP_OKAY;
2284  }
2285  }
2286  else
2287  {
2288  assert(strcmp(SCIPconshdlrGetName(conshdlr), "linear") == 0 || strcmp(SCIPconshdlrGetName(conshdlr), "logicor") == 0
2289  || strcmp(SCIPconshdlrGetName(conshdlr), "setppc") == 0);
2290 
2291  SCIPerrorMessage("Cannot handle constraints of type <%s> in saveConsLinear.\n", SCIPconshdlrGetName(conshdlr));
2292  return SCIP_INVALIDDATA;
2293  }
2294  assert(vars != NULL);
2295  assert(vals != NULL);
2296 
2297  /* transform all variables into the original space */
2298  for( v = 0; v < reoptconsdata->nvars; v++ )
2299  {
2300  SCIP_Real constant = 0.0;
2301  SCIP_Real scalar = 1.0;
2302 
2303  assert(vars[v] != NULL);
2304 
2305  reoptconsdata->vars[v] = vars[v];
2306  reoptconsdata->vals[v] = vals[v];
2307 
2308  SCIP_CALL( SCIPvarGetOrigvarSum(&reoptconsdata->vars[v], &scalar, &constant) );
2309  assert(!SCIPsetIsZero(set, scalar));
2310 
2311  assert(!SCIPsetIsInfinity(set, REALABS(reoptconsdata->vals[v])));
2312  reoptconsdata->vals[v] *= scalar;
2313 
2314  if( !SCIPsetIsZero(set, constant) && !SCIPsetIsInfinity(set, -reoptconsdata->lhs) )
2315  reoptconsdata->lhs -= constant;
2316  if( !SCIPsetIsZero(set, constant) && !SCIPsetIsInfinity(set, reoptconsdata->rhs) )
2317  reoptconsdata->rhs -= constant;
2318  }
2319 
2320  /* free buffer if needed */
2321  if( allocbuffervals )
2322  {
2323  SCIPsetFreeBufferArray(set, &vals);
2324  }
2325 
2326  return SCIP_OKAY;
2327 }
2328 
2329 /** transform a bounddisjunction constraint into reoptimization constraint data */
2330 static
2332  SCIP_REOPTCONSDATA* reoptconsdata, /**< reoptimization constraint data */
2333  SCIP_SET* set, /**< global SCIP settings */
2334  BMS_BLKMEM* blkmem, /**< block memory */
2335  SCIP_CONS* cons, /**< bounddisjuction constraint that should be stored */
2336  SCIP_Bool* success /**< pointer to store the success */
2337  )
2338 {
2339  SCIP_VAR** vars;
2340  SCIP_CONSHDLR* conshdlr;
2341  SCIP_BOUNDTYPE* boundtypes;
2342  SCIP_Real* bounds;
2343  int v;
2344 
2345  assert(reoptconsdata != NULL);
2346  assert(cons != NULL);
2347 
2348  *success = FALSE;
2349  reoptconsdata->linear = FALSE;
2350 
2351  conshdlr = SCIPconsGetHdlr(cons);
2352  assert(conshdlr != NULL);
2353  assert(strcmp(SCIPconshdlrGetName(conshdlr), "bounddisjunction") == 0);
2354 
2355  if( strcmp(SCIPconshdlrGetName(conshdlr), "bounddisjunction") != 0 )
2356  {
2357  SCIPerrorMessage("Cannot handle constraints of type <%s> in saveConsBounddisjuction.\n",
2358  SCIPconshdlrGetName(conshdlr));
2359  return SCIP_INVALIDDATA;
2360  }
2361 
2362  SCIP_CALL( SCIPconsGetNVars(cons, set, &reoptconsdata->nvars, success) );
2363  assert(*success);
2364 
2365  /* allocate memory for variables and values; boundtypes are not needed */
2366  vars = SCIPgetVarsBounddisjunction(NULL, cons);
2367  bounds = SCIPgetBoundsBounddisjunction(NULL, cons);
2368  boundtypes = SCIPgetBoundtypesBounddisjunction(NULL, cons);
2369  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &reoptconsdata->vars, vars, reoptconsdata->nvars) );
2370  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &reoptconsdata->vals, bounds, reoptconsdata->nvars) );
2371  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &reoptconsdata->boundtypes, boundtypes, reoptconsdata->nvars) );
2372  reoptconsdata->varssize = reoptconsdata->nvars;
2373  reoptconsdata->lhs = SCIP_UNKNOWN;
2374  reoptconsdata->rhs = SCIP_UNKNOWN;
2375 
2376  /* transform all variables into the original space */
2377  for( v = 0; v < reoptconsdata->nvars; v++ )
2378  {
2379  SCIP_Real constant = 0.0;
2380  SCIP_Real scalar = 1.0;
2381 
2382  assert(reoptconsdata->vars[v] != NULL);
2383 
2384  SCIP_CALL( SCIPvarGetOrigvarSum(&reoptconsdata->vars[v], &scalar, &constant) );
2385  assert(!SCIPsetIsZero(set, scalar));
2386 
2387  assert(!SCIPsetIsInfinity(set, REALABS(reoptconsdata->vals[v])));
2388  reoptconsdata->vals[v] -= constant;
2389  reoptconsdata->vals[v] *= scalar;
2390 
2391  /* due to multipling with a negative scalar the relation need to be changed */
2392  if( SCIPsetIsNegative(set, scalar) )
2393  reoptconsdata->boundtypes[v] = (SCIP_BOUNDTYPE)(SCIP_BOUNDTYPE_UPPER - reoptconsdata->boundtypes[v]); /*lint !e656*/
2394  }
2395 
2396  return SCIP_OKAY;
2397 }
2398 
2399 /** save additional all constraints that were additionally added to @p node */
2400 static
2402  SCIP_REOPTTREE* reopttree, /**< reopttree */
2403  SCIP_SET* set, /**< global SCIP settings */
2404  BMS_BLKMEM* blkmem, /**< block memory */
2405  SCIP_NODE* node, /**< node of the branch and bound tree */
2406  unsigned int id /**< id of the node*/
2407  )
2408 {
2409  SCIP_CONS** addedcons;
2410  int naddedconss;
2411  int addedconsssize;
2412  int nconss;
2413  int c;
2414 
2415  assert(node != NULL );
2416  assert(reopttree != NULL);
2417  assert(id < reopttree->reoptnodessize);
2418 
2419  /* save the added pseudo-constraint */
2420  if( SCIPnodeGetNAddedConss(node) > 0 )
2421  {
2422  addedconsssize = SCIPnodeGetNAddedConss(node);
2423 
2424  SCIPsetDebugMsg(set, " -> save %d locally added constraints\n", addedconsssize);
2425 
2426  /* get memory */
2427  SCIP_CALL( SCIPsetAllocBufferArray(set, &addedcons, addedconsssize) );
2428  SCIPnodeGetAddedConss(node, addedcons, &naddedconss, addedconsssize);
2429 
2430  nconss = reopttree->reoptnodes[id]->nconss;
2431 
2432  /* check memory for added constraints */
2433  SCIP_CALL( reoptnodeCheckMemory(reopttree->reoptnodes[id], set, blkmem, 0, 0, naddedconss) );
2434 
2435  /* since the first nconss are already stored in the data structure, we skip them */
2436  for( c = nconss; c < naddedconss; c++ )
2437  {
2438  SCIP_CONSHDLR* conshdlr;
2439  SCIP_Bool islinear;
2440  SCIP_Bool success;
2441 
2442  conshdlr = SCIPconsGetHdlr(addedcons[c]);
2443 
2444  /* check whether the constraint has a linear representation */
2445  islinear = (strcmp(SCIPconshdlrGetName(conshdlr), "linear") == 0
2446  || strcmp(SCIPconshdlrGetName(conshdlr), "logicor") == 0
2447  || strcmp(SCIPconshdlrGetName(conshdlr), "setppc") == 0);
2448 
2449  SCIP_ALLOC( BMSallocBlockMemory(blkmem, &reopttree->reoptnodes[id]->conss[c]) ); /*lint !e866*/
2450 
2451  success = FALSE;
2452 
2453  /* the constraint has a linear representation */
2454  if( islinear )
2455  {
2456  SCIP_CALL( saveConsLinear(reopttree->reoptnodes[id]->conss[c], set, blkmem, addedcons[c], &success) );
2457  assert(success);
2458 
2459  /* increase the counter for added constraints */
2460  ++reopttree->reoptnodes[id]->nconss;
2461  }
2462  else
2463  {
2464  assert(strcmp(SCIPconshdlrGetName(conshdlr), "bounddisjunction") == 0);
2465  SCIP_CALL( saveConsBounddisjuction(reopttree->reoptnodes[id]->conss[c], set, blkmem, addedcons[c], &success) );
2466  assert(success);
2467 
2468  /* increase the counter for added constraints */
2469  ++reopttree->reoptnodes[id]->nconss;
2470  }
2471  assert(reopttree->reoptnodes[id]->conss[c]->nvars > 0);
2472 
2473  if( strcmp("reopt_inf", SCIPconsGetName(addedcons[c])) == 0 )
2474  reopttree->reoptnodes[id]->conss[c]->constype = REOPT_CONSTYPE_INFSUBTREE;
2475  else if( strcmp("reopt_dual", SCIPconsGetName(addedcons[c])) == 0 )
2476  reopttree->reoptnodes[id]->conss[c]->constype = REOPT_CONSTYPE_DUALREDS;
2477  else
2478  reopttree->reoptnodes[id]->conss[c]->constype = REOPT_CONSTYPE_UNKNOWN;
2479  }
2480 
2481  assert(reopttree->reoptnodes[id]->nconss == naddedconss);
2482  SCIPsetFreeBufferArray(set, &addedcons);
2483  }
2484 
2485  return SCIP_OKAY;
2486 }
2487 
2488 /** collect all bound changes based on dual information
2489  *
2490  * If the bound changes are global, all information are already stored because they were caught by the event handler.
2491  * otherwise, we have to use SCIPnodeGetDualBoundchgs.
2492  *
2493  * Afterwards, we check if the constraint will be added in the next iteration or after splitting the node.
2494  */
2495 static
2497  SCIP_REOPT* reopt, /**< reoptimization data structure */
2498  SCIP_SET* set, /**< global SCIP settings */
2499  BMS_BLKMEM* blkmem, /**< block memory */
2500  SCIP_NODE* node, /**< node of the search tree */
2501  unsigned int id, /**< id of the node */
2502  SCIP_REOPTTYPE reopttype /**< reopttype */
2503  )
2504 {
2505  SCIP_Bool cons_is_next = TRUE;
2506  int nbndchgs;
2507  int v;
2508 
2509  assert(reopt != NULL);
2510  assert(reopt->reopttree != NULL);
2511  assert(id < reopt->reopttree->reoptnodessize);
2512  assert(reopt->reopttree->reoptnodes[id]->dualreds);
2513  assert(node != NULL);
2514  assert(blkmem != NULL);
2515 
2516  /* first case, all bound changes were global */
2517  if( reopt->currentnode == SCIPnodeGetNumber(node) && reopt->dualreds != NULL && reopt->dualreds->nvars > 0 )
2518  {
2519  nbndchgs = reopt->dualreds->nvars;
2520  }
2521  else
2522  {
2523  assert(reopt->currentnode == SCIPnodeGetNumber(node));
2524 
2525  /* get the number of bound changes based on dual information */
2526  nbndchgs = SCIPnodeGetNDualBndchgs(node);
2527 
2528  /* ensure that enough memory is allocated */
2529  SCIP_CALL( checkMemDualCons(reopt, set, blkmem, nbndchgs) );
2530 
2531  /* collect the bound changes */
2532  SCIPnodeGetDualBoundchgs(node, reopt->dualreds->vars, reopt->dualreds->vals, reopt->dualreds->boundtypes,
2533  &nbndchgs, reopt->dualreds->varssize);
2534  assert(nbndchgs <= reopt->dualreds->varssize);
2535 
2536  reopt->dualreds->nvars = nbndchgs;
2537  reopt->dualreds->linear = FALSE;
2538 
2539  /* transform the variables into the original space */
2540  for( v = 0; v < nbndchgs; v++ )
2541  {
2542  SCIP_Real constant = 0.0;
2543  SCIP_Real scalar = 1.0;
2544 
2545  SCIP_CALL( SCIPvarGetOrigvarSum(&reopt->dualreds->vars[v], &scalar, &constant) );
2546  reopt->dualreds->vals[v] = (reopt->dualreds->vals[v] - constant) / scalar;
2547 
2548  assert(SCIPvarIsOriginal(reopt->dualreds->vars[v]));
2549  }
2550  }
2551 
2552  assert(nbndchgs > 0);
2553 
2554  /* due to the strong branching initialization it can be possible that two
2555  * constraints handling dual information are stored at the same time.
2556  * During reoptimizing a node we add the constraint stored at dualredscur only,
2557  * i.e, if dualredscur is not NULL, we need to store the constraint for the next
2558  * iteration at dualredsnex because the constraint stored at dualredscur is needed
2559  * to split the constraint in the current iteration.
2560  */
2561  if( reopt->reopttree->reoptnodes[id]->dualredscur != NULL )
2562  {
2563  assert(reopt->reopttree->reoptnodes[id]->dualredsnex == NULL);
2564  cons_is_next = FALSE;
2565  }
2566  assert((cons_is_next && reopt->reopttree->reoptnodes[id]->dualredscur == NULL)
2567  || (!cons_is_next && reopt->reopttree->reoptnodes[id]->dualredsnex == NULL));
2568 
2569  /* the constraint will be added next */
2570  if( cons_is_next )
2571  {
2572  assert(reopt->reopttree->reoptnodes[id]->dualredscur == NULL);
2575  reopt->dualreds->vars, nbndchgs) );
2577  reopt->dualreds->vals, nbndchgs) );
2578  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &reopt->reopttree->reoptnodes[id]->dualredscur->boundtypes, \
2579  reopt->dualreds->boundtypes, nbndchgs) );
2580 
2581  reopt->reopttree->reoptnodes[id]->dualredscur->nvars = nbndchgs;
2582  reopt->reopttree->reoptnodes[id]->dualredscur->varssize = nbndchgs;
2583  reopt->reopttree->reoptnodes[id]->dualredscur->lhs = 1.0;
2584  reopt->reopttree->reoptnodes[id]->dualredscur->rhs = SCIPsetInfinity(set);
2585  reopt->reopttree->reoptnodes[id]->dualredscur->constype = (reopttype == SCIP_REOPTTYPE_STRBRANCHED ?
2587  reopt->reopttree->reoptnodes[id]->dualredscur->linear = FALSE;
2588 
2589  SCIPsetDebugMsg(set, " -> save dual information of type 1: node %lld, nvars %d, constype %d\n",
2590  SCIPnodeGetNumber(node), reopt->reopttree->reoptnodes[id]->dualredscur->nvars,
2591  reopt->reopttree->reoptnodes[id]->dualredscur->constype);
2592  }
2593  /* the constraint will be added after next */
2594  else
2595  {
2596  assert(reopt->reopttree->reoptnodes[id]->dualredsnex == NULL);
2598  reopt->reopttree->reoptnodes[id]->dualredsnex->nvars = -1;
2599 
2601  reopt->dualreds->vars, nbndchgs) );
2603  reopt->dualreds->vals, nbndchgs) );
2604  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &reopt->reopttree->reoptnodes[id]->dualredsnex->boundtypes, \
2605  reopt->dualreds->boundtypes, nbndchgs) );
2606  reopt->reopttree->reoptnodes[id]->dualredsnex->nvars = nbndchgs;
2607  reopt->reopttree->reoptnodes[id]->dualredsnex->varssize = nbndchgs;
2608  reopt->reopttree->reoptnodes[id]->dualredsnex->lhs = 1.0;
2609  reopt->reopttree->reoptnodes[id]->dualredsnex->rhs = SCIPsetInfinity(set);
2610  reopt->reopttree->reoptnodes[id]->dualredsnex->constype = (reopttype == SCIP_REOPTTYPE_STRBRANCHED ?
2612 
2613  SCIPsetDebugMsg(set, " -> save dual information of type 2: node %lld, nvars %d, constype %d\n",
2614  SCIPnodeGetNumber(node), reopt->reopttree->reoptnodes[id]->dualredsnex->nvars,
2615  reopt->reopttree->reoptnodes[id]->dualredsnex->constype);
2616  }
2617 
2618  return SCIP_OKAY;
2619 }
2620 
2621 /** adds a node of the branch and bound tree to the reoptimization tree */
2622 static
2624  SCIP_REOPT* reopt, /**< reoptimization data structure */
2625  SCIP_SET* set, /**< global SCIP settings */
2626  SCIP_LP* lp, /**< current LP */
2627  BMS_BLKMEM* blkmem, /**< block memory */
2628  SCIP_NODE* node, /**< current node */
2629  SCIP_REOPTTYPE reopttype, /**< reason for storing the node*/
2630  SCIP_Bool saveafterdual, /**< save branching decisions after the first dual */
2631  SCIP_Bool isrootnode, /**< node is the root node */
2632  SCIP_Real lowerbound /**< lower bound of the node */
2633  )
2634 {
2635  SCIP_NODE* parent = NULL;
2636  SCIP_Bool shrank = FALSE;
2637  unsigned int id;
2638  unsigned int parentid = 0;
2639 
2640  assert(reopt != NULL);
2641  assert(set != NULL);
2642  assert(blkmem != NULL);
2643  assert(node != NULL);
2644 
2645  if( set->reopt_maxsavednodes == 0 )
2646  return SCIP_OKAY;
2647 
2648  assert(reopttype == SCIP_REOPTTYPE_TRANSIT
2649  || reopttype == SCIP_REOPTTYPE_INFSUBTREE
2650  || reopttype == SCIP_REOPTTYPE_STRBRANCHED
2651  || reopttype == SCIP_REOPTTYPE_LOGICORNODE
2652  || reopttype == SCIP_REOPTTYPE_LEAF
2653  || reopttype == SCIP_REOPTTYPE_PRUNED
2654  || reopttype == SCIP_REOPTTYPE_FEASIBLE);
2655 
2656  /* start clock */
2657  SCIPclockStart(reopt->savingtime, set);
2658 
2659  /* the node was created by reoptimization, i.e., we need to update the
2660  * stored data */
2661  if( SCIPnodeGetReoptID(node) >= 1 )
2662  {
2663  SCIP_Bool transintoorig;
2664 
2665  assert(reopttype != SCIP_REOPTTYPE_LEAF);
2666  assert(!isrootnode);
2667 
2668  id = SCIPnodeGetReoptID(node);
2669  assert(id < reopt->reopttree->reoptnodessize);
2670 
2671  /* this is a special case:
2672  * due to re-propagation of the an anchester node it can happen that we try to update a node that was created by
2673  * reoptimization and already removed by deleteChildrenBelow. In this case we do not want to save the current
2674  * node
2675  */
2676  if( reopt->reopttree->reoptnodes[id] == NULL )
2677  {
2678  parent = SCIPnodeGetParent(node);
2679  assert(parent != NULL);
2680 
2681  parentid = SCIPnodeGetReoptID(parent);
2682 
2683  /* traverse along the branching path until reaching a node that is part of the reoptimization tree or the root node */
2684  while( SCIPnodeGetDepth(parent) > 0 && reopt->reopttree->reoptnodes[parentid] == NULL )
2685  {
2686  /* the parent node is not part of the reoptimization, reset the reoptid and reopttype of the parent node */
2687  SCIPnodeSetReoptID(parent, 0);
2689 
2690  parent = SCIPnodeGetParent(parent);
2691  assert(parent != NULL);
2692 
2693  parentid = SCIPnodeGetReoptID(parent);
2694  }
2695 
2696  /* the anchestor node has to be part of the reoptimization tree. either the parent is the root itself or
2697  * marked to be a leaf, pruned or feasible
2698  */
2699  assert(reopt->reopttree->reoptnodes[parentid] != NULL);
2700  assert(parentid == 0
2701  || reopt->reopttree->reoptnodes[parentid]->reopttype == SCIP_REOPTTYPE_FEASIBLE
2702  || reopt->reopttree->reoptnodes[parentid]->reopttype == SCIP_REOPTTYPE_INFSUBTREE
2703  || reopt->reopttree->reoptnodes[parentid]->reopttype == SCIP_REOPTTYPE_LEAF
2704  || reopt->reopttree->reoptnodes[parentid]->reopttype == SCIP_REOPTTYPE_PRUNED); /*lint !e641*/
2705 
2706  SCIPsetDebugMsg(set, " -> skip saving\n");
2707  SCIPnodeSetReoptID(node, 0);
2709 
2710  /* stop clock */
2711  SCIPclockStop(reopt->savingtime, set);
2712 
2713  return SCIP_OKAY;
2714  }
2715 
2716  SCIPsetDebugMsg(set, "update node %lld at ID %u:\n", SCIPnodeGetNumber(node), id);
2717 
2718  transintoorig = FALSE;
2719 
2720  /* store separated cuts */
2721  if( set->reopt_usecuts )
2722  {
2723  SCIP_CALL( storeCuts(reopt, set, blkmem, lp, id) );
2724  }
2725 
2726  /* save primal bound changes made after the first dual bound change */
2727  if( saveafterdual )
2728  {
2729  assert(reopttype == SCIP_REOPTTYPE_STRBRANCHED);
2730  SCIP_CALL( saveAfterDualBranchings(reopt, set, blkmem, node, id, &transintoorig) );
2731  }
2732 
2733  /* update constraint propagations */
2734  if( set->reopt_saveconsprop )
2735  {
2736  SCIP_CALL( updateConstraintPropagation(reopt, set, blkmem, node, id, &transintoorig) );
2737  }
2738 
2739  /* ensure that all variables describing the branching path are original */
2740  if( transintoorig )
2741  {
2742  SCIP_CALL( transformIntoOrig(reopt, id) );
2743  }
2744 
2745  /* update the lowerbound if the new lower bound is finite */
2746  if( !SCIPsetIsInfinity(set, REALABS(lowerbound)) )
2747  reopt->reopttree->reoptnodes[id]->lowerbound = lowerbound;
2748  SCIPsetDebugMsg(set, " -> reopttype: %d, lowerbound: %g\n", reopttype, reopt->reopttree->reoptnodes[id]->lowerbound);
2749 
2750 #ifdef SCIP_MORE_DEBUG
2751  {
2752  int varnr;
2753  SCIPsetDebugMsg(set, " -> saved variables:\n");
2754  for (varnr = 0; varnr < reopt->reopttree->reoptnodes[id]->nvars; varnr++)
2755  {
2756  SCIPsetDebugMsg(set, " <%s> %s %g\n", SCIPvarGetName(reopt->reopttree->reoptnodes[id]->vars[varnr]),
2757  reopt->reopttree->reoptnodes[id]->varboundtypes[varnr] == SCIP_BOUNDTYPE_LOWER ?
2758  "=>" : "<=", reopt->reopttree->reoptnodes[id]->varbounds[varnr]);
2759  }
2760  for (varnr = 0; varnr < reopt->reopttree->reoptnodes[id]->nafterdualvars; varnr++)
2761  {
2762  int varnr;
2763  SCIPsetDebugMsg(set, " -> saved variables:\n");
2764  for (varnr = 0; varnr < reopt->reopttree->reoptnodes[id]->nvars; varnr++)
2765  {
2766  SCIPsetDebugMsg(set, " <%s> %s %g\n", SCIPvarGetName(reopt->reopttree->reoptnodes[id]->vars[varnr]),
2767  reopt->reopttree->reoptnodes[id]->varboundtypes[varnr] == SCIP_BOUNDTYPE_LOWER ?
2768  "=>" : "<=", reopt->reopttree->reoptnodes[id]->varbounds[varnr]);
2769  }
2770  for (varnr = 0; varnr < reopt->reopttree->reoptnodes[id]->nafterdualvars; varnr++)
2771  {
2772  SCIPsetDebugMsg(set, " <%s> %s %g (after dual red.)\n", SCIPvarGetName(reopt->reopttree->reoptnodes[id]->afterdualvars[varnr]),
2774  "=>" : "<=", reopt->reopttree->reoptnodes[id]->afterdualvarbounds[varnr]);
2775  }
2776  }
2777  }
2778 #endif
2779 
2780  /* update LPI state */
2781  switch( reopttype )
2782  {
2784  if( set->reopt_shrinkinner )
2785  {
2786  SCIP_CALL( shrinkNode(reopt, set, node, id, &shrank, blkmem) );
2787  }
2788  goto TRANSIT;
2789 
2791  case SCIP_REOPTTYPE_LEAF:
2792  goto TRANSIT;
2793 
2795  /* delete the whole subtree induced be the current node */
2796  SCIP_CALL( deleteChildrenBelow(reopt->reopttree, set, blkmem, id, FALSE, FALSE) );
2797  goto PSEUDO;
2798 
2800  goto PSEUDO;
2801 
2803  /* delete the subtree */
2804  if( set->reopt_reducetofrontier )
2805  {
2806  SCIP_CALL( deleteChildrenBelow(reopt->reopttree, set, blkmem, id, FALSE, FALSE) );
2807  SCIP_CALL( SCIPreoptResetDualBndchgs(reopt, node, blkmem) );
2808  }
2809  /* dive through all children and change the reopttype to PRUNED */
2810  else
2811  {
2813  }
2814  goto FEASIBLE;
2815 
2816  case SCIP_REOPTTYPE_PRUNED:
2817  /* delete the subtree */
2818  if( set->reopt_reducetofrontier )
2819  {
2820  SCIP_CALL( deleteChildrenBelow(reopt->reopttree, set, blkmem, id, FALSE, FALSE) );
2821  SCIP_CALL( SCIPreoptResetDualBndchgs(reopt, node, blkmem) );
2822  }
2823  /* dive through all children and change the reopttype to LEAF */
2824  else
2825  {
2827  }
2828 
2829  /* increase number of reoptimized nodes that could be pruned */
2830  ++reopt->reopttree->ncutoffreoptnodes;
2832 
2833  goto PRUNED;
2834 
2835  default:
2836  break;
2837  } /*lint !e788*/
2838 
2839  /* stop clock */
2840  SCIPclockStart(reopt->savingtime, set);
2841 
2842  return SCIP_OKAY;
2843  }
2844 
2845  /* get new IDs */
2846  SCIP_CALL( reopttreeCheckMemory(reopt->reopttree, set, blkmem) );
2847 
2848  /* the current node is the root node */
2849  if( isrootnode )
2850  {
2851  id = 0;
2852 
2853  /* save local constraints
2854  * note: currently, there will be no constraint to save because all global constraints are added by calling
2855  * SCIPprobAddCons.
2856  */
2857  if (SCIPnodeGetNAddedConss(node) >= 1)
2858  {
2859  assert(reopt->reopttree->reoptnodes[id]->nconss == 0);
2860 
2861  SCIP_CALL( saveLocalConssData(reopt->reopttree, set, blkmem, node, id) );
2862  }
2863 
2864  /* store separated cuts
2865  * note: we need to call this after saveLocalConssData to be sure that the local conss array is ordered, first all
2866  * local constraints, then cuts
2867  */
2868  if( set->reopt_usecuts )
2869  {
2870  SCIP_CALL( storeCuts(reopt, set, blkmem, lp, id) );
2871  }
2872 
2873  switch( reopttype )
2874  {
2876  /* ensure that no dual constraints are stored */
2877  SCIP_CALL( SCIPreoptResetDualBndchgs(reopt, node, blkmem) );
2878 
2879  /* update the lowerbound */
2880  if( !SCIPsetIsInfinity(set, REALABS(lowerbound)) )
2881  reopt->reopttree->reoptnodes[id]->lowerbound = lowerbound;
2882 
2883  goto TRANSIT;
2884 
2887  reopt->reopttree->reoptnodes[0]->reopttype = (unsigned int)reopttype;
2888  reopt->reopttree->reoptnodes[0]->dualreds = TRUE;
2889  reopt->reopttree->reoptnodes[0]->nvars = 0;
2890 
2891  if( reopttype == SCIP_REOPTTYPE_INFSUBTREE )
2892  {
2893  /* delete the whole subtree induced be the current node */
2894  SCIP_CALL( deleteChildrenBelow(reopt->reopttree, set, blkmem, 0, FALSE, FALSE) );
2895  }
2896 
2897  /* update the lowerbound */
2898  if( !SCIPsetIsInfinity(set, REALABS(lowerbound)) )
2899  reopt->reopttree->reoptnodes[id]->lowerbound = lowerbound;
2900 
2901  SCIPsetDebugMsg(set, "update node %d at ID %d:\n", 1, 0);
2902  SCIPsetDebugMsg(set, " -> nvars: 0, ncons: 0, parentID: -, reopttype: %d, lowerbound: %g\n", reopttype,
2903  reopt->reopttree->reoptnodes[id]->lowerbound);
2904 
2905  goto PSEUDO;
2906 
2908  ++reopt->reopttree->ntotalfeasnodes;
2909  ++reopt->reopttree->nfeasnodes;
2910  reopt->reopttree->reoptnodes[0]->reopttype = (unsigned int)SCIP_REOPTTYPE_FEASIBLE;
2911  reopt->reopttree->reoptnodes[0]->dualreds = FALSE;
2912 
2913  if( reopt->reopttree->reoptnodes[0]->childids != NULL && reopt->reopttree->reoptnodes[0]->nchilds > 0 )
2914  {
2915  /* delete the subtree */
2916  if( set->reopt_reducetofrontier )
2917  {
2918  SCIP_CALL( deleteChildrenBelow(reopt->reopttree, set, blkmem, 0, FALSE, FALSE) );
2919  SCIP_CALL( SCIPreoptResetDualBndchgs(reopt, node, blkmem) );
2920  }
2921  /* dive through all children and change the reopttype to LEAF */
2922  else
2923  {
2925  }
2926  }
2927  else
2928  SCIP_CALL( SCIPreoptResetDualBndchgs(reopt, node, blkmem) );
2929 
2930  /* update the lowerbound */
2931  if( !SCIPsetIsInfinity(set, REALABS(lowerbound)) )
2932  reopt->reopttree->reoptnodes[id]->lowerbound = lowerbound;
2933 
2934  SCIPsetDebugMsg(set, "update node %d at ID %d:\n", 1, 0);
2935  SCIPsetDebugMsg(set, " -> nvars: 0, ncons: 0, parentID: -, reopttype: %d, lowerbound: %g\n", reopttype,
2936  reopt->reopttree->reoptnodes[id]->lowerbound);
2937 
2938  break;
2939 
2940  case SCIP_REOPTTYPE_PRUNED:
2941  ++reopt->reopttree->nprunednodes;
2942  ++reopt->reopttree->ntotalprunednodes;
2943  reopt->reopttree->reoptnodes[0]->reopttype = (unsigned int)SCIP_REOPTTYPE_PRUNED;
2944  reopt->reopttree->reoptnodes[0]->dualreds = FALSE;
2945 
2946  if( reopt->reopttree->reoptnodes[0]->childids != NULL && reopt->reopttree->reoptnodes[0]->nchilds > 0 )
2947  {
2948  /* delete the subtree */
2949  if( set->reopt_reducetofrontier )
2950  {
2951  SCIP_CALL( deleteChildrenBelow(reopt->reopttree, set, blkmem, 0, FALSE, FALSE) );
2952  SCIP_CALL( SCIPreoptResetDualBndchgs(reopt, node, blkmem) );
2953  }
2954  /* dive through all children and change the reopttype to LEAF */
2955  else
2956  {
2958  }
2959  }
2960  else
2961  SCIP_CALL( SCIPreoptResetDualBndchgs(reopt, node, blkmem) );
2962 
2963  /* update the lowerbound if it was not set */
2964  if( !SCIPsetIsInfinity(set, REALABS(lowerbound)) )
2965  reopt->reopttree->reoptnodes[id]->lowerbound = lowerbound;
2966 
2967  SCIPsetDebugMsg(set, "update node %d at ID %d:\n", 1, 0);
2968  SCIPsetDebugMsg(set, " -> nvars: 0, ncons: 0, parentID: -, reopttype: %d, lowerbound:%g \n", reopttype,
2969  reopt->reopttree->reoptnodes[id]->lowerbound);
2970 
2971  break;
2972 
2973  default:
2974  assert(reopttype == SCIP_REOPTTYPE_TRANSIT
2975  || reopttype == SCIP_REOPTTYPE_INFSUBTREE
2976  || reopttype == SCIP_REOPTTYPE_STRBRANCHED
2977  || reopttype == SCIP_REOPTTYPE_PRUNED
2978  || reopttype == SCIP_REOPTTYPE_FEASIBLE);
2979  break;
2980  }/*lint !e788*/
2981 
2982  /* reset the information of dual bound changes */
2983  reopt->currentnode = -1;
2984  if( reopt->dualreds != NULL )
2985  reopt->dualreds->nvars = 0;
2986 
2987  /* stop clock */
2988  SCIPclockStop(reopt->savingtime, set);
2989 
2990  return SCIP_OKAY;
2991  }
2992  else
2993  {
2994  int nbndchgdiff;
2995  SCIP_Bool transintoorig;
2996 
2997  SCIPsetDebugMsg(set, "try to add node #%lld to the reopttree\n", SCIPnodeGetNumber(node));
2998  SCIPsetDebugMsg(set, " -> reopttype = %d\n", reopttype);
2999 
3000  /* check if we really want to save this node:
3001  * 1. save the node if reopttype is at least SCIP_REOPTTYPE_INFSUBTREE
3002  * 2. save the node if the number of bound changes of this node
3003  * and the last saved node is at least a given number n
3004  */
3005 
3006  /* get the ID of the last saved node or 0 for the root */
3007  SCIP_CALL( getLastSavedNode(reopt, set, node, &parent, &parentid, &nbndchgdiff) );
3008 
3009  if( (reopttype < SCIP_REOPTTYPE_INFSUBTREE && nbndchgdiff <= set->reopt_maxdiffofnodes)
3010  || reopt->reopttree->reoptnodes[parentid]->reopttype >= SCIP_REOPTTYPE_LEAF ) /*lint !e641*/
3011  {
3012  SCIPsetDebugMsg(set, " -> skip saving\n");
3013 
3014  /* stop clock */
3015  SCIPclockStop(reopt->savingtime, set);
3016 
3017  return SCIP_OKAY;
3018  }
3019 
3020  /* check if there are free slots to store the node */
3021  SCIP_CALL( reopttreeCheckMemory(reopt->reopttree, set, blkmem) );
3022 
3023  id = SCIPqueueRemoveUInt(reopt->reopttree->openids);
3024 
3025  SCIPsetDebugMsg(set, " -> save at ID %u\n", id);
3026 
3027  assert(reopt->reopttree->reoptnodes[id] == NULL
3028  || (reopt->reopttree->reoptnodes[id]->nvars == 0 && reopt->reopttree->reoptnodes[id]->nconss == 0));
3029  assert(id >= 1 && id < reopt->reopttree->reoptnodessize);
3030  assert(!isrootnode);
3031 
3032  /* get memory for nodedata */
3033  assert(reopt->reopttree->reoptnodes[id] == NULL || reopt->reopttree->reoptnodes[id]->nvars == 0);
3034  SCIP_CALL( createReoptnode(reopt->reopttree, set, blkmem, id) );
3035  reopt->reopttree->reoptnodes[id]->parentID = parentid;
3036 
3037  assert(parent != NULL );
3038  assert((SCIPnodeGetDepth(parent) == 0 && parentid == 0) || (SCIPnodeGetDepth(parent) >= 1 && parentid > 0));
3039  assert(id >= 1);
3040 
3041  /* create the array of "child nodes" if they not exist */
3042  if( reopt->reopttree->reoptnodes[parentid]->childids == NULL
3043  || reopt->reopttree->reoptnodes[parentid]->allocchildmem == 0 )
3044  {
3045  SCIP_CALL( reoptnodeCheckMemory(reopt->reopttree->reoptnodes[parentid], set, blkmem, 0, 2, 0) );
3046  }
3047 
3048  /* add the new node as a "child node" of the last saved reoptminization node */
3049  SCIP_CALL( reoptAddChild(reopt->reopttree, set, blkmem, parentid, id) );
3050 
3051  /* save branching path */
3052  SCIP_CALL( saveAncestorBranchings(reopt->reopttree, set, blkmem, node, parent, id, parentid) );
3053 
3054  /* save bound changes after some dual reduction */
3055  if( saveafterdual )
3056  {
3057  assert(reopttype == SCIP_REOPTTYPE_STRBRANCHED);
3058  SCIP_CALL( saveAfterDualBranchings(reopt, set, blkmem, node, id, &transintoorig) );
3059  }
3060  else
3061  {
3062  SCIPsetDebugMsg(set, " -> skip saving bound changes after dual reductions.\n");
3063  }
3064 
3065  /* transform all bounds of branched variables and ensure that they are original. */
3066  SCIP_CALL( transformIntoOrig(reopt, id) );
3067 
3068  /* save pseudo-constraints (if one exists) */
3069  if (SCIPnodeGetNAddedConss(node) >= 1)
3070  {
3071  assert(reopt->reopttree->reoptnodes[id]->nconss == 0);
3072 
3073  SCIP_CALL( saveLocalConssData(reopt->reopttree, set, blkmem, node, id) );
3074  }
3075 
3076  /* store separated cuts
3077  * note: we need to call this after saveLocalConssData to be sure that the local conss array is ordered, first all
3078  * local constraints, then cuts
3079  */
3080  if( set->reopt_usecuts )
3081  {
3082  SCIP_CALL( storeCuts(reopt, set, blkmem, lp, id) );
3083  }
3084 
3085  /* update the lowerbound if it was not set */
3086  if( !SCIPsetIsInfinity(set, REALABS(lowerbound)) )
3087  reopt->reopttree->reoptnodes[id]->lowerbound = lowerbound;
3088 
3089  /* set ID */
3090  SCIPnodeSetReoptID(node, id);
3091 
3092  /* set the REOPTTYPE */
3093  SCIPnodeSetReopttype(node, reopttype);
3094 
3095  SCIPsetDebugMsg(set, "save node #%lld successful\n", SCIPnodeGetNumber(node));
3096  SCIPsetDebugMsg(set, " -> nvars: %d, ncons: %d, parentID: %u, reopttype: %d, lowerbound: %g\n",
3097  reopt->reopttree->reoptnodes[id]->nvars + reopt->reopttree->reoptnodes[id]->nafterdualvars,
3098  reopt->reopttree->reoptnodes[id]->nconss, reopt->reopttree->reoptnodes[id]->parentID,
3099  reopttype, reopt->reopttree->reoptnodes[id]->lowerbound);
3100 #ifdef SCIP_MORE_DEBUG
3101  {
3102  int varnr;
3103  for (varnr = 0; varnr < reopt->reopttree->reoptnodes[id]->nvars; varnr++)
3104  {
3105  int varnr;
3106  for (varnr = 0; varnr < reopt->reopttree->reoptnodes[id]->nvars; varnr++)
3107  {
3108  SCIPsetDebugMsg(set, " <%s> %s %g\n", SCIPvarGetName(reopt->reopttree->reoptnodes[id]->vars[varnr]),
3109  reopt->reopttree->reoptnodes[id]->varboundtypes[varnr] == SCIP_BOUNDTYPE_LOWER ?
3110  "=>" : "<=", reopt->reopttree->reoptnodes[id]->varbounds[varnr]);
3111  }
3112  for (varnr = 0; varnr < reopt->reopttree->reoptnodes[id]->nafterdualvars; varnr++)
3113  {
3114  SCIPsetDebugMsg(set, " <%s> %s %g (after dual red.)\n",
3115  SCIPvarGetName(reopt->reopttree->reoptnodes[id]->afterdualvars[varnr]),
3117  "=>" : "<=", reopt->reopttree->reoptnodes[id]->afterdualvarbounds[varnr]);
3118  }
3119  }
3120  }
3121 #endif
3122  } /*lint !e438*/
3123 
3124  switch( reopttype )
3125  {
3128  case SCIP_REOPTTYPE_LEAF:
3129  TRANSIT:
3130  if( !shrank )
3131  reopt->reopttree->reoptnodes[id]->reopttype = (unsigned int)reopttype;
3132  else
3133  {
3134  SCIPnodeSetReoptID(node, 0);
3136  }
3137  break;
3138 
3141  PSEUDO:
3142  assert(reopt->currentnode == SCIPnodeGetNumber(node));
3143 
3144  reopt->reopttree->reoptnodes[id]->reopttype = (unsigned int)reopttype;
3145  reopt->reopttree->reoptnodes[id]->dualreds = TRUE;
3146 
3147  /* get all the dual information and decide if the constraint need
3148  * to be added next or after next */
3149  SCIP_CALL( collectDualInformation(reopt, set, blkmem, node, id, reopttype) );
3150 
3151  break;
3152 
3154  FEASIBLE:
3155  reopt->reopttree->reoptnodes[id]->reopttype = (unsigned int)SCIP_REOPTTYPE_FEASIBLE;
3156  reopt->reopttree->reoptnodes[id]->dualreds = FALSE;
3157  ++reopt->reopttree->nfeasnodes;
3158  ++reopt->reopttree->ntotalfeasnodes;
3159 
3160  break;
3161 
3162  case SCIP_REOPTTYPE_PRUNED:
3163  PRUNED:
3164  reopt->reopttree->reoptnodes[id]->reopttype = (unsigned int)SCIP_REOPTTYPE_PRUNED;
3165  reopt->reopttree->reoptnodes[id]->dualreds = FALSE;
3166  ++reopt->reopttree->nprunednodes;
3167  ++reopt->reopttree->ntotalprunednodes;
3168 
3169  break;
3170 
3171  default:
3172  assert(reopttype == SCIP_REOPTTYPE_TRANSIT
3173  || reopttype == SCIP_REOPTTYPE_LOGICORNODE
3174  || reopttype == SCIP_REOPTTYPE_LEAF
3175  || reopttype == SCIP_REOPTTYPE_INFSUBTREE
3176  || reopttype == SCIP_REOPTTYPE_STRBRANCHED
3177  || reopttype == SCIP_REOPTTYPE_FEASIBLE
3178  || reopttype == SCIP_REOPTTYPE_PRUNED);
3179  break;
3180  } /*lint !e788*/
3181 
3182  /* stop clock */
3183  SCIPclockStop(reopt->savingtime, set);
3184 
3185  /* reset the information of dual bound changes */
3186  reopt->currentnode = -1;
3187  if( reopt->dualreds != NULL )
3188  reopt->dualreds->nvars = 0;
3189 
3190  return SCIP_OKAY;
3191 }
3192 
3193 /** delete the stored information about dual bound changes of the last focused node */
3194 static
3196  SCIP_REOPT* reopt /**< reoptimization data structure */
3197  )
3198 {
3199  assert(reopt != NULL);
3200 
3201  if( reopt->dualreds != NULL && reopt->dualreds->nvars > 0 )
3202  {
3203  SCIPdebugMessage("delete %d dual variable information about node %lld\n", reopt->dualreds->nvars,
3204  reopt->currentnode);
3205  reopt->dualreds->nvars = 0;
3206  reopt->currentnode = -1;
3207  }
3208 }
3209 
3210 /** delete the stored constraints that dual information at the given reoptimization node */
3211 static
3213  SCIP_REOPTNODE* reoptnode, /**< reoptimization node */
3214  BMS_BLKMEM* blkmem /**< block memory */
3215  )
3216 {
3217  assert(reoptnode != NULL);
3218  assert(blkmem != NULL);
3219 
3220  if( reoptnode->dualredscur != NULL )
3221  {
3222  SCIP_REOPTCONSDATA* reoptconsdata;
3223 
3224  SCIPdebugMessage("reset dual information (current run)\n");
3225 
3226  reoptconsdata = reoptnode->dualredscur;
3227 
3228  BMSfreeBlockMemoryArray(blkmem, &reoptconsdata->boundtypes, reoptconsdata->varssize);
3229  BMSfreeBlockMemoryArray(blkmem, &reoptconsdata->vals, reoptconsdata->varssize);
3230  BMSfreeBlockMemoryArray(blkmem, &reoptconsdata->vars, reoptconsdata->varssize);
3231  BMSfreeBlockMemory(blkmem, &reoptnode->dualredscur);
3232  reoptnode->dualredscur = NULL;
3233  }
3234 
3235  if( reoptnode->dualredsnex != NULL )
3236  {
3237  SCIP_REOPTCONSDATA* reoptconsdata;
3238 
3239  SCIPdebugMessage("reset dual information (next run)\n");
3240 
3241  reoptconsdata = reoptnode->dualredsnex;
3242 
3243  BMSfreeBlockMemoryArray(blkmem, &reoptconsdata->boundtypes, reoptconsdata->varssize);
3244  BMSfreeBlockMemoryArray(blkmem, &reoptconsdata->vals, reoptconsdata->varssize);
3245  BMSfreeBlockMemoryArray(blkmem, &reoptconsdata->vars, reoptconsdata->varssize);
3246  BMSfreeBlockMemory(blkmem, &reoptnode->dualredsnex);
3247  reoptnode->dualredsnex = NULL;
3248  }
3249 
3250  reoptnode->dualreds = FALSE;
3251 
3252  return SCIP_OKAY;
3253 }
3254 
3255 
3256 /** transform given set of variables, bounds and boundtypes into a global cut.
3257  *
3258  * @note: boundtypes can be NULL if all variables are binary or a MIP solution should be separated.
3259  * @note: continuous variables will be skiped if boundtypes is NULL
3260  */
3261 static
3263  SCIP_REOPT* reopt, /**< reoptimization data structure */
3264  BMS_BLKMEM* blkmem, /**< block memory */
3265  SCIP_SET* set, /**< global SCIP settings */
3266  SCIP_VAR** vars, /**< variables of the cut */
3267  SCIP_Real* vals, /**< values of the cut */
3268  SCIP_BOUNDTYPE* boundtypes, /**< bounds of the cut */
3269  int nvars, /**< number of variables in the cut */
3270  int nbinvars, /**< number of binary variables */
3271  int nintvars /**< number of integer variables */
3272  )
3273 {
3274  SCIP_REOPTCONSDATA* reoptconsdata;
3275  int nglbconss;
3276  int nvarsadded;
3277  int v;
3278 
3279  assert(reopt != NULL);
3280  assert(blkmem != NULL);
3281  assert(set != NULL);
3282  assert(vars != NULL);
3283  assert(vals != NULL);
3284  assert(nbinvars + nintvars == nvars);
3285 
3286  nvarsadded = 0;
3287 
3288  /* check whether we have enough memory allocated */
3289  SCIP_CALL( checkMemGlbCons(reopt, set, blkmem, 10) );
3290  nglbconss = reopt->nglbconss;
3291  reoptconsdata = NULL;
3292 
3293  if( reopt->glbconss[nglbconss] == NULL )
3294  {
3295  SCIP_ALLOC( BMSallocBlockMemory(blkmem, &reopt->glbconss[nglbconss]) ); /*lint !e866*/
3296  reoptconsdata = reopt->glbconss[nglbconss];
3297 
3298  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reoptconsdata->vars, (int)(nbinvars+2*nintvars)) );
3299  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reoptconsdata->vals, (int)(nbinvars+2*nintvars)) );
3300  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reoptconsdata->boundtypes, (int)(nbinvars+2*nintvars)) );
3301  reoptconsdata->varssize = (int)(nbinvars+2*nintvars);
3302  reoptconsdata->nvars = 0;
3303  }
3304  else
3305  {
3306  assert(reopt->glbconss[nglbconss]->nvars == 0);
3307  assert(reopt->glbconss[nglbconss]->varssize > 0);
3308 
3309  reoptconsdata = reopt->glbconss[nglbconss];
3310 
3311  if( reoptconsdata->varssize < nbinvars+2*nintvars )
3312  {
3313  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reoptconsdata->vars, reoptconsdata->varssize, \
3314  (int)(nbinvars+2*nintvars)) );
3315  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reoptconsdata->vals, reoptconsdata->varssize, \
3316  (int)(nbinvars+2*nintvars)) );
3317  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reoptconsdata->boundtypes, reoptconsdata->varssize, \
3318  (int)(nbinvars+2*nintvars)) );
3319  reoptconsdata->varssize = (int)(nbinvars+2*nintvars);
3320  }
3321  }
3322  assert(reoptconsdata != NULL);
3323 
3324  reoptconsdata->lhs = 1.0;
3325  reoptconsdata->rhs = SCIPsetInfinity(set);
3326  reoptconsdata->linear = FALSE;
3327  reoptconsdata->constype = REOPT_CONSTYPE_CUT;
3328 
3329  for( v = 0; v < nvars; v++ )
3330  {
3331  assert(nvarsadded < reoptconsdata->varssize);
3332  assert(vars[v] != NULL);
3333  assert(SCIPvarIsOriginal(vars[v]));
3334  assert(SCIPvarGetType(vars[v]) == SCIP_VARTYPE_CONTINUOUS || SCIPsetIsIntegral(set, vals[v]));
3335 
3336  /* if no boundtypes are given we skip continuous variables, otherwise we would add trivial clauses:
3337  * a) x <= ub
3338  * b) lb <= x
3339  * c) (x <= val) or (x >= val)
3340  */
3341  if( boundtypes == NULL && SCIPvarGetType(vars[v]) == SCIP_VARTYPE_CONTINUOUS )
3342  continue;
3343 
3344  if( SCIPvarGetType(vars[v]) == SCIP_VARTYPE_BINARY )
3345  {
3346  reoptconsdata->vars[nvarsadded] = vars[v];
3347 
3348  if( SCIPsetIsEQ(set, vals[v], 1.0) )
3349  {
3350  assert(boundtypes == NULL || boundtypes[v] == SCIP_BOUNDTYPE_LOWER);
3351  reoptconsdata->vals[nvarsadded] = 0.0;
3352  reoptconsdata->boundtypes[nvarsadded] = SCIP_BOUNDTYPE_UPPER;
3353  }
3354  else
3355  {
3356  assert(SCIPsetIsEQ(set, vals[v], 0.0));
3357  assert(boundtypes == NULL || boundtypes[v] == SCIP_BOUNDTYPE_UPPER);
3358  reoptconsdata->vals[nvarsadded] = 1.0;
3359  reoptconsdata->boundtypes[nvarsadded] = SCIP_BOUNDTYPE_LOWER;
3360  }
3361  ++nvarsadded;
3362  }
3363  else if( SCIPvarGetType(vars[v]) == SCIP_VARTYPE_CONTINUOUS)
3364  {
3365  assert(boundtypes != NULL);
3366 
3367  reoptconsdata->vals[nvarsadded] = vals[v];
3368  reoptconsdata->boundtypes[nvarsadded] = (boundtypes[v] == SCIP_BOUNDTYPE_LOWER ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER);
3369  ++nvarsadded;
3370  }
3371  else
3372  {
3373  SCIP_Real roundedval;
3374  SCIP_Real ubglb;
3375  SCIP_Real lbglb;
3376 
3377  assert(SCIPvarGetType(vars[v]) == SCIP_VARTYPE_INTEGER || SCIPvarGetType(vars[v]) == SCIP_VARTYPE_IMPLINT);
3378 
3379  reoptconsdata->vars[nvarsadded] = vars[v];
3380 
3381  ubglb = SCIPvarGetUbGlobal(vars[v]);
3382  lbglb = SCIPvarGetLbGlobal(vars[v]);
3383 
3384  /* case 1 : x == val == ub -> x <= ub-1
3385  * case 2 : x == val == lb -> x >= lb+1
3386  * case 3.1: x <= val < ub -> x >= y+1
3387  * case 3.2: x >= val > lb -> x <= y-1
3388  * case 4 : lb < x == val < ub -> (x <= y-1) or (x >= y+1)
3389  */
3390 
3391  /* case 1 */
3392  if( SCIPsetIsEQ(set, vals[v], ubglb) )
3393  {
3394  assert(boundtypes == NULL || boundtypes[v] == SCIP_BOUNDTYPE_LOWER);
3395  reoptconsdata->vals[nvarsadded] = ubglb - 1.0;
3396  reoptconsdata->boundtypes[nvarsadded] = SCIP_BOUNDTYPE_UPPER;
3397  ++nvarsadded;
3398  }
3399  /* case 2 */
3400  else if( SCIPsetIsEQ(set, vals[v], lbglb) )
3401  {
3402  assert(boundtypes == NULL || boundtypes[v] == SCIP_BOUNDTYPE_UPPER);
3403  reoptconsdata->vals[nvarsadded] = lbglb + 1.0;
3404  reoptconsdata->boundtypes[nvarsadded] = SCIP_BOUNDTYPE_LOWER;
3405  ++nvarsadded;
3406  }
3407  else if( boundtypes != NULL )
3408  {
3409  /* we round the solution value to get a 'clean' bound */
3410  assert(SCIPsetIsIntegral(set, vals[v]));
3411  roundedval = SCIPsetRound(set, vals[v]);
3412 
3413  /* case 3.1 */
3414  if( boundtypes[v] == SCIP_BOUNDTYPE_UPPER )
3415  {
3416  reoptconsdata->vals[nvarsadded] = roundedval + 1.0;
3417  reoptconsdata->boundtypes[nvarsadded] = SCIP_BOUNDTYPE_LOWER;
3418  ++nvarsadded;
3419  }
3420  /* case 3.2 */
3421  else
3422  {
3423  assert(boundtypes[v] == SCIP_BOUNDTYPE_LOWER);
3424  reoptconsdata->vals[nvarsadded] = roundedval - 1.0;
3425  reoptconsdata->boundtypes[nvarsadded] = SCIP_BOUNDTYPE_UPPER;
3426  ++nvarsadded;
3427  }
3428  }
3429  /* case 4: in this case we have to add two clauses: (x <= val-1) and (x >= val+1) */
3430  else
3431  {
3432  /* we round the solution value to get a 'clean' bound */
3433  assert(SCIPsetIsIntegral(set, vals[v]));
3434  roundedval = SCIPsetRound(set, vals[v]);
3435 
3436  /* first clause: x <= val-1 */
3437  reoptconsdata->vals[nvarsadded] = roundedval - 1.0;
3438  reoptconsdata->boundtypes[nvarsadded] = SCIP_BOUNDTYPE_UPPER;
3439  ++nvarsadded;
3440 
3441  /* second clause: x >= val+1 */
3442  reoptconsdata->vars[nvarsadded] = vars[v];
3443  reoptconsdata->vals[nvarsadded] = roundedval + 1.0;
3444  reoptconsdata->boundtypes[nvarsadded] = SCIP_BOUNDTYPE_LOWER;
3445  ++nvarsadded;
3446  }
3447  }
3448  }
3449  assert(nvars <= nvarsadded);
3450  assert(nvarsadded == nbinvars + 2 * nintvars);
3451 
3452  reoptconsdata->nvars = nvarsadded;
3453  ++reopt->nglbconss;
3454 
3455  return SCIP_OKAY;
3456 }
3457 
3458 /** generate a global constraint to separate an infeasible subtree */
3459 static
3461  SCIP_REOPT* reopt, /**< reoptimization data structure */
3462  SCIP_SET* set, /**< global SCIP settings */
3463  BMS_BLKMEM* blkmem, /**< block memory */
3464  SCIP_NODE* node, /**< node of the search tree */
3465  REOPT_CONSTYPE consttype /**< reopttype of the constraint */
3466  )
3467 {
3468  assert(reopt != NULL);
3469  assert(node != NULL);
3470 
3471  if( consttype == REOPT_CONSTYPE_INFSUBTREE )
3472  {
3473  SCIP_VAR** vars;
3474  SCIP_Real* vals;
3475  SCIP_BOUNDTYPE* boundtypes;
3476  int allocmem;
3477  int nbranchvars;
3478  int nbinvars;
3479  int nintvars;
3480  int v;
3481 
3482  /* allocate memory to store the infeasible path */
3483  allocmem = SCIPnodeGetDepth(node);
3484  SCIP_CALL( SCIPsetAllocBufferArray(set, &vars, allocmem) );
3485  SCIP_CALL( SCIPsetAllocBufferArray(set, &vals, allocmem) );
3486  SCIP_CALL( SCIPsetAllocBufferArray(set, &boundtypes, allocmem) );
3487 
3488  /* get the branching path */
3489  SCIPnodeGetAncestorBranchings(node, vars, vals, boundtypes, &nbranchvars, allocmem);
3490 
3491  if( allocmem < nbranchvars )
3492  {
3493  SCIP_CALL( SCIPsetReallocBufferArray(set, &vars, nbranchvars) );
3494  SCIP_CALL( SCIPsetReallocBufferArray(set, &vals, nbranchvars) );
3495  SCIP_CALL( SCIPsetReallocBufferArray(set, &boundtypes, nbranchvars) );
3496  allocmem = nbranchvars;
3497 
3498  SCIPnodeGetAncestorBranchings(node, vars, vals, boundtypes, &nbranchvars, allocmem);
3499  }
3500 
3501  /* we count the number of binary and (impl) integer variables */
3502  nbinvars = 0;
3503  nintvars = 0;
3504  for( v = 0; v < nbranchvars; v++ )
3505  {
3506  if( SCIPvarGetType(vars[v]) == SCIP_VARTYPE_BINARY )
3507  ++nbinvars;
3509  ++nintvars;
3510  }
3511  assert(nbinvars + nintvars == nbranchvars);
3512 
3513  SCIP_CALL( addGlobalCut(reopt, blkmem, set, vars, vals, boundtypes, nbranchvars, nbinvars, nintvars) );
3514  assert(!reopt->glbconss[reopt->nglbconss - 1]->linear);
3515 
3516  /* free buffer */
3517  SCIPsetFreeBufferArray(set, &boundtypes);
3518  SCIPsetFreeBufferArray(set, &vals);
3519  SCIPsetFreeBufferArray(set, &vars);
3520  }
3521 
3522  return SCIP_OKAY;
3523 }
3524 
3525 
3526 /** move all id of child nodes from reoptimization node stored at @p id1 to the node stored at @p id2 */
3527 static
3529  SCIP_REOPTTREE* reopttree, /**< reopttree */
3530  SCIP_SET* set, /**< global SCIP settings */
3531  BMS_BLKMEM* blkmem, /**< block memory */
3532  unsigned int id1, /**< source id */
3533  unsigned int id2 /**< target id */
3534  )
3535 {
3536  int c;
3537  int nchilds_id1;
3538  int nchilds_id2;
3539 
3540  assert(reopttree != NULL);
3541  assert(blkmem != NULL);
3542  assert(id1 < reopttree->reoptnodessize);
3543  assert(id2 < reopttree->reoptnodessize);
3544  assert(reopttree->reoptnodes[id1] != NULL);
3545  assert(reopttree->reoptnodes[id2] != NULL);
3546 
3547  nchilds_id1 = reopttree->reoptnodes[id1]->nchilds;
3548  nchilds_id2 = reopttree->reoptnodes[id2]->nchilds;
3549 
3550  /* ensure that the array storing the child id's is large enough */
3551  SCIP_CALL( reoptnodeCheckMemory(reopttree->reoptnodes[id2], set, blkmem, 0, nchilds_id1+nchilds_id2, 0) );
3552  assert(reopttree->reoptnodes[id2]->allocchildmem >= nchilds_id1+nchilds_id2);
3553 
3554  SCIPsetDebugMsg(set, "move %d IDs: %u -> %u\n", nchilds_id1, id1, id2);
3555 
3556  /* move the ids */
3557  for( c = 0; c < nchilds_id1; c++ )
3558  {
3559 #ifdef SCIP_DEBUG
3560  {
3561  /* check that no id is added twice */
3562  int k;
3563  for( k = 0; k < nchilds_id2; k++ )
3564  assert(reopttree->reoptnodes[id2]->childids[k] != reopttree->reoptnodes[id1]->childids[c]);
3565  }
3566 #endif
3567 
3568  reopttree->reoptnodes[id2]->childids[nchilds_id2+c] = reopttree->reoptnodes[id1]->childids[c];
3569  }
3570 
3571  /* update the number of childs */
3572  reopttree->reoptnodes[id1]->nchilds = 0;
3573  reopttree->reoptnodes[id2]->nchilds += nchilds_id1;
3574 
3575  return SCIP_OKAY;
3576 }
3577 
3578 /** change all bound changes along the root path */
3579 static
3581  SCIP_REOPT* reopt, /**< reoptimization data structure */
3582  SCIP_SET* set, /**< global SCIP settings */
3583  SCIP_STAT* stat, /**< dynamic problem statistics */
3584  SCIP_PROB* transprob, /**< transformed problem */
3585  SCIP_PROB* origprob, /**< original problem */
3586  SCIP_TREE* tree, /**< search tree */
3587  SCIP_LP* lp, /**< current LP */
3588  SCIP_BRANCHCAND* branchcand, /**< branching candidates */
3589  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3590  SCIP_CLIQUETABLE* cliquetable, /**< clique table */
3591  BMS_BLKMEM* blkmem, /**< block memory */
3592  SCIP_NODE* node, /**< node of the branch and bound tree */
3593  unsigned int id, /**< id of stored node */
3594  SCIP_Bool afterdualbranching /**< convert all bound changes made directly after the first bound
3595  * changes based on dual information into normal branchings */
3596  )
3597 {
3598  SCIP_REOPTTREE* reopttree;
3599  SCIP_REOPTNODE* reoptnode;
3600  int v;
3601 
3602  assert(reopt != NULL);
3603  assert(set != NULL);
3604  assert(stat != NULL);
3605  assert(transprob != NULL);
3606  assert(tree != NULL);
3607  assert(lp != NULL);
3608  assert(branchcand != NULL);
3609  assert(eventqueue != NULL);
3610  assert(cliquetable != NULL);
3611  assert(node != NULL);
3612  assert(blkmem != NULL);
3613 
3614  reopttree = reopt->reopttree;
3615  assert(reopttree != NULL);
3616  assert(id < reopttree->reoptnodessize);
3617 
3618  reoptnode = reopttree->reoptnodes[id];
3619  assert(reoptnode != NULL);
3620 
3621  /* copy memory to ensure that only original variables are saved */
3622  if( reoptnode->nvars == 0 && reoptnode->nafterdualvars == 0)
3623  return SCIP_OKAY;
3624 
3625  /* change the bounds along the branching path */
3626  for( v = 0; v < reoptnode->nvars; v++ )
3627  {
3628  SCIP_VAR* var;
3629  SCIP_Real val;
3630  SCIP_BOUNDTYPE boundtype;
3631  SCIP_Real oldlb;
3632  SCIP_Real oldub;
3633  SCIP_Real newbound;
3634 
3635  var = reoptnode->vars[v];
3636  val = reoptnode->varbounds[v];
3637  boundtype = reoptnode->varboundtypes[v];
3638 
3639  assert(SCIPvarIsOriginal(var));
3640  SCIP_CALL( SCIPvarGetProbvarBound(&var, &val, &boundtype) );
3641  assert(SCIPvarIsTransformed(var));
3642  assert(SCIPvarGetStatus(var) != SCIP_VARSTATUS_MULTAGGR);
3643 
3644  oldlb = SCIPvarGetLbLocal(var);
3645  oldub = SCIPvarGetUbLocal(var);
3646  newbound = val;
3647 
3648  assert(boundtype == SCIP_BOUNDTYPE_LOWER || boundtype == SCIP_BOUNDTYPE_UPPER);
3649 
3650  if( boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsGT(set, newbound, oldlb) && SCIPsetIsFeasLE(set, newbound, oldub) )
3651  {
3652  SCIPvarAdjustLb(var, set, &newbound);
3653 
3654  SCIP_CALL( SCIPnodeAddBoundchg(node, blkmem, set, stat, transprob, origprob,
3655  tree, reopt, lp, branchcand, eventqueue, cliquetable, var, newbound, SCIP_BOUNDTYPE_LOWER, FALSE) );
3656  }
3657  else if( boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsLT(set, newbound, oldub) && SCIPsetIsFeasGE(set, newbound, oldlb) )
3658  {
3659  SCIPvarAdjustUb(var, set, &newbound);
3660 
3661  SCIP_CALL( SCIPnodeAddBoundchg(node, blkmem, set, stat, transprob, origprob,
3662  tree, reopt, lp, branchcand, eventqueue, cliquetable, var, newbound, SCIP_BOUNDTYPE_UPPER, FALSE) );
3663  }
3664 #ifdef SCIP_MORE_DEBUG
3665  SCIPsetDebugMsg(set, " (path) <%s> %s %g\n", SCIPvarGetName(var), boundtype == SCIP_BOUNDTYPE_LOWER ? "=>" : "<=", newbound);
3666 #endif
3667  }
3668 
3669  if( afterdualbranching && reoptnode->nafterdualvars > 0 )
3670  {
3671  /* check the memory to convert this bound changes into 'normal' */
3672  SCIP_CALL( reoptnodeCheckMemory(reopttree->reoptnodes[id], set, blkmem,
3673  reoptnode->nvars + reoptnode->nafterdualvars, 0, 0) );
3674 
3675  /* change the bounds */
3676  for( v = 0; v < reoptnode->nafterdualvars; v++ )
3677  {
3678  SCIP_VAR* var;
3679  SCIP_Real val;
3680  SCIP_BOUNDTYPE boundtype;
3681  SCIP_Bool bndchgd;
3682  SCIP_Real oldlb;
3683  SCIP_Real oldub;
3684  SCIP_Real newbound;
3685 
3686  var = reoptnode->afterdualvars[v];
3687  val = reoptnode->afterdualvarbounds[v];
3688  boundtype = reoptnode->afterdualvarboundtypes[v];
3689 
3690  assert(SCIPvarIsOriginal(var));
3691  SCIP_CALL( SCIPvarGetProbvarBound(&var, &val, &boundtype) );
3692  assert(SCIPvarIsTransformed(var));
3693  assert(SCIPvarGetStatus(var) != SCIP_VARSTATUS_MULTAGGR);
3694 
3695  bndchgd = FALSE;
3696 
3697  oldlb = SCIPvarGetLbLocal(var);
3698  oldub = SCIPvarGetUbLocal(var);
3699  newbound = val;
3700 
3701  if( boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsGT(set, newbound, oldlb) && SCIPsetIsFeasLE(set, newbound, oldub) )
3702  {
3703  SCIPvarAdjustLb(var, set, &newbound);
3704  SCIP_CALL( SCIPnodeAddBoundchg(node, blkmem, set, stat, transprob, origprob,
3705  tree, reopt, lp, branchcand, eventqueue, cliquetable, var, newbound, SCIP_BOUNDTYPE_LOWER, FALSE) );
3706 
3707  bndchgd = TRUE;
3708  }
3709  else if( boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsLT(set, newbound, oldub) && SCIPsetIsFeasGE(set, newbound, oldlb) )
3710  {
3711  SCIPvarAdjustUb(var, set, &newbound);
3712  SCIP_CALL( SCIPnodeAddBoundchg(node, blkmem, set, stat, transprob, origprob,
3713  tree, reopt, lp, branchcand, eventqueue, cliquetable, var, newbound, SCIP_BOUNDTYPE_UPPER, FALSE) );
3714 
3715  bndchgd = TRUE;
3716  }
3717 
3718  assert(boundtype == SCIP_BOUNDTYPE_LOWER || boundtype == SCIP_BOUNDTYPE_UPPER);
3719 
3720 #ifdef SCIP_MORE_DEBUG
3721  SCIPsetDebugMsg(set, " (prop) <%s> %s %g\n", SCIPvarGetName(var), boundtype == SCIP_BOUNDTYPE_LOWER ? "=>" : "<=", newbound);
3722 #endif
3723  if( bndchgd )
3724  {
3725  int nvars;
3726 
3727  nvars = reoptnode->nvars;
3728  reoptnode->vars[nvars] = reoptnode->afterdualvars[v];
3729  reoptnode->varbounds[nvars] = reoptnode->afterdualvarbounds[v];
3730  reoptnode->varboundtypes[nvars] = reoptnode->afterdualvarboundtypes[v];
3731  ++reoptnode->nvars;
3732  }
3733  }
3734 
3735  /* free the afterdualvars, -bounds, and -boundtypes */
3736  BMSfreeBlockMemoryArray(blkmem, &reoptnode->afterdualvarboundtypes, reoptnode->afterdualvarssize);
3737  reoptnode->afterdualvarboundtypes = NULL;
3738 
3739  BMSfreeBlockMemoryArray(blkmem, &reoptnode->afterdualvarbounds, reoptnode->afterdualvarssize);
3740  reoptnode->afterdualvarbounds = NULL;
3741 
3742  BMSfreeBlockMemoryArray(blkmem, &reoptnode->afterdualvars, reoptnode->afterdualvarssize);
3743  reoptnode->afterdualvars = NULL;
3744 
3745  reoptnode->nafterdualvars = 0;
3746  reoptnode->afterdualvarssize = 0;
3747  }
3748 
3749  return SCIP_OKAY;
3750 }
3751 
3752 
3753 /** add a constraint to ensure that at least one variable bound gets different */
3754 static
3756  SCIP_REOPT* reopt, /**< reoptimization data structure */
3757  SCIP* scip, /**< SCIP data structure */
3758  SCIP_SET* set, /**< global SCIP settings */
3759  SCIP_STAT* stat, /**< dynamic problem statistics */
3760  BMS_BLKMEM* blkmem, /**< block memory */
3761  SCIP_PROB* transprob, /**< transformed problem */
3762  SCIP_PROB* origprob, /**< original problem */
3763  SCIP_TREE* tree, /**< search tree */
3764  SCIP_LP* lp, /**< current LP */
3765  SCIP_BRANCHCAND* branchcand, /**< branching candidates */
3766  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3767  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3768  SCIP_NODE* node, /**< node corresponding to the pruned part */
3769  unsigned int id /**< id of stored node */
3770  )
3771 {
3772  SCIP_CONS* cons;
3773  char name[SCIP_MAXSTRLEN];
3774  int v;
3775 
3776  assert(reopt != NULL);
3777  assert(reopt->reopttree != NULL);
3778  assert(id < reopt->reopttree->reoptnodessize);
3779  assert(reopt->reopttree->reoptnodes[id] != NULL);
3780  assert(reopt->reopttree->reoptnodes[id]->dualreds);
3781  assert(reopt->reopttree->reoptnodes[id]->dualredscur != NULL);
3782  assert(scip != NULL);
3783  assert(set != NULL);
3784  assert(stat != NULL);
3785  assert(blkmem != NULL);
3786  assert(transprob != NULL);
3787  assert(origprob != NULL);
3788  assert(tree != NULL);
3789  assert(lp != NULL);
3790  assert(branchcand != NULL);
3791  assert(eventqueue != NULL);
3792  assert(node != NULL);
3793 
3794  assert(reopt->reopttree->reoptnodes[id]->dualredscur->constype == REOPT_CONSTYPE_DUALREDS
3795  || reopt->reopttree->reoptnodes[id]->dualredscur->constype == REOPT_CONSTYPE_INFSUBTREE);
3796 
3797 #ifndef NDEBUG
3798  if( reopt->reopttree->reoptnodes[id]->dualredscur->constype == REOPT_CONSTYPE_DUALREDS )
3799  SCIPsetDebugMsg(set, " create a split-node #%lld\n", SCIPnodeGetNumber(node));
3800  else
3801  SCIPsetDebugMsg(set, " separate an infeasible subtree\n");
3802 #endif
3803 
3804  /* if the constraint consists of exactly one variable it can be interpreted
3805  * as a normal branching step, i.e., we can fix the variable to the negated bound */
3806  if( reopt->reopttree->reoptnodes[id]->dualredscur->nvars == 1 )
3807  {
3808  SCIP_REOPTCONSDATA* reoptconsdata;
3809  SCIP_VAR* var;
3810  SCIP_BOUNDTYPE boundtype;
3811  SCIP_Real oldlb;
3812  SCIP_Real oldub;
3813  SCIP_Real newbound;
3814 
3815  reoptconsdata = reopt->reopttree->reoptnodes[id]->dualredscur;
3816  assert(!reoptconsdata->linear);
3817  assert(reoptconsdata->vars != NULL);
3818  assert(reoptconsdata->vals != NULL);
3819  assert(reoptconsdata->boundtypes != NULL);
3820 
3821  var = reoptconsdata->vars[0];
3822  newbound = reoptconsdata->vals[0];
3823  boundtype = reoptconsdata->boundtypes[0];
3824 
3825  assert(SCIPvarIsOriginal(var));
3826  SCIP_CALL( SCIPvarGetProbvarBound(&var, &newbound, &boundtype) );
3827  assert(SCIPvarIsTransformed(var));
3828 
3829  oldlb = SCIPvarGetLbLocal(var);
3830  oldub = SCIPvarGetUbLocal(var);
3831 
3832  if( boundtype == SCIP_BOUNDTYPE_LOWER )
3833  {
3834  newbound = reoptconsdata->vals[0] - 1.0;
3835  assert(SCIPisLE(scip, newbound, oldub));
3836  }
3837  else
3838  {
3839  newbound = reoptconsdata->vals[0] + 1.0;
3840  assert(SCIPisGE(scip, newbound, oldlb));
3841  }
3842  boundtype = (SCIP_BOUNDTYPE) (1 - (int)boundtype);
3843  assert(boundtype == SCIP_BOUNDTYPE_LOWER || boundtype == SCIP_BOUNDTYPE_UPPER);
3844 
3845  if( boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsGT(set, newbound, oldlb) && SCIPsetIsFeasLE(set, newbound, oldub) )
3846  {
3847  SCIPvarAdjustLb(var, set, &newbound);
3848  SCIP_CALL( SCIPnodeAddBoundchg(node, blkmem, set, stat, transprob, origprob,
3849  tree, reopt, lp, branchcand, eventqueue, cliquetable, var, newbound, SCIP_BOUNDTYPE_LOWER, FALSE) );
3850  }
3851  else if( boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsLT(set, newbound, oldub) && SCIPsetIsFeasGE(set, newbound, oldlb) )
3852  {
3853  SCIPvarAdjustUb(var, set, &newbound);
3854  SCIP_CALL( SCIPnodeAddBoundchg(node, blkmem, set, stat, transprob, origprob,
3855  tree, reopt, lp, branchcand, eventqueue, cliquetable, var, newbound, SCIP_BOUNDTYPE_UPPER, FALSE) );
3856  }
3857 
3858  SCIPsetDebugMsg(set, " -> constraint consists of only one variable: <%s> %s %g\n", SCIPvarGetName(var),
3859  boundtype == SCIP_BOUNDTYPE_LOWER ? "=>" : "<=", newbound);
3860  }
3861  else
3862  {
3863  SCIP_REOPTCONSDATA* reoptconsdata;
3864  SCIP_VAR** consvars;
3865  SCIP_Real consval;
3866  SCIP_BOUNDTYPE consboundtype;
3867  int nbinvars = 0;
3868  int nintvars = 0;
3869  int ncontvars = 0;
3870 
3871  reoptconsdata = reopt->reopttree->reoptnodes[id]->dualredscur;
3872  assert(!reoptconsdata->linear);
3873  assert(reoptconsdata->vars != NULL);
3874  assert(reoptconsdata->vals != NULL);
3875  assert(reoptconsdata->boundtypes != NULL);
3876 
3877  /* allocate buffer */
3878  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, reoptconsdata->nvars) );
3879 
3880  /* count number of binary, integer, and continuous variables */
3881  for( v = 0; v < reoptconsdata->nvars; v++ )
3882  {
3883  switch ( SCIPvarGetType(reoptconsdata->vars[v]) )
3884  {
3885  case SCIP_VARTYPE_BINARY:
3886  ++nbinvars;
3887  break;
3888  case SCIP_VARTYPE_IMPLINT:
3889  case SCIP_VARTYPE_INTEGER:
3890  if( SCIPisEQ(scip, SCIPvarGetLbLocal(reoptconsdata->vars[v]), 0.0)
3891  && SCIPisEQ(scip, SCIPvarGetUbLocal(reoptconsdata->vars[v]), 1.0) )
3892  ++nbinvars;
3893  else
3894  ++nintvars;
3895  break;
3897  ++ncontvars;
3898  break;
3899  default:
3900  SCIPerrorMessage("Variable <%s> has to be either binary, (implied) integer, or continuous.\n",
3901  SCIPvarGetName(reoptconsdata->vars[v]));
3902  return SCIP_INVALIDDATA;
3903  }
3904  }
3905 
3906  if( reoptconsdata->constype == REOPT_CONSTYPE_INFSUBTREE )
3907  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "reopt_inf");
3908  else
3909  {
3910  assert(reoptconsdata->constype == REOPT_CONSTYPE_DUALREDS);
3911  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "reopt_dual");
3912  }
3913 
3914  /* case 1: all variables are binary, we use a logic-or constraint. */
3915  if( reoptconsdata->nvars == nbinvars )
3916  {
3917  for( v = 0; v < reoptconsdata->nvars; v++ )
3918  {
3919  consvars[v] = reoptconsdata->vars[v];
3920  consval = reoptconsdata->vals[v];
3921  consboundtype = SCIPsetIsFeasEQ(set, consval, 1.0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER;
3922 
3923  assert(SCIPvarIsOriginal(consvars[v]));
3924  SCIP_CALL( SCIPvarGetProbvarBound(&consvars[v], &consval, &consboundtype) );
3925  assert(SCIPvarIsTransformed(consvars[v]));
3926  assert(SCIPvarGetStatus(consvars[v]) != SCIP_VARSTATUS_MULTAGGR);
3927 
3928  if ( SCIPsetIsFeasEQ(set, consval, 1.0) )
3929  {
3930  SCIP_CALL( SCIPvarNegate(consvars[v], blkmem, set, stat, &consvars[v]) );
3931  assert(SCIPvarIsNegated(consvars[v]));
3932  }
3933  }
3934 
3935  SCIP_CALL( SCIPcreateConsLogicor(scip, &cons, name, reoptconsdata->nvars, consvars,
3937  }
3938  /* case 2: at least one variable is integer or continuous. we use a bounddisjunction constraint. */
3939  else
3940  {
3941  SCIP_Real* consvals;
3942  SCIP_BOUNDTYPE* consboundtypes;
3943 
3944  assert(nintvars > 0 || ncontvars > 0);
3945 
3946  /* alloc buffer memory */
3947  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, reoptconsdata->nvars) );
3948  SCIP_CALL( SCIPallocBufferArray(scip, &consboundtypes, reoptconsdata->nvars) );
3949 
3950  /* iterate over all variables and transform them */
3951  for( v = 0; v < reoptconsdata->nvars; v++ )
3952  {
3953  consvars[v] = reoptconsdata->vars[v];
3954  consvals[v] = reoptconsdata->vals[v];
3955  consboundtypes[v] = reoptconsdata->boundtypes[v];
3956 
3957  /* we have to switch the bounds.
3958  * case 1: integer variable with bound x <= u is transformed to u+1 <= x
3959  * and l <= x is transformed to x <= l-1
3960  * case 2: continuous variable with bound x <= u is transformed to u <= x
3961  * and l <= x is transformed to x <= l
3962  */
3963  if( SCIPvarGetType(consvars[v]) == SCIP_VARTYPE_BINARY
3964  || SCIPvarGetType(consvars[v]) == SCIP_VARTYPE_INTEGER
3965  || SCIPvarGetType(consvars[v]) == SCIP_VARTYPE_IMPLINT )
3966  {
3967  if( consboundtypes[v] == SCIP_BOUNDTYPE_UPPER )
3968  {
3969  consvals[v] += 1.0;
3970  assert(SCIPsetIsLE(set, consvals[v], SCIPvarGetUbGlobal(consvars[v])));
3971  }
3972  else
3973  {
3974  consvals[v] -= 1.0;
3975  assert(SCIPsetIsGE(set, consvals[v], SCIPvarGetLbGlobal(consvars[v])));
3976  }
3977  }
3978 
3979  consboundtypes[v] = (SCIP_BOUNDTYPE)(1 - consboundtypes[v]); /*lint !e641*/
3980 
3981  assert(SCIPvarIsOriginal(consvars[v]));
3982  SCIP_CALL( SCIPvarGetProbvarBound(&consvars[v], &consvals[v], &consboundtypes[v]) );
3983  assert(SCIPvarIsTransformed(consvars[v]));
3984  assert(SCIPvarGetStatus(consvars[v]) != SCIP_VARSTATUS_MULTAGGR);
3985  }
3986 
3987  /* create the constraints and add them to the corresponding nodes */
3988  SCIP_CALL( SCIPcreateConsBounddisjunctionRedundant(scip, &cons, name, reoptconsdata->nvars, consvars, consboundtypes,
3989  consvals, FALSE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE) );
3990 
3991  /* free buffer memory */
3992  SCIPfreeBufferArray(scip, &consboundtypes);
3993  SCIPfreeBufferArray(scip, &consvals);
3994  }
3995 
3996  SCIPsetDebugMsg(set, " -> add constraint in node #%lld:\n", SCIPnodeGetNumber(node));
3997 #ifdef SCIP_DEBUG_CONSS
3998  SCIPdebugPrintCons(scip, cons, NULL);
3999 #endif
4000 
4001  SCIP_CALL( SCIPaddConsNode(scip, node, cons, NULL) );
4002  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
4003 
4004  /* free buffer */
4005  SCIPfreeBufferArray(scip, &consvars);
4006  }
4007 
4008  return SCIP_OKAY;
4009 }
4010 
4011 /** fix all bounds ad stored in dualredscur at the given node @p node_fix */
4012 static
4014  SCIP_REOPT* reopt, /**< reoptimization data structure */
4015  SCIP_SET* set, /**< global SCIP settings */
4016  SCIP_STAT* stat, /**< dynamic problem statistics */
4017  SCIP_PROB* transprob, /**< transformed problem */
4018  SCIP_PROB* origprob, /**< original problem */
4019  SCIP_TREE* tree, /**< search tree */
4020  SCIP_LP* lp, /**< current LP */
4021  SCIP_BRANCHCAND* branchcand, /**< branching candidates */
4022  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4023  SCIP_CLIQUETABLE* cliquetable, /**< clique table */
4024  BMS_BLKMEM* blkmem, /**< block memory */
4025  SCIP_NODE* node, /**< node corresponding to the fixed part */
4026  unsigned int id, /**< id of stored node */
4027  SCIP_Bool updatedualconss /**< update constraint representing dual bound changes */
4028  )
4029 {
4030  SCIP_REOPTTREE* reopttree;
4031  SCIP_REOPTNODE* reoptnode;
4032  int v;
4033 
4034  assert(reopt != NULL);
4035  assert(set != NULL);
4036  assert(stat != NULL);
4037  assert(transprob != NULL);
4038  assert(origprob != NULL);
4039  assert(tree != NULL);
4040  assert(lp != NULL);
4041  assert(branchcand != NULL);
4042  assert(eventqueue != NULL);
4043  assert(cliquetable != NULL);
4044  assert(node != NULL);
4045  assert(blkmem != NULL);
4046 
4047  reopttree = reopt->reopttree;
4048  assert(reopttree != NULL);
4049  assert(0 < id && id < reopttree->reoptnodessize);
4050 
4051  reoptnode = reopttree->reoptnodes[id];
4052  assert(reoptnode != NULL);
4053  assert(reoptnode->dualreds);
4054  assert(reoptnode->dualredscur != NULL);
4055 
4056  /* ensure that the arrays to store the bound changes are large enough */
4057  SCIP_CALL( reoptnodeCheckMemory(reoptnode, set, blkmem, reoptnode->nvars + reoptnode->dualredscur->nvars, 0, 0) );
4058 
4059  for( v = 0; v < reoptnode->dualredscur->nvars; v++ )
4060  {
4061  SCIP_VAR* var;
4062  SCIP_Real val;
4063  SCIP_BOUNDTYPE boundtype;
4064  SCIP_Bool bndchgd;
4065 
4066  var = reoptnode->dualredscur->vars[v];
4067  val = reoptnode->dualredscur->vals[v];
4068  boundtype = reoptnode->dualredscur->boundtypes[v];
4069 
4070  SCIP_CALL(SCIPvarGetProbvarBound(&var, &val, &boundtype));
4071  assert(SCIPvarIsTransformedOrigvar(var));
4072 
4073  bndchgd = FALSE;
4074 
4075  if( boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsGT(set, val, SCIPvarGetLbLocal(var))
4076  && SCIPsetIsFeasLE(set, val, SCIPvarGetUbLocal(var)) )
4077  {
4078  SCIPvarAdjustLb(var, set, &val);
4079  SCIP_CALL( SCIPnodeAddBoundchg(node, blkmem, set, stat, transprob, origprob,
4080  tree, reopt, lp, branchcand, eventqueue, cliquetable, var, val, SCIP_BOUNDTYPE_LOWER, FALSE) );
4081 
4082  bndchgd = TRUE;
4083  }
4084  else if( boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsLT(set, val, SCIPvarGetUbLocal(var))
4085  && SCIPsetIsFeasGE(set, val, SCIPvarGetLbLocal(var)) )
4086  {
4087  SCIPvarAdjustUb(var, set, &val);
4088  SCIP_CALL( SCIPnodeAddBoundchg(node, blkmem, set, stat, transprob, origprob,
4089  tree, reopt, lp, branchcand, eventqueue, cliquetable, var, val, SCIP_BOUNDTYPE_UPPER, FALSE) );
4090 
4091  bndchgd = TRUE;
4092  }
4093  else if( boundtype != SCIP_BOUNDTYPE_LOWER && boundtype != SCIP_BOUNDTYPE_UPPER )
4094  {
4095  SCIPerrorMessage("** Unknown boundtype: %d **\n", boundtype);
4096  return SCIP_INVALIDDATA;
4097  }
4098 #ifdef SCIP_MORE_DEBUG
4099  SCIPsetDebugMsg(set, " (dual) <%s> %s %g\n", SCIPvarGetName(var), boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", val);
4100 #endif
4101  /* add variable and bound to branching path information, because we don't want to delete this data */
4102  if( bndchgd )
4103  {
4104  int pos;
4105  SCIP_Real constant;
4106  SCIP_Real scalar;
4107 
4108  pos = reoptnode->nvars;
4109 
4110  reoptnode->vars[pos] = var;
4111  scalar = 1.0;
4112  constant = 0.0;
4113  SCIP_CALL( SCIPvarGetOrigvarSum(&reoptnode->vars[pos], &scalar, &constant) );
4114  assert(SCIPvarIsOriginal(reoptnode->vars[pos]));
4115 
4116  reoptnode->varbounds[pos] = reoptnode->dualredscur->vals[v];
4117  reoptnode->varboundtypes[pos] = (SCIPsetIsFeasEQ(set, reoptnode->varbounds[pos], 0.0) ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER);
4118  ++reoptnode->nvars;
4119  }
4120  }
4121 
4122  if( updatedualconss )
4123  {
4124  /* delete dualredscur and move dualredsnex -> dualredscur */
4125  SCIP_CALL( reoptnodeUpdateDualConss(reoptnode, blkmem) );
4126  }
4127 
4128  return SCIP_OKAY;
4129 }
4130 
4131 /** fix all bounds corresponding to dual bound changes in a previous iteration in the fashion of interdiction branching;
4132  * keep the first negbndchg-1 bound changes as stored in dualredscur and negate the negbndchg-th bound.
4133  */
4134 static
4136  SCIP_REOPT* reopt, /**< reoptimization data structure */
4137  SCIP_SET* set, /**< global SCIP settings */
4138  SCIP_STAT* stat, /**< dynamic problem statistics */
4139  SCIP_PROB* transprob, /**< transformed problem */
4140  SCIP_PROB* origprob, /**< original problem */
4141  SCIP_TREE* tree, /**< search tree */
4142  SCIP_LP* lp, /**< current LP */
4143  SCIP_BRANCHCAND* branchcand, /**< branching candidates */
4144  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4145  SCIP_CLIQUETABLE* cliquetable, /**< clique table */
4146  BMS_BLKMEM* blkmem, /**< block memory */
4147  SCIP_NODE* node, /**< child node */
4148  unsigned int id, /**< id of the node */
4149  int* perm, /**< array of permuted indices */
4150  SCIP_VAR** vars, /**< variables */
4151  SCIP_Real* vals, /**< bounds */
4152  SCIP_BOUNDTYPE* boundtypes, /**< boundtypes */
4153  int nvars, /**< number of variables */
4154  int negbndchg /**< index of the variable that should negated */
4155  )
4156 {
4157  SCIP_VAR* var;
4158  SCIP_Real val;
4159  SCIP_BOUNDTYPE boundtype;
4160  int nbndchgs;
4161  int v;
4162 
4163  assert(reopt != NULL);
4164  assert(set != NULL);
4165  assert(stat != NULL);
4166  assert(transprob != NULL);
4167  assert(origprob != NULL);
4168  assert(tree != NULL);
4169  assert(lp != NULL);
4170  assert(branchcand != NULL);
4171  assert(eventqueue != NULL);
4172  assert(cliquetable != NULL);
4173  assert(node != NULL);
4174  assert(perm != NULL);
4175  assert(vars != NULL);
4176  assert(vals != NULL);
4177  assert(boundtypes != NULL);
4178  assert(nvars >= 0);
4179  assert(blkmem != NULL);
4180  assert(0 < id && id < reopt->reopttree->reoptnodessize);
4181 
4182 #ifndef NDEBUG
4183  {
4184  SCIP_REOPTTREE* reopttree;
4185  SCIP_REOPTNODE* reoptnode;
4186 
4187  reopttree = reopt->reopttree;
4188  assert(reopttree != NULL);
4189 
4190  reoptnode = reopttree->reoptnodes[id];
4191  assert(reoptnode != NULL);
4192  assert(reoptnode->dualreds);
4193  }
4194 #endif
4195 
4196  nbndchgs = MIN(negbndchg, nvars);
4197 
4198  /* change the first nbndchg-1 bounds as stored in dualredscur and negate the negbndchg-th bound */
4199  for( v = 0; v < nbndchgs; v++ )
4200  {
4201  var = vars[perm[v]];
4202  val = vals[perm[v]];
4203  boundtype = boundtypes[perm[v]];
4204 
4205  SCIP_CALL(SCIPvarGetProbvarBound(&var, &val, &boundtype));
4206  assert(SCIPvarIsTransformedOrigvar(var));
4207 
4208  /* negate the last bound change */
4209  if( v == nbndchgs-1 )
4210  {
4211  boundtype = (SCIP_BOUNDTYPE)(SCIP_BOUNDTYPE_UPPER - boundtype); /*lint !e656*/
4212  if( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS && boundtype == SCIP_BOUNDTYPE_UPPER )
4213  val = val - 1.0;
4214  else if( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS && boundtype == SCIP_BOUNDTYPE_LOWER )
4215  val = val + 1.0;
4216  }
4217 
4218  if( boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsGT(set, val, SCIPvarGetLbLocal(var))
4219  && SCIPsetIsFeasLE(set, val, SCIPvarGetUbLocal(var)) )
4220  {
4221  SCIPvarAdjustLb(var, set, &val);
4222  SCIP_CALL( SCIPnodeAddBoundchg(node, blkmem, set, stat, transprob, origprob,
4223  tree, reopt, lp, branchcand, eventqueue, cliquetable, var, val, SCIP_BOUNDTYPE_LOWER, FALSE) );
4224  }
4225  else if( boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsLT(set, val, SCIPvarGetUbLocal(var))
4226  && SCIPsetIsFeasGE(set, val, SCIPvarGetLbLocal(var)) )
4227  {
4228  SCIPvarAdjustUb(var, set, &val);
4229  SCIP_CALL( SCIPnodeAddBoundchg(node, blkmem, set, stat, transprob, origprob,
4230  tree, reopt, lp, branchcand, eventqueue, cliquetable, var, val, SCIP_BOUNDTYPE_UPPER, FALSE) );
4231  }
4232  else if( boundtype != SCIP_BOUNDTYPE_LOWER && boundtype != SCIP_BOUNDTYPE_UPPER )
4233  {
4234  SCIPerrorMessage("** Unknown boundtype: %d **\n", boundtype);
4235  return SCIP_INVALIDDATA;
4236  }
4237 #ifdef SCIP_MORE_DEBUG
4238  SCIPsetDebugMsg(set, " (dual) <%s> %s %g\n", SCIPvarGetName(var), boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", val);
4239 #endif
4240  }
4241 
4242  return SCIP_OKAY;
4243 }
4244 
4245 /** add all constraints stored at @p id to the given nodes @p node_fix and @p node_cons */
4246 static
4248  SCIP* scip, /**< SCIP data structure */
4249  SCIP_REOPT* reopt, /**< reoptimization data structure */
4250  SCIP_SET* set, /**< global SCIP settings */
4251  SCIP_STAT* stat, /**< dynamic problem statistics */
4252  BMS_BLKMEM* blkmem, /**< block memory */
4253  SCIP_NODE* node, /**< node of the branch and bound tree*/
4254  unsigned int id /**< id of stored node */
4255  )
4256 {
4257  int c;
4258  char name[SCIP_MAXSTRLEN];
4259 
4260  assert(scip != NULL);
4261  assert(reopt != NULL);
4262  assert(reopt->reopttree != NULL);
4263  assert(set != NULL);
4264  assert(stat != NULL);
4265  assert(blkmem != NULL);
4266  assert(node != NULL);
4267  assert(0 < id && id < reopt->reopttree->reoptnodessize);
4268 
4269  if( reopt->reopttree->reoptnodes[id]->nconss == 0 )
4270  return SCIP_OKAY;
4271 
4272  SCIPsetDebugMsg(set, " -> add %d constraint(s) to node #%lld:\n", reopt->reopttree->reoptnodes[id]->nconss,
4273  SCIPnodeGetNumber(node));
4274 
4275  for( c = 0; c < reopt->reopttree->reoptnodes[id]->nconss; c++ )
4276  {
4277  SCIP_CONS* cons;
4278  SCIP_REOPTCONSDATA* reoptconsdata;
4279 
4280  reoptconsdata = reopt->reopttree->reoptnodes[id]->conss[c];
4281  assert(reoptconsdata != NULL);
4282  assert(reoptconsdata->nvars > 0);
4283  assert(reoptconsdata->varssize >= reoptconsdata->nvars);
4284 
4285  if( reoptconsdata->constype == REOPT_CONSTYPE_CUT )
4286  continue;
4287 
4288  if( reoptconsdata->constype == REOPT_CONSTYPE_INFSUBTREE )
4289  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "reopt_inf");
4290  else if( reoptconsdata->constype == REOPT_CONSTYPE_DUALREDS )
4291  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "reopt_dual");
4292  else
4293  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "reopt_unkn");
4294 
4295  if( reoptconsdata->linear )
4296  {
4297  SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, reoptconsdata->nvars, reoptconsdata->vars, reoptconsdata->vals,
4298  reoptconsdata->lhs, reoptconsdata->rhs, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE) );
4299  }
4300  else
4301  {
4302  assert(reoptconsdata->boundtypes != NULL);
4303  SCIP_CALL( SCIPcreateConsBounddisjunctionRedundant(scip, &cons, name, reoptconsdata->nvars, reoptconsdata->vars, reoptconsdata->boundtypes,
4304  reoptconsdata->vals, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE) );
4305  }
4306 #ifdef SCIP_DEBUG_CONSS
4307  SCIPdebugPrintCons(scip, cons, NULL);
4308 #endif
4309  SCIP_CALL( SCIPaddConsNode(scip, node, cons, NULL) );
4310  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
4311  }
4312 
4313  return SCIP_OKAY;
4314 }
4315 
4316 /** reset the internal statistics at the beginning of a new iteration */
4317 static
4319  SCIP_REOPT* reopt /**< reoptimization data structure */
4320  )
4321 {
4322  assert(reopt != NULL);
4323 
4324  reopt->lastbranched = -1;
4325  reopt->currentnode = -1;
4326  reopt->lastseennode = -1;
4327  reopt->reopttree->nfeasnodes = 0;
4328  reopt->reopttree->ninfnodes = 0;
4329  reopt->reopttree->nprunednodes = 0;
4330  reopt->reopttree->ncutoffreoptnodes = 0;
4331 
4332  if( reopt->dualreds != NULL )
4333  reopt->dualreds->nvars = 0;
4334 }
4335 
4336 /** check the stored bound changes of all child nodes for redundancy and infeasibility
4337  *
4338  * Due to strongbranching initialization at node stored at @p id it can happen, that some bound changes stored in the
4339  * child nodes of the reoptimization node stored at @p id become redundant or make the subproblem infeasible. in this
4340  * method we remove all redundant bound changes and delete infeasible child nodes.
4341  */
4342 static
4344  SCIP_REOPT* reopt, /**< reoptimization data structure */
4345  SCIP_SET* set, /**< global SCIP settings */
4346  BMS_BLKMEM* blkmem, /**< block memory */
4347  SCIP_Bool* runagain, /**< pointer to store of this method should run again */
4348  unsigned int id /**< id of stored node */
4349  )
4350 {
4351  SCIP_REOPTNODE* reoptnode;
4352  unsigned int* cutoffchilds;
4353  int ncutoffchilds = 0;
4354  unsigned int* redchilds;
4355  int nredchilds = 0;
4356  int c;
4357 
4358  assert(reopt != NULL);
4359  assert(reopt->reopttree != NULL);
4360  assert(id < reopt->reopttree->reoptnodessize);
4361  assert(reopt->reopttree->reoptnodes != NULL);
4362  assert(reopt->reopttree->reoptnodes[id] != NULL);
4363 
4364  reoptnode = reopt->reopttree->reoptnodes[id];
4365 
4366  *runagain = FALSE;
4367 
4368  SCIPsetDebugMsg(set, "start dry branching of node at ID %u\n", id);
4369 
4370  /* allocate buffer arrays */
4371  SCIP_CALL( SCIPsetAllocBufferArray(set, &cutoffchilds, reoptnode->nchilds) );
4372  SCIP_CALL( SCIPsetAllocBufferArray(set, &redchilds, reoptnode->nchilds) );
4373 
4374  /* iterate over all child nodes and check each bound changes
4375  * for redundancy and conflict */
4376  for( c = 0; c < reoptnode->nchilds; c++ )
4377  {
4378  SCIP_REOPTNODE* child;
4379  SCIP_Bool cutoff;
4380  SCIP_Bool redundant;
4381  int* redundantvars;
4382  int nredundantvars;
4383  int v;
4384  unsigned int childid;
4385 
4386  cutoff = FALSE;
4387  redundant = FALSE;
4388  nredundantvars = 0;
4389 
4390  childid = reoptnode->childids[c];
4391  assert(childid < reopt->reopttree->reoptnodessize);
4392  child = reopt->reopttree->reoptnodes[childid];
4393  assert(child != NULL);
4394 #ifdef SCIP_MORE_DEBUG
4395  SCIPsetDebugMsg(set, "-> check child at ID %d (%d vars, %d conss):\n", childid, child->nvars, child->nconss);
4396 #endif
4397  if( child->nvars > 0 )
4398  {
4399  /* allocate buffer memory to store the redundant variables */
4400  SCIP_CALL( SCIPsetAllocBufferArray(set, &redundantvars, child->nvars) );
4401 
4402  for( v = 0; v < child->nvars && !cutoff; v++ )
4403  {
4404  SCIP_VAR* transvar;
4405  SCIP_Real transval;
4406  SCIP_BOUNDTYPE transbndtype;
4407  SCIP_Real ub;
4408  SCIP_Real lb;
4409 
4410  transvar = child->vars[v];
4411  transval = child->varbounds[v];
4412  transbndtype = child->varboundtypes[v];
4413 
4414  /* transform into the transformed space */
4415  SCIP_CALL( SCIPvarGetProbvarBound(&transvar, &transval, &transbndtype) );
4416 
4417  lb = SCIPvarGetLbLocal(transvar);
4418  ub = SCIPvarGetUbLocal(transvar);
4419 
4420  /* check for infeasibility */
4421  if( SCIPsetIsFeasEQ(set, lb, ub) && !SCIPsetIsFeasEQ(set, lb, transval) )
4422  {
4423  SCIPsetDebugMsg(set, " -> <%s> is fixed to %g, can not change bound to %g -> cutoff\n",
4424  SCIPvarGetName(transvar), lb, transval);
4425 
4426  cutoff = TRUE;
4427  break;
4428  }
4429 
4430  /* check for redundancy */
4431  if( SCIPsetIsFeasEQ(set, lb, ub) && SCIPsetIsFeasEQ(set, lb, transval) )
4432  {
4433  SCIPsetDebugMsg(set, " -> <%s> is already fixed to %g -> redundant bound change\n",
4434  SCIPvarGetName(transvar), lb);
4435 
4436  redundantvars[nredundantvars] = v;
4437  ++nredundantvars;
4438  }
4439  }
4440 
4441  if( !cutoff && nredundantvars > 0 )
4442  {
4443  for( v = 0; v < nredundantvars; v++ )
4444  {
4445  /* replace the redundant variable by the last stored variable */
4446  child->vars[redundantvars[v]] = child->vars[child->nvars-1];
4447  child->varbounds[redundantvars[v]] = child->varbounds[child->nvars-1];
4448  child->varboundtypes[redundantvars[v]] = child->varboundtypes[child->nvars-1];
4449  --child->nvars;
4450  }
4451  }
4452 
4453  /* free buffer memory */
4454  SCIPsetFreeBufferArray(set, &redundantvars);
4455  }
4456  else if( child->nconss == 0 )
4457  {
4458  redundant = TRUE;
4459  SCIPsetDebugMsg(set, " -> redundant node found.\n");
4460  }
4461 
4462  if( cutoff )
4463  {
4464  cutoffchilds[ncutoffchilds] = childid;
4465  ++ncutoffchilds;
4466  }
4467  else if( redundant )
4468  {
4469  redchilds[nredchilds] = childid;
4470  ++nredchilds;
4471  }
4472  }
4473 
4474  SCIPsetDebugMsg(set, "-> found %d redundant and %d infeasible nodes\n", nredchilds, ncutoffchilds);
4475 
4476  /* delete all nodes that can be cut off */
4477  while( ncutoffchilds > 0 )
4478  {
4479  /* delete the node and the induced subtree */
4480  SCIP_CALL( deleteChildrenBelow(reopt->reopttree, set, blkmem, cutoffchilds[ncutoffchilds-1], TRUE, TRUE) );
4481 
4482  /* find the position in the childid array */
4483  c = 0;
4484  while( reoptnode->childids[c] != cutoffchilds[ncutoffchilds-1] && c < reoptnode->nchilds )
4485  ++c;
4486  assert(reoptnode->childids[c] == cutoffchilds[ncutoffchilds-1]);
4487 
4488  /* replace the ID at position c by the last ID */
4489  reoptnode->childids[c] = reoptnode->childids[reoptnode->nchilds-1];
4490  --reoptnode->nchilds;
4491 
4492  /* decrease the number of nodes to cutoff */
4493  --ncutoffchilds;
4494  }
4495 
4496  /* replace all redundant nodes their child nodes or cutoff the node if it is a leaf */
4497  while( nredchilds > 0 )
4498  {
4499  /* find the position in the childid array */
4500  c = 0;
4501  while( reoptnode->childids[c] != redchilds[nredchilds-1] && c < reoptnode->nchilds )
4502  ++c;
4503  assert(reoptnode->childids[c] == redchilds[nredchilds-1]);
4504 
4505  /* the node is a leaf and we can cutoff them */
4506  if( reopt->reopttree->reoptnodes[redchilds[nredchilds-1]]->nchilds == 0 )
4507  {
4508  /* delete the node and the induced subtree */
4509  SCIP_CALL( deleteChildrenBelow(reopt->reopttree, set, blkmem, redchilds[nredchilds-1], TRUE, TRUE) );
4510 
4511  /* replace the ID at position c by the last ID */
4512  reoptnode->childids[c] = reoptnode->childids[reoptnode->nchilds-1];
4513  --reoptnode->nchilds;
4514 
4515  /* decrease the number of redundant nodes */
4516  --nredchilds;
4517  }
4518  else
4519  {
4520  int cc;
4521  int ncc;
4522 
4523  /* replace the ID at position c by the last ID */
4524  reoptnode->childids[c] = reoptnode->childids[reoptnode->nchilds-1];
4525  --reoptnode->nchilds;
4526 
4527  ncc = reopt->reopttree->reoptnodes[redchilds[nredchilds-1]]->nchilds;
4528 
4529  /* check the memory */
4530  SCIP_CALL( reoptnodeCheckMemory(reopt->reopttree->reoptnodes[id], set, blkmem, 0, reoptnode->nchilds+ncc, 0) );
4531 
4532  /* add all IDs of child nodes to the current node */
4533  for( cc = 0; cc < ncc; cc++ )
4534  {
4535  reoptnode->childids[reoptnode->nchilds] = reopt->reopttree->reoptnodes[redchilds[nredchilds-1]]->childids[cc];
4536  ++reoptnode->nchilds;
4537  }
4538 
4539  /* delete the redundant node */
4540  SCIP_CALL( reopttreeDeleteNode(reopt->reopttree, set, blkmem, redchilds[nredchilds-1], TRUE) );
4541  SCIP_CALL( SCIPqueueInsertUInt(reopt->reopttree->openids, redchilds[nredchilds-1]) );
4542 
4543  /* decrease the number of redundant nodes */
4544  --nredchilds;
4545 
4546  /* update the flag to rerun this method */
4547  *runagain = TRUE;
4548  }
4549  }
4550 
4551  /* free buffer arrays */
4552  SCIPsetFreeBufferArray(set, &redchilds);
4553  SCIPsetFreeBufferArray(set, &cutoffchilds);
4554 
4555  return SCIP_OKAY;
4556 }
4557 
4558 /** return the number of all nodes in the subtree induced by the reoptimization node stored at @p id */
4559 static
4561  SCIP_REOPTTREE* reopttree, /**< reopttree */
4562  unsigned int id /**< id of stored node */
4563  )
4564 {
4565  int nnodes = 0;
4566  int i;
4567 
4568  assert(reopttree != NULL);
4569  assert(id < reopttree->reoptnodessize);
4570 
4571  for( i = 0; i < reopttree->reoptnodes[id]->nchilds; i++ )
4572  nnodes += reopttreeGetNNodes(reopttree, reopttree->reoptnodes[id]->childids[i]);
4573 
4574  return nnodes + 1;
4575 }
4576 
4577 /** returns the number of leaf nodes of the induced subtree */
4578 static
4580  SCIP_REOPT* reopt, /**< reoptimization data structure */
4581  unsigned int id /**< id of stored node */
4582  )
4583 {
4584  int i;
4585  int nleaves = 0;
4586 
4587  assert(reopt != NULL);
4588  assert(id < reopt->reopttree->reoptnodessize);
4589  assert(reopt->reopttree->reoptnodes[id] != NULL);
4590 
4591  /* iterate over all child nods and check whether they are leaves or not */
4592  for( i = 0; i < reopt->reopttree->reoptnodes[id]->nchilds; i++ )
4593  {
4594  unsigned int childid;
4595 
4596  childid = reopt->reopttree->reoptnodes[id]->childids[i];
4597  assert(childid < reopt->reopttree->reoptnodessize);
4598 
4599  if( reopt->reopttree->reoptnodes[childid]->nchilds == 0 )
4600  ++nleaves;
4601  else
4602  nleaves += reoptGetNLeaves(reopt, childid);
4603  }
4604 
4605  return nleaves;
4606 }
4607 
4608 /** returns all leaves of the subtree induced by the node stored at @p id*/
4609 static
4611  SCIP_REOPT* reopt, /**< reoptimization data structure*/
4612  unsigned int id, /**< id of stored node */
4613  unsigned int* leaves, /**< array of leave nodes */
4614  int leavessize, /**< size of leaves array */
4615  int* nleaves /**< pointer to store the number of leave nodes */
4616  )
4617 {
4618  int i;
4619  int l;
4620 
4621  assert(reopt != NULL);
4622  assert(leavessize > 0 && leaves != NULL);
4623  assert((*nleaves) >= 0);
4624  assert(id < reopt->reopttree->reoptnodessize);
4625  assert(reopt->reopttree->reoptnodes[id] != NULL);
4626 
4627  for( i = 0, l = 0; i < reopt->reopttree->reoptnodes[id]->nchilds; i++ )
4628  {
4629  unsigned int childid;
4630 
4631  assert(*nleaves <= leavessize);
4632 
4633  childid = reopt->reopttree->reoptnodes[id]->childids[i];
4634  assert(childid < reopt->reopttree->reoptnodessize);
4635 
4636  if( reopt->reopttree->reoptnodes[childid]->nchilds == 0 )
4637  {
4638  leaves[l] = reopt->reopttree->reoptnodes[id]->childids[i];
4639  ++l;
4640  ++(*nleaves);
4641  }
4642  else
4643  {
4644  int nleaves2 = 0;
4645 
4646  SCIP_CALL( reoptGetLeaves(reopt, childid, &leaves[l], leavessize - l, &nleaves2) );
4647  l += nleaves2;
4648  (*nleaves) += nleaves2;
4649  }
4650  }
4651 
4652  return SCIP_OKAY;
4653 }
4654 
4655 /** after restarting the reoptimization and an after compressing the search tree we have to delete all stored information */
4656 static
4658  SCIP_REOPT* reopt, /**< reoptimization data structure */
4659  SCIP_SET* set, /**< global SCIP settings */
4660  BMS_BLKMEM* blkmem, /**< block memory */
4661  SCIP_Bool softreset /**< mark the nodes to overwriteable (TRUE) or delete them completely (FALSE) */
4662  )
4663 {
4664  assert(reopt != NULL);
4665  assert(set != NULL);
4666  assert(blkmem != NULL);
4667 
4668  /* clear the tree */
4669  SCIP_CALL( clearReoptnodes(reopt->reopttree, set, blkmem, softreset) );
4670  assert(reopt->reopttree->nreoptnodes == 0);
4671 
4672  /* reset the dual constraint */
4673  if( reopt->dualreds != NULL )
4674  reopt->dualreds->nvars = 0;
4675 
4676  reopt->currentnode = -1;
4677 
4678  return SCIP_OKAY;
4679 }
4680 
4681 /** restart the reoptimization by removing all stored information about nodes and increase the number of restarts */
4682 static
4684  SCIP_REOPT* reopt, /**< reoptimization data structure */
4685  SCIP_SET* set, /**< global SCIP settings */
4686  BMS_BLKMEM* blkmem /**< block memory */
4687  )
4688 {
4689  assert(reopt != NULL);
4690  assert(reopt->reopttree != NULL);
4691  assert(set != NULL);
4692  assert(blkmem != NULL);
4693 
4694  /* clear the tree */
4695  SCIP_CALL( reoptResetTree(reopt, set, blkmem, FALSE) );
4696  assert(reopt->reopttree->nreoptnodes == 0);
4697 
4698  /* allocate memory for the root node */
4699  SCIP_CALL( createReoptnode(reopt->reopttree, set, blkmem, 0) );
4700 
4701  reopt->nglbrestarts += 1;
4702 
4703  if( reopt->firstrestart == -1 )
4704  reopt->firstrestart = reopt->run;
4705 
4706  reopt->lastrestart = reopt->run;
4707 
4708  return SCIP_OKAY;
4709 }
4710 
4711 /** save the new objective function */
4712 static
4714  SCIP_REOPT* reopt, /**< reoptimization data */
4715  SCIP_SET* set, /**< global SCIP settings */
4716  BMS_BLKMEM* blkmem, /**< block memory */
4717  SCIP_VAR** origvars, /**< original problem variables */
4718  int norigvars /**< number of original problem variables */
4719  )
4720 {
4721  int probidx;
4722  int v;
4723 
4724  assert(reopt != NULL);
4725  assert(set != NULL);
4726  assert(blkmem != NULL);
4727  assert(origvars != NULL);
4728  assert(norigvars >= 0);
4729 
4730  /* check memory */
4731  SCIP_CALL( ensureRunSize(reopt, set, reopt->run, blkmem) );
4732 
4733  /* get memory and check whether we have to resize all previous objectives */
4734  if( reopt->nobjvars < norigvars )
4735  {
4736  int i;
4737  for( i = 0; i < reopt->run-1; i++ )
4738  {
4739  SCIP_ALLOC( BMSreallocMemoryArray(&reopt->objs[i], norigvars) ); /*lint !e866*/
4740  for( v = reopt->nobjvars-1; v < norigvars; v++ )
4741  reopt->objs[i][v] = 0.0;
4742  }
4743  reopt->nobjvars = norigvars;
4744  }
4745  SCIP_ALLOC( BMSallocClearMemoryArray(&reopt->objs[reopt->run-1], reopt->nobjvars) ); /*lint !e866*/
4746 
4747  /* save coefficients */
4748  for( v = 0; v < norigvars; v++ )
4749  {
4750  assert(SCIPvarIsOriginal(origvars[v]));
4751 
4752  probidx = SCIPvarGetIndex(origvars[v]);
4753 
4754  /* it can happen that the index is greater than the number of problem variables,
4755  * i.e., not all created variables were added
4756  */
4757  if( probidx >= reopt->nobjvars )
4758  {
4759  int i;
4760  int j;
4761  int newsize = SCIPsetCalcMemGrowSize(set, probidx+1);
4762  for( i = 0; i < reopt->run; i++ )
4763  {
4764  SCIP_ALLOC( BMSreallocMemoryArray(&reopt->objs[i], newsize) ); /*lint !e866*/
4765  for( j = reopt->nobjvars; j < newsize; j++ )
4766  reopt->objs[i][j] = 0.0;
4767  }
4768  reopt->nobjvars = newsize;
4769  }
4770  assert(0 <= probidx && probidx < reopt->nobjvars);
4771 
4772  reopt->objs[reopt->run-1][probidx] = SCIPvarGetObj(origvars[v]);
4773 
4774  /* update flag to remember if the objective function has changed */
4775  if( !reopt->objhaschanged && reopt->run >= 2
4776  && ! SCIPsetIsEQ(set, reopt->objs[reopt->run-2][probidx], reopt->objs[reopt->run-1][probidx]) )
4777  reopt->objhaschanged = TRUE;
4778 
4779  /* mark this objective as the first non empty */
4780  if( reopt->firstobj == -1 && reopt->objs[reopt->run-1][probidx] != 0 )
4781  reopt->firstobj = reopt->run-1;
4782  }
4783 
4784  /* calculate similarity to last objective */
4785  if( reopt->run-1 >= 1 )
4786  {
4787  /* calculate similarity to last objective */
4788  reopt->simtolastobj = reoptSimilarity(reopt, set, reopt->run-1, reopt->run-2, origvars, norigvars);
4789 
4790  if( reopt->simtolastobj == SCIP_INVALID ) /*lint !e777*/
4791  return SCIP_INVALIDRESULT;
4792 
4793  SCIPverbMessage(set->scip, SCIP_VERBLEVEL_HIGH, NULL, "new objective has similarity of %g compared to previous.\n",
4794  reopt->simtolastobj);
4795  }
4796 
4797  SCIPsetDebugMsg(set, "saved obj for run %d.\n", reopt->run);
4798 
4799  return SCIP_OKAY;
4800 }
4801 
4802 /** orders the variable by inference score */
4803 static
4805  SCIP_SET* set, /**< global SCIP settings */
4806  SCIP_STAT* stat, /**< dynamic problem statistics */
4807  int* perm, /**< array of indices that need to be permuted */
4808  SCIP_VAR** vars, /**< variable array to permute */
4809  SCIP_Real* bounds, /**< bound array to permute in the same order */
4810  SCIP_BOUNDTYPE* boundtypes, /**< boundtype array to permute in the same order */
4811  int nvars /**< number of variables */
4812  )
4813 {
4814  SCIP_Real* infscore;
4815  int v;
4816 
4817  assert(set != NULL);
4818  assert(perm != NULL);
4819  assert(vars != NULL);
4820  assert(bounds != NULL);
4821  assert(boundtypes != NULL);
4822  assert(nvars >= 0);
4823 
4824  /* allocate buffer for the scores */
4825  SCIP_CALL( SCIPsetAllocBufferArray(set, &infscore, nvars) );
4826 
4827  for( v = 0; v < nvars; v++ )
4828  {
4829  if( boundtypes[v] == SCIP_BOUNDTYPE_UPPER )
4830  {
4831  infscore[v] = 0.75 * SCIPvarGetAvgInferences(vars[v], stat, SCIP_BRANCHDIR_UPWARDS)
4832  + 0.25 * SCIPvarGetAvgInferences(vars[v], stat, SCIP_BRANCHDIR_DOWNWARDS);
4833  }
4834  else
4835  {
4836  infscore[v] = 0.25 * SCIPvarGetAvgInferences(vars[v], stat, SCIP_BRANCHDIR_UPWARDS)
4837  + 0.75 * SCIPvarGetAvgInferences(vars[v], stat, SCIP_BRANCHDIR_DOWNWARDS);
4838  }
4839  }
4840 
4841  /* permute indices by inference score */
4842  SCIPsortDownRealInt(infscore, perm, nvars);
4843 
4844  /* free buffer */
4845  SCIPsetFreeBufferArray(set, &infscore);
4846 
4847  return SCIP_OKAY;
4848 }
4849 
4850 /** create a global constraint to separate the given solution */
4851 static
4853  SCIP_REOPT* reopt, /**< reoptimization data structure */
4854  BMS_BLKMEM* blkmem, /**< block memory */
4855  SCIP_SET* set, /**< global SCIP settings */
4856  SCIP_STAT* stat, /**< dynamic SCIP statistics */
4857  SCIP_SOL* sol, /**< solution to separate */
4858  SCIP_VAR** vars, /**< array of original problem variables */
4859  int nvars /**< number of original problem variables */
4860  )
4861 {
4862  SCIP_VAR** origvars;
4863  SCIP_Real* vals;
4864  int nintvars;
4865  int nbinvars;
4866  int v;
4867  int w;
4868 
4869  assert(reopt != NULL);
4870  assert(sol != NULL);
4871  assert(blkmem != NULL);
4872  assert(set != NULL);
4873  assert(stat != NULL);
4874  assert(vars != NULL);
4875  assert(nvars != 0);
4876  assert(SCIPsolIsOriginal(sol));
4877 
4878  /* allocate buffer memory */
4879  SCIP_CALL( SCIPsetAllocBufferArray(set, &origvars, nvars) );
4880  SCIP_CALL( SCIPsetAllocBufferArray(set, &vals, nvars) );
4881 
4882  nbinvars = 0;
4883  nintvars = 0;
4884 
4885  /* get the solution values of the variables */
4886  for( v = 0, w = 0; v < nvars; v++ )
4887  {
4888  assert(SCIPvarIsOriginal(vars[v]));
4889  assert(nbinvars + nintvars == w);
4890 
4891  /* we do not want to create cuts for continous variables */
4892  if( SCIPvarGetType(vars[v]) == SCIP_VARTYPE_CONTINUOUS )
4893  continue;
4894 
4895  if( SCIPvarGetType(vars[v]) == SCIP_VARTYPE_BINARY )
4896  ++nbinvars;
4898  ++nintvars;
4899 
4900  origvars[v] = vars[v];
4901  assert(origvars[v] != NULL);
4902  assert(SCIPvarIsOriginal(origvars[v]));
4903 
4904  vals[w] = SCIPsolGetVal(sol, set, stat, origvars[v]);
4905  ++w;
4906  }
4907 
4908  SCIP_CALL( addGlobalCut(reopt, blkmem, set, origvars, vals, NULL, w, nbinvars, nintvars) );
4909 
4910  /* free buffer memory */
4911  SCIPsetFreeBufferArray(set, &vals);
4912  SCIPsetFreeBufferArray(set, &origvars);
4913 
4914  return SCIP_OKAY;
4915 }
4916 
4917 /*
4918  * public methods
4919  */
4920 
4921 /* ---------------- methods of general reoptimization ---------------- */
4922 
4923 /* In debug mode, the following methods are implemented as function calls to ensure
4924  * type validity.
4925  * In optimized mode, the methods are implemented as defines to improve performance.
4926  * However, we want to have them in the library anyways, so we have to undef the defines.
4927  */
4928 
4929 #undef SCIPreoptGetNRestartsGlobal
4930 #undef SCIPreoptGetNRestartsLocal
4931 #undef SCIPreoptGetNTotalRestartsLocal
4932 #undef SCIPreoptGetFirstRestarts
4933 #undef SCIPreoptGetLastRestarts
4934 #undef SCIPreoptGetNFeasNodes
4935 #undef SCIPreoptGetNTotalFeasNodes
4936 #undef SCIPreoptGetNPrunedNodes
4937 #undef SCIPreoptGetNTotalPrunedNodes
4938 #undef SCIPreoptGetNCutoffReoptnodes
4939 #undef SCIPreoptGetNTotalCutoffReoptnodes
4940 #undef SCIPreoptGetNInfNodes
4941 #undef SCIPreoptGetNTotalInfNodes
4942 #undef SCIPreoptGetNInfSubtrees
4943 
4944 
4945 /** returns the number of global restarts */
4947  SCIP_REOPT* reopt /**< reoptimization data structure */
4948  )
4949 {
4950  assert(reopt != NULL);
4951 
4952  return reopt->nglbrestarts;
4953 }
4954 
4955 /** returns the number of local restarts in the current run */
4957  SCIP_REOPT* reopt /**< reoptimization data structure */
4958  )
4959 {
4960  assert(reopt != NULL);
4961 
4962  return reopt->nlocrestarts;
4963 }
4964 
4965 /** returns the number of local restarts over all runs */
4967  SCIP_REOPT* reopt /**< reoptimization data structure */
4968  )
4969 {
4970  assert(reopt != NULL);
4971 
4972  return reopt->ntotallocrestarts;
4973 }
4974 
4975 /** returns the number of iteration with the first global restarts */
4977  SCIP_REOPT* reopt /**< reoptimization data structure */
4978  )
4979 {
4980  assert(reopt != NULL);
4981 
4982  return reopt->firstrestart;
4983 }
4984 
4985 /** returns the number of iteration with the last global restarts */
4987  SCIP_REOPT* reopt /**< reoptimization data structure */
4988  )
4989 {
4990  assert(reopt != NULL);
4991 
4992  return reopt->lastrestart;
4993 }
4994 
4995 /** returns the number of stored nodes providing an improving feasible LP solution in the current run */
4997  SCIP_REOPT* reopt /**< reoptimization data structure */
4998  )
4999 {
5000  assert(reopt != NULL);
5001 
5002  return reopt->reopttree->nfeasnodes;
5003 }
5004 
5005 /** returns the number of stored nodes providing an improving feasible LP solution over all runs */
5007  SCIP_REOPT* reopt /**< reoptimization data structure */
5008  )
5009 {
5010  assert(reopt != NULL);
5011 
5012  return reopt->reopttree->ntotalfeasnodes;
5013 }
5014 
5015 /** returns the number of stored nodes that exceeded the cutoff bound in the current run */
5017  SCIP_REOPT* reopt /**< reoptimization data structure */
5018  )
5019 {
5020  assert(reopt != NULL);
5021 
5022  return reopt->reopttree->nprunednodes;
5023 }
5024 
5025 /** returns the number of stored nodes that exceeded the cutoff bound over all runs */
5027  SCIP_REOPT* reopt /**< reoptimization data structure */
5028  )
5029 {
5030  assert(reopt != NULL);
5031 
5032  return reopt->reopttree->ntotalprunednodes;
5033 }
5034 
5035 /** rerturns the number of reoptimized nodes that were cutoff in the same iteration in the current run */
5037  SCIP_REOPT* reopt /**< reoptimization data structure */
5038  )
5039 {
5040  assert(reopt != NULL);
5041 
5042  return reopt->reopttree->ncutoffreoptnodes;
5043 }
5044 
5045 /** rerturns the number of reoptimized nodes that were cutoff in the same iteration over all runs */
5047  SCIP_REOPT* reopt /**< reoptimization data structure */
5048  )
5049 {
5050  assert(reopt != NULL);
5051 
5052  return reopt->reopttree->ntotalcutoffreoptnodes;
5053 }
5054 
5055 /** returns the number of stored nodes with an infeasible LP in the current run */
5057  SCIP_REOPT* reopt /**< reoptimization data structure */
5058  )
5059 {
5060  assert(reopt != NULL);
5061 
5062  return reopt->reopttree->ninfnodes;
5063 }
5064 
5065 /** returns the number of stored nodes with an infeasible LP over all runs */
5067  SCIP_REOPT* reopt /**< reoptimization data structure */
5068  )
5069 {
5070  assert(reopt != NULL);
5071 
5072  return reopt->reopttree->ntotalinfnodes;
5073 }
5074 
5075 /** constructor for the reoptimization data */
5077  SCIP_REOPT** reopt, /**< pointer to reoptimization data structure */
5078  SCIP_SET* set, /**< global SCIP settings */
5079  BMS_BLKMEM* blkmem /**< block memory */
5080  )
5081 {
5082  SCIP_EVENTHDLR* eventhdlr;
5083  int i;
5084 
5085  assert(reopt != NULL);
5086 
5087  SCIP_ALLOC( BMSallocMemory(reopt) );
5088  (*reopt)->runsize = DEFAULT_MEM_RUN;
5089  (*reopt)->run = 0;
5090  (*reopt)->simtolastobj = -2.0;
5091  (*reopt)->simtofirstobj = -2.0;
5092  (*reopt)->firstobj = -1;
5093  (*reopt)->currentnode = -1;
5094  (*reopt)->lastbranched = -1;
5095  (*reopt)->dualreds = NULL;
5096  (*reopt)->glbconss = NULL;
5097  (*reopt)->nglbconss = 0;
5098  (*reopt)->allocmemglbconss = 0;
5099  (*reopt)->ncheckedsols = 0;
5100  (*reopt)->nimprovingsols = 0;
5101  (*reopt)->noptsolsbyreoptsol = 0;
5102  (*reopt)->nglbrestarts = 0;
5103  (*reopt)->nlocrestarts = 0;
5104  (*reopt)->ntotallocrestarts = 0;
5105  (*reopt)->firstrestart = -1;
5106  (*reopt)->lastrestart = 0;
5107  (*reopt)->nobjvars = 0;
5108  (*reopt)->objhaschanged = FALSE;
5109  (*reopt)->consadded = FALSE;
5110  (*reopt)->addedconss = NULL;
5111  (*reopt)->naddedconss = 0;
5112  (*reopt)->addedconsssize = 0;
5113  (*reopt)->glblb = NULL;
5114  (*reopt)->glbub = NULL;
5115  (*reopt)->nactiveconss = 0;
5116  (*reopt)->nmaxactiveconss = 0;
5117  (*reopt)->activeconss = NULL;
5118  (*reopt)->activeconssset = NULL;
5119 
5120  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*reopt)->varhistory, (*reopt)->runsize) );
5121  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*reopt)->prevbestsols, (*reopt)->runsize) );
5122  SCIP_ALLOC( BMSallocMemoryArray(&(*reopt)->objs, (*reopt)->runsize) );
5123 
5124  for( i = 0; i < (*reopt)->runsize; i++ )
5125  {
5126  (*reopt)->objs[i] = NULL;
5127  (*reopt)->prevbestsols[i] = NULL;
5128  (*reopt)->varhistory[i] = NULL;
5129  }
5130 
5131  /* clocks */
5132  SCIP_CALL( SCIPclockCreate(&(*reopt)->savingtime, SCIP_CLOCKTYPE_DEFAULT) );
5133 
5134  /* create and initialize SCIP_SOLTREE */
5135  SCIP_ALLOC( BMSallocMemory(&(*reopt)->soltree) );
5136  SCIP_CALL( createSolTree((*reopt)->soltree, blkmem) );
5137 
5138  /* create and initialize SCIP_REOPTTREE */
5139  SCIP_ALLOC( BMSallocMemory(&(*reopt)->reopttree) );
5140  SCIP_CALL( createReopttree((*reopt)->reopttree, set, blkmem) );
5141 
5142  /* create a random number generator */
5143  SCIP_CALL( SCIPrandomCreate(&(*reopt)->randnumgen, blkmem, (unsigned int)SCIPsetInitializeRandomSeed(set, DEFAULT_RANDSEED)) );
5144 
5145  /* create event handler for node events */
5146  eventhdlr = NULL;
5147 
5148  /* include event handler into SCIP */
5150  eventInitsolReopt, eventExitsolReopt, NULL, eventExecReopt, NULL) );
5151  SCIP_CALL( SCIPsetIncludeEventhdlr(set, eventhdlr) );
5152  assert(eventhdlr != NULL);
5153 
5154  return SCIP_OKAY;
5155 }
5156 
5157 /* release all variables and constraints captured during reoptimization */
5159  SCIP_REOPT* reopt, /**< pointer to reoptimization data structure */
5160  SCIP_SET* set, /**< global SCIP settings */
5161  BMS_BLKMEM* blkmem /**< block memory */
5162  )
5163 {
5164  /* release all added constraints and free the data */
5165  if( reopt->addedconss != NULL )
5166  {
5167  int c;
5168  for( c = 0; c < reopt->naddedconss; c++)
5169  {
5170  assert(reopt->addedconss[c] != NULL);
5171 
5172  SCIP_CALL( SCIPconsRelease(&reopt->addedconss[c], blkmem, set) );
5173  }
5174 
5