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