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