Scippy

SCIP

Solving Constraint Integer Programs

tree.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2019 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file tree.c
17  * @brief methods for branch and bound tree
18  * @author Tobias Achterberg
19  * @author Timo Berthold
20  * @author Gerald Gamrath
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #include <assert.h>
26 
27 #include "scip/def.h"
28 #include "scip/set.h"
29 #include "scip/stat.h"
30 #include "scip/clock.h"
31 #include "scip/visual.h"
32 #include "scip/event.h"
33 #include "scip/lp.h"
34 #include "scip/relax.h"
35 #include "scip/var.h"
36 #include "scip/implics.h"
37 #include "scip/primal.h"
38 #include "scip/tree.h"
39 #include "scip/reopt.h"
40 #include "scip/conflictstore.h"
41 #include "scip/solve.h"
42 #include "scip/cons.h"
43 #include "scip/nodesel.h"
44 #include "scip/prop.h"
45 #include "scip/debug.h"
46 #include "scip/prob.h"
47 #include "scip/scip.h"
48 #include "scip/pub_message.h"
49 #include "lpi/lpi.h"
50 
51 
52 #define MAXREPROPMARK 511 /**< maximal subtree repropagation marker; must correspond to node data structure */
53 
54 
55 /*
56  * dynamic memory arrays
57  */
58 
59 /** resizes children arrays to be able to store at least num nodes */
60 static
62  SCIP_TREE* tree, /**< branch and bound tree */
63  SCIP_SET* set, /**< global SCIP settings */
64  int num /**< minimal number of node slots in array */
65  )
66 {
67  assert(tree != NULL);
68  assert(set != NULL);
69 
70  if( num > tree->childrensize )
71  {
72  int newsize;
73 
74  newsize = SCIPsetCalcMemGrowSize(set, num);
75  SCIP_ALLOC( BMSreallocMemoryArray(&tree->children, newsize) );
76  SCIP_ALLOC( BMSreallocMemoryArray(&tree->childrenprio, newsize) );
77  tree->childrensize = newsize;
78  }
79  assert(num <= tree->childrensize);
80 
81  return SCIP_OKAY;
82 }
83 
84 /** resizes path array to be able to store at least num nodes */
85 static
87  SCIP_TREE* tree, /**< branch and bound tree */
88  SCIP_SET* set, /**< global SCIP settings */
89  int num /**< minimal number of node slots in path */
90  )
91 {
92  assert(tree != NULL);
93  assert(set != NULL);
94 
95  if( num > tree->pathsize )
96  {
97  int newsize;
98 
99  newsize = SCIPsetCalcPathGrowSize(set, num);
100  SCIP_ALLOC( BMSreallocMemoryArray(&tree->path, newsize) );
101  SCIP_ALLOC( BMSreallocMemoryArray(&tree->pathnlpcols, newsize) );
102  SCIP_ALLOC( BMSreallocMemoryArray(&tree->pathnlprows, newsize) );
103  tree->pathsize = newsize;
104  }
105  assert(num <= tree->pathsize);
106 
107  return SCIP_OKAY;
108 }
109 
110 /** resizes pendingbdchgs array to be able to store at least num nodes */
111 static
113  SCIP_TREE* tree, /**< branch and bound tree */
114  SCIP_SET* set, /**< global SCIP settings */
115  int num /**< minimal number of node slots in path */
116  )
117 {
118  assert(tree != NULL);
119  assert(set != NULL);
120 
121  if( num > tree->pendingbdchgssize )
122  {
123  int newsize;
124 
125  newsize = SCIPsetCalcMemGrowSize(set, num);
126  SCIP_ALLOC( BMSreallocMemoryArray(&tree->pendingbdchgs, newsize) );
127  tree->pendingbdchgssize = newsize;
128  }
129  assert(num <= tree->pendingbdchgssize);
130 
131  return SCIP_OKAY;
132 }
133 
134 
135 
136 
137 /*
138  * Node methods
139  */
140 
141 /** node comparator for best lower bound */
142 SCIP_DECL_SORTPTRCOMP(SCIPnodeCompLowerbound)
143 { /*lint --e{715}*/
144  assert(elem1 != NULL);
145  assert(elem2 != NULL);
146 
147  if( ((SCIP_NODE*)elem1)->lowerbound < ((SCIP_NODE*)elem2)->lowerbound )
148  return -1;
149  else if( ((SCIP_NODE*)elem1)->lowerbound > ((SCIP_NODE*)elem2)->lowerbound )
150  return +1;
151  else
152  return 0;
153 }
154 
155 /** increases the reference counter of the LP state in the fork */
156 static
158  SCIP_FORK* fork, /**< fork data */
159  int nuses /**< number to add to the usage counter */
160  )
161 {
162  assert(fork != NULL);
163  assert(fork->nlpistateref >= 0);
164  assert(nuses > 0);
165 
166  fork->nlpistateref += nuses;
167  SCIPdebugMessage("captured LPI state of fork %p %d times -> new nlpistateref=%d\n", (void*)fork, nuses, fork->nlpistateref);
168 }
169 
170 /** decreases the reference counter of the LP state in the fork */
171 static
173  SCIP_FORK* fork, /**< fork data */
174  BMS_BLKMEM* blkmem, /**< block memory buffers */
175  SCIP_LP* lp /**< current LP data */
176  )
177 {
178  assert(fork != NULL);
179  assert(fork->nlpistateref > 0);
180  assert(blkmem != NULL);
181  assert(lp != NULL);
182 
183  fork->nlpistateref--;
184  if( fork->nlpistateref == 0 )
185  {
186  SCIP_CALL( SCIPlpFreeState(lp, blkmem, &(fork->lpistate)) );
187  }
188 
189  SCIPdebugMessage("released LPI state of fork %p -> new nlpistateref=%d\n", (void*)fork, fork->nlpistateref);
190 
191  return SCIP_OKAY;
192 }
193 
194 /** increases the reference counter of the LP state in the subroot */
195 static
197  SCIP_SUBROOT* subroot, /**< subroot data */
198  int nuses /**< number to add to the usage counter */
199  )
200 {
201  assert(subroot != NULL);
202  assert(subroot->nlpistateref >= 0);
203  assert(nuses > 0);
204 
205  subroot->nlpistateref += nuses;
206  SCIPdebugMessage("captured LPI state of subroot %p %d times -> new nlpistateref=%d\n",
207  (void*)subroot, nuses, subroot->nlpistateref);
208 }
209 
210 /** decreases the reference counter of the LP state in the subroot */
211 static
213  SCIP_SUBROOT* subroot, /**< subroot data */
214  BMS_BLKMEM* blkmem, /**< block memory buffers */
215  SCIP_LP* lp /**< current LP data */
216  )
217 {
218  assert(subroot != NULL);
219  assert(subroot->nlpistateref > 0);
220  assert(blkmem != NULL);
221  assert(lp != NULL);
222 
223  subroot->nlpistateref--;
224  if( subroot->nlpistateref == 0 )
225  {
226  SCIP_CALL( SCIPlpFreeState(lp, blkmem, &(subroot->lpistate)) );
227  }
228 
229  SCIPdebugMessage("released LPI state of subroot %p -> new nlpistateref=%d\n", (void*)subroot, subroot->nlpistateref);
230 
231  return SCIP_OKAY;
232 }
233 
234 /** increases the reference counter of the LP state in the fork or subroot node */
236  SCIP_NODE* node, /**< fork/subroot node */
237  int nuses /**< number to add to the usage counter */
238  )
239 {
240  assert(node != NULL);
241 
242  SCIPdebugMessage("capture %d times LPI state of node #%" SCIP_LONGINT_FORMAT " at depth %d (current: %d)\n",
243  nuses, SCIPnodeGetNumber(node), SCIPnodeGetDepth(node),
245 
246  switch( SCIPnodeGetType(node) )
247  {
248  case SCIP_NODETYPE_FORK:
249  forkCaptureLPIState(node->data.fork, nuses);
250  break;
252  subrootCaptureLPIState(node->data.subroot, nuses);
253  break;
254  default:
255  SCIPerrorMessage("node for capturing the LPI state is neither fork nor subroot\n");
256  SCIPABORT();
257  return SCIP_INVALIDDATA; /*lint !e527*/
258  } /*lint !e788*/
259  return SCIP_OKAY;
260 }
261 
262 /** decreases the reference counter of the LP state in the fork or subroot node */
264  SCIP_NODE* node, /**< fork/subroot node */
265  BMS_BLKMEM* blkmem, /**< block memory buffers */
266  SCIP_LP* lp /**< current LP data */
267  )
268 {
269  assert(node != NULL);
270 
271  SCIPdebugMessage("release LPI state of node #%" SCIP_LONGINT_FORMAT " at depth %d (current: %d)\n",
272  SCIPnodeGetNumber(node), SCIPnodeGetDepth(node),
274  switch( SCIPnodeGetType(node) )
275  {
276  case SCIP_NODETYPE_FORK:
277  return forkReleaseLPIState(node->data.fork, blkmem, lp);
279  return subrootReleaseLPIState(node->data.subroot, blkmem, lp);
280  default:
281  SCIPerrorMessage("node for releasing the LPI state is neither fork nor subroot\n");
282  return SCIP_INVALIDDATA;
283  } /*lint !e788*/
284 }
285 
286 /** creates probingnode data without LP information */
287 static
289  SCIP_PROBINGNODE** probingnode, /**< pointer to probingnode data */
290  BMS_BLKMEM* blkmem, /**< block memory */
291  SCIP_LP* lp /**< current LP data */
292  )
293 {
294  assert(probingnode != NULL);
295 
296  SCIP_ALLOC( BMSallocBlockMemory(blkmem, probingnode) );
297 
298  (*probingnode)->lpistate = NULL;
299  (*probingnode)->lpinorms = NULL;
300  (*probingnode)->ninitialcols = SCIPlpGetNCols(lp);
301  (*probingnode)->ninitialrows = SCIPlpGetNRows(lp);
302  (*probingnode)->ncols = (*probingnode)->ninitialcols;
303  (*probingnode)->nrows = (*probingnode)->ninitialrows;
304  (*probingnode)->origobjvars = NULL;
305  (*probingnode)->origobjvals = NULL;
306  (*probingnode)->nchgdobjs = 0;
307 
308  SCIPdebugMessage("created probingnode information (%d cols, %d rows)\n", (*probingnode)->ncols, (*probingnode)->nrows);
309 
310  return SCIP_OKAY;
311 }
312 
313 /** updates LP information in probingnode data */
314 static
316  SCIP_PROBINGNODE* probingnode, /**< probingnode data */
317  BMS_BLKMEM* blkmem, /**< block memory */
318  SCIP_TREE* tree, /**< branch and bound tree */
319  SCIP_LP* lp /**< current LP data */
320  )
321 {
322  SCIP_Bool storenorms = FALSE;
323 
324  assert(probingnode != NULL);
325  assert(SCIPtreeIsPathComplete(tree));
326  assert(lp != NULL);
327 
328  /* free old LP state */
329  if( probingnode->lpistate != NULL )
330  {
331  SCIP_CALL( SCIPlpFreeState(lp, blkmem, &probingnode->lpistate) );
332  }
333 
334  /* free old LP norms */
335  if( probingnode->lpinorms != NULL )
336  {
337  SCIP_CALL( SCIPlpFreeNorms(lp, blkmem, &probingnode->lpinorms) );
338  probingnode->lpinorms = NULL;
339  storenorms = TRUE;
340  }
341 
342  /* get current LP state */
343  if( lp->flushed && lp->solved )
344  {
345  SCIP_CALL( SCIPlpGetState(lp, blkmem, &probingnode->lpistate) );
346 
347  /* if LP norms were stored at this node before, store the new ones */
348  if( storenorms )
349  {
350  SCIP_CALL( SCIPlpGetNorms(lp, blkmem, &probingnode->lpinorms) );
351  }
352  probingnode->lpwasprimfeas = lp->primalfeasible;
353  probingnode->lpwasprimchecked = lp->primalchecked;
354  probingnode->lpwasdualfeas = lp->dualfeasible;
355  probingnode->lpwasdualchecked = lp->dualchecked;
356  }
357  else
358  probingnode->lpistate = NULL;
359 
360  probingnode->ncols = SCIPlpGetNCols(lp);
361  probingnode->nrows = SCIPlpGetNRows(lp);
362 
363  SCIPdebugMessage("updated probingnode information (%d cols, %d rows)\n", probingnode->ncols, probingnode->nrows);
364 
365  return SCIP_OKAY;
366 }
367 
368 /** frees probingnode data */
369 static
371  SCIP_PROBINGNODE** probingnode, /**< probingnode data */
372  BMS_BLKMEM* blkmem, /**< block memory */
373  SCIP_LP* lp /**< current LP data */
374  )
375 {
376  assert(probingnode != NULL);
377  assert(*probingnode != NULL);
378 
379  /* free the associated LP state */
380  if( (*probingnode)->lpistate != NULL )
381  {
382  SCIP_CALL( SCIPlpFreeState(lp, blkmem, &(*probingnode)->lpistate) );
383  }
384  /* free the associated LP norms */
385  if( (*probingnode)->lpinorms != NULL )
386  {
387  SCIP_CALL( SCIPlpFreeNorms(lp, blkmem, &(*probingnode)->lpinorms) );
388  }
389 
390  /* free objective information */
391  if( (*probingnode)->nchgdobjs > 0 )
392  {
393  assert((*probingnode)->origobjvars != NULL);
394  assert((*probingnode)->origobjvals != NULL);
395 
396  BMSfreeMemoryArray(&(*probingnode)->origobjvars);
397  BMSfreeMemoryArray(&(*probingnode)->origobjvals);
398  }
399 
400  BMSfreeBlockMemory(blkmem, probingnode);
401 
402  return SCIP_OKAY;
403 }
404 
405 /** initializes junction data */
406 static
408  SCIP_JUNCTION* junction, /**< pointer to junction data */
409  SCIP_TREE* tree /**< branch and bound tree */
410  )
411 {
412  assert(junction != NULL);
413  assert(tree != NULL);
414  assert(tree->nchildren > 0);
415  assert(SCIPtreeIsPathComplete(tree));
416  assert(tree->focusnode != NULL);
417 
418  junction->nchildren = tree->nchildren;
419 
420  /* increase the LPI state usage counter of the current LP fork */
421  if( tree->focuslpstatefork != NULL )
422  {
424  }
425 
426  return SCIP_OKAY;
427 }
428 
429 /** creates pseudofork data */
430 static
432  SCIP_PSEUDOFORK** pseudofork, /**< pointer to pseudofork data */
433  BMS_BLKMEM* blkmem, /**< block memory */
434  SCIP_TREE* tree, /**< branch and bound tree */
435  SCIP_LP* lp /**< current LP data */
436  )
437 {
438  assert(pseudofork != NULL);
439  assert(blkmem != NULL);
440  assert(tree != NULL);
441  assert(tree->nchildren > 0);
442  assert(SCIPtreeIsPathComplete(tree));
443  assert(tree->focusnode != NULL);
444 
445  SCIP_ALLOC( BMSallocBlockMemory(blkmem, pseudofork) );
446 
447  (*pseudofork)->addedcols = NULL;
448  (*pseudofork)->addedrows = NULL;
449  (*pseudofork)->naddedcols = SCIPlpGetNNewcols(lp);
450  (*pseudofork)->naddedrows = SCIPlpGetNNewrows(lp);
451  (*pseudofork)->nchildren = tree->nchildren;
452 
453  SCIPdebugMessage("creating pseudofork information with %d children (%d new cols, %d new rows)\n",
454  (*pseudofork)->nchildren, (*pseudofork)->naddedcols, (*pseudofork)->naddedrows);
455 
456  if( (*pseudofork)->naddedcols > 0 )
457  {
458  /* copy the newly created columns to the pseudofork's col array */
459  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*pseudofork)->addedcols, SCIPlpGetNewcols(lp), (*pseudofork)->naddedcols) ); /*lint !e666*/
460  }
461  if( (*pseudofork)->naddedrows > 0 )
462  {
463  int i;
464 
465  /* copy the newly created rows to the pseudofork's row array */
466  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*pseudofork)->addedrows, SCIPlpGetNewrows(lp), (*pseudofork)->naddedrows) ); /*lint !e666*/
467 
468  /* capture the added rows */
469  for( i = 0; i < (*pseudofork)->naddedrows; ++i )
470  SCIProwCapture((*pseudofork)->addedrows[i]);
471  }
472 
473  /* increase the LPI state usage counter of the current LP fork */
474  if( tree->focuslpstatefork != NULL )
475  {
477  }
478 
479  return SCIP_OKAY;
480 }
481 
482 /** frees pseudofork data */
483 static
485  SCIP_PSEUDOFORK** pseudofork, /**< pseudofork data */
486  BMS_BLKMEM* blkmem, /**< block memory */
487  SCIP_SET* set, /**< global SCIP settings */
488  SCIP_LP* lp /**< current LP data */
489  )
490 {
491  int i;
492 
493  assert(pseudofork != NULL);
494  assert(*pseudofork != NULL);
495  assert((*pseudofork)->nchildren == 0);
496  assert(blkmem != NULL);
497  assert(set != NULL);
498 
499  /* release the added rows */
500  for( i = 0; i < (*pseudofork)->naddedrows; ++i )
501  {
502  SCIP_CALL( SCIProwRelease(&(*pseudofork)->addedrows[i], blkmem, set, lp) );
503  }
504 
505  BMSfreeBlockMemoryArrayNull(blkmem, &(*pseudofork)->addedcols, (*pseudofork)->naddedcols);
506  BMSfreeBlockMemoryArrayNull(blkmem, &(*pseudofork)->addedrows, (*pseudofork)->naddedrows);
507  BMSfreeBlockMemory(blkmem, pseudofork);
508 
509  return SCIP_OKAY;
510 }
511 
512 /** creates fork data */
513 static
515  SCIP_FORK** fork, /**< pointer to fork data */
516  BMS_BLKMEM* blkmem, /**< block memory */
517  SCIP_SET* set, /**< global SCIP settings */
518  SCIP_PROB* prob, /**< transformed problem after presolve */
519  SCIP_TREE* tree, /**< branch and bound tree */
520  SCIP_LP* lp /**< current LP data */
521  )
522 {
523  assert(fork != NULL);
524  assert(blkmem != NULL);
525  assert(tree != NULL);
526  assert(tree->nchildren > 0);
527  assert(tree->nchildren < (1 << 30));
528  assert(SCIPtreeIsPathComplete(tree));
529  assert(tree->focusnode != NULL);
530  assert(lp != NULL);
531  assert(lp->flushed);
532  assert(lp->solved);
534 
535  SCIP_ALLOC( BMSallocBlockMemory(blkmem, fork) );
536 
537  SCIP_CALL( SCIPlpGetState(lp, blkmem, &((*fork)->lpistate)) );
538  (*fork)->lpwasprimfeas = lp->primalfeasible;
539  (*fork)->lpwasprimchecked = lp->primalchecked;
540  (*fork)->lpwasdualfeas = lp->dualfeasible;
541  (*fork)->lpwasdualchecked = lp->dualchecked;
542  (*fork)->lpobjval = SCIPlpGetObjval(lp, set, prob);
543  (*fork)->nlpistateref = 0;
544  (*fork)->addedcols = NULL;
545  (*fork)->addedrows = NULL;
546  (*fork)->naddedcols = SCIPlpGetNNewcols(lp);
547  (*fork)->naddedrows = SCIPlpGetNNewrows(lp);
548  (*fork)->nchildren = (unsigned int) tree->nchildren;
549 
550  SCIPsetDebugMsg(set, "creating fork information with %u children (%d new cols, %d new rows)\n", (*fork)->nchildren, (*fork)->naddedcols, (*fork)->naddedrows);
551 
552  if( (*fork)->naddedcols > 0 )
553  {
554  /* copy the newly created columns to the fork's col array */
555  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*fork)->addedcols, SCIPlpGetNewcols(lp), (*fork)->naddedcols) ); /*lint !e666*/
556  }
557  if( (*fork)->naddedrows > 0 )
558  {
559  int i;
560 
561  /* copy the newly created rows to the fork's row array */
562  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*fork)->addedrows, SCIPlpGetNewrows(lp), (*fork)->naddedrows) ); /*lint !e666*/
563 
564  /* capture the added rows */
565  for( i = 0; i < (*fork)->naddedrows; ++i )
566  SCIProwCapture((*fork)->addedrows[i]);
567  }
568 
569  /* capture the LPI state for the children */
570  forkCaptureLPIState(*fork, tree->nchildren);
571 
572  return SCIP_OKAY;
573 }
574 
575 /** frees fork data */
576 static
578  SCIP_FORK** fork, /**< fork data */
579  BMS_BLKMEM* blkmem, /**< block memory */
580  SCIP_SET* set, /**< global SCIP settings */
581  SCIP_LP* lp /**< current LP data */
582  )
583 {
584  int i;
585 
586  assert(fork != NULL);
587  assert(*fork != NULL);
588  assert((*fork)->nchildren == 0);
589  assert((*fork)->nlpistateref == 0);
590  assert((*fork)->lpistate == NULL);
591  assert(blkmem != NULL);
592  assert(set != NULL);
593  assert(lp != NULL);
594 
595  /* release the added rows */
596  for( i = (*fork)->naddedrows - 1; i >= 0; --i )
597  {
598  SCIP_CALL( SCIProwRelease(&(*fork)->addedrows[i], blkmem, set, lp) );
599  }
600 
601  BMSfreeBlockMemoryArrayNull(blkmem, &(*fork)->addedcols, (*fork)->naddedcols);
602  BMSfreeBlockMemoryArrayNull(blkmem, &(*fork)->addedrows, (*fork)->naddedrows);
603  BMSfreeBlockMemory(blkmem, fork);
604 
605  return SCIP_OKAY;
606 }
607 
608 #ifdef WITHSUBROOTS /** @todo test whether subroots should be created */
609 /** creates subroot data */
610 static
611 SCIP_RETCODE subrootCreate(
612  SCIP_SUBROOT** subroot, /**< pointer to subroot data */
613  BMS_BLKMEM* blkmem, /**< block memory */
614  SCIP_SET* set, /**< global SCIP settings */
615  SCIP_PROB* prob, /**< transformed problem after presolve */
616  SCIP_TREE* tree, /**< branch and bound tree */
617  SCIP_LP* lp /**< current LP data */
618  )
619 {
620  int i;
621 
622  assert(subroot != NULL);
623  assert(blkmem != NULL);
624  assert(tree != NULL);
625  assert(tree->nchildren > 0);
626  assert(SCIPtreeIsPathComplete(tree));
627  assert(tree->focusnode != NULL);
628  assert(lp != NULL);
629  assert(lp->flushed);
630  assert(lp->solved);
632 
633  SCIP_ALLOC( BMSallocBlockMemory(blkmem, subroot) );
634  (*subroot)->lpobjval = SCIPlpGetObjval(lp, set, prob);
635  (*subroot)->nlpistateref = 0;
636  (*subroot)->ncols = SCIPlpGetNCols(lp);
637  (*subroot)->nrows = SCIPlpGetNRows(lp);
638  (*subroot)->nchildren = (unsigned int) tree->nchildren;
639  SCIP_CALL( SCIPlpGetState(lp, blkmem, &((*subroot)->lpistate)) );
640  (*subroot)->lpwasprimfeas = lp->primalfeasible;
641  (*subroot)->lpwasprimchecked = lp->primalchecked;
642  (*subroot)->lpwasdualfeas = lp->dualfeasible;
643  (*subroot)->lpwasdualchecked = lp->dualchecked;
644 
645  if( (*subroot)->ncols != 0 )
646  {
647  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*subroot)->cols, SCIPlpGetCols(lp), (*subroot)->ncols) );
648  }
649  else
650  (*subroot)->cols = NULL;
651  if( (*subroot)->nrows != 0 )
652  {
653  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*subroot)->rows, SCIPlpGetRows(lp), (*subroot)->nrows) );
654  }
655  else
656  (*subroot)->rows = NULL;
657 
658  /* capture the rows of the subroot */
659  for( i = 0; i < (*subroot)->nrows; ++i )
660  SCIProwCapture((*subroot)->rows[i]);
661 
662  /* capture the LPI state for the children */
663  subrootCaptureLPIState(*subroot, tree->nchildren);
664 
665  return SCIP_OKAY;
666 }
667 #endif
668 
669 /** frees subroot */
670 static
672  SCIP_SUBROOT** subroot, /**< subroot data */
673  BMS_BLKMEM* blkmem, /**< block memory */
674  SCIP_SET* set, /**< global SCIP settings */
675  SCIP_LP* lp /**< current LP data */
676  )
677 {
678  int i;
679 
680  assert(subroot != NULL);
681  assert(*subroot != NULL);
682  assert((*subroot)->nchildren == 0);
683  assert((*subroot)->nlpistateref == 0);
684  assert((*subroot)->lpistate == NULL);
685  assert(blkmem != NULL);
686  assert(set != NULL);
687  assert(lp != NULL);
688 
689  /* release the rows of the subroot */
690  for( i = 0; i < (*subroot)->nrows; ++i )
691  {
692  SCIP_CALL( SCIProwRelease(&(*subroot)->rows[i], blkmem, set, lp) );
693  }
694 
695  BMSfreeBlockMemoryArrayNull(blkmem, &(*subroot)->cols, (*subroot)->ncols);
696  BMSfreeBlockMemoryArrayNull(blkmem, &(*subroot)->rows, (*subroot)->nrows);
697  BMSfreeBlockMemory(blkmem, subroot);
698 
699  return SCIP_OKAY;
700 }
701 
702 /** removes given sibling node from the siblings array */
703 static
705  SCIP_TREE* tree, /**< branch and bound tree */
706  SCIP_NODE* sibling /**< sibling node to remove */
707  )
708 {
709  int delpos;
710 
711  assert(tree != NULL);
712  assert(sibling != NULL);
713  assert(SCIPnodeGetType(sibling) == SCIP_NODETYPE_SIBLING);
714  assert(sibling->data.sibling.arraypos >= 0 && sibling->data.sibling.arraypos < tree->nsiblings);
715  assert(tree->siblings[sibling->data.sibling.arraypos] == sibling);
716  assert(SCIPnodeGetType(tree->siblings[tree->nsiblings-1]) == SCIP_NODETYPE_SIBLING);
717 
718  delpos = sibling->data.sibling.arraypos;
719 
720  /* move last sibling in array to position of removed sibling */
721  tree->siblings[delpos] = tree->siblings[tree->nsiblings-1];
722  tree->siblingsprio[delpos] = tree->siblingsprio[tree->nsiblings-1];
723  tree->siblings[delpos]->data.sibling.arraypos = delpos;
724  sibling->data.sibling.arraypos = -1;
725  tree->nsiblings--;
726 }
727 
728 /** adds given child node to children array of focus node */
729 static
731  SCIP_TREE* tree, /**< branch and bound tree */
732  SCIP_SET* set, /**< global SCIP settings */
733  SCIP_NODE* child, /**< child node to add */
734  SCIP_Real nodeselprio /**< node selection priority of child node */
735  )
736 {
737  assert(tree != NULL);
738  assert(child != NULL);
739  assert(SCIPnodeGetType(child) == SCIP_NODETYPE_CHILD);
740  assert(child->data.child.arraypos == -1);
741 
742  SCIP_CALL( treeEnsureChildrenMem(tree, set, tree->nchildren+1) );
743  tree->children[tree->nchildren] = child;
744  tree->childrenprio[tree->nchildren] = nodeselprio;
745  child->data.child.arraypos = tree->nchildren;
746  tree->nchildren++;
747 
748  return SCIP_OKAY;
749 }
750 
751 /** removes given child node from the children array */
752 static
754  SCIP_TREE* tree, /**< branch and bound tree */
755  SCIP_NODE* child /**< child node to remove */
756  )
757 {
758  int delpos;
759 
760  assert(tree != NULL);
761  assert(child != NULL);
762  assert(SCIPnodeGetType(child) == SCIP_NODETYPE_CHILD);
763  assert(child->data.child.arraypos >= 0 && child->data.child.arraypos < tree->nchildren);
764  assert(tree->children[child->data.child.arraypos] == child);
765  assert(SCIPnodeGetType(tree->children[tree->nchildren-1]) == SCIP_NODETYPE_CHILD);
766 
767  delpos = child->data.child.arraypos;
768 
769  /* move last child in array to position of removed child */
770  tree->children[delpos] = tree->children[tree->nchildren-1];
771  tree->childrenprio[delpos] = tree->childrenprio[tree->nchildren-1];
772  tree->children[delpos]->data.child.arraypos = delpos;
773  child->data.child.arraypos = -1;
774  tree->nchildren--;
775 }
776 
777 /** makes node a child of the given parent node, which must be the focus node; if the child is a probing node,
778  * the parent node can also be a refocused node or a probing node
779  */
780 static
782  SCIP_NODE* node, /**< child node */
783  BMS_BLKMEM* blkmem, /**< block memory buffers */
784  SCIP_SET* set, /**< global SCIP settings */
785  SCIP_TREE* tree, /**< branch and bound tree */
786  SCIP_NODE* parent, /**< parent (= focus) node (or NULL, if node is root) */
787  SCIP_Real nodeselprio /**< node selection priority of child node */
788  )
789 {
790  assert(node != NULL);
791  assert(node->parent == NULL);
793  assert(node->conssetchg == NULL);
794  assert(node->domchg == NULL);
795  assert(SCIPsetIsInfinity(set, -node->lowerbound)); /* node was just created */
796  assert(blkmem != NULL);
797  assert(set != NULL);
798  assert(tree != NULL);
799  assert(SCIPtreeIsPathComplete(tree));
800  assert(tree->pathlen == 0 || tree->path[tree->pathlen-1] == parent);
801  assert(parent == tree->focusnode || SCIPnodeGetType(parent) == SCIP_NODETYPE_PROBINGNODE);
802  assert(parent == NULL || SCIPnodeGetType(parent) == SCIP_NODETYPE_FOCUSNODE
806 
807  /* link node to parent */
808  node->parent = parent;
809  if( parent != NULL )
810  {
811  assert(parent->lowerbound <= parent->estimate);
812  node->lowerbound = parent->lowerbound;
813  node->estimate = parent->estimate;
814  node->depth = parent->depth+1; /*lint !e732*/
815  if( parent->depth >= SCIP_MAXTREEDEPTH )
816  {
817  SCIPerrorMessage("maximal depth level exceeded\n");
818  return SCIP_MAXDEPTHLEVEL;
819  }
820  }
821  SCIPsetDebugMsg(set, "assigning parent #%" SCIP_LONGINT_FORMAT " to node #%" SCIP_LONGINT_FORMAT " at depth %d\n",
822  parent != NULL ? SCIPnodeGetNumber(parent) : -1, SCIPnodeGetNumber(node), SCIPnodeGetDepth(node));
823 
824  /* register node in the childlist of the focus (the parent) node */
825  if( SCIPnodeGetType(node) == SCIP_NODETYPE_CHILD )
826  {
827  assert(parent == NULL || SCIPnodeGetType(parent) == SCIP_NODETYPE_FOCUSNODE);
828  SCIP_CALL( treeAddChild(tree, set, node, nodeselprio) );
829  }
830 
831  return SCIP_OKAY;
832 }
833 
834 /** decreases number of children of the parent, frees it if no children are left */
835 static
837  SCIP_NODE* node, /**< child node */
838  BMS_BLKMEM* blkmem, /**< block memory buffer */
839  SCIP_SET* set, /**< global SCIP settings */
840  SCIP_STAT* stat, /**< problem statistics */
841  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
842  SCIP_TREE* tree, /**< branch and bound tree */
843  SCIP_LP* lp /**< current LP data */
844  )
845 {
846  SCIP_NODE* parent;
847 
848  assert(node != NULL);
849  assert(blkmem != NULL);
850  assert(tree != NULL);
851 
852  SCIPsetDebugMsg(set, "releasing parent-child relationship of node #%" SCIP_LONGINT_FORMAT " at depth %d of type %d with parent #%" SCIP_LONGINT_FORMAT " of type %d\n",
854  node->parent != NULL ? SCIPnodeGetNumber(node->parent) : -1,
855  node->parent != NULL ? (int)SCIPnodeGetType(node->parent) : -1);
856  parent = node->parent;
857  if( parent != NULL )
858  {
859  SCIP_Bool freeParent;
860  SCIP_Bool singleChild;
861 
862  freeParent = FALSE;
863  singleChild = FALSE;
864  switch( SCIPnodeGetType(parent) )
865  {
867  assert(parent->active);
869  || SCIPnodeGetType(node) == SCIP_NODETYPE_LEAF);
870  if( SCIPnodeGetType(node) == SCIP_NODETYPE_CHILD )
871  treeRemoveChild(tree, node);
872  /* don't kill the focus node at this point => freeParent = FALSE */
873  break;
875  assert(SCIPtreeProbing(tree));
876  /* probing nodes have to be freed individually => freeParent = FALSE */
877  break;
879  SCIPerrorMessage("sibling cannot be a parent node\n");
880  return SCIP_INVALIDDATA;
881  case SCIP_NODETYPE_CHILD:
882  SCIPerrorMessage("child cannot be a parent node\n");
883  return SCIP_INVALIDDATA;
884  case SCIP_NODETYPE_LEAF:
885  SCIPerrorMessage("leaf cannot be a parent node\n");
886  return SCIP_INVALIDDATA;
888  SCIPerrorMessage("dead-end cannot be a parent node\n");
889  return SCIP_INVALIDDATA;
891  assert(parent->data.junction.nchildren > 0);
892  parent->data.junction.nchildren--;
893  freeParent = (parent->data.junction.nchildren == 0); /* free parent if it has no more children */
894  singleChild = (parent->data.junction.nchildren == 1);
895  break;
897  assert(parent->data.pseudofork != NULL);
898  assert(parent->data.pseudofork->nchildren > 0);
899  parent->data.pseudofork->nchildren--;
900  freeParent = (parent->data.pseudofork->nchildren == 0); /* free parent if it has no more children */
901  singleChild = (parent->data.pseudofork->nchildren == 1);
902  break;
903  case SCIP_NODETYPE_FORK:
904  assert(parent->data.fork != NULL);
905  assert(parent->data.fork->nchildren > 0);
906  parent->data.fork->nchildren--;
907  freeParent = (parent->data.fork->nchildren == 0); /* free parent if it has no more children */
908  singleChild = (parent->data.fork->nchildren == 1);
909  break;
911  assert(parent->data.subroot != NULL);
912  assert(parent->data.subroot->nchildren > 0);
913  parent->data.subroot->nchildren--;
914  freeParent = (parent->data.subroot->nchildren == 0); /* free parent if it has no more children */
915  singleChild = (parent->data.subroot->nchildren == 1);
916  break;
918  /* the only possible child a refocused node can have in its refocus state is the probing root node;
919  * we don't want to free the refocused node, because we first have to convert it back to its original
920  * type (where it possibly has children) => freeParent = FALSE
921  */
923  assert(!SCIPtreeProbing(tree));
924  break;
925  default:
926  SCIPerrorMessage("unknown node type %d\n", SCIPnodeGetType(parent));
927  return SCIP_INVALIDDATA;
928  }
929 
930  /* free parent, if it is not on the current active path */
931  if( freeParent && !parent->active )
932  {
933  SCIP_CALL( SCIPnodeFree(&node->parent, blkmem, set, stat, eventqueue, tree, lp) );
934  }
935 
936  /* update the effective root depth
937  * in reoptimization we must not increase the effective root depth
938  */
939  assert(tree->effectiverootdepth >= 0);
940  if( singleChild && SCIPnodeGetDepth(parent) == tree->effectiverootdepth && !set->reopt_enable )
941  {
942  tree->effectiverootdepth++;
943  SCIPsetDebugMsg(set, "unlinked node #%" SCIP_LONGINT_FORMAT " in depth %d -> new effective root depth: %d\n",
945  }
946  }
947 
948  return SCIP_OKAY;
949 }
950 
951 /** creates a node data structure */
952 static
954  SCIP_NODE** node, /**< pointer to node data structure */
955  BMS_BLKMEM* blkmem, /**< block memory */
956  SCIP_SET* set /**< global SCIP settings */
957  )
958 {
959  assert(node != NULL);
960 
961  SCIP_ALLOC( BMSallocBlockMemory(blkmem, node) );
962  (*node)->parent = NULL;
963  (*node)->conssetchg = NULL;
964  (*node)->domchg = NULL;
965  (*node)->number = 0;
966  (*node)->lowerbound = -SCIPsetInfinity(set);
967  (*node)->estimate = -SCIPsetInfinity(set);
968  (*node)->reoptid = 0;
969  (*node)->reopttype = (unsigned int) SCIP_REOPTTYPE_NONE;
970  (*node)->depth = 0;
971  (*node)->active = FALSE;
972  (*node)->cutoff = FALSE;
973  (*node)->reprop = FALSE;
974  (*node)->repropsubtreemark = 0;
975 
976  return SCIP_OKAY;
977 }
978 
979 /** creates a child node of the focus node */
981  SCIP_NODE** node, /**< pointer to node data structure */
982  BMS_BLKMEM* blkmem, /**< block memory */
983  SCIP_SET* set, /**< global SCIP settings */
984  SCIP_STAT* stat, /**< problem statistics */
985  SCIP_TREE* tree, /**< branch and bound tree */
986  SCIP_Real nodeselprio, /**< node selection priority of new node */
987  SCIP_Real estimate /**< estimate for (transformed) objective value of best feasible solution in subtree */
988  )
989 {
990  assert(node != NULL);
991  assert(blkmem != NULL);
992  assert(set != NULL);
993  assert(stat != NULL);
994  assert(tree != NULL);
995  assert(SCIPtreeIsPathComplete(tree));
996  assert(tree->pathlen == 0 || tree->path != NULL);
997  assert((tree->pathlen == 0) == (tree->focusnode == NULL));
998  assert(tree->focusnode == NULL || tree->focusnode == tree->path[tree->pathlen-1]);
999  assert(tree->focusnode == NULL || SCIPnodeGetType(tree->focusnode) == SCIP_NODETYPE_FOCUSNODE);
1000 
1001  stat->ncreatednodes++;
1002  stat->ncreatednodesrun++;
1003 
1004  /* create the node data structure */
1005  SCIP_CALL( nodeCreate(node, blkmem, set) );
1006  (*node)->number = stat->ncreatednodesrun;
1007 
1008  /* mark node to be a child node */
1009  (*node)->nodetype = SCIP_NODETYPE_CHILD; /*lint !e641*/
1010  (*node)->data.child.arraypos = -1;
1011 
1012  /* make focus node the parent of the new child */
1013  SCIP_CALL( nodeAssignParent(*node, blkmem, set, tree, tree->focusnode, nodeselprio) );
1014 
1015  /* update the estimate of the child */
1016  SCIPnodeSetEstimate(*node, set, estimate);
1017 
1018  /* output node creation to visualization file */
1019  SCIP_CALL( SCIPvisualNewChild(stat->visual, set, stat, *node) );
1020 
1021  SCIPsetDebugMsg(set, "created child node #%" SCIP_LONGINT_FORMAT " at depth %u (prio: %g)\n", SCIPnodeGetNumber(*node), (*node)->depth, nodeselprio);
1022 
1023  return SCIP_OKAY;
1024 }
1025 
1026 /** frees node */
1028  SCIP_NODE** node, /**< node data */
1029  BMS_BLKMEM* blkmem, /**< block memory buffer */
1030  SCIP_SET* set, /**< global SCIP settings */
1031  SCIP_STAT* stat, /**< problem statistics */
1032  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1033  SCIP_TREE* tree, /**< branch and bound tree */
1034  SCIP_LP* lp /**< current LP data */
1035  )
1036 {
1037  SCIP_Bool isroot;
1038 
1039  assert(node != NULL);
1040  assert(*node != NULL);
1041  assert(!(*node)->active);
1042  assert(blkmem != NULL);
1043  assert(tree != NULL);
1044 
1045  SCIPsetDebugMsg(set, "free node #%" SCIP_LONGINT_FORMAT " at depth %d of type %d\n", SCIPnodeGetNumber(*node), SCIPnodeGetDepth(*node), SCIPnodeGetType(*node));
1046 
1047  /* inform solution debugger, that the node has been freed */
1048  SCIP_CALL( SCIPdebugRemoveNode(blkmem, set, *node) );
1049 
1050  /* check, if the node to be freed is the root node */
1051  isroot = (SCIPnodeGetDepth(*node) == 0);
1052 
1053  /* free nodetype specific data, and release no longer needed LPI states */
1054  switch( SCIPnodeGetType(*node) )
1055  {
1057  assert(tree->focusnode == *node);
1058  assert(!SCIPtreeProbing(tree));
1059  SCIPerrorMessage("cannot free focus node - has to be converted into a dead end first\n");
1060  return SCIP_INVALIDDATA;
1062  assert(SCIPtreeProbing(tree));
1063  assert(SCIPnodeGetDepth(tree->probingroot) <= SCIPnodeGetDepth(*node));
1064  assert(SCIPnodeGetDepth(*node) > 0);
1065  SCIP_CALL( probingnodeFree(&((*node)->data.probingnode), blkmem, lp) );
1066  break;
1067  case SCIP_NODETYPE_SIBLING:
1068  assert((*node)->data.sibling.arraypos >= 0);
1069  assert((*node)->data.sibling.arraypos < tree->nsiblings);
1070  assert(tree->siblings[(*node)->data.sibling.arraypos] == *node);
1071  if( tree->focuslpstatefork != NULL )
1072  {
1075  SCIP_CALL( SCIPnodeReleaseLPIState(tree->focuslpstatefork, blkmem, lp) );
1076  }
1077  treeRemoveSibling(tree, *node);
1078  break;
1079  case SCIP_NODETYPE_CHILD:
1080  assert((*node)->data.child.arraypos >= 0);
1081  assert((*node)->data.child.arraypos < tree->nchildren);
1082  assert(tree->children[(*node)->data.child.arraypos] == *node);
1083  /* The children capture the LPI state at the moment, where the focus node is
1084  * converted into a junction, pseudofork, fork, or subroot, and a new node is focused.
1085  * At the same time, they become siblings or leaves, such that freeing a child
1086  * of the focus node doesn't require to release the LPI state;
1087  * we don't need to call treeRemoveChild(), because this is done in nodeReleaseParent()
1088  */
1089  break;
1090  case SCIP_NODETYPE_LEAF:
1091  if( (*node)->data.leaf.lpstatefork != NULL )
1092  {
1093  SCIP_CALL( SCIPnodeReleaseLPIState((*node)->data.leaf.lpstatefork, blkmem, lp) );
1094  }
1095  break;
1096  case SCIP_NODETYPE_DEADEND:
1098  break;
1100  SCIP_CALL( pseudoforkFree(&((*node)->data.pseudofork), blkmem, set, lp) );
1101  break;
1102  case SCIP_NODETYPE_FORK:
1103 
1104  /* release special root LPI state capture which is used to keep the root LPI state over the whole solving
1105  * process
1106  */
1107  if( isroot )
1108  {
1109  SCIP_CALL( SCIPnodeReleaseLPIState(*node, blkmem, lp) );
1110  }
1111  SCIP_CALL( forkFree(&((*node)->data.fork), blkmem, set, lp) );
1112  break;
1113  case SCIP_NODETYPE_SUBROOT:
1114  SCIP_CALL( subrootFree(&((*node)->data.subroot), blkmem, set, lp) );
1115  break;
1117  SCIPerrorMessage("cannot free node as long it is refocused\n");
1118  return SCIP_INVALIDDATA;
1119  default:
1120  SCIPerrorMessage("unknown node type %d\n", SCIPnodeGetType(*node));
1121  return SCIP_INVALIDDATA;
1122  }
1123 
1124  /* free common data */
1125  SCIP_CALL( SCIPconssetchgFree(&(*node)->conssetchg, blkmem, set) );
1126  SCIP_CALL( SCIPdomchgFree(&(*node)->domchg, blkmem, set, eventqueue, lp) );
1127  SCIP_CALL( nodeReleaseParent(*node, blkmem, set, stat, eventqueue, tree, lp) );
1128 
1129  /* check, if the node is the current probing root */
1130  if( *node == tree->probingroot )
1131  {
1132  assert(SCIPnodeGetType(*node) == SCIP_NODETYPE_PROBINGNODE);
1133  tree->probingroot = NULL;
1134  }
1135 
1136  BMSfreeBlockMemory(blkmem, node);
1137 
1138  /* delete the tree's root node pointer, if the freed node was the root */
1139  if( isroot )
1140  tree->root = NULL;
1141 
1142  return SCIP_OKAY;
1143 }
1144 
1145 /** cuts off node and whole sub tree from branch and bound tree */
1147  SCIP_NODE* node, /**< node that should be cut off */
1148  SCIP_SET* set, /**< global SCIP settings */
1149  SCIP_STAT* stat, /**< problem statistics */
1150  SCIP_TREE* tree, /**< branch and bound tree */
1151  SCIP_PROB* transprob, /**< transformed problem after presolve */
1152  SCIP_PROB* origprob, /**< original problem */
1153  SCIP_REOPT* reopt, /**< reoptimization data structure */
1154  SCIP_LP* lp, /**< current LP */
1155  BMS_BLKMEM* blkmem /**< block memory */
1156  )
1157 {
1158  SCIP_Real oldbound;
1159 
1160  assert(node != NULL);
1161  assert(set != NULL);
1162  assert(stat != NULL);
1163  assert(tree != NULL);
1164 
1165  if( set->reopt_enable )
1166  {
1167  assert(reopt != NULL);
1168  /* check if the node should be stored for reoptimization */
1170  tree->root == node, tree->focusnode == node, node->lowerbound, tree->effectiverootdepth) );
1171  }
1172 
1173  oldbound = node->lowerbound;
1174  node->cutoff = TRUE;
1175  node->lowerbound = SCIPsetInfinity(set);
1176  node->estimate = SCIPsetInfinity(set);
1177  if( node->active )
1178  tree->cutoffdepth = MIN(tree->cutoffdepth, (int)node->depth);
1179 
1180  /* update primal integral */
1181  if( node->depth == 0 )
1182  {
1183  stat->rootlowerbound = SCIPsetInfinity(set);
1184  if( set->misc_calcintegral )
1185  SCIPstatUpdatePrimalDualIntegral(stat, set, transprob, origprob, SCIPsetInfinity(set), SCIPsetInfinity(set));
1186  }
1187  else if( set->misc_calcintegral && SCIPsetIsEQ(set, oldbound, stat->lastlowerbound) )
1188  {
1189  SCIP_Real lowerbound;
1190  lowerbound = SCIPtreeGetLowerbound(tree, set);
1191 
1192  /* updating the primal integral is only necessary if dual bound has increased since last evaluation */
1193  if( lowerbound > stat->lastlowerbound )
1194  SCIPstatUpdatePrimalDualIntegral(stat, set, transprob, origprob, SCIPsetInfinity(set), SCIPsetInfinity(set));
1195  }
1196 
1197  SCIPvisualCutoffNode(stat->visual, set, stat, node, TRUE);
1198 
1199  SCIPsetDebugMsg(set, "cutting off %s node #%" SCIP_LONGINT_FORMAT " at depth %d (cutoffdepth: %d)\n",
1200  node->active ? "active" : "inactive", SCIPnodeGetNumber(node), SCIPnodeGetDepth(node), tree->cutoffdepth);
1201 
1202  return SCIP_OKAY;
1203 }
1204 
1205 /** marks node, that propagation should be applied again the next time, a node of its subtree is focused */
1207  SCIP_NODE* node, /**< node that should be propagated again */
1208  SCIP_SET* set, /**< global SCIP settings */
1209  SCIP_STAT* stat, /**< problem statistics */
1210  SCIP_TREE* tree /**< branch and bound tree */
1211  )
1212 {
1213  assert(node != NULL);
1214  assert(set != NULL);
1215  assert(stat != NULL);
1216  assert(tree != NULL);
1217 
1218  if( !node->reprop )
1219  {
1220  node->reprop = TRUE;
1221  if( node->active )
1222  tree->repropdepth = MIN(tree->repropdepth, (int)node->depth);
1223 
1224  SCIPvisualMarkedRepropagateNode(stat->visual, stat, node);
1225 
1226  SCIPsetDebugMsg(set, "marked %s node #%" SCIP_LONGINT_FORMAT " at depth %d to be propagated again (repropdepth: %d)\n",
1227  node->active ? "active" : "inactive", SCIPnodeGetNumber(node), SCIPnodeGetDepth(node), tree->repropdepth);
1228  }
1229 }
1230 
1231 /** marks node, that it is completely propagated in the current repropagation subtree level */
1233  SCIP_NODE* node, /**< node that should be marked to be propagated */
1234  SCIP_TREE* tree /**< branch and bound tree */
1235  )
1236 {
1237  assert(node != NULL);
1238  assert(tree != NULL);
1239 
1240  if( node->parent != NULL )
1241  node->repropsubtreemark = node->parent->repropsubtreemark; /*lint !e732*/
1242  node->reprop = FALSE;
1243 
1244  /* if the node was the highest repropagation node in the path, update the repropdepth in the tree data */
1245  if( node->active && node->depth == tree->repropdepth )
1246  {
1247  do
1248  {
1249  assert(tree->repropdepth < tree->pathlen);
1250  assert(tree->path[tree->repropdepth]->active);
1251  assert(!tree->path[tree->repropdepth]->reprop);
1252  tree->repropdepth++;
1253  }
1254  while( tree->repropdepth < tree->pathlen && !tree->path[tree->repropdepth]->reprop );
1255  if( tree->repropdepth == tree->pathlen )
1256  tree->repropdepth = INT_MAX;
1257  }
1258 }
1259 
1260 /** moves the subtree repropagation counter to the next value */
1261 static
1263  SCIP_TREE* tree /**< branch and bound tree */
1264  )
1265 {
1266  assert(tree != NULL);
1267 
1268  tree->repropsubtreecount++;
1269  tree->repropsubtreecount %= (MAXREPROPMARK+1);
1270 }
1271 
1272 /** applies propagation on the node, that was marked to be propagated again */
1273 static
1275  SCIP_NODE* node, /**< node to apply propagation on */
1276  BMS_BLKMEM* blkmem, /**< block memory buffers */
1277  SCIP_SET* set, /**< global SCIP settings */
1278  SCIP_STAT* stat, /**< dynamic problem statistics */
1279  SCIP_PROB* transprob, /**< transformed problem */
1280  SCIP_PROB* origprob, /**< original problem */
1281  SCIP_PRIMAL* primal, /**< primal data */
1282  SCIP_TREE* tree, /**< branch and bound tree */
1283  SCIP_REOPT* reopt, /**< reoptimization data structure */
1284  SCIP_LP* lp, /**< current LP data */
1285  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1286  SCIP_CONFLICT* conflict, /**< conflict analysis data */
1287  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
1288  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1289  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1290  SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
1291  )
1292 {
1293  SCIP_NODETYPE oldtype;
1294  SCIP_NODE* oldfocusnode;
1295  SCIP_NODE* oldfocuslpfork;
1296  SCIP_NODE* oldfocuslpstatefork;
1297  SCIP_NODE* oldfocussubroot;
1298  SCIP_Longint oldfocuslpstateforklpcount;
1299  int oldnchildren;
1300  int oldnsiblings;
1301  SCIP_Bool oldfocusnodehaslp;
1302  SCIP_Longint oldnboundchgs;
1303  SCIP_Bool initialreprop;
1304  SCIP_Bool clockisrunning;
1305 
1306  assert(node != NULL);
1312  assert(node->active);
1313  assert(node->reprop || node->repropsubtreemark != node->parent->repropsubtreemark);
1314  assert(stat != NULL);
1315  assert(tree != NULL);
1316  assert(SCIPeventqueueIsDelayed(eventqueue));
1317  assert(cutoff != NULL);
1318 
1319  SCIPsetDebugMsg(set, "propagating again node #%" SCIP_LONGINT_FORMAT " at depth %d\n", SCIPnodeGetNumber(node), SCIPnodeGetDepth(node));
1320  initialreprop = node->reprop;
1321 
1322  SCIPvisualRepropagatedNode(stat->visual, stat, node);
1323 
1324  /* process the delayed events in order to flush the problem changes */
1325  SCIP_CALL( SCIPeventqueueProcess(eventqueue, blkmem, set, primal, lp, branchcand, eventfilter) );
1326 
1327  /* stop node activation timer */
1328  clockisrunning = SCIPclockIsRunning(stat->nodeactivationtime);
1329  if( clockisrunning )
1330  SCIPclockStop(stat->nodeactivationtime, set);
1331 
1332  /* mark the node refocused and temporarily install it as focus node */
1333  oldtype = (SCIP_NODETYPE)node->nodetype;
1334  oldfocusnode = tree->focusnode;
1335  oldfocuslpfork = tree->focuslpfork;
1336  oldfocuslpstatefork = tree->focuslpstatefork;
1337  oldfocussubroot = tree->focussubroot;
1338  oldfocuslpstateforklpcount = tree->focuslpstateforklpcount;
1339  oldnchildren = tree->nchildren;
1340  oldnsiblings = tree->nsiblings;
1341  oldfocusnodehaslp = tree->focusnodehaslp;
1342  node->nodetype = SCIP_NODETYPE_REFOCUSNODE; /*lint !e641*/
1343  tree->focusnode = node;
1344  tree->focuslpfork = NULL;
1345  tree->focuslpstatefork = NULL;
1346  tree->focussubroot = NULL;
1347  tree->focuslpstateforklpcount = -1;
1348  tree->nchildren = 0;
1349  tree->nsiblings = 0;
1350  tree->focusnodehaslp = FALSE;
1351 
1352  /* propagate the domains again */
1353  oldnboundchgs = stat->nboundchgs;
1354  SCIP_CALL( SCIPpropagateDomains(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
1355  eventqueue, conflict, cliquetable, SCIPnodeGetDepth(node), 0, SCIP_PROPTIMING_ALWAYS, cutoff) );
1356  assert(!node->reprop || *cutoff);
1357  assert(node->parent == NULL || node->repropsubtreemark == node->parent->repropsubtreemark);
1359  assert(tree->focusnode == node);
1360  assert(tree->focuslpfork == NULL);
1361  assert(tree->focuslpstatefork == NULL);
1362  assert(tree->focussubroot == NULL);
1363  assert(tree->focuslpstateforklpcount == -1);
1364  assert(tree->nchildren == 0);
1365  assert(tree->nsiblings == 0);
1366  assert(tree->focusnodehaslp == FALSE);
1367  assert(stat->nboundchgs >= oldnboundchgs);
1368  stat->nreprops++;
1369  stat->nrepropboundchgs += stat->nboundchgs - oldnboundchgs;
1370  if( *cutoff )
1371  stat->nrepropcutoffs++;
1372 
1373  SCIPsetDebugMsg(set, "repropagation %" SCIP_LONGINT_FORMAT " at depth %u changed %" SCIP_LONGINT_FORMAT " bounds (total reprop bound changes: %" SCIP_LONGINT_FORMAT "), cutoff: %u\n",
1374  stat->nreprops, node->depth, stat->nboundchgs - oldnboundchgs, stat->nrepropboundchgs, *cutoff);
1375 
1376  /* if a propagation marked with the reprop flag was successful, we want to repropagate the whole subtree */
1377  /**@todo because repropsubtree is only a bit flag, we cannot mark a whole subtree a second time for
1378  * repropagation; use a (small) part of the node's bits to be able to store larger numbers,
1379  * and update tree->repropsubtreelevel with this number
1380  */
1381  if( initialreprop && !(*cutoff) && stat->nboundchgs > oldnboundchgs )
1382  {
1384  node->repropsubtreemark = tree->repropsubtreecount; /*lint !e732*/
1385  SCIPsetDebugMsg(set, "initial repropagation at depth %u changed %" SCIP_LONGINT_FORMAT " bounds -> repropagating subtree (new mark: %d)\n",
1386  node->depth, stat->nboundchgs - oldnboundchgs, tree->repropsubtreecount);
1387  assert((int)(node->repropsubtreemark) == tree->repropsubtreecount); /* bitfield must be large enough */
1388  }
1389 
1390  /* reset the node's type and reinstall the old focus node */
1391  node->nodetype = oldtype; /*lint !e641*/
1392  tree->focusnode = oldfocusnode;
1393  tree->focuslpfork = oldfocuslpfork;
1394  tree->focuslpstatefork = oldfocuslpstatefork;
1395  tree->focussubroot = oldfocussubroot;
1396  tree->focuslpstateforklpcount = oldfocuslpstateforklpcount;
1397  tree->nchildren = oldnchildren;
1398  tree->nsiblings = oldnsiblings;
1399  tree->focusnodehaslp = oldfocusnodehaslp;
1400 
1401  /* make the domain change data static again to save memory */
1403  {
1404  SCIP_CALL( SCIPdomchgMakeStatic(&node->domchg, blkmem, set, eventqueue, lp) );
1405  }
1406 
1407  /* start node activation timer again */
1408  if( clockisrunning )
1409  SCIPclockStart(stat->nodeactivationtime, set);
1410 
1411  /* delay events in path switching */
1412  SCIP_CALL( SCIPeventqueueDelay(eventqueue) );
1413 
1414  /* mark the node to be cut off if a cutoff was detected */
1415  if( *cutoff )
1416  {
1417  SCIP_CALL( SCIPnodeCutoff(node, set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
1418  }
1419 
1420  return SCIP_OKAY;
1421 }
1422 
1423 /** informs node, that it is now on the active path and applies any domain and constraint set changes */
1424 static
1426  SCIP_NODE* node, /**< node to activate */
1427  BMS_BLKMEM* blkmem, /**< block memory buffers */
1428  SCIP_SET* set, /**< global SCIP settings */
1429  SCIP_STAT* stat, /**< problem statistics */
1430  SCIP_PROB* transprob, /**< transformed problem */
1431  SCIP_PROB* origprob, /**< original problem */
1432  SCIP_PRIMAL* primal, /**< primal data */
1433  SCIP_TREE* tree, /**< branch and bound tree */
1434  SCIP_REOPT* reopt, /**< reotimization data structure */
1435  SCIP_LP* lp, /**< current LP data */
1436  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1437  SCIP_CONFLICT* conflict, /**< conflict analysis data */
1438  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
1439  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1440  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1441  SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
1442  )
1443 {
1444  assert(node != NULL);
1445  assert(!node->active);
1446  assert(stat != NULL);
1447  assert(tree != NULL);
1448  assert(!SCIPtreeProbing(tree));
1449  assert(cutoff != NULL);
1450 
1451  SCIPsetDebugMsg(set, "activate node #%" SCIP_LONGINT_FORMAT " at depth %d of type %d (reprop subtree mark: %u)\n",
1453 
1454  /* apply domain and constraint set changes */
1455  SCIP_CALL( SCIPconssetchgApply(node->conssetchg, blkmem, set, stat, node->depth,
1457  SCIP_CALL( SCIPdomchgApply(node->domchg, blkmem, set, stat, lp, branchcand, eventqueue, node->depth, cutoff) );
1458 
1459  /* mark node active */
1460  node->active = TRUE;
1461  stat->nactivatednodes++;
1462 
1463  /* check if the domain change produced a cutoff */
1464  if( *cutoff )
1465  {
1466  /* try to repropagate the node to see, if the propagation also leads to a conflict and a conflict constraint
1467  * could be generated; if propagation conflict analysis is turned off, repropagating the node makes no
1468  * sense, since it is already cut off
1469  */
1470  node->reprop = set->conf_enable && set->conf_useprop;
1471 
1472  /* mark the node to be cut off */
1473  SCIP_CALL( SCIPnodeCutoff(node, set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
1474  }
1475 
1476  /* propagate node again, if the reprop flag is set; in the new focus node, no repropagation is necessary, because
1477  * the focus node is propagated anyways
1478  */
1480  && (node->reprop || (node->parent != NULL && node->repropsubtreemark != node->parent->repropsubtreemark)) )
1481  {
1482  SCIP_Bool propcutoff;
1483 
1484  SCIP_CALL( nodeRepropagate(node, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, conflict,
1485  eventfilter, eventqueue, cliquetable, &propcutoff) );
1486  *cutoff = *cutoff || propcutoff;
1487  }
1488 
1489  return SCIP_OKAY;
1490 }
1491 
1492 /** informs node, that it is no longer on the active path and undoes any domain and constraint set changes */
1493 static
1495  SCIP_NODE* node, /**< node to deactivate */
1496  BMS_BLKMEM* blkmem, /**< block memory buffers */
1497  SCIP_SET* set, /**< global SCIP settings */
1498  SCIP_STAT* stat, /**< problem statistics */
1499  SCIP_TREE* tree, /**< branch and bound tree */
1500  SCIP_LP* lp, /**< current LP data */
1501  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1502  SCIP_EVENTQUEUE* eventqueue /**< event queue */
1503  )
1504 {
1505  SCIP_Bool freeNode;
1506 
1507  assert(node != NULL);
1508  assert(node->active);
1509  assert(tree != NULL);
1510  assert(SCIPnodeGetType(node) != SCIP_NODETYPE_FOCUSNODE);
1511 
1512  SCIPsetDebugMsg(set, "deactivate node #%" SCIP_LONGINT_FORMAT " at depth %d of type %d (reprop subtree mark: %u)\n",
1514 
1515  /* undo domain and constraint set changes */
1516  SCIP_CALL( SCIPdomchgUndo(node->domchg, blkmem, set, stat, lp, branchcand, eventqueue) );
1517  SCIP_CALL( SCIPconssetchgUndo(node->conssetchg, blkmem, set, stat) );
1518 
1519  /* mark node inactive */
1520  node->active = FALSE;
1521 
1522  /* count number of deactivated nodes (ignoring probing switches) */
1523  if( !SCIPtreeProbing(tree) )
1524  stat->ndeactivatednodes++;
1525 
1526  /* free node if it is a dead-end node, i.e., has no children */
1527  switch( SCIPnodeGetType(node) )
1528  {
1531  case SCIP_NODETYPE_SIBLING:
1532  case SCIP_NODETYPE_CHILD:
1533  case SCIP_NODETYPE_LEAF:
1534  case SCIP_NODETYPE_DEADEND:
1536  freeNode = FALSE;
1537  break;
1539  freeNode = (node->data.junction.nchildren == 0);
1540  break;
1542  freeNode = (node->data.pseudofork->nchildren == 0);
1543  break;
1544  case SCIP_NODETYPE_FORK:
1545  freeNode = (node->data.fork->nchildren == 0);
1546  break;
1547  case SCIP_NODETYPE_SUBROOT:
1548  freeNode = (node->data.subroot->nchildren == 0);
1549  break;
1550  default:
1551  SCIPerrorMessage("unknown node type %d\n", SCIPnodeGetType(node));
1552  return SCIP_INVALIDDATA;
1553  }
1554  if( freeNode )
1555  {
1556  SCIP_CALL( SCIPnodeFree(&node, blkmem, set, stat, eventqueue, tree, lp) );
1557  }
1558 
1559  return SCIP_OKAY;
1560 }
1561 
1562 /** adds constraint locally to the node and captures it; activates constraint, if node is active;
1563  * if a local constraint is added to the root node, it is automatically upgraded into a global constraint
1564  */
1566  SCIP_NODE* node, /**< node to add constraint to */
1567  BMS_BLKMEM* blkmem, /**< block memory */
1568  SCIP_SET* set, /**< global SCIP settings */
1569  SCIP_STAT* stat, /**< problem statistics */
1570  SCIP_TREE* tree, /**< branch and bound tree */
1571  SCIP_CONS* cons /**< constraint to add */
1572  )
1573 {
1574  assert(node != NULL);
1575  assert(cons != NULL);
1576  assert(cons->validdepth <= SCIPnodeGetDepth(node));
1577  assert(tree != NULL);
1578  assert(tree->effectiverootdepth >= 0);
1579  assert(tree->root != NULL);
1580  assert(SCIPconsIsGlobal(cons) || SCIPnodeGetDepth(node) > tree->effectiverootdepth);
1581 
1582 #ifndef NDEBUG
1583  /* check if we add this constraint to the same scip, where we create the constraint */
1584  if( cons->scip != set->scip )
1585  {
1586  SCIPerrorMessage("try to add a constraint of another scip instance\n");
1587  return SCIP_INVALIDDATA;
1588  }
1589 #endif
1590 
1591  /* add constraint addition to the node's constraint set change data, and activate constraint if node is active */
1592  SCIP_CALL( SCIPconssetchgAddAddedCons(&node->conssetchg, blkmem, set, stat, cons, node->depth,
1593  (SCIPnodeGetType(node) == SCIP_NODETYPE_FOCUSNODE), node->active) );
1594  assert(node->conssetchg != NULL);
1595  assert(node->conssetchg->addedconss != NULL);
1596  assert(!node->active || SCIPconsIsActive(cons));
1597 
1598  /* if the constraint is added to an active node which is not a probing node, increment the corresponding counter */
1599  if( node->active && SCIPnodeGetType(node) != SCIP_NODETYPE_PROBINGNODE )
1600  stat->nactiveconssadded++;
1601 
1602  return SCIP_OKAY;
1603 }
1604 
1605 /** locally deletes constraint at the given node by disabling its separation, enforcing, and propagation capabilities
1606  * at the node; captures constraint; disables constraint, if node is active
1607  */
1609  SCIP_NODE* node, /**< node to add constraint to */
1610  BMS_BLKMEM* blkmem, /**< block memory */
1611  SCIP_SET* set, /**< global SCIP settings */
1612  SCIP_STAT* stat, /**< problem statistics */
1613  SCIP_TREE* tree, /**< branch and bound tree */
1614  SCIP_CONS* cons /**< constraint to locally delete */
1615  )
1616 {
1617  assert(node != NULL);
1618  assert(tree != NULL);
1619  assert(cons != NULL);
1620 
1621  SCIPsetDebugMsg(set, "disabling constraint <%s> at node at depth %u\n", cons->name, node->depth);
1622 
1623  /* add constraint disabling to the node's constraint set change data */
1624  SCIP_CALL( SCIPconssetchgAddDisabledCons(&node->conssetchg, blkmem, set, cons) );
1625  assert(node->conssetchg != NULL);
1626  assert(node->conssetchg->disabledconss != NULL);
1627 
1628  /* disable constraint, if node is active */
1629  if( node->active && cons->enabled && !cons->updatedisable )
1630  {
1631  SCIP_CALL( SCIPconsDisable(cons, set, stat) );
1632  }
1633 
1634  return SCIP_OKAY;
1635 }
1636 
1637 /** returns all constraints added to a given node */
1639  SCIP_NODE* node, /**< node */
1640  SCIP_CONS** addedconss, /**< array to store the constraints */
1641  int* naddedconss, /**< number of added constraints */
1642  int addedconsssize /**< size of the constraint array */
1643  )
1644 {
1645  int cons;
1646 
1647  assert(node != NULL );
1648  assert(node->conssetchg != NULL);
1649  assert(node->conssetchg->addedconss != NULL);
1650  assert(node->conssetchg->naddedconss >= 1);
1651 
1652  *naddedconss = node->conssetchg->naddedconss;
1653 
1654  /* check the size and return if the array is not large enough */
1655  if( addedconsssize < *naddedconss )
1656  return;
1657 
1658  /* fill the array */
1659  for( cons = 0; cons < *naddedconss; cons++ )
1660  {
1661  addedconss[cons] = node->conssetchg->addedconss[cons];
1662  }
1663 
1664  return;
1665 }
1666 
1667 /** returns the number of added constraints to the given node */
1669  SCIP_NODE* node /**< node */
1670  )
1671 {
1672  assert(node != NULL);
1673 
1674  if( node->conssetchg == NULL )
1675  return 0;
1676  else
1677  return node->conssetchg->naddedconss;
1678 }
1679 
1680 /** adds the given bound change to the list of pending bound changes */
1681 static
1683  SCIP_TREE* tree, /**< branch and bound tree */
1684  SCIP_SET* set, /**< global SCIP settings */
1685  SCIP_NODE* node, /**< node to add bound change to */
1686  SCIP_VAR* var, /**< variable to change the bounds for */
1687  SCIP_Real newbound, /**< new value for bound */
1688  SCIP_BOUNDTYPE boundtype, /**< type of bound: lower or upper bound */
1689  SCIP_CONS* infercons, /**< constraint that deduced the bound change, or NULL */
1690  SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
1691  int inferinfo, /**< user information for inference to help resolving the conflict */
1692  SCIP_Bool probingchange /**< is the bound change a temporary setting due to probing? */
1693  )
1694 {
1695  assert(tree != NULL);
1696 
1697  /* make sure that enough memory is allocated for the pendingbdchgs array */
1698  SCIP_CALL( treeEnsurePendingbdchgsMem(tree, set, tree->npendingbdchgs+1) );
1699 
1700  /* capture the variable */
1701  SCIPvarCapture(var);
1702 
1703  /* add the bound change to the pending list */
1704  tree->pendingbdchgs[tree->npendingbdchgs].node = node;
1705  tree->pendingbdchgs[tree->npendingbdchgs].var = var;
1706  tree->pendingbdchgs[tree->npendingbdchgs].newbound = newbound;
1707  tree->pendingbdchgs[tree->npendingbdchgs].boundtype = boundtype;
1708  tree->pendingbdchgs[tree->npendingbdchgs].infercons = infercons;
1709  tree->pendingbdchgs[tree->npendingbdchgs].inferprop = inferprop;
1710  tree->pendingbdchgs[tree->npendingbdchgs].inferinfo = inferinfo;
1711  tree->pendingbdchgs[tree->npendingbdchgs].probingchange = probingchange;
1712  tree->npendingbdchgs++;
1713 
1714  /* check global pending boundchanges against debug solution */
1715  if( node->depth == 0 )
1716  {
1717 #ifndef NDEBUG
1718  SCIP_Real bound = newbound;
1719 
1720  /* get bound adjusted for integrality(, this should already be done) */
1721  SCIPvarAdjustBd(var, set, boundtype, &bound);
1722 
1723  if( boundtype == SCIP_BOUNDTYPE_LOWER )
1724  {
1725  /* check that the bound is feasible */
1726  if( bound > SCIPvarGetUbGlobal(var) )
1727  {
1728  /* due to numerics we only want to be feasible in feasibility tolerance */
1729  assert(SCIPsetIsFeasLE(set, bound, SCIPvarGetUbGlobal(var)));
1730  bound = SCIPvarGetUbGlobal(var);
1731  }
1732  }
1733  else
1734  {
1735  assert(boundtype == SCIP_BOUNDTYPE_UPPER);
1736 
1737  /* check that the bound is feasible */
1738  if( bound < SCIPvarGetLbGlobal(var) )
1739  {
1740  /* due to numerics we only want to be feasible in feasibility tolerance */
1741  assert(SCIPsetIsFeasGE(set, bound, SCIPvarGetLbGlobal(var)));
1742  bound = SCIPvarGetLbGlobal(var);
1743  }
1744  }
1745  /* check that the given bound was already adjusted for integrality */
1746  assert(SCIPsetIsEQ(set, newbound, bound));
1747 #endif
1748  if( boundtype == SCIP_BOUNDTYPE_LOWER )
1749  {
1750  /* check bound on debugging solution */
1751  SCIP_CALL( SCIPdebugCheckLbGlobal(set->scip, var, newbound) ); /*lint !e506 !e774*/
1752  }
1753  else
1754  {
1755  assert(boundtype == SCIP_BOUNDTYPE_UPPER);
1756 
1757  /* check bound on debugging solution */
1758  SCIP_CALL( SCIPdebugCheckUbGlobal(set->scip, var, newbound) ); /*lint !e506 !e774*/
1759  }
1760  }
1761 
1762  return SCIP_OKAY;
1763 }
1764 
1765 /** adds bound change with inference information to focus node, child of focus node, or probing node;
1766  * if possible, adjusts bound to integral value;
1767  * at most one of infercons and inferprop may be non-NULL
1768  */
1770  SCIP_NODE* node, /**< node to add bound change to */
1771  BMS_BLKMEM* blkmem, /**< block memory */
1772  SCIP_SET* set, /**< global SCIP settings */
1773  SCIP_STAT* stat, /**< problem statistics */
1774  SCIP_PROB* transprob, /**< transformed problem after presolve */
1775  SCIP_PROB* origprob, /**< original problem */
1776  SCIP_TREE* tree, /**< branch and bound tree */
1777  SCIP_REOPT* reopt, /**< reoptimization data structure */
1778  SCIP_LP* lp, /**< current LP data */
1779  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1780  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1781  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1782  SCIP_VAR* var, /**< variable to change the bounds for */
1783  SCIP_Real newbound, /**< new value for bound */
1784  SCIP_BOUNDTYPE boundtype, /**< type of bound: lower or upper bound */
1785  SCIP_CONS* infercons, /**< constraint that deduced the bound change, or NULL */
1786  SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
1787  int inferinfo, /**< user information for inference to help resolving the conflict */
1788  SCIP_Bool probingchange /**< is the bound change a temporary setting due to probing? */
1789  )
1790 {
1791  SCIP_VAR* infervar;
1792  SCIP_BOUNDTYPE inferboundtype;
1793  SCIP_Real oldlb;
1794  SCIP_Real oldub;
1795  SCIP_Real oldbound;
1796 
1797  assert(node != NULL);
1802  || node->depth == 0);
1803  assert(set != NULL);
1804  assert(tree != NULL);
1805  assert(tree->effectiverootdepth >= 0);
1806  assert(tree->root != NULL);
1807  assert(var != NULL);
1808  assert(node->active || (infercons == NULL && inferprop == NULL));
1809  assert((SCIP_NODETYPE)node->nodetype == SCIP_NODETYPE_PROBINGNODE || !probingchange);
1810 
1811  SCIPsetDebugMsg(set, "adding boundchange at node %llu at depth %u to variable <%s>: old bounds=[%g,%g], new %s bound: %g (infer%s=<%s>, inferinfo=%d)\n",
1812  node->number, node->depth, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var),
1813  boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", newbound, infercons != NULL ? "cons" : "prop",
1814  infercons != NULL ? SCIPconsGetName(infercons) : (inferprop != NULL ? SCIPpropGetName(inferprop) : "-"), inferinfo);
1815 
1816  /* remember variable as inference variable, and get corresponding active variable, bound and bound type */
1817  infervar = var;
1818  inferboundtype = boundtype;
1819 
1820  SCIP_CALL( SCIPvarGetProbvarBound(&var, &newbound, &boundtype) );
1821 
1823  {
1824  SCIPerrorMessage("cannot change bounds of multi-aggregated variable <%s>\n", SCIPvarGetName(var));
1825  SCIPABORT();
1826  return SCIP_INVALIDDATA; /*lint !e527*/
1827  }
1829 
1830  if( (int) node->depth <= tree->effectiverootdepth )
1831  {
1832  oldlb = SCIPvarGetLbGlobal(var);
1833  oldub = SCIPvarGetUbGlobal(var);
1834  }
1835  else
1836  {
1837  oldlb = SCIPvarGetLbLocal(var);
1838  oldub = SCIPvarGetUbLocal(var);
1839  }
1840  assert(SCIPsetIsLE(set, oldlb, oldub));
1841 
1842  if( boundtype == SCIP_BOUNDTYPE_LOWER )
1843  {
1844  /* adjust lower bound w.r.t. to integrality */
1845  SCIPvarAdjustLb(var, set, &newbound);
1846  assert(SCIPsetIsGT(set, newbound, oldlb));
1847  assert(SCIPsetIsFeasLE(set, newbound, oldub));
1848  oldbound = oldlb;
1849  newbound = MIN(newbound, oldub);
1850 
1851  if ( set->stage == SCIP_STAGE_SOLVING && SCIPsetIsInfinity(set, newbound) )
1852  {
1853  SCIPerrorMessage("cannot change lower bound of variable <%s> to infinity.\n", SCIPvarGetName(var));
1854  SCIPABORT();
1855  return SCIP_INVALIDDATA; /*lint !e527*/
1856  }
1857  }
1858  else
1859  {
1860  assert(boundtype == SCIP_BOUNDTYPE_UPPER);
1861 
1862  /* adjust the new upper bound */
1863  SCIPvarAdjustUb(var, set, &newbound);
1864  assert(SCIPsetIsLT(set, newbound, oldub));
1865  assert(SCIPsetIsFeasGE(set, newbound, oldlb));
1866  oldbound = oldub;
1867  newbound = MAX(newbound, oldlb);
1868 
1869  if ( set->stage == SCIP_STAGE_SOLVING && SCIPsetIsInfinity(set, -newbound) )
1870  {
1871  SCIPerrorMessage("cannot change upper bound of variable <%s> to minus infinity.\n", SCIPvarGetName(var));
1872  SCIPABORT();
1873  return SCIP_INVALIDDATA; /*lint !e527*/
1874  }
1875  }
1876 
1877  SCIPsetDebugMsg(set, " -> transformed to active variable <%s>: old bounds=[%g,%g], new %s bound: %g, obj: %g\n",
1878  SCIPvarGetName(var), oldlb, oldub, boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", newbound,
1879  SCIPvarGetObj(var));
1880 
1881  /* if the bound change takes place at an active node but is conflicting with the current local bounds,
1882  * we cannot apply it immediately because this would introduce inconsistencies to the bound change data structures
1883  * in the tree and to the bound change information data in the variable;
1884  * instead we have to remember the bound change as a pending bound change and mark the affected nodes on the active
1885  * path to be infeasible
1886  */
1887  if( node->active )
1888  {
1889  int conflictingdepth;
1890 
1891  conflictingdepth = SCIPvarGetConflictingBdchgDepth(var, set, boundtype, newbound);
1892 
1893  if( conflictingdepth >= 0 )
1894  {
1895  /* 0 would mean the bound change conflicts with a global bound */
1896  assert(conflictingdepth > 0);
1897  assert(conflictingdepth < tree->pathlen);
1898 
1899  SCIPsetDebugMsg(set, " -> bound change <%s> %s %g violates current local bounds [%g,%g] since depth %d: remember for later application\n",
1900  SCIPvarGetName(var), boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", newbound,
1901  SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), conflictingdepth);
1902 
1903  /* remember the pending bound change */
1904  SCIP_CALL( treeAddPendingBdchg(tree, set, node, var, newbound, boundtype, infercons, inferprop, inferinfo,
1905  probingchange) );
1906 
1907  /* mark the node with the conflicting bound change to be cut off */
1908  SCIP_CALL( SCIPnodeCutoff(tree->path[conflictingdepth], set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
1909 
1910  return SCIP_OKAY;
1911  }
1912  }
1913 
1914  SCIPstatIncrement(stat, set, nboundchgs);
1915 
1916  /* if we are in probing mode we have to additionally count the bound changes for the probing statistic */
1917  if( tree->probingroot != NULL )
1918  SCIPstatIncrement(stat, set, nprobboundchgs);
1919 
1920  /* if the node is the root node: change local and global bound immediately */
1921  if( SCIPnodeGetDepth(node) <= tree->effectiverootdepth )
1922  {
1923  assert(node->active || tree->focusnode == NULL );
1924  assert(SCIPnodeGetType(node) != SCIP_NODETYPE_PROBINGNODE);
1925  assert(!probingchange);
1926 
1927  SCIPsetDebugMsg(set, " -> bound change in root node: perform global bound change\n");
1928  SCIP_CALL( SCIPvarChgBdGlobal(var, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, newbound, boundtype) );
1929 
1930  if( set->stage == SCIP_STAGE_SOLVING )
1931  {
1932  /* the root should be repropagated due to the bound change */
1933  SCIPnodePropagateAgain(tree->root, set, stat, tree);
1934  SCIPsetDebugMsg(set, "marked root node to be repropagated due to global bound change <%s>:[%g,%g] -> [%g,%g] found in depth %u\n",
1935  SCIPvarGetName(var), oldlb, oldub, boundtype == SCIP_BOUNDTYPE_LOWER ? newbound : oldlb,
1936  boundtype == SCIP_BOUNDTYPE_LOWER ? oldub : newbound, node->depth);
1937  }
1938 
1939  return SCIP_OKAY;
1940  }
1941 
1942  /* if the node is a child, or the bound is a temporary probing bound
1943  * - the bound change is a branching decision
1944  * - the child's lower bound can be updated due to the changed pseudo solution
1945  * otherwise:
1946  * - the bound change is an inference
1947  */
1948  if( SCIPnodeGetType(node) == SCIP_NODETYPE_CHILD || probingchange )
1949  {
1950  SCIP_Real newpseudoobjval;
1951  SCIP_Real lpsolval;
1952 
1953  assert(!node->active || SCIPnodeGetType(node) == SCIP_NODETYPE_PROBINGNODE);
1954 
1955  /* get the solution value of variable in last solved LP on the active path:
1956  * - if the LP was solved at the current node, the LP values of the columns are valid
1957  * - if the last solved LP was the one in the current lpstatefork, the LP value in the columns are still valid
1958  * - otherwise, the LP values are invalid
1959  */
1960  if( SCIPtreeHasCurrentNodeLP(tree)
1962  {
1963  lpsolval = SCIPvarGetLPSol(var);
1964  }
1965  else
1966  lpsolval = SCIP_INVALID;
1967 
1968  /* remember the bound change as branching decision (infervar/infercons/inferprop are not important: use NULL) */
1969  SCIP_CALL( SCIPdomchgAddBoundchg(&node->domchg, blkmem, set, var, newbound, boundtype, SCIP_BOUNDCHGTYPE_BRANCHING,
1970  lpsolval, NULL, NULL, NULL, 0, inferboundtype) );
1971 
1972  /* update the child's lower bound */
1973  if( set->misc_exactsolve )
1974  newpseudoobjval = SCIPlpGetModifiedProvedPseudoObjval(lp, set, var, oldbound, newbound, boundtype);
1975  else
1976  newpseudoobjval = SCIPlpGetModifiedPseudoObjval(lp, set, transprob, var, oldbound, newbound, boundtype);
1977  SCIPnodeUpdateLowerbound(node, stat, set, tree, transprob, origprob, newpseudoobjval);
1978  }
1979  else
1980  {
1981  /* check the infered bound change on the debugging solution */
1982  SCIP_CALL( SCIPdebugCheckInference(blkmem, set, node, var, newbound, boundtype) ); /*lint !e506 !e774*/
1983 
1984  /* remember the bound change as inference (lpsolval is not important: use 0.0) */
1985  SCIP_CALL( SCIPdomchgAddBoundchg(&node->domchg, blkmem, set, var, newbound, boundtype,
1987  0.0, infervar, infercons, inferprop, inferinfo, inferboundtype) );
1988  }
1989 
1990  assert(node->domchg != NULL);
1991  assert(node->domchg->domchgdyn.domchgtype == SCIP_DOMCHGTYPE_DYNAMIC); /*lint !e641*/
1992  assert(node->domchg->domchgdyn.boundchgs != NULL);
1993  assert(node->domchg->domchgdyn.nboundchgs > 0);
1994  assert(node->domchg->domchgdyn.boundchgs[node->domchg->domchgdyn.nboundchgs-1].var == var);
1995  assert(node->domchg->domchgdyn.boundchgs[node->domchg->domchgdyn.nboundchgs-1].newbound == newbound); /*lint !e777*/
1996 
1997  /* if node is active, apply the bound change immediately */
1998  if( node->active )
1999  {
2000  SCIP_Bool cutoff;
2001 
2002  /**@todo if the node is active, it currently must either be the effective root (see above) or the current node;
2003  * if a bound change to an intermediate active node should be added, we must make sure, the bound change
2004  * information array of the variable stays sorted (new info must be sorted in instead of putting it to
2005  * the end of the array), and we should identify now redundant bound changes that are applied at a
2006  * later node on the active path
2007  */
2008  assert(SCIPtreeGetCurrentNode(tree) == node);
2010  blkmem, set, stat, lp, branchcand, eventqueue, node->depth, node->domchg->domchgdyn.nboundchgs-1, &cutoff) );
2011  assert(node->domchg->domchgdyn.boundchgs[node->domchg->domchgdyn.nboundchgs-1].var == var);
2012  assert(!cutoff);
2013  }
2014 
2015  return SCIP_OKAY;
2016 }
2017 
2018 /** adds bound change to focus node, or child of focus node, or probing node;
2019  * if possible, adjusts bound to integral value
2020  */
2022  SCIP_NODE* node, /**< node to add bound change to */
2023  BMS_BLKMEM* blkmem, /**< block memory */
2024  SCIP_SET* set, /**< global SCIP settings */
2025  SCIP_STAT* stat, /**< problem statistics */
2026  SCIP_PROB* transprob, /**< transformed problem after presolve */
2027  SCIP_PROB* origprob, /**< original problem */
2028  SCIP_TREE* tree, /**< branch and bound tree */
2029  SCIP_REOPT* reopt, /**< reoptimization data structure */
2030  SCIP_LP* lp, /**< current LP data */
2031  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2032  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2033  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2034  SCIP_VAR* var, /**< variable to change the bounds for */
2035  SCIP_Real newbound, /**< new value for bound */
2036  SCIP_BOUNDTYPE boundtype, /**< type of bound: lower or upper bound */
2037  SCIP_Bool probingchange /**< is the bound change a temporary setting due to probing? */
2038  )
2039 {
2040  SCIP_CALL( SCIPnodeAddBoundinfer(node, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
2041  cliquetable, var, newbound, boundtype, NULL, NULL, 0, probingchange) );
2042 
2043  return SCIP_OKAY;
2044 }
2045 
2046 /** adds hole with inference information to focus node, child of focus node, or probing node;
2047  * if possible, adjusts bound to integral value;
2048  * at most one of infercons and inferprop may be non-NULL
2049  */
2051  SCIP_NODE* node, /**< node to add bound change to */
2052  BMS_BLKMEM* blkmem, /**< block memory */
2053  SCIP_SET* set, /**< global SCIP settings */
2054  SCIP_STAT* stat, /**< problem statistics */
2055  SCIP_TREE* tree, /**< branch and bound tree */
2056  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2057  SCIP_VAR* var, /**< variable to change the bounds for */
2058  SCIP_Real left, /**< left bound of open interval defining the hole (left,right) */
2059  SCIP_Real right, /**< right bound of open interval defining the hole (left,right) */
2060  SCIP_CONS* infercons, /**< constraint that deduced the bound change, or NULL */
2061  SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
2062  int inferinfo, /**< user information for inference to help resolving the conflict */
2063  SCIP_Bool probingchange, /**< is the bound change a temporary setting due to probing? */
2064  SCIP_Bool* added /**< pointer to store whether the hole was added, or NULL */
2065  )
2066 {
2067 #if 0
2068  SCIP_VAR* infervar;
2069 #endif
2070 
2071  assert(node != NULL);
2076  || node->depth == 0);
2077  assert(blkmem != NULL);
2078  assert(set != NULL);
2079  assert(tree != NULL);
2080  assert(tree->effectiverootdepth >= 0);
2081  assert(tree->root != NULL);
2082  assert(var != NULL);
2083  assert(node->active || (infercons == NULL && inferprop == NULL));
2084  assert((SCIP_NODETYPE)node->nodetype == SCIP_NODETYPE_PROBINGNODE || !probingchange);
2085 
2086  /* the interval should not be empty */
2087  assert(SCIPsetIsLT(set, left, right));
2088 
2089 #ifndef NDEBUG
2090  {
2091  SCIP_Real adjustedleft;
2092  SCIP_Real adjustedright;
2093 
2094  adjustedleft = left;
2095  adjustedright = right;
2096 
2097  SCIPvarAdjustUb(var, set, &adjustedleft);
2098  SCIPvarAdjustLb(var, set, &adjustedright);
2099 
2100  assert(SCIPsetIsEQ(set, left, adjustedleft));
2101  assert(SCIPsetIsEQ(set, right, adjustedright));
2102  }
2103 #endif
2104 
2105  /* the hole should lay within the lower and upper bounds */
2106  assert(SCIPsetIsGE(set, left, SCIPvarGetLbLocal(var)));
2107  assert(SCIPsetIsLE(set, right, SCIPvarGetUbLocal(var)));
2108 
2109  SCIPsetDebugMsg(set, "adding hole (%g,%g) at node at depth %u to variable <%s>: bounds=[%g,%g], (infer%s=<%s>, inferinfo=%d)\n",
2110  left, right, node->depth, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), infercons != NULL ? "cons" : "prop",
2111  infercons != NULL ? SCIPconsGetName(infercons) : (inferprop != NULL ? SCIPpropGetName(inferprop) : "-"), inferinfo);
2112 
2113 #if 0
2114  /* remember variable as inference variable, and get corresponding active variable, bound and bound type */
2115  infervar = var;
2116 #endif
2117  SCIP_CALL( SCIPvarGetProbvarHole(&var, &left, &right) );
2118 
2120  {
2121  SCIPerrorMessage("cannot change bounds of multi-aggregated variable <%s>\n", SCIPvarGetName(var));
2122  SCIPABORT();
2123  return SCIP_INVALIDDATA; /*lint !e527*/
2124  }
2126 
2127  SCIPsetDebugMsg(set, " -> transformed to active variable <%s>: hole (%g,%g), obj: %g\n", SCIPvarGetName(var), left, right, SCIPvarGetObj(var));
2128 
2129  stat->nholechgs++;
2130 
2131  /* if we are in probing mode we have to additionally count the bound changes for the probing statistic */
2132  if( tree->probingroot != NULL )
2133  stat->nprobholechgs++;
2134 
2135  /* if the node is the root node: change local and global bound immediately */
2136  if( SCIPnodeGetDepth(node) <= tree->effectiverootdepth )
2137  {
2138  assert(node->active || tree->focusnode == NULL );
2139  assert(SCIPnodeGetType(node) != SCIP_NODETYPE_PROBINGNODE);
2140  assert(!probingchange);
2141 
2142  SCIPsetDebugMsg(set, " -> hole added in root node: perform global domain change\n");
2143  SCIP_CALL( SCIPvarAddHoleGlobal(var, blkmem, set, stat, eventqueue, left, right, added) );
2144 
2145  if( set->stage == SCIP_STAGE_SOLVING && (*added) )
2146  {
2147  /* the root should be repropagated due to the bound change */
2148  SCIPnodePropagateAgain(tree->root, set, stat, tree);
2149  SCIPsetDebugMsg(set, "marked root node to be repropagated due to global added hole <%s>: (%g,%g) found in depth %u\n",
2150  SCIPvarGetName(var), left, right, node->depth);
2151  }
2152 
2153  return SCIP_OKAY;
2154  }
2155 
2156  /**@todo add adding of local domain holes */
2157 
2158  (*added) = FALSE;
2159  SCIPerrorMessage("WARNING: currently domain holes can only be handled globally!\n");
2160 
2161  stat->nholechgs--;
2162 
2163  /* if we are in probing mode we have to additionally count the bound changes for the probing statistic */
2164  if( tree->probingroot != NULL )
2165  stat->nprobholechgs--;
2166 
2167  return SCIP_OKAY;
2168 }
2169 
2170 /** adds hole change to focus node, or child of focus node */
2172  SCIP_NODE* node, /**< node to add bound change to */
2173  BMS_BLKMEM* blkmem, /**< block memory */
2174  SCIP_SET* set, /**< global SCIP settings */
2175  SCIP_STAT* stat, /**< problem statistics */
2176  SCIP_TREE* tree, /**< branch and bound tree */
2177  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2178  SCIP_VAR* var, /**< variable to change the bounds for */
2179  SCIP_Real left, /**< left bound of open interval defining the hole (left,right) */
2180  SCIP_Real right, /**< right bound of open interval defining the hole (left,right) */
2181  SCIP_Bool probingchange, /**< is the bound change a temporary setting due to probing? */
2182  SCIP_Bool* added /**< pointer to store whether the hole was added, or NULL */
2183  )
2184 {
2185  assert(node != NULL);
2189  assert(blkmem != NULL);
2190 
2191  SCIPsetDebugMsg(set, "adding hole (%g,%g) at node at depth %u of variable <%s>\n",
2192  left, right, node->depth, SCIPvarGetName(var));
2193 
2194  SCIP_CALL( SCIPnodeAddHoleinfer(node, blkmem, set, stat, tree, eventqueue, var, left, right,
2195  NULL, NULL, 0, probingchange, added) );
2196 
2197  /**@todo apply hole change on active nodes and issue event */
2198 
2199  return SCIP_OKAY;
2200 }
2201 
2202 /** applies the pending bound changes */
2203 static
2205  SCIP_TREE* tree, /**< branch and bound tree */
2206  SCIP_REOPT* reopt, /**< reoptimization data structure */
2207  BMS_BLKMEM* blkmem, /**< block memory */
2208  SCIP_SET* set, /**< global SCIP settings */
2209  SCIP_STAT* stat, /**< problem statistics */
2210  SCIP_PROB* transprob, /**< transformed problem after presolve */
2211  SCIP_PROB* origprob, /**< original problem */
2212  SCIP_LP* lp, /**< current LP data */
2213  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2214  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2215  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
2216  )
2217 {
2218  SCIP_VAR* var;
2219  int npendingbdchgs;
2220  int conflictdepth;
2221  int i;
2222 
2223  assert(tree != NULL);
2224 
2225  npendingbdchgs = tree->npendingbdchgs;
2226  for( i = 0; i < npendingbdchgs; ++i )
2227  {
2228  var = tree->pendingbdchgs[i].var;
2229  assert(SCIPnodeGetDepth(tree->pendingbdchgs[i].node) < tree->cutoffdepth);
2230 
2231  conflictdepth = SCIPvarGetConflictingBdchgDepth(var, set, tree->pendingbdchgs[i].boundtype,
2232  tree->pendingbdchgs[i].newbound);
2233 
2234  /* It can happen, that a pending bound change conflicts with the global bounds, because when it was collected, it
2235  * just conflicted with the local bounds, but a conflicting global bound change was applied afterwards. In this
2236  * case, we can cut off the node where the pending bound change should be applied.
2237  */
2238  if( conflictdepth == 0 )
2239  {
2240  SCIP_CALL( SCIPnodeCutoff(tree->pendingbdchgs[i].node, set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
2241 
2242  if( ((int) tree->pendingbdchgs[i].node->depth) <= tree->effectiverootdepth )
2243  return SCIP_OKAY;
2244  else
2245  continue;
2246  }
2247 
2248  assert(conflictdepth == -1);
2249 
2250  SCIPsetDebugMsg(set, "applying pending bound change <%s>[%g,%g] %s %g\n", SCIPvarGetName(var),
2252  tree->pendingbdchgs[i].boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
2253  tree->pendingbdchgs[i].newbound);
2254 
2255  /* ignore bounds that are now redundant (for example, multiple entries in the pendingbdchgs for the same
2256  * variable)
2257  */
2258  if( tree->pendingbdchgs[i].boundtype == SCIP_BOUNDTYPE_LOWER )
2259  {
2260  SCIP_Real lb;
2261 
2262  lb = SCIPvarGetLbLocal(var);
2263  if( !SCIPsetIsGT(set, tree->pendingbdchgs[i].newbound, lb) )
2264  {
2265  /* release the variable */
2266  SCIP_CALL( SCIPvarRelease(&var, blkmem, set, eventqueue, lp) );
2267  continue;
2268  }
2269  }
2270  else
2271  {
2272  SCIP_Real ub;
2273 
2274  assert(tree->pendingbdchgs[i].boundtype == SCIP_BOUNDTYPE_UPPER);
2275  ub = SCIPvarGetUbLocal(var);
2276  if( !SCIPsetIsLT(set, tree->pendingbdchgs[i].newbound, ub) )
2277  {
2278  /* release the variable */
2279  SCIP_CALL( SCIPvarRelease(&var, blkmem, set, eventqueue, lp) );
2280  continue;
2281  }
2282  }
2283 
2284  SCIP_CALL( SCIPnodeAddBoundinfer(tree->pendingbdchgs[i].node, blkmem, set, stat, transprob, origprob, tree, reopt,
2285  lp, branchcand, eventqueue, cliquetable, var, tree->pendingbdchgs[i].newbound, tree->pendingbdchgs[i].boundtype,
2287  tree->pendingbdchgs[i].probingchange) );
2288  assert(tree->npendingbdchgs == npendingbdchgs); /* this time, the bound change can be applied! */
2289 
2290  /* release the variable */
2291  SCIP_CALL( SCIPvarRelease(&var, blkmem, set, eventqueue, lp) );
2292  }
2293  tree->npendingbdchgs = 0;
2294 
2295  return SCIP_OKAY;
2296 }
2297 
2298 /** if given value is larger than the node's lower bound, sets the node's lower bound to the new value */
2300  SCIP_NODE* node, /**< node to update lower bound for */
2301  SCIP_STAT* stat, /**< problem statistics */
2302  SCIP_SET* set, /**< global SCIP settings */
2303  SCIP_TREE* tree, /**< branch and bound tree */
2304  SCIP_PROB* transprob, /**< transformed problem after presolve */
2305  SCIP_PROB* origprob, /**< original problem */
2306  SCIP_Real newbound /**< new lower bound for the node (if it's larger than the old one) */
2307  )
2308 {
2309  assert(node != NULL);
2310  assert(stat != NULL);
2311 
2312  if( newbound > node->lowerbound )
2313  {
2314  SCIP_Real oldbound;
2315 
2316  oldbound = node->lowerbound;
2317  node->lowerbound = newbound;
2318  node->estimate = MAX(node->estimate, newbound);
2319 
2320  if( node->depth == 0 )
2321  {
2322  stat->rootlowerbound = newbound;
2323  if( set->misc_calcintegral )
2324  SCIPstatUpdatePrimalDualIntegral(stat, set, transprob, origprob, SCIPsetInfinity(set), newbound);
2325  SCIPvisualLowerbound(stat->visual, set, stat, newbound);
2326  }
2327  else if ( SCIPnodeGetType(node) != SCIP_NODETYPE_PROBINGNODE )
2328  {
2329  SCIP_Real lowerbound;
2330 
2331  lowerbound = SCIPtreeGetLowerbound(tree, set);
2332  assert(newbound >= lowerbound);
2333  SCIPvisualLowerbound(stat->visual, set, stat, lowerbound);
2334 
2335  /* updating the primal integral is only necessary if dual bound has increased since last evaluation */
2336  if( set->misc_calcintegral && SCIPsetIsEQ(set, oldbound, stat->lastlowerbound) && lowerbound > stat->lastlowerbound )
2337  SCIPstatUpdatePrimalDualIntegral(stat, set, transprob, origprob, SCIPsetInfinity(set), lowerbound);
2338  }
2339  }
2340 }
2341 
2342 /** updates lower bound of node using lower bound of LP */
2344  SCIP_NODE* node, /**< node to set lower bound for */
2345  SCIP_SET* set, /**< global SCIP settings */
2346  SCIP_STAT* stat, /**< problem statistics */
2347  SCIP_TREE* tree, /**< branch and bound tree */
2348  SCIP_PROB* transprob, /**< transformed problem after presolve */
2349  SCIP_PROB* origprob, /**< original problem */
2350  SCIP_LP* lp /**< LP data */
2351  )
2352 {
2353  SCIP_Real lpobjval;
2354 
2355  assert(set != NULL);
2356  assert(lp->flushed);
2357 
2358  /* in case of iteration or time limit, the LP value may not be a valid dual bound */
2359  /* @todo check for dual feasibility of LP solution and use sub-optimal solution if they are dual feasible */
2361  return SCIP_OKAY;
2362 
2363  if( set->misc_exactsolve )
2364  {
2365  SCIP_CALL( SCIPlpGetProvedLowerbound(lp, set, &lpobjval) );
2366  }
2367  else
2368  lpobjval = SCIPlpGetObjval(lp, set, transprob);
2369 
2370  SCIPnodeUpdateLowerbound(node, stat, set, tree, transprob, origprob, lpobjval);
2371 
2372  return SCIP_OKAY;
2373 }
2374 
2375 
2376 /** change the node selection priority of the given child */
2378  SCIP_TREE* tree, /**< branch and bound tree */
2379  SCIP_NODE* child, /**< child to update the node selection priority */
2380  SCIP_Real priority /**< node selection priority value */
2381  )
2382 {
2383  int pos;
2384 
2385  assert( SCIPnodeGetType(child) == SCIP_NODETYPE_CHILD );
2386 
2387  pos = child->data.child.arraypos;
2388  assert( pos >= 0 );
2389 
2390  tree->childrenprio[pos] = priority;
2391 }
2392 
2393 
2394 /** sets the node's estimated bound to the new value */
2396  SCIP_NODE* node, /**< node to update lower bound for */
2397  SCIP_SET* set, /**< global SCIP settings */
2398  SCIP_Real newestimate /**< new estimated bound for the node */
2399  )
2400 {
2401  assert(node != NULL);
2402  assert(set != NULL);
2403  assert(SCIPsetIsRelGE(set, newestimate, node->lowerbound));
2404 
2405  node->estimate = newestimate;
2406 }
2407 
2408 /** propagates implications of binary fixings at the given node triggered by the implication graph and the clique table */
2410  SCIP_NODE* node, /**< node to propagate implications on */
2411  BMS_BLKMEM* blkmem, /**< block memory */
2412  SCIP_SET* set, /**< global SCIP settings */
2413  SCIP_STAT* stat, /**< problem statistics */
2414  SCIP_PROB* transprob, /**< transformed problem after presolve */
2415  SCIP_PROB* origprob, /**< original problem */
2416  SCIP_TREE* tree, /**< branch and bound tree */
2417  SCIP_REOPT* reopt, /**< reoptimization data structure */
2418  SCIP_LP* lp, /**< current LP data */
2419  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2420  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2421  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2422  SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
2423  )
2424 {
2425  int nboundchgs;
2426  int i;
2427 
2428  assert(node != NULL);
2429  assert(SCIPnodeIsActive(node));
2433  assert(cutoff != NULL);
2434 
2435  SCIPsetDebugMsg(set, "implication graph propagation of node #%" SCIP_LONGINT_FORMAT " in depth %d\n",
2436  SCIPnodeGetNumber(node), SCIPnodeGetDepth(node));
2437 
2438  *cutoff = FALSE;
2439 
2440  /* propagate all fixings of binary variables performed at this node */
2441  nboundchgs = SCIPdomchgGetNBoundchgs(node->domchg);
2442  for( i = 0; i < nboundchgs && !(*cutoff); ++i )
2443  {
2444  SCIP_BOUNDCHG* boundchg;
2445  SCIP_VAR* var;
2446 
2447  boundchg = SCIPdomchgGetBoundchg(node->domchg, i);
2448 
2449  /* ignore redundant bound changes */
2450  if( SCIPboundchgIsRedundant(boundchg) )
2451  continue;
2452 
2453  var = SCIPboundchgGetVar(boundchg);
2454  if( SCIPvarIsBinary(var) )
2455  {
2456  SCIP_Bool varfixing;
2457  int nimpls;
2458  SCIP_VAR** implvars;
2459  SCIP_BOUNDTYPE* impltypes;
2460  SCIP_Real* implbounds;
2461  SCIP_CLIQUE** cliques;
2462  int ncliques;
2463  int j;
2464 
2465  varfixing = (SCIPboundchgGetBoundtype(boundchg) == SCIP_BOUNDTYPE_LOWER);
2466  nimpls = SCIPvarGetNImpls(var, varfixing);
2467  implvars = SCIPvarGetImplVars(var, varfixing);
2468  impltypes = SCIPvarGetImplTypes(var, varfixing);
2469  implbounds = SCIPvarGetImplBounds(var, varfixing);
2470 
2471  /* apply implications */
2472  for( j = 0; j < nimpls; ++j )
2473  {
2474  SCIP_Real lb;
2475  SCIP_Real ub;
2476 
2477  /* @note should this be checked here (because SCIPnodeAddBoundinfer fails for multi-aggregated variables)
2478  * or should SCIPnodeAddBoundinfer() just return for multi-aggregated variables?
2479  */
2481  continue;
2482 
2483  /* check for infeasibility */
2484  lb = SCIPvarGetLbLocal(implvars[j]);
2485  ub = SCIPvarGetUbLocal(implvars[j]);
2486  if( impltypes[j] == SCIP_BOUNDTYPE_LOWER )
2487  {
2488  if( SCIPsetIsFeasGT(set, implbounds[j], ub) )
2489  {
2490  *cutoff = TRUE;
2491  return SCIP_OKAY;
2492  }
2493  if( SCIPsetIsFeasLE(set, implbounds[j], lb) )
2494  continue;
2495  }
2496  else
2497  {
2498  if( SCIPsetIsFeasLT(set, implbounds[j], lb) )
2499  {
2500  *cutoff = TRUE;
2501  return SCIP_OKAY;
2502  }
2503  if( SCIPsetIsFeasGE(set, implbounds[j], ub) )
2504  continue;
2505  }
2506 
2507  /* @note the implication might affect a fixed variable (after resolving (multi-)aggregations);
2508  * normally, the implication should have been deleted in that case, but this is only possible
2509  * if the implied variable has the reverse implication stored as a variable bound;
2510  * due to numerics, the variable bound may not be present and so the implication is not deleted
2511  */
2513  continue;
2514 
2515  /* apply the implication */
2516  SCIP_CALL( SCIPnodeAddBoundinfer(node, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
2517  eventqueue, cliquetable, implvars[j], implbounds[j], impltypes[j], NULL, NULL, 0, FALSE) );
2518  }
2519 
2520  /* apply cliques */
2521  ncliques = SCIPvarGetNCliques(var, varfixing);
2522  cliques = SCIPvarGetCliques(var, varfixing);
2523  for( j = 0; j < ncliques; ++j )
2524  {
2525  SCIP_VAR** vars;
2526  SCIP_Bool* values;
2527  int nvars;
2528  int k;
2529 
2530  nvars = SCIPcliqueGetNVars(cliques[j]);
2531  vars = SCIPcliqueGetVars(cliques[j]);
2532  values = SCIPcliqueGetValues(cliques[j]);
2533  for( k = 0; k < nvars; ++k )
2534  {
2535  SCIP_Real lb;
2536  SCIP_Real ub;
2537 
2538  assert(SCIPvarIsBinary(vars[k]));
2539 
2540  if( SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_MULTAGGR )
2541  continue;
2542 
2543  if( vars[k] == var && values[k] == varfixing )
2544  continue;
2545 
2546  /* check for infeasibility */
2547  lb = SCIPvarGetLbLocal(vars[k]);
2548  ub = SCIPvarGetUbLocal(vars[k]);
2549  if( values[k] == FALSE )
2550  {
2551  if( ub < 0.5 )
2552  {
2553  *cutoff = TRUE;
2554  return SCIP_OKAY;
2555  }
2556  if( lb > 0.5 )
2557  continue;
2558  }
2559  else
2560  {
2561  if( lb > 0.5 )
2562  {
2563  *cutoff = TRUE;
2564  return SCIP_OKAY;
2565  }
2566  if( ub < 0.5 )
2567  continue;
2568  }
2569 
2571  continue;
2572 
2573  /* apply the clique implication */
2574  SCIP_CALL( SCIPnodeAddBoundinfer(node, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
2575  eventqueue, cliquetable, vars[k], (SCIP_Real)(!values[k]), values[k] ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER,
2576  NULL, NULL, 0, FALSE) );
2577  }
2578  }
2579  }
2580  }
2581 
2582  return SCIP_OKAY;
2583 }
2584 
2585 
2586 
2587 
2588 /*
2589  * Path Switching
2590  */
2591 
2592 /** updates the LP sizes of the active path starting at the given depth */
2593 static
2595  SCIP_TREE* tree, /**< branch and bound tree */
2596  int startdepth /**< depth to start counting */
2597  )
2598 {
2599  SCIP_NODE* node;
2600  int ncols;
2601  int nrows;
2602  int i;
2603 
2604  assert(tree != NULL);
2605  assert(startdepth >= 0);
2606  assert(startdepth <= tree->pathlen);
2607 
2608  if( startdepth == 0 )
2609  {
2610  ncols = 0;
2611  nrows = 0;
2612  }
2613  else
2614  {
2615  ncols = tree->pathnlpcols[startdepth-1];
2616  nrows = tree->pathnlprows[startdepth-1];
2617  }
2618 
2619  for( i = startdepth; i < tree->pathlen; ++i )
2620  {
2621  node = tree->path[i];
2622  assert(node != NULL);
2623  assert(node->active);
2624  assert((int)(node->depth) == i);
2625 
2626  switch( SCIPnodeGetType(node) )
2627  {
2629  assert(i == tree->pathlen-1 || SCIPtreeProbing(tree));
2630  break;
2632  assert(SCIPtreeProbing(tree));
2633  assert(i >= 1);
2634  assert(SCIPnodeGetType(tree->path[i-1]) == SCIP_NODETYPE_FOCUSNODE
2635  || (ncols == node->data.probingnode->ninitialcols && nrows == node->data.probingnode->ninitialrows));
2636  assert(ncols <= node->data.probingnode->ncols || !tree->focuslpconstructed);
2637  assert(nrows <= node->data.probingnode->nrows || !tree->focuslpconstructed);
2638  if( i < tree->pathlen-1 )
2639  {
2640  ncols = node->data.probingnode->ncols;
2641  nrows = node->data.probingnode->nrows;
2642  }
2643  else
2644  {
2645  /* for the current probing node, the initial LP size is stored in the path */
2646  ncols = node->data.probingnode->ninitialcols;
2647  nrows = node->data.probingnode->ninitialrows;
2648  }
2649  break;
2650  case SCIP_NODETYPE_SIBLING:
2651  SCIPerrorMessage("sibling cannot be in the active path\n");
2652  SCIPABORT();
2653  return SCIP_INVALIDDATA; /*lint !e527*/
2654  case SCIP_NODETYPE_CHILD:
2655  SCIPerrorMessage("child cannot be in the active path\n");
2656  SCIPABORT();
2657  return SCIP_INVALIDDATA; /*lint !e527*/
2658  case SCIP_NODETYPE_LEAF:
2659  SCIPerrorMessage("leaf cannot be in the active path\n");
2660  SCIPABORT();
2661  return SCIP_INVALIDDATA; /*lint !e527*/
2662  case SCIP_NODETYPE_DEADEND:
2663  SCIPerrorMessage("dead-end cannot be in the active path\n");
2664  SCIPABORT();
2665  return SCIP_INVALIDDATA; /*lint !e527*/
2667  break;
2669  assert(node->data.pseudofork != NULL);
2670  ncols += node->data.pseudofork->naddedcols;
2671  nrows += node->data.pseudofork->naddedrows;
2672  break;
2673  case SCIP_NODETYPE_FORK:
2674  assert(node->data.fork != NULL);
2675  ncols += node->data.fork->naddedcols;
2676  nrows += node->data.fork->naddedrows;
2677  break;
2678  case SCIP_NODETYPE_SUBROOT:
2679  assert(node->data.subroot != NULL);
2680  ncols = node->data.subroot->ncols;
2681  nrows = node->data.subroot->nrows;
2682  break;
2684  SCIPerrorMessage("node cannot be of type REFOCUSNODE at this point\n");
2685  SCIPABORT();
2686  return SCIP_INVALIDDATA; /*lint !e527*/
2687  default:
2688  SCIPerrorMessage("unknown node type %d\n", SCIPnodeGetType(node));
2689  SCIPABORT();
2690  return SCIP_INVALIDDATA; /*lint !e527*/
2691  }
2692  tree->pathnlpcols[i] = ncols;
2693  tree->pathnlprows[i] = nrows;
2694  }
2695  return SCIP_OKAY;
2696 }
2697 
2698 /** finds the common fork node, the new LP state defining fork, and the new focus subroot, if the path is switched to
2699  * the given node
2700  */
2701 static
2703  SCIP_TREE* tree, /**< branch and bound tree */
2704  SCIP_NODE* node, /**< new focus node, or NULL */
2705  SCIP_NODE** commonfork, /**< pointer to store common fork node of old and new focus node */
2706  SCIP_NODE** newlpfork, /**< pointer to store the new LP defining fork node */
2707  SCIP_NODE** newlpstatefork, /**< pointer to store the new LP state defining fork node */
2708  SCIP_NODE** newsubroot, /**< pointer to store the new subroot node */
2709  SCIP_Bool* cutoff /**< pointer to store whether the given node can be cut off and no path switching
2710  * should be performed */
2711  )
2712 {
2713  SCIP_NODE* fork;
2714  SCIP_NODE* lpfork;
2715  SCIP_NODE* lpstatefork;
2716  SCIP_NODE* subroot;
2717 
2718  assert(tree != NULL);
2719  assert(tree->root != NULL);
2720  assert((tree->focusnode == NULL) == !tree->root->active);
2721  assert(tree->focuslpfork == NULL || tree->focusnode != NULL);
2722  assert(tree->focuslpfork == NULL || tree->focuslpfork->depth < tree->focusnode->depth);
2723  assert(tree->focuslpstatefork == NULL || tree->focuslpfork != NULL);
2724  assert(tree->focuslpstatefork == NULL || tree->focuslpstatefork->depth <= tree->focuslpfork->depth);
2725  assert(tree->focussubroot == NULL || tree->focuslpstatefork != NULL);
2726  assert(tree->focussubroot == NULL || tree->focussubroot->depth <= tree->focuslpstatefork->depth);
2727  assert(tree->cutoffdepth >= 0);
2728  assert(tree->cutoffdepth == INT_MAX || tree->cutoffdepth < tree->pathlen);
2729  assert(tree->cutoffdepth == INT_MAX || tree->path[tree->cutoffdepth]->cutoff);
2730  assert(tree->repropdepth >= 0);
2731  assert(tree->repropdepth == INT_MAX || tree->repropdepth < tree->pathlen);
2732  assert(tree->repropdepth == INT_MAX || tree->path[tree->repropdepth]->reprop);
2733  assert(commonfork != NULL);
2734  assert(newlpfork != NULL);
2735  assert(newlpstatefork != NULL);
2736  assert(newsubroot != NULL);
2737  assert(cutoff != NULL);
2738 
2739  *commonfork = NULL;
2740  *newlpfork = NULL;
2741  *newlpstatefork = NULL;
2742  *newsubroot = NULL;
2743  *cutoff = FALSE;
2744 
2745  /* if the new focus node is NULL, there is no common fork node, and the new LP fork, LP state fork, and subroot
2746  * are NULL
2747  */
2748  if( node == NULL )
2749  {
2750  tree->cutoffdepth = INT_MAX;
2751  tree->repropdepth = INT_MAX;
2752  return;
2753  }
2754 
2755  /* check if the new node is marked to be cut off */
2756  if( node->cutoff )
2757  {
2758  *cutoff = TRUE;
2759  return;
2760  }
2761 
2762  /* if the old focus node is NULL, there is no common fork node, and we have to search the new LP fork, LP state fork
2763  * and subroot
2764  */
2765  if( tree->focusnode == NULL )
2766  {
2767  assert(!tree->root->active);
2768  assert(tree->pathlen == 0);
2769  assert(tree->cutoffdepth == INT_MAX);
2770  assert(tree->repropdepth == INT_MAX);
2771 
2772  lpfork = node;
2773  while( SCIPnodeGetType(lpfork) != SCIP_NODETYPE_PSEUDOFORK
2775  {
2776  lpfork = lpfork->parent;
2777  if( lpfork == NULL )
2778  return;
2779  if( lpfork->cutoff )
2780  {
2781  *cutoff = TRUE;
2782  return;
2783  }
2784  }
2785  *newlpfork = lpfork;
2786 
2787  lpstatefork = lpfork;
2788  while( SCIPnodeGetType(lpstatefork) != SCIP_NODETYPE_FORK && SCIPnodeGetType(lpstatefork) != SCIP_NODETYPE_SUBROOT )
2789  {
2790  lpstatefork = lpstatefork->parent;
2791  if( lpstatefork == NULL )
2792  return;
2793  if( lpstatefork->cutoff )
2794  {
2795  *cutoff = TRUE;
2796  return;
2797  }
2798  }
2799  *newlpstatefork = lpstatefork;
2800 
2801  subroot = lpstatefork;
2802  while( SCIPnodeGetType(subroot) != SCIP_NODETYPE_SUBROOT )
2803  {
2804  subroot = subroot->parent;
2805  if( subroot == NULL )
2806  return;
2807  if( subroot->cutoff )
2808  {
2809  *cutoff = TRUE;
2810  return;
2811  }
2812  }
2813  *newsubroot = subroot;
2814 
2815  fork = subroot;
2816  while( fork->parent != NULL )
2817  {
2818  fork = fork->parent;
2819  if( fork->cutoff )
2820  {
2821  *cutoff = TRUE;
2822  return;
2823  }
2824  }
2825  return;
2826  }
2827 
2828  /* find the common fork node, the new LP defining fork, the new LP state defining fork, and the new focus subroot */
2829  fork = node;
2830  lpfork = NULL;
2831  lpstatefork = NULL;
2832  subroot = NULL;
2833  assert(fork != NULL);
2834 
2835  while( !fork->active )
2836  {
2837  fork = fork->parent;
2838  assert(fork != NULL); /* because the root is active, there must be a common fork node */
2839 
2840  if( fork->cutoff )
2841  {
2842  *cutoff = TRUE;
2843  return;
2844  }
2845  if( lpfork == NULL
2848  lpfork = fork;
2849  if( lpstatefork == NULL
2851  lpstatefork = fork;
2852  if( subroot == NULL && SCIPnodeGetType(fork) == SCIP_NODETYPE_SUBROOT )
2853  subroot = fork;
2854  }
2855  assert(lpfork == NULL || !lpfork->active || lpfork == fork);
2856  assert(lpstatefork == NULL || !lpstatefork->active || lpstatefork == fork);
2857  assert(subroot == NULL || !subroot->active || subroot == fork);
2858  SCIPdebugMessage("find switch forks: forkdepth=%u\n", fork->depth);
2859 
2860  /* if the common fork node is below the current cutoff depth, the cutoff node is an ancestor of the common fork
2861  * and thus an ancestor of the new focus node, s.t. the new node can also be cut off
2862  */
2863  assert((int)fork->depth != tree->cutoffdepth);
2864  if( (int)fork->depth > tree->cutoffdepth )
2865  {
2866 #ifndef NDEBUG
2867  while( !fork->cutoff )
2868  {
2869  fork = fork->parent;
2870  assert(fork != NULL);
2871  }
2872  assert((int)fork->depth >= tree->cutoffdepth);
2873 #endif
2874  *cutoff = TRUE;
2875  return;
2876  }
2877  tree->cutoffdepth = INT_MAX;
2878 
2879  /* if not already found, continue searching the LP defining fork; it cannot be deeper than the common fork */
2880  if( lpfork == NULL )
2881  {
2882  if( tree->focuslpfork != NULL && (int)(tree->focuslpfork->depth) > fork->depth )
2883  {
2884  /* focuslpfork is not on the same active path as the new node: we have to continue searching */
2885  lpfork = fork;
2886  while( lpfork != NULL
2888  && SCIPnodeGetType(lpfork) != SCIP_NODETYPE_FORK
2889  && SCIPnodeGetType(lpfork) != SCIP_NODETYPE_SUBROOT )
2890  {
2891  assert(lpfork->active);
2892  lpfork = lpfork->parent;
2893  }
2894  }
2895  else
2896  {
2897  /* focuslpfork is on the same active path as the new node: old and new node have the same lpfork */
2898  lpfork = tree->focuslpfork;
2899  }
2900  assert(lpfork == NULL || (int)(lpfork->depth) <= fork->depth);
2901  assert(lpfork == NULL || lpfork->active);
2902  }
2903  assert(lpfork == NULL
2905  || SCIPnodeGetType(lpfork) == SCIP_NODETYPE_FORK
2906  || SCIPnodeGetType(lpfork) == SCIP_NODETYPE_SUBROOT);
2907  SCIPdebugMessage("find switch forks: lpforkdepth=%d\n", lpfork == NULL ? -1 : (int)(lpfork->depth));
2908 
2909  /* if not already found, continue searching the LP state defining fork; it cannot be deeper than the
2910  * LP defining fork and the common fork
2911  */
2912  if( lpstatefork == NULL )
2913  {
2914  if( tree->focuslpstatefork != NULL && (int)(tree->focuslpstatefork->depth) > fork->depth )
2915  {
2916  /* focuslpstatefork is not on the same active path as the new node: we have to continue searching */
2917  if( lpfork != NULL && lpfork->depth < fork->depth )
2918  lpstatefork = lpfork;
2919  else
2920  lpstatefork = fork;
2921  while( lpstatefork != NULL
2922  && SCIPnodeGetType(lpstatefork) != SCIP_NODETYPE_FORK
2923  && SCIPnodeGetType(lpstatefork) != SCIP_NODETYPE_SUBROOT )
2924  {
2925  assert(lpstatefork->active);
2926  lpstatefork = lpstatefork->parent;
2927  }
2928  }
2929  else
2930  {
2931  /* focuslpstatefork is on the same active path as the new node: old and new node have the same lpstatefork */
2932  lpstatefork = tree->focuslpstatefork;
2933  }
2934  assert(lpstatefork == NULL || (int)(lpstatefork->depth) <= fork->depth);
2935  assert(lpstatefork == NULL || lpstatefork->active);
2936  }
2937  assert(lpstatefork == NULL
2938  || SCIPnodeGetType(lpstatefork) == SCIP_NODETYPE_FORK
2939  || SCIPnodeGetType(lpstatefork) == SCIP_NODETYPE_SUBROOT);
2940  assert(lpstatefork == NULL || (lpfork != NULL && lpstatefork->depth <= lpfork->depth));
2941  SCIPdebugMessage("find switch forks: lpstateforkdepth=%d\n", lpstatefork == NULL ? -1 : (int)(lpstatefork->depth));
2942 
2943  /* if not already found, continue searching the subroot; it cannot be deeper than the LP defining fork, the
2944  * LP state fork and the common fork
2945  */
2946  if( subroot == NULL )
2947  {
2948  if( tree->focussubroot != NULL && (int)(tree->focussubroot->depth) > fork->depth )
2949  {
2950  /* focussubroot is not on the same active path as the new node: we have to continue searching */
2951  if( lpstatefork != NULL && lpstatefork->depth < fork->depth )
2952  subroot = lpstatefork;
2953  else if( lpfork != NULL && lpfork->depth < fork->depth )
2954  subroot = lpfork;
2955  else
2956  subroot = fork;
2957  while( subroot != NULL && SCIPnodeGetType(subroot) != SCIP_NODETYPE_SUBROOT )
2958  {
2959  assert(subroot->active);
2960  subroot = subroot->parent;
2961  }
2962  }
2963  else
2964  subroot = tree->focussubroot;
2965  assert(subroot == NULL || subroot->depth <= fork->depth);
2966  assert(subroot == NULL || subroot->active);
2967  }
2968  assert(subroot == NULL || SCIPnodeGetType(subroot) == SCIP_NODETYPE_SUBROOT);
2969  assert(subroot == NULL || (lpstatefork != NULL && subroot->depth <= lpstatefork->depth));
2970  SCIPdebugMessage("find switch forks: subrootdepth=%d\n", subroot == NULL ? -1 : (int)(subroot->depth));
2971 
2972  /* if a node prior to the common fork should be repropagated, we select the node to be repropagated as common
2973  * fork in order to undo all bound changes up to this node, repropagate the node, and redo the bound changes
2974  * afterwards
2975  */
2976  if( (int)fork->depth > tree->repropdepth )
2977  {
2978  fork = tree->path[tree->repropdepth];
2979  assert(fork->active);
2980  assert(fork->reprop);
2981  }
2982 
2983  *commonfork = fork;
2984  *newlpfork = lpfork;
2985  *newlpstatefork = lpstatefork;
2986  *newsubroot = subroot;
2987 
2988 #ifndef NDEBUG
2989  while( fork != NULL )
2990  {
2991  assert(fork->active);
2992  assert(!fork->cutoff);
2993  assert(fork->parent == NULL || !fork->parent->reprop);
2994  fork = fork->parent;
2995  }
2996 #endif
2997  tree->repropdepth = INT_MAX;
2998 }
2999 
3000 /** switches the active path to the new focus node, applies domain and constraint set changes */
3001 static
3003  SCIP_TREE* tree, /**< branch and bound tree */
3004  SCIP_REOPT* reopt, /**< reoptimization data structure */
3005  BMS_BLKMEM* blkmem, /**< block memory buffers */
3006  SCIP_SET* set, /**< global SCIP settings */
3007  SCIP_STAT* stat, /**< problem statistics */
3008  SCIP_PROB* transprob, /**< transformed problem after presolve */
3009  SCIP_PROB* origprob, /**< original problem */
3010  SCIP_PRIMAL* primal, /**< primal data */
3011  SCIP_LP* lp, /**< current LP data */
3012  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3013  SCIP_CONFLICT* conflict, /**< conflict analysis data */
3014  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
3015  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3016  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3017  SCIP_NODE* fork, /**< common fork node of old and new focus node, or NULL */
3018  SCIP_NODE* focusnode, /**< new focus node, or NULL */
3019  SCIP_Bool* cutoff /**< pointer to store whether the new focus node can be cut off */
3020  )
3021 {
3022  int focusnodedepth; /* depth of the new focus node, or -1 if focusnode == NULL */
3023  int forkdepth; /* depth of the common subroot/fork/pseudofork/junction node, or -1 if no common fork exists */
3024  int i;
3025 
3026  assert(tree != NULL);
3027  assert(fork == NULL || (fork->active && !fork->cutoff));
3028  assert(fork == NULL || focusnode != NULL);
3029  assert(focusnode == NULL || (!focusnode->active && !focusnode->cutoff));
3030  assert(focusnode == NULL || SCIPnodeGetType(focusnode) == SCIP_NODETYPE_FOCUSNODE);
3031  assert(cutoff != NULL);
3032 
3033  *cutoff = FALSE;
3034 
3035  SCIPsetDebugMsg(set, "switch path: old pathlen=%d\n", tree->pathlen);
3036 
3037  /* get the nodes' depths */
3038  focusnodedepth = (focusnode != NULL ? (int)focusnode->depth : -1);
3039  forkdepth = (fork != NULL ? (int)fork->depth : -1);
3040  assert(forkdepth <= focusnodedepth);
3041  assert(forkdepth < tree->pathlen);
3042 
3043  /* delay events in path switching */
3044  SCIP_CALL( SCIPeventqueueDelay(eventqueue) );
3045 
3046  /* undo the domain and constraint set changes of the old active path by deactivating the path's nodes */
3047  for( i = tree->pathlen-1; i > forkdepth; --i )
3048  {
3049  SCIP_CALL( nodeDeactivate(tree->path[i], blkmem, set, stat, tree, lp, branchcand, eventqueue) );
3050  }
3051  tree->pathlen = forkdepth+1;
3052 
3053  /* apply the pending bound changes */
3054  SCIP_CALL( treeApplyPendingBdchgs(tree, reopt, blkmem, set, stat, transprob, origprob, lp, branchcand, eventqueue, cliquetable) );
3055 
3056  /* create the new active path */
3057  SCIP_CALL( treeEnsurePathMem(tree, set, focusnodedepth+1) );
3058 
3059  while( focusnode != fork )
3060  {
3061  assert(focusnode != NULL);
3062  assert(!focusnode->active);
3063  assert(!focusnode->cutoff);
3064  /* coverity[var_deref_op] */
3065  tree->path[focusnode->depth] = focusnode;
3066  focusnode = focusnode->parent;
3067  }
3068 
3069  /* fork might be cut off when applying the pending bound changes */
3070  if( fork != NULL && fork->cutoff )
3071  *cutoff = TRUE;
3072  else if( fork != NULL && fork->reprop )
3073  {
3074  /* propagate common fork again, if the reprop flag is set */
3075  assert(tree->path[forkdepth] == fork);
3076  assert(fork->active);
3077  assert(!fork->cutoff);
3078 
3079  SCIP_CALL( nodeRepropagate(fork, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, conflict,
3080  eventfilter, eventqueue, cliquetable, cutoff) );
3081  }
3082  assert(fork != NULL || !(*cutoff));
3083 
3084  /* Apply domain and constraint set changes of the new path by activating the path's nodes;
3085  * on the way, domain propagation might be applied again to the path's nodes, which can result in the cutoff of
3086  * the node (and its subtree).
3087  * We only activate all nodes down to the parent of the new focus node, because the events in this process are
3088  * delayed, which means that multiple changes of a bound of a variable are merged (and might even be cancelled out,
3089  * if the bound is first relaxed when deactivating a node on the old path and then tightened to the same value
3090  * when activating a node on the new path).
3091  * This is valid for all nodes down to the parent of the new focus node, since they have already been propagated.
3092  * Bound change events on the new focus node, however, must not be cancelled out, since they need to be propagated
3093  * and thus, the event must be thrown and catched by the constraint handlers to mark constraints for propagation.
3094  */
3095  for( i = forkdepth+1; i < focusnodedepth && !(*cutoff); ++i )
3096  {
3097  assert(!tree->path[i]->cutoff);
3098  assert(tree->pathlen == i);
3099 
3100  /* activate the node, and apply domain propagation if the reprop flag is set */
3101  tree->pathlen++;
3102  SCIP_CALL( nodeActivate(tree->path[i], blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
3103  conflict, eventfilter, eventqueue, cliquetable, cutoff) );
3104  }
3105 
3106  /* process the delayed events */
3107  SCIP_CALL( SCIPeventqueueProcess(eventqueue, blkmem, set, primal, lp, branchcand, eventfilter) );
3108 
3109  /* activate the new focus node; there is no need to delay these events */
3110  if( !(*cutoff) && (i == focusnodedepth) )
3111  {
3112  assert(!tree->path[focusnodedepth]->cutoff);
3113  assert(tree->pathlen == focusnodedepth);
3114 
3115  /* activate the node, and apply domain propagation if the reprop flag is set */
3116  tree->pathlen++;
3117  SCIP_CALL( nodeActivate(tree->path[focusnodedepth], blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
3118  conflict, eventfilter, eventqueue, cliquetable, cutoff) );
3119  }
3120 
3121  /* mark last node of path to be cut off, if a cutoff was found */
3122  if( *cutoff )
3123  {
3124  assert(tree->pathlen > 0);
3125  assert(tree->path[tree->pathlen-1]->active);
3126  SCIP_CALL( SCIPnodeCutoff(tree->path[tree->pathlen-1], set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
3127  }
3128 
3129  /* count the new LP sizes of the path */
3130  SCIP_CALL( treeUpdatePathLPSize(tree, forkdepth+1) );
3131 
3132  SCIPsetDebugMsg(set, "switch path: new pathlen=%d\n", tree->pathlen);
3133 
3134  return SCIP_OKAY;
3135 }
3136 
3137 /** loads the subroot's LP data */
3138 static
3140  SCIP_NODE* subroot, /**< subroot node to construct LP for */
3141  BMS_BLKMEM* blkmem, /**< block memory buffers */
3142  SCIP_SET* set, /**< global SCIP settings */
3143  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3144  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
3145  SCIP_LP* lp /**< current LP data */
3146  )
3147 {
3148  SCIP_COL** cols;
3149  SCIP_ROW** rows;
3150  int ncols;
3151  int nrows;
3152  int c;
3153  int r;
3154 
3155  assert(subroot != NULL);
3156  assert(SCIPnodeGetType(subroot) == SCIP_NODETYPE_SUBROOT);
3157  assert(subroot->data.subroot != NULL);
3158  assert(blkmem != NULL);
3159  assert(set != NULL);
3160  assert(lp != NULL);
3161 
3162  cols = subroot->data.subroot->cols;
3163  rows = subroot->data.subroot->rows;
3164  ncols = subroot->data.subroot->ncols;
3165  nrows = subroot->data.subroot->nrows;
3166 
3167  assert(ncols == 0 || cols != NULL);
3168  assert(nrows == 0 || rows != NULL);
3169 
3170  for( c = 0; c < ncols; ++c )
3171  {
3172  SCIP_CALL( SCIPlpAddCol(lp, set, cols[c], subroot->depth) );
3173  }
3174  for( r = 0; r < nrows; ++r )
3175  {
3176  SCIP_CALL( SCIPlpAddRow(lp, blkmem, set, eventqueue, eventfilter, rows[r], subroot->depth) );
3177  }
3178 
3179  return SCIP_OKAY;
3180 }
3181 
3182 /** loads the fork's additional LP data */
3183 static
3185  SCIP_NODE* fork, /**< fork node to construct additional LP for */
3186  BMS_BLKMEM* blkmem, /**< block memory buffers */
3187  SCIP_SET* set, /**< global SCIP settings */
3188  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3189  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
3190  SCIP_LP* lp /**< current LP data */
3191  )
3192 {
3193  SCIP_COL** cols;
3194  SCIP_ROW** rows;
3195  int ncols;
3196  int nrows;
3197  int c;
3198  int r;
3199 
3200  assert(fork != NULL);
3201  assert(SCIPnodeGetType(fork) == SCIP_NODETYPE_FORK);
3202  assert(fork->data.fork != NULL);
3203  assert(blkmem != NULL);
3204  assert(set != NULL);
3205  assert(lp != NULL);
3206 
3207  cols = fork->data.fork->addedcols;
3208  rows = fork->data.fork->addedrows;
3209  ncols = fork->data.fork->naddedcols;
3210  nrows = fork->data.fork->naddedrows;
3211 
3212  assert(ncols == 0 || cols != NULL);
3213  assert(nrows == 0 || rows != NULL);
3214 
3215  for( c = 0; c < ncols; ++c )
3216  {
3217  SCIP_CALL( SCIPlpAddCol(lp, set, cols[c], fork->depth) );
3218  }
3219  for( r = 0; r < nrows; ++r )
3220  {
3221  SCIP_CALL( SCIPlpAddRow(lp, blkmem, set, eventqueue, eventfilter, rows[r], fork->depth) );
3222  }
3223 
3224  return SCIP_OKAY;
3225 }
3226 
3227 /** loads the pseudofork's additional LP data */
3228 static
3230  SCIP_NODE* pseudofork, /**< pseudofork node to construct additional LP for */
3231  BMS_BLKMEM* blkmem, /**< block memory buffers */
3232  SCIP_SET* set, /**< global SCIP settings */
3233  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3234  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
3235  SCIP_LP* lp /**< current LP data */
3236  )
3237 {
3238  SCIP_COL** cols;
3239  SCIP_ROW** rows;
3240  int ncols;
3241  int nrows;
3242  int c;
3243  int r;
3244 
3245  assert(pseudofork != NULL);
3246  assert(SCIPnodeGetType(pseudofork) == SCIP_NODETYPE_PSEUDOFORK);
3247  assert(pseudofork->data.pseudofork != NULL);
3248  assert(blkmem != NULL);
3249  assert(set != NULL);
3250  assert(lp != NULL);
3251 
3252  cols = pseudofork->data.pseudofork->addedcols;
3253  rows = pseudofork->data.pseudofork->addedrows;
3254  ncols = pseudofork->data.pseudofork->naddedcols;
3255  nrows = pseudofork->data.pseudofork->naddedrows;
3256 
3257  assert(ncols == 0 || cols != NULL);
3258  assert(nrows == 0 || rows != NULL);
3259 
3260  for( c = 0; c < ncols; ++c )
3261  {
3262  SCIP_CALL( SCIPlpAddCol(lp, set, cols[c], pseudofork->depth) );
3263  }
3264  for( r = 0; r < nrows; ++r )
3265  {
3266  SCIP_CALL( SCIPlpAddRow(lp, blkmem, set, eventqueue, eventfilter, rows[r], pseudofork->depth) );
3267  }
3268 
3269  return SCIP_OKAY;
3270 }
3271 
3272 #ifndef NDEBUG
3273 /** checks validity of active path */
3274 static
3276  SCIP_TREE* tree /**< branch and bound tree */
3277  )
3278 {
3279  SCIP_NODE* node;
3280  int ncols;
3281  int nrows;
3282  int d;
3283 
3284  assert(tree != NULL);
3285  assert(tree->path != NULL);
3286 
3287  ncols = 0;
3288  nrows = 0;
3289  for( d = 0; d < tree->pathlen; ++d )
3290  {
3291  node = tree->path[d];
3292  assert(node != NULL);
3293  assert((int)(node->depth) == d);
3294  switch( SCIPnodeGetType(node) )
3295  {
3297  assert(SCIPtreeProbing(tree));
3298  assert(d >= 1);
3299  assert(SCIPnodeGetType(tree->path[d-1]) == SCIP_NODETYPE_FOCUSNODE
3300  || (ncols == node->data.probingnode->ninitialcols && nrows == node->data.probingnode->ninitialrows));
3301  assert(ncols <= node->data.probingnode->ncols || !tree->focuslpconstructed);
3302  assert(nrows <= node->data.probingnode->nrows || !tree->focuslpconstructed);
3303  if( d < tree->pathlen-1 )
3304  {
3305  ncols = node->data.probingnode->ncols;
3306  nrows = node->data.probingnode->nrows;
3307  }
3308  else
3309  {
3310  /* for the current probing node, the initial LP size is stored in the path */
3311  ncols = node->data.probingnode->ninitialcols;
3312  nrows = node->data.probingnode->ninitialrows;
3313  }
3314  break;
3316  break;
3318  ncols += node->data.pseudofork->naddedcols;
3319  nrows += node->data.pseudofork->naddedrows;
3320  break;
3321  case SCIP_NODETYPE_FORK:
3322  ncols += node->data.fork->naddedcols;
3323  nrows += node->data.fork->naddedrows;
3324  break;
3325  case SCIP_NODETYPE_SUBROOT:
3326  ncols = node->data.subroot->ncols;
3327  nrows = node->data.subroot->nrows;
3328  break;
3331  assert(d == tree->pathlen-1 || SCIPtreeProbing(tree));
3332  break;
3333  default:
3334  SCIPerrorMessage("node at depth %d on active path has to be of type JUNCTION, PSEUDOFORK, FORK, SUBROOT, FOCUSNODE, REFOCUSNODE, or PROBINGNODE, but is %d\n",
3335  d, SCIPnodeGetType(node));
3336  SCIPABORT();
3337  } /*lint !e788*/
3338  assert(tree->pathnlpcols[d] == ncols);
3339  assert(tree->pathnlprows[d] == nrows);
3340  }
3341 }
3342 #else
3343 #define treeCheckPath(tree) /**/
3344 #endif
3345 
3346 /** constructs the LP relaxation of the focus node */
3348  SCIP_TREE* tree, /**< branch and bound tree */
3349  BMS_BLKMEM* blkmem, /**< block memory buffers */
3350  SCIP_SET* set, /**< global SCIP settings */
3351  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3352  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
3353  SCIP_LP* lp, /**< current LP data */
3354  SCIP_Bool* initroot /**< pointer to store whether the root LP relaxation has to be initialized */
3355  )
3356 {
3357  SCIP_NODE* lpfork;
3358  int lpforkdepth;
3359  int d;
3360 
3361  assert(tree != NULL);
3362  assert(!tree->focuslpconstructed);
3363  assert(tree->path != NULL);
3364  assert(tree->pathlen > 0);
3365  assert(tree->focusnode != NULL);
3367  assert(SCIPnodeGetDepth(tree->focusnode) == tree->pathlen-1);
3368  assert(!SCIPtreeProbing(tree));
3369  assert(tree->focusnode == tree->path[tree->pathlen-1]);
3370  assert(blkmem != NULL);
3371  assert(set != NULL);
3372  assert(lp != NULL);
3373  assert(initroot != NULL);
3374 
3375  SCIPsetDebugMsg(set, "load LP for current fork node #%" SCIP_LONGINT_FORMAT " at depth %d\n",
3376  tree->focuslpfork == NULL ? -1 : SCIPnodeGetNumber(tree->focuslpfork),
3377  tree->focuslpfork == NULL ? -1 : SCIPnodeGetDepth(tree->focuslpfork));
3378  SCIPsetDebugMsg(set, "-> old LP has %d cols and %d rows\n", SCIPlpGetNCols(lp), SCIPlpGetNRows(lp));
3379  SCIPsetDebugMsg(set, "-> correct LP has %d cols and %d rows\n",
3380  tree->correctlpdepth >= 0 ? tree->pathnlpcols[tree->correctlpdepth] : 0,
3381  tree->correctlpdepth >= 0 ? tree->pathnlprows[tree->correctlpdepth] : 0);
3382  SCIPsetDebugMsg(set, "-> old correctlpdepth: %d\n", tree->correctlpdepth);
3383 
3384  treeCheckPath(tree);
3385 
3386  lpfork = tree->focuslpfork;
3387 
3388  /* find out the lpfork's depth (or -1, if lpfork is NULL) */
3389  if( lpfork == NULL )
3390  {
3391  assert(tree->correctlpdepth == -1 || tree->pathnlpcols[tree->correctlpdepth] == 0);
3392  assert(tree->correctlpdepth == -1 || tree->pathnlprows[tree->correctlpdepth] == 0);
3393  assert(tree->focuslpstatefork == NULL);
3394  assert(tree->focussubroot == NULL);
3395  lpforkdepth = -1;
3396  }
3397  else
3398  {
3399  assert(SCIPnodeGetType(lpfork) == SCIP_NODETYPE_PSEUDOFORK
3401  assert(lpfork->active);
3402  assert(tree->path[lpfork->depth] == lpfork);
3403  lpforkdepth = lpfork->depth;
3404  }
3405  assert(lpforkdepth < tree->pathlen-1); /* lpfork must not be the last (the focus) node of the active path */
3406 
3407  /* find out, if we are in the same subtree */
3408  if( tree->correctlpdepth >= 0 )
3409  {
3410  /* same subtree: shrink LP to the deepest node with correct LP */
3411  assert(lpforkdepth == -1 || tree->pathnlpcols[tree->correctlpdepth] <= tree->pathnlpcols[lpforkdepth]);
3412  assert(lpforkdepth == -1 || tree->pathnlprows[tree->correctlpdepth] <= tree->pathnlprows[lpforkdepth]);
3413  assert(lpforkdepth >= 0 || tree->pathnlpcols[tree->correctlpdepth] == 0);
3414  assert(lpforkdepth >= 0 || tree->pathnlprows[tree->correctlpdepth] == 0);
3415  SCIP_CALL( SCIPlpShrinkCols(lp, set, tree->pathnlpcols[tree->correctlpdepth]) );
3416  SCIP_CALL( SCIPlpShrinkRows(lp, blkmem, set, eventqueue, eventfilter, tree->pathnlprows[tree->correctlpdepth]) );
3417  }
3418  else
3419  {
3420  /* other subtree: fill LP with the subroot LP data */
3421  SCIP_CALL( SCIPlpClear(lp, blkmem, set, eventqueue, eventfilter) );
3422  if( tree->focussubroot != NULL )
3423  {
3424  SCIP_CALL( subrootConstructLP(tree->focussubroot, blkmem, set, eventqueue, eventfilter, lp) );
3425  tree->correctlpdepth = tree->focussubroot->depth;
3426  }
3427  }
3428 
3429  assert(lpforkdepth < tree->pathlen);
3430 
3431  /* add the missing columns and rows */
3432  for( d = tree->correctlpdepth+1; d <= lpforkdepth; ++d )
3433  {
3434  SCIP_NODE* pathnode;
3435 
3436  pathnode = tree->path[d];
3437  assert(pathnode != NULL);
3438  assert((int)(pathnode->depth) == d);
3439  assert(SCIPnodeGetType(pathnode) == SCIP_NODETYPE_JUNCTION
3441  || SCIPnodeGetType(pathnode) == SCIP_NODETYPE_FORK);
3442  if( SCIPnodeGetType(pathnode) == SCIP_NODETYPE_FORK )
3443  {
3444  SCIP_CALL( forkAddLP(pathnode, blkmem, set, eventqueue, eventfilter, lp) );
3445  }
3446  else if( SCIPnodeGetType(pathnode) == SCIP_NODETYPE_PSEUDOFORK )
3447  {
3448  SCIP_CALL( pseudoforkAddLP(pathnode, blkmem, set, eventqueue, eventfilter, lp) );
3449  }
3450  }
3451  tree->correctlpdepth = MAX(tree->correctlpdepth, lpforkdepth);
3452  assert(lpforkdepth == -1 || tree->pathnlpcols[tree->correctlpdepth] == tree->pathnlpcols[lpforkdepth]);
3453  assert(lpforkdepth == -1 || tree->pathnlprows[tree->correctlpdepth] == tree->pathnlprows[lpforkdepth]);
3454  assert(lpforkdepth == -1 || SCIPlpGetNCols(lp) == tree->pathnlpcols[lpforkdepth]);
3455  assert(lpforkdepth == -1 || SCIPlpGetNRows(lp) == tree->pathnlprows[lpforkdepth]);
3456  assert(lpforkdepth >= 0 || SCIPlpGetNCols(lp) == 0);
3457  assert(lpforkdepth >= 0 || SCIPlpGetNRows(lp) == 0);
3458 
3459  /* mark the LP's size, such that we know which rows and columns were added in the new node */
3460  SCIPlpMarkSize(lp);
3461 
3462  SCIPsetDebugMsg(set, "-> new correctlpdepth: %d\n", tree->correctlpdepth);
3463  SCIPsetDebugMsg(set, "-> new LP has %d cols and %d rows\n", SCIPlpGetNCols(lp), SCIPlpGetNRows(lp));
3464 
3465  /* if the correct LP depth is still -1, the root LP relaxation has to be initialized */
3466  *initroot = (tree->correctlpdepth == -1);
3467 
3468  /* mark the LP of the focus node constructed */
3469  tree->focuslpconstructed = TRUE;
3470 
3471  return SCIP_OKAY;
3472 }
3473 
3474 /** loads LP state for fork/subroot of the focus node */
3476  SCIP_TREE* tree, /**< branch and bound tree */
3477  BMS_BLKMEM* blkmem, /**< block memory buffers */
3478  SCIP_SET* set, /**< global SCIP settings */
3479  SCIP_STAT* stat, /**< dynamic problem statistics */
3480  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3481  SCIP_LP* lp /**< current LP data */
3482  )
3483 {
3484  SCIP_NODE* lpstatefork;
3485  SCIP_Bool updatefeas;
3486  SCIP_Bool checkbdchgs;
3487  int lpstateforkdepth;
3488  int d;
3489 
3490  assert(tree != NULL);
3491  assert(tree->focuslpconstructed);
3492  assert(tree->path != NULL);
3493  assert(tree->pathlen > 0);
3494  assert(tree->focusnode != NULL);
3495  assert(tree->correctlpdepth < tree->pathlen);
3497  assert(SCIPnodeGetDepth(tree->focusnode) == tree->pathlen-1);
3498  assert(!SCIPtreeProbing(tree));
3499  assert(tree->focusnode == tree->path[tree->pathlen-1]);
3500  assert(blkmem != NULL);
3501  assert(set != NULL);
3502  assert(lp != NULL);
3503 
3504  SCIPsetDebugMsg(set, "load LP state for current fork node #%" SCIP_LONGINT_FORMAT " at depth %d\n",
3506  tree->focuslpstatefork == NULL ? -1 : SCIPnodeGetDepth(tree->focuslpstatefork));
3507 
3508  lpstatefork = tree->focuslpstatefork;
3509 
3510  /* if there is no LP state defining fork, nothing can be done */
3511  if( lpstatefork == NULL )
3512  return SCIP_OKAY;
3513 
3514  /* get the lpstatefork's depth */
3515  assert(SCIPnodeGetType(lpstatefork) == SCIP_NODETYPE_FORK || SCIPnodeGetType(lpstatefork) == SCIP_NODETYPE_SUBROOT);
3516  assert(lpstatefork->active);
3517  assert(tree->path[lpstatefork->depth] == lpstatefork);
3518  lpstateforkdepth = lpstatefork->depth;
3519  assert(lpstateforkdepth < tree->pathlen-1); /* lpstatefork must not be the last (the focus) node of the active path */
3520  assert(lpstateforkdepth <= tree->correctlpdepth); /* LP must have been constructed at least up to the fork depth */
3521  assert(tree->pathnlpcols[tree->correctlpdepth] >= tree->pathnlpcols[lpstateforkdepth]); /* LP can only grow */
3522  assert(tree->pathnlprows[tree->correctlpdepth] >= tree->pathnlprows[lpstateforkdepth]); /* LP can only grow */
3523 
3524  /* load LP state */
3525  if( tree->focuslpstateforklpcount != stat->lpcount )
3526  {
3527  if( SCIPnodeGetType(lpstatefork) == SCIP_NODETYPE_FORK )
3528  {
3529  assert(lpstatefork->data.fork != NULL);
3530  SCIP_CALL( SCIPlpSetState(lp, blkmem, set, eventqueue, lpstatefork->data.fork->lpistate,
3531  lpstatefork->data.fork->lpwasprimfeas, lpstatefork->data.fork->lpwasprimchecked,
3532  lpstatefork->data.fork->lpwasdualfeas, lpstatefork->data.fork->lpwasdualchecked) );
3533  }
3534  else
3535  {
3536  assert(SCIPnodeGetType(lpstatefork) == SCIP_NODETYPE_SUBROOT);
3537  assert(lpstatefork->data.subroot != NULL);
3538  SCIP_CALL( SCIPlpSetState(lp, blkmem, set, eventqueue, lpstatefork->data.subroot->lpistate,
3539  lpstatefork->data.subroot->lpwasprimfeas, lpstatefork->data.subroot->lpwasprimchecked,
3540  lpstatefork->data.subroot->lpwasdualfeas, lpstatefork->data.subroot->lpwasdualchecked) );
3541  }
3542  updatefeas = !lp->solved || !lp->solisbasic;
3543  checkbdchgs = TRUE;
3544  }
3545  else
3546  {
3547  updatefeas = TRUE;
3548 
3549  /* we do not need to check the bounds, since primalfeasible is updated anyway when flushing the LP */
3550  checkbdchgs = FALSE;
3551  }
3552 
3553  if( updatefeas )
3554  {
3555  /* check whether the size of the LP increased (destroying primal/dual feasibility) */
3556  lp->primalfeasible = lp->primalfeasible
3557  && (tree->pathnlprows[tree->correctlpdepth] == tree->pathnlprows[lpstateforkdepth]);
3558  lp->primalchecked = lp->primalchecked
3559  && (tree->pathnlprows[tree->correctlpdepth] == tree->pathnlprows[lpstateforkdepth]);
3560  lp->dualfeasible = lp->dualfeasible
3561  && (tree->pathnlpcols[tree->correctlpdepth] == tree->pathnlpcols[lpstateforkdepth]);
3562  lp->dualchecked = lp->dualchecked
3563  && (tree->pathnlpcols[tree->correctlpdepth] == tree->pathnlpcols[lpstateforkdepth]);
3564 
3565  /* check the path from LP fork to focus node for domain changes (destroying primal feasibility of LP basis) */
3566  if( checkbdchgs )
3567  {
3568  for( d = lpstateforkdepth; d < (int)(tree->focusnode->depth) && lp->primalfeasible; ++d )
3569  {
3570  assert(d < tree->pathlen);
3571  lp->primalfeasible = (tree->path[d]->domchg == NULL || tree->path[d]->domchg->domchgbound.nboundchgs == 0);
3572  lp->primalchecked = lp->primalfeasible;
3573  }
3574  }
3575  }
3576 
3577  SCIPsetDebugMsg(set, "-> primalfeasible=%u, dualfeasible=%u\n", lp->primalfeasible, lp->dualfeasible);
3578 
3579  return SCIP_OKAY;
3580 }
3581 
3582 
3583 
3584 
3585 /*
3586  * Node Conversion
3587  */
3588 
3589 /** converts node into LEAF and moves it into the array of the node queue
3590  * if node's lower bound is greater or equal than the given upper bound, the node is deleted;
3591  * otherwise, it is moved to the node queue; anyways, the given pointer is NULL after the call
3592  */
3593 static
3595  SCIP_NODE** node, /**< pointer to child or sibling node to convert */
3596  BMS_BLKMEM* blkmem, /**< block memory buffers */
3597  SCIP_SET* set, /**< global SCIP settings */
3598  SCIP_STAT* stat, /**< dynamic problem statistics */
3599  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3600  SCIP_TREE* tree, /**< branch and bound tree */
3601  SCIP_REOPT* reopt, /**< reoptimization data structure */
3602  SCIP_LP* lp, /**< current LP data */
3603  SCIP_NODE* lpstatefork, /**< LP state defining fork of the node */
3604  SCIP_Real cutoffbound /**< cutoff bound: all nodes with lowerbound >= cutoffbound are cut off */
3605  )
3606 {
3609  assert(stat != NULL);
3610  assert(lpstatefork == NULL || lpstatefork->depth < (*node)->depth);
3611  assert(lpstatefork == NULL || lpstatefork->active || SCIPsetIsGE(set, (*node)->lowerbound, cutoffbound));
3612  assert(lpstatefork == NULL
3613  || SCIPnodeGetType(lpstatefork) == SCIP_NODETYPE_FORK
3614  || SCIPnodeGetType(lpstatefork) == SCIP_NODETYPE_SUBROOT);
3615 
3616  /* convert node into leaf */
3617  SCIPsetDebugMsg(set, "convert node #%" SCIP_LONGINT_FORMAT " at depth %d to leaf with lpstatefork #%" SCIP_LONGINT_FORMAT " at depth %d\n",
3618  SCIPnodeGetNumber(*node), SCIPnodeGetDepth(*node),
3619  lpstatefork == NULL ? -1 : SCIPnodeGetNumber(lpstatefork),
3620  lpstatefork == NULL ? -1 : SCIPnodeGetDepth(lpstatefork));
3621  (*node)->nodetype = SCIP_NODETYPE_LEAF; /*lint !e641*/
3622  (*node)->data.leaf.lpstatefork = lpstatefork;
3623 
3624 #ifndef NDEBUG
3625  /* check, if the LP state fork is the first node with LP state information on the path back to the root */
3626  if( !SCIPsetIsInfinity(set, -cutoffbound) ) /* if the node was cut off in SCIPnodeFocus(), the lpstatefork is invalid */
3627  {
3628  SCIP_NODE* pathnode;
3629  pathnode = (*node)->parent;
3630  while( pathnode != NULL && pathnode != lpstatefork )
3631  {
3632  assert(SCIPnodeGetType(pathnode) == SCIP_NODETYPE_JUNCTION
3633  || SCIPnodeGetType(pathnode) == SCIP_NODETYPE_PSEUDOFORK);
3634  pathnode = pathnode->parent;
3635  }
3636  assert(pathnode == lpstatefork);
3637  }
3638 #endif
3639 
3640  /* if node is good enough to keep, put it on the node queue */
3641  if( SCIPsetIsLT(set, (*node)->lowerbound, cutoffbound) )
3642  {
3643  /* insert leaf in node queue */
3644  SCIP_CALL( SCIPnodepqInsert(tree->leaves, set, *node) );
3645 
3646  /* make the domain change data static to save memory */
3647  SCIP_CALL( SCIPdomchgMakeStatic(&(*node)->domchg, blkmem, set, eventqueue, lp) );
3648 
3649  /* node is now member of the node queue: delete the pointer to forbid further access */
3650  *node = NULL;
3651  }
3652  else
3653  {
3654  if( set->reopt_enable )
3655  {
3656  assert(reopt != NULL);
3657  /* check if the node should be stored for reoptimization */
3659  tree->root == *node, tree->focusnode == *node, (*node)->lowerbound, tree->effectiverootdepth) );
3660  }
3661 
3662  /* delete node due to bound cut off */
3663  SCIPvisualCutoffNode(stat->visual, set, stat, *node, FALSE);
3664  SCIP_CALL( SCIPnodeFree(node, blkmem, set, stat, eventqueue, tree, lp) );
3665  }
3666  assert(*node == NULL);
3667 
3668  return SCIP_OKAY;
3669 }
3670 
3671 /** removes variables from the problem, that are marked to be deletable, and were created at the focusnode;
3672  * only removes variables that were created at the focusnode, unless inlp is TRUE (e.g., when the node is cut off, anyway)
3673  */
3674 static
3676  BMS_BLKMEM* blkmem, /**< block memory buffers */
3677  SCIP_SET* set, /**< global SCIP settings */
3678  SCIP_STAT* stat, /**< dynamic problem statistics */
3679  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3680  SCIP_PROB* transprob, /**< transformed problem after presolve */
3681  SCIP_PROB* origprob, /**< original problem */
3682  SCIP_TREE* tree, /**< branch and bound tree */
3683  SCIP_REOPT* reopt, /**< reoptimization data structure */
3684  SCIP_LP* lp, /**< current LP data */
3685  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3686  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3687  SCIP_Bool inlp /**< should variables in the LP be deleted, too?*/
3688  )
3689 {
3690  SCIP_VAR* var;
3691  int i;
3692  int ndelvars;
3693  SCIP_Bool needdel;
3694  SCIP_Bool deleted;
3695 
3696  assert(blkmem != NULL);
3697  assert(set != NULL);
3698  assert(stat != NULL);
3699  assert(tree != NULL);
3700  assert(!SCIPtreeProbing(tree));
3701  assert(tree->focusnode != NULL);
3703  assert(lp != NULL);
3704 
3705  /* check the settings, whether variables should be deleted */
3706  needdel = (tree->focusnode == tree->root ? set->price_delvarsroot : set->price_delvars);
3707 
3708  if( !needdel )
3709  return SCIP_OKAY;
3710 
3711  ndelvars = 0;
3712 
3713  /* also delete variables currently in the LP, thus remove all new variables from the LP, first */
3714  if( inlp )
3715  {
3716  /* remove all additions to the LP at this node */
3718 
3719  SCIP_CALL( SCIPlpFlush(lp, blkmem, set, eventqueue) );
3720  }
3721 
3722  /* mark variables as deleted */
3723  for( i = 0; i < transprob->nvars; i++ )
3724  {
3725  var = transprob->vars[i];
3726  assert(var != NULL);
3727 
3728  /* check whether variable is deletable */
3729  if( SCIPvarIsDeletable(var) )
3730  {
3731  if( !SCIPvarIsInLP(var) )
3732  {
3733  /* fix the variable to 0, first */
3734  assert(!SCIPsetIsFeasPositive(set, SCIPvarGetLbGlobal(var)));
3735  assert(!SCIPsetIsFeasNegative(set, SCIPvarGetUbGlobal(var)));
3736 
3737  if( !SCIPsetIsFeasZero(set, SCIPvarGetLbGlobal(var)) )
3738  {
3739  SCIP_CALL( SCIPnodeAddBoundchg(tree->root, blkmem, set, stat, transprob, origprob,
3740  tree, reopt, lp, branchcand, eventqueue, cliquetable, var, 0.0, SCIP_BOUNDTYPE_LOWER, FALSE) );
3741  }
3742  if( !SCIPsetIsFeasZero(set, SCIPvarGetUbGlobal(var)) )
3743  {
3744  SCIP_CALL( SCIPnodeAddBoundchg(tree->root, blkmem, set, stat, transprob, origprob,
3745  tree, reopt, lp, branchcand, eventqueue, cliquetable, var, 0.0, SCIP_BOUNDTYPE_UPPER, FALSE) );
3746  }
3747 
3748  SCIP_CALL( SCIPprobDelVar(transprob, blkmem, set, eventqueue, var, &deleted) );
3749 
3750  if( deleted )
3751  ndelvars++;
3752  }
3753  else
3754  {
3755  /* mark variable to be non-deletable, because it will be contained in the basis information
3756  * at this node and must not be deleted from now on
3757  */
3759  }
3760  }
3761  }
3762 
3763  SCIPsetDebugMsg(set, "delvars at node %" SCIP_LONGINT_FORMAT ", deleted %d vars\n", stat->nnodes, ndelvars);
3764 
3765  if( ndelvars > 0 )
3766  {
3767  /* perform the variable deletions from the problem */
3768  SCIP_CALL( SCIPprobPerformVarDeletions(transprob, blkmem, set, stat, eventqueue, cliquetable, lp, branchcand) );
3769  }
3770 
3771  return SCIP_OKAY;
3772 }
3773 
3774 /** converts the focus node into a dead-end node */
3775 static
3777  BMS_BLKMEM* blkmem, /**< block memory buffers */
3778  SCIP_SET* set, /**< global SCIP settings */
3779  SCIP_STAT* stat, /**< dynamic problem statistics */
3780  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3781  SCIP_PROB* transprob, /**< transformed problem after presolve */
3782  SCIP_PROB* origprob, /**< original problem */
3783  SCIP_TREE* tree, /**< branch and bound tree */
3784  SCIP_REOPT* reopt, /**< reoptimization data structure */
3785  SCIP_LP* lp, /**< current LP data */
3786  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3787  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3788  )
3789 {
3790  assert(blkmem != NULL);
3791  assert(tree != NULL);
3792  assert(!SCIPtreeProbing(tree));
3793  assert(tree->focusnode != NULL);
3795  assert(tree->nchildren == 0);
3796 
3797  SCIPsetDebugMsg(set, "focusnode #%" SCIP_LONGINT_FORMAT " to dead-end at depth %d\n",
3799 
3800  /* remove variables from the problem that are marked as deletable and were created at this node */
3801  SCIP_CALL( focusnodeCleanupVars(blkmem, set, stat, eventqueue, transprob, origprob, tree, reopt, lp, branchcand, cliquetable, TRUE) );
3802 
3803  tree->focusnode->nodetype = SCIP_NODETYPE_DEADEND; /*lint !e641*/
3804 
3805  /* release LPI state */
3806  if( tree->focuslpstatefork != NULL )
3807  {
3808  SCIP_CALL( SCIPnodeReleaseLPIState(tree->focuslpstatefork, blkmem, lp) );
3809  }
3810 
3811  return SCIP_OKAY;
3812 }
3813 
3814 /** converts the focus node into a leaf node (if it was postponed) */
3815 static
3817  BMS_BLKMEM* blkmem, /**< block memory buffers */
3818  SCIP_SET* set, /**< global SCIP settings */
3819  SCIP_STAT* stat, /**< dynamic problem statistics */
3820  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3821  SCIP_TREE* tree, /**< branch and bound tree */
3822  SCIP_REOPT* reopt, /**< reoptimization data structure */
3823  SCIP_LP* lp, /**< current LP data */
3824  SCIP_NODE* lpstatefork, /**< LP state defining fork of the node */
3825  SCIP_Real cutoffbound /**< cutoff bound: all nodes with lowerbound >= cutoffbound are cut off */
3826 
3827  )
3828 {
3829  assert(tree != NULL);
3830  assert(!SCIPtreeProbing(tree));
3831  assert(tree->focusnode != NULL);
3832  assert(tree->focusnode->active);
3834 
3835  SCIPsetDebugMsg(set, "focusnode #%" SCIP_LONGINT_FORMAT " to leaf at depth %d\n",
3837 
3838  SCIP_CALL( nodeToLeaf(&tree->focusnode, blkmem, set, stat, eventqueue, tree, reopt, lp, lpstatefork, cutoffbound));
3839 
3840  return SCIP_OKAY;
3841 }
3842 
3843 /** converts the focus node into a junction node */
3844 static
3846  BMS_BLKMEM* blkmem, /**< block memory buffers */
3847  SCIP_SET* set, /**< global SCIP settings */
3848  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3849  SCIP_TREE* tree, /**< branch and bound tree */
3850  SCIP_LP* lp /**< current LP data */
3851  )
3852 {
3853  assert(tree != NULL);
3854  assert(!SCIPtreeProbing(tree));
3855  assert(tree->focusnode != NULL);
3856  assert(tree->focusnode->active); /* otherwise, no children could be created at the focus node */
3858  assert(SCIPlpGetNNewcols(lp) == 0);
3859 
3860  SCIPsetDebugMsg(set, "focusnode #%" SCIP_LONGINT_FORMAT " to junction at depth %d\n",
3862 
3863  /* convert node into junction */
3864  tree->focusnode->nodetype = SCIP_NODETYPE_JUNCTION; /*lint !e641*/
3865 
3866  SCIP_CALL( junctionInit(&tree->focusnode->data.junction, tree) );
3867 
3868  /* release LPI state */
3869  if( tree->focuslpstatefork != NULL )
3870  {
3871  SCIP_CALL( SCIPnodeReleaseLPIState(tree->focuslpstatefork, blkmem, lp) );
3872  }
3873 
3874  /* make the domain change data static to save memory */
3875  SCIP_CALL( SCIPdomchgMakeStatic(&tree->focusnode->domchg, blkmem, set, eventqueue, lp) );
3876 
3877  return SCIP_OKAY;
3878 }
3879 
3880 /** converts the focus node into a pseudofork node */
3881 static
3883  BMS_BLKMEM* blkmem, /**< block memory buffers */
3884  SCIP_SET* set, /**< global SCIP settings */
3885  SCIP_STAT* stat, /**< dynamic problem statistics */
3886  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3887  SCIP_PROB* transprob, /**< transformed problem after presolve */
3888  SCIP_PROB* origprob, /**< original problem */
3889  SCIP_TREE* tree, /**< branch and bound tree */
3890  SCIP_REOPT* reopt, /**< reoptimization data structure */
3891  SCIP_LP* lp, /**< current LP data */
3892  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3893  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3894  )
3895 {
3896  SCIP_PSEUDOFORK* pseudofork;
3897 
3898  assert(blkmem != NULL);
3899  assert(tree != NULL);
3900  assert(!SCIPtreeProbing(tree));
3901  assert(tree->focusnode != NULL);
3902  assert(tree->focusnode->active); /* otherwise, no children could be created at the focus node */
3904  assert(tree->nchildren > 0);
3905  assert(lp != NULL);
3906 
3907  SCIPsetDebugMsg(set, "focusnode #%" SCIP_LONGINT_FORMAT " to pseudofork at depth %d\n",
3909 
3910  /* remove variables from the problem that are marked as deletable and were created at this node */
3911  SCIP_CALL( focusnodeCleanupVars(blkmem, set, stat, eventqueue, transprob, origprob, tree, reopt, lp, branchcand, cliquetable, FALSE) );
3912 
3913  /* create pseudofork data */
3914  SCIP_CALL( pseudoforkCreate(&pseudofork, blkmem, tree, lp) );
3915 
3916  tree->focusnode->nodetype = SCIP_NODETYPE_PSEUDOFORK; /*lint !e641*/
3917  tree->focusnode->data.pseudofork = pseudofork;
3918 
3919  /* release LPI state */
3920  if( tree->focuslpstatefork != NULL )
3921  {
3922  SCIP_CALL( SCIPnodeReleaseLPIState(tree->focuslpstatefork, blkmem, lp) );
3923  }
3924 
3925  /* make the domain change data static to save memory */
3926  SCIP_CALL( SCIPdomchgMakeStatic(&tree->focusnode->domchg, blkmem, set, eventqueue, lp) );
3927 
3928  return SCIP_OKAY;
3929 }
3930 
3931 /** converts the focus node into a fork node */
3932 static
3934  BMS_BLKMEM* blkmem, /**< block memory buffers */
3935  SCIP_SET* set, /**< global SCIP settings */
3936  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
3937  SCIP_STAT* stat, /**< dynamic problem statistics */
3938  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3939  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
3940  SCIP_PROB* transprob, /**< transformed problem after presolve */
3941  SCIP_PROB* origprob, /**< original problem */
3942  SCIP_TREE* tree, /**< branch and bound tree */
3943  SCIP_REOPT* reopt, /**< reoptimization data structure */
3944  SCIP_LP* lp, /**< current LP data */
3945  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3946  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3947  )
3948 {
3949  SCIP_FORK* fork;
3950  SCIP_Bool lperror;
3951 
3952  assert(blkmem != NULL);
3953  assert(tree != NULL);
3954  assert(!SCIPtreeProbing(tree));
3955  assert(tree->focusnode != NULL);
3956  assert(tree->focusnode->active); /* otherwise, no children could be created at the focus node */
3958  assert(tree->nchildren > 0);
3959  assert(lp != NULL);
3960  assert(lp->flushed);
3961  assert(lp->solved || lp->resolvelperror);
3962 
3963  SCIPsetDebugMsg(set, "focusnode #%" SCIP_LONGINT_FORMAT " to fork at depth %d\n",
3965 
3966  /* usually, the LP should be solved to optimality; otherwise, numerical troubles occured,
3967  * and we have to forget about the LP and transform the node into a junction (see below)
3968  */
3969  lperror = FALSE;
3971  {
3972  /* clean up newly created part of LP to keep only necessary columns and rows */
3973  SCIP_CALL( SCIPlpCleanupNew(lp, blkmem, set, stat, eventqueue, eventfilter, (tree->focusnode->depth == 0)) );
3974 
3975  /* resolve LP after cleaning up */
3976  if( !lp->solved || !lp->flushed )
3977  {
3978  SCIPsetDebugMsg(set, "resolving LP after cleanup\n");
3979  SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, FALSE, TRUE, &lperror) );
3980  }
3981  }
3982  assert(lp->flushed);
3983  assert(lp->solved || lperror || lp->resolvelperror);
3984 
3985  /* There are two reasons, that the (reduced) LP is not solved to optimality:
3986  * - The primal heuristics (called after the current node's LP was solved) found a new
3987  * solution, that is better than the current node's lower bound.
3988  * (But in this case, all children should be cut off and the node should be converted
3989  * into a dead-end instead of a fork.)
3990  * - Something numerically weird happened after cleaning up or after resolving a diving or probing LP.
3991  * The only thing we can do, is to completely forget about the LP and treat the node as
3992  * if it was only a pseudo-solution node. Therefore we have to remove all additional
3993  * columns and rows from the LP and convert the node into a junction.
3994  * However, the node's lower bound is kept, thus automatically throwing away nodes that
3995  * were cut off due to a primal solution.
3996  */
3997  if( lperror || lp->resolvelperror || SCIPlpGetSolstat(lp) != SCIP_LPSOLSTAT_OPTIMAL )
3998  {
3999  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
4000  "(node %" SCIP_LONGINT_FORMAT ") numerical troubles: LP %" SCIP_LONGINT_FORMAT " not optimal -- convert node into junction instead of fork\n",
4001  stat->nnodes, stat->nlps);
4002 
4003  /* remove all additions to the LP at this node */
4005  SCIP_CALL( SCIPlpShrinkRows(lp, blkmem, set, eventqueue, eventfilter, SCIPlpGetNRows(lp) - SCIPlpGetNNewrows(lp)) );
4006 
4007  /* convert node into a junction */
4008  SCIP_CALL( focusnodeToJunction(blkmem, set, eventqueue, tree, lp) );
4009 
4010  return SCIP_OKAY;
4011  }
4012  assert(lp->flushed);
4013  assert(lp->solved);
4015 
4016  /* remove variables from the problem that are marked as deletable, were created at this node and are not contained in the LP */
4017  SCIP_CALL( focusnodeCleanupVars(blkmem, set, stat, eventqueue, transprob, origprob, tree, reopt, lp, branchcand, cliquetable, FALSE) );
4018 
4019  assert(lp->flushed);
4020  assert(lp->solved);
4021 
4022  /* create fork data */
4023  SCIP_CALL( forkCreate(&fork, blkmem, set, transprob, tree, lp) );
4024 
4025  tree->focusnode->nodetype = SCIP_NODETYPE_FORK; /*lint !e641*/
4026  tree->focusnode->data.fork = fork;
4027 
4028  /* capture the LPI state of the root node to ensure that the LPI state of the root stays for the whole solving
4029  * process
4030  */
4031  if( tree->focusnode == tree->root )
4032  forkCaptureLPIState(fork, 1);
4033 
4034  /* release LPI state */
4035  if( tree->focuslpstatefork != NULL )
4036  {
4037  SCIP_CALL( SCIPnodeReleaseLPIState(tree->focuslpstatefork, blkmem, lp) );
4038  }
4039 
4040  /* make the domain change data static to save memory */
4041  SCIP_CALL( SCIPdomchgMakeStatic(&tree->focusnode->domchg, blkmem, set, eventqueue, lp) );
4042 
4043  return SCIP_OKAY;
4044 }
4045 
4046 #ifdef WITHSUBROOTS /** @todo test whether subroots should be created */
4047 /** converts the focus node into a subroot node */
4048 static
4049 SCIP_RETCODE focusnodeToSubroot(
4050  BMS_BLKMEM* blkmem, /**< block memory buffers */
4051  SCIP_SET* set, /**< global SCIP settings */
4052  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
4053  SCIP_STAT* stat, /**< dynamic problem statistics */
4054  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4055  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
4056  SCIP_PROB* transprob, /**< transformed problem after presolve */
4057  SCIP_PROB* origprob, /**< original problem */
4058  SCIP_TREE* tree, /**< branch and bound tree */
4059  SCIP_LP* lp, /**< current LP data */
4060  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4061  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
4062  )
4063 {
4064  SCIP_SUBROOT* subroot;
4065  SCIP_Bool lperror;
4066 
4067  assert(blkmem != NULL);
4068  assert(tree != NULL);
4069  assert(!SCIPtreeProbing(tree));
4070  assert(tree->focusnode != NULL);
4072  assert(tree->focusnode->active); /* otherwise, no children could be created at the focus node */
4073  assert(tree->nchildren > 0);
4074  assert(lp != NULL);
4075  assert(lp->flushed);
4076  assert(lp->solved);
4077 
4078  SCIPsetDebugMsg(set, "focusnode #%" SCIP_LONGINT_FORMAT " to subroot at depth %d\n",
4080 
4081  /* usually, the LP should be solved to optimality; otherwise, numerical troubles occured,
4082  * and we have to forget about the LP and transform the node into a junction (see below)
4083  */
4084  lperror = FALSE;
4086  {
4087  /* clean up whole LP to keep only necessary columns and rows */
4088 #ifdef SCIP_DISABLED_CODE
4089  if( tree->focusnode->depth == 0 )
4090  {
4091  SCIP_CALL( SCIPlpCleanupAll(lp, blkmem, set, stat, eventqueue, eventfilter, (tree->focusnode->depth == 0)) );
4092  }
4093  else
4094 #endif
4095  {
4096  SCIP_CALL( SCIPlpRemoveAllObsoletes(lp, blkmem, set, stat, eventqueue, eventfilter) );
4097  }
4098 
4099  /* resolve LP after cleaning up */
4100  if( !lp->solved || !lp->flushed )
4101  {
4102  SCIPsetDebugMsg(set, "resolving LP after cleanup\n");
4103  SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, FALSE, TRUE, &lperror) );
4104  }
4105  }
4106  assert(lp->flushed);
4107  assert(lp->solved || lperror);
4108 
4109  /* There are two reasons, that the (reduced) LP is not solved to optimality:
4110  * - The primal heuristics (called after the current node's LP was solved) found a new
4111  * solution, that is better than the current node's lower bound.
4112  * (But in this case, all children should be cut off and the node should be converted
4113  * into a dead-end instead of a subroot.)
4114  * - Something numerically weird happened after cleaning up.
4115  * The only thing we can do, is to completely forget about the LP and treat the node as
4116  * if it was only a pseudo-solution node. Therefore we have to remove all additional
4117  * columns and rows from the LP and convert the node into a junction.
4118  * However, the node's lower bound is kept, thus automatically throwing away nodes that
4119  * were cut off due to a primal solution.
4120  */
4121  if( lperror || SCIPlpGetSolstat(lp) != SCIP_LPSOLSTAT_OPTIMAL )
4122  {
4123  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL,
4124  "(node %" SCIP_LONGINT_FORMAT ") numerical troubles: LP %" SCIP_LONGINT_FORMAT " not optimal -- convert node into junction instead of subroot\n",
4125  stat->nnodes, stat->nlps);
4126 
4127  /* remove all additions to the LP at this node */
4129  SCIP_CALL( SCIPlpShrinkRows(lp, blkmem, set, eventqueue, eventfilter, SCIPlpGetNRows(lp) - SCIPlpGetNNewrows(lp)) );
4130 
4131  /* convert node into a junction */
4132  SCIP_CALL( focusnodeToJunction(blkmem, set, eventqueue, tree, lp) );
4133 
4134  return SCIP_OKAY;
4135  }
4136  assert(lp->flushed);
4137  assert(lp->solved);
4139 
4140  /* remove variables from the problem that are marked as deletable, were created at this node and are not contained in the LP */
4141  SCIP_CALL( focusnodeCleanupVars(blkmem, set, stat, eventqueue, transprob, origprob, tree, lp, branchcand, cliquetable, FALSE) );
4142 
4143  assert(lp->flushed);
4144  assert(lp->solved);
4145 
4146  /* create subroot data */
4147  SCIP_CALL( subrootCreate(&subroot, blkmem, set, transprob, tree, lp) );
4148 
4149  tree->focusnode->nodetype = SCIP_NODETYPE_SUBROOT; /*lint !e641*/
4150  tree->focusnode->data.subroot = subroot;
4151 
4152  /* update the LP column and row counter for the converted node */
4153  SCIP_CALL( treeUpdatePathLPSize(tree, tree->focusnode->depth) );
4154 
4155  /* release LPI state */
4156  if( tree->focuslpstatefork != NULL )
4157  {
4158  SCIP_CALL( SCIPnodeReleaseLPIState(tree->focuslpstatefork, blkmem, lp) );
4159  }
4160 
4161  /* make the domain change data static to save memory */
4162  SCIP_CALL( SCIPdomchgMakeStatic(&tree->focusnode->domchg, blkmem, set, eventqueue, lp) );
4163 
4164  return SCIP_OKAY;
4165 }
4166 #endif
4167 
4168 /** puts all nodes in the array on the node queue and makes them LEAFs */
4169 static
4171  SCIP_TREE* tree, /**< branch and bound tree */
4172  SCIP_REOPT* reopt, /**< reoptimization data structure */
4173  BMS_BLKMEM* blkmem, /**< block memory buffers */
4174  SCIP_SET* set, /**< global SCIP settings */
4175  SCIP_STAT* stat, /**< dynamic problem statistics */
4176  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4177  SCIP_LP* lp, /**< current LP data */
4178  SCIP_NODE** nodes, /**< array of nodes to put on the queue */
4179  int* nnodes, /**< pointer to number of nodes in the array */
4180  SCIP_NODE* lpstatefork, /**< LP state defining fork of the nodes */
4181  SCIP_Real cutoffbound /**< cutoff bound: all nodes with lowerbound >= cutoffbound are cut off */
4182  )
4183 {
4184  int i;
4185 
4186  assert(tree != NULL);
4187  assert(set != NULL);
4188  assert(nnodes != NULL);
4189  assert(*nnodes == 0 || nodes != NULL);
4190 
4191  for( i = 0; i < *nnodes; ++i )
4192  {
4193  /* convert node to LEAF and put it into leaves queue, or delete it if it's lower bound exceeds the cutoff bound */
4194  SCIP_CALL( nodeToLeaf(&nodes[i], blkmem, set, stat, eventqueue, tree, reopt, lp, lpstatefork, cutoffbound) );
4195  assert(nodes[i] == NULL);
4196  }
4197  *nnodes = 0;
4198 
4199  return SCIP_OKAY;
4200 }
4201 
4202 /** converts children into siblings, clears children array */
4203 static
4205  SCIP_TREE* tree /**< branch and bound tree */
4206  )
4207 {
4208  SCIP_NODE** tmpnodes;
4209  SCIP_Real* tmpprios;
4210  int tmpnodessize;
4211  int i;
4212 
4213  assert(tree != NULL);
4214  assert(tree->nsiblings == 0);
4215 
4216  tmpnodes = tree->siblings;
4217  tmpprios = tree->siblingsprio;
4218  tmpnodessize = tree->siblingssize;
4219 
4220  tree->siblings = tree->children;
4221  tree->siblingsprio = tree->childrenprio;
4222  tree->nsiblings = tree->nchildren;
4223  tree->siblingssize = tree->childrensize;
4224 
4225  tree->children = tmpnodes;
4226  tree->childrenprio = tmpprios;
4227  tree->nchildren = 0;
4228  tree->childrensize = tmpnodessize;
4229 
4230  for( i = 0; i < tree->nsiblings; ++i )
4231  {
4232  assert(SCIPnodeGetType(tree->siblings[i]) == SCIP_NODETYPE_CHILD);
4233  tree->siblings[i]->nodetype = SCIP_NODETYPE_SIBLING; /*lint !e641*/
4234 
4235  /* because CHILD and SIBLING structs contain the same data in the same order, we do not have to copy it */
4236  assert(&(tree->siblings[i]->data.sibling.arraypos) == &(tree->siblings[i]->data.child.arraypos));
4237  }
4238 }
4239 
4240 /** installs a child, a sibling, or a leaf node as the new focus node */
4242  SCIP_NODE** node, /**< pointer to node to focus (or NULL to remove focus); the node
4243  * is freed, if it was cut off due to a cut off subtree */
4244  BMS_BLKMEM* blkmem, /**< block memory buffers */
4245  SCIP_SET* set, /**< global SCIP settings */
4246  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
4247  SCIP_STAT* stat, /**< problem statistics */
4248  SCIP_PROB* transprob, /**< transformed problem */
4249  SCIP_PROB* origprob, /**< original problem */
4250  SCIP_PRIMAL* primal, /**< primal data */
4251  SCIP_TREE* tree, /**< branch and bound tree */
4252  SCIP_REOPT* reopt, /**< reoptimization data structure */
4253  SCIP_LP* lp, /**< current LP data */
4254  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4255  SCIP_CONFLICT* conflict, /**< conflict analysis data */
4256  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
4257  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4258  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4259  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
4260  SCIP_Bool* cutoff, /**< pointer to store whether the given node can be cut off */
4261  SCIP_Bool postponed, /**< was the current focus node postponed? */
4262  SCIP_Bool exitsolve /**< are we in exitsolve stage, so we only need to loose the children */
4263  )
4264 { /*lint --e{715}*/
4265  SCIP_NODE* oldfocusnode;
4266  SCIP_NODE* fork;
4267  SCIP_NODE* lpfork;
4268  SCIP_NODE* lpstatefork;
4269  SCIP_NODE* subroot;
4270  SCIP_NODE* childrenlpstatefork;
4271  int oldcutoffdepth;
4272 
4273  assert(node != NULL);
4274  assert(*node == NULL
4277  || SCIPnodeGetType(*node) == SCIP_NODETYPE_LEAF);
4278  assert(*node == NULL || !(*node)->active);
4279  assert(stat != NULL);
4280  assert(tree != NULL);
4281  assert(!SCIPtreeProbing(tree));
4282  assert(lp != NULL);
4283  assert(cutoff != NULL);
4284 
4285  SCIPsetDebugMsg(set, "focusing node #%" SCIP_LONGINT_FORMAT " of type %d in depth %d\n",
4286  *node != NULL ? SCIPnodeGetNumber(*node) : -1, *node != NULL ? (int)SCIPnodeGetType(*node) : 0,
4287  *node != NULL ? SCIPnodeGetDepth(*node) : -1);
4288 
4289  /* remember old cutoff depth in order to know, whether the children and siblings can be deleted */
4290  oldcutoffdepth = tree->cutoffdepth;
4291 
4292  /* find the common fork node, the new LP defining fork, and the new focus subroot,
4293  * thereby checking, if the new node can be cut off
4294  */
4295  treeFindSwitchForks(tree, *node, &fork, &lpfork, &lpstatefork, &subroot, cutoff);
4296  SCIPsetDebugMsg(set, "focus node: focusnodedepth=%d, forkdepth=%d, lpforkdepth=%d, lpstateforkdepth=%d, subrootdepth=%d, cutoff=%u\n",
4297  *node != NULL ? (*node)->depth : -1, fork != NULL ? fork->depth : -1, /*lint !e705 */
4298  lpfork != NULL ? lpfork->depth : -1, lpstatefork != NULL ? lpstatefork->depth : -1, /*lint !e705 */
4299  subroot != NULL ? subroot->depth : -1, *cutoff); /*lint !e705 */
4300 
4301  /* free the new node, if it is located in a cut off subtree */
4302  if( *cutoff )
4303  {
4304  assert(*node != NULL);
4305  assert(tree->cutoffdepth == oldcutoffdepth);
4306  if( SCIPnodeGetType(*node) == SCIP_NODETYPE_LEAF )
4307  {
4308  SCIP_CALL( SCIPnodepqRemove(tree->leaves, set, *node) );
4309  }
4310  SCIPvisualCutoffNode(stat->visual, set, stat, *node, FALSE);
4311 
4312  if( set->reopt_enable )
4313  {
4314  assert(reopt != NULL);
4315  /* check if the node should be stored for reoptimization */
4317  tree->root == (*node), tree->focusnode == (*node), (*node)->lowerbound, tree->effectiverootdepth) );
4318  }
4319 
4320  SCIP_CALL( SCIPnodeFree(node, blkmem, set, stat, eventqueue, tree, lp) );
4321 
4322  return SCIP_OKAY;
4323  }
4324 
4325  assert(tree->cutoffdepth == INT_MAX);
4326  assert(fork == NULL || fork->active);
4327  assert(lpstatefork == NULL || lpfork != NULL);
4328  assert(subroot == NULL || lpstatefork != NULL);
4329 
4330  /* remember the depth of the common fork node for LP updates */
4331  SCIPsetDebugMsg(set, "focus node: old correctlpdepth=%d\n", tree->correctlpdepth);
4332  if( subroot == tree->focussubroot && fork != NULL && lpfork != NULL )
4333  {
4334  /* we are in the same subtree with valid LP fork: the LP is correct at most upto the common fork depth */
4335  assert(subroot == NULL || subroot->active);
4336  tree->correctlpdepth = MIN(tree->correctlpdepth, (int)fork->depth);
4337  }
4338  else
4339  {
4340  /* we are in a different subtree, or no valid LP fork exists: the LP is completely incorrect */
4341  assert(subroot == NULL || !subroot->active
4342  || (tree->focussubroot != NULL && (int)(tree->focussubroot->depth) > subroot->depth));
4343  tree->correctlpdepth = -1;
4344  }
4345 
4346  /* if the LP state fork changed, the lpcount information for the new LP state fork is unknown */
4347  if( lpstatefork != tree->focuslpstatefork )
4348  tree->focuslpstateforklpcount = -1;
4349 
4350  /* in exitsolve we only need to take care of open children
4351  *
4352  * @note because we might do a 'newstart' and converted cuts to constraints might have rendered the LP in the current
4353  * focusnode unsolved the latter code would have resolved the LP unnecessarily
4354  */
4355  if( exitsolve && tree->nchildren > 0 )
4356  {
4357  SCIPsetDebugMsg(set, " -> deleting the %d children (in exitsolve) of the old focus node\n", tree->nchildren);
4358  SCIP_CALL( treeNodesToQueue(tree, reopt, blkmem, set, stat, eventqueue, lp, tree->children, &tree->nchildren, NULL, -SCIPsetInfinity(set)) );
4359  assert(tree->nchildren == 0);
4360  }
4361 
4362  /* if the old focus node was cut off, we can delete its children;
4363  * if the old focus node's parent was cut off, we can also delete the focus node's siblings
4364  */
4365  /* coverity[var_compare_op] */
4366  if( tree->focusnode != NULL && oldcutoffdepth <= (int)tree->focusnode->depth )
4367  {
4368  SCIPsetDebugMsg(set, "path to old focus node of depth %u was cut off at depth %d\n", tree->focusnode->depth, oldcutoffdepth);
4369 
4370  /* delete the focus node's children by converting them to leaves with a cutoffbound of -SCIPsetInfinity(set);
4371  * we cannot delete them directly, because in SCIPnodeFree(), the children array is changed, which is the
4372  * same array we would have to iterate over here;
4373  * the children don't have an LP fork, because the old focus node is not yet converted into a fork or subroot
4374  */
4375  SCIPsetDebugMsg(set, " -> deleting the %d children of the old focus node\n", tree->nchildren);
4376  SCIP_CALL( treeNodesToQueue(tree, reopt, blkmem, set, stat, eventqueue, lp, tree->children, &tree->nchildren, NULL, -SCIPsetInfinity(set)) );
4377  assert(tree->nchildren == 0);
4378 
4379  if( oldcutoffdepth < (int)tree->focusnode->depth )
4380  {
4381  /* delete the focus node's siblings by converting them to leaves with a cutoffbound of -SCIPsetInfinity(set);
4382  * we cannot delete them directly, because in SCIPnodeFree(), the siblings array is changed, which is the
4383  * same array we would have to iterate over here;
4384  * the siblings have the same LP state fork as the old focus node
4385  */
4386  SCIPsetDebugMsg(set, " -> deleting the %d siblings of the old focus node\n", tree->nsiblings);
4387  SCIP_CALL( treeNodesToQueue(tree, reopt, blkmem, set, stat, eventqueue, lp, tree->siblings, &tree->nsiblings, tree->focuslpstatefork,
4388  -SCIPsetInfinity(set)) );
4389  assert(tree->nsiblings == 0);
4390  }
4391  }
4392 
4393  /* convert the old focus node into a fork or subroot node, if it has children;
4394  * otherwise, convert it into a dead-end, which will be freed later in treeSwitchPath();
4395  * if the node was postponed, make it a leaf.
4396  */
4397  childrenlpstatefork = tree->focuslpstatefork;
4398 
4399  assert(!postponed || *node == NULL);
4400  assert(!postponed || tree->focusnode != NULL);
4401 
4402  if( postponed )
4403  {
4404  assert(tree->nchildren == 0);
4405  assert(*node == NULL);
4406 
4407  /* if the node is infeasible, convert it into a deadend; otherwise, put it into the LEAF queue */
4408  if( SCIPsetIsGE(set, tree->focusnode->lowerbound, primal->cutoffbound) )
4409  {
4410  /* in case the LP was not constructed (due to the parameter settings for example) we have the finally remember the
4411  * old size of the LP (if it was constructed in an earlier node) before we change the current node into a deadend
4412  */
4413  if( !tree->focuslpconstructed )
4414  SCIPlpMarkSize(lp);
4415 
4416  /* convert old focus node into deadend */
4417  SCIP_CALL( focusnodeToDeadend(blkmem, set, stat, eventqueue, transprob, origprob, tree, reopt, lp, branchcand,
4418  cliquetable) );
4419  }
4420  else
4421  {
4422  SCIP_CALL( focusnodeToLeaf(blkmem, set, stat, eventqueue, tree, reopt, lp, tree->focuslpstatefork,
4423  SCIPsetInfinity(set)) );
4424  }
4425  }
4426  else if( tree->nchildren > 0 )
4427  {
4428  SCIP_Bool selectedchild;
4429 
4430  assert(tree->focusnode != NULL);
4432  assert(oldcutoffdepth == INT_MAX);
4433 
4434  /* check whether the next focus node is a child of the old focus node */
4435  selectedchild = (*node != NULL && SCIPnodeGetType(*node) == SCIP_NODETYPE_CHILD);
4436 
4437  if( tree->focusnodehaslp && lp->isrelax )
4438  {
4439  assert(tree->focuslpconstructed);
4440 
4441 #ifdef WITHSUBROOTS /** @todo test whether subroots should be created, decide: old focus node becomes fork or subroot */
4442  if( tree->focusnode->depth > 0 && tree->focusnode->depth % 25 == 0 )
4443  {
4444  /* convert old focus node into a subroot node */
4445  SCIP_CALL( focusnodeToSubroot(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, transprob, origprob, tree, lp, branchcand) );
4446  if( *node != NULL && SCIPnodeGetType(*node) == SCIP_NODETYPE_CHILD
4448  subroot = tree->focusnode;
4449  }
4450  else
4451 #endif
4452  {
4453  /* convert old focus node into a fork node */
4454  SCIP_CALL( focusnodeToFork(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, transprob, origprob, tree,
4455  reopt, lp, branchcand, cliquetable) );
4456  }
4457 
4458  /* check, if the conversion into a subroot or fork was successful */
4461  {
4462  childrenlpstatefork = tree->focusnode;
4463 
4464  /* if a child of the old focus node was selected as new focus node, the old node becomes the new focus
4465  * LP fork and LP state fork
4466  */
4467  if( selectedchild )
4468  {
4469  lpfork = tree->focusnode;
4470  tree->correctlpdepth = tree->focusnode->depth;
4471  lpstatefork = tree->focusnode;
4472  tree->focuslpstateforklpcount = stat->lpcount;
4473  }
4474  }
4475 
4476  /* update the path's LP size */
4477  tree->pathnlpcols[tree->focusnode->depth] = SCIPlpGetNCols(lp);
4478  tree->pathnlprows[tree->focusnode->depth] = SCIPlpGetNRows(lp);
4479  }
4480  else if( tree->focuslpconstructed && (SCIPlpGetNNewcols(lp) > 0 || SCIPlpGetNNewrows(lp) > 0) )
4481  {
4482  /* convert old focus node into pseudofork */
4483  SCIP_CALL( focusnodeToPseudofork(blkmem, set, stat, eventqueue, transprob, origprob, tree, reopt, lp,
4484  branchcand, cliquetable) );
4486 
4487  /* update the path's LP size */
4488  tree->pathnlpcols[tree->focusnode->depth] = SCIPlpGetNCols(lp);
4489  tree->pathnlprows[tree->focusnode->depth] = SCIPlpGetNRows(lp);
4490 
4491  /* if a child of the old focus node was selected as new focus node, the old node becomes the new focus LP fork */
4492  if( selectedchild )
4493  {
4494  lpfork = tree->focusnode;
4495  tree->correctlpdepth = tree->focusnode->depth;
4496  }
4497  }
4498  else
4499  {
4500  /* in case the LP was not constructed (due to the parameter settings for example) we have the finally remember the
4501  * old size of the LP (if it was constructed in an earlier node) before we change the current node into a junction
4502  */
4503  SCIPlpMarkSize(lp);
4504 
4505  /* convert old focus node into junction */
4506  SCIP_CALL( focusnodeToJunction(blkmem, set, eventqueue, tree, lp) );
4507  }
4508  }
4509  else if( tree->focusnode != NULL )
4510  {
4511  /* in case the LP was not constructed (due to the parameter settings for example) we have the finally remember the
4512  * old size of the LP (if it was constructed in an earlier node) before we change the current node into a deadend
4513  */
4514  if( !tree->focuslpconstructed )
4515  SCIPlpMarkSize(lp);
4516 
4517  /* convert old focus node into deadend */
4518  SCIP_CALL( focusnodeToDeadend(blkmem, set, stat, eventqueue, transprob, origprob, tree, reopt, lp, branchcand, cliquetable) );
4519  }
4520  assert(subroot == NULL || SCIPnodeGetType(subroot) == SCIP_NODETYPE_SUBROOT);
4521  assert(lpstatefork == NULL
4522  || SCIPnodeGetType(lpstatefork) == SCIP_NODETYPE_SUBROOT
4523  || SCIPnodeGetType(lpstatefork) == SCIP_NODETYPE_FORK);
4524  assert(childrenlpstatefork == NULL
4525  || SCIPnodeGetType(childrenlpstatefork) == SCIP_NODETYPE_SUBROOT
4526  || SCIPnodeGetType(childrenlpstatefork) == SCIP_NODETYPE_FORK);
4527  assert(lpfork == NULL
4529  || SCIPnodeGetType(lpfork) == SCIP_NODETYPE_FORK
4531  SCIPsetDebugMsg(set, "focus node: new correctlpdepth=%d\n", tree->correctlpdepth);
4532 
4533  /* set up the new lists of siblings and children */
4534  oldfocusnode = tree->focusnode;
4535  if( *node == NULL )
4536  {
4537  /* move siblings to the queue, make them LEAFs */
4538  SCIP_CALL( treeNodesToQueue(tree, reopt, blkmem, set, stat, eventqueue, lp, tree->siblings, &tree->nsiblings, tree->focuslpstatefork,
4539  primal->cutoffbound) );
4540 
4541  /* move children to the queue, make them LEAFs */
4542  SCIP_CALL( treeNodesToQueue(tree, reopt, blkmem, set, stat, eventqueue, lp, tree->children, &tree->nchildren, childrenlpstatefork,
4543  primal->cutoffbound) );
4544  }
4545  else
4546  {
4547  SCIP_NODE* bestleaf;
4548 
4549  switch( SCIPnodeGetType(*node) )
4550  {
4551  case SCIP_NODETYPE_SIBLING:
4552  /* reset plunging depth, if the selected node is better than all leaves */
4553  bestleaf = SCIPtreeGetBestLeaf(tree);
4554  if( bestleaf == NULL || SCIPnodepqCompare(tree->leaves, set, *node, bestleaf) <= 0 )
4555  stat->plungedepth = 0;
4556 
4557  /* move children to the queue, make them LEAFs */
4558  SCIP_CALL( treeNodesToQueue(tree, reopt, blkmem, set, stat, eventqueue, lp, tree->children, &tree->nchildren, childrenlpstatefork,
4559  primal->cutoffbound) );
4560 
4561  /* remove selected sibling from the siblings array */
4562  treeRemoveSibling(tree, *node);
4563 
4564  SCIPsetDebugMsg(set, "selected sibling node, lowerbound=%g, plungedepth=%d\n", (*node)->lowerbound, stat->plungedepth);
4565  break;
4566 
4567  case SCIP_NODETYPE_CHILD:
4568  /* reset plunging depth, if the selected node is better than all leaves; otherwise, increase plunging depth */
4569  bestleaf = SCIPtreeGetBestLeaf(tree);
4570  if( bestleaf == NULL || SCIPnodepqCompare(tree->leaves, set, *node, bestleaf) <= 0 )
4571  stat->plungedepth = 0;
4572  else
4573  stat->plungedepth++;
4574 
4575  /* move siblings to the queue, make them LEAFs */
4576  SCIP_CALL( treeNodesToQueue(tree, reopt, blkmem, set, stat, eventqueue, lp, tree->siblings, &tree->nsiblings, tree->focuslpstatefork,
4577  primal->cutoffbound) );
4578 
4579  /* remove selected child from the children array */
4580  treeRemoveChild(tree, *node);
4581 
4582  /* move remaining children to the siblings array, make them SIBLINGs */
4583  treeChildrenToSiblings(tree);
4584 
4585  SCIPsetDebugMsg(set, "selected child node, lowerbound=%g, plungedepth=%d\n", (*node)->lowerbound, stat->plungedepth);
4586  break;
4587 
4588  case SCIP_NODETYPE_LEAF:
4589  /* move siblings to the queue, make them LEAFs */
4590  SCIP_CALL( treeNodesToQueue(tree, reopt, blkmem, set, stat, eventqueue, lp, tree->siblings, &tree->nsiblings, tree->focuslpstatefork,
4591  primal->cutoffbound) );
4592 
4593  /* encounter an early backtrack if there is a child which does not exceed given reference bound */
4594  if( !SCIPsetIsInfinity(set, stat->referencebound) )
4595  {
4596  int c;
4597 
4598  /* loop over children and stop if we find a child with a lower bound below given reference bound */
4599  for( c = 0; c < tree->nchildren; ++c )
4600  {
4601  if( SCIPsetIsLT(set, SCIPnodeGetLowerbound(tree->children[c]), stat->referencebound) )
4602  {
4603  ++stat->nearlybacktracks;
4604  break;
4605  }
4606  }
4607  }
4608  /* move children to the queue, make them LEAFs */
4609  SCIP_CALL( treeNodesToQueue(tree, reopt, blkmem, set, stat, eventqueue, lp, tree->children, &tree->nchildren, childrenlpstatefork,
4610  primal->cutoffbound) );
4611 
4612  /* remove node from the queue */
4613  SCIP_CALL( SCIPnodepqRemove(tree->leaves, set, *node) );
4614 
4615  stat->plungedepth = 0;
4616  if( SCIPnodeGetDepth(*node) > 0 )
4617  stat->nbacktracks++;
4618  SCIPsetDebugMsg(set, "selected leaf node, lowerbound=%g, plungedepth=%d\n", (*node)->lowerbound, stat->plungedepth);
4619  break;
4620 
4621  default:
4622  SCIPerrorMessage("selected node is neither sibling, child, nor leaf (nodetype=%d)\n", SCIPnodeGetType(*node));
4623  return SCIP_INVALIDDATA;
4624  } /*lint !e788*/
4625 
4626  /* convert node into the focus node */
4627  (*node)->nodetype = SCIP_NODETYPE_FOCUSNODE; /*lint !e641*/
4628  }
4629  assert(tree->nchildren == 0);
4630 
4631  /* set new focus node, LP fork, LP state fork, and subroot */
4632  assert(subroot == NULL || (lpstatefork != NULL && subroot->depth <= lpstatefork->depth));
4633  assert(lpstatefork == NULL || (lpfork != NULL && lpstatefork->depth <= lpfork->depth));
4634  assert(lpfork == NULL || (*node != NULL && lpfork->depth < (*node)->depth));
4635  tree->focusnode = *node;
4636  tree->focuslpfork = lpfork;
4637  tree->focuslpstatefork = lpstatefork;
4638  tree->focussubroot = subroot;
4639  tree->focuslpconstructed = FALSE;
4640  lp->resolvelperror = FALSE;
4641 
4642  /* track the path from the old focus node to the new node, and perform domain and constraint set changes */
4643  SCIP_CALL( treeSwitchPath(tree, reopt, blkmem, set, stat, transprob, origprob, primal, lp, branchcand, conflict,
4644  eventfilter, eventqueue, cliquetable, fork, *node, cutoff) );
4645  assert(tree->pathlen >= 0);
4646  assert(*node != NULL || tree->pathlen == 0);
4647  assert(*node == NULL || tree->pathlen-1 <= (int)(*node)->depth);
4648 
4649  /* if the old focus node is a dead end (has no children), delete it */
4650  if( oldfocusnode != NULL && SCIPnodeGetType(oldfocusnode) == SCIP_NODETYPE_DEADEND )
4651  {
4652  int appliedeffectiverootdepth;
4653 
4654  appliedeffectiverootdepth = tree->appliedeffectiverootdepth;
4655  assert(appliedeffectiverootdepth <= tree->effectiverootdepth);
4656 
4657  SCIP_CALL( SCIPnodeFree(&oldfocusnode, blkmem, set, stat, eventqueue, tree, lp) );
4658  assert(tree->effectiverootdepth < tree->pathlen || *node == NULL || *cutoff);
4659 
4660  if( tree->effectiverootdepth > appliedeffectiverootdepth && *node != NULL && !(*cutoff) )
4661  {
4662  int d;
4663 
4664  /* promote the constraint set and bound changes up to the new effective root to be global changes */
4665  SCIPsetDebugMsg(set, "effective root is now at depth %d: applying constraint set and bound changes to global problem\n",
4666  tree->effectiverootdepth);
4667 
4668  for( d = appliedeffectiverootdepth + 1; d <= tree->effectiverootdepth; ++d )
4669  {
4670  SCIP_Bool nodecutoff;
4671 
4672  SCIPsetDebugMsg(set, " -> applying constraint set changes of depth %d\n", d);
4673  SCIP_CALL( SCIPconssetchgMakeGlobal(&tree->path[d]->conssetchg, blkmem, set, stat, transprob, reopt) );
4674  SCIPsetDebugMsg(set, " -> applying bound changes of depth %d\n", d);
4675  SCIP_CALL( SCIPdomchgApplyGlobal(tree->path[d]->domchg, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable,
4676  &nodecutoff) );
4677 
4678  if( nodecutoff )
4679  {
4680  SCIP_CALL( SCIPnodeCutoff(tree->path[d], set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
4681  *cutoff = TRUE;
4682  }
4683  }
4684 
4686  }
4687  }
4688  assert(*cutoff || SCIPtreeIsPathComplete(tree));
4689 
4690  return SCIP_OKAY;
4691 }
4692 
4693 
4694 
4695 
4696 /*
4697  * Tree methods
4698  */
4699 
4700 /** creates an initialized tree data structure */
4702  SCIP_TREE** tree, /**< pointer to tree data structure */
4703  BMS_BLKMEM* blkmem, /**< block memory buffers */
4704  SCIP_SET* set, /**< global SCIP settings */
4705  SCIP_NODESEL* nodesel /**< node selector to use for sorting leaves in the priority queue */
4706  )
4707 {
4708  int p;
4709 
4710  assert(tree != NULL);
4711  assert(blkmem != NULL);
4712 
4713  SCIP_ALLOC( BMSallocMemory(tree) );
4714 
4715  (*tree)->root = NULL;
4716 
4717  SCIP_CALL( SCIPnodepqCreate(&(*tree)->leaves, set, nodesel) );
4718 
4719  /* allocate one slot for the prioritized and the unprioritized bound change */
4720  for( p = 0; p <= 1; ++p )
4721  {
4722  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*tree)->divebdchgdirs[p], 1) ); /*lint !e866*/
4723  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*tree)->divebdchgvars[p], 1) ); /*lint !e866*/
4724  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*tree)->divebdchgvals[p], 1) ); /*lint !e866*/
4725  (*tree)->ndivebdchanges[p] = 0;
4726  (*tree)->divebdchgsize[p] = 1;
4727  }
4728 
4729  (*tree)->path = NULL;
4730  (*tree)->focusnode = NULL;
4731  (*tree)->focuslpfork = NULL;
4732  (*tree)->focuslpstatefork = NULL;
4733  (*tree)->focussubroot = NULL;
4734  (*tree)->children = NULL;
4735  (*tree)->siblings = NULL;
4736  (*tree)->probingroot = NULL;
4737  (*tree)->childrenprio = NULL;
4738  (*tree)->siblingsprio = NULL;
4739  (*tree)->pathnlpcols = NULL;
4740  (*tree)->pathnlprows = NULL;
4741  (*tree)->probinglpistate = NULL;
4742  (*tree)->probinglpinorms = NULL;
4743  (*tree)->pendingbdchgs = NULL;
4744  (*tree)->probdiverelaxsol = NULL;
4745  (*tree)->pendingbdchgssize = 0;
4746  (*tree)->npendingbdchgs = 0;
4747  (*tree)->focuslpstateforklpcount = -1;
4748  (*tree)->childrensize = 0;
4749  (*tree)->nchildren = 0;
4750  (*tree)->siblingssize = 0;
4751  (*tree)->nsiblings = 0;
4752  (*tree)->pathlen = 0;
4753  (*tree)->pathsize = 0;
4754  (*tree)->effectiverootdepth = 0;
4755  (*tree)->appliedeffectiverootdepth = 0;
4756  (*tree)->correctlpdepth = -1;
4757  (*tree)->cutoffdepth = INT_MAX;
4758  (*tree)->repropdepth = INT_MAX;
4759  (*tree)->repropsubtreecount = 0;
4760  (*tree)->focusnodehaslp = FALSE;
4761  (*tree)->probingnodehaslp = FALSE;
4762  (*tree)->focuslpconstructed = FALSE;
4763  (*tree)->cutoffdelayed = FALSE;
4764  (*tree)->probinglpwasflushed = FALSE;
4765  (*tree)->probinglpwassolved = FALSE;
4766  (*tree)->probingloadlpistate = FALSE;
4767  (*tree)->probinglpwasrelax = FALSE;
4768  (*tree)->probingsolvedlp = FALSE;
4769  (*tree)->forcinglpmessage = FALSE;
4770  (*tree)->sbprobing = FALSE;
4771  (*tree)->probinglpwasprimfeas = TRUE;
4772  (*tree)->probinglpwasdualfeas = TRUE;
4773  (*tree)->probdiverelaxstored = FALSE;
4774  (*tree)->probdiverelaxincludeslp = FALSE;
4775 
4776  return SCIP_OKAY;
4777 }
4778 
4779 /** frees tree data structure */
4781  SCIP_TREE** tree, /**< pointer to tree data structure */
4782  BMS_BLKMEM* blkmem, /**< block memory buffers */
4783  SCIP_SET* set, /**< global SCIP settings */
4784  SCIP_STAT* stat, /**< problem statistics */
4785  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4786  SCIP_LP* lp /**< current LP data */
4787  )
4788 {
4789  int p;
4790 
4791  assert(tree != NULL);
4792  assert(*tree != NULL);
4793  assert((*tree)->nchildren == 0);
4794  assert((*tree)->nsiblings == 0);
4795  assert((*tree)->focusnode == NULL);
4796  assert(!SCIPtreeProbing(*tree));
4797 
4798  SCIPsetDebugMsg(set, "free tree\n");
4799 
4800  /* free node queue */
4801  SCIP_CALL( SCIPnodepqFree(&(*tree)->leaves, blkmem, set, stat, eventqueue, *tree, lp) );
4802 
4803  /* free diving bound change storage */
4804  for( p = 0; p <= 1; ++p )
4805  {
4806  BMSfreeBlockMemoryArray(blkmem, &(*tree)->divebdchgdirs[p], (*tree)->divebdchgsize[p]); /*lint !e866*/
4807  BMSfreeBlockMemoryArray(blkmem, &(*tree)->divebdchgvals[p], (*tree)->divebdchgsize[p]); /*lint !e866*/
4808  BMSfreeBlockMemoryArray(blkmem, &(*tree)->divebdchgvars[p], (*tree)->divebdchgsize[p]); /*lint !e866*/
4809  }
4810 
4811  /* free pointer arrays */
4812  BMSfreeMemoryArrayNull(&(*tree)->path);
4813  BMSfreeMemoryArrayNull(&(*tree)->children);
4814  BMSfreeMemoryArrayNull(&(*tree)->siblings);
4815  BMSfreeMemoryArrayNull(&(*tree)->childrenprio);
4816  BMSfreeMemoryArrayNull(&(*tree)->siblingsprio);
4817  BMSfreeMemoryArrayNull(&(*tree)->pathnlpcols);
4818  BMSfreeMemoryArrayNull(&(*tree)->pathnlprows);
4819  BMSfreeMemoryArrayNull(&(*tree)->probdiverelaxsol);
4820  BMSfreeMemoryArrayNull(&(*tree)->pendingbdchgs);
4821 
4822  BMSfreeMemory(tree);
4823 
4824  return SCIP_OKAY;
4825 }
4826 
4827 /** clears and resets tree data structure and deletes all nodes */
4829  SCIP_TREE* tree, /**< tree data structure */
4830  BMS_BLKMEM* blkmem, /**< block memory buffers */
4831  SCIP_SET* set, /**< global SCIP settings */
4832  SCIP_STAT* stat, /**< problem statistics */
4833  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4834  SCIP_LP* lp /**< current LP data */
4835  )
4836 {
4837  int v;
4838 
4839  assert(tree != NULL);
4840  assert(tree->nchildren == 0);
4841  assert(tree->nsiblings == 0);
4842  assert(tree->focusnode == NULL);
4843  assert(!SCIPtreeProbing(tree));
4844 
4845  SCIPsetDebugMsg(set, "clearing tree\n");
4846 
4847  /* clear node queue */
4848  SCIP_CALL( SCIPnodepqClear(tree->leaves, blkmem, set, stat, eventqueue, tree, lp) );
4849  assert(tree->root == NULL);
4850 
4851  /* we have to remove the captures of the variables within the pending bound change data structure */
4852  for( v = tree->npendingbdchgs-1; v >= 0; --v )
4853  {
4854  SCIP_VAR* var;
4855 
4856  var = tree->pendingbdchgs[v].var;
4857  assert(var != NULL);
4858 
4859  /* release the variable */
4860  SCIP_CALL( SCIPvarRelease(&var, blkmem, set, eventqueue, lp) );
4861  }
4862 
4863  /* mark working arrays to be empty and reset data */
4864  tree->focuslpstateforklpcount = -1;
4865  tree->nchildren = 0;
4866  tree->nsiblings = 0;
4867  tree->pathlen = 0;
4868  tree->effectiverootdepth = 0;
4869  tree->appliedeffectiverootdepth = 0;
4870  tree->correctlpdepth = -1;
4871  tree->cutoffdepth = INT_MAX;
4872  tree->repropdepth = INT_MAX;
4873  tree->repropsubtreecount = 0;
4874  tree->npendingbdchgs = 0;
4875  tree->focusnodehaslp = FALSE;
4876  tree->probingnodehaslp = FALSE;
4877  tree->cutoffdelayed = FALSE;
4878  tree->probinglpwasflushed = FALSE;
4879  tree->probinglpwassolved = FALSE;
4880  tree->probingloadlpistate = FALSE;
4881  tree->probinglpwasrelax = FALSE;
4882  tree->probingsolvedlp = FALSE;
4883 
4884  return SCIP_OKAY;
4885 }
4886 
4887 /** creates the root node of the tree and puts it into the leaves queue */
4889  SCIP_TREE* tree, /**< tree data structure */
4890  SCIP_REOPT* reopt, /**< reoptimization data structure */
4891  BMS_BLKMEM* blkmem, /**< block memory buffers */
4892  SCIP_SET* set, /**< global SCIP settings */
4893  SCIP_STAT* stat, /**< problem statistics */
4894  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4895  SCIP_LP* lp /**< current LP data */
4896  )
4897 {
4898  assert(tree != NULL);
4899  assert(tree->nchildren == 0);
4900  assert(tree->nsiblings == 0);
4901  assert(tree->root == NULL);
4902  assert(tree->focusnode == NULL);
4903  assert(!SCIPtreeProbing(tree));
4904 
4905  /* create root node */
4906  SCIP_CALL( SCIPnodeCreateChild(&tree->root, blkmem, set, stat, tree, 0.0, -SCIPsetInfinity(set)) );
4907  assert(tree->nchildren == 1);
4908 
4909 #ifndef NDEBUG
4910  /* check, if the sizes in the data structures match the maximal numbers defined here */
4911  tree->root->depth = SCIP_MAXTREEDEPTH + 1;
4913  assert(tree->root->depth - 1 == SCIP_MAXTREEDEPTH); /*lint !e650*/
4914  assert(tree->root->repropsubtreemark == MAXREPROPMARK);
4915  tree->root->depth++; /* this should produce an overflow and reset the value to 0 */
4916  tree->root->repropsubtreemark++; /* this should produce an overflow and reset the value to 0 */
4917  assert(tree->root->depth == 0);
4918  assert((SCIP_NODETYPE)tree->root->nodetype == SCIP_NODETYPE_CHILD);
4919  assert(!tree->root->active);
4920  assert(!tree->root->cutoff);
4921  assert(!tree->root->reprop);
4922  assert(tree->root->repropsubtreemark == 0);
4923 #endif
4924 
4925  /* move root to the queue, convert it to LEAF */
4926  SCIP_CALL( treeNodesToQueue(tree, reopt, blkmem, set, stat, eventqueue, lp, tree->children, &tree->nchildren, NULL,
4927  SCIPsetInfinity(set)) );
4928 
4929  return SCIP_OKAY;
4930 }
4931 
4932 /** creates a temporary presolving root node of the tree and installs it as focus node */
4934  SCIP_TREE* tree, /**< tree data structure */
4935  SCIP_REOPT* reopt, /**< reoptimization data structure */
4936  BMS_BLKMEM* blkmem, /**< block memory buffers */
4937  SCIP_SET* set, /**< global SCIP settings */
4938  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
4939  SCIP_STAT* stat, /**< problem statistics */
4940  SCIP_PROB* transprob, /**< transformed problem */
4941  SCIP_PROB* origprob, /**< original problem */
4942  SCIP_PRIMAL* primal, /**< primal data */
4943  SCIP_LP* lp, /**< current LP data */
4944  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4945  SCIP_CONFLICT* conflict, /**< conflict analysis data */
4946  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
4947  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4948  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4949  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
4950  )
4951 {
4952  SCIP_Bool cutoff;
4953 
4954  assert(tree !=