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.c 26 * @ingroup OTHER_CFILES 27 * @brief public methods for the branch-and-bound tree 28 * @author Tobias Achterberg 29 * @author Timo Berthold 30 * @author Gerald Gamrath 31 * @author Leona Gottwald 32 * @author Stefan Heinz 33 * @author Gregor Hendel 34 * @author Thorsten Koch 35 * @author Alexander Martin 36 * @author Marc Pfetsch 37 * @author Michael Winkler 38 * @author Kati Wolter 39 * 40 * @todo check all SCIP_STAGE_* switches, and include the new stages TRANSFORMED and INITSOLVE 41 */ 42 43 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 44 45 #include "blockmemshell/memory.h" 46 #include "scip/debug.h" 47 #include "scip/nodesel.h" 48 #include "scip/pub_message.h" 49 #include "scip/pub_tree.h" 50 #include "scip/pub_var.h" 51 #include "scip/scip_mem.h" 52 #include "scip/scip_tree.h" 53 #include "scip/scip_numerics.h" 54 #include "scip/struct_mem.h" 55 #include "scip/struct_scip.h" 56 #include "scip/struct_stat.h" 57 #include "scip/struct_tree.h" 58 #include "scip/tree.h" 59 60 /** gets focus node in the tree 61 * 62 * if we are in probing/diving mode this method returns the node in the tree where the probing/diving mode was started. 63 * 64 * @return the current node of the search tree 65 * 66 * @pre This method can be called if @p scip is in one of the following stages: 67 * - \ref SCIP_STAGE_INITPRESOLVE 68 * - \ref SCIP_STAGE_PRESOLVING 69 * - \ref SCIP_STAGE_EXITPRESOLVE 70 * - \ref SCIP_STAGE_SOLVING 71 */ 72 SCIP_NODE* SCIPgetFocusNode( 73 SCIP* scip /**< SCIP data structure */ 74 ) 75 { 76 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetFocusNode", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 77 78 return SCIPtreeGetFocusNode(scip->tree); 79 } 80 81 /** gets current node in the tree 82 * 83 * @return the current node of the search tree 84 * 85 * @pre This method can be called if @p scip is in one of the following stages: 86 * - \ref SCIP_STAGE_INITPRESOLVE 87 * - \ref SCIP_STAGE_PRESOLVING 88 * - \ref SCIP_STAGE_EXITPRESOLVE 89 * - \ref SCIP_STAGE_SOLVING 90 */ 91 SCIP_NODE* SCIPgetCurrentNode( 92 SCIP* scip /**< SCIP data structure */ 93 ) 94 { 95 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetCurrentNode", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 96 97 return SCIPtreeGetCurrentNode(scip->tree); 98 } 99 100 /** gets the root node of the tree 101 * 102 * @return the root node of the search tree 103 * 104 * @pre This method can be called if @p scip is in one of the following stages: 105 * - \ref SCIP_STAGE_INITPRESOLVE 106 * - \ref SCIP_STAGE_PRESOLVING 107 * - \ref SCIP_STAGE_EXITPRESOLVE 108 * - \ref SCIP_STAGE_SOLVING 109 */ 110 SCIP_NODE* SCIPgetRootNode( 111 SCIP* scip /**< SCIP data structure */ 112 ) 113 { 114 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetRootNode", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 115 116 return SCIPtreeGetRootNode(scip->tree); 117 } 118 119 /** gets the effective root depth, i.e., the depth of the deepest node which is part of all paths from the root node 120 * to the unprocessed nodes. 121 * 122 * @return effective root depth 123 * 124 * @pre This method can be called if @p scip is in one of the following stages: 125 * - \ref SCIP_STAGE_SOLVING 126 */ 127 int SCIPgetEffectiveRootDepth( 128 SCIP* scip /**< SCIP data structure */ 129 ) 130 { 131 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetEffectiveRootDepth", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 132 133 return SCIPtreeGetEffectiveRootDepth(scip->tree); 134 } 135 136 /** returns whether the current node is already solved and only propagated again 137 * 138 * @return TRUE is returned if \SCIP performance repropagation, otherwise FALSE. 139 * 140 * @pre This method can be called if @p scip is in one of the following stages: 141 * - \ref SCIP_STAGE_INITPRESOLVE 142 * - \ref SCIP_STAGE_PRESOLVING 143 * - \ref SCIP_STAGE_EXITPRESOLVE 144 * - \ref SCIP_STAGE_SOLVING 145 */ 146 SCIP_Bool SCIPinRepropagation( 147 SCIP* scip /**< SCIP data structure */ 148 ) 149 { 150 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPinRepropagation", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 151 152 return SCIPtreeInRepropagation(scip->tree); 153 } 154 155 /** gets children of focus node along with the number of children 156 * 157 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 158 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 159 * 160 * @pre This method can be called if @p scip is in one of the following stages: 161 * - \ref SCIP_STAGE_SOLVING 162 * - \ref SCIP_STAGE_SOLVED 163 */ 164 SCIP_RETCODE SCIPgetChildren( 165 SCIP* scip, /**< SCIP data structure */ 166 SCIP_NODE*** children, /**< pointer to store children array, or NULL if not needed */ 167 int* nchildren /**< pointer to store number of children, or NULL if not needed */ 168 ) 169 { 170 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetChildren", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 171 172 if( children != NULL ) 173 *children = scip->tree->children; 174 if( nchildren != NULL ) 175 *nchildren = scip->tree->nchildren; 176 177 return SCIP_OKAY; 178 } 179 180 /** gets number of children of focus node 181 * 182 * @return number of children of the focus node 183 * 184 * @pre This method can be called if @p scip is in one of the following stages: 185 * - \ref SCIP_STAGE_SOLVING 186 * - \ref SCIP_STAGE_SOLVED 187 */ 188 int SCIPgetNChildren( 189 SCIP* scip /**< SCIP data structure */ 190 ) 191 { 192 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNChildren", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 193 194 return scip->tree->nchildren; 195 } 196 197 /** gets siblings of focus node along with the number of siblings 198 * 199 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 200 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 201 * 202 * @pre This method can be called if @p scip is in one of the following stages: 203 * - \ref SCIP_STAGE_SOLVING 204 * - \ref SCIP_STAGE_SOLVED 205 */ 206 SCIP_RETCODE SCIPgetSiblings( 207 SCIP* scip, /**< SCIP data structure */ 208 SCIP_NODE*** siblings, /**< pointer to store siblings array, or NULL if not needed */ 209 int* nsiblings /**< pointer to store number of siblings, or NULL if not needed */ 210 ) 211 { 212 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetSiblings", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 213 214 if( siblings != NULL ) 215 *siblings = scip->tree->siblings; 216 if( nsiblings != NULL ) 217 *nsiblings = scip->tree->nsiblings; 218 219 return SCIP_OKAY; 220 } 221 222 /** gets number of siblings of focus node 223 * 224 * @return the number of siblings of focus node 225 * 226 * @pre This method can be called if @p scip is in one of the following stages: 227 * - \ref SCIP_STAGE_SOLVING 228 * - \ref SCIP_STAGE_SOLVED 229 */ 230 int SCIPgetNSiblings( 231 SCIP* scip /**< SCIP data structure */ 232 ) 233 { 234 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNSiblings", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 235 236 return scip->tree->nsiblings; 237 } 238 239 /** gets leaves of the tree along with the number of leaves 240 * 241 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 242 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 243 * 244 * @pre This method can be called if @p scip is in one of the following stages: 245 * - \ref SCIP_STAGE_SOLVING 246 * - \ref SCIP_STAGE_SOLVED 247 */ 248 SCIP_RETCODE SCIPgetLeaves( 249 SCIP* scip, /**< SCIP data structure */ 250 SCIP_NODE*** leaves, /**< pointer to store leaves array, or NULL if not needed */ 251 int* nleaves /**< pointer to store number of leaves, or NULL if not needed */ 252 ) 253 { 254 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetLeaves", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 255 256 if( leaves != NULL ) 257 *leaves = SCIPnodepqNodes(scip->tree->leaves); 258 if( nleaves != NULL ) 259 *nleaves = SCIPnodepqLen(scip->tree->leaves); 260 261 return SCIP_OKAY; 262 } 263 264 /** gets number of leaves in the tree 265 * 266 * @return the number of leaves in the tree 267 * 268 * @pre This method can be called if @p scip is in one of the following stages: 269 * - \ref SCIP_STAGE_SOLVING 270 * - \ref SCIP_STAGE_SOLVED 271 */ 272 int SCIPgetNLeaves( 273 SCIP* scip /**< SCIP data structure */ 274 ) 275 { 276 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNLeaves", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 277 278 return SCIPnodepqLen(scip->tree->leaves); 279 } 280 281 /** gets the best child of the focus node w.r.t. the node selection priority assigned by the branching rule 282 * 283 * @return the best child of the focus node w.r.t. the node selection priority assigned by the branching rule 284 * 285 * @pre This method can be called if @p scip is in one of the following stages: 286 * - \ref SCIP_STAGE_SOLVING 287 */ 288 SCIP_NODE* SCIPgetPrioChild( 289 SCIP* scip /**< SCIP data structure */ 290 ) 291 { 292 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetPrioChild", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 293 294 return SCIPtreeGetPrioChild(scip->tree); 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_NODE* SCIPgetPrioSibling( 305 SCIP* scip /**< SCIP data structure */ 306 ) 307 { 308 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetPrioSibling", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 309 310 return SCIPtreeGetPrioSibling(scip->tree); 311 } 312 313 /** gets the best child of the focus node w.r.t. the node selection strategy 314 * 315 * @return the best child of the focus node w.r.t. the node selection strategy 316 * 317 * @pre This method can be called if @p scip is in one of the following stages: 318 * - \ref SCIP_STAGE_SOLVING 319 */ 320 SCIP_NODE* SCIPgetBestChild( 321 SCIP* scip /**< SCIP data structure */ 322 ) 323 { 324 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBestChild", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 325 326 return SCIPtreeGetBestChild(scip->tree, scip->set); 327 } 328 329 /** gets the best sibling of the focus node w.r.t. the node selection strategy 330 * 331 * @return the best sibling of the focus node w.r.t. the node selection strategy 332 * 333 * @pre This method can be called if @p scip is in one of the following stages: 334 * - \ref SCIP_STAGE_SOLVING 335 */ 336 SCIP_NODE* SCIPgetBestSibling( 337 SCIP* scip /**< SCIP data structure */ 338 ) 339 { 340 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBestSibling", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 341 342 return SCIPtreeGetBestSibling(scip->tree, scip->set); 343 } 344 345 /** gets the best leaf from the node queue w.r.t. the node selection strategy 346 * 347 * @return the best leaf from the node queue 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_NODE* SCIPgetBestLeaf( 353 SCIP* scip /**< SCIP data structure */ 354 ) 355 { 356 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBestLeaf", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 357 358 return SCIPtreeGetBestLeaf(scip->tree); 359 } 360 361 /** gets the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy 362 * 363 * @return the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy 364 * 365 * @pre This method can be called if @p scip is in one of the following stages: 366 * - \ref SCIP_STAGE_SOLVING 367 */ 368 SCIP_NODE* SCIPgetBestNode( 369 SCIP* scip /**< SCIP data structure */ 370 ) 371 { 372 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBestNode", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 373 374 return SCIPtreeGetBestNode(scip->tree, scip->set); 375 } 376 377 /** gets the node with smallest lower bound from the tree (child, sibling, or leaf) 378 * 379 * @return the node with smallest lower bound from the tree (child, sibling, or leaf) 380 * 381 * @pre This method can be called if @p scip is in one of the following stages: 382 * - \ref SCIP_STAGE_SOLVING 383 */ 384 SCIP_NODE* SCIPgetBestboundNode( 385 SCIP* scip /**< SCIP data structure */ 386 ) 387 { 388 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBestboundNode", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 389 390 return SCIPtreeGetLowerboundNode(scip->tree, scip->set); 391 } 392 393 /** access to all data of open nodes (leaves, children, and siblings) 394 * 395 * @pre This method can be called if @p scip is in one of the following stages: 396 * - \ref SCIP_STAGE_SOLVING 397 */ 398 SCIP_RETCODE SCIPgetOpenNodesData( 399 SCIP* scip, /**< SCIP data structure */ 400 SCIP_NODE*** leaves, /**< pointer to store the leaves, or NULL if not needed */ 401 SCIP_NODE*** children, /**< pointer to store the children, or NULL if not needed */ 402 SCIP_NODE*** siblings, /**< pointer to store the siblings, or NULL if not needed */ 403 int* nleaves, /**< pointer to store the number of leaves, or NULL */ 404 int* nchildren, /**< pointer to store the number of children, or NULL */ 405 int* nsiblings /**< pointer to store the number of siblings, or NULL */ 406 ) 407 { 408 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetOpenNodesData", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 409 410 if( leaves != NULL ) 411 *leaves = SCIPnodepqNodes(scip->tree->leaves); 412 if( children != NULL ) 413 *children = scip->tree->children; 414 if( siblings != NULL ) 415 *siblings = scip->tree->siblings; 416 if( nleaves != NULL ) 417 *nleaves = SCIPnodepqLen(scip->tree->leaves); 418 if( nchildren != NULL ) 419 *nchildren = SCIPtreeGetNChildren(scip->tree); 420 if( nsiblings != NULL ) 421 *nsiblings = SCIPtreeGetNSiblings(scip->tree); 422 423 return SCIP_OKAY; 424 } 425 426 /** cuts off node and whole sub tree from branch and bound tree 427 * 428 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 429 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 430 * 431 * @pre This method can be called if @p scip is in one of the following stages: 432 * - \ref SCIP_STAGE_SOLVING 433 */ 434 SCIP_RETCODE SCIPcutoffNode( 435 SCIP* scip, /**< SCIP data structure */ 436 SCIP_NODE* node /**< node that should be cut off */ 437 ) 438 { 439 SCIP_CALL( SCIPcheckStage(scip, "SCIPcutoffNode", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 440 441 SCIP_CALL( SCIPnodeCutoff(node, scip->set, scip->stat, scip->tree, scip->transprob, scip->origprob, scip->reopt, 442 scip->lp, scip->mem->probmem) ); 443 444 return SCIP_OKAY; 445 } 446 447 /** removes all nodes from branch and bound tree that were marked to be cut off via SCIPcutoffNode() 448 * 449 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 450 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 451 * 452 * @pre This method can be called if @p scip is in one of the following stages: 453 * - \ref SCIP_STAGE_SOLVING 454 * 455 * @note In diving mode, the removal of nodes is delayed until diving ends. 456 */ 457 SCIP_RETCODE SCIPpruneTree( 458 SCIP* scip /**< SCIP data structure */ 459 ) 460 { 461 SCIP_CALL( SCIPcheckStage(scip, "SCIPpruneTree", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 462 463 SCIP_CALL( SCIPtreeCutoff(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter, 464 scip->eventqueue, scip->lp, SCIPinfinity(scip)) ); 465 466 return SCIP_OKAY; 467 } 468 469 /** marks the given node to be propagated again the next time a node of its subtree is processed 470 * 471 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 472 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 473 * 474 * @pre This method can be called if @p scip is in one of the following stages: 475 * - \ref SCIP_STAGE_SOLVING 476 */ 477 SCIP_RETCODE SCIPrepropagateNode( 478 SCIP* scip, /**< SCIP data structure */ 479 SCIP_NODE* node /**< node that should be propagated again */ 480 ) 481 { 482 SCIP_CALL( SCIPcheckStage(scip, "SCIPrepropagateNode", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 483 484 SCIPnodePropagateAgain(node, scip->set, scip->stat, scip->tree); 485 486 return SCIP_OKAY; 487 } 488 489 /** returns depth of first node in active path that is marked being cutoff 490 * 491 * @return depth of first node in active path that is marked being cutoff 492 * 493 * @pre This method can be called if @p scip is in one of the following stages: 494 * - \ref SCIP_STAGE_SOLVING 495 */ 496 int SCIPgetCutoffdepth( 497 SCIP* scip /**< SCIP data structure */ 498 ) 499 { 500 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetCutoffdepth", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 501 502 return scip->tree->cutoffdepth; 503 } 504 505 /** returns depth of first node in active path that has to be propagated again 506 * 507 * @return depth of first node in active path that has to be propagated again 508 * 509 * @pre This method can be called if @p scip is in one of the following stages: 510 * - \ref SCIP_STAGE_SOLVING 511 */ 512 int SCIPgetRepropdepth( 513 SCIP* scip /**< SCIP data structure */ 514 ) 515 { 516 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetRepropdepth", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 517 518 return scip->tree->repropdepth; 519 } 520 521 /** prints all branching decisions on variables from the root to the given node 522 * 523 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 524 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 525 * 526 * @pre This method can be called if @p scip is in one of the following stages: 527 * - \ref SCIP_STAGE_SOLVING 528 */ 529 SCIP_RETCODE SCIPprintNodeRootPath( 530 SCIP* scip, /**< SCIP data structure */ 531 SCIP_NODE* node, /**< node data */ 532 FILE* file /**< output file (or NULL for standard output) */ 533 ) 534 { 535 SCIP_VAR** branchvars; /* array of variables on which the branchings has been performed in all ancestors */ 536 SCIP_Real* branchbounds; /* array of bounds which the branchings in all ancestors set */ 537 SCIP_BOUNDTYPE* boundtypes; /* array of boundtypes which the branchings in all ancestors set */ 538 int* nodeswitches; /* marks, where in the arrays the branching decisions of the next node on the path start 539 * branchings performed at the parent of node always start at position 0. For single variable branching, 540 * nodeswitches[i] = i holds */ 541 int nbranchvars; /* number of variables on which branchings have been performed in all ancestors 542 * if this is larger than the array size, arrays should be reallocated and method should be called again */ 543 int branchvarssize; /* available slots in arrays */ 544 int nnodes; /* number of nodes in the nodeswitch array */ 545 int nodeswitchsize; /* available slots in node switch array */ 546 547 branchvarssize = SCIPnodeGetDepth(node); 548 nodeswitchsize = branchvarssize; 549 550 /* memory allocation */ 551 SCIP_CALL( SCIPallocBufferArray(scip, &branchvars, branchvarssize) ); 552 SCIP_CALL( SCIPallocBufferArray(scip, &branchbounds, branchvarssize) ); 553 SCIP_CALL( SCIPallocBufferArray(scip, &boundtypes, branchvarssize) ); 554 SCIP_CALL( SCIPallocBufferArray(scip, &nodeswitches, nodeswitchsize) ); 555 556 SCIPnodeGetAncestorBranchingPath(node, branchvars, branchbounds, boundtypes, &nbranchvars, branchvarssize, nodeswitches, &nnodes, nodeswitchsize ); 557 558 /* if the arrays were too small, we have to reallocate them and recall SCIPnodeGetAncestorBranchingPath */ 559 if( nbranchvars > branchvarssize || nnodes > nodeswitchsize ) 560 { 561 branchvarssize = nbranchvars; 562 nodeswitchsize = nnodes; 563 564 /* memory reallocation */ 565 SCIP_CALL( SCIPreallocBufferArray(scip, &branchvars, branchvarssize) ); 566 SCIP_CALL( SCIPreallocBufferArray(scip, &branchbounds, branchvarssize) ); 567 SCIP_CALL( SCIPreallocBufferArray(scip, &boundtypes, branchvarssize) ); 568 SCIP_CALL( SCIPreallocBufferArray(scip, &nodeswitches, nodeswitchsize) ); 569 570 SCIPnodeGetAncestorBranchingPath(node, branchvars, branchbounds, boundtypes, &nbranchvars, branchvarssize, nodeswitches, &nnodes, nodeswitchsize); 571 assert(nbranchvars == branchvarssize); 572 } 573 574 /* we only want to create output, if branchings were performed */ 575 if( nbranchvars >= 1 ) 576 { 577 int i; 578 int j; 579 580 /* print all nodes, starting from the root, which is last in the arrays */ 581 for( j = nnodes-1; j >= 0; --j) 582 { 583 int end; 584 if(j == nnodes-1) 585 end = nbranchvars; 586 else 587 end = nodeswitches[j+1]; 588 589 for( i = nodeswitches[j]; i < end; ++i ) 590 { 591 if( i > nodeswitches[j] ) 592 SCIPmessageFPrintInfo(scip->messagehdlr, file, " AND "); 593 SCIPmessageFPrintInfo(scip->messagehdlr, file, "<%s> %s %.1f",SCIPvarGetName(branchvars[i]), boundtypes[i] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", branchbounds[i]); 594 } 595 SCIPmessageFPrintInfo(scip->messagehdlr, file, "\n"); 596 if( j > 0 ) 597 { 598 if( nodeswitches[j]-nodeswitches[j-1] != 1 ) 599 SCIPmessageFPrintInfo(scip->messagehdlr, file, " |\n |\n"); 600 else if( boundtypes[i-1] == SCIP_BOUNDTYPE_LOWER ) 601 SCIPmessageFPrintInfo(scip->messagehdlr, file, "\\ \n \\\n"); 602 else 603 SCIPmessageFPrintInfo(scip->messagehdlr, file, " /\n/ \n"); 604 } 605 } 606 } 607 608 /* free all local memory */ 609 SCIPfreeBufferArray(scip, &nodeswitches); 610 SCIPfreeBufferArray(scip, &boundtypes); 611 SCIPfreeBufferArray(scip, &branchbounds); 612 SCIPfreeBufferArray(scip, &branchvars); 613 614 return SCIP_OKAY; 615 } 616 617 /** sets whether the LP should be solved at the focus node 618 * 619 * @note In order to have an effect, this method needs to be called after a node is focused but before the LP is 620 * solved. 621 * 622 * @pre This method can be called if @p scip is in one of the following stages: 623 * - \ref SCIP_STAGE_SOLVING 624 */ 625 void SCIPsetFocusnodeLP( 626 SCIP* scip, /**< SCIP data structure */ 627 SCIP_Bool solvelp /**< should the LP be solved? */ 628 ) 629 { 630 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPsetFocusnodeLP", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 631 632 SCIPtreeSetFocusNodeLP(scip->tree, solvelp); 633 } 634 635 /** gets number of nodes left in the tree (children + siblings + leaves) 636 * 637 * @return the number of nodes left in the tree (children + siblings + leaves) 638 * 639 * @pre This method can be called if SCIP is in one of the following stages: 640 * - \ref SCIP_STAGE_PRESOLVED 641 * - \ref SCIP_STAGE_SOLVING 642 * - \ref SCIP_STAGE_SOLVED 643 */ 644 int SCIPgetNNodesLeft( 645 SCIP* scip /**< SCIP data structure */ 646 ) 647 { 648 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNNodesLeft", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 649 650 return SCIPtreeGetNNodes(scip->tree); 651 } 652 653 /** gets depth of current node, or -1 if no current node exists; in probing, the current node is the last probing node, 654 * such that the depth includes the probing path 655 * 656 * @return the depth of current node, or -1 if no current node exists; in probing, the current node is the last probing node, 657 * such that the depth includes the probing path 658 * 659 * @pre This method can be called if SCIP is in one of the following stages: 660 * - \ref SCIP_STAGE_TRANSFORMED 661 * - \ref SCIP_STAGE_INITPRESOLVE 662 * - \ref SCIP_STAGE_PRESOLVING 663 * - \ref SCIP_STAGE_EXITPRESOLVE 664 * - \ref SCIP_STAGE_PRESOLVED 665 * - \ref SCIP_STAGE_INITSOLVE 666 * - \ref SCIP_STAGE_SOLVING 667 * - \ref SCIP_STAGE_SOLVED 668 * - \ref SCIP_STAGE_EXITSOLVE 669 */ 670 int SCIPgetDepth( 671 SCIP* scip /**< SCIP data structure */ 672 ) 673 { 674 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetDepth", FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE) ); 675 676 return SCIPtreeGetCurrentDepth(scip->tree); 677 } 678 679 /** gets depth of the focus node, or -1 if no focus node exists; the focus node is the currently processed node in the 680 * branching tree, excluding the nodes of the probing path 681 * 682 * @return the depth of the focus node, or -1 if no focus node exists; the focus node is the currently processed node in the 683 * branching tree, excluding the nodes of the probing path 684 * 685 * @pre This method can be called if SCIP is in one of the following stages: 686 * - \ref SCIP_STAGE_TRANSFORMED 687 * - \ref SCIP_STAGE_INITPRESOLVE 688 * - \ref SCIP_STAGE_PRESOLVING 689 * - \ref SCIP_STAGE_EXITPRESOLVE 690 * - \ref SCIP_STAGE_PRESOLVED 691 * - \ref SCIP_STAGE_INITSOLVE 692 * - \ref SCIP_STAGE_SOLVING 693 * - \ref SCIP_STAGE_SOLVED 694 * - \ref SCIP_STAGE_EXITSOLVE 695 */ 696 int SCIPgetFocusDepth( 697 SCIP* scip /**< SCIP data structure */ 698 ) 699 { 700 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetFocusDepth", FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE) ); 701 702 return SCIPtreeGetFocusDepth(scip->tree); 703 } 704 705 /** gets current plunging depth (successive times, a child was selected as next node) 706 * 707 * @return the current plunging depth (successive times, a child was selected as next node) 708 * 709 * @pre This method can be called if SCIP is in one of the following stages: 710 * - \ref SCIP_STAGE_PRESOLVED 711 * - \ref SCIP_STAGE_SOLVING 712 */ 713 int SCIPgetPlungeDepth( 714 SCIP* scip /**< SCIP data structure */ 715 ) 716 { 717 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetPlungeDepth", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 718 719 return scip->stat->plungedepth; 720 } 721 722 /** query if node was the last parent of a branching of the tree 723 * 724 * @return TRUE if node was the last parent of a branching of the tree 725 * 726 * @pre This method can be called if SCIP is in one of the following stages: 727 * - \ref SCIP_STAGE_PRESOLVED 728 * - \ref SCIP_STAGE_SOLVING 729 * - \ref SCIP_STAGE_SOLVED 730 */ 731 SCIP_Bool SCIPwasNodeLastBranchParent( 732 SCIP* scip, /**< SCIP data structure */ 733 SCIP_NODE* node /**< tree node, or NULL to check focus node */ 734 ) 735 { 736 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPwasNodeLastBranchParent", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 737 738 return SCIPtreeWasNodeLastBranchParent(scip->tree, node); 739 } 740