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-2022 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  */
61 SCIP_EXPORT
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  */
76 SCIP_EXPORT
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  */
98 SCIP_EXPORT
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  */
120 SCIP_EXPORT
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  */
133 SCIP_EXPORT
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  */
148 SCIP_EXPORT
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  */
161 SCIP_EXPORT
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  */
176 SCIP_EXPORT
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  */
189 SCIP_EXPORT
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  */
203 SCIP_EXPORT
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  */
216 SCIP_EXPORT
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  */
230 SCIP_EXPORT
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  */
243 SCIP_EXPORT
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  */
257 SCIP_EXPORT
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  */
271 SCIP_EXPORT
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  */
283 SCIP_EXPORT
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  */
295 SCIP_EXPORT
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  */
307 SCIP_EXPORT
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  */
319 SCIP_EXPORT
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  */
331 SCIP_EXPORT
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  */
343 SCIP_EXPORT
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  */
355 SCIP_EXPORT
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  */
365 SCIP_EXPORT
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 /** marks node and whole sub tree to be cut off 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  */
384 SCIP_EXPORT
386  SCIP* scip, /**< SCIP data structure */
387  SCIP_NODE* node /**< node that should be cut off */
388  );
389 
390 /** removes all nodes from branch and bound tree that were marked to be cut off via SCIPcutoffNode()
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  *
398  * @note In diving mode, the removal of nodes is delayed until diving ends.
399  */
400 SCIP_EXPORT
402  SCIP* scip /**< SCIP data structure */
403  );
404 
405 /** marks the given node to be propagated again the next time a node of its subtree is processed
406  *
407  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
408  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
409  *
410  * @pre This method can be called if @p scip is in one of the following stages:
411  * - \ref SCIP_STAGE_SOLVING
412  */
413 SCIP_EXPORT
415  SCIP* scip, /**< SCIP data structure */
416  SCIP_NODE* node /**< node that should be propagated again */
417  );
418 
419 /** returns depth of first node in active path that is marked being cutoff
420  *
421  * @return depth of first node in active path that is marked being cutoff
422  *
423  * @pre This method can be called if @p scip is in one of the following stages:
424  * - \ref SCIP_STAGE_SOLVING
425  */
426 SCIP_EXPORT
428  SCIP* scip /**< SCIP data structure */
429  );
430 
431 /** returns depth of first node in active path that has to be propagated again
432  *
433  * @return depth of first node in active path that has to be propagated again
434  *
435  * @pre This method can be called if @p scip is in one of the following stages:
436  * - \ref SCIP_STAGE_SOLVING
437  */
438 SCIP_EXPORT
440  SCIP* scip /**< SCIP data structure */
441  );
442 
443 /** prints all branching decisions on variables from the root to the given node
444  *
445  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
446  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
447  *
448  * @pre This method can be called if @p scip is in one of the following stages:
449  * - \ref SCIP_STAGE_SOLVING
450  */
451 SCIP_EXPORT
453  SCIP* scip, /**< SCIP data structure */
454  SCIP_NODE* node, /**< node data */
455  FILE* file /**< output file (or NULL for standard output) */
456  );
457 
458 /** sets whether the LP should be solved at the focus node
459  *
460  * @note In order to have an effect, this method needs to be called after a node is focused but before the LP is
461  * solved.
462  *
463  * @pre This method can be called if @p scip is in one of the following stages:
464  * - \ref SCIP_STAGE_SOLVING
465  */
466 SCIP_EXPORT
467 void SCIPsetFocusnodeLP(
468  SCIP* scip, /**< SCIP data structure */
469  SCIP_Bool solvelp /**< should the LP be solved? */
470  );
471 
472 
473 /** query if node was the last parent of a branching of the tree
474  *
475  * @return TRUE if node was the last parent of a branching of the tree
476  *
477  * @pre This method can be called if SCIP is in one of the following stages:
478  * - \ref SCIP_STAGE_PRESOLVED
479  * - \ref SCIP_STAGE_SOLVING
480  * - \ref SCIP_STAGE_SOLVED
481  */
482 SCIP_EXPORT
484  SCIP* scip, /**< SCIP data structure */
485  SCIP_NODE* node /**< tree node, or NULL to check focus node */
486  );
487 
488 /**@} */
489 
490 #ifdef __cplusplus
491 }
492 #endif
493 
494 #endif
int SCIPgetFocusDepth(SCIP *scip)
Definition: scip_tree.c:687
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:137
int SCIPgetPlungeDepth(SCIP *scip)
Definition: scip_tree.c:704
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:82
SCIP_RETCODE SCIPpruneTree(SCIP *scip)
Definition: scip_tree.c:448
SCIP_RETCODE SCIPgetLeaves(SCIP *scip, SCIP_NODE ***leaves, int *nleaves)
Definition: scip_tree.c:239
int SCIPgetNSiblings(SCIP *scip)
Definition: scip_tree.c:221
int SCIPgetNLeaves(SCIP *scip)
Definition: scip_tree.c:263
SCIP_RETCODE SCIPgetOpenNodesData(SCIP *scip, SCIP_NODE ***leaves, SCIP_NODE ***children, SCIP_NODE ***siblings, int *nleaves, int *nchildren, int *nsiblings)
Definition: scip_tree.c:389
SCIP_Bool SCIPwasNodeLastBranchParent(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:722
SCIP_NODE * SCIPgetBestSibling(SCIP *scip)
Definition: scip_tree.c:327
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:425
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
int SCIPgetNNodesLeft(SCIP *scip)
Definition: scip_tree.c:635
type definitions for return codes for SCIP methods
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip_tree.c:101
SCIP_RETCODE SCIPgetSiblings(SCIP *scip, SCIP_NODE ***siblings, int *nsiblings)
Definition: scip_tree.c:197
SCIP_RETCODE SCIPrepropagateNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:468
int SCIPgetCutoffdepth(SCIP *scip)
Definition: scip_tree.c:487
SCIP_RETCODE SCIPgetChildren(SCIP *scip, SCIP_NODE ***children, int *nchildren)
Definition: scip_tree.c:155
type definitions for SCIP&#39;s main datastructure
int SCIPgetNChildren(SCIP *scip)
Definition: scip_tree.c:179
int SCIPgetEffectiveRootDepth(SCIP *scip)
Definition: scip_tree.c:118
SCIP_NODE * SCIPgetBestboundNode(SCIP *scip)
Definition: scip_tree.c:375
SCIP_NODE * SCIPgetBestNode(SCIP *scip)
Definition: scip_tree.c:359
#define SCIP_Bool
Definition: def.h:84
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:661
type definitions for branch and bound tree
SCIP_NODE * SCIPgetFocusNode(SCIP *scip)
Definition: scip_tree.c:63
SCIP_NODE * SCIPgetPrioSibling(SCIP *scip)
Definition: scip_tree.c:295
SCIP_RETCODE SCIPprintNodeRootPath(SCIP *scip, SCIP_NODE *node, FILE *file)
Definition: scip_tree.c:520
int SCIPgetRepropdepth(SCIP *scip)
Definition: scip_tree.c:503
SCIP_NODE * SCIPgetPrioChild(SCIP *scip)
Definition: scip_tree.c:279
SCIP_NODE * SCIPgetBestChild(SCIP *scip)
Definition: scip_tree.c:311
SCIP_NODE * SCIPgetBestLeaf(SCIP *scip)
Definition: scip_tree.c:343
common defines and data types used in all packages of SCIP
void SCIPsetFocusnodeLP(SCIP *scip, SCIP_Bool solvelp)
Definition: scip_tree.c:616