1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 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   scip_tree.c
26   	 * @ingroup OTHER_CFILES
27   	 * @brief  public methods for the branch-and-bound tree
28   	 * @author Tobias Achterberg
29   	 * @author Timo Berthold
30   	 * @author Gerald Gamrath
31   	 * @author Leona Gottwald
32   	 * @author Stefan Heinz
33   	 * @author Gregor Hendel
34   	 * @author Thorsten Koch
35   	 * @author Alexander Martin
36   	 * @author Marc Pfetsch
37   	 * @author Michael Winkler
38   	 * @author Kati Wolter
39   	 *
40   	 * @todo check all SCIP_STAGE_* switches, and include the new stages TRANSFORMED and INITSOLVE
41   	 */
42   	
43   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
44   	
45   	#include "blockmemshell/memory.h"
46   	#include "scip/debug.h"
47   	#include "scip/nodesel.h"
48   	#include "scip/pub_message.h"
49   	#include "scip/pub_tree.h"
50   	#include "scip/pub_var.h"
51   	#include "scip/scip_mem.h"
52   	#include "scip/scip_tree.h"
53   	#include "scip/scip_numerics.h"
54   	#include "scip/struct_mem.h"
55   	#include "scip/struct_scip.h"
56   	#include "scip/struct_stat.h"
57   	#include "scip/struct_tree.h"
58   	#include "scip/tree.h"
59   	
60   	/** gets focus node in the tree
61   	 *
62   	 *  if we are in probing/diving mode this method returns the node in the tree where the probing/diving mode was started.
63   	 *
64   	 *  @return the current node of the search tree
65   	 *
66   	 *  @pre This method can be called if @p scip is in one of the following stages:
67   	 *       - \ref SCIP_STAGE_INITPRESOLVE
68   	 *       - \ref SCIP_STAGE_PRESOLVING
69   	 *       - \ref SCIP_STAGE_EXITPRESOLVE
70   	 *       - \ref SCIP_STAGE_SOLVING
71   	 */
72   	SCIP_NODE* SCIPgetFocusNode(
73   	   SCIP*                 scip                /**< SCIP data structure */
74   	   )
75   	{
76   	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetFocusNode", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
77   	
78   	   return SCIPtreeGetFocusNode(scip->tree);
79   	}
80   	
81   	/** gets current node in the tree
82   	 *
83   	 *  @return the current node of the search tree
84   	 *
85   	 *  @pre This method can be called if @p scip is in one of the following stages:
86   	 *       - \ref SCIP_STAGE_INITPRESOLVE
87   	 *       - \ref SCIP_STAGE_PRESOLVING
88   	 *       - \ref SCIP_STAGE_EXITPRESOLVE
89   	 *       - \ref SCIP_STAGE_SOLVING
90   	 */
91   	SCIP_NODE* SCIPgetCurrentNode(
92   	   SCIP*                 scip                /**< SCIP data structure */
93   	   )
94   	{
95   	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetCurrentNode", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
96   	
97   	   return SCIPtreeGetCurrentNode(scip->tree);
98   	}
99   	
100  	/** gets the root node of the tree
101  	 *
102  	 *  @return the root node of the search tree
103  	 *
104  	 *  @pre This method can be called if @p scip is in one of the following stages:
105  	 *       - \ref SCIP_STAGE_INITPRESOLVE
106  	 *       - \ref SCIP_STAGE_PRESOLVING
107  	 *       - \ref SCIP_STAGE_EXITPRESOLVE
108  	 *       - \ref SCIP_STAGE_SOLVING
109  	 */
110  	SCIP_NODE* SCIPgetRootNode(
111  	   SCIP*                 scip                /**< SCIP data structure */
112  	   )
113  	{
114  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetRootNode", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
115  	
116  	   return SCIPtreeGetRootNode(scip->tree);
117  	}
118  	
119  	/** gets the effective root depth, i.e., the depth of the deepest node which is part of all paths from the root node
120  	 *  to the unprocessed nodes.
121  	 *
122  	 *  @return effective root depth
123  	 *
124  	 *  @pre This method can be called if @p scip is in one of the following stages:
125  	 *       - \ref SCIP_STAGE_SOLVING
126  	 */
127  	int SCIPgetEffectiveRootDepth(
128  	   SCIP*                 scip                /**< SCIP data structure */
129  	   )
130  	{
131  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetEffectiveRootDepth", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
132  	
133  	   return SCIPtreeGetEffectiveRootDepth(scip->tree);
134  	}
135  	
136  	/** returns whether the current node is already solved and only propagated again
137  	 *
138  	 *  @return TRUE is returned if \SCIP performance repropagation, otherwise FALSE.
139  	 *
140  	 *  @pre This method can be called if @p scip is in one of the following stages:
141  	 *       - \ref SCIP_STAGE_INITPRESOLVE
142  	 *       - \ref SCIP_STAGE_PRESOLVING
143  	 *       - \ref SCIP_STAGE_EXITPRESOLVE
144  	 *       - \ref SCIP_STAGE_SOLVING
145  	 */
146  	SCIP_Bool SCIPinRepropagation(
147  	   SCIP*                 scip                /**< SCIP data structure */
148  	   )
149  	{
150  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPinRepropagation", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
151  	
152  	   return SCIPtreeInRepropagation(scip->tree);
153  	}
154  	
155  	/** gets children of focus node along with the number of children
156  	 *
157  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
158  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
159  	 *
160  	 *  @pre This method can be called if @p scip is in one of the following stages:
161  	 *       - \ref SCIP_STAGE_SOLVING
162  	 *       - \ref SCIP_STAGE_SOLVED
163  	 */
164  	SCIP_RETCODE SCIPgetChildren(
165  	   SCIP*                 scip,               /**< SCIP data structure */
166  	   SCIP_NODE***          children,           /**< pointer to store children array, or NULL if not needed */
167  	   int*                  nchildren           /**< pointer to store number of children, or NULL if not needed */
168  	   )
169  	{
170  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPgetChildren", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
171  	
172  	   if( children != NULL )
173  	      *children = scip->tree->children;
174  	   if( nchildren != NULL )
175  	      *nchildren = scip->tree->nchildren;
176  	
177  	   return SCIP_OKAY;
178  	}
179  	
180  	/** gets number of children of focus node
181  	 *
182  	 *  @return number of children of the focus node
183  	 *
184  	 *  @pre This method can be called if @p scip is in one of the following stages:
185  	 *       - \ref SCIP_STAGE_SOLVING
186  	 *       - \ref SCIP_STAGE_SOLVED
187  	 */
188  	int SCIPgetNChildren(
189  	   SCIP*                 scip                /**< SCIP data structure */
190  	   )
191  	{
192  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNChildren", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
193  	
194  	   return scip->tree->nchildren;
195  	}
196  	
197  	/** gets siblings of focus node along with the number of siblings
198  	 *
199  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
200  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
201  	 *
202  	 *  @pre This method can be called if @p scip is in one of the following stages:
203  	 *       - \ref SCIP_STAGE_SOLVING
204  	 *       - \ref SCIP_STAGE_SOLVED
205  	 */
206  	SCIP_RETCODE SCIPgetSiblings(
207  	   SCIP*                 scip,               /**< SCIP data structure */
208  	   SCIP_NODE***          siblings,           /**< pointer to store siblings array, or NULL if not needed */
209  	   int*                  nsiblings           /**< pointer to store number of siblings, or NULL if not needed */
210  	   )
211  	{
212  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPgetSiblings", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
213  	
214  	   if( siblings != NULL )
215  	      *siblings = scip->tree->siblings;
216  	   if( nsiblings != NULL )
217  	      *nsiblings = scip->tree->nsiblings;
218  	
219  	   return SCIP_OKAY;
220  	}
221  	
222  	/** gets number of siblings of focus node
223  	 *
224  	 *  @return the number of siblings of focus node
225  	 *
226  	 *  @pre This method can be called if @p scip is in one of the following stages:
227  	 *       - \ref SCIP_STAGE_SOLVING
228  	 *       - \ref SCIP_STAGE_SOLVED
229  	 */
230  	int SCIPgetNSiblings(
231  	   SCIP*                 scip                /**< SCIP data structure */
232  	   )
233  	{
234  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNSiblings", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
235  	
236  	   return scip->tree->nsiblings;
237  	}
238  	
239  	/** gets leaves of the tree along with the number of leaves
240  	 *
241  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
242  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
243  	 *
244  	 *  @pre This method can be called if @p scip is in one of the following stages:
245  	 *       - \ref SCIP_STAGE_SOLVING
246  	 *       - \ref SCIP_STAGE_SOLVED
247  	 */
248  	SCIP_RETCODE SCIPgetLeaves(
249  	   SCIP*                 scip,               /**< SCIP data structure */
250  	   SCIP_NODE***          leaves,             /**< pointer to store leaves array, or NULL if not needed */
251  	   int*                  nleaves             /**< pointer to store number of leaves, or NULL if not needed */
252  	   )
253  	{
254  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPgetLeaves", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
255  	
256  	   if( leaves != NULL )
257  	      *leaves = SCIPnodepqNodes(scip->tree->leaves);
258  	   if( nleaves != NULL )
259  	      *nleaves = SCIPnodepqLen(scip->tree->leaves);
260  	
261  	   return SCIP_OKAY;
262  	}
263  	
264  	/** gets number of leaves in the tree
265  	 *
266  	 *  @return the number of leaves in the tree
267  	 *
268  	 *  @pre This method can be called if @p scip is in one of the following stages:
269  	 *       - \ref SCIP_STAGE_SOLVING
270  	 *       - \ref SCIP_STAGE_SOLVED
271  	 */
272  	int SCIPgetNLeaves(
273  	   SCIP*                 scip                /**< SCIP data structure */
274  	   )
275  	{
276  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNLeaves", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
277  	
278  	   return SCIPnodepqLen(scip->tree->leaves);
279  	}
280  	
281  	/** gets the best child of the focus node w.r.t. the node selection priority assigned by the branching rule
282  	 *
283  	 *  @return the best child of the focus node w.r.t. the node selection priority assigned by the branching rule
284  	 *
285  	 *  @pre This method can be called if @p scip is in one of the following stages:
286  	 *       - \ref SCIP_STAGE_SOLVING
287  	 */
288  	SCIP_NODE* SCIPgetPrioChild(
289  	   SCIP*                 scip                /**< SCIP data structure */
290  	   )
291  	{
292  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetPrioChild", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
293  	
294  	   return SCIPtreeGetPrioChild(scip->tree);
295  	}
296  	
297  	/** gets the best sibling of the focus node w.r.t. the node selection priority assigned by the branching rule
298  	 *
299  	 *  @return the best sibling of the focus node w.r.t. the node selection priority assigned by the branching rule
300  	 *
301  	 *  @pre This method can be called if @p scip is in one of the following stages:
302  	 *       - \ref SCIP_STAGE_SOLVING
303  	 */
304  	SCIP_NODE* SCIPgetPrioSibling(
305  	   SCIP*                 scip                /**< SCIP data structure */
306  	   )
307  	{
308  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetPrioSibling", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
309  	
310  	   return SCIPtreeGetPrioSibling(scip->tree);
311  	}
312  	
313  	/** gets the best child of the focus node w.r.t. the node selection strategy
314  	 *
315  	 *  @return the best child of the focus node w.r.t. the node selection strategy
316  	 *
317  	 *  @pre This method can be called if @p scip is in one of the following stages:
318  	 *       - \ref SCIP_STAGE_SOLVING
319  	 */
320  	SCIP_NODE* SCIPgetBestChild(
321  	   SCIP*                 scip                /**< SCIP data structure */
322  	   )
323  	{
324  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBestChild", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
325  	
326  	   return SCIPtreeGetBestChild(scip->tree, scip->set);
327  	}
328  	
329  	/** gets the best sibling of the focus node w.r.t. the node selection strategy
330  	 *
331  	 *  @return the best sibling of the focus node w.r.t. the node selection strategy
332  	 *
333  	 *  @pre This method can be called if @p scip is in one of the following stages:
334  	 *       - \ref SCIP_STAGE_SOLVING
335  	 */
336  	SCIP_NODE* SCIPgetBestSibling(
337  	   SCIP*                 scip                /**< SCIP data structure */
338  	   )
339  	{
340  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBestSibling", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
341  	
342  	   return SCIPtreeGetBestSibling(scip->tree, scip->set);
343  	}
344  	
345  	/** gets the best leaf from the node queue w.r.t. the node selection strategy
346  	 *
347  	 *  @return the best leaf from the node queue w.r.t. the node selection strategy
348  	 *
349  	 *  @pre This method can be called if @p scip is in one of the following stages:
350  	 *       - \ref SCIP_STAGE_SOLVING
351  	 */
352  	SCIP_NODE* SCIPgetBestLeaf(
353  	   SCIP*                 scip                /**< SCIP data structure */
354  	   )
355  	{
356  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBestLeaf", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
357  	
358  	   return SCIPtreeGetBestLeaf(scip->tree);
359  	}
360  	
361  	/** gets the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy
362  	 *
363  	 *  @return the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy
364  	 *
365  	 *  @pre This method can be called if @p scip is in one of the following stages:
366  	 *       - \ref SCIP_STAGE_SOLVING
367  	 */
368  	SCIP_NODE* SCIPgetBestNode(
369  	   SCIP*                 scip                /**< SCIP data structure */
370  	   )
371  	{
372  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBestNode", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
373  	
374  	   return SCIPtreeGetBestNode(scip->tree, scip->set);
375  	}
376  	
377  	/** gets the node with smallest lower bound from the tree (child, sibling, or leaf)
378  	 *
379  	 *  @return the node with smallest lower bound from the tree (child, sibling, or leaf)
380  	 *
381  	 *  @pre This method can be called if @p scip is in one of the following stages:
382  	 *       - \ref SCIP_STAGE_SOLVING
383  	 */
384  	SCIP_NODE* SCIPgetBestboundNode(
385  	   SCIP*                 scip                /**< SCIP data structure */
386  	   )
387  	{
388  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBestboundNode", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
389  	
390  	   return SCIPtreeGetLowerboundNode(scip->tree, scip->set);
391  	}
392  	
393  	/** access to all data of open nodes (leaves, children, and siblings)
394  	 *
395  	 *  @pre This method can be called if @p scip is in one of the following stages:
396  	 *       - \ref SCIP_STAGE_SOLVING
397  	 */
398  	SCIP_RETCODE SCIPgetOpenNodesData(
399  	   SCIP*                 scip,               /**< SCIP data structure */
400  	   SCIP_NODE***          leaves,             /**< pointer to store the leaves, or NULL if not needed */
401  	   SCIP_NODE***          children,           /**< pointer to store the children, or NULL if not needed */
402  	   SCIP_NODE***          siblings,           /**< pointer to store the siblings, or NULL if not needed */
403  	   int*                  nleaves,            /**< pointer to store the number of leaves, or NULL */
404  	   int*                  nchildren,          /**< pointer to store the number of children, or NULL */
405  	   int*                  nsiblings           /**< pointer to store the number of siblings, or NULL */
406  	   )
407  	{
408  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPgetOpenNodesData", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
409  	
410  	   if( leaves != NULL )
411  	      *leaves = SCIPnodepqNodes(scip->tree->leaves);
412  	   if( children != NULL )
413  	      *children = scip->tree->children;
414  	   if( siblings != NULL )
415  	      *siblings = scip->tree->siblings;
416  	   if( nleaves != NULL )
417  	      *nleaves = SCIPnodepqLen(scip->tree->leaves);
418  	   if( nchildren != NULL )
419  	      *nchildren = SCIPtreeGetNChildren(scip->tree);
420  	   if( nsiblings != NULL )
421  	      *nsiblings = SCIPtreeGetNSiblings(scip->tree);
422  	
423  	   return SCIP_OKAY;
424  	}
425  	
426  	/** cuts off node and whole sub tree from branch and bound tree
427  	 *
428  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
429  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
430  	 *
431  	 *  @pre This method can be called if @p scip is in one of the following stages:
432  	 *       - \ref SCIP_STAGE_SOLVING
433  	 */
434  	SCIP_RETCODE SCIPcutoffNode(
435  	   SCIP*                 scip,               /**< SCIP data structure */
436  	   SCIP_NODE*            node                /**< node that should be cut off */
437  	   )
438  	{
439  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPcutoffNode", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
440  	
441  	   SCIP_CALL( SCIPnodeCutoff(node, scip->set, scip->stat, scip->tree, scip->transprob, scip->origprob, scip->reopt,
442  	         scip->lp, scip->mem->probmem) );
443  	
444  	   return SCIP_OKAY;
445  	}
446  	
447  	/** removes all nodes from branch and bound tree that were marked to be cut off via SCIPcutoffNode()
448  	 *
449  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
450  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
451  	 *
452  	 *  @pre This method can be called if @p scip is in one of the following stages:
453  	 *       - \ref SCIP_STAGE_SOLVING
454  	 *
455  	 *  @note In diving mode, the removal of nodes is delayed until diving ends.
456  	 */
457  	SCIP_RETCODE SCIPpruneTree(
458  	   SCIP*                 scip                /**< SCIP data structure */
459  	   )
460  	{
461  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPpruneTree", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
462  	
463  	   SCIP_CALL( SCIPtreeCutoff(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter,
464  	         scip->eventqueue, scip->lp, SCIPinfinity(scip)) );
465  	
466  	   return SCIP_OKAY;
467  	}
468  	
469  	/** marks the given node to be propagated again the next time a node of its subtree is processed
470  	 *
471  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
472  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
473  	 *
474  	 *  @pre This method can be called if @p scip is in one of the following stages:
475  	 *       - \ref SCIP_STAGE_SOLVING
476  	 */
477  	SCIP_RETCODE SCIPrepropagateNode(
478  	   SCIP*                 scip,               /**< SCIP data structure */
479  	   SCIP_NODE*            node                /**< node that should be propagated again */
480  	   )
481  	{
482  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPrepropagateNode", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
483  	
484  	   SCIPnodePropagateAgain(node, scip->set, scip->stat, scip->tree);
485  	
486  	   return SCIP_OKAY;
487  	}
488  	
489  	/** returns depth of first node in active path that is marked being cutoff
490  	 *
491  	 *  @return depth of first node in active path that is marked being cutoff
492  	 *
493  	 *  @pre This method can be called if @p scip is in one of the following stages:
494  	 *       - \ref SCIP_STAGE_SOLVING
495  	 */
496  	int SCIPgetCutoffdepth(
497  	   SCIP*                 scip                /**< SCIP data structure */
498  	   )
499  	{
500  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetCutoffdepth", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
501  	
502  	   return scip->tree->cutoffdepth;
503  	}
504  	
505  	/** returns depth of first node in active path that has to be propagated again
506  	 *
507  	 *  @return depth of first node in active path that has to be propagated again
508  	 *
509  	 *  @pre This method can be called if @p scip is in one of the following stages:
510  	 *       - \ref SCIP_STAGE_SOLVING
511  	 */
512  	int SCIPgetRepropdepth(
513  	   SCIP*                 scip                /**< SCIP data structure */
514  	   )
515  	{
516  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetRepropdepth", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
517  	
518  	   return scip->tree->repropdepth;
519  	}
520  	
521  	/** prints all branching decisions on variables from the root to the given node
522  	 *
523  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
524  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
525  	 *
526  	 *  @pre This method can be called if @p scip is in one of the following stages:
527  	 *       - \ref SCIP_STAGE_SOLVING
528  	 */
529  	SCIP_RETCODE SCIPprintNodeRootPath(
530  	   SCIP*                 scip,               /**< SCIP data structure */
531  	   SCIP_NODE*            node,               /**< node data */
532  	   FILE*                 file                /**< output file (or NULL for standard output) */
533  	   )
534  	{
535  	   SCIP_VAR**            branchvars;         /* array of variables on which the branchings has been performed in all ancestors */
536  	   SCIP_Real*            branchbounds;       /* array of bounds which the branchings in all ancestors set */
537  	   SCIP_BOUNDTYPE*       boundtypes;         /* array of boundtypes which the branchings in all ancestors set */
538  	   int*                  nodeswitches;       /* marks, where in the arrays the branching decisions of the next node on the path start
539  	                                              * branchings performed at the parent of node always start at position 0. For single variable branching,
540  	                                              * nodeswitches[i] = i holds */
541  	   int                   nbranchvars;        /* number of variables on which branchings have been performed in all ancestors
542  	                                              *   if this is larger than the array size, arrays should be reallocated and method should be called again */
543  	   int                   branchvarssize;     /* available slots in arrays */
544  	   int                   nnodes;             /* number of nodes in the nodeswitch array */
545  	   int                   nodeswitchsize;     /* available slots in node switch array */
546  	
547  	   branchvarssize = SCIPnodeGetDepth(node);
548  	   nodeswitchsize = branchvarssize;
549  	
550  	   /* memory allocation */
551  	   SCIP_CALL( SCIPallocBufferArray(scip, &branchvars, branchvarssize) );
552  	   SCIP_CALL( SCIPallocBufferArray(scip, &branchbounds, branchvarssize) );
553  	   SCIP_CALL( SCIPallocBufferArray(scip, &boundtypes, branchvarssize) );
554  	   SCIP_CALL( SCIPallocBufferArray(scip, &nodeswitches, nodeswitchsize) );
555  	
556  	   SCIPnodeGetAncestorBranchingPath(node, branchvars, branchbounds, boundtypes, &nbranchvars, branchvarssize, nodeswitches, &nnodes, nodeswitchsize );
557  	
558  	   /* if the arrays were too small, we have to reallocate them and recall SCIPnodeGetAncestorBranchingPath */
559  	   if( nbranchvars > branchvarssize || nnodes > nodeswitchsize )
560  	   {
561  	      branchvarssize = nbranchvars;
562  	      nodeswitchsize = nnodes;
563  	
564  	      /* memory reallocation */
565  	      SCIP_CALL( SCIPreallocBufferArray(scip, &branchvars, branchvarssize) );
566  	      SCIP_CALL( SCIPreallocBufferArray(scip, &branchbounds, branchvarssize) );
567  	      SCIP_CALL( SCIPreallocBufferArray(scip, &boundtypes, branchvarssize) );
568  	      SCIP_CALL( SCIPreallocBufferArray(scip, &nodeswitches, nodeswitchsize) );
569  	
570  	      SCIPnodeGetAncestorBranchingPath(node, branchvars, branchbounds, boundtypes, &nbranchvars, branchvarssize, nodeswitches, &nnodes, nodeswitchsize);
571  	      assert(nbranchvars == branchvarssize);
572  	   }
573  	
574  	   /* we only want to create output, if branchings were performed */
575  	   if( nbranchvars >= 1 )
576  	   {
577  	      int i;
578  	      int j;
579  	
580  	      /* print all nodes, starting from the root, which is last in the arrays */
581  	      for( j = nnodes-1; j >= 0; --j)
582  	      {
583  	         int end;
584  	         if(j == nnodes-1)
585  	            end =  nbranchvars;
586  	         else
587  	            end =  nodeswitches[j+1];
588  	
589  	         for( i = nodeswitches[j]; i < end; ++i )
590  	         {
591  	            if( i > nodeswitches[j] )
592  	               SCIPmessageFPrintInfo(scip->messagehdlr, file, " AND ");
593  	            SCIPmessageFPrintInfo(scip->messagehdlr, file, "<%s> %s %.1f",SCIPvarGetName(branchvars[i]), boundtypes[i] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", branchbounds[i]);
594  	         }
595  	         SCIPmessageFPrintInfo(scip->messagehdlr, file, "\n");
596  	         if( j > 0 )
597  	         {
598  	            if(  nodeswitches[j]-nodeswitches[j-1] != 1 )
599  	               SCIPmessageFPrintInfo(scip->messagehdlr, file, " |\n |\n");
600  	            else if( boundtypes[i-1] == SCIP_BOUNDTYPE_LOWER )
601  	               SCIPmessageFPrintInfo(scip->messagehdlr, file, "\\ \n \\\n");
602  	            else
603  	               SCIPmessageFPrintInfo(scip->messagehdlr, file, " /\n/ \n");
604  	         }
605  	      }
606  	   }
607  	
608  	   /* free all local memory */
609  	   SCIPfreeBufferArray(scip, &nodeswitches);
610  	   SCIPfreeBufferArray(scip, &boundtypes);
611  	   SCIPfreeBufferArray(scip, &branchbounds);
612  	   SCIPfreeBufferArray(scip, &branchvars);
613  	
614  	   return SCIP_OKAY;
615  	}
616  	
617  	/** sets whether the LP should be solved at the focus node
618  	 *
619  	 *  @note In order to have an effect, this method needs to be called after a node is focused but before the LP is
620  	 *        solved.
621  	 *
622  	 *  @pre This method can be called if @p scip is in one of the following stages:
623  	 *       - \ref SCIP_STAGE_SOLVING
624  	 */
625  	void SCIPsetFocusnodeLP(
626  	   SCIP*                 scip,               /**< SCIP data structure */
627  	   SCIP_Bool             solvelp             /**< should the LP be solved? */
628  	   )
629  	{
630  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPsetFocusnodeLP", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
631  	
632  	   SCIPtreeSetFocusNodeLP(scip->tree, solvelp);
633  	}
634  	
635  	/** gets number of nodes left in the tree (children + siblings + leaves)
636  	 *
637  	 *  @return the number of nodes left in the tree (children + siblings + leaves)
638  	 *
639  	 *  @pre This method can be called if SCIP is in one of the following stages:
640  	 *       - \ref SCIP_STAGE_PRESOLVED
641  	 *       - \ref SCIP_STAGE_SOLVING
642  	 *       - \ref SCIP_STAGE_SOLVED
643  	 */
644  	int SCIPgetNNodesLeft(
645  	   SCIP*                 scip                /**< SCIP data structure */
646  	   )
647  	{
648  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNNodesLeft", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
649  	
650  	   return SCIPtreeGetNNodes(scip->tree);
651  	}
652  	
653  	/** gets depth of current node, or -1 if no current node exists; in probing, the current node is the last probing node,
654  	 *  such that the depth includes the probing path
655  	 *
656  	 *  @return the depth of current node, or -1 if no current node exists; in probing, the current node is the last probing node,
657  	 *  such that the depth includes the probing path
658  	 *
659  	 *  @pre This method can be called if SCIP is in one of the following stages:
660  	 *       - \ref SCIP_STAGE_TRANSFORMED
661  	 *       - \ref SCIP_STAGE_INITPRESOLVE
662  	 *       - \ref SCIP_STAGE_PRESOLVING
663  	 *       - \ref SCIP_STAGE_EXITPRESOLVE
664  	 *       - \ref SCIP_STAGE_PRESOLVED
665  	 *       - \ref SCIP_STAGE_INITSOLVE
666  	 *       - \ref SCIP_STAGE_SOLVING
667  	 *       - \ref SCIP_STAGE_SOLVED
668  	 *       - \ref SCIP_STAGE_EXITSOLVE
669  	 */
670  	int SCIPgetDepth(
671  	   SCIP*                 scip                /**< SCIP data structure */
672  	   )
673  	{
674  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetDepth", FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE) );
675  	
676  	   return SCIPtreeGetCurrentDepth(scip->tree);
677  	}
678  	
679  	/** gets depth of the focus node, or -1 if no focus node exists; the focus node is the currently processed node in the
680  	 *  branching tree, excluding the nodes of the probing path
681  	 *
682  	 *  @return the depth of the focus node, or -1 if no focus node exists; the focus node is the currently processed node in the
683  	 *  branching tree, excluding the nodes of the probing path
684  	 *
685  	 *  @pre This method can be called if SCIP is in one of the following stages:
686  	 *       - \ref SCIP_STAGE_TRANSFORMED
687  	 *       - \ref SCIP_STAGE_INITPRESOLVE
688  	 *       - \ref SCIP_STAGE_PRESOLVING
689  	 *       - \ref SCIP_STAGE_EXITPRESOLVE
690  	 *       - \ref SCIP_STAGE_PRESOLVED
691  	 *       - \ref SCIP_STAGE_INITSOLVE
692  	 *       - \ref SCIP_STAGE_SOLVING
693  	 *       - \ref SCIP_STAGE_SOLVED
694  	 *       - \ref SCIP_STAGE_EXITSOLVE
695  	 */
696  	int SCIPgetFocusDepth(
697  	   SCIP*                 scip                /**< SCIP data structure */
698  	   )
699  	{
700  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetFocusDepth", FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE) );
701  	
702  	   return SCIPtreeGetFocusDepth(scip->tree);
703  	}
704  	
705  	/** gets current plunging depth (successive times, a child was selected as next node)
706  	 *
707  	 *  @return the current plunging depth (successive times, a child was selected as next node)
708  	 *
709  	 *  @pre This method can be called if SCIP is in one of the following stages:
710  	 *       - \ref SCIP_STAGE_PRESOLVED
711  	 *       - \ref SCIP_STAGE_SOLVING
712  	 */
713  	int SCIPgetPlungeDepth(
714  	   SCIP*                 scip                /**< SCIP data structure */
715  	   )
716  	{
717  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetPlungeDepth", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
718  	
719  	   return scip->stat->plungedepth;
720  	}
721  	
722  	/** query if node was the last parent of a branching of the tree
723  	 *
724  	 *  @return TRUE if node was the last parent of a branching of the tree
725  	 *
726  	 *  @pre This method can be called if SCIP is in one of the following stages:
727  	 *       - \ref SCIP_STAGE_PRESOLVED
728  	 *       - \ref SCIP_STAGE_SOLVING
729  	 *       - \ref SCIP_STAGE_SOLVED
730  	 */
731  	SCIP_Bool SCIPwasNodeLastBranchParent(
732  	   SCIP*                 scip,               /**< SCIP data structure */
733  	   SCIP_NODE*            node                /**< tree node, or NULL to check focus node */
734  	   )
735  	{
736  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPwasNodeLastBranchParent", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
737  	
738  	   return SCIPtreeWasNodeLastBranchParent(scip->tree, node);
739  	}
740