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.h
26   	 * @ingroup PUBLICCOREAPI
27   	 * @brief  public methods for the branch-and-bound tree
28   	 * @author Tobias Achterberg
29   	 * @author Timo Berthold
30   	 * @author Thorsten Koch
31   	 * @author Alexander Martin
32   	 * @author Marc Pfetsch
33   	 * @author Kati Wolter
34   	 * @author Gregor Hendel
35   	 * @author Leona Gottwald
36   	 */
37   	
38   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
39   	
40   	#ifndef __SCIP_SCIP_TREE_H__
41   	#define __SCIP_SCIP_TREE_H__
42   	
43   	
44   	#include "scip/def.h"
45   	#include "scip/type_retcode.h"
46   	#include "scip/type_scip.h"
47   	#include "scip/type_tree.h"
48   	
49   	#ifdef __cplusplus
50   	extern "C" {
51   	#endif
52   	
53   	/**@addtogroup PublicTreeMethods
54   	 *
55   	 * @{
56   	 */
57   	
58   	/** gets focus node in the tree
59   	 *
60   	 *  if we are in probing/diving mode this method returns the node in the tree where the probing/diving mode was started.
61   	 *
62   	 *  @return the current node of the search tree
63   	 *
64   	 *  @pre This method can be called if @p scip is in one of the following stages:
65   	 *       - \ref SCIP_STAGE_INITPRESOLVE
66   	 *       - \ref SCIP_STAGE_PRESOLVING
67   	 *       - \ref SCIP_STAGE_EXITPRESOLVE
68   	 *       - \ref SCIP_STAGE_SOLVING
69   	 */
70   	SCIP_EXPORT
71   	SCIP_NODE* SCIPgetFocusNode(
72   	   SCIP*                 scip                /**< SCIP data structure */
73   	   );
74   	
75   	/** gets current node in the tree
76   	 *
77   	 *  @return the current node of the search tree
78   	 *
79   	 *  @pre This method can be called if @p scip is in one of the following stages:
80   	 *       - \ref SCIP_STAGE_INITPRESOLVE
81   	 *       - \ref SCIP_STAGE_PRESOLVING
82   	 *       - \ref SCIP_STAGE_EXITPRESOLVE
83   	 *       - \ref SCIP_STAGE_SOLVING
84   	 */
85   	SCIP_EXPORT
86   	SCIP_NODE* SCIPgetCurrentNode(
87   	   SCIP*                 scip                /**< SCIP data structure */
88   	   );
89   	
90   	/** gets depth of current node, or -1 if no current node exists; in probing, the current node is the last probing node,
91   	 *  such that the depth includes the probing path
92   	 *
93   	 *  @return the depth of current node, or -1 if no current node exists; in probing, the current node is the last probing node,
94   	 *  such that the depth includes the probing path
95   	 *
96   	 *  @pre This method can be called if SCIP is in one of the following stages:
97   	 *       - \ref SCIP_STAGE_TRANSFORMED
98   	 *       - \ref SCIP_STAGE_INITPRESOLVE
99   	 *       - \ref SCIP_STAGE_PRESOLVING
100  	 *       - \ref SCIP_STAGE_EXITPRESOLVE
101  	 *       - \ref SCIP_STAGE_PRESOLVED
102  	 *       - \ref SCIP_STAGE_INITSOLVE
103  	 *       - \ref SCIP_STAGE_SOLVING
104  	 *       - \ref SCIP_STAGE_SOLVED
105  	 *       - \ref SCIP_STAGE_EXITSOLVE
106  	 */
107  	SCIP_EXPORT
108  	int SCIPgetDepth(
109  	   SCIP*                 scip                /**< SCIP data structure */
110  	   );
111  	
112  	/** gets depth of the focus node, or -1 if no focus node exists; the focus node is the currently processed node in the
113  	 *  branching tree, excluding the nodes of the probing path
114  	 *
115  	 *  @return the depth of the focus node, or -1 if no focus node exists; the focus node is the currently processed node in the
116  	 *  branching tree, excluding the nodes of the probing path
117  	 *
118  	 *  @pre This method can be called if SCIP is in one of the following stages:
119  	 *       - \ref SCIP_STAGE_TRANSFORMED
120  	 *       - \ref SCIP_STAGE_INITPRESOLVE
121  	 *       - \ref SCIP_STAGE_PRESOLVING
122  	 *       - \ref SCIP_STAGE_EXITPRESOLVE
123  	 *       - \ref SCIP_STAGE_PRESOLVED
124  	 *       - \ref SCIP_STAGE_INITSOLVE
125  	 *       - \ref SCIP_STAGE_SOLVING
126  	 *       - \ref SCIP_STAGE_SOLVED
127  	 *       - \ref SCIP_STAGE_EXITSOLVE
128  	 */
129  	SCIP_EXPORT
130  	int SCIPgetFocusDepth(
131  	   SCIP*                 scip                /**< SCIP data structure */
132  	   );
133  	
134  	/** gets current plunging depth (successive times, a child was selected as next node)
135  	 *
136  	 *  @return the current plunging depth (successive times, a child was selected as next node)
137  	 *
138  	 *  @pre This method can be called if SCIP is in one of the following stages:
139  	 *       - \ref SCIP_STAGE_PRESOLVED
140  	 *       - \ref SCIP_STAGE_SOLVING
141  	 */
142  	SCIP_EXPORT
143  	int SCIPgetPlungeDepth(
144  	   SCIP*                 scip                /**< SCIP data structure */
145  	   );
146  	
147  	/** gets the root node of the tree
148  	 *
149  	 *  @return the root node of the search tree
150  	 *
151  	 *  @pre This method can be called if @p scip is in one of the following stages:
152  	 *       - \ref SCIP_STAGE_INITPRESOLVE
153  	 *       - \ref SCIP_STAGE_PRESOLVING
154  	 *       - \ref SCIP_STAGE_EXITPRESOLVE
155  	 *       - \ref SCIP_STAGE_SOLVING
156  	 */
157  	SCIP_EXPORT
158  	SCIP_NODE* SCIPgetRootNode(
159  	   SCIP*                 scip                /**< SCIP data structure */
160  	   );
161  	
162  	/** gets the effective root depth, i.e., the depth of the deepest node which is part of all paths from the root node
163  	 *  to the unprocessed nodes.
164  	 *
165  	 *  @return effective root depth
166  	 *
167  	 *  @pre This method can be called if @p scip is in one of the following stages:
168  	 *       - \ref SCIP_STAGE_SOLVING
169  	 */
170  	SCIP_EXPORT
171  	int SCIPgetEffectiveRootDepth(
172  	   SCIP*                 scip                /**< SCIP data structure */
173  	   );
174  	
175  	/** returns whether the current node is already solved and only propagated again
176  	 *
177  	 *  @return TRUE is returned if \SCIP performance repropagation, otherwise FALSE.
178  	 *
179  	 *  @pre This method can be called if @p scip is in one of the following stages:
180  	 *       - \ref SCIP_STAGE_INITPRESOLVE
181  	 *       - \ref SCIP_STAGE_PRESOLVING
182  	 *       - \ref SCIP_STAGE_EXITPRESOLVE
183  	 *       - \ref SCIP_STAGE_SOLVING
184  	 */
185  	SCIP_EXPORT
186  	SCIP_Bool SCIPinRepropagation(
187  	   SCIP*                 scip                /**< SCIP data structure */
188  	   );
189  	
190  	/** gets children of focus node along with the number of children
191  	 *
192  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
193  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
194  	 *
195  	 *  @pre This method can be called if @p scip is in one of the following stages:
196  	 *       - \ref SCIP_STAGE_SOLVING
197  	 */
198  	SCIP_EXPORT
199  	SCIP_RETCODE SCIPgetChildren(
200  	   SCIP*                 scip,               /**< SCIP data structure */
201  	   SCIP_NODE***          children,           /**< pointer to store children array, or NULL if not needed */
202  	   int*                  nchildren           /**< pointer to store number of children, or NULL if not needed */
203  	   );
204  	
205  	/** gets number of children of focus node
206  	 *
207  	 *  @return number of children of the focus node
208  	 *
209  	 *  @pre This method can be called if @p scip is in one of the following stages:
210  	 *       - \ref SCIP_STAGE_SOLVING
211  	 */
212  	SCIP_EXPORT
213  	int SCIPgetNChildren(
214  	   SCIP*                 scip                /**< SCIP data structure */
215  	   );
216  	
217  	/** gets siblings of focus node along with the number of siblings
218  	 *
219  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
220  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
221  	 *
222  	 *  @pre This method can be called if @p scip is in one of the following stages:
223  	 *       - \ref SCIP_STAGE_SOLVING
224  	 */
225  	SCIP_EXPORT
226  	SCIP_RETCODE SCIPgetSiblings(
227  	   SCIP*                 scip,               /**< SCIP data structure */
228  	   SCIP_NODE***          siblings,           /**< pointer to store siblings array, or NULL if not needed */
229  	   int*                  nsiblings           /**< pointer to store number of siblings, or NULL if not needed */
230  	   );
231  	
232  	/** gets number of siblings of focus node
233  	 *
234  	 *  @return the number of siblings of focus node
235  	 *
236  	 *  @pre This method can be called if @p scip is in one of the following stages:
237  	 *       - \ref SCIP_STAGE_SOLVING
238  	 */
239  	SCIP_EXPORT
240  	int SCIPgetNSiblings(
241  	   SCIP*                 scip                /**< SCIP data structure */
242  	   );
243  	
244  	/** gets leaves of the tree along with the number of leaves
245  	 *
246  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
247  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
248  	 *
249  	 *  @pre This method can be called if @p scip is in one of the following stages:
250  	 *       - \ref SCIP_STAGE_SOLVING
251  	 */
252  	SCIP_EXPORT
253  	SCIP_RETCODE SCIPgetLeaves(
254  	   SCIP*                 scip,               /**< SCIP data structure */
255  	   SCIP_NODE***          leaves,             /**< pointer to store leaves array, or NULL if not needed */
256  	   int*                  nleaves             /**< pointer to store number of leaves, or NULL if not needed */
257  	   );
258  	
259  	/** gets number of leaves in the tree
260  	 *
261  	 *  @return the number of leaves in the tree
262  	 *
263  	 *  @pre This method can be called if @p scip is in one of the following stages:
264  	 *       - \ref SCIP_STAGE_SOLVING
265  	 */
266  	SCIP_EXPORT
267  	int SCIPgetNLeaves(
268  	   SCIP*                 scip                /**< SCIP data structure */
269  	   );
270  	
271  	/** gets number of nodes left in the tree (children + siblings + leaves)
272  	 *
273  	 *  @return the number of nodes left in the tree (children + siblings + leaves)
274  	 *
275  	 *  @pre This method can be called if SCIP is in one of the following stages:
276  	 *       - \ref SCIP_STAGE_PRESOLVED
277  	 *       - \ref SCIP_STAGE_SOLVING
278  	 *       - \ref SCIP_STAGE_SOLVED
279  	 */
280  	SCIP_EXPORT
281  	int SCIPgetNNodesLeft(
282  	   SCIP*                 scip                /**< SCIP data structure */
283  	   );
284  	
285  	/** gets the best child of the focus node w.r.t. the node selection priority assigned by the branching rule
286  	 *
287  	 *  @return the best child of the focus node w.r.t. the node selection priority assigned by the branching rule
288  	 *
289  	 *  @pre This method can be called if @p scip is in one of the following stages:
290  	 *       - \ref SCIP_STAGE_SOLVING
291  	 */
292  	SCIP_EXPORT
293  	SCIP_NODE* SCIPgetPrioChild(
294  	   SCIP*                 scip                /**< SCIP data structure */
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_EXPORT
305  	SCIP_NODE* SCIPgetPrioSibling(
306  	   SCIP*                 scip                /**< SCIP data structure */
307  	   );
308  	
309  	/** gets the best child of the focus node w.r.t. the node selection strategy
310  	 *
311  	 *  @return the best child of the focus node w.r.t. the node selection strategy
312  	 *
313  	 *  @pre This method can be called if @p scip is in one of the following stages:
314  	 *       - \ref SCIP_STAGE_SOLVING
315  	 */
316  	SCIP_EXPORT
317  	SCIP_NODE* SCIPgetBestChild(
318  	   SCIP*                 scip                /**< SCIP data structure */
319  	   );
320  	
321  	/** gets the best sibling of the focus node w.r.t. the node selection strategy
322  	 *
323  	 *  @return the best sibling of the focus node w.r.t. the node selection strategy
324  	 *
325  	 *  @pre This method can be called if @p scip is in one of the following stages:
326  	 *       - \ref SCIP_STAGE_SOLVING
327  	 */
328  	SCIP_EXPORT
329  	SCIP_NODE* SCIPgetBestSibling(
330  	   SCIP*                 scip                /**< SCIP data structure */
331  	   );
332  	
333  	/** gets the best leaf from the node queue w.r.t. the node selection strategy
334  	 *
335  	 *  @return the best leaf from the node queue w.r.t. the node selection strategy
336  	 *
337  	 *  @pre This method can be called if @p scip is in one of the following stages:
338  	 *       - \ref SCIP_STAGE_SOLVING
339  	 */
340  	SCIP_EXPORT
341  	SCIP_NODE* SCIPgetBestLeaf(
342  	   SCIP*                 scip                /**< SCIP data structure */
343  	   );
344  	
345  	/** gets the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy
346  	 *
347  	 *  @return the best node from the tree (child, sibling, or leaf) 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_EXPORT
353  	SCIP_NODE* SCIPgetBestNode(
354  	   SCIP*                 scip                /**< SCIP data structure */
355  	   );
356  	
357  	/** gets the node with smallest lower bound from the tree (child, sibling, or leaf)
358  	 *
359  	 *  @return the node with smallest lower bound from the tree (child, sibling, or leaf)
360  	 *
361  	 *  @pre This method can be called if @p scip is in one of the following stages:
362  	 *       - \ref SCIP_STAGE_SOLVING
363  	 */
364  	SCIP_EXPORT
365  	SCIP_NODE* SCIPgetBestboundNode(
366  	   SCIP*                 scip                /**< SCIP data structure */
367  	   );
368  	
369  	/** access to all data of open nodes (leaves, children, and siblings)
370  	 *
371  	 *  @pre This method can be called if @p scip is in one of the following stages:
372  	 *       - \ref SCIP_STAGE_SOLVING
373  	 */
374  	SCIP_EXPORT
375  	SCIP_RETCODE SCIPgetOpenNodesData(
376  	   SCIP*                 scip,               /**< SCIP data structure */
377  	   SCIP_NODE***          leaves,             /**< pointer to store the leaves, or NULL if not needed */
378  	   SCIP_NODE***          children,           /**< pointer to store the children, or NULL if not needed */
379  	   SCIP_NODE***          siblings,           /**< pointer to store the siblings, or NULL if not needed */
380  	   int*                  nleaves,            /**< pointer to store the number of leaves, or NULL */
381  	   int*                  nchildren,          /**< pointer to store the number of children, or NULL */
382  	   int*                  nsiblings           /**< pointer to store the number of siblings, or NULL */
383  	   );
384  	
385  	/** marks node and whole sub tree to be cut off from branch and bound tree
386  	 *
387  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
388  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
389  	 *
390  	 *  @pre This method can be called if @p scip is in one of the following stages:
391  	 *       - \ref SCIP_STAGE_SOLVING
392  	 */
393  	SCIP_EXPORT
394  	SCIP_RETCODE SCIPcutoffNode(
395  	   SCIP*                 scip,               /**< SCIP data structure */
396  	   SCIP_NODE*            node                /**< node that should be cut off */
397  	   );
398  	
399  	/** removes all nodes from branch and bound tree that were marked to be cut off via SCIPcutoffNode()
400  	 *
401  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
402  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
403  	 *
404  	 *  @pre This method can be called if @p scip is in one of the following stages:
405  	 *       - \ref SCIP_STAGE_SOLVING
406  	 *
407  	 *  @note In diving mode, the removal of nodes is delayed until diving ends.
408  	 */
409  	SCIP_EXPORT
410  	SCIP_RETCODE SCIPpruneTree(
411  	   SCIP*                 scip                /**< SCIP data structure */
412  	   );
413  	
414  	/** marks the given node to be propagated again the next time a node of its subtree is processed
415  	 *
416  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
417  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
418  	 *
419  	 *  @pre This method can be called if @p scip is in one of the following stages:
420  	 *       - \ref SCIP_STAGE_SOLVING
421  	 */
422  	SCIP_EXPORT
423  	SCIP_RETCODE SCIPrepropagateNode(
424  	   SCIP*                 scip,               /**< SCIP data structure */
425  	   SCIP_NODE*            node                /**< node that should be propagated again */
426  	   );
427  	
428  	/** returns depth of first node in active path that is marked being cutoff
429  	 *
430  	 *  @return depth of first node in active path that is marked being cutoff
431  	 *
432  	 *  @pre This method can be called if @p scip is in one of the following stages:
433  	 *       - \ref SCIP_STAGE_SOLVING
434  	 */
435  	SCIP_EXPORT
436  	int SCIPgetCutoffdepth(
437  	   SCIP*                 scip                /**< SCIP data structure */
438  	   );
439  	
440  	/** returns depth of first node in active path that has to be propagated again
441  	 *
442  	 *  @return depth of first node in active path that has to be propagated again
443  	 *
444  	 *  @pre This method can be called if @p scip is in one of the following stages:
445  	 *       - \ref SCIP_STAGE_SOLVING
446  	 */
447  	SCIP_EXPORT
448  	int SCIPgetRepropdepth(
449  	   SCIP*                 scip                /**< SCIP data structure */
450  	   );
451  	
452  	/** prints all branching decisions on variables from the root to the given node
453  	 *
454  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
455  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
456  	 *
457  	 *  @pre This method can be called if @p scip is in one of the following stages:
458  	 *       - \ref SCIP_STAGE_SOLVING
459  	 */
460  	SCIP_EXPORT
461  	SCIP_RETCODE SCIPprintNodeRootPath(
462  	   SCIP*                 scip,               /**< SCIP data structure */
463  	   SCIP_NODE*            node,               /**< node data */
464  	   FILE*                 file                /**< output file (or NULL for standard output) */
465  	   );
466  	
467  	/** sets whether the LP should be solved at the focus node
468  	 *
469  	 *  @note In order to have an effect, this method needs to be called after a node is focused but before the LP is
470  	 *        solved.
471  	 *
472  	 *  @pre This method can be called if @p scip is in one of the following stages:
473  	 *       - \ref SCIP_STAGE_SOLVING
474  	 */
475  	SCIP_EXPORT
476  	void SCIPsetFocusnodeLP(
477  	   SCIP*                 scip,               /**< SCIP data structure */
478  	   SCIP_Bool             solvelp             /**< should the LP be solved? */
479  	   );
480  	
481  	
482  	/** query if node was the last parent of a branching of the tree
483  	 *
484  	 *  @return TRUE if node was the last parent of a branching of the tree
485  	 *
486  	 *  @pre This method can be called if SCIP is in one of the following stages:
487  	 *       - \ref SCIP_STAGE_PRESOLVED
488  	 *       - \ref SCIP_STAGE_SOLVING
489  	 *       - \ref SCIP_STAGE_SOLVED
490  	 */
491  	SCIP_EXPORT
492  	SCIP_Bool SCIPwasNodeLastBranchParent(
493  	   SCIP*                 scip,               /**< SCIP data structure */
494  	   SCIP_NODE*            node                /**< tree node, or NULL to check focus node */
495  	   );
496  	
497  	/**@} */
498  	
499  	#ifdef __cplusplus
500  	}
501  	#endif
502  	
503  	#endif
504