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-2023 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
50 extern "C" {
51 #endif
52 
53 /*
54  * Node methods
55  */
56 
57 /**@addtogroup PublicNodeMethods
58  *
59  * @{
60  */
61 
62 /** node comparator for best lower bound */
63 SCIP_EXPORT
64 SCIP_DECL_SORTPTRCOMP(SCIPnodeCompLowerbound);
65 
66 /** returns the set of variable branchings that were performed in the parent node to create this node */
67 SCIP_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 */
79 SCIP_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. */
91 SCIP_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 */
104 SCIP_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  */
113 SCIP_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 */
132 SCIP_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 */
139 SCIP_EXPORT
141  SCIP_NODE* node1, /**< node data */
142  SCIP_NODE* node2 /**< node data */
143  );
144 
145 
146 /** gets the type of the node */
147 SCIP_EXPORT
149  SCIP_NODE* node /**< node */
150  );
151 
152 /** gets successively assigned number of the node */
153 SCIP_EXPORT
155  SCIP_NODE* node /**< node */
156  );
157 
158 /** gets the depth of the node */
159 SCIP_EXPORT
160 int SCIPnodeGetDepth(
161  SCIP_NODE* node /**< node */
162  );
163 
164 /** gets the lower bound of the node */
165 SCIP_EXPORT
167  SCIP_NODE* node /**< node */
168  );
169 
170 /** gets the estimated value of the best feasible solution in subtree of the node */
171 SCIP_EXPORT
173  SCIP_NODE* node /**< node */
174  );
175 
176 
177 /** gets the reoptimization type of a node */
178 SCIP_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  */
186 SCIP_EXPORT
187 unsigned int SCIPnodeGetReoptID(
188  SCIP_NODE* node /**< node */
189  );
190 
191 /** sets the reoptimization type of the node */
192 SCIP_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 */
199 SCIP_EXPORT
200 void SCIPnodeSetReoptID(
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 */
206 SCIP_EXPORT
207 void SCIPnodeGetNDomchg(
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  */
217 SCIP_EXPORT
219  SCIP_NODE* node /**< node */
220  );
221 
222 /** gets the parent node of a node in the branch-and-bound tree, if any */
223 SCIP_EXPORT
225  SCIP_NODE* node /**< node */
226  );
227 
228 /** returns all constraints added to a given node */
229 SCIP_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 */
238 SCIP_EXPORT
240  SCIP_NODE* node
241  );
242 
243 /** returns whether node is in the path to the current node */
244 SCIP_EXPORT
246  SCIP_NODE* node /**< node */
247  );
248 
249 /** returns whether the node is marked to be propagated again */
250 SCIP_EXPORT
252  SCIP_NODE* node /**< node data */
253  );
254 
255 /* returns the set of changed constraints for a particular node */
256 SCIP_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
SCIP_DECL_SORTPTRCOMP(SCIPnodeCompLowerbound)
Definition: tree.c:154
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
void SCIPnodeGetParentBranchings(SCIP_NODE *node, SCIP_VAR **branchvars, SCIP_Real *branchbounds, SCIP_BOUNDTYPE *boundtypes, int *nbranchvars, int branchvarssize)
Definition: tree.c:7734
type definitions for miscellaneous datastructures
SCIP_NODE * SCIPnodesGetCommonAncestor(SCIP_NODE *node1, SCIP_NODE *node2)
Definition: tree.c:8168
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7464
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7724
void SCIPnodeSetReoptID(SCIP_NODE *node, unsigned int id)
Definition: tree.c:7525
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type definitions for return codes for SCIP methods
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7454
type definitions for collecting reoptimization information
void SCIPnodeGetAncestorBranchings(SCIP_NODE *node, SCIP_VAR **branchvars, SCIP_Real *branchbounds, SCIP_BOUNDTYPE *boundtypes, int *nbranchvars, int branchvarssize)
Definition: tree.c:7798
type definitions for LP management
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7444
SCIP_REOPTTYPE SCIPnodeGetReopttype(SCIP_NODE *node)
Definition: tree.c:7484
SCIP_Bool SCIPnodesSharePath(SCIP_NODE *node1, SCIP_NODE *node2)
Definition: tree.c:8144
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:8095
void SCIPnodeGetNDomchg(SCIP_NODE *node, int *nbranchings, int *nconsprop, int *nprop)
Definition: tree.c:7549
SCIP_RETCODE SCIPnodePrintAncestorBranchings(SCIP_NODE *node, FILE *file)
Definition: tree.c:8043
void SCIPnodeGetAncestorBranchingsPart(SCIP_NODE *node, SCIP_NODE *parent, SCIP_VAR **branchvars, SCIP_Real *branchbounds, SCIP_BOUNDTYPE *boundtypes, int *nbranchvars, int branchvarssize)
Definition: tree.c:7835
SCIP_Bool SCIPnodeIsPropagatedAgain(SCIP_NODE *node)
Definition: tree.c:8209
SCIP_DOMCHG * SCIPnodeGetDomchg(SCIP_NODE *node)
Definition: tree.c:7539
enum SCIP_ReoptType SCIP_REOPTTYPE
Definition: type_reopt.h:67
data structures for branch and bound tree
type definitions for problem variables
SCIP_CONSSETCHG * SCIPnodeGetConssetchg(SCIP_NODE *node)
Definition: tree.c:8219
#define SCIP_Bool
Definition: def.h:93
type definitions for branch and bound tree
SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
Definition: tree.c:7474
enum SCIP_NodeType SCIP_NODETYPE
Definition: type_tree.h:53
unsigned int SCIPnodeGetReoptID(SCIP_NODE *node)
Definition: tree.c:7515
SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
Definition: tree.c:7434
#define SCIP_Real
Definition: def.h:186
SCIP_Bool SCIPnodeIsActive(SCIP_NODE *node)
Definition: tree.c:8199
#define SCIP_Longint
Definition: def.h:171
int SCIPnodeGetNAddedConss(SCIP_NODE *node)
Definition: tree.c:1711
void SCIPnodeSetReopttype(SCIP_NODE *node, SCIP_REOPTTYPE reopttype)
Definition: tree.c:7494
#define nnodes
Definition: gastrans.c:74
common defines and data types used in all packages of SCIP
void SCIPnodeGetAddedConss(SCIP_NODE *node, SCIP_CONS **addedconss, int *naddedconss, int addedconsssize)
Definition: tree.c:1681
type definitions for constraints and constraint handlers