Scippy

SCIP

Solving Constraint Integer Programs

scip_tree.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file scip_tree.h
17  * @ingroup PUBLICCOREAPI
18  * @brief public methods for the branch-and-bound tree
19  * @author Tobias Achterberg
20  * @author Timo Berthold
21  * @author Thorsten Koch
22  * @author Alexander Martin
23  * @author Marc Pfetsch
24  * @author Kati Wolter
25  * @author Gregor Hendel
26  * @author Leona Gottwald
27  */
28 
29 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
30 
31 #ifndef __SCIP_SCIP_TREE_H__
32 #define __SCIP_SCIP_TREE_H__
33 
34 
35 #include "scip/def.h"
36 #include "scip/type_retcode.h"
37 #include "scip/type_scip.h"
38 #include "scip/type_tree.h"
39 
40 #ifdef __cplusplus
41 extern "C" {
42 #endif
43 
44 /**@addtogroup PublicTreeMethods
45  *
46  * @{
47  */
48 
49 /** gets focus node in the tree
50  *
51  * if we are in probing/diving mode this method returns the node in the tree where the probing/diving mode was started.
52  *
53  * @return the current node of the search tree
54  *
55  * @pre This method can be called if @p scip is in one of the following stages:
56  * - \ref SCIP_STAGE_INITPRESOLVE
57  * - \ref SCIP_STAGE_PRESOLVING
58  * - \ref SCIP_STAGE_EXITPRESOLVE
59  * - \ref SCIP_STAGE_SOLVING
60  */
63  SCIP* scip /**< SCIP data structure */
64  );
65 
66 /** gets current node in the tree
67  *
68  * @return the current node of the search tree
69  *
70  * @pre This method can be called if @p scip is in one of the following stages:
71  * - \ref SCIP_STAGE_INITPRESOLVE
72  * - \ref SCIP_STAGE_PRESOLVING
73  * - \ref SCIP_STAGE_EXITPRESOLVE
74  * - \ref SCIP_STAGE_SOLVING
75  */
78  SCIP* scip /**< SCIP data structure */
79  );
80 
81 /** gets depth of current node, or -1 if no current node exists; in probing, the current node is the last probing node,
82  * such that the depth includes the probing path
83  *
84  * @return the depth of current node, or -1 if no current node exists; in probing, the current node is the last probing node,
85  * such that the depth includes the probing path
86  *
87  * @pre This method can be called if SCIP is in one of the following stages:
88  * - \ref SCIP_STAGE_TRANSFORMED
89  * - \ref SCIP_STAGE_INITPRESOLVE
90  * - \ref SCIP_STAGE_PRESOLVING
91  * - \ref SCIP_STAGE_EXITPRESOLVE
92  * - \ref SCIP_STAGE_PRESOLVED
93  * - \ref SCIP_STAGE_INITSOLVE
94  * - \ref SCIP_STAGE_SOLVING
95  * - \ref SCIP_STAGE_SOLVED
96  * - \ref SCIP_STAGE_EXITSOLVE
97  */
99 int SCIPgetDepth(
100  SCIP* scip /**< SCIP data structure */
101  );
102 
103 /** gets depth of the focus node, or -1 if no focus node exists; the focus node is the currently processed node in the
104  * branching tree, excluding the nodes of the probing path
105  *
106  * @return the depth of the focus node, or -1 if no focus node exists; the focus node is the currently processed node in the
107  * branching tree, excluding the nodes of the probing path
108  *
109  * @pre This method can be called if SCIP is in one of the following stages:
110  * - \ref SCIP_STAGE_TRANSFORMED
111  * - \ref SCIP_STAGE_INITPRESOLVE
112  * - \ref SCIP_STAGE_PRESOLVING
113  * - \ref SCIP_STAGE_EXITPRESOLVE
114  * - \ref SCIP_STAGE_PRESOLVED
115  * - \ref SCIP_STAGE_INITSOLVE
116  * - \ref SCIP_STAGE_SOLVING
117  * - \ref SCIP_STAGE_SOLVED
118  * - \ref SCIP_STAGE_EXITSOLVE
119  */
122  SCIP* scip /**< SCIP data structure */
123  );
124 
125 /** gets current plunging depth (successive times, a child was selected as next node)
126  *
127  * @return the current plunging depth (successive times, a child was selected as next node)
128  *
129  * @pre This method can be called if SCIP is in one of the following stages:
130  * - \ref SCIP_STAGE_PRESOLVED
131  * - \ref SCIP_STAGE_SOLVING
132  */
135  SCIP* scip /**< SCIP data structure */
136  );
137 
138 /** gets the root node of the tree
139  *
140  * @return the root node of the search tree
141  *
142  * @pre This method can be called if @p scip is in one of the following stages:
143  * - \ref SCIP_STAGE_INITPRESOLVE
144  * - \ref SCIP_STAGE_PRESOLVING
145  * - \ref SCIP_STAGE_EXITPRESOLVE
146  * - \ref SCIP_STAGE_SOLVING
147  */
150  SCIP* scip /**< SCIP data structure */
151  );
152 
153 /** gets the effective root depth, i.e., the depth of the deepest node which is part of all paths from the root node
154  * to the unprocessed nodes.
155  *
156  * @return effective root depth
157  *
158  * @pre This method can be called if @p scip is in one of the following stages:
159  * - \ref SCIP_STAGE_SOLVING
160  */
163  SCIP* scip /**< SCIP data structure */
164  );
165 
166 /** returns whether the current node is already solved and only propagated again
167  *
168  * @return TRUE is returned if \SCIP performance repropagation, otherwise FALSE.
169  *
170  * @pre This method can be called if @p scip is in one of the following stages:
171  * - \ref SCIP_STAGE_INITPRESOLVE
172  * - \ref SCIP_STAGE_PRESOLVING
173  * - \ref SCIP_STAGE_EXITPRESOLVE
174  * - \ref SCIP_STAGE_SOLVING
175  */
178  SCIP* scip /**< SCIP data structure */
179  );
180 
181 /** gets children of focus node along with the number of children
182  *
183  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
184  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
185  *
186  * @pre This method can be called if @p scip is in one of the following stages:
187  * - \ref SCIP_STAGE_SOLVING
188  */
191  SCIP* scip, /**< SCIP data structure */
192  SCIP_NODE*** children, /**< pointer to store children array, or NULL if not needed */
193  int* nchildren /**< pointer to store number of children, or NULL if not needed */
194  );
195 
196 /** gets number of children of focus node
197  *
198  * @return number of children of the focus node
199  *
200  * @pre This method can be called if @p scip is in one of the following stages:
201  * - \ref SCIP_STAGE_SOLVING
202  */
204 int SCIPgetNChildren(
205  SCIP* scip /**< SCIP data structure */
206  );
207 
208 /** gets siblings of focus node along with the number of siblings
209  *
210  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
211  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
212  *
213  * @pre This method can be called if @p scip is in one of the following stages:
214  * - \ref SCIP_STAGE_SOLVING
215  */
218  SCIP* scip, /**< SCIP data structure */
219  SCIP_NODE*** siblings, /**< pointer to store siblings array, or NULL if not needed */
220  int* nsiblings /**< pointer to store number of siblings, or NULL if not needed */
221  );
222 
223 /** gets number of siblings of focus node
224  *
225  * @return the number of siblings of focus node
226  *
227  * @pre This method can be called if @p scip is in one of the following stages:
228  * - \ref SCIP_STAGE_SOLVING
229  */
231 int SCIPgetNSiblings(
232  SCIP* scip /**< SCIP data structure */
233  );
234 
235 /** gets leaves of the tree along with the number of leaves
236  *
237  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
238  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
239  *
240  * @pre This method can be called if @p scip is in one of the following stages:
241  * - \ref SCIP_STAGE_SOLVING
242  */
245  SCIP* scip, /**< SCIP data structure */
246  SCIP_NODE*** leaves, /**< pointer to store leaves array, or NULL if not needed */
247  int* nleaves /**< pointer to store number of leaves, or NULL if not needed */
248  );
249 
250 /** gets number of leaves in the tree
251  *
252  * @return the number of leaves in the tree
253  *
254  * @pre This method can be called if @p scip is in one of the following stages:
255  * - \ref SCIP_STAGE_SOLVING
256  */
258 int SCIPgetNLeaves(
259  SCIP* scip /**< SCIP data structure */
260  );
261 
262 /** gets number of nodes left in the tree (children + siblings + leaves)
263  *
264  * @return the number of nodes left in the tree (children + siblings + leaves)
265  *
266  * @pre This method can be called if SCIP is in one of the following stages:
267  * - \ref SCIP_STAGE_PRESOLVED
268  * - \ref SCIP_STAGE_SOLVING
269  * - \ref SCIP_STAGE_SOLVED
270  */
273  SCIP* scip /**< SCIP data structure */
274  );
275 
276 /** gets the best child of the focus node w.r.t. the node selection priority assigned by the branching rule
277  *
278  * @return the best child of the focus node w.r.t. the node selection priority assigned by the branching rule
279  *
280  * @pre This method can be called if @p scip is in one of the following stages:
281  * - \ref SCIP_STAGE_SOLVING
282  */
285  SCIP* scip /**< SCIP data structure */
286  );
287 
288 /** gets the best sibling of the focus node w.r.t. the node selection priority assigned by the branching rule
289  *
290  * @return the best sibling of the focus node w.r.t. the node selection priority assigned by the branching rule
291  *
292  * @pre This method can be called if @p scip is in one of the following stages:
293  * - \ref SCIP_STAGE_SOLVING
294  */
297  SCIP* scip /**< SCIP data structure */
298  );
299 
300 /** gets the best child of the focus node w.r.t. the node selection strategy
301  *
302  * @return the best child of the focus node w.r.t. the node selection strategy
303  *
304  * @pre This method can be called if @p scip is in one of the following stages:
305  * - \ref SCIP_STAGE_SOLVING
306  */
309  SCIP* scip /**< SCIP data structure */
310  );
311 
312 /** gets the best sibling of the focus node w.r.t. the node selection strategy
313  *
314  * @return the best sibling of the focus node w.r.t. the node selection strategy
315  *
316  * @pre This method can be called if @p scip is in one of the following stages:
317  * - \ref SCIP_STAGE_SOLVING
318  */
321  SCIP* scip /**< SCIP data structure */
322  );
323 
324 /** gets the best leaf from the node queue w.r.t. the node selection strategy
325  *
326  * @return the best leaf from the node queue w.r.t. the node selection strategy
327  *
328  * @pre This method can be called if @p scip is in one of the following stages:
329  * - \ref SCIP_STAGE_SOLVING
330  */
333  SCIP* scip /**< SCIP data structure */
334  );
335 
336 /** gets the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy
337  *
338  * @return the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy
339  *
340  * @pre This method can be called if @p scip is in one of the following stages:
341  * - \ref SCIP_STAGE_SOLVING
342  */
345  SCIP* scip /**< SCIP data structure */
346  );
347 
348 /** gets the node with smallest lower bound from the tree (child, sibling, or leaf)
349  *
350  * @return the node with smallest lower bound from the tree (child, sibling, or leaf)
351  *
352  * @pre This method can be called if @p scip is in one of the following stages:
353  * - \ref SCIP_STAGE_SOLVING
354  */
357  SCIP* scip /**< SCIP data structure */
358  );
359 
360 /** access to all data of open nodes (leaves, children, and siblings)
361  *
362  * @pre This method can be called if @p scip is in one of the following stages:
363  * - \ref SCIP_STAGE_SOLVING
364  */
367  SCIP* scip, /**< SCIP data structure */
368  SCIP_NODE*** leaves, /**< pointer to store the leaves, or NULL if not needed */
369  SCIP_NODE*** children, /**< pointer to store the children, or NULL if not needed */
370  SCIP_NODE*** siblings, /**< pointer to store the siblings, or NULL if not needed */
371  int* nleaves, /**< pointer to store the number of leaves, or NULL */
372  int* nchildren, /**< pointer to store the number of children, or NULL */
373  int* nsiblings /**< pointer to store the number of siblings, or NULL */
374  );
375 
376 /** cuts off node and whole sub tree from branch and bound tree
377  *
378  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
379  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
380  *
381  * @pre This method can be called if @p scip is in one of the following stages:
382  * - \ref SCIP_STAGE_SOLVING
383  */
386  SCIP* scip, /**< SCIP data structure */
387  SCIP_NODE* node /**< node that should be cut off */
388  );
389 
390 /** marks the given node to be propagated again the next time a node of its subtree is processed
391  *
392  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
393  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
394  *
395  * @pre This method can be called if @p scip is in one of the following stages:
396  * - \ref SCIP_STAGE_SOLVING
397  */
400  SCIP* scip, /**< SCIP data structure */
401  SCIP_NODE* node /**< node that should be propagated again */
402  );
403 
404 /** returns depth of first node in active path that is marked being cutoff
405  *
406  * @return depth of first node in active path that is marked being cutoff
407  *
408  * @pre This method can be called if @p scip is in one of the following stages:
409  * - \ref SCIP_STAGE_SOLVING
410  */
413  SCIP* scip /**< SCIP data structure */
414  );
415 
416 /** returns depth of first node in active path that has to be propagated again
417  *
418  * @return depth of first node in active path that has to be propagated again
419  *
420  * @pre This method can be called if @p scip is in one of the following stages:
421  * - \ref SCIP_STAGE_SOLVING
422  */
425  SCIP* scip /**< SCIP data structure */
426  );
427 
428 /** prints all branching decisions on variables from the root to the given node
429  *
430  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
431  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
432  *
433  * @pre This method can be called if @p scip is in one of the following stages:
434  * - \ref SCIP_STAGE_SOLVING
435  */
438  SCIP* scip, /**< SCIP data structure */
439  SCIP_NODE* node, /**< node data */
440  FILE* file /**< output file (or NULL for standard output) */
441  );
442 
443 /** sets whether the LP should be solved at the focus node
444  *
445  * @note In order to have an effect, this method needs to be called after a node is focused but before the LP is
446  * solved.
447  *
448  * @pre This method can be called if @p scip is in one of the following stages:
449  * - \ref SCIP_STAGE_SOLVING
450  */
452 void SCIPsetFocusnodeLP(
453  SCIP* scip, /**< SCIP data structure */
454  SCIP_Bool solvelp /**< should the LP be solved? */
455  );
456 
457 
458 /** query if node was the last parent of a branching of the tree
459  *
460  * @return TRUE if node was the last parent of a branching of the tree
461  *
462  * @pre This method can be called if SCIP is in one of the following stages:
463  * - \ref SCIP_STAGE_PRESOLVED
464  * - \ref SCIP_STAGE_SOLVING
465  * - \ref SCIP_STAGE_SOLVED
466  */
469  SCIP* scip, /**< SCIP data structure */
470  SCIP_NODE* node /**< tree node, or NULL to check focus node */
471  );
472 
473 /**@} */
474 
475 #ifdef __cplusplus
476 }
477 #endif
478 
479 #endif
SCIP_EXPORT SCIP_NODE * SCIPgetBestChild(SCIP *scip)
Definition: scip_tree.c:310
SCIP_EXPORT SCIP_RETCODE SCIPprintNodeRootPath(SCIP *scip, SCIP_NODE *node, FILE *file)
Definition: scip_tree.c:497
SCIP_EXPORT SCIP_NODE * SCIPgetBestLeaf(SCIP *scip)
Definition: scip_tree.c:342
SCIP_EXPORT void SCIPsetFocusnodeLP(SCIP *scip, SCIP_Bool solvelp)
Definition: scip_tree.c:593
SCIP_EXPORT int SCIPgetCutoffdepth(SCIP *scip)
Definition: scip_tree.c:464
#define SCIP_EXPORT
Definition: def.h:100
SCIP_EXPORT SCIP_RETCODE SCIPgetOpenNodesData(SCIP *scip, SCIP_NODE ***leaves, SCIP_NODE ***children, SCIP_NODE ***siblings, int *nleaves, int *nchildren, int *nsiblings)
Definition: scip_tree.c:388
SCIP_EXPORT SCIP_NODE * SCIPgetPrioSibling(SCIP *scip)
Definition: scip_tree.c:294
SCIP_EXPORT SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:81
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_EXPORT SCIP_RETCODE SCIPgetChildren(SCIP *scip, SCIP_NODE ***children, int *nchildren)
Definition: scip_tree.c:154
SCIP_EXPORT SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:424
type definitions for return codes for SCIP methods
SCIP_EXPORT SCIP_NODE * SCIPgetBestSibling(SCIP *scip)
Definition: scip_tree.c:326
SCIP_EXPORT SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:136
SCIP_EXPORT int SCIPgetEffectiveRootDepth(SCIP *scip)
Definition: scip_tree.c:117
SCIP_EXPORT SCIP_NODE * SCIPgetFocusNode(SCIP *scip)
Definition: scip_tree.c:62
SCIP_EXPORT SCIP_NODE * SCIPgetBestNode(SCIP *scip)
Definition: scip_tree.c:358
SCIP_EXPORT SCIP_RETCODE SCIPgetLeaves(SCIP *scip, SCIP_NODE ***leaves, int *nleaves)
Definition: scip_tree.c:238
type definitions for SCIP&#39;s main datastructure
SCIP_EXPORT SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip_tree.c:100
SCIP_EXPORT int SCIPgetNChildren(SCIP *scip)
Definition: scip_tree.c:178
SCIP_EXPORT SCIP_NODE * SCIPgetPrioChild(SCIP *scip)
Definition: scip_tree.c:278
SCIP_EXPORT int SCIPgetPlungeDepth(SCIP *scip)
Definition: scip_tree.c:681
SCIP_EXPORT int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:638
#define SCIP_Bool
Definition: def.h:70
type definitions for branch and bound tree
SCIP_EXPORT int SCIPgetNNodesLeft(SCIP *scip)
Definition: scip_tree.c:612
SCIP_EXPORT SCIP_NODE * SCIPgetBestboundNode(SCIP *scip)
Definition: scip_tree.c:374
SCIP_EXPORT int SCIPgetNLeaves(SCIP *scip)
Definition: scip_tree.c:262
SCIP_EXPORT SCIP_RETCODE SCIPgetSiblings(SCIP *scip, SCIP_NODE ***siblings, int *nsiblings)
Definition: scip_tree.c:196
SCIP_EXPORT SCIP_RETCODE SCIPrepropagateNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:445
SCIP_EXPORT int SCIPgetRepropdepth(SCIP *scip)
Definition: scip_tree.c:480
SCIP_EXPORT SCIP_Bool SCIPwasNodeLastBranchParent(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:699
common defines and data types used in all packages of SCIP
SCIP_EXPORT int SCIPgetFocusDepth(SCIP *scip)
Definition: scip_tree.c:664
SCIP_EXPORT int SCIPgetNSiblings(SCIP *scip)
Definition: scip_tree.c:220