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