Scippy

SCIP

Solving Constraint Integer Programs

pub_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 pub_tree.h
26 * @ingroup PUBLICCOREAPI
27 * @brief public methods for branch and bound tree
28 * @author Tobias Achterberg
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
33#ifndef __SCIP_PUB_TREE_H__
34#define __SCIP_PUB_TREE_H__
35
36#include "scip/def.h"
37#include "scip/type_cons.h"
38#include "scip/type_lp.h"
39#include "scip/type_misc.h"
40#include "scip/type_reopt.h"
41#include "scip/type_retcode.h"
42#include "scip/type_tree.h"
43#include "scip/type_var.h"
44
45#ifdef NDEBUG
46#include "scip/struct_tree.h"
47#endif
48
49#ifdef __cplusplus
50extern "C" {
51#endif
52
53/*
54 * Node methods
55 */
56
57/**@addtogroup PublicNodeMethods
58 *
59 * @{
60 */
61
62/** node comparator for best lower bound */
63SCIP_EXPORT
64SCIP_DECL_SORTPTRCOMP(SCIPnodeCompLowerbound);
65
66/** returns the set of variable branchings that were performed in the parent node to create this node */
67SCIP_EXPORT
69 SCIP_NODE* node, /**< node data */
70 SCIP_VAR** branchvars, /**< array of variables on which the branching has been performed in the parent node */
71 SCIP_Real* branchbounds, /**< array of bounds which the branching in the parent node set */
72 SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branching in the parent node set */
73 int* nbranchvars, /**< number of variables on which branching has been performed in the parent node
74 * if this is larger than the array size, arrays should be reallocated and method should be called again */
75 int branchvarssize /**< available slots in arrays */
76 );
77
78/** returns the set of variable branchings that were performed in all ancestor nodes (nodes on the path to the root) to create this node */
79SCIP_EXPORT
81 SCIP_NODE* node, /**< node data */
82 SCIP_VAR** branchvars, /**< array of variables on which the branchings has been performed in all ancestors */
83 SCIP_Real* branchbounds, /**< array of bounds which the branchings in all ancestors set */
84 SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branchings in all ancestors set */
85 int* nbranchvars, /**< number of variables on which branchings have been performed in all ancestors
86 * if this is larger than the array size, arrays should be reallocated and method should be called again */
87 int branchvarssize /**< available slots in arrays */
88 );
89
90/** returns the set of variable branchings that were performed between the given @p node and the given @p parent node. */
91SCIP_EXPORT
93 SCIP_NODE* node, /**< node data */
94 SCIP_NODE* parent, /**< node data */
95 SCIP_VAR** branchvars, /**< array of variables on which the branchings has been performed in all ancestors */
96 SCIP_Real* branchbounds, /**< array of bounds which the branchings in all ancestors set */
97 SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branchings in all ancestors set */
98 int* nbranchvars, /**< number of variables on which branchings have been performed in all ancestors
99 * if this is larger than the array size, arrays should be reallocated and method should be called again */
100 int branchvarssize /**< available slots in arrays */
101 );
102
103/** outputs the path into given file stream in GML format */
104SCIP_EXPORT
106 SCIP_NODE* node, /**< node data */
107 FILE* file /**< file to output the path */
108 );
109
110/** returns the set of variable branchings that were performed in all ancestor nodes (nodes on the path to the root) to create this node
111 * sorted by the nodes, starting from the current node going up to the root
112 */
113SCIP_EXPORT
115 SCIP_NODE* node, /**< node data */
116 SCIP_VAR** branchvars, /**< array of variables on which the branchings has been performed in all ancestors */
117 SCIP_Real* branchbounds, /**< array of bounds which the branchings in all ancestors set */
118 SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branchings in all ancestors set */
119 int* nbranchvars, /**< number of variables on which branchings have been performed in all ancestors
120 * if this is larger than the array size, arrays should be reallocated and method
121 * should be called again */
122 int branchvarssize, /**< available slots in arrays */
123 int* nodeswitches, /**< marks, where in the arrays the branching decisions of the next node on the path
124 * start; branchings performed at the parent of node always start at position 0.
125 * For single variable branching, nodeswitches[i] = i holds */
126 int* nnodes, /**< number of nodes in the nodeswitch array */
127 int nodeswitchsize /**< available slots in node switch array */
128 );
129
130
131/** checks for two nodes whether they share the same root path, i.e., whether one is an ancestor of the other */
132SCIP_EXPORT
134 SCIP_NODE* node1, /**< node data */
135 SCIP_NODE* node2 /**< node data */
136 );
137
138/** finds the common ancestor node of two given nodes */
139SCIP_EXPORT
141 SCIP_NODE* node1, /**< node data */
142 SCIP_NODE* node2 /**< node data */
143 );
144
145
146/** gets the type of the node */
147SCIP_EXPORT
149 SCIP_NODE* node /**< node */
150 );
151
152/** gets successively assigned number of the node */
153SCIP_EXPORT
155 SCIP_NODE* node /**< node */
156 );
157
158/** gets the depth of the node */
159SCIP_EXPORT
161 SCIP_NODE* node /**< node */
162 );
163
164/** gets the lower bound of the node */
165SCIP_EXPORT
167 SCIP_NODE* node /**< node */
168 );
169
170/** gets the estimated value of the best feasible solution in subtree of the node */
171SCIP_EXPORT
173 SCIP_NODE* node /**< node */
174 );
175
176
177/** gets the reoptimization type of a node */
178SCIP_EXPORT
180 SCIP_NODE* node /**< node */
181 );
182
183/** gets the unique id to identify the node during reoptimization; id is 0 if the node is the root or not part of the
184 * reoptimization tree
185 */
186SCIP_EXPORT
187unsigned int SCIPnodeGetReoptID(
188 SCIP_NODE* node /**< node */
189 );
190
191/** sets the reoptimization type of the node */
192SCIP_EXPORT
194 SCIP_NODE* node, /**< node */
195 SCIP_REOPTTYPE reopttype /**< reoptimization type */
196 );
197
198/** sets a unique id to identify the node during reoptimization */
199SCIP_EXPORT
201 SCIP_NODE* node, /**< node */
202 unsigned int id /**< unique id */
203 );
204
205/** counts the number of bound changes due to branching, constraint propagation, and propagation */
206SCIP_EXPORT
208 SCIP_NODE* node, /**< node */
209 int* nbranchings, /**< pointer to store number of branchings (or NULL if not needed) */
210 int* nconsprop, /**< pointer to store number of constraint propagations (or NULL if not needed) */
211 int* nprop /**< pointer to store number of propagations (or NULL if not needed) */
212 );
213
214/** gets the domain change information of the node, i.e., the information about the differences in the
215 * variables domains to the parent node
216 */
217SCIP_EXPORT
219 SCIP_NODE* node /**< node */
220 );
221
222/** gets the parent node of a node in the branch-and-bound tree, if any */
223SCIP_EXPORT
225 SCIP_NODE* node /**< node */
226 );
227
228/** returns all constraints added to a given node */
229SCIP_EXPORT
231 SCIP_NODE* node, /**< node */
232 SCIP_CONS** addedconss, /**< array to store the constraints */
233 int* naddedconss, /**< number of added constraints */
234 int addedconsssize /**< size of the constraint array */
235 );
236
237/** returns the number of added constraints to the given node */
238SCIP_EXPORT
240 SCIP_NODE* node
241 );
242
243/** returns whether node is in the path to the current node */
244SCIP_EXPORT
246 SCIP_NODE* node /**< node */
247 );
248
249/** returns whether the node is marked to be propagated again */
250SCIP_EXPORT
252 SCIP_NODE* node /**< node data */
253 );
254
255/* returns the set of changed constraints for a particular node */
256SCIP_EXPORT
258 SCIP_NODE* node /**< node data */
259 );
260
261
262#ifdef NDEBUG
263
264/* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
265 * speed up the algorithms.
266 */
267
268#define SCIPnodeGetType(node) ((SCIP_NODETYPE)(node)->nodetype)
269#define SCIPnodeGetNumber(node) ((node)->number)
270#define SCIPnodeGetDepth(node) ((int) (node)->depth)
271#define SCIPnodeGetLowerbound(node) ((node)->lowerbound)
272#define SCIPnodeGetEstimate(node) ((node)->estimate)
273#define SCIPnodeGetDomchg(node) ((node)->domchg)
274#define SCIPnodeGetParent(node) ((node)->parent)
275#define SCIPnodeIsActive(node) ((node)->active)
276#define SCIPnodeIsPropagatedAgain(node) ((node)->reprop)
277#define SCIPnodeGetConssetchg(node) ((node)->conssetchg)
278
279#endif
280
281/** @} */
282
283#ifdef __cplusplus
284}
285#endif
286
287#endif
common defines and data types used in all packages of SCIP
#define SCIP_Longint
Definition: def.h:158
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define nnodes
Definition: gastrans.c:74
void SCIPnodeGetAncestorBranchings(SCIP_NODE *node, SCIP_VAR **branchvars, SCIP_Real *branchbounds, SCIP_BOUNDTYPE *boundtypes, int *nbranchvars, int branchvarssize)
Definition: tree.c:7847
void SCIPnodeSetReopttype(SCIP_NODE *node, SCIP_REOPTTYPE reopttype)
Definition: tree.c:7543
void SCIPnodeSetReoptID(SCIP_NODE *node, unsigned int id)
Definition: tree.c:7574
void SCIPnodeGetAncestorBranchingsPart(SCIP_NODE *node, SCIP_NODE *parent, SCIP_VAR **branchvars, SCIP_Real *branchbounds, SCIP_BOUNDTYPE *boundtypes, int *nbranchvars, int branchvarssize)
Definition: tree.c:7884
void SCIPnodeGetParentBranchings(SCIP_NODE *node, SCIP_VAR **branchvars, SCIP_Real *branchbounds, SCIP_BOUNDTYPE *boundtypes, int *nbranchvars, int branchvarssize)
Definition: tree.c:7783
SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
Definition: tree.c:7483
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7513
void SCIPnodeGetAncestorBranchingPath(SCIP_NODE *node, SCIP_VAR **branchvars, SCIP_Real *branchbounds, SCIP_BOUNDTYPE *boundtypes, int *nbranchvars, int branchvarssize, int *nodeswitches, int *nnodes, int nodeswitchsize)
Definition: tree.c:8143
void SCIPnodeGetNDomchg(SCIP_NODE *node, int *nbranchings, int *nconsprop, int *nprop)
Definition: tree.c:7598
SCIP_NODE * SCIPnodesGetCommonAncestor(SCIP_NODE *node1, SCIP_NODE *node2)
Definition: tree.c:8216
SCIP_Bool SCIPnodeIsActive(SCIP_NODE *node)
Definition: tree.c:8247
SCIP_DOMCHG * SCIPnodeGetDomchg(SCIP_NODE *node)
Definition: tree.c:7588
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7493
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7773
SCIP_Bool SCIPnodesSharePath(SCIP_NODE *node1, SCIP_NODE *node2)
Definition: tree.c:8192
int SCIPnodeGetNAddedConss(SCIP_NODE *node)
Definition: tree.c:1721
SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
Definition: tree.c:7523
void SCIPnodeGetAddedConss(SCIP_NODE *node, SCIP_CONS **addedconss, int *naddedconss, int addedconsssize)
Definition: tree.c:1691
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7503
SCIP_REOPTTYPE SCIPnodeGetReopttype(SCIP_NODE *node)
Definition: tree.c:7533
unsigned int SCIPnodeGetReoptID(SCIP_NODE *node)
Definition: tree.c:7564
SCIP_Bool SCIPnodeIsPropagatedAgain(SCIP_NODE *node)
Definition: tree.c:8257
SCIP_RETCODE SCIPnodePrintAncestorBranchings(SCIP_NODE *node, FILE *file)
Definition: tree.c:8091
SCIP_DECL_SORTPTRCOMP(SCIPnodeCompLowerbound)
Definition: tree.c:154
SCIP_CONSSETCHG * SCIPnodeGetConssetchg(SCIP_NODE *node)
Definition: tree.c:8267
data structures for branch and bound tree
type definitions for constraints and constraint handlers
type definitions for LP management
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
type definitions for miscellaneous datastructures
type definitions for collecting reoptimization information
enum SCIP_ReoptType SCIP_REOPTTYPE
Definition: type_reopt.h:67
type definitions for return codes for SCIP methods
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type definitions for branch and bound tree
enum SCIP_NodeType SCIP_NODETYPE
Definition: type_tree.h:53
type definitions for problem variables