1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file pub_tree.h 26 * @ingroup PUBLICCOREAPI 27 * @brief public methods for branch and bound tree 28 * @author Tobias Achterberg 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #ifndef __SCIP_PUB_TREE_H__ 34 #define __SCIP_PUB_TREE_H__ 35 36 #include "scip/def.h" 37 #include "scip/type_cons.h" 38 #include "scip/type_lp.h" 39 #include "scip/type_misc.h" 40 #include "scip/type_reopt.h" 41 #include "scip/type_retcode.h" 42 #include "scip/type_tree.h" 43 #include "scip/type_var.h" 44 45 #ifdef NDEBUG 46 #include "scip/struct_tree.h" 47 #endif 48 49 #ifdef __cplusplus 50 extern "C" { 51 #endif 52 53 /* 54 * Node methods 55 */ 56 57 /**@addtogroup PublicNodeMethods 58 * 59 * @{ 60 */ 61 62 /** node comparator for best lower bound */ 63 SCIP_EXPORT 64 SCIP_DECL_SORTPTRCOMP(SCIPnodeCompLowerbound); 65 66 /** returns the set of variable branchings that were performed in the parent node to create this node */ 67 SCIP_EXPORT 68 void SCIPnodeGetParentBranchings( 69 SCIP_NODE* node, /**< node data */ 70 SCIP_VAR** branchvars, /**< array of variables on which the branching has been performed in the parent node */ 71 SCIP_Real* branchbounds, /**< array of bounds which the branching in the parent node set */ 72 SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branching in the parent node set */ 73 int* nbranchvars, /**< number of variables on which branching has been performed in the parent node 74 * if this is larger than the array size, arrays should be reallocated and method should be called again */ 75 int branchvarssize /**< available slots in arrays */ 76 ); 77 78 /** returns the set of variable branchings that were performed in all ancestor nodes (nodes on the path to the root) to create this node */ 79 SCIP_EXPORT 80 void SCIPnodeGetAncestorBranchings( 81 SCIP_NODE* node, /**< node data */ 82 SCIP_VAR** branchvars, /**< array of variables on which the branchings has been performed in all ancestors */ 83 SCIP_Real* branchbounds, /**< array of bounds which the branchings in all ancestors set */ 84 SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branchings in all ancestors set */ 85 int* nbranchvars, /**< number of variables on which branchings have been performed in all ancestors 86 * if this is larger than the array size, arrays should be reallocated and method should be called again */ 87 int branchvarssize /**< available slots in arrays */ 88 ); 89 90 /** returns the set of variable branchings that were performed between the given @p node and the given @p parent node. */ 91 SCIP_EXPORT 92 void SCIPnodeGetAncestorBranchingsPart( 93 SCIP_NODE* node, /**< node data */ 94 SCIP_NODE* parent, /**< node data */ 95 SCIP_VAR** branchvars, /**< array of variables on which the branchings has been performed in all ancestors */ 96 SCIP_Real* branchbounds, /**< array of bounds which the branchings in all ancestors set */ 97 SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branchings in all ancestors set */ 98 int* nbranchvars, /**< number of variables on which branchings have been performed in all ancestors 99 * if this is larger than the array size, arrays should be reallocated and method should be called again */ 100 int branchvarssize /**< available slots in arrays */ 101 ); 102 103 /** outputs the path into given file stream in GML format */ 104 SCIP_EXPORT 105 SCIP_RETCODE SCIPnodePrintAncestorBranchings( 106 SCIP_NODE* node, /**< node data */ 107 FILE* file /**< file to output the path */ 108 ); 109 110 /** returns the set of variable branchings that were performed in all ancestor nodes (nodes on the path to the root) to create this node 111 * sorted by the nodes, starting from the current node going up to the root 112 */ 113 SCIP_EXPORT 114 void SCIPnodeGetAncestorBranchingPath( 115 SCIP_NODE* node, /**< node data */ 116 SCIP_VAR** branchvars, /**< array of variables on which the branchings has been performed in all ancestors */ 117 SCIP_Real* branchbounds, /**< array of bounds which the branchings in all ancestors set */ 118 SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which the branchings in all ancestors set */ 119 int* nbranchvars, /**< number of variables on which branchings have been performed in all ancestors 120 * if this is larger than the array size, arrays should be reallocated and method 121 * should be called again */ 122 int branchvarssize, /**< available slots in arrays */ 123 int* nodeswitches, /**< marks, where in the arrays the branching decisions of the next node on the path 124 * start; branchings performed at the parent of node always start at position 0. 125 * For single variable branching, nodeswitches[i] = i holds */ 126 int* nnodes, /**< number of nodes in the nodeswitch array */ 127 int nodeswitchsize /**< available slots in node switch array */ 128 ); 129 130 131 /** checks for two nodes whether they share the same root path, i.e., whether one is an ancestor of the other */ 132 SCIP_EXPORT 133 SCIP_Bool SCIPnodesSharePath( 134 SCIP_NODE* node1, /**< node data */ 135 SCIP_NODE* node2 /**< node data */ 136 ); 137 138 /** finds the common ancestor node of two given nodes */ 139 SCIP_EXPORT 140 SCIP_NODE* SCIPnodesGetCommonAncestor( 141 SCIP_NODE* node1, /**< node data */ 142 SCIP_NODE* node2 /**< node data */ 143 ); 144 145 146 /** gets the type of the node */ 147 SCIP_EXPORT 148 SCIP_NODETYPE SCIPnodeGetType( 149 SCIP_NODE* node /**< node */ 150 ); 151 152 /** gets successively assigned number of the node */ 153 SCIP_EXPORT 154 SCIP_Longint SCIPnodeGetNumber( 155 SCIP_NODE* node /**< node */ 156 ); 157 158 /** gets the depth of the node */ 159 SCIP_EXPORT 160 int SCIPnodeGetDepth( 161 SCIP_NODE* node /**< node */ 162 ); 163 164 /** gets the lower bound of the node */ 165 SCIP_EXPORT 166 SCIP_Real SCIPnodeGetLowerbound( 167 SCIP_NODE* node /**< node */ 168 ); 169 170 /** gets the estimated value of the best feasible solution in subtree of the node */ 171 SCIP_EXPORT 172 SCIP_Real SCIPnodeGetEstimate( 173 SCIP_NODE* node /**< node */ 174 ); 175 176 177 /** gets the reoptimization type of a node */ 178 SCIP_EXPORT 179 SCIP_REOPTTYPE SCIPnodeGetReopttype( 180 SCIP_NODE* node /**< node */ 181 ); 182 183 /** gets the unique id to identify the node during reoptimization; id is 0 if the node is the root or not part of the 184 * reoptimization tree 185 */ 186 SCIP_EXPORT 187 unsigned int SCIPnodeGetReoptID( 188 SCIP_NODE* node /**< node */ 189 ); 190 191 /** sets the reoptimization type of the node */ 192 SCIP_EXPORT 193 void SCIPnodeSetReopttype( 194 SCIP_NODE* node, /**< node */ 195 SCIP_REOPTTYPE reopttype /**< reoptimization type */ 196 ); 197 198 /** sets a unique id to identify the node during reoptimization */ 199 SCIP_EXPORT 200 void SCIPnodeSetReoptID( 201 SCIP_NODE* node, /**< node */ 202 unsigned int id /**< unique id */ 203 ); 204 205 /** counts the number of bound changes due to branching, constraint propagation, and propagation */ 206 SCIP_EXPORT 207 void SCIPnodeGetNDomchg( 208 SCIP_NODE* node, /**< node */ 209 int* nbranchings, /**< pointer to store number of branchings (or NULL if not needed) */ 210 int* nconsprop, /**< pointer to store number of constraint propagations (or NULL if not needed) */ 211 int* nprop /**< pointer to store number of propagations (or NULL if not needed) */ 212 ); 213 214 /** gets the domain change information of the node, i.e., the information about the differences in the 215 * variables domains to the parent node 216 */ 217 SCIP_EXPORT 218 SCIP_DOMCHG* SCIPnodeGetDomchg( 219 SCIP_NODE* node /**< node */ 220 ); 221 222 /** gets the parent node of a node in the branch-and-bound tree, if any */ 223 SCIP_EXPORT 224 SCIP_NODE* SCIPnodeGetParent( 225 SCIP_NODE* node /**< node */ 226 ); 227 228 /** returns all constraints added to a given node */ 229 SCIP_EXPORT 230 void SCIPnodeGetAddedConss( 231 SCIP_NODE* node, /**< node */ 232 SCIP_CONS** addedconss, /**< array to store the constraints */ 233 int* naddedconss, /**< number of added constraints */ 234 int addedconsssize /**< size of the constraint array */ 235 ); 236 237 /** returns the number of added constraints to the given node */ 238 SCIP_EXPORT 239 int SCIPnodeGetNAddedConss( 240 SCIP_NODE* node 241 ); 242 243 /** returns whether node is in the path to the current node */ 244 SCIP_EXPORT 245 SCIP_Bool SCIPnodeIsActive( 246 SCIP_NODE* node /**< node */ 247 ); 248 249 /** returns whether the node is marked to be propagated again */ 250 SCIP_EXPORT 251 SCIP_Bool SCIPnodeIsPropagatedAgain( 252 SCIP_NODE* node /**< node data */ 253 ); 254 255 /* returns the set of changed constraints for a particular node */ 256 SCIP_EXPORT 257 SCIP_CONSSETCHG* SCIPnodeGetConssetchg( 258 SCIP_NODE* node /**< node data */ 259 ); 260 261 262 #ifdef NDEBUG 263 264 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and 265 * speed up the algorithms. 266 */ 267 268 #define SCIPnodeGetType(node) ((SCIP_NODETYPE)(node)->nodetype) 269 #define SCIPnodeGetNumber(node) ((node)->number) 270 #define SCIPnodeGetDepth(node) ((int) (node)->depth) 271 #define SCIPnodeGetLowerbound(node) ((node)->lowerbound) 272 #define SCIPnodeGetEstimate(node) ((node)->estimate) 273 #define SCIPnodeGetDomchg(node) ((node)->domchg) 274 #define SCIPnodeGetParent(node) ((node)->parent) 275 #define SCIPnodeIsActive(node) ((node)->active) 276 #define SCIPnodeIsPropagatedAgain(node) ((node)->reprop) 277 #define SCIPnodeGetConssetchg(node) ((node)->conssetchg) 278 279 #endif 280 281 /** @} */ 282 283 #ifdef __cplusplus 284 } 285 #endif 286 287 #endif 288