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-2014 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 
32 #ifdef NDEBUG
33 #include "scip/struct_tree.h"
34 #endif
35 
36 #ifdef __cplusplus
37 extern "C" {
38 #endif
39 
40 /*
41  * Node methods
42  */
43 
44 /** node comparator for best lower bound */
45 extern
46 SCIP_DECL_SORTPTRCOMP(SCIPnodeCompLowerbound);
47 
48 /** returns the set of variable branchings that were performed in the parent node to create this node */
49 extern
50 void SCIPnodeGetParentBranchings(
51  SCIP_NODE* node, /**< node data */
52  SCIP_VAR** branchvars, /**< array of variables on which the branching has been performed in the parent node */
53  SCIP_Real* branchbounds, /**< array of bounds which the branching in the parent node set */
54  SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branching in the parent node set */
55  int* nbranchvars, /**< number of variables on which branching has been performed in the parent node
56  * if this is larger than the array size, arrays should be reallocated and method should be called again */
57  int branchvarssize /**< available slots in arrays */
58  );
59 
60 /** returns the set of variable branchings that were performed in all ancestor nodes (nodes on the path to the root) to create this node */
61 extern
62 void SCIPnodeGetAncestorBranchings(
63  SCIP_NODE* node, /**< node data */
64  SCIP_VAR** branchvars, /**< array of variables on which the branchings has been performed in all ancestors */
65  SCIP_Real* branchbounds, /**< array of bounds which the branchings in all ancestors set */
66  SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branchings in all ancestors set */
67  int* nbranchvars, /**< number of variables on which branchings have been performed in all ancestors
68  * if this is larger than the array size, arrays should be reallocated and method should be called again */
69  int branchvarssize /**< available slots in arrays */
70  );
71 
72 /** outputs the path into given file stream in GML format */
73 extern
74 SCIP_RETCODE SCIPnodePrintAncestorBranchings(
75  SCIP_NODE* node, /**< node data */
76  FILE* file /**< file to output the path */
77  );
78 
79 /** returns the set of variable branchings that were performed in all ancestor nodes (nodes on the path to the root) to create this node
80  * sorted by the nodes, starting from the current node going up to the root
81  */
82 extern
83 void SCIPnodeGetAncestorBranchingPath(
84  SCIP_NODE* node, /**< node data */
85  SCIP_VAR** branchvars, /**< array of variables on which the branchings has been performed in all ancestors */
86  SCIP_Real* branchbounds, /**< array of bounds which the branchings in all ancestors set */
87  SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branchings in all ancestors set */
88  int* nbranchvars, /**< number of variables on which branchings have been performed in all ancestors
89  * if this is larger than the array size, arrays should be reallocated and method
90  * should be called again */
91  int branchvarssize, /**< available slots in arrays */
92  int* nodeswitches, /**< marks, where in the arrays the branching decisions of the next node on the path
93  * start; branchings performed at the parent of node always start at position 0.
94  * For single variable branching, nodeswitches[i] = i holds */
95  int* nnodes, /**< number of nodes in the nodeswitch array */
96  int nodeswitchsize /**< available slots in node switch array */
97  );
98 
99 
100 /** checks for two nodes whether they share the same root path, i.e., whether one is an ancestor of the other */
101 extern
102 SCIP_Bool SCIPnodesSharePath(
103  SCIP_NODE* node1, /**< node data */
104  SCIP_NODE* node2 /**< node data */
105  );
106 
107 /** finds the common ancestor node of two given nodes */
108 extern
109 SCIP_NODE* SCIPnodesGetCommonAncestor(
110  SCIP_NODE* node1, /**< node data */
111  SCIP_NODE* node2 /**< node data */
112  );
113 
114 
115 /** gets the type of the node */
116 extern
117 SCIP_NODETYPE SCIPnodeGetType(
118  SCIP_NODE* node /**< node */
119  );
120 
121 /** gets successively assigned number of the node */
122 extern
123 SCIP_Longint SCIPnodeGetNumber(
124  SCIP_NODE* node /**< node */
125  );
126 
127 /** gets the depth of the node */
128 extern
129 int SCIPnodeGetDepth(
130  SCIP_NODE* node /**< node */
131  );
132 
133 /** gets the lower bound of the node */
134 extern
135 SCIP_Real SCIPnodeGetLowerbound(
136  SCIP_NODE* node /**< node */
137  );
138 
139 /** gets the estimated value of the best feasible solution in subtree of the node */
140 extern
141 SCIP_Real SCIPnodeGetEstimate(
142  SCIP_NODE* node /**< node */
143  );
144 
145 /** gets the domain change information of the node, i.e., the information about the differences in the
146  * variables domains to the parent node
147  */
148 extern
149 SCIP_DOMCHG* SCIPnodeGetDomchg(
150  SCIP_NODE* node /**< node */
151  );
152 
153 /** gets the parent node of a node in the branch-and-bound tree, if any */
154 extern
155 SCIP_NODE* SCIPnodeGetParent(
156  SCIP_NODE* node /**< node */
157  );
158 
159 /** returns whether node is in the path to the current node */
160 extern
161 SCIP_Bool SCIPnodeIsActive(
162  SCIP_NODE* node /**< node */
163  );
164 
165 /** returns whether the node is marked to be propagated again */
166 extern
167 SCIP_Bool SCIPnodeIsPropagatedAgain(
168  SCIP_NODE* node /**< node data */
169  );
170 
171 
172 #ifdef NDEBUG
173 
174 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
175  * speed up the algorithms.
176  */
177 
178 #define SCIPnodeGetType(node) ((SCIP_NODETYPE)(node)->nodetype)
179 #define SCIPnodeGetNumber(node) ((node)->number)
180 #define SCIPnodeGetDepth(node) ((int) (node)->depth)
181 #define SCIPnodeGetLowerbound(node) ((node)->lowerbound)
182 #define SCIPnodeGetEstimate(node) ((node)->estimate)
183 #define SCIPnodeGetDomchg(node) ((node)->domchg)
184 #define SCIPnodeGetParent(node) ((node)->parent)
185 #define SCIPnodeIsActive(node) ((node)->active)
186 #define SCIPnodeIsPropagatedAgain(node) ((node)->reprop)
187 
188 #endif
189 
190 #ifdef __cplusplus
191 }
192 #endif
193 
194 #endif
195