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   tree.h
26   	 * @ingroup INTERNALAPI
27   	 * @brief  internal methods for branch and bound tree
28   	 * @author Tobias Achterberg
29   	 * @author Timo Berthold
30   	 */
31   	
32   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33   	
34   	#ifndef __SCIP_TREE_H__
35   	#define __SCIP_TREE_H__
36   	
37   	
38   	#include "blockmemshell/memory.h"
39   	#include "scip/def.h"
40   	#include "scip/nodesel.h"
41   	#include "scip/type_set.h"
42   	#include "scip/type_stat.h"
43   	#include "scip/type_cons.h"
44   	#include "scip/type_event.h"
45   	#include "scip/type_lp.h"
46   	#include "scip/type_var.h"
47   	#include "scip/type_prob.h"
48   	#include "scip/type_primal.h"
49   	#include "scip/type_tree.h"
50   	#include "scip/type_reopt.h"
51   	#include "scip/type_branch.h"
52   	#include "scip/type_prop.h"
53   	#include "scip/type_implics.h"
54   	#include "scip/type_history.h"
55   	#include "scip/type_conflictstore.h"
56   	#include "scip/pub_tree.h"
57   	
58   	#ifndef NDEBUG
59   	#include "scip/struct_tree.h"
60   	#endif
61   	
62   	#ifdef __cplusplus
63   	extern "C" {
64   	#endif
65   	
66   	
67   	/*
68   	 * Node methods
69   	 */
70   	
71   	/** creates a child node of the focus node */
72   	SCIP_RETCODE SCIPnodeCreateChild(
73   	   SCIP_NODE**           node,               /**< pointer to node data structure */
74   	   BMS_BLKMEM*           blkmem,             /**< block memory */
75   	   SCIP_SET*             set,                /**< global SCIP settings */
76   	   SCIP_STAT*            stat,               /**< problem statistics */
77   	   SCIP_TREE*            tree,               /**< branch and bound tree */
78   	   SCIP_Real             nodeselprio,        /**< node selection priority of new node */
79   	   SCIP_Real             estimate            /**< estimate for (transformed) objective value of best feasible solution in subtree */
80   	   );
81   	
82   	/** frees node */
83   	SCIP_RETCODE SCIPnodeFree(
84   	   SCIP_NODE**           node,               /**< node data */
85   	   BMS_BLKMEM*           blkmem,             /**< block memory buffer */
86   	   SCIP_SET*             set,                /**< global SCIP settings */
87   	   SCIP_STAT*            stat,               /**< problem statistics */
88   	   SCIP_EVENTFILTER*     eventfilter,        /**< event filter for global (not variable dependent) events */
89   	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
90   	   SCIP_TREE*            tree,               /**< branch and bound tree */
91   	   SCIP_LP*              lp                  /**< current LP data */
92   	   );
93   	
94   	/** increases the reference counter of the LP state in the fork or subroot node */
95   	SCIP_RETCODE SCIPnodeCaptureLPIState(
96   	   SCIP_NODE*            node,               /**< fork/subroot node */
97   	   int                   nuses               /**< number to add to the usage counter */
98   	   );
99   	
100  	/** decreases the reference counter of the LP state in the fork or subroot node */
101  	SCIP_RETCODE SCIPnodeReleaseLPIState(
102  	   SCIP_NODE*            node,               /**< fork/subroot node */
103  	   BMS_BLKMEM*           blkmem,             /**< block memory buffers */
104  	   SCIP_LP*              lp                  /**< current LP data */
105  	   );
106  	
107  	/** installs a child, a sibling, or a leaf node as the new focus node */
108  	SCIP_RETCODE SCIPnodeFocus(
109  	   SCIP_NODE**           node,               /**< pointer to node to focus (or NULL to remove focus); the node
110  	                                              *   is freed, if it was cut off due to a cut off subtree */
111  	   BMS_BLKMEM*           blkmem,             /**< block memory */
112  	   SCIP_SET*             set,                /**< global SCIP settings */
113  	   SCIP_MESSAGEHDLR*     messagehdlr,        /**< message handler */
114  	   SCIP_STAT*            stat,               /**< problem statistics */
115  	   SCIP_PROB*            transprob,          /**< transformed problem */
116  	   SCIP_PROB*            origprob,           /**< original problem */
117  	   SCIP_PRIMAL*          primal,             /**< primal data */
118  	   SCIP_TREE*            tree,               /**< branch and bound tree */
119  	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
120  	   SCIP_LP*              lp,                 /**< current LP data */
121  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
122  	   SCIP_CONFLICT*        conflict,           /**< conflict analysis data */
123  	   SCIP_CONFLICTSTORE*   conflictstore,      /**< conflict store */
124  	   SCIP_EVENTFILTER*     eventfilter,        /**< event filter for global (not variable dependent) events */
125  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
126  	   SCIP_CLIQUETABLE*     cliquetable,        /**< clique table data structure */
127  	   SCIP_Bool*            cutoff,             /**< pointer to store whether the given node can be cut off */
128  	   SCIP_Bool             postponed,          /**< was the current focus node postponed? */
129  	   SCIP_Bool             exitsolve           /**< are we in exitsolve stage, so we only need to loose the children */
130  	   );
131  	
132  	/** cuts off node and whole sub tree from branch and bound tree */
133  	SCIP_RETCODE SCIPnodeCutoff(
134  	   SCIP_NODE*            node,               /**< node that should be cut off */
135  	   SCIP_SET*             set,                /**< global SCIP settings */
136  	   SCIP_STAT*            stat,               /**< problem statistics */
137  	   SCIP_TREE*            tree,               /**< branch and bound tree */
138  	   SCIP_PROB*            transprob,          /**< transformed problem after presolve */
139  	   SCIP_PROB*            origprob,           /**< original problem */
140  	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
141  	   SCIP_LP*              lp,                 /**< current LP */
142  	   BMS_BLKMEM*           blkmem              /**< block memory */
143  	   );
144  	
145  	/** marks node, that propagation should be applied again the next time, a node of its subtree is focused */
146  	void SCIPnodePropagateAgain(
147  	   SCIP_NODE*            node,               /**< node that should be propagated again */
148  	   SCIP_SET*             set,                /**< global SCIP settings */
149  	   SCIP_STAT*            stat,               /**< problem statistics */
150  	   SCIP_TREE*            tree                /**< branch and bound tree */
151  	   );
152  	
153  	/** marks node, that it is completely propagated in the current repropagation subtree level */
154  	void SCIPnodeMarkPropagated(
155  	   SCIP_NODE*            node,               /**< node that should be propagated again */
156  	   SCIP_TREE*            tree                /**< branch and bound tree */
157  	   );
158  	
159  	/** adds constraint locally to the node and captures it; activates constraint, if node is active;
160  	 *  if a local constraint is added to the root node, it is automatically upgraded into a global constraint
161  	 */
162  	SCIP_RETCODE SCIPnodeAddCons(
163  	   SCIP_NODE*            node,               /**< node to add constraint to */
164  	   BMS_BLKMEM*           blkmem,             /**< block memory */
165  	   SCIP_SET*             set,                /**< global SCIP settings */
166  	   SCIP_STAT*            stat,               /**< problem statistics */
167  	   SCIP_TREE*            tree,               /**< branch and bound tree */
168  	   SCIP_CONS*            cons                /**< constraint to add */
169  	   );
170  	
171  	/** locally deletes constraint at the given node by disabling its separation, enforcing, and propagation capabilities
172  	 *  at the node; captures constraint; disables constraint, if node is active
173  	 */
174  	SCIP_RETCODE SCIPnodeDelCons(
175  	   SCIP_NODE*            node,               /**< node to add constraint to */
176  	   BMS_BLKMEM*           blkmem,             /**< block memory */
177  	   SCIP_SET*             set,                /**< global SCIP settings */
178  	   SCIP_STAT*            stat,               /**< problem statistics */
179  	   SCIP_TREE*            tree,               /**< branch and bound tree */
180  	   SCIP_CONS*            cons                /**< constraint to locally delete */
181  	   );
182  	
183  	/** return all bound changes based on constraint propagation; stop saving the bound changes if we reach a branching
184  	 *  decision based on a dual information
185  	 */
186  	void SCIPnodeGetConsProps(
187  	   SCIP_NODE*            node,               /**< node */
188  	   SCIP_VAR**            vars,               /**< array of variables on which constraint propagation triggers a bound change */
189  	   SCIP_Real*            varbounds,          /**< array of bounds set by constraint propagation */
190  	   SCIP_BOUNDTYPE*       varboundtypes,      /**< array of boundtypes set by constraint propagation */
191  	   int*                  nconspropvars,      /**< number of variables on which constraint propagation triggers a bound change
192  	                                              *   if this is larger than the array size, arrays should be reallocated and method
193  	                                              *   should be called again */
194  	   int                   conspropvarssize    /**< available slots in arrays */
195  	   );
196  	
197  	/** gets all bound changes applied after the first bound change based on dual information.
198  	 *
199  	 *  @note: currently, we can only detect bound changes based in dual information if they arise from strong branching.
200  	 */
201  	void SCIPnodeGetBdChgsAfterDual(
202  	   SCIP_NODE*            node,               /**< node */
203  	   SCIP_VAR**            vars,               /**< array of variables on which the branching has been performed in the parent node */
204  	   SCIP_Real*            varbounds,          /**< array of bounds which the branching in the parent node set */
205  	   SCIP_BOUNDTYPE*       varboundtypes,      /**< array of boundtypes which the branching in the parent node set */
206  	   int                   start,              /**< first free slot in the arrays */
207  	   int*                  nbranchvars,        /**< number of variables on which branching has been performed in the parent node
208  	                                              *   if this is larger than the array size, arrays should be reallocated and method
209  	                                              *   should be called again */
210  	   int                   branchvarssize      /**< available slots in arrays */
211  	   );
212  	
213  	/** adds bound change with inference information to focus node, child of focus node, or probing node;
214  	 *  if possible, adjusts bound to integral value;
215  	 *  at most one of infercons and inferprop may be non-NULL
216  	 */
217  	SCIP_RETCODE SCIPnodeAddBoundinfer(
218  	   SCIP_NODE*            node,               /**< node to add bound change to */
219  	   BMS_BLKMEM*           blkmem,             /**< block memory */
220  	   SCIP_SET*             set,                /**< global SCIP settings */
221  	   SCIP_STAT*            stat,               /**< problem statistics */
222  	   SCIP_PROB*            transprob,          /**< transformed problem after presolve */
223  	   SCIP_PROB*            origprob,           /**< original problem */
224  	   SCIP_TREE*            tree,               /**< branch and bound tree */
225  	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
226  	   SCIP_LP*              lp,                 /**< current LP data */
227  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
228  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
229  	   SCIP_CLIQUETABLE*     cliquetable,        /**< clique table data structure */
230  	   SCIP_VAR*             var,                /**< variable to change the bounds for */
231  	   SCIP_Real             newbound,           /**< new value for bound */
232  	   SCIP_BOUNDTYPE        boundtype,          /**< type of bound: lower or upper bound */
233  	   SCIP_CONS*            infercons,          /**< constraint that deduced the bound change, or NULL */
234  	   SCIP_PROP*            inferprop,          /**< propagator that deduced the bound change, or NULL */
235  	   int                   inferinfo,          /**< user information for inference to help resolving the conflict */
236  	   SCIP_Bool             probingchange       /**< is the bound change a temporary setting due to probing? */
237  	   );
238  	
239  	/** adds bound change to focus node, or child of focus node, or probing node;
240  	 *  if possible, adjusts bound to integral value
241  	 */
242  	SCIP_RETCODE SCIPnodeAddBoundchg(
243  	   SCIP_NODE*            node,               /**< node to add bound change to */
244  	   BMS_BLKMEM*           blkmem,             /**< block memory */
245  	   SCIP_SET*             set,                /**< global SCIP settings */
246  	   SCIP_STAT*            stat,               /**< problem statistics */
247  	   SCIP_PROB*            transprob,          /**< transformed problem after presolve */
248  	   SCIP_PROB*            origprob,           /**< original problem */
249  	   SCIP_TREE*            tree,               /**< branch and bound tree */
250  	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
251  	   SCIP_LP*              lp,                 /**< current LP data */
252  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
253  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
254  	   SCIP_CLIQUETABLE*     cliquetable,        /**< clique table data structure */
255  	   SCIP_VAR*             var,                /**< variable to change the bounds for */
256  	   SCIP_Real             newbound,           /**< new value for bound */
257  	   SCIP_BOUNDTYPE        boundtype,          /**< type of bound: lower or upper bound */
258  	   SCIP_Bool             probingchange       /**< is the bound change a temporary setting due to probing? */
259  	   );
260  	
261  	/** adds hole with inference information to focus node, child of focus node, or probing node;
262  	 *  if possible, adjusts bound to integral value;
263  	 *  at most one of infercons and inferprop may be non-NULL
264  	 */
265  	SCIP_RETCODE SCIPnodeAddHoleinfer(
266  	   SCIP_NODE*            node,               /**< node to add bound change to */
267  	   BMS_BLKMEM*           blkmem,             /**< block memory */
268  	   SCIP_SET*             set,                /**< global SCIP settings */
269  	   SCIP_STAT*            stat,               /**< problem statistics */
270  	   SCIP_TREE*            tree,               /**< branch and bound tree */
271  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
272  	   SCIP_VAR*             var,                /**< variable to change the bounds for */
273  	   SCIP_Real             left,               /**< left bound of open interval defining the hole (left,right) */
274  	   SCIP_Real             right,              /**< right bound of open interval defining the hole (left,right) */
275  	   SCIP_CONS*            infercons,          /**< constraint that deduced the bound change, or NULL */
276  	   SCIP_PROP*            inferprop,          /**< propagator that deduced the bound change, or NULL */
277  	   int                   inferinfo,          /**< user information for inference to help resolving the conflict */
278  	   SCIP_Bool             probingchange,      /**< is the bound change a temporary setting due to probing? */
279  	   SCIP_Bool*            added               /**< pointer to store whether the hole was added, or NULL */
280  	   );
281  	
282  	/** adds hole change to focus node, or child of focus node */
283  	SCIP_RETCODE SCIPnodeAddHolechg(
284  	   SCIP_NODE*            node,               /**< node to add bound change to */
285  	   BMS_BLKMEM*           blkmem,             /**< block memory */
286  	   SCIP_SET*             set,                /**< global SCIP settings */
287  	   SCIP_STAT*            stat,               /**< problem statistics */
288  	   SCIP_TREE*            tree,               /**< branch and bound tree */
289  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
290  	   SCIP_VAR*             var,                /**< variable to change the bounds for */
291  	   SCIP_Real             left,               /**< left bound of open interval defining the hole (left,right) */
292  	   SCIP_Real             right,              /**< right bound of open interval defining the hole (left,right) */
293  	   SCIP_Bool             probingchange,      /**< is the bound change a temporary setting due to probing? */
294  	   SCIP_Bool*            added               /**< pointer to store whether the hole was added, or NULL */
295  	   );
296  	
297  	/** if given value is larger than the node's lower bound, sets the node's lower bound to the new value */
298  	void SCIPnodeUpdateLowerbound(
299  	   SCIP_NODE*            node,               /**< node to update lower bound for */
300  	   SCIP_STAT*            stat,               /**< problem statistics */
301  	   SCIP_SET*             set,                /**< global SCIP settings */
302  	   SCIP_TREE*            tree,               /**< branch and bound tree */
303  	   SCIP_PROB*            transprob,          /**< transformed problem data */
304  	   SCIP_PROB*            origprob,           /**< original problem */
305  	   SCIP_Real             newbound            /**< new lower bound for the node (if it's larger than the old one) */
306  	   );
307  	
308  	/** updates lower bound of node using lower bound of LP */
309  	SCIP_RETCODE SCIPnodeUpdateLowerboundLP(
310  	   SCIP_NODE*            node,               /**< node to set lower bound for */
311  	   SCIP_SET*             set,                /**< global SCIP settings */
312  	   SCIP_STAT*            stat,               /**< problem statistics */
313  	   SCIP_TREE*            tree,               /**< branch and bound tree */
314  	   SCIP_PROB*            transprob,          /**< transformed problem after presolve */
315  	   SCIP_PROB*            origprob,           /**< original problem */
316  	   SCIP_LP*              lp                  /**< LP data */
317  	   );
318  	
319  	/** change the node selection priority of the given child */
320  	void SCIPchildChgNodeselPrio(
321  	   SCIP_TREE*            tree,               /**< branch and bound tree */
322  	   SCIP_NODE*            child,              /**< child to update the node selection priority */
323  	   SCIP_Real             priority            /**< node selection priority value */
324  	   );
325  	
326  	
327  	/** sets the node's estimated bound to the new value */
328  	void SCIPnodeSetEstimate(
329  	   SCIP_NODE*            node,               /**< node to update lower bound for */
330  	   SCIP_SET*             set,                /**< global SCIP settings */
331  	   SCIP_Real             newestimate         /**< new estimated bound for the node */
332  	   );
333  	
334  	/** propagates implications of binary fixings at the given node triggered by the implication graph and the clique table */
335  	SCIP_RETCODE SCIPnodePropagateImplics(
336  	   SCIP_NODE*            node,               /**< node to propagate implications on */
337  	   BMS_BLKMEM*           blkmem,             /**< block memory */
338  	   SCIP_SET*             set,                /**< global SCIP settings */
339  	   SCIP_STAT*            stat,               /**< problem statistics */
340  	   SCIP_PROB*            transprob,          /**< transformed problem after presolve */
341  	   SCIP_PROB*            origprob,           /**< original problem */
342  	   SCIP_TREE*            tree,               /**< branch and bound tree */
343  	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
344  	   SCIP_LP*              lp,                 /**< current LP data */
345  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
346  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
347  	   SCIP_CLIQUETABLE*     cliquetable,        /**< clique table data structure */
348  	   SCIP_Bool*            cutoff              /**< pointer to store whether the node can be cut off */
349  	   );
350  	
351  	/** returns all bound changes based on dual information.
352  	 *
353  	 *  currently, this methods works only for bound changes made by strong branching on binary variables. we need this
354  	 *  method to ensure optimality within reoptimization.
355  	 *
356  	 *  since the bound changes made by strong branching are stored as SCIP_BOUNDCHGTYPE_CONSINFER or SCIP_BOUNDCHGTYPE_PROPINFER
357  	 *  with no constraint or propagator, resp., we are are interested in bound changes with these attributes.
358  	 *
359  	 *  all bound changes of type SCIP_BOUNDCHGTYPE_BRANCHING are stored in the beginning of the bound change array, afterwards,
360  	 *  we can find the other two types. thus, we start the search at the end of the list and stop when reaching the first
361  	 *  bound change of type SCIP_BOUNDCHGTYPE_BRANCHING.
362  	 */
363  	void SCIPnodeGetDualBoundchgs(
364  	   SCIP_NODE*            node,               /**< node data */
365  	   SCIP_VAR**            vars,               /**< array of variables on which the bound change is based on dual information */
366  	   SCIP_Real*            bounds,             /**< array of bounds which are based on dual information */
367  	   SCIP_BOUNDTYPE*       boundtypes,         /**< array of boundtypes which are based on dual information */
368  	   int*                  nvars,              /**< number of variables on which the bound change is based on dual information
369  	                                              *   if this is larger than the array size, arrays should be reallocated and method
370  	                                              *   should be called again */
371  	   int                   varssize            /**< available slots in arrays */
372  	   );
373  	
374  	/** returns the number of bound changes based on dual information.
375  	 *
376  	 *  currently, this methods works only for bound changes made by strong branching on binary variables. we need this
377  	 *  method to ensure optimality within reoptimization.
378  	 *
379  	 *  since the bound changes made by strong branching are stored as SCIP_BOUNDCHGTYPE_CONSINFER or SCIP_BOUNDCHGTYPE_PROPINFER
380  	 *  with no constraint or propagator, resp., we are are interested in bound changes with these attributes.
381  	 *
382  	 *  all bound changes of type SCIP_BOUNDCHGTYPE_BRANCHING are stored in the beginning of the bound change array, afterwards,
383  	 *  we can find the other two types. thus, we start the search at the end of the list and stop when reaching the first
384  	 *  bound change of type SCIP_BOUNDCHGTYPE_BRANCHING.
385  	 */
386  	int SCIPnodeGetNDualBndchgs(
387  	   SCIP_NODE*            node
388  	   );
389  	
390  	/*
391  	 * Tree methods
392  	 */
393  	
394  	/** creates an initialized tree data structure */
395  	SCIP_RETCODE SCIPtreeCreate(
396  	   SCIP_TREE**           tree,               /**< pointer to tree data structure */
397  	   BMS_BLKMEM*           blkmem,             /**< block memory buffers */
398  	   SCIP_SET*             set,                /**< global SCIP settings */
399  	   SCIP_NODESEL*         nodesel             /**< node selector to use for sorting leaves in the priority queue */
400  	   );
401  	
402  	/** frees tree data structure */
403  	SCIP_RETCODE SCIPtreeFree(
404  	   SCIP_TREE**           tree,               /**< pointer to tree data structure */
405  	   BMS_BLKMEM*           blkmem,             /**< block memory buffers */
406  	   SCIP_SET*             set,                /**< global SCIP settings */
407  	   SCIP_STAT*            stat,               /**< problem statistics */
408  	   SCIP_EVENTFILTER*     eventfilter,        /**< event filter for global (not variable dependent) events */
409  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
410  	   SCIP_LP*              lp                  /**< current LP data */
411  	   );
412  	
413  	/** clears and resets tree data structure and deletes all nodes */
414  	SCIP_RETCODE SCIPtreeClear(
415  	   SCIP_TREE*            tree,               /**< tree data structure */
416  	   BMS_BLKMEM*           blkmem,             /**< block memory buffers */
417  	   SCIP_SET*             set,                /**< global SCIP settings */
418  	   SCIP_STAT*            stat,               /**< problem statistics */
419  	   SCIP_EVENTFILTER*     eventfilter,        /**< event filter for global (not variable dependent) events */
420  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
421  	   SCIP_LP*              lp                  /**< current LP data */
422  	   );
423  	
424  	/** creates the root node of the tree and puts it into the leaves queue */
425  	SCIP_RETCODE SCIPtreeCreateRoot(
426  	   SCIP_TREE*            tree,               /**< tree data structure */
427  	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
428  	   BMS_BLKMEM*           blkmem,             /**< block memory buffers */
429  	   SCIP_SET*             set,                /**< global SCIP settings */
430  	   SCIP_STAT*            stat,               /**< problem statistics */
431  	   SCIP_EVENTFILTER*     eventfilter,        /**< event filter for global (not variable dependent) events */
432  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
433  	   SCIP_LP*              lp                  /**< current LP data */
434  	   );
435  	
436  	/** creates a temporary presolving root node of the tree and installs it as focus node */
437  	SCIP_RETCODE SCIPtreeCreatePresolvingRoot(
438  	   SCIP_TREE*            tree,               /**< tree data structure */
439  	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
440  	   BMS_BLKMEM*           blkmem,             /**< block memory buffers */
441  	   SCIP_SET*             set,                /**< global SCIP settings */
442  	   SCIP_MESSAGEHDLR*     messagehdlr,        /**< message handler */
443  	   SCIP_STAT*            stat,               /**< problem statistics */
444  	   SCIP_PROB*            transprob,          /**< transformed problem */
445  	   SCIP_PROB*            origprob,           /**< original problem */
446  	   SCIP_PRIMAL*          primal,             /**< primal data */
447  	   SCIP_LP*              lp,                 /**< current LP data */
448  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
449  	   SCIP_CONFLICT*        conflict,           /**< conflict analysis data */
450  	   SCIP_CONFLICTSTORE*   conflictstore,      /**< conflict store */
451  	   SCIP_EVENTFILTER*     eventfilter,        /**< event filter for global (not variable dependent) events */
452  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
453  	   SCIP_CLIQUETABLE*     cliquetable         /**< clique table data structure */
454  	   );
455  	
456  	/** frees the temporary presolving root and resets tree data structure */
457  	SCIP_RETCODE SCIPtreeFreePresolvingRoot(
458  	   SCIP_TREE*            tree,               /**< tree data structure */
459  	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
460  	   BMS_BLKMEM*           blkmem,             /**< block memory buffers */
461  	   SCIP_SET*             set,                /**< global SCIP settings */
462  	   SCIP_MESSAGEHDLR*     messagehdlr,        /**< message handler */
463  	   SCIP_STAT*            stat,               /**< problem statistics */
464  	   SCIP_PROB*            transprob,          /**< transformed problem */
465  	   SCIP_PROB*            origprob,           /**< original problem */
466  	   SCIP_PRIMAL*          primal,             /**< primal data */
467  	   SCIP_LP*              lp,                 /**< current LP data */
468  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
469  	   SCIP_CONFLICT*        conflict,           /**< conflict analysis data */
470  	   SCIP_CONFLICTSTORE*   conflictstore,      /**< conflict store */
471  	   SCIP_EVENTFILTER*     eventfilter,        /**< event filter for global (not variable dependent) events */
472  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
473  	   SCIP_CLIQUETABLE*     cliquetable         /**< clique table data structure */
474  	   );
475  	
476  	/** returns the node selector associated with the given node priority queue */
477  	SCIP_NODESEL* SCIPtreeGetNodesel(
478  	   SCIP_TREE*            tree                /**< branch and bound tree */
479  	   );
480  	
481  	/** sets the node selector used for sorting the nodes in the priority queue, and resorts the queue if necessary */
482  	SCIP_RETCODE SCIPtreeSetNodesel(
483  	   SCIP_TREE*            tree,               /**< branch and bound tree */
484  	   SCIP_SET*             set,                /**< global SCIP settings */
485  	   SCIP_MESSAGEHDLR*     messagehdlr,        /**< message handler */
486  	   SCIP_STAT*            stat,               /**< problem statistics */
487  	   SCIP_NODESEL*         nodesel             /**< node selector to use for sorting the nodes in the queue */
488  	   );
489  	
490  	/** cuts off nodes with lower bound not better than given upper bound */
491  	SCIP_RETCODE SCIPtreeCutoff(
492  	   SCIP_TREE*            tree,               /**< branch and bound tree */
493  	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
494  	   BMS_BLKMEM*           blkmem,             /**< block memory */
495  	   SCIP_SET*             set,                /**< global SCIP settings */
496  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
497  	   SCIP_EVENTFILTER*     eventfilter,        /**< event filter for global (not variable dependent) events */
498  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
499  	   SCIP_LP*              lp,                 /**< current LP data */
500  	   SCIP_Real             cutoffbound         /**< cutoff bound: all nodes with lowerbound >= cutoffbound are cut off */
501  	   );
502  	
503  	/** constructs the LP relaxation of the focus node */
504  	SCIP_RETCODE SCIPtreeLoadLP(
505  	   SCIP_TREE*            tree,               /**< branch and bound tree */
506  	   BMS_BLKMEM*           blkmem,             /**< block memory */
507  	   SCIP_SET*             set,                /**< global SCIP settings */
508  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
509  	   SCIP_EVENTFILTER*     eventfilter,        /**< global event filter */
510  	   SCIP_LP*              lp,                 /**< current LP data */
511  	   SCIP_Bool*            initroot            /**< pointer to store whether the root LP relaxation has to be initialized */
512  	   );
513  	
514  	/** loads LP state for fork/subroot of the focus node */
515  	SCIP_RETCODE SCIPtreeLoadLPState(
516  	   SCIP_TREE*            tree,               /**< branch and bound tree */
517  	   BMS_BLKMEM*           blkmem,             /**< block memory buffers */
518  	   SCIP_SET*             set,                /**< global SCIP settings */
519  	   SCIP_PROB*            prob,               /**< problem data */
520  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
521  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
522  	   SCIP_LP*              lp                  /**< current LP data */
523  	   );
524  	
525  	/** calculates the node selection priority for moving the given variable's LP value to the given target value;
526  	 *  this node selection priority can be given to the SCIPcreateChild() call
527  	 */
528  	SCIP_Real SCIPtreeCalcNodeselPriority(
529  	   SCIP_TREE*            tree,               /**< branch and bound tree */
530  	   SCIP_SET*             set,                /**< global SCIP settings */
531  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
532  	   SCIP_VAR*             var,                /**< variable, of which the branching factor should be applied, or NULL */
533  	   SCIP_BRANCHDIR        branchdir,          /**< type of branching that was performed: upwards, downwards, or fixed 
534  	                                              * fixed should only be used, when both bounds changed 
535  	                                              */
536  	   SCIP_Real             targetvalue         /**< new value of the variable in the child node */
537  	   );
538  	
539  	/** calculates an estimate for the objective of the best feasible solution contained in the subtree after applying the given 
540  	 *  branching; this estimate can be given to the SCIPcreateChild() call
541  	 */
542  	SCIP_Real SCIPtreeCalcChildEstimate(
543  	   SCIP_TREE*            tree,               /**< branch and bound tree */
544  	   SCIP_SET*             set,                /**< global SCIP settings */
545  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
546  	   SCIP_VAR*             var,                /**< variable, of which the branching factor should be applied, or NULL */
547  	   SCIP_Real             targetvalue         /**< new value of the variable in the child node */
548  	   );
549  	
550  	/** branches on a variable x
551  	 *  if x is a continuous variable, then two child nodes will be created
552  	 *  (x <= x', x >= x')
553  	 *  but if the bounds of x are such that their relative difference is smaller than epsilon,
554  	 *  the variable is fixed to val (if not SCIP_INVALID) or a well chosen alternative in the current node,
555  	 *  i.e., no children are created
556  	 *  if x is not a continuous variable, then:
557  	 *  if solution value x' is fractional, two child nodes will be created
558  	 *  (x <= floor(x'), x >= ceil(x')),
559  	 *  if solution value is integral, the x' is equal to lower or upper bound of the branching
560  	 *  variable and the bounds of x are finite, then two child nodes will be created
561  	 *  (x <= x", x >= x"+1 with x" = floor((lb + ub)/2)),
562  	 *  otherwise (up to) three child nodes will be created
563  	 *  (x <= x'-1, x == x', x >= x'+1)
564  	 *  if solution value is equal to one of the bounds and the other bound is infinite, only two child nodes
565  	 *  will be created (the third one would be infeasible anyway)
566  	 */
567  	SCIP_RETCODE SCIPtreeBranchVar(
568  	   SCIP_TREE*            tree,               /**< branch and bound tree */
569  	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
570  	   BMS_BLKMEM*           blkmem,             /**< block memory */
571  	   SCIP_SET*             set,                /**< global SCIP settings */
572  	   SCIP_STAT*            stat,               /**< problem statistics data */
573  	   SCIP_PROB*            transprob,          /**< transformed problem after presolve */
574  	   SCIP_PROB*            origprob,           /**< original problem */
575  	   SCIP_LP*              lp,                 /**< current LP data */
576  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
577  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
578  	   SCIP_VAR*             var,                /**< variable to branch on */
579  	   SCIP_Real             val,                /**< value to branch on or SCIP_INVALID for branching on current LP/pseudo solution. A branching value is required for branching on continuous variables */
580  	   SCIP_NODE**           downchild,          /**< pointer to return the left child with variable rounded down, or NULL */
581  	   SCIP_NODE**           eqchild,            /**< pointer to return the middle child with variable fixed, or NULL */
582  	   SCIP_NODE**           upchild             /**< pointer to return the right child with variable rounded up, or NULL */
583  	   );
584  	
585  	/** branches a variable x using the given domain hole; two child nodes will be created (x <= left, x >= right) */
586  	SCIP_RETCODE SCIPtreeBranchVarHole(
587  	   SCIP_TREE*            tree,               /**< branch and bound tree */
588  	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
589  	   BMS_BLKMEM*           blkmem,             /**< block memory */
590  	   SCIP_SET*             set,                /**< global SCIP settings */
591  	   SCIP_STAT*            stat,               /**< problem statistics data */
592  	   SCIP_PROB*            transprob,          /**< transformed problem after presolve */
593  	   SCIP_PROB*            origprob,           /**< original problem */
594  	   SCIP_LP*              lp,                 /**< current LP data */
595  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
596  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
597  	   SCIP_VAR*             var,                /**< variable to branch on */
598  	   SCIP_Real             left,               /**< left side of the domain hole */
599  	   SCIP_Real             right,              /**< right side of the domain hole */
600  	   SCIP_NODE**           downchild,          /**< pointer to return the left child with variable rounded down, or NULL */
601  	   SCIP_NODE**           upchild             /**< pointer to return the right child with variable rounded up, or NULL */
602  	   );
603  	
604  	/** n-ary branching on a variable x
605  	 * Branches on variable x such that up to n/2 children are created on each side of the usual branching value.
606  	 * The branching value is selected as in SCIPtreeBranchVar().
607  	 * If n is 2 or the variables local domain is too small for a branching into n pieces, SCIPtreeBranchVar() is called.
608  	 * The parameters minwidth and widthfactor determine the domain width of the branching variable in the child nodes.
609  	 * If n is odd, one child with domain width 'width' and having the branching value in the middle is created.
610  	 * Otherwise, two children with domain width 'width' and being left and right of the branching value are created.
611  	 * Next further nodes to the left and right are created, where width is multiplied by widthfactor with increasing distance from the first nodes.
612  	 * The initial width is calculated such that n/2 nodes are created to the left and to the right of the branching value.
613  	 * If this value is below minwidth, the initial width is set to minwidth, which may result in creating less than n nodes.
614  	 *
615  	 * Giving a large value for widthfactor results in creating children with small domain when close to the branching value
616  	 * and large domain when closer to the current variable bounds. That is, setting widthfactor to a very large value and n to 3
617  	 * results in a ternary branching where the branching variable is mostly fixed in the middle child.
618  	 * Setting widthfactor to 1.0 results in children where the branching variable always has the same domain width
619  	 * (except for one child if the branching value is not in the middle).
620  	 */
621  	SCIP_RETCODE SCIPtreeBranchVarNary(
622  	   SCIP_TREE*            tree,               /**< branch and bound tree */
623  	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
624  	   BMS_BLKMEM*           blkmem,             /**< block memory */
625  	   SCIP_SET*             set,                /**< global SCIP settings */
626  	   SCIP_STAT*            stat,               /**< problem statistics data */
627  	   SCIP_PROB*            transprob,          /**< transformed problem after presolve */
628  	   SCIP_PROB*            origprob,           /**< original problem */
629  	   SCIP_LP*              lp,                 /**< current LP data */
630  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
631  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
632  	   SCIP_VAR*             var,                /**< variable to branch on */
633  	   SCIP_Real             val,                /**< value to branch on or SCIP_INVALID for branching on current LP/pseudo solution.
634  	                                              *   A branching value is required for branching on continuous variables */
635  	   int                   n,                  /**< attempted number of children to be created, must be >= 2 */
636  	   SCIP_Real             minwidth,           /**< minimal domain width in children */
637  	   SCIP_Real             widthfactor,        /**< multiplier for children domain width with increasing distance from val, must be >= 1.0 */
638  	   int*                  nchildren           /**< buffer to store number of created children, or NULL */
639  	   );
640  	
641  	/** adds a diving bound change to the tree together with the information if this is a bound change
642  	 *  for the preferred direction or not
643  	 */
644  	SCIP_RETCODE SCIPtreeAddDiveBoundChange(
645  	   SCIP_TREE*            tree,               /**< branch and bound tree */
646  	   BMS_BLKMEM*           blkmem,             /**< block memory buffers */
647  	   SCIP_VAR*             var,                /**< variable to apply the bound change to */
648  	   SCIP_BRANCHDIR        dir,                /**< direction of the bound change */
649  	   SCIP_Real             value,              /**< value to adjust this variable bound to */
650  	   SCIP_Bool             preferred           /**< is this a bound change for the preferred child? */
651  	   );
652  	
653  	/** get the dive bound change data for the preferred or the alternative direction */
654  	void SCIPtreeGetDiveBoundChangeData(
655  	   SCIP_TREE*            tree,               /**< branch and bound tree */
656  	   SCIP_VAR***           variables,          /**< pointer to store variables for the specified direction */
657  	   SCIP_BRANCHDIR**      directions,         /**< pointer to store the branching directions */
658  	   SCIP_Real**           values,             /**< pointer to store bound change values */
659  	   int*                  ndivebdchgs,        /**< pointer to store the number of dive bound changes */
660  	   SCIP_Bool             preferred           /**< should the dive bound changes for the preferred child be output? */
661  	   );
662  	
663  	/** clear the tree dive bound change data structure */
664  	void SCIPtreeClearDiveBoundChanges(
665  	   SCIP_TREE*            tree                /**< branch and bound tree */
666  	   );
667  	
668  	/** switches to probing mode and creates a probing root */
669  	SCIP_RETCODE SCIPtreeStartProbing(
670  	   SCIP_TREE*            tree,               /**< branch and bound tree */
671  	   BMS_BLKMEM*           blkmem,             /**< block memory */
672  	   SCIP_SET*             set,                /**< global SCIP settings */
673  	   SCIP_LP*              lp,                 /**< current LP data */
674  	   SCIP_RELAXATION*      relaxation,         /**< global relaxation data */
675  	   SCIP_PROB*            transprob,          /**< transformed problem after presolve */
676  	   SCIP_Bool             strongbranching     /**< is the probing mode used for strongbranching? */
677  	   );
678  	
679  	/** creates a new probing child node in the probing path */
680  	SCIP_RETCODE SCIPtreeCreateProbingNode(
681  	   SCIP_TREE*            tree,               /**< branch and bound tree */
682  	   BMS_BLKMEM*           blkmem,             /**< block memory */
683  	   SCIP_SET*             set,                /**< global SCIP settings */
684  	   SCIP_LP*              lp                  /**< current LP data */
685  	   );
686  	
687  	/** sets the LP state for the current probing node
688  	 *
689  	 *  @note state and norms are stored at the node and later released by SCIP; therefore, the pointers are set
690  	 *        to NULL by the method
691  	 *
692  	 *  @note the pointers to state and norms must not be NULL; however, they may point to a NULL pointer if the
693  	 *        respective information should not be set
694  	 */
695  	SCIP_RETCODE SCIPtreeSetProbingLPState(
696  	   SCIP_TREE*            tree,               /**< branch and bound tree */
697  	   BMS_BLKMEM*           blkmem,             /**< block memory */
698  	   SCIP_LP*              lp,                 /**< current LP data */
699  	   SCIP_LPISTATE**       lpistate,           /**< pointer to LP state information (like basis information) */
700  	   SCIP_LPINORMS**       lpinorms,           /**< pointer to LP pricing norms information */
701  	   SCIP_Bool             primalfeas,         /**< primal feasibility when LP state information was stored */
702  	   SCIP_Bool             dualfeas            /**< dual feasibility when LP state information was stored */
703  	   );
704  	
705  	/** loads the LP state for the current probing node */
706  	SCIP_RETCODE SCIPtreeLoadProbingLPState(
707  	   SCIP_TREE*            tree,               /**< branch and bound tree */
708  	   BMS_BLKMEM*           blkmem,             /**< block memory buffers */
709  	   SCIP_SET*             set,                /**< global SCIP settings */
710  	   SCIP_PROB*            prob,               /**< problem data */
711  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
712  	   SCIP_LP*              lp                  /**< current LP data */
713  	   );
714  	
715  	/** marks the probing node to have a solved LP relaxation */
716  	SCIP_RETCODE SCIPtreeMarkProbingNodeHasLP(
717  	   SCIP_TREE*            tree,               /**< branch and bound tree */
718  	   BMS_BLKMEM*           blkmem,             /**< block memory */
719  	   SCIP_LP*              lp                  /**< current LP data */
720  	   );
721  	
722  	/** undoes all changes to the problem applied in probing up to the given probing depth;
723  	 *  the changes of the probing node of the given probing depth are the last ones that remain active;
724  	 *  changes that were applied before calling SCIPtreeCreateProbingNode() cannot be undone
725  	 */
726  	SCIP_RETCODE SCIPtreeBacktrackProbing(
727  	   SCIP_TREE*            tree,               /**< branch and bound tree */
728  	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
729  	   BMS_BLKMEM*           blkmem,             /**< block memory buffers */
730  	   SCIP_SET*             set,                /**< global SCIP settings */
731  	   SCIP_STAT*            stat,               /**< problem statistics */
732  	   SCIP_PROB*            transprob,          /**< transformed problem */
733  	   SCIP_PROB*            origprob,           /**< original problem */
734  	   SCIP_LP*              lp,                 /**< current LP data */
735  	   SCIP_PRIMAL*          primal,             /**< primal data structure */
736  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
737  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
738  	   SCIP_EVENTFILTER*     eventfilter,        /**< global event filter */
739  	   SCIP_CLIQUETABLE*     cliquetable,        /**< clique table data structure */
740  	   int                   probingdepth        /**< probing depth of the node in the probing path that should be reactivated */
741  	   );
742  	
743  	/** switches back from probing to normal operation mode, frees all nodes on the probing path, restores bounds of all
744  	 *  variables and restores active constraints arrays of focus node
745  	 */
746  	SCIP_RETCODE SCIPtreeEndProbing(
747  	   SCIP_TREE*            tree,               /**< branch and bound tree */
748  	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
749  	   BMS_BLKMEM*           blkmem,             /**< block memory buffers */
750  	   SCIP_SET*             set,                /**< global SCIP settings */
751  	   SCIP_MESSAGEHDLR*     messagehdlr,        /**< message handler */
752  	   SCIP_STAT*            stat,               /**< problem statistics */
753  	   SCIP_PROB*            transprob,          /**< transformed problem after presolve */
754  	   SCIP_PROB*            origprob,           /**< original problem */
755  	   SCIP_LP*              lp,                 /**< current LP data */
756  	   SCIP_RELAXATION*      relaxation,         /**< global relaxation data */
757  	   SCIP_PRIMAL*          primal,             /**< primal LP data */
758  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
759  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
760  	   SCIP_EVENTFILTER*     eventfilter,        /**< global event filter */
761  	   SCIP_CLIQUETABLE*     cliquetable         /**< clique table data structure */
762  	   );
763  	
764  	/** stores relaxation solution before diving or probing */
765  	SCIP_RETCODE SCIPtreeStoreRelaxSol(
766  	   SCIP_TREE*            tree,               /**< branch and bound tree */
767  	   SCIP_SET*             set,                /**< global SCIP settings */
768  	   SCIP_RELAXATION*      relaxation,         /**< global relaxation data */
769  	   SCIP_PROB*            transprob           /**< transformed problem after presolve */
770  	   );
771  	
772  	/** restores relaxation solution after diving or probing */
773  	SCIP_RETCODE SCIPtreeRestoreRelaxSol(
774  	   SCIP_TREE*            tree,               /**< branch and bound tree */
775  	   SCIP_SET*             set,                /**< global SCIP settings */
776  	   SCIP_RELAXATION*      relaxation,         /**< global relaxation data */
777  	   SCIP_PROB*            transprob           /**< transformed problem after presolve */
778  	   );
779  	
780  	
781  	/** gets number of children of the focus node  */
782  	int SCIPtreeGetNChildren(
783  	   SCIP_TREE*            tree                /**< branch and bound tree */
784  	   );
785  	
786  	/** gets number of siblings of the focus node  */
787  	int SCIPtreeGetNSiblings(
788  	   SCIP_TREE*            tree                /**< branch and bound tree */
789  	   );
790  	
791  	/** gets number of leaves in the tree (excluding children and siblings of focus nodes) */
792  	int SCIPtreeGetNLeaves(
793  	   SCIP_TREE*            tree                /**< branch and bound tree */
794  	   );
795  	
796  	/** gets number of open nodes in the tree (children + siblings + leaves) */
797  	int SCIPtreeGetNNodes(
798  	   SCIP_TREE*            tree                /**< branch and bound tree */
799  	   );
800  	
801  	/** returns whether the active path goes completely down to the focus node */
802  	SCIP_Bool SCIPtreeIsPathComplete(
803  	   SCIP_TREE*            tree                /**< branch and bound tree */
804  	   );
805  	
806  	/** returns whether the current node is a temporary probing node */
807  	SCIP_Bool SCIPtreeProbing(
808  	   SCIP_TREE*            tree                /**< branch and bound tree */
809  	   );
810  	
811  	/** returns the temporary probing root node, or NULL if the we are not in probing mode */
812  	SCIP_NODE* SCIPtreeGetProbingRoot(
813  	   SCIP_TREE*            tree                /**< branch and bound tree */
814  	   );
815  	
816  	/** returns the current probing depth, i.e. the number of probing sub nodes existing in the probing path */
817  	int SCIPtreeGetProbingDepth(
818  	   SCIP_TREE*            tree                /**< branch and bound tree */
819  	   );
820  	
821  	/** gets focus node of the tree */
822  	SCIP_NODE* SCIPtreeGetFocusNode(
823  	   SCIP_TREE*            tree                /**< branch and bound tree */
824  	   );
825  	
826  	/** gets depth of focus node in the tree, or -1 if no focus node exists */
827  	int SCIPtreeGetFocusDepth(
828  	   SCIP_TREE*            tree                /**< branch and bound tree */
829  	   );
830  	
831  	/** returns, whether the LP was or is to be solved in the focus node */
832  	SCIP_Bool SCIPtreeHasFocusNodeLP(
833  	   SCIP_TREE*            tree                /**< branch and bound tree */
834  	   );
835  	
836  	/** sets mark to solve or to ignore the LP while processing the focus node */
837  	void SCIPtreeSetFocusNodeLP(
838  	   SCIP_TREE*            tree,               /**< branch and bound tree */
839  	   SCIP_Bool             solvelp             /**< should the LP be solved in focus node? */
840  	   );
841  	
842  	/** returns whether the LP of the focus node is already constructed */
843  	SCIP_Bool SCIPtreeIsFocusNodeLPConstructed(
844  	   SCIP_TREE*            tree                /**< branch and bound tree */
845  	   );
846  	
847  	/** returns whether the focus node is already solved and only propagated again */
848  	SCIP_Bool SCIPtreeInRepropagation(
849  	   SCIP_TREE*            tree                /**< branch and bound tree */
850  	   );
851  	
852  	/** gets current node of the tree, i.e. the last node in the active path, or NULL if no current node exists */
853  	SCIP_NODE* SCIPtreeGetCurrentNode(
854  	   SCIP_TREE*            tree                /**< branch and bound tree */
855  	   );
856  	
857  	/** gets depth of current node in the tree, i.e. the length of the active path minus 1, or -1 if no current node exists */
858  	int SCIPtreeGetCurrentDepth(
859  	   SCIP_TREE*            tree                /**< branch and bound tree */
860  	   );
861  	
862  	/** returns, whether the LP was or is to be solved in the current node */
863  	SCIP_Bool SCIPtreeHasCurrentNodeLP(
864  	   SCIP_TREE*            tree                /**< branch and bound tree */
865  	   );
866  	
867  	/** returns the depth of the effective root node (i.e. the first depth level of a node with at least two children) */
868  	int SCIPtreeGetEffectiveRootDepth(
869  	   SCIP_TREE*            tree                /**< branch and bound tree */
870  	   );
871  	
872  	/** gets the root node of the tree */
873  	SCIP_NODE* SCIPtreeGetRootNode(
874  	   SCIP_TREE*            tree                /**< branch and bound tree */
875  	   );
876  	
877  	/** returns whether we are in probing and the objective value of at least one column was changed */
878  	SCIP_Bool SCIPtreeProbingObjChanged(
879  	   SCIP_TREE*            tree                /**< branch and bound tree */
880  	   );
881  	
882  	/** marks the current probing node to have a changed objective function */
883  	void SCIPtreeMarkProbingObjChanged(
884  	   SCIP_TREE*            tree                /**< branch and bound tree */
885  	   );
886  	
887  	#ifdef NDEBUG
888  	
889  	/* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
890  	 * speed up the algorithms.
891  	 */
892  	
893  	#define SCIPtreeGetNLeaves(tree)        SCIPnodepqLen((tree)->leaves)
894  	#define SCIPtreeGetNChildren(tree)      ((tree)->nchildren)
895  	#define SCIPtreeGetNSiblings(tree)      ((tree)->nsiblings)
896  	#define SCIPtreeGetNNodes(tree)         \
897  	   (SCIPtreeGetNChildren(tree) + SCIPtreeGetNSiblings(tree) + SCIPtreeGetNLeaves(tree))
898  	#define SCIPtreeIsPathComplete(tree)    ((tree)->focusnode == NULL || (tree)->focusnode->depth < (tree)->pathlen)
899  	#define SCIPtreeProbing(tree)           ((tree)->probingroot != NULL)
900  	#define SCIPtreeGetProbingRoot(tree)    (tree)->probingroot
901  	#define SCIPtreeGetProbingDepth(tree)   (SCIPtreeGetCurrentDepth(tree) - SCIPnodeGetDepth((tree)->probingroot))
902  	#define SCIPtreeGetFocusNode(tree)      (tree)->focusnode
903  	#define SCIPtreeGetFocusDepth(tree)     ((tree)->focusnode != NULL ? (int)(tree)->focusnode->depth : -1)
904  	#define SCIPtreeHasFocusNodeLP(tree)    (tree)->focusnodehaslp
905  	#define SCIPtreeSetFocusNodeLP(tree,solvelp)  ((tree)->focusnodehaslp = solvelp)
906  	#define SCIPtreeIsFocusNodeLPConstructed(tree) (tree)->focuslpconstructed
907  	#define SCIPtreeInRepropagation(tree)   ((tree)->focusnode != NULL \
908  	      && SCIPnodeGetType((tree)->focusnode) == SCIP_NODETYPE_REFOCUSNODE)
909  	#define SCIPtreeGetCurrentNode(tree)    ((tree)->pathlen > 0 ? (tree)->path[(tree)->pathlen-1] : NULL)
910  	#define SCIPtreeGetCurrentDepth(tree)   ((tree)->pathlen-1)
911  	#define SCIPtreeHasCurrentNodeLP(tree)  (SCIPtreeProbing(tree) ? (tree)->probingnodehaslp : SCIPtreeHasFocusNodeLP(tree))
912  	#define SCIPtreeGetEffectiveRootDepth(tree) ((tree)->effectiverootdepth)
913  	#define SCIPtreeGetRootNode(tree)       ((tree)->root)
914  	#define SCIPtreeProbingObjChanged(tree) ((tree)->probingobjchanged)
915  	#define SCIPtreeMarkProbingObjChanged(tree) ((tree)->probingobjchanged = TRUE)
916  	
917  	#endif
918  	
919  	
920  	/** gets the best child of the focus node w.r.t. the node selection priority assigned by the branching rule */
921  	SCIP_NODE* SCIPtreeGetPrioChild(
922  	   SCIP_TREE*            tree                /**< branch and bound tree */
923  	   );
924  	
925  	/** gets the best sibling of the focus node w.r.t. the node selection priority assigned by the branching rule */
926  	SCIP_NODE* SCIPtreeGetPrioSibling(
927  	   SCIP_TREE*            tree                /**< branch and bound tree */
928  	   );
929  	
930  	/** gets the best child of the focus node w.r.t. the node selection strategy */
931  	SCIP_NODE* SCIPtreeGetBestChild(
932  	   SCIP_TREE*            tree,               /**< branch and bound tree */
933  	   SCIP_SET*             set                 /**< global SCIP settings */
934  	   );
935  	
936  	/** gets the best sibling of the focus node w.r.t. the node selection strategy */
937  	SCIP_NODE* SCIPtreeGetBestSibling(
938  	   SCIP_TREE*            tree,               /**< branch and bound tree */
939  	   SCIP_SET*             set                 /**< global SCIP settings */
940  	   );
941  	
942  	/** gets the best leaf from the node queue w.r.t. the node selection strategy */
943  	SCIP_NODE* SCIPtreeGetBestLeaf(
944  	   SCIP_TREE*            tree                /**< branch and bound tree */
945  	   );
946  	
947  	/** gets the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy */
948  	SCIP_NODE* SCIPtreeGetBestNode(
949  	   SCIP_TREE*            tree,               /**< branch and bound tree */
950  	   SCIP_SET*             set                 /**< global SCIP settings */
951  	   );
952  	
953  	/** gets the minimal lower bound of all nodes in the tree */
954  	SCIP_Real SCIPtreeGetLowerbound(
955  	   SCIP_TREE*            tree,               /**< branch and bound tree */
956  	   SCIP_SET*             set                 /**< global SCIP settings */
957  	   );
958  	
959  	/** gets the node with minimal lower bound of all nodes in the tree (child, sibling, or leaf) */
960  	SCIP_NODE* SCIPtreeGetLowerboundNode(
961  	   SCIP_TREE*            tree,               /**< branch and bound tree */
962  	   SCIP_SET*             set                 /**< global SCIP settings */
963  	   );
964  	
965  	/** gets the average lower bound of all nodes in the tree */
966  	SCIP_Real SCIPtreeGetAvgLowerbound(
967  	   SCIP_TREE*            tree,               /**< branch and bound tree */
968  	   SCIP_Real             cutoffbound         /**< global cutoff bound */
969  	   );
970  	
971  	/** query if focus node was already branched on */
972  	SCIP_Bool SCIPtreeWasNodeLastBranchParent(
973  	   SCIP_TREE*            tree,               /**< branch and bound tree */
974  	   SCIP_NODE*            node                /**< tree node, or NULL to check focus node */
975  	   );
976  	
977  	#ifdef __cplusplus
978  	}
979  	#endif
980  	
981  	#endif
982