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
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
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
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
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
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
110  SCIP_NODE* node1, /**< node data */
111  SCIP_NODE* node2 /**< node data */
112  );
113 
114 
115 /** gets the type of the node */
116 extern
118  SCIP_NODE* node /**< node */
119  );
120 
121 /** gets successively assigned number of the node */
122 extern
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
136  SCIP_NODE* node /**< node */
137  );
138 
139 /** gets the estimated value of the best feasible solution in subtree of the node */
140 extern
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
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
156  SCIP_NODE* node /**< node */
157  );
158 
159 /** returns whether node is in the path to the current node */
160 extern
162  SCIP_NODE* node /**< node */
163  );
164 
165 /** returns whether the node is marked to be propagated again */
166 extern
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
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
type definitions for miscellaneous datastructures
SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
int SCIPnodeGetDepth(SCIP_NODE *node)
union SCIP_DomChg SCIP_DOMCHG
Definition: type_var.h:81
SCIP_DOMCHG * SCIPnodeGetDomchg(SCIP_NODE *node)
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)
SCIP_Bool SCIPnodeIsPropagatedAgain(SCIP_NODE *node)
void SCIPnodeGetParentBranchings(SCIP_NODE *node, SCIP_VAR **branchvars, SCIP_Real *branchbounds, SCIP_BOUNDTYPE *boundtypes, int *nbranchvars, int branchvarssize)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
#define SCIP_Bool
Definition: def.h:49
type definitions for branch and bound tree
struct SCIP_Var SCIP_VAR
Definition: type_var.h:95
void SCIPnodeGetAncestorBranchings(SCIP_NODE *node, SCIP_VAR **branchvars, SCIP_Real *branchbounds, SCIP_BOUNDTYPE *boundtypes, int *nbranchvars, int branchvarssize)
SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
enum SCIP_NodeType SCIP_NODETYPE
Definition: type_tree.h:44
SCIP_Bool SCIPnodesSharePath(SCIP_NODE *node1, SCIP_NODE *node2)
SCIP_Bool SCIPnodeIsActive(SCIP_NODE *node)
#define SCIP_Real
Definition: def.h:123
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
#define SCIP_Longint
Definition: def.h:107
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
SCIP_NODE * SCIPnodesGetCommonAncestor(SCIP_NODE *node1, SCIP_NODE *node2)
common defines and data types used in all packages of SCIP
SCIP_RETCODE SCIPnodePrintAncestorBranchings(SCIP_NODE *node, FILE *file)
SCIP_DECL_SORTPTRCOMP(SCIPnodeCompLowerbound)
struct SCIP_Node SCIP_NODE
Definition: type_tree.h:54