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-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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file pub_tree.h
17  * @ingroup PUBLICCOREAPI
18  * @brief public methods for branch and bound tree
19  * @author Tobias Achterberg
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef __SCIP_PUB_TREE_H__
25 #define __SCIP_PUB_TREE_H__
26 
27 
28 #include "scip/def.h"
29 #include "scip/type_misc.h"
30 #include "scip/type_tree.h"
31 #include "scip/type_reopt.h"
32 
33 #ifdef NDEBUG
34 #include "scip/struct_tree.h"
35 #endif
36 
37 #ifdef __cplusplus
38 extern "C" {
39 #endif
40 
41 /*
42  * Node methods
43  */
44 
45 /**@addtogroup PublicNodeMethods
46  *
47  * @{
48  */
49 
50 /** node comparator for best lower bound */
51 extern
52 SCIP_DECL_SORTPTRCOMP(SCIPnodeCompLowerbound);
53 
54 /** returns the set of variable branchings that were performed in the parent node to create this node */
55 extern
57  SCIP_NODE* node, /**< node data */
58  SCIP_VAR** branchvars, /**< array of variables on which the branching has been performed in the parent node */
59  SCIP_Real* branchbounds, /**< array of bounds which the branching in the parent node set */
60  SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branching in the parent node set */
61  int* nbranchvars, /**< number of variables on which branching has been performed in the parent node
62  * if this is larger than the array size, arrays should be reallocated and method should be called again */
63  int branchvarssize /**< available slots in arrays */
64  );
65 
66 /** returns the set of variable branchings that were performed in all ancestor nodes (nodes on the path to the root) to create this node */
67 extern
69  SCIP_NODE* node, /**< node data */
70  SCIP_VAR** branchvars, /**< array of variables on which the branchings has been performed in all ancestors */
71  SCIP_Real* branchbounds, /**< array of bounds which the branchings in all ancestors set */
72  SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branchings in all ancestors set */
73  int* nbranchvars, /**< number of variables on which branchings have been performed in all ancestors
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 between the given @p node and the given @p parent node. */
79 extern
81  SCIP_NODE* node, /**< node data */
82  SCIP_NODE* parent, /**< node data */
83  SCIP_VAR** branchvars, /**< array of variables on which the branchings has been performed in all ancestors */
84  SCIP_Real* branchbounds, /**< array of bounds which the branchings in all ancestors set */
85  SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branchings in all ancestors set */
86  int* nbranchvars, /**< number of variables on which branchings have been performed in all ancestors
87  * if this is larger than the array size, arrays should be reallocated and method should be called again */
88  int branchvarssize /**< available slots in arrays */
89  );
90 
91 /** outputs the path into given file stream in GML format */
92 extern
94  SCIP_NODE* node, /**< node data */
95  FILE* file /**< file to output the path */
96  );
97 
98 /** returns the set of variable branchings that were performed in all ancestor nodes (nodes on the path to the root) to create this node
99  * sorted by the nodes, starting from the current node going up to the root
100  */
101 extern
103  SCIP_NODE* node, /**< node data */
104  SCIP_VAR** branchvars, /**< array of variables on which the branchings has been performed in all ancestors */
105  SCIP_Real* branchbounds, /**< array of bounds which the branchings in all ancestors set */
106  SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branchings in all ancestors set */
107  int* nbranchvars, /**< number of variables on which branchings have been performed in all ancestors
108  * if this is larger than the array size, arrays should be reallocated and method
109  * should be called again */
110  int branchvarssize, /**< available slots in arrays */
111  int* nodeswitches, /**< marks, where in the arrays the branching decisions of the next node on the path
112  * start; branchings performed at the parent of node always start at position 0.
113  * For single variable branching, nodeswitches[i] = i holds */
114  int* nnodes, /**< number of nodes in the nodeswitch array */
115  int nodeswitchsize /**< available slots in node switch array */
116  );
117 
118 
119 /** checks for two nodes whether they share the same root path, i.e., whether one is an ancestor of the other */
120 extern
122  SCIP_NODE* node1, /**< node data */
123  SCIP_NODE* node2 /**< node data */
124  );
125 
126 /** finds the common ancestor node of two given nodes */
127 extern
129  SCIP_NODE* node1, /**< node data */
130  SCIP_NODE* node2 /**< node data */
131  );
132 
133 
134 /** gets the type of the node */
135 extern
137  SCIP_NODE* node /**< node */
138  );
139 
140 /** gets successively assigned number of the node */
141 extern
143  SCIP_NODE* node /**< node */
144  );
145 
146 /** gets the depth of the node */
147 extern
148 int SCIPnodeGetDepth(
149  SCIP_NODE* node /**< node */
150  );
151 
152 /** gets the lower bound of the node */
153 extern
155  SCIP_NODE* node /**< node */
156  );
157 
158 /** gets the estimated value of the best feasible solution in subtree of the node */
159 extern
161  SCIP_NODE* node /**< node */
162  );
163 
164 
165 /** gets the reoptimization type of a node */
166 extern
168  SCIP_NODE* node /**< node */
169  );
170 
171 /** gets the unique id to identify the node during reoptimization; id is 0 if the node is the root or not part of the
172  * reoptimization tree
173  */
174 extern
175 unsigned int SCIPnodeGetReoptID(
176  SCIP_NODE* node /**< node */
177  );
178 
179 /** sets the reoptimization type of the node */
180 extern
182  SCIP_NODE* node, /**< node */
183  SCIP_REOPTTYPE reopttype /**< reoptimization type */
184  );
185 
186 /** sets a unique id to identify the node during reoptimization */
187 extern
188 void SCIPnodeSetReoptID(
189  SCIP_NODE* node, /**< node */
190  unsigned int id /**< unique id */
191  );
192 
193 /** counts the number of bound changes due to branching, constraint propagation, and propagation */
194 extern
195 void SCIPnodeGetNDomchg(
196  SCIP_NODE* node, /**< node */
197  int* nbranchings, /**< pointer to store number of branchings (or NULL if not needed) */
198  int* nconsprop, /**< pointer to store number of constraint propagations (or NULL if not needed) */
199  int* nprop /**< pointer to store number of propagations (or NULL if not needed) */
200  );
201 
202 /** gets the domain change information of the node, i.e., the information about the differences in the
203  * variables domains to the parent node
204  */
205 extern
207  SCIP_NODE* node /**< node */
208  );
209 
210 /** gets the parent node of a node in the branch-and-bound tree, if any */
211 extern
213  SCIP_NODE* node /**< node */
214  );
215 
216 /** returns whether node is in the path to the current node */
217 extern
219  SCIP_NODE* node /**< node */
220  );
221 
222 /** returns whether the node is marked to be propagated again */
223 extern
225  SCIP_NODE* node /**< node data */
226  );
227 
228 /* returns the set of changed constraints for a particular node */
229 extern
231  SCIP_NODE* node /**< node data */
232  );
233 
234 
235 #ifdef NDEBUG
236 
237 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
238  * speed up the algorithms.
239  */
240 
241 #define SCIPnodeGetType(node) ((SCIP_NODETYPE)(node)->nodetype)
242 #define SCIPnodeGetNumber(node) ((node)->number)
243 #define SCIPnodeGetDepth(node) ((int) (node)->depth)
244 #define SCIPnodeGetLowerbound(node) ((node)->lowerbound)
245 #define SCIPnodeGetEstimate(node) ((node)->estimate)
246 #define SCIPnodeGetDomchg(node) ((node)->domchg)
247 #define SCIPnodeGetParent(node) ((node)->parent)
248 #define SCIPnodeIsActive(node) ((node)->active)
249 #define SCIPnodeIsPropagatedAgain(node) ((node)->reprop)
250 #define SCIPnodeGetConssetchg(node) ((node)->conssetchg)
251 
252 #endif
253 
254 /* @} */
255 
256 #ifdef __cplusplus
257 }
258 #endif
259 
260 #endif
SCIP_DECL_SORTPTRCOMP(SCIPnodeCompLowerbound)
Definition: tree.c:142
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
void SCIPnodeGetParentBranchings(SCIP_NODE *node, SCIP_VAR **branchvars, SCIP_Real *branchbounds, SCIP_BOUNDTYPE *boundtypes, int *nbranchvars, int branchvarssize)
Definition: tree.c:7632
type definitions for miscellaneous datastructures
SCIP_NODE * SCIPnodesGetCommonAncestor(SCIP_NODE *node1, SCIP_NODE *node2)
Definition: tree.c:8066
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7362
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7622
void SCIPnodeSetReoptID(SCIP_NODE *node, unsigned int id)
Definition: tree.c:7423
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7352
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:7696
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7342
SCIP_REOPTTYPE SCIPnodeGetReopttype(SCIP_NODE *node)
Definition: tree.c:7382
SCIP_Bool SCIPnodesSharePath(SCIP_NODE *node1, SCIP_NODE *node2)
Definition: tree.c:8042
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:7993
void SCIPnodeGetNDomchg(SCIP_NODE *node, int *nbranchings, int *nconsprop, int *nprop)
Definition: tree.c:7447
SCIP_RETCODE SCIPnodePrintAncestorBranchings(SCIP_NODE *node, FILE *file)
Definition: tree.c:7941
void SCIPnodeGetAncestorBranchingsPart(SCIP_NODE *node, SCIP_NODE *parent, SCIP_VAR **branchvars, SCIP_Real *branchbounds, SCIP_BOUNDTYPE *boundtypes, int *nbranchvars, int branchvarssize)
Definition: tree.c:7733
SCIP_Bool SCIPnodeIsPropagatedAgain(SCIP_NODE *node)
Definition: tree.c:8107
SCIP_DOMCHG * SCIPnodeGetDomchg(SCIP_NODE *node)
Definition: tree.c:7437
enum SCIP_ReoptType SCIP_REOPTTYPE
Definition: type_reopt.h:58
data structures for branch and bound tree
SCIP_CONSSETCHG * SCIPnodeGetConssetchg(SCIP_NODE *node)
Definition: tree.c:8117
#define SCIP_Bool
Definition: def.h:61
type definitions for branch and bound tree
SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
Definition: tree.c:7372
enum SCIP_NodeType SCIP_NODETYPE
Definition: type_tree.h:44
unsigned int SCIPnodeGetReoptID(SCIP_NODE *node)
Definition: tree.c:7413
SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
Definition: tree.c:7332
#define SCIP_Real
Definition: def.h:149
SCIP_Bool SCIPnodeIsActive(SCIP_NODE *node)
Definition: tree.c:8097
#define SCIP_Longint
Definition: def.h:134
void SCIPnodeSetReopttype(SCIP_NODE *node, SCIP_REOPTTYPE reopttype)
Definition: tree.c:7392
#define nnodes
Definition: gastrans.c:65
common defines and data types used in all packages of SCIP