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 scip_tree.h 26 * @ingroup PUBLICCOREAPI 27 * @brief public methods for the branch-and-bound tree 28 * @author Tobias Achterberg 29 * @author Timo Berthold 30 * @author Thorsten Koch 31 * @author Alexander Martin 32 * @author Marc Pfetsch 33 * @author Kati Wolter 34 * @author Gregor Hendel 35 * @author Leona Gottwald 36 */ 37 38 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 39 40 #ifndef __SCIP_SCIP_TREE_H__ 41 #define __SCIP_SCIP_TREE_H__ 42 43 44 #include "scip/def.h" 45 #include "scip/type_retcode.h" 46 #include "scip/type_scip.h" 47 #include "scip/type_tree.h" 48 49 #ifdef __cplusplus 50 extern "C" { 51 #endif 52 53 /**@addtogroup PublicTreeMethods 54 * 55 * @{ 56 */ 57 58 /** gets focus node in the tree 59 * 60 * if we are in probing/diving mode this method returns the node in the tree where the probing/diving mode was started. 61 * 62 * @return the current node of the search tree 63 * 64 * @pre This method can be called if @p scip is in one of the following stages: 65 * - \ref SCIP_STAGE_INITPRESOLVE 66 * - \ref SCIP_STAGE_PRESOLVING 67 * - \ref SCIP_STAGE_EXITPRESOLVE 68 * - \ref SCIP_STAGE_SOLVING 69 */ 70 SCIP_EXPORT 71 SCIP_NODE* SCIPgetFocusNode( 72 SCIP* scip /**< SCIP data structure */ 73 ); 74 75 /** gets current node in the tree 76 * 77 * @return the current node of the search tree 78 * 79 * @pre This method can be called if @p scip is in one of the following stages: 80 * - \ref SCIP_STAGE_INITPRESOLVE 81 * - \ref SCIP_STAGE_PRESOLVING 82 * - \ref SCIP_STAGE_EXITPRESOLVE 83 * - \ref SCIP_STAGE_SOLVING 84 */ 85 SCIP_EXPORT 86 SCIP_NODE* SCIPgetCurrentNode( 87 SCIP* scip /**< SCIP data structure */ 88 ); 89 90 /** gets depth of current node, or -1 if no current node exists; in probing, the current node is the last probing node, 91 * such that the depth includes the probing path 92 * 93 * @return the depth of current node, or -1 if no current node exists; in probing, the current node is the last probing node, 94 * such that the depth includes the probing path 95 * 96 * @pre This method can be called if SCIP is in one of the following stages: 97 * - \ref SCIP_STAGE_TRANSFORMED 98 * - \ref SCIP_STAGE_INITPRESOLVE 99 * - \ref SCIP_STAGE_PRESOLVING 100 * - \ref SCIP_STAGE_EXITPRESOLVE 101 * - \ref SCIP_STAGE_PRESOLVED 102 * - \ref SCIP_STAGE_INITSOLVE 103 * - \ref SCIP_STAGE_SOLVING 104 * - \ref SCIP_STAGE_SOLVED 105 * - \ref SCIP_STAGE_EXITSOLVE 106 */ 107 SCIP_EXPORT 108 int SCIPgetDepth( 109 SCIP* scip /**< SCIP data structure */ 110 ); 111 112 /** gets depth of the focus node, or -1 if no focus node exists; the focus node is the currently processed node in the 113 * branching tree, excluding the nodes of the probing path 114 * 115 * @return the depth of the focus node, or -1 if no focus node exists; the focus node is the currently processed node in the 116 * branching tree, excluding the nodes of the probing path 117 * 118 * @pre This method can be called if SCIP is in one of the following stages: 119 * - \ref SCIP_STAGE_TRANSFORMED 120 * - \ref SCIP_STAGE_INITPRESOLVE 121 * - \ref SCIP_STAGE_PRESOLVING 122 * - \ref SCIP_STAGE_EXITPRESOLVE 123 * - \ref SCIP_STAGE_PRESOLVED 124 * - \ref SCIP_STAGE_INITSOLVE 125 * - \ref SCIP_STAGE_SOLVING 126 * - \ref SCIP_STAGE_SOLVED 127 * - \ref SCIP_STAGE_EXITSOLVE 128 */ 129 SCIP_EXPORT 130 int SCIPgetFocusDepth( 131 SCIP* scip /**< SCIP data structure */ 132 ); 133 134 /** gets current plunging depth (successive times, a child was selected as next node) 135 * 136 * @return the current plunging depth (successive times, a child was selected as next node) 137 * 138 * @pre This method can be called if SCIP is in one of the following stages: 139 * - \ref SCIP_STAGE_PRESOLVED 140 * - \ref SCIP_STAGE_SOLVING 141 */ 142 SCIP_EXPORT 143 int SCIPgetPlungeDepth( 144 SCIP* scip /**< SCIP data structure */ 145 ); 146 147 /** gets the root node of the tree 148 * 149 * @return the root node of the search tree 150 * 151 * @pre This method can be called if @p scip is in one of the following stages: 152 * - \ref SCIP_STAGE_INITPRESOLVE 153 * - \ref SCIP_STAGE_PRESOLVING 154 * - \ref SCIP_STAGE_EXITPRESOLVE 155 * - \ref SCIP_STAGE_SOLVING 156 */ 157 SCIP_EXPORT 158 SCIP_NODE* SCIPgetRootNode( 159 SCIP* scip /**< SCIP data structure */ 160 ); 161 162 /** gets the effective root depth, i.e., the depth of the deepest node which is part of all paths from the root node 163 * to the unprocessed nodes. 164 * 165 * @return effective root depth 166 * 167 * @pre This method can be called if @p scip is in one of the following stages: 168 * - \ref SCIP_STAGE_SOLVING 169 */ 170 SCIP_EXPORT 171 int SCIPgetEffectiveRootDepth( 172 SCIP* scip /**< SCIP data structure */ 173 ); 174 175 /** returns whether the current node is already solved and only propagated again 176 * 177 * @return TRUE is returned if \SCIP performance repropagation, otherwise FALSE. 178 * 179 * @pre This method can be called if @p scip is in one of the following stages: 180 * - \ref SCIP_STAGE_INITPRESOLVE 181 * - \ref SCIP_STAGE_PRESOLVING 182 * - \ref SCIP_STAGE_EXITPRESOLVE 183 * - \ref SCIP_STAGE_SOLVING 184 */ 185 SCIP_EXPORT 186 SCIP_Bool SCIPinRepropagation( 187 SCIP* scip /**< SCIP data structure */ 188 ); 189 190 /** gets children of focus node along with the number of children 191 * 192 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 193 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 194 * 195 * @pre This method can be called if @p scip is in one of the following stages: 196 * - \ref SCIP_STAGE_SOLVING 197 */ 198 SCIP_EXPORT 199 SCIP_RETCODE SCIPgetChildren( 200 SCIP* scip, /**< SCIP data structure */ 201 SCIP_NODE*** children, /**< pointer to store children array, or NULL if not needed */ 202 int* nchildren /**< pointer to store number of children, or NULL if not needed */ 203 ); 204 205 /** gets number of children of focus node 206 * 207 * @return number of children of the focus node 208 * 209 * @pre This method can be called if @p scip is in one of the following stages: 210 * - \ref SCIP_STAGE_SOLVING 211 */ 212 SCIP_EXPORT 213 int SCIPgetNChildren( 214 SCIP* scip /**< SCIP data structure */ 215 ); 216 217 /** gets siblings of focus node along with the number of siblings 218 * 219 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 220 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 221 * 222 * @pre This method can be called if @p scip is in one of the following stages: 223 * - \ref SCIP_STAGE_SOLVING 224 */ 225 SCIP_EXPORT 226 SCIP_RETCODE SCIPgetSiblings( 227 SCIP* scip, /**< SCIP data structure */ 228 SCIP_NODE*** siblings, /**< pointer to store siblings array, or NULL if not needed */ 229 int* nsiblings /**< pointer to store number of siblings, or NULL if not needed */ 230 ); 231 232 /** gets number of siblings of focus node 233 * 234 * @return the number of siblings of focus node 235 * 236 * @pre This method can be called if @p scip is in one of the following stages: 237 * - \ref SCIP_STAGE_SOLVING 238 */ 239 SCIP_EXPORT 240 int SCIPgetNSiblings( 241 SCIP* scip /**< SCIP data structure */ 242 ); 243 244 /** gets leaves of the tree along with the number of leaves 245 * 246 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 247 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 248 * 249 * @pre This method can be called if @p scip is in one of the following stages: 250 * - \ref SCIP_STAGE_SOLVING 251 */ 252 SCIP_EXPORT 253 SCIP_RETCODE SCIPgetLeaves( 254 SCIP* scip, /**< SCIP data structure */ 255 SCIP_NODE*** leaves, /**< pointer to store leaves array, or NULL if not needed */ 256 int* nleaves /**< pointer to store number of leaves, or NULL if not needed */ 257 ); 258 259 /** gets number of leaves in the tree 260 * 261 * @return the number of leaves in the tree 262 * 263 * @pre This method can be called if @p scip is in one of the following stages: 264 * - \ref SCIP_STAGE_SOLVING 265 */ 266 SCIP_EXPORT 267 int SCIPgetNLeaves( 268 SCIP* scip /**< SCIP data structure */ 269 ); 270 271 /** gets number of nodes left in the tree (children + siblings + leaves) 272 * 273 * @return the number of nodes left in the tree (children + siblings + leaves) 274 * 275 * @pre This method can be called if SCIP is in one of the following stages: 276 * - \ref SCIP_STAGE_PRESOLVED 277 * - \ref SCIP_STAGE_SOLVING 278 * - \ref SCIP_STAGE_SOLVED 279 */ 280 SCIP_EXPORT 281 int SCIPgetNNodesLeft( 282 SCIP* scip /**< SCIP data structure */ 283 ); 284 285 /** gets the best child of the focus node w.r.t. the node selection priority assigned by the branching rule 286 * 287 * @return the best child of the focus node w.r.t. the node selection priority assigned by the branching rule 288 * 289 * @pre This method can be called if @p scip is in one of the following stages: 290 * - \ref SCIP_STAGE_SOLVING 291 */ 292 SCIP_EXPORT 293 SCIP_NODE* SCIPgetPrioChild( 294 SCIP* scip /**< SCIP data structure */ 295 ); 296 297 /** gets the best sibling of the focus node w.r.t. the node selection priority assigned by the branching rule 298 * 299 * @return the best sibling of the focus node w.r.t. the node selection priority assigned by the branching rule 300 * 301 * @pre This method can be called if @p scip is in one of the following stages: 302 * - \ref SCIP_STAGE_SOLVING 303 */ 304 SCIP_EXPORT 305 SCIP_NODE* SCIPgetPrioSibling( 306 SCIP* scip /**< SCIP data structure */ 307 ); 308 309 /** gets the best child of the focus node w.r.t. the node selection strategy 310 * 311 * @return the best child of the focus node w.r.t. the node selection strategy 312 * 313 * @pre This method can be called if @p scip is in one of the following stages: 314 * - \ref SCIP_STAGE_SOLVING 315 */ 316 SCIP_EXPORT 317 SCIP_NODE* SCIPgetBestChild( 318 SCIP* scip /**< SCIP data structure */ 319 ); 320 321 /** gets the best sibling of the focus node w.r.t. the node selection strategy 322 * 323 * @return the best sibling of the focus node w.r.t. the node selection strategy 324 * 325 * @pre This method can be called if @p scip is in one of the following stages: 326 * - \ref SCIP_STAGE_SOLVING 327 */ 328 SCIP_EXPORT 329 SCIP_NODE* SCIPgetBestSibling( 330 SCIP* scip /**< SCIP data structure */ 331 ); 332 333 /** gets the best leaf from the node queue w.r.t. the node selection strategy 334 * 335 * @return the best leaf from the node queue w.r.t. the node selection strategy 336 * 337 * @pre This method can be called if @p scip is in one of the following stages: 338 * - \ref SCIP_STAGE_SOLVING 339 */ 340 SCIP_EXPORT 341 SCIP_NODE* SCIPgetBestLeaf( 342 SCIP* scip /**< SCIP data structure */ 343 ); 344 345 /** gets the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy 346 * 347 * @return the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy 348 * 349 * @pre This method can be called if @p scip is in one of the following stages: 350 * - \ref SCIP_STAGE_SOLVING 351 */ 352 SCIP_EXPORT 353 SCIP_NODE* SCIPgetBestNode( 354 SCIP* scip /**< SCIP data structure */ 355 ); 356 357 /** gets the node with smallest lower bound from the tree (child, sibling, or leaf) 358 * 359 * @return the node with smallest lower bound from the tree (child, sibling, or leaf) 360 * 361 * @pre This method can be called if @p scip is in one of the following stages: 362 * - \ref SCIP_STAGE_SOLVING 363 */ 364 SCIP_EXPORT 365 SCIP_NODE* SCIPgetBestboundNode( 366 SCIP* scip /**< SCIP data structure */ 367 ); 368 369 /** access to all data of open nodes (leaves, children, and siblings) 370 * 371 * @pre This method can be called if @p scip is in one of the following stages: 372 * - \ref SCIP_STAGE_SOLVING 373 */ 374 SCIP_EXPORT 375 SCIP_RETCODE SCIPgetOpenNodesData( 376 SCIP* scip, /**< SCIP data structure */ 377 SCIP_NODE*** leaves, /**< pointer to store the leaves, or NULL if not needed */ 378 SCIP_NODE*** children, /**< pointer to store the children, or NULL if not needed */ 379 SCIP_NODE*** siblings, /**< pointer to store the siblings, or NULL if not needed */ 380 int* nleaves, /**< pointer to store the number of leaves, or NULL */ 381 int* nchildren, /**< pointer to store the number of children, or NULL */ 382 int* nsiblings /**< pointer to store the number of siblings, or NULL */ 383 ); 384 385 /** marks node and whole sub tree to be cut off from branch and bound tree 386 * 387 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 388 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 389 * 390 * @pre This method can be called if @p scip is in one of the following stages: 391 * - \ref SCIP_STAGE_SOLVING 392 */ 393 SCIP_EXPORT 394 SCIP_RETCODE SCIPcutoffNode( 395 SCIP* scip, /**< SCIP data structure */ 396 SCIP_NODE* node /**< node that should be cut off */ 397 ); 398 399 /** removes all nodes from branch and bound tree that were marked to be cut off via SCIPcutoffNode() 400 * 401 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 402 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 403 * 404 * @pre This method can be called if @p scip is in one of the following stages: 405 * - \ref SCIP_STAGE_SOLVING 406 * 407 * @note In diving mode, the removal of nodes is delayed until diving ends. 408 */ 409 SCIP_EXPORT 410 SCIP_RETCODE SCIPpruneTree( 411 SCIP* scip /**< SCIP data structure */ 412 ); 413 414 /** marks the given node to be propagated again the next time a node of its subtree is processed 415 * 416 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 417 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 418 * 419 * @pre This method can be called if @p scip is in one of the following stages: 420 * - \ref SCIP_STAGE_SOLVING 421 */ 422 SCIP_EXPORT 423 SCIP_RETCODE SCIPrepropagateNode( 424 SCIP* scip, /**< SCIP data structure */ 425 SCIP_NODE* node /**< node that should be propagated again */ 426 ); 427 428 /** returns depth of first node in active path that is marked being cutoff 429 * 430 * @return depth of first node in active path that is marked being cutoff 431 * 432 * @pre This method can be called if @p scip is in one of the following stages: 433 * - \ref SCIP_STAGE_SOLVING 434 */ 435 SCIP_EXPORT 436 int SCIPgetCutoffdepth( 437 SCIP* scip /**< SCIP data structure */ 438 ); 439 440 /** returns depth of first node in active path that has to be propagated again 441 * 442 * @return depth of first node in active path that has to be propagated again 443 * 444 * @pre This method can be called if @p scip is in one of the following stages: 445 * - \ref SCIP_STAGE_SOLVING 446 */ 447 SCIP_EXPORT 448 int SCIPgetRepropdepth( 449 SCIP* scip /**< SCIP data structure */ 450 ); 451 452 /** prints all branching decisions on variables from the root to the given node 453 * 454 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 455 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 456 * 457 * @pre This method can be called if @p scip is in one of the following stages: 458 * - \ref SCIP_STAGE_SOLVING 459 */ 460 SCIP_EXPORT 461 SCIP_RETCODE SCIPprintNodeRootPath( 462 SCIP* scip, /**< SCIP data structure */ 463 SCIP_NODE* node, /**< node data */ 464 FILE* file /**< output file (or NULL for standard output) */ 465 ); 466 467 /** sets whether the LP should be solved at the focus node 468 * 469 * @note In order to have an effect, this method needs to be called after a node is focused but before the LP is 470 * solved. 471 * 472 * @pre This method can be called if @p scip is in one of the following stages: 473 * - \ref SCIP_STAGE_SOLVING 474 */ 475 SCIP_EXPORT 476 void SCIPsetFocusnodeLP( 477 SCIP* scip, /**< SCIP data structure */ 478 SCIP_Bool solvelp /**< should the LP be solved? */ 479 ); 480 481 482 /** query if node was the last parent of a branching of the tree 483 * 484 * @return TRUE if node was the last parent of a branching of the tree 485 * 486 * @pre This method can be called if SCIP is in one of the following stages: 487 * - \ref SCIP_STAGE_PRESOLVED 488 * - \ref SCIP_STAGE_SOLVING 489 * - \ref SCIP_STAGE_SOLVED 490 */ 491 SCIP_EXPORT 492 SCIP_Bool SCIPwasNodeLastBranchParent( 493 SCIP* scip, /**< SCIP data structure */ 494 SCIP_NODE* node /**< tree node, or NULL to check focus node */ 495 ); 496 497 /**@} */ 498 499 #ifdef __cplusplus 500 } 501 #endif 502 503 #endif 504