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