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-2024 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
50extern "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 */
70SCIP_EXPORT
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 */
85SCIP_EXPORT
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 */
107SCIP_EXPORT
108int 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 */
129SCIP_EXPORT
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 */
142SCIP_EXPORT
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 */
157SCIP_EXPORT
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 */
170SCIP_EXPORT
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 */
185SCIP_EXPORT
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 */
198SCIP_EXPORT
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 */
212SCIP_EXPORT
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 */
225SCIP_EXPORT
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 */
239SCIP_EXPORT
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 */
252SCIP_EXPORT
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 */
266SCIP_EXPORT
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 */
280SCIP_EXPORT
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 */
292SCIP_EXPORT
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 */
304SCIP_EXPORT
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 */
316SCIP_EXPORT
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 */
328SCIP_EXPORT
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 */
340SCIP_EXPORT
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 */
352SCIP_EXPORT
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 */
364SCIP_EXPORT
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 */
374SCIP_EXPORT
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 */
393SCIP_EXPORT
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 */
409SCIP_EXPORT
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 */
422SCIP_EXPORT
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 */
435SCIP_EXPORT
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 */
447SCIP_EXPORT
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 */
460SCIP_EXPORT
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 */
475SCIP_EXPORT
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 */
491SCIP_EXPORT
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
common defines and data types used in all packages of SCIP
#define SCIP_Bool
Definition: def.h:91
SCIP_RETCODE SCIPpruneTree(SCIP *scip)
Definition: scip_tree.c:457
int SCIPgetEffectiveRootDepth(SCIP *scip)
Definition: scip_tree.c:127
int SCIPgetNSiblings(SCIP *scip)
Definition: scip_tree.c:230
SCIP_RETCODE SCIPrepropagateNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:477
SCIP_NODE * SCIPgetBestSibling(SCIP *scip)
Definition: scip_tree.c:336
int SCIPgetNChildren(SCIP *scip)
Definition: scip_tree.c:188
SCIP_RETCODE SCIPgetOpenNodesData(SCIP *scip, SCIP_NODE ***leaves, SCIP_NODE ***children, SCIP_NODE ***siblings, int *nleaves, int *nchildren, int *nsiblings)
Definition: scip_tree.c:398
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:146
void SCIPsetFocusnodeLP(SCIP *scip, SCIP_Bool solvelp)
Definition: scip_tree.c:625
SCIP_RETCODE SCIPgetChildren(SCIP *scip, SCIP_NODE ***children, int *nchildren)
Definition: scip_tree.c:164
int SCIPgetNNodesLeft(SCIP *scip)
Definition: scip_tree.c:644
int SCIPgetFocusDepth(SCIP *scip)
Definition: scip_tree.c:696
SCIP_NODE * SCIPgetFocusNode(SCIP *scip)
Definition: scip_tree.c:72
SCIP_RETCODE SCIPgetLeaves(SCIP *scip, SCIP_NODE ***leaves, int *nleaves)
Definition: scip_tree.c:248
SCIP_NODE * SCIPgetBestChild(SCIP *scip)
Definition: scip_tree.c:320
SCIP_NODE * SCIPgetPrioSibling(SCIP *scip)
Definition: scip_tree.c:304
int SCIPgetCutoffdepth(SCIP *scip)
Definition: scip_tree.c:496
SCIP_RETCODE SCIPprintNodeRootPath(SCIP *scip, SCIP_NODE *node, FILE *file)
Definition: scip_tree.c:529
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
int SCIPgetNLeaves(SCIP *scip)
Definition: scip_tree.c:272
SCIP_Bool SCIPwasNodeLastBranchParent(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:731
SCIP_NODE * SCIPgetBestNode(SCIP *scip)
Definition: scip_tree.c:368
SCIP_RETCODE SCIPgetSiblings(SCIP *scip, SCIP_NODE ***siblings, int *nsiblings)
Definition: scip_tree.c:206
int SCIPgetPlungeDepth(SCIP *scip)
Definition: scip_tree.c:713
SCIP_NODE * SCIPgetBestboundNode(SCIP *scip)
Definition: scip_tree.c:384
SCIP_NODE * SCIPgetPrioChild(SCIP *scip)
Definition: scip_tree.c:288
int SCIPgetRepropdepth(SCIP *scip)
Definition: scip_tree.c:512
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:434
SCIP_NODE * SCIPgetBestLeaf(SCIP *scip)
Definition: scip_tree.c:352
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:91
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip_tree.c:110
type definitions for return codes for SCIP methods
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type definitions for SCIP's main datastructure
type definitions for branch and bound tree