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