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-2021 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 visit scipopt.org. */
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 #include "scip/def.h"
28 #include "scip/type_cons.h"
29 #include "scip/type_lp.h"
30 #include "scip/type_misc.h"
31 #include "scip/type_reopt.h"
32 #include "scip/type_retcode.h"
33 #include "scip/type_tree.h"
34 #include "scip/type_var.h"
35 
36 #ifdef NDEBUG
37 #include "scip/struct_tree.h"
38 #endif
39 
40 #ifdef __cplusplus
41 extern "C" {
42 #endif
43 
44 /*
45  * Node methods
46  */
47 
48 /**@addtogroup PublicNodeMethods
49  *
50  * @{
51  */
52 
53 /** node comparator for best lower bound */
55 SCIP_DECL_SORTPTRCOMP(SCIPnodeCompLowerbound);
56 
57 /** returns the set of variable branchings that were performed in the parent node to create this node */
60  SCIP_NODE* node, /**< node data */
61  SCIP_VAR** branchvars, /**< array of variables on which the branching has been performed in the parent node */
62  SCIP_Real* branchbounds, /**< array of bounds which the branching in the parent node set */
63  SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branching in the parent node set */
64  int* nbranchvars, /**< number of variables on which branching has been performed in the parent node
65  * if this is larger than the array size, arrays should be reallocated and method should be called again */
66  int branchvarssize /**< available slots in arrays */
67  );
68 
69 /** returns the set of variable branchings that were performed in all ancestor nodes (nodes on the path to the root) to create this node */
72  SCIP_NODE* node, /**< node data */
73  SCIP_VAR** branchvars, /**< array of variables on which the branchings has been performed in all ancestors */
74  SCIP_Real* branchbounds, /**< array of bounds which the branchings in all ancestors set */
75  SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branchings in all ancestors set */
76  int* nbranchvars, /**< number of variables on which branchings have been performed in all ancestors
77  * if this is larger than the array size, arrays should be reallocated and method should be called again */
78  int branchvarssize /**< available slots in arrays */
79  );
80 
81 /** returns the set of variable branchings that were performed between the given @p node and the given @p parent node. */
84  SCIP_NODE* node, /**< node data */
85  SCIP_NODE* parent, /**< node data */
86  SCIP_VAR** branchvars, /**< array of variables on which the branchings has been performed in all ancestors */
87  SCIP_Real* branchbounds, /**< array of bounds which the branchings in all ancestors set */
88  SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branchings in all ancestors set */
89  int* nbranchvars, /**< number of variables on which branchings have been performed in all ancestors
90  * if this is larger than the array size, arrays should be reallocated and method should be called again */
91  int branchvarssize /**< available slots in arrays */
92  );
93 
94 /** outputs the path into given file stream in GML format */
97  SCIP_NODE* node, /**< node data */
98  FILE* file /**< file to output the path */
99  );
100 
101 /** returns the set of variable branchings that were performed in all ancestor nodes (nodes on the path to the root) to create this node
102  * sorted by the nodes, starting from the current node going up to the root
103  */
106  SCIP_NODE* node, /**< node data */
107  SCIP_VAR** branchvars, /**< array of variables on which the branchings has been performed in all ancestors */
108  SCIP_Real* branchbounds, /**< array of bounds which the branchings in all ancestors set */
109  SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branchings in all ancestors set */
110  int* nbranchvars, /**< number of variables on which branchings have been performed in all ancestors
111  * if this is larger than the array size, arrays should be reallocated and method
112  * should be called again */
113  int branchvarssize, /**< available slots in arrays */
114  int* nodeswitches, /**< marks, where in the arrays the branching decisions of the next node on the path
115  * start; branchings performed at the parent of node always start at position 0.
116  * For single variable branching, nodeswitches[i] = i holds */
117  int* nnodes, /**< number of nodes in the nodeswitch array */
118  int nodeswitchsize /**< available slots in node switch array */
119  );
120 
121 
122 /** checks for two nodes whether they share the same root path, i.e., whether one is an ancestor of the other */
125  SCIP_NODE* node1, /**< node data */
126  SCIP_NODE* node2 /**< node data */
127  );
128 
129 /** finds the common ancestor node of two given nodes */
132  SCIP_NODE* node1, /**< node data */
133  SCIP_NODE* node2 /**< node data */
134  );
135 
136 
137 /** gets the type of the node */
140  SCIP_NODE* node /**< node */
141  );
142 
143 /** gets successively assigned number of the node */
146  SCIP_NODE* node /**< node */
147  );
148 
149 /** gets the depth of the node */
151 int SCIPnodeGetDepth(
152  SCIP_NODE* node /**< node */
153  );
154 
155 /** gets the lower bound of the node */
158  SCIP_NODE* node /**< node */
159  );
160 
161 /** gets the estimated value of the best feasible solution in subtree of the node */
164  SCIP_NODE* node /**< node */
165  );
166 
167 
168 /** gets the reoptimization type of a node */
171  SCIP_NODE* node /**< node */
172  );
173 
174 /** gets the unique id to identify the node during reoptimization; id is 0 if the node is the root or not part of the
175  * reoptimization tree
176  */
178 unsigned int SCIPnodeGetReoptID(
179  SCIP_NODE* node /**< node */
180  );
181 
182 /** sets the reoptimization type of the node */
185  SCIP_NODE* node, /**< node */
186  SCIP_REOPTTYPE reopttype /**< reoptimization type */
187  );
188 
189 /** sets a unique id to identify the node during reoptimization */
191 void SCIPnodeSetReoptID(
192  SCIP_NODE* node, /**< node */
193  unsigned int id /**< unique id */
194  );
195 
196 /** counts the number of bound changes due to branching, constraint propagation, and propagation */
198 void SCIPnodeGetNDomchg(
199  SCIP_NODE* node, /**< node */
200  int* nbranchings, /**< pointer to store number of branchings (or NULL if not needed) */
201  int* nconsprop, /**< pointer to store number of constraint propagations (or NULL if not needed) */
202  int* nprop /**< pointer to store number of propagations (or NULL if not needed) */
203  );
204 
205 /** gets the domain change information of the node, i.e., the information about the differences in the
206  * variables domains to the parent node
207  */
210  SCIP_NODE* node /**< node */
211  );
212 
213 /** gets the parent node of a node in the branch-and-bound tree, if any */
216  SCIP_NODE* node /**< node */
217  );
218 
219 /** returns all constraints added to a given node */
222  SCIP_NODE* node, /**< node */
223  SCIP_CONS** addedconss, /**< array to store the constraints */
224  int* naddedconss, /**< number of added constraints */
225  int addedconsssize /**< size of the constraint array */
226  );
227 
228 /** returns the number of added constraints to the given node */
231  SCIP_NODE* node
232  );
233 
234 /** returns whether node is in the path to the current node */
237  SCIP_NODE* node /**< node */
238  );
239 
240 /** returns whether the node is marked to be propagated again */
243  SCIP_NODE* node /**< node data */
244  );
245 
246 /* returns the set of changed constraints for a particular node */
249  SCIP_NODE* node /**< node data */
250  );
251 
252 
253 #ifdef NDEBUG
254 
255 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
256  * speed up the algorithms.
257  */
258 
259 #define SCIPnodeGetType(node) ((SCIP_NODETYPE)(node)->nodetype)
260 #define SCIPnodeGetNumber(node) ((node)->number)
261 #define SCIPnodeGetDepth(node) ((int) (node)->depth)
262 #define SCIPnodeGetLowerbound(node) ((node)->lowerbound)
263 #define SCIPnodeGetEstimate(node) ((node)->estimate)
264 #define SCIPnodeGetDomchg(node) ((node)->domchg)
265 #define SCIPnodeGetParent(node) ((node)->parent)
266 #define SCIPnodeIsActive(node) ((node)->active)
267 #define SCIPnodeIsPropagatedAgain(node) ((node)->reprop)
268 #define SCIPnodeGetConssetchg(node) ((node)->conssetchg)
269 
270 #endif
271 
272 /** @} */
273 
274 #ifdef __cplusplus
275 }
276 #endif
277 
278 #endif
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
type definitions for miscellaneous datastructures
SCIP_EXPORT SCIP_CONSSETCHG * SCIPnodeGetConssetchg(SCIP_NODE *node)
Definition: tree.c:8213
SCIP_EXPORT SCIP_REOPTTYPE SCIPnodeGetReopttype(SCIP_NODE *node)
Definition: tree.c:7478
SCIP_EXPORT SCIP_NODE * SCIPnodesGetCommonAncestor(SCIP_NODE *node1, SCIP_NODE *node2)
Definition: tree.c:8162
SCIP_EXPORT SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7438
#define SCIP_EXPORT
Definition: def.h:100
SCIP_EXPORT int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7448
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_EXPORT void SCIPnodeSetReoptID(SCIP_NODE *node, unsigned int id)
Definition: tree.c:7519
type definitions for return codes for SCIP methods
SCIP_EXPORT SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7458
SCIP_EXPORT SCIP_Bool SCIPnodeIsPropagatedAgain(SCIP_NODE *node)
Definition: tree.c:8203
type definitions for collecting reoptimization information
SCIP_EXPORT SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7718
SCIP_EXPORT unsigned int SCIPnodeGetReoptID(SCIP_NODE *node)
Definition: tree.c:7509
SCIP_EXPORT void SCIPnodeGetAncestorBranchings(SCIP_NODE *node, SCIP_VAR **branchvars, SCIP_Real *branchbounds, SCIP_BOUNDTYPE *boundtypes, int *nbranchvars, int branchvarssize)
Definition: tree.c:7792
SCIP_EXPORT SCIP_DECL_SORTPTRCOMP(SCIPnodeCompLowerbound)
Definition: tree.c:145
type definitions for LP management
SCIP_EXPORT int SCIPnodeGetNAddedConss(SCIP_NODE *node)
Definition: tree.c:1702
SCIP_EXPORT SCIP_DOMCHG * SCIPnodeGetDomchg(SCIP_NODE *node)
Definition: tree.c:7533
SCIP_EXPORT void SCIPnodeSetReopttype(SCIP_NODE *node, SCIP_REOPTTYPE reopttype)
Definition: tree.c:7488
enum SCIP_ReoptType SCIP_REOPTTYPE
Definition: type_reopt.h:58
data structures for branch and bound tree
SCIP_EXPORT SCIP_RETCODE SCIPnodePrintAncestorBranchings(SCIP_NODE *node, FILE *file)
Definition: tree.c:8037
type definitions for problem variables
#define SCIP_Bool
Definition: def.h:70
SCIP_EXPORT SCIP_Bool SCIPnodeIsActive(SCIP_NODE *node)
Definition: tree.c:8193
SCIP_EXPORT void SCIPnodeGetAncestorBranchingsPart(SCIP_NODE *node, SCIP_NODE *parent, SCIP_VAR **branchvars, SCIP_Real *branchbounds, SCIP_BOUNDTYPE *boundtypes, int *nbranchvars, int branchvarssize)
Definition: tree.c:7829
type definitions for branch and bound tree
SCIP_EXPORT SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
Definition: tree.c:7468
enum SCIP_NodeType SCIP_NODETYPE
Definition: type_tree.h:44
SCIP_EXPORT SCIP_Bool SCIPnodesSharePath(SCIP_NODE *node1, SCIP_NODE *node2)
Definition: tree.c:8138
#define SCIP_Real
Definition: def.h:163
SCIP_EXPORT void SCIPnodeGetNDomchg(SCIP_NODE *node, int *nbranchings, int *nconsprop, int *nprop)
Definition: tree.c:7543
#define SCIP_Longint
Definition: def.h:148
SCIP_EXPORT void SCIPnodeGetAddedConss(SCIP_NODE *node, SCIP_CONS **addedconss, int *naddedconss, int addedconsssize)
Definition: tree.c:1672
#define nnodes
Definition: gastrans.c:65
SCIP_EXPORT SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
Definition: tree.c:7428
common defines and data types used in all packages of SCIP
SCIP_EXPORT 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:8089
SCIP_EXPORT void SCIPnodeGetParentBranchings(SCIP_NODE *node, SCIP_VAR **branchvars, SCIP_Real *branchbounds, SCIP_BOUNDTYPE *boundtypes, int *nbranchvars, int branchvarssize)
Definition: tree.c:7728
type definitions for constraints and constraint handlers