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-2016 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 PUBLICMETHODS
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 /** node comparator for best lower bound */
46 extern
47 SCIP_DECL_SORTPTRCOMP(SCIPnodeCompLowerbound);
48 
49 /** returns the set of variable branchings that were performed in the parent node to create this node */
50 extern
52  SCIP_NODE* node, /**< node data */
53  SCIP_VAR** branchvars, /**< array of variables on which the branching has been performed in the parent node */
54  SCIP_Real* branchbounds, /**< array of bounds which the branching in the parent node set */
55  SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branching in the parent node set */
56  int* nbranchvars, /**< number of variables on which branching has been performed in the parent node
57  * if this is larger than the array size, arrays should be reallocated and method should be called again */
58  int branchvarssize /**< available slots in arrays */
59  );
60 
61 /** returns the set of variable branchings that were performed in all ancestor nodes (nodes on the path to the root) to create this node */
62 extern
64  SCIP_NODE* node, /**< node data */
65  SCIP_VAR** branchvars, /**< array of variables on which the branchings has been performed in all ancestors */
66  SCIP_Real* branchbounds, /**< array of bounds which the branchings in all ancestors set */
67  SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branchings in all ancestors set */
68  int* nbranchvars, /**< number of variables on which branchings have been performed in all ancestors
69  * if this is larger than the array size, arrays should be reallocated and method should be called again */
70  int branchvarssize /**< available slots in arrays */
71  );
72 
73 /** returns the set of variable branchings that were performed between the given @p node and the given @p parent node. */
74 extern
76  SCIP_NODE* node, /**< node data */
77  SCIP_NODE* parent, /**< node data */
78  SCIP_VAR** branchvars, /**< array of variables on which the branchings has been performed in all ancestors */
79  SCIP_Real* branchbounds, /**< array of bounds which the branchings in all ancestors set */
80  SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branchings in all ancestors set */
81  int* nbranchvars, /**< number of variables on which branchings have been performed in all ancestors
82  * if this is larger than the array size, arrays should be reallocated and method should be called again */
83  int branchvarssize /**< available slots in arrays */
84  );
85 
86 /** outputs the path into given file stream in GML format */
87 extern
89  SCIP_NODE* node, /**< node data */
90  FILE* file /**< file to output the path */
91  );
92 
93 /** returns the set of variable branchings that were performed in all ancestor nodes (nodes on the path to the root) to create this node
94  * sorted by the nodes, starting from the current node going up to the root
95  */
96 extern
98  SCIP_NODE* node, /**< node data */
99  SCIP_VAR** branchvars, /**< array of variables on which the branchings has been performed in all ancestors */
100  SCIP_Real* branchbounds, /**< array of bounds which the branchings in all ancestors set */
101  SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branchings in all ancestors set */
102  int* nbranchvars, /**< number of variables on which branchings have been performed in all ancestors
103  * if this is larger than the array size, arrays should be reallocated and method
104  * should be called again */
105  int branchvarssize, /**< available slots in arrays */
106  int* nodeswitches, /**< marks, where in the arrays the branching decisions of the next node on the path
107  * start; branchings performed at the parent of node always start at position 0.
108  * For single variable branching, nodeswitches[i] = i holds */
109  int* nnodes, /**< number of nodes in the nodeswitch array */
110  int nodeswitchsize /**< available slots in node switch array */
111  );
112 
113 
114 /** checks for two nodes whether they share the same root path, i.e., whether one is an ancestor of the other */
115 extern
117  SCIP_NODE* node1, /**< node data */
118  SCIP_NODE* node2 /**< node data */
119  );
120 
121 /** finds the common ancestor node of two given nodes */
122 extern
124  SCIP_NODE* node1, /**< node data */
125  SCIP_NODE* node2 /**< node data */
126  );
127 
128 
129 /** gets the type of the node */
130 extern
132  SCIP_NODE* node /**< node */
133  );
134 
135 /** gets successively assigned number of the node */
136 extern
138  SCIP_NODE* node /**< node */
139  );
140 
141 /** gets the depth of the node */
142 extern
143 int SCIPnodeGetDepth(
144  SCIP_NODE* node /**< node */
145  );
146 
147 /** gets the lower bound of the node */
148 extern
150  SCIP_NODE* node /**< node */
151  );
152 
153 /** gets the estimated value of the best feasible solution in subtree of the node */
154 extern
156  SCIP_NODE* node /**< node */
157  );
158 
159 
160 /** gets the reoptimization type of a node */
161 extern
163  SCIP_NODE* node /**< node */
164  );
165 
166 /** gets the unique id to identify the node during reoptimization; id is 0 if the node is the root or not part of the
167  * reoptimization tree
168  */
169 extern
170 unsigned int SCIPnodeGetReoptID(
171  SCIP_NODE* node /**< node */
172  );
173 
174 /** sets the reoptimization type of the node */
175 extern
177  SCIP_NODE* node, /**< node */
178  SCIP_REOPTTYPE type /**< reoptimization type */
179  );
180 
181 /** sets a unique id to identify the node during reoptimization */
182 extern
183 void SCIPnodeSetReoptID(
184  SCIP_NODE* node, /**< node */
185  unsigned int id /**< unique id */
186  );
187 
188 /** counts the number of bound changes due to branching, constraint propagation, and propagation */
189 extern
190 void SCIPnodeGetNDomchg(
191  SCIP_NODE* node, /**< node */
192  int* nbranchings, /**< pointer to store number of branchings (or NULL if not needed) */
193  int* nconsprop, /**< pointer to store number of constraint propagations (or NULL if not needed) */
194  int* nprop /**< pointer to store number of propagations (or NULL if not needed) */
195  );
196 
197 /** gets the domain change information of the node, i.e., the information about the differences in the
198  * variables domains to the parent node
199  */
200 extern
202  SCIP_NODE* node /**< node */
203  );
204 
205 /** gets the parent node of a node in the branch-and-bound tree, if any */
206 extern
208  SCIP_NODE* node /**< node */
209  );
210 
211 /** returns whether node is in the path to the current node */
212 extern
214  SCIP_NODE* node /**< node */
215  );
216 
217 /** returns whether the node is marked to be propagated again */
218 extern
220  SCIP_NODE* node /**< node data */
221  );
222 
223 
224 #ifdef NDEBUG
225 
226 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
227  * speed up the algorithms.
228  */
229 
230 #define SCIPnodeGetType(node) ((SCIP_NODETYPE)(node)->nodetype)
231 #define SCIPnodeGetNumber(node) ((node)->number)
232 #define SCIPnodeGetDepth(node) ((int) (node)->depth)
233 #define SCIPnodeGetLowerbound(node) ((node)->lowerbound)
234 #define SCIPnodeGetEstimate(node) ((node)->estimate)
235 #define SCIPnodeGetDomchg(node) ((node)->domchg)
236 #define SCIPnodeGetParent(node) ((node)->parent)
237 #define SCIPnodeIsActive(node) ((node)->active)
238 #define SCIPnodeIsPropagatedAgain(node) ((node)->reprop)
239 
240 #endif
241 
242 #ifdef __cplusplus
243 }
244 #endif
245 
246 #endif
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
unsigned int SCIPnodeGetReoptID(SCIP_NODE *node)
Definition: tree.c:7087
type definitions for miscellaneous datastructures
SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
Definition: tree.c:7006
void SCIPnodeSetReoptID(SCIP_NODE *node, unsigned int id)
Definition: tree.c:7097
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7026
SCIP_REOPTTYPE SCIPnodeGetReopttype(SCIP_NODE *node)
Definition: tree.c:7056
SCIP_DOMCHG * SCIPnodeGetDomchg(SCIP_NODE *node)
Definition: tree.c:7111
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
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:7658
SCIP_Bool SCIPnodeIsPropagatedAgain(SCIP_NODE *node)
Definition: tree.c:7772
type definitions for collecting reoptimization information
void SCIPnodeGetParentBranchings(SCIP_NODE *node, SCIP_VAR **branchvars, SCIP_Real *branchbounds, SCIP_BOUNDTYPE *boundtypes, int *nbranchvars, int branchvarssize)
Definition: tree.c:7297
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7016
void SCIPnodeSetReopttype(SCIP_NODE *node, SCIP_REOPTTYPE type)
Definition: tree.c:7066
enum SCIP_ReoptType SCIP_REOPTTYPE
Definition: type_reopt.h:56
datastructures for branch and bound tree
#define SCIP_Bool
Definition: def.h:53
void SCIPnodeGetNDomchg(SCIP_NODE *node, int *nbranchings, int *nconsprop, int *nprop)
Definition: tree.c:7121
type definitions for branch and bound tree
void SCIPnodeGetAncestorBranchings(SCIP_NODE *node, SCIP_VAR **branchvars, SCIP_Real *branchbounds, SCIP_BOUNDTYPE *boundtypes, int *nbranchvars, int branchvarssize)
Definition: tree.c:7361
SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
Definition: tree.c:7046
enum SCIP_NodeType SCIP_NODETYPE
Definition: type_tree.h:44
SCIP_Bool SCIPnodesSharePath(SCIP_NODE *node1, SCIP_NODE *node2)
Definition: tree.c:7707
SCIP_Bool SCIPnodeIsActive(SCIP_NODE *node)
Definition: tree.c:7762
#define SCIP_Real
Definition: def.h:127
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7287
#define SCIP_Longint
Definition: def.h:112
void SCIPnodeGetAncestorBranchingsPart(SCIP_NODE *node, SCIP_NODE *parent, SCIP_VAR **branchvars, SCIP_Real *branchbounds, SCIP_BOUNDTYPE *boundtypes, int *nbranchvars, int branchvarssize)
Definition: tree.c:7398
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7036
SCIP_NODE * SCIPnodesGetCommonAncestor(SCIP_NODE *node1, SCIP_NODE *node2)
Definition: tree.c:7731
common defines and data types used in all packages of SCIP
SCIP_RETCODE SCIPnodePrintAncestorBranchings(SCIP_NODE *node, FILE *file)
Definition: tree.c:7606
SCIP_DECL_SORTPTRCOMP(SCIPnodeCompLowerbound)
Definition: tree.c:140