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 */ 54 SCIP_EXPORT 55 SCIP_DECL_SORTPTRCOMP(SCIPnodeCompLowerbound); 56 57 /** returns the set of variable branchings that were performed in the parent node to create this node */ 58 SCIP_EXPORT 59 void SCIPnodeGetParentBranchings( 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 */ 70 SCIP_EXPORT 71 void SCIPnodeGetAncestorBranchings( 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. */ 82 SCIP_EXPORT 83 void SCIPnodeGetAncestorBranchingsPart( 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 */ 95 SCIP_EXPORT 96 SCIP_RETCODE SCIPnodePrintAncestorBranchings( 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 */ 104 SCIP_EXPORT 105 void SCIPnodeGetAncestorBranchingPath( 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 */ 123 SCIP_EXPORT 124 SCIP_Bool SCIPnodesSharePath( 125 SCIP_NODE* node1, /**< node data */ 126 SCIP_NODE* node2 /**< node data */ 127 ); 128 129 /** finds the common ancestor node of two given nodes */ 130 SCIP_EXPORT 131 SCIP_NODE* SCIPnodesGetCommonAncestor( 132 SCIP_NODE* node1, /**< node data */ 133 SCIP_NODE* node2 /**< node data */ 134 ); 135 136 137 /** gets the type of the node */ 138 SCIP_EXPORT 139 SCIP_NODETYPE SCIPnodeGetType( 140 SCIP_NODE* node /**< node */ 141 ); 142 143 /** gets successively assigned number of the node */ 144 SCIP_EXPORT 145 SCIP_Longint SCIPnodeGetNumber( 146 SCIP_NODE* node /**< node */ 147 ); 148 149 /** gets the depth of the node */ 150 SCIP_EXPORT 151 int SCIPnodeGetDepth( 152 SCIP_NODE* node /**< node */ 153 ); 154 155 /** gets the lower bound of the node */ 156 SCIP_EXPORT 157 SCIP_Real SCIPnodeGetLowerbound( 158 SCIP_NODE* node /**< node */ 159 ); 160 161 /** gets the estimated value of the best feasible solution in subtree of the node */ 162 SCIP_EXPORT 163 SCIP_Real SCIPnodeGetEstimate( 164 SCIP_NODE* node /**< node */ 165 ); 166 167 168 /** gets the reoptimization type of a node */ 169 SCIP_EXPORT 170 SCIP_REOPTTYPE SCIPnodeGetReopttype( 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 */ 177 SCIP_EXPORT 178 unsigned int SCIPnodeGetReoptID( 179 SCIP_NODE* node /**< node */ 180 ); 181 182 /** sets the reoptimization type of the node */ 183 SCIP_EXPORT 184 void SCIPnodeSetReopttype( 185 SCIP_NODE* node, /**< node */ 186 SCIP_REOPTTYPE reopttype /**< reoptimization type */ 187 ); 188 189 /** sets a unique id to identify the node during reoptimization */ 190 SCIP_EXPORT 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 */ 197 SCIP_EXPORT 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 */ 208 SCIP_EXPORT 209 SCIP_DOMCHG* SCIPnodeGetDomchg( 210 SCIP_NODE* node /**< node */ 211 ); 212 213 /** gets the parent node of a node in the branch-and-bound tree, if any */ 214 SCIP_EXPORT 215 SCIP_NODE* SCIPnodeGetParent( 216 SCIP_NODE* node /**< node */ 217 ); 218 219 /** returns all constraints added to a given node */ 220 SCIP_EXPORT 221 void SCIPnodeGetAddedConss( 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 */ 229 SCIP_EXPORT 230 int SCIPnodeGetNAddedConss( 231 SCIP_NODE* node 232 ); 233 234 /** returns whether node is in the path to the current node */ 235 SCIP_EXPORT 236 SCIP_Bool SCIPnodeIsActive( 237 SCIP_NODE* node /**< node */ 238 ); 239 240 /** returns whether the node is marked to be propagated again */ 241 SCIP_EXPORT 242 SCIP_Bool SCIPnodeIsPropagatedAgain( 243 SCIP_NODE* node /**< node data */ 244 ); 245 246 /* returns the set of changed constraints for a particular node */ 247 SCIP_EXPORT 248 SCIP_CONSSETCHG* SCIPnodeGetConssetchg( 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 279