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-2018 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 scip.zib.de. */
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 Robert Lion 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 /* In debug mode, we include the SCIP's structure in scip.c, such that no one can access
41  * this structure except the interface methods in scip.c.
42  * In optimized mode, the structure is included in scip.h, because some of the methods
43  * are implemented as defines for performance reasons (e.g. the numerical comparisons).
44  * Additionally, the internal "set.h" is included, such that the defines in set.h are
45  * available in optimized mode.
46  */
47 #ifdef NDEBUG
48 #include "scip/struct_scip.h"
49 #include "scip/struct_stat.h"
50 #include "scip/set.h"
51 #include "scip/tree.h"
52 #include "scip/misc.h"
53 #include "scip/var.h"
54 #include "scip/cons.h"
55 #include "scip/solve.h"
56 #include "scip/debug.h"
57 #endif
58 
59 #ifdef __cplusplus
60 extern "C" {
61 #endif
62 
63 /**@addtogroup PublicTreeMethods
64  *
65  * @{
66  */
67 
68 /** gets focus node in the tree
69  *
70  * if we are in probing/diving mode this method returns the node in the tree where the probing/diving mode was started.
71  *
72  * @return the current node of the search tree
73  *
74  * @pre This method can be called if @p scip is in one of the following stages:
75  * - \ref SCIP_STAGE_INITPRESOLVE
76  * - \ref SCIP_STAGE_PRESOLVING
77  * - \ref SCIP_STAGE_EXITPRESOLVE
78  * - \ref SCIP_STAGE_SOLVING
79  */
80 extern
82  SCIP* scip /**< SCIP data structure */
83  );
84 
85 /** gets current node in the tree
86  *
87  * @return the current node of the search tree
88  *
89  * @pre This method can be called if @p scip is in one of the following stages:
90  * - \ref SCIP_STAGE_INITPRESOLVE
91  * - \ref SCIP_STAGE_PRESOLVING
92  * - \ref SCIP_STAGE_EXITPRESOLVE
93  * - \ref SCIP_STAGE_SOLVING
94  */
95 extern
97  SCIP* scip /**< SCIP data structure */
98  );
99 
100 /** gets depth of current node, or -1 if no current node exists; in probing, the current node is the last probing node,
101  * such that the depth includes the probing path
102  *
103  * @return the depth of current node, or -1 if no current node exists; in probing, the current node is the last probing node,
104  * such that the depth includes the probing path
105  *
106  * @pre This method can be called if SCIP is in one of the following stages:
107  * - \ref SCIP_STAGE_TRANSFORMED
108  * - \ref SCIP_STAGE_INITPRESOLVE
109  * - \ref SCIP_STAGE_PRESOLVING
110  * - \ref SCIP_STAGE_EXITPRESOLVE
111  * - \ref SCIP_STAGE_PRESOLVED
112  * - \ref SCIP_STAGE_INITSOLVE
113  * - \ref SCIP_STAGE_SOLVING
114  * - \ref SCIP_STAGE_SOLVED
115  * - \ref SCIP_STAGE_EXITSOLVE
116  */
117 extern
118 int SCIPgetDepth(
119  SCIP* scip /**< SCIP data structure */
120  );
121 
122 /** gets depth of the focus node, or -1 if no focus node exists; the focus node is the currently processed node in the
123  * branching tree, excluding the nodes of the probing path
124  *
125  * @return the depth of the focus node, or -1 if no focus node exists; the focus node is the currently processed node in the
126  * branching tree, excluding the nodes of the probing path
127  *
128  * @pre This method can be called if SCIP is in one of the following stages:
129  * - \ref SCIP_STAGE_TRANSFORMED
130  * - \ref SCIP_STAGE_INITPRESOLVE
131  * - \ref SCIP_STAGE_PRESOLVING
132  * - \ref SCIP_STAGE_EXITPRESOLVE
133  * - \ref SCIP_STAGE_PRESOLVED
134  * - \ref SCIP_STAGE_INITSOLVE
135  * - \ref SCIP_STAGE_SOLVING
136  * - \ref SCIP_STAGE_SOLVED
137  * - \ref SCIP_STAGE_EXITSOLVE
138  */
139 extern
141  SCIP* scip /**< SCIP data structure */
142  );
143 
144 /** gets current plunging depth (successive times, a child was selected as next node)
145  *
146  * @return the current plunging depth (successive times, a child was selected as next node)
147  *
148  * @pre This method can be called if SCIP is in one of the following stages:
149  * - \ref SCIP_STAGE_PRESOLVED
150  * - \ref SCIP_STAGE_SOLVING
151  */
152 extern
154  SCIP* scip /**< SCIP data structure */
155  );
156 
157 /** gets the root node of the tree
158  *
159  * @return the root node of the search tree
160  *
161  * @pre This method can be called if @p scip is in one of the following stages:
162  * - \ref SCIP_STAGE_INITPRESOLVE
163  * - \ref SCIP_STAGE_PRESOLVING
164  * - \ref SCIP_STAGE_EXITPRESOLVE
165  * - \ref SCIP_STAGE_SOLVING
166  */
167 extern
169  SCIP* scip /**< SCIP data structure */
170  );
171 
172 /** gets the effective root depth, i.e., the depth of the deepest node which is part of all paths from the root node
173  * to the unprocessed nodes.
174  *
175  * @return effective root depth
176  *
177  * @pre This method can be called if @p scip is in one of the following stages:
178  * - \ref SCIP_STAGE_SOLVING
179  */
180 extern
182  SCIP* scip /**< SCIP data structure */
183  );
184 
185 /** returns whether the current node is already solved and only propagated again
186  *
187  * @return TRUE is returned if \SCIP performance repropagation, otherwise FALSE.
188  *
189  * @pre This method can be called if @p scip is in one of the following stages:
190  * - \ref SCIP_STAGE_INITPRESOLVE
191  * - \ref SCIP_STAGE_PRESOLVING
192  * - \ref SCIP_STAGE_EXITPRESOLVE
193  * - \ref SCIP_STAGE_SOLVING
194  */
195 extern
197  SCIP* scip /**< SCIP data structure */
198  );
199 
200 /** gets children of focus node along with the number of children
201  *
202  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
203  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
204  *
205  * @pre This method can be called if @p scip is in one of the following stages:
206  * - \ref SCIP_STAGE_SOLVING
207  */
208 extern
210  SCIP* scip, /**< SCIP data structure */
211  SCIP_NODE*** children, /**< pointer to store children array, or NULL if not needed */
212  int* nchildren /**< pointer to store number of children, or NULL if not needed */
213  );
214 
215 /** gets number of children of focus node
216  *
217  * @return number of children of the focus node
218  *
219  * @pre This method can be called if @p scip is in one of the following stages:
220  * - \ref SCIP_STAGE_SOLVING
221  */
222 extern
223 int SCIPgetNChildren(
224  SCIP* scip /**< SCIP data structure */
225  );
226 
227 /** gets siblings of focus node along with the number of siblings
228  *
229  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
230  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
231  *
232  * @pre This method can be called if @p scip is in one of the following stages:
233  * - \ref SCIP_STAGE_SOLVING
234  */
235 extern
237  SCIP* scip, /**< SCIP data structure */
238  SCIP_NODE*** siblings, /**< pointer to store siblings array, or NULL if not needed */
239  int* nsiblings /**< pointer to store number of siblings, or NULL if not needed */
240  );
241 
242 /** gets number of siblings of focus node
243  *
244  * @return the number of siblings of focus node
245  *
246  * @pre This method can be called if @p scip is in one of the following stages:
247  * - \ref SCIP_STAGE_SOLVING
248  */
249 extern
250 int SCIPgetNSiblings(
251  SCIP* scip /**< SCIP data structure */
252  );
253 
254 /** gets leaves of the tree along with the number of leaves
255  *
256  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
257  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
258  *
259  * @pre This method can be called if @p scip is in one of the following stages:
260  * - \ref SCIP_STAGE_SOLVING
261  */
262 extern
264  SCIP* scip, /**< SCIP data structure */
265  SCIP_NODE*** leaves, /**< pointer to store leaves array, or NULL if not needed */
266  int* nleaves /**< pointer to store number of leaves, or NULL if not needed */
267  );
268 
269 /** gets number of leaves in the tree
270  *
271  * @return the number of leaves in the tree
272  *
273  * @pre This method can be called if @p scip is in one of the following stages:
274  * - \ref SCIP_STAGE_SOLVING
275  */
276 extern
277 int SCIPgetNLeaves(
278  SCIP* scip /**< SCIP data structure */
279  );
280 
281 /** gets number of nodes left in the tree (children + siblings + leaves)
282  *
283  * @return the number of nodes left in the tree (children + siblings + leaves)
284  *
285  * @pre This method can be called if SCIP is in one of the following stages:
286  * - \ref SCIP_STAGE_PRESOLVED
287  * - \ref SCIP_STAGE_SOLVING
288  * - \ref SCIP_STAGE_SOLVED
289  */
290 extern
292  SCIP* scip /**< SCIP data structure */
293  );
294 
295 /** gets the best child of the focus node w.r.t. the node selection priority assigned by the branching rule
296  *
297  * @return the best child of the focus node w.r.t. the node selection priority assigned by the branching rule
298  *
299  * @pre This method can be called if @p scip is in one of the following stages:
300  * - \ref SCIP_STAGE_SOLVING
301  */
302 extern
304  SCIP* scip /**< SCIP data structure */
305  );
306 
307 /** gets the best sibling of the focus node w.r.t. the node selection priority assigned by the branching rule
308  *
309  * @return the best sibling of the focus node w.r.t. the node selection priority assigned by the branching rule
310  *
311  * @pre This method can be called if @p scip is in one of the following stages:
312  * - \ref SCIP_STAGE_SOLVING
313  */
314 extern
316  SCIP* scip /**< SCIP data structure */
317  );
318 
319 /** gets the best child of the focus node w.r.t. the node selection strategy
320  *
321  * @return the best child of the focus node w.r.t. the node selection strategy
322  *
323  * @pre This method can be called if @p scip is in one of the following stages:
324  * - \ref SCIP_STAGE_SOLVING
325  */
326 extern
328  SCIP* scip /**< SCIP data structure */
329  );
330 
331 /** gets the best sibling of the focus node w.r.t. the node selection strategy
332  *
333  * @return the best sibling of the focus node w.r.t. the node selection strategy
334  *
335  * @pre This method can be called if @p scip is in one of the following stages:
336  * - \ref SCIP_STAGE_SOLVING
337  */
338 extern
340  SCIP* scip /**< SCIP data structure */
341  );
342 
343 /** gets the best leaf from the node queue w.r.t. the node selection strategy
344  *
345  * @return the best leaf from the node queue w.r.t. the node selection strategy
346  *
347  * @pre This method can be called if @p scip is in one of the following stages:
348  * - \ref SCIP_STAGE_SOLVING
349  */
350 extern
352  SCIP* scip /**< SCIP data structure */
353  );
354 
355 /** gets the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy
356  *
357  * @return the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy
358  *
359  * @pre This method can be called if @p scip is in one of the following stages:
360  * - \ref SCIP_STAGE_SOLVING
361  */
362 extern
364  SCIP* scip /**< SCIP data structure */
365  );
366 
367 /** gets the node with smallest lower bound from the tree (child, sibling, or leaf)
368  *
369  * @return the node with smallest lower bound from the tree (child, sibling, or leaf)
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 extern
376  SCIP* scip /**< SCIP data structure */
377  );
378 
379 /** access to all data of open nodes (leaves, children, and siblings)
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 extern
386  SCIP* scip, /**< SCIP data structure */
387  SCIP_NODE*** leaves, /**< pointer to store the leaves, or NULL if not needed */
388  SCIP_NODE*** children, /**< pointer to store the children, or NULL if not needed */
389  SCIP_NODE*** siblings, /**< pointer to store the siblings, or NULL if not needed */
390  int* nleaves, /**< pointer to store the number of leaves, or NULL */
391  int* nchildren, /**< pointer to store the number of children, or NULL */
392  int* nsiblings /**< pointer to store the number of siblings, or NULL */
393  );
394 
395 /** cuts off node and whole sub tree from branch and bound tree
396  *
397  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
398  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
399  *
400  * @pre This method can be called if @p scip is in one of the following stages:
401  * - \ref SCIP_STAGE_SOLVING
402  */
403 extern
405  SCIP* scip, /**< SCIP data structure */
406  SCIP_NODE* node /**< node that should be cut off */
407  );
408 
409 /** marks the given node to be propagated again the next time a node of its subtree is processed
410  *
411  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
412  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
413  *
414  * @pre This method can be called if @p scip is in one of the following stages:
415  * - \ref SCIP_STAGE_SOLVING
416  */
417 extern
419  SCIP* scip, /**< SCIP data structure */
420  SCIP_NODE* node /**< node that should be propagated again */
421  );
422 
423 /** returns depth of first node in active path that is marked being cutoff
424  *
425  * @return depth of first node in active path that is marked being cutoff
426  *
427  * @pre This method can be called if @p scip is in one of the following stages:
428  * - \ref SCIP_STAGE_SOLVING
429  */
430 extern
432  SCIP* scip /**< SCIP data structure */
433  );
434 
435 /** returns depth of first node in active path that has to be propagated again
436  *
437  * @return depth of first node in active path that has to be propagated again
438  *
439  * @pre This method can be called if @p scip is in one of the following stages:
440  * - \ref SCIP_STAGE_SOLVING
441  */
442 extern
444  SCIP* scip /**< SCIP data structure */
445  );
446 
447 /** prints all branching decisions on variables from the root to the given node
448  *
449  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
450  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
451  *
452  * @pre This method can be called if @p scip is in one of the following stages:
453  * - \ref SCIP_STAGE_SOLVING
454  */
455 extern
457  SCIP* scip, /**< SCIP data structure */
458  SCIP_NODE* node, /**< node data */
459  FILE* file /**< output file (or NULL for standard output) */
460  );
461 
462 /** sets whether the LP should be solved at the focus node
463  *
464  * @note In order to have an effect, this method needs to be called after a node is focused but before the LP is
465  * solved.
466  *
467  * @pre This method can be called if @p scip is in one of the following stages:
468  * - \ref SCIP_STAGE_SOLVING
469  */
470 extern
471 void SCIPsetFocusnodeLP(
472  SCIP* scip, /**< SCIP data structure */
473  SCIP_Bool solvelp /**< should the LP be solved? */
474  );
475 
476 /**@} */
477 
478 #ifdef __cplusplus
479 }
480 #endif
481 
482 #endif
int SCIPgetFocusDepth(SCIP *scip)
Definition: scip_tree.c:741
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:213
int SCIPgetPlungeDepth(SCIP *scip)
Definition: scip_tree.c:758
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:158
internal methods for branch and bound tree
SCIP_RETCODE SCIPgetLeaves(SCIP *scip, SCIP_NODE ***leaves, int *nleaves)
Definition: scip_tree.c:315
int SCIPgetNSiblings(SCIP *scip)
Definition: scip_tree.c:297
int SCIPgetNLeaves(SCIP *scip)
Definition: scip_tree.c:339
SCIP_RETCODE SCIPgetOpenNodesData(SCIP *scip, SCIP_NODE ***leaves, SCIP_NODE ***children, SCIP_NODE ***siblings, int *nleaves, int *nchildren, int *nsiblings)
Definition: scip_tree.c:465
SCIP_NODE * SCIPgetBestSibling(SCIP *scip)
Definition: scip_tree.c:403
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:501
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
int SCIPgetNNodesLeft(SCIP *scip)
Definition: scip_tree.c:689
type definitions for return codes for SCIP methods
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip_tree.c:177
SCIP_RETCODE SCIPgetSiblings(SCIP *scip, SCIP_NODE ***siblings, int *nsiblings)
Definition: scip_tree.c:273
SCIP_RETCODE SCIPrepropagateNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:522
int SCIPgetCutoffdepth(SCIP *scip)
Definition: scip_tree.c:541
SCIP_RETCODE SCIPgetChildren(SCIP *scip, SCIP_NODE ***children, int *nchildren)
Definition: scip_tree.c:231
type definitions for SCIP&#39;s main datastructure
int SCIPgetNChildren(SCIP *scip)
Definition: scip_tree.c:255
internal miscellaneous methods
int SCIPgetEffectiveRootDepth(SCIP *scip)
Definition: scip_tree.c:194
internal methods for global SCIP settings
SCIP main data structure.
SCIP_NODE * SCIPgetBestboundNode(SCIP *scip)
Definition: scip_tree.c:451
SCIP_NODE * SCIPgetBestNode(SCIP *scip)
Definition: scip_tree.c:435
internal methods for problem variables
#define SCIP_Bool
Definition: def.h:62
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:715
methods for debugging
type definitions for branch and bound tree
datastructures for problem statistics
SCIP_NODE * SCIPgetFocusNode(SCIP *scip)
Definition: scip_tree.c:139
SCIP_NODE * SCIPgetPrioSibling(SCIP *scip)
Definition: scip_tree.c:371
SCIP_RETCODE SCIPprintNodeRootPath(SCIP *scip, SCIP_NODE *node, FILE *file)
Definition: scip_tree.c:574
internal methods for main solving loop and node processing
int SCIPgetRepropdepth(SCIP *scip)
Definition: scip_tree.c:557
internal methods for constraints and constraint handlers
SCIP_NODE * SCIPgetPrioChild(SCIP *scip)
Definition: scip_tree.c:355
SCIP_NODE * SCIPgetBestChild(SCIP *scip)
Definition: scip_tree.c:387
SCIP_NODE * SCIPgetBestLeaf(SCIP *scip)
Definition: scip_tree.c:419
common defines and data types used in all packages of SCIP
void SCIPsetFocusnodeLP(SCIP *scip, SCIP_Bool solvelp)
Definition: scip_tree.c:670