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 tree.h 17 * @ingroup INTERNALAPI 18 * @brief internal methods for branch and bound tree 19 * @author Tobias Achterberg 20 * @author Timo Berthold 21 */ 22 23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 24 25 #ifndef __SCIP_TREE_H__ 26 #define __SCIP_TREE_H__ 27 28 29 #include "blockmemshell/memory.h" 30 #include "scip/def.h" 31 #include "scip/nodesel.h" 32 #include "scip/type_set.h" 33 #include "scip/type_stat.h" 34 #include "scip/type_cons.h" 35 #include "scip/type_event.h" 36 #include "scip/type_lp.h" 37 #include "scip/type_var.h" 38 #include "scip/type_prob.h" 39 #include "scip/type_primal.h" 40 #include "scip/type_tree.h" 41 #include "scip/type_reopt.h" 42 #include "scip/type_branch.h" 43 #include "scip/type_prop.h" 44 #include "scip/type_implics.h" 45 #include "scip/type_history.h" 46 #include "scip/type_conflictstore.h" 47 #include "scip/pub_tree.h" 48 49 #ifndef NDEBUG 50 #include "scip/struct_tree.h" 51 #endif 52 53 #ifdef __cplusplus 54 extern "C" { 55 #endif 56 57 58 /* 59 * Node methods 60 */ 61 62 /** creates a child node of the focus node */ 63 SCIP_RETCODE SCIPnodeCreateChild( 64 SCIP_NODE** node, /**< pointer to node data structure */ 65 BMS_BLKMEM* blkmem, /**< block memory */ 66 SCIP_SET* set, /**< global SCIP settings */ 67 SCIP_STAT* stat, /**< problem statistics */ 68 SCIP_TREE* tree, /**< branch and bound tree */ 69 SCIP_Real nodeselprio, /**< node selection priority of new node */ 70 SCIP_Real estimate /**< estimate for (transformed) objective value of best feasible solution in subtree */ 71 ); 72 73 /** frees node */ 74 SCIP_RETCODE SCIPnodeFree( 75 SCIP_NODE** node, /**< node data */ 76 BMS_BLKMEM* blkmem, /**< block memory buffer */ 77 SCIP_SET* set, /**< global SCIP settings */ 78 SCIP_STAT* stat, /**< problem statistics */ 79 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 80 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 81 SCIP_TREE* tree, /**< branch and bound tree */ 82 SCIP_LP* lp /**< current LP data */ 83 ); 84 85 /** increases the reference counter of the LP state in the fork or subroot node */ 86 SCIP_RETCODE SCIPnodeCaptureLPIState( 87 SCIP_NODE* node, /**< fork/subroot node */ 88 int nuses /**< number to add to the usage counter */ 89 ); 90 91 /** decreases the reference counter of the LP state in the fork or subroot node */ 92 SCIP_RETCODE SCIPnodeReleaseLPIState( 93 SCIP_NODE* node, /**< fork/subroot node */ 94 BMS_BLKMEM* blkmem, /**< block memory buffers */ 95 SCIP_LP* lp /**< current LP data */ 96 ); 97 98 /** installs a child, a sibling, or a leaf node as the new focus node */ 99 SCIP_RETCODE SCIPnodeFocus( 100 SCIP_NODE** node, /**< pointer to node to focus (or NULL to remove focus); the node 101 * is freed, if it was cut off due to a cut off subtree */ 102 BMS_BLKMEM* blkmem, /**< block memory */ 103 SCIP_SET* set, /**< global SCIP settings */ 104 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 105 SCIP_STAT* stat, /**< problem statistics */ 106 SCIP_PROB* transprob, /**< transformed problem */ 107 SCIP_PROB* origprob, /**< original problem */ 108 SCIP_PRIMAL* primal, /**< primal data */ 109 SCIP_TREE* tree, /**< branch and bound tree */ 110 SCIP_REOPT* reopt, /**< reoptimization data structure */ 111 SCIP_LP* lp, /**< current LP data */ 112 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 113 SCIP_CONFLICT* conflict, /**< conflict analysis data */ 114 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 115 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 116 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 117 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 118 SCIP_Bool* cutoff, /**< pointer to store whether the given node can be cut off */ 119 SCIP_Bool postponed, /**< was the current focus node postponed? */ 120 SCIP_Bool exitsolve /**< are we in exitsolve stage, so we only need to loose the children */ 121 ); 122 123 /** cuts off node and whole sub tree from branch and bound tree */ 124 SCIP_RETCODE SCIPnodeCutoff( 125 SCIP_NODE* node, /**< node that should be cut off */ 126 SCIP_SET* set, /**< global SCIP settings */ 127 SCIP_STAT* stat, /**< problem statistics */ 128 SCIP_TREE* tree, /**< branch and bound tree */ 129 SCIP_PROB* transprob, /**< transformed problem after presolve */ 130 SCIP_PROB* origprob, /**< original problem */ 131 SCIP_REOPT* reopt, /**< reoptimization data structure */ 132 SCIP_LP* lp, /**< current LP */ 133 BMS_BLKMEM* blkmem /**< block memory */ 134 ); 135 136 /** marks node, that propagation should be applied again the next time, a node of its subtree is focused */ 137 void SCIPnodePropagateAgain( 138 SCIP_NODE* node, /**< node that should be propagated again */ 139 SCIP_SET* set, /**< global SCIP settings */ 140 SCIP_STAT* stat, /**< problem statistics */ 141 SCIP_TREE* tree /**< branch and bound tree */ 142 ); 143 144 /** marks node, that it is completely propagated in the current repropagation subtree level */ 145 void SCIPnodeMarkPropagated( 146 SCIP_NODE* node, /**< node that should be propagated again */ 147 SCIP_TREE* tree /**< branch and bound tree */ 148 ); 149 150 /** adds constraint locally to the node and captures it; activates constraint, if node is active; 151 * if a local constraint is added to the root node, it is automatically upgraded into a global constraint 152 */ 153 SCIP_RETCODE SCIPnodeAddCons( 154 SCIP_NODE* node, /**< node to add constraint to */ 155 BMS_BLKMEM* blkmem, /**< block memory */ 156 SCIP_SET* set, /**< global SCIP settings */ 157 SCIP_STAT* stat, /**< problem statistics */ 158 SCIP_TREE* tree, /**< branch and bound tree */ 159 SCIP_CONS* cons /**< constraint to add */ 160 ); 161 162 /** locally deletes constraint at the given node by disabling its separation, enforcing, and propagation capabilities 163 * at the node; captures constraint; disables constraint, if node is active 164 */ 165 SCIP_RETCODE SCIPnodeDelCons( 166 SCIP_NODE* node, /**< node to add constraint to */ 167 BMS_BLKMEM* blkmem, /**< block memory */ 168 SCIP_SET* set, /**< global SCIP settings */ 169 SCIP_STAT* stat, /**< problem statistics */ 170 SCIP_TREE* tree, /**< branch and bound tree */ 171 SCIP_CONS* cons /**< constraint to locally delete */ 172 ); 173 174 /** return all bound changes based on constraint propagation; stop saving the bound changes if we reach a branching 175 * decision based on a dual information 176 */ 177 void SCIPnodeGetConsProps( 178 SCIP_NODE* node, /**< node */ 179 SCIP_VAR** vars, /**< array of variables on which constraint propagation triggers a bound change */ 180 SCIP_Real* varbounds, /**< array of bounds set by constraint propagation */ 181 SCIP_BOUNDTYPE* varboundtypes, /**< array of boundtypes set by constraint propagation */ 182 int* nconspropvars, /**< number of variables on which constraint propagation triggers a bound change 183 * if this is larger than the array size, arrays should be reallocated and method 184 * should be called again */ 185 int conspropvarssize /**< available slots in arrays */ 186 ); 187 188 /** gets all bound changes applied after the first bound change based on dual information. 189 * 190 * @note: currently, we can only detect bound changes based in dual information if they arise from strong branching. 191 */ 192 void SCIPnodeGetBdChgsAfterDual( 193 SCIP_NODE* node, /**< node */ 194 SCIP_VAR** vars, /**< array of variables on which the branching has been performed in the parent node */ 195 SCIP_Real* varbounds, /**< array of bounds which the branching in the parent node set */ 196 SCIP_BOUNDTYPE* varboundtypes, /**< array of boundtypes which the branching in the parent node set */ 197 int start, /**< first free slot in the arrays */ 198 int* nbranchvars, /**< number of variables on which branching has been performed in the parent node 199 * if this is larger than the array size, arrays should be reallocated and method 200 * should be called again */ 201 int branchvarssize /**< available slots in arrays */ 202 ); 203 204 /** adds bound change with inference information to focus node, child of focus node, or probing node; 205 * if possible, adjusts bound to integral value; 206 * at most one of infercons and inferprop may be non-NULL 207 */ 208 SCIP_RETCODE SCIPnodeAddBoundinfer( 209 SCIP_NODE* node, /**< node to add bound change to */ 210 BMS_BLKMEM* blkmem, /**< block memory */ 211 SCIP_SET* set, /**< global SCIP settings */ 212 SCIP_STAT* stat, /**< problem statistics */ 213 SCIP_PROB* transprob, /**< transformed problem after presolve */ 214 SCIP_PROB* origprob, /**< original problem */ 215 SCIP_TREE* tree, /**< branch and bound tree */ 216 SCIP_REOPT* reopt, /**< reoptimization data structure */ 217 SCIP_LP* lp, /**< current LP data */ 218 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 219 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 220 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 221 SCIP_VAR* var, /**< variable to change the bounds for */ 222 SCIP_Real newbound, /**< new value for bound */ 223 SCIP_BOUNDTYPE boundtype, /**< type of bound: lower or upper bound */ 224 SCIP_CONS* infercons, /**< constraint that deduced the bound change, or NULL */ 225 SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */ 226 int inferinfo, /**< user information for inference to help resolving the conflict */ 227 SCIP_Bool probingchange /**< is the bound change a temporary setting due to probing? */ 228 ); 229 230 /** adds bound change to focus node, or child of focus node, or probing node; 231 * if possible, adjusts bound to integral value 232 */ 233 SCIP_RETCODE SCIPnodeAddBoundchg( 234 SCIP_NODE* node, /**< node to add bound change to */ 235 BMS_BLKMEM* blkmem, /**< block memory */ 236 SCIP_SET* set, /**< global SCIP settings */ 237 SCIP_STAT* stat, /**< problem statistics */ 238 SCIP_PROB* transprob, /**< transformed problem after presolve */ 239 SCIP_PROB* origprob, /**< original problem */ 240 SCIP_TREE* tree, /**< branch and bound tree */ 241 SCIP_REOPT* reopt, /**< reoptimization data structure */ 242 SCIP_LP* lp, /**< current LP data */ 243 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 244 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 245 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 246 SCIP_VAR* var, /**< variable to change the bounds for */ 247 SCIP_Real newbound, /**< new value for bound */ 248 SCIP_BOUNDTYPE boundtype, /**< type of bound: lower or upper bound */ 249 SCIP_Bool probingchange /**< is the bound change a temporary setting due to probing? */ 250 ); 251 252 /** adds hole with inference information to focus node, child of focus node, or probing node; 253 * if possible, adjusts bound to integral value; 254 * at most one of infercons and inferprop may be non-NULL 255 */ 256 SCIP_RETCODE SCIPnodeAddHoleinfer( 257 SCIP_NODE* node, /**< node to add bound change to */ 258 BMS_BLKMEM* blkmem, /**< block memory */ 259 SCIP_SET* set, /**< global SCIP settings */ 260 SCIP_STAT* stat, /**< problem statistics */ 261 SCIP_TREE* tree, /**< branch and bound tree */ 262 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 263 SCIP_VAR* var, /**< variable to change the bounds for */ 264 SCIP_Real left, /**< left bound of open interval defining the hole (left,right) */ 265 SCIP_Real right, /**< right bound of open interval defining the hole (left,right) */ 266 SCIP_CONS* infercons, /**< constraint that deduced the bound change, or NULL */ 267 SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */ 268 int inferinfo, /**< user information for inference to help resolving the conflict */ 269 SCIP_Bool probingchange, /**< is the bound change a temporary setting due to probing? */ 270 SCIP_Bool* added /**< pointer to store whether the hole was added, or NULL */ 271 ); 272 273 /** adds hole change to focus node, or child of focus node */ 274 SCIP_RETCODE SCIPnodeAddHolechg( 275 SCIP_NODE* node, /**< node to add bound change to */ 276 BMS_BLKMEM* blkmem, /**< block memory */ 277 SCIP_SET* set, /**< global SCIP settings */ 278 SCIP_STAT* stat, /**< problem statistics */ 279 SCIP_TREE* tree, /**< branch and bound tree */ 280 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 281 SCIP_VAR* var, /**< variable to change the bounds for */ 282 SCIP_Real left, /**< left bound of open interval defining the hole (left,right) */ 283 SCIP_Real right, /**< right bound of open interval defining the hole (left,right) */ 284 SCIP_Bool probingchange, /**< is the bound change a temporary setting due to probing? */ 285 SCIP_Bool* added /**< pointer to store whether the hole was added, or NULL */ 286 ); 287 288 /** if given value is larger than the node's lower bound, sets the node's lower bound to the new value */ 289 void SCIPnodeUpdateLowerbound( 290 SCIP_NODE* node, /**< node to update lower bound for */ 291 SCIP_STAT* stat, /**< problem statistics */ 292 SCIP_SET* set, /**< global SCIP settings */ 293 SCIP_TREE* tree, /**< branch and bound tree */ 294 SCIP_PROB* transprob, /**< transformed problem data */ 295 SCIP_PROB* origprob, /**< original problem */ 296 SCIP_Real newbound /**< new lower bound for the node (if it's larger than the old one) */ 297 ); 298 299 /** updates lower bound of node using lower bound of LP */ 300 SCIP_RETCODE SCIPnodeUpdateLowerboundLP( 301 SCIP_NODE* node, /**< node to set lower bound for */ 302 SCIP_SET* set, /**< global SCIP settings */ 303 SCIP_STAT* stat, /**< problem statistics */ 304 SCIP_TREE* tree, /**< branch and bound tree */ 305 SCIP_PROB* transprob, /**< transformed problem after presolve */ 306 SCIP_PROB* origprob, /**< original problem */ 307 SCIP_LP* lp /**< LP data */ 308 ); 309 310 /** change the node selection priority of the given child */ 311 void SCIPchildChgNodeselPrio( 312 SCIP_TREE* tree, /**< branch and bound tree */ 313 SCIP_NODE* child, /**< child to update the node selection priority */ 314 SCIP_Real priority /**< node selection priority value */ 315 ); 316 317 318 /** sets the node's estimated bound to the new value */ 319 void SCIPnodeSetEstimate( 320 SCIP_NODE* node, /**< node to update lower bound for */ 321 SCIP_SET* set, /**< global SCIP settings */ 322 SCIP_Real newestimate /**< new estimated bound for the node */ 323 ); 324 325 /** propagates implications of binary fixings at the given node triggered by the implication graph and the clique table */ 326 SCIP_RETCODE SCIPnodePropagateImplics( 327 SCIP_NODE* node, /**< node to propagate implications on */ 328 BMS_BLKMEM* blkmem, /**< block memory */ 329 SCIP_SET* set, /**< global SCIP settings */ 330 SCIP_STAT* stat, /**< problem statistics */ 331 SCIP_PROB* transprob, /**< transformed problem after presolve */ 332 SCIP_PROB* origprob, /**< original problem */ 333 SCIP_TREE* tree, /**< branch and bound tree */ 334 SCIP_REOPT* reopt, /**< reoptimization data structure */ 335 SCIP_LP* lp, /**< current LP data */ 336 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 337 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 338 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 339 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */ 340 ); 341 342 /** returns all bound changes based on dual information. 343 * 344 * currently, this methods works only for bound changes made by strong branching on binary variables. we need this 345 * method to ensure optimality within reoptimization. 346 * 347 * since the bound changes made by strong branching are stored as SCIP_BOUNDCHGTYPE_CONSINFER or SCIP_BOUNDCHGTYPE_PROPINFER 348 * with no constraint or propagator, resp., we are are interested in bound changes with these attributes. 349 * 350 * all bound changes of type SCIP_BOUNDCHGTYPE_BRANCHING are stored in the beginning of the bound change array, afterwards, 351 * we can find the other two types. thus, we start the search at the end of the list and stop when reaching the first 352 * bound change of type SCIP_BOUNDCHGTYPE_BRANCHING. 353 */ 354 void SCIPnodeGetDualBoundchgs( 355 SCIP_NODE* node, /**< node data */ 356 SCIP_VAR** vars, /**< array of variables on which the bound change is based on dual information */ 357 SCIP_Real* bounds, /**< array of bounds which are based on dual information */ 358 SCIP_BOUNDTYPE* boundtypes, /**< array of boundtypes which are based on dual information */ 359 int* nvars, /**< number of variables on which the bound change is based on dual information 360 * if this is larger than the array size, arrays should be reallocated and method 361 * should be called again */ 362 int varssize /**< available slots in arrays */ 363 ); 364 365 /** returns the number of bound changes based on dual information. 366 * 367 * currently, this methods works only for bound changes made by strong branching on binary variables. we need this 368 * method to ensure optimality within reoptimization. 369 * 370 * since the bound changes made by strong branching are stored as SCIP_BOUNDCHGTYPE_CONSINFER or SCIP_BOUNDCHGTYPE_PROPINFER 371 * with no constraint or propagator, resp., we are are interested in bound changes with these attributes. 372 * 373 * all bound changes of type SCIP_BOUNDCHGTYPE_BRANCHING are stored in the beginning of the bound change array, afterwards, 374 * we can find the other two types. thus, we start the search at the end of the list and stop when reaching the first 375 * bound change of type SCIP_BOUNDCHGTYPE_BRANCHING. 376 */ 377 int SCIPnodeGetNDualBndchgs( 378 SCIP_NODE* node 379 ); 380 381 /* 382 * Tree methods 383 */ 384 385 /** creates an initialized tree data structure */ 386 SCIP_RETCODE SCIPtreeCreate( 387 SCIP_TREE** tree, /**< pointer to tree data structure */ 388 BMS_BLKMEM* blkmem, /**< block memory buffers */ 389 SCIP_SET* set, /**< global SCIP settings */ 390 SCIP_NODESEL* nodesel /**< node selector to use for sorting leaves in the priority queue */ 391 ); 392 393 /** frees tree data structure */ 394 SCIP_RETCODE SCIPtreeFree( 395 SCIP_TREE** tree, /**< pointer to tree data structure */ 396 BMS_BLKMEM* blkmem, /**< block memory buffers */ 397 SCIP_SET* set, /**< global SCIP settings */ 398 SCIP_STAT* stat, /**< problem statistics */ 399 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 400 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 401 SCIP_LP* lp /**< current LP data */ 402 ); 403 404 /** clears and resets tree data structure and deletes all nodes */ 405 SCIP_RETCODE SCIPtreeClear( 406 SCIP_TREE* tree, /**< tree data structure */ 407 BMS_BLKMEM* blkmem, /**< block memory buffers */ 408 SCIP_SET* set, /**< global SCIP settings */ 409 SCIP_STAT* stat, /**< problem statistics */ 410 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 411 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 412 SCIP_LP* lp /**< current LP data */ 413 ); 414 415 /** creates the root node of the tree and puts it into the leaves queue */ 416 SCIP_RETCODE SCIPtreeCreateRoot( 417 SCIP_TREE* tree, /**< tree data structure */ 418 SCIP_REOPT* reopt, /**< reoptimization data structure */ 419 BMS_BLKMEM* blkmem, /**< block memory buffers */ 420 SCIP_SET* set, /**< global SCIP settings */ 421 SCIP_STAT* stat, /**< problem statistics */ 422 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 423 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 424 SCIP_LP* lp /**< current LP data */ 425 ); 426 427 /** creates a temporary presolving root node of the tree and installs it as focus node */ 428 SCIP_RETCODE SCIPtreeCreatePresolvingRoot( 429 SCIP_TREE* tree, /**< tree data structure */ 430 SCIP_REOPT* reopt, /**< reoptimization data structure */ 431 BMS_BLKMEM* blkmem, /**< block memory buffers */ 432 SCIP_SET* set, /**< global SCIP settings */ 433 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 434 SCIP_STAT* stat, /**< problem statistics */ 435 SCIP_PROB* transprob, /**< transformed problem */ 436 SCIP_PROB* origprob, /**< original problem */ 437 SCIP_PRIMAL* primal, /**< primal data */ 438 SCIP_LP* lp, /**< current LP data */ 439 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 440 SCIP_CONFLICT* conflict, /**< conflict analysis data */ 441 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 442 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 443 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 444 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */ 445 ); 446 447 /** frees the temporary presolving root and resets tree data structure */ 448 SCIP_RETCODE SCIPtreeFreePresolvingRoot( 449 SCIP_TREE* tree, /**< tree data structure */ 450 SCIP_REOPT* reopt, /**< reoptimization data structure */ 451 BMS_BLKMEM* blkmem, /**< block memory buffers */ 452 SCIP_SET* set, /**< global SCIP settings */ 453 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 454 SCIP_STAT* stat, /**< problem statistics */ 455 SCIP_PROB* transprob, /**< transformed problem */ 456 SCIP_PROB* origprob, /**< original problem */ 457 SCIP_PRIMAL* primal, /**< primal data */ 458 SCIP_LP* lp, /**< current LP data */ 459 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 460 SCIP_CONFLICT* conflict, /**< conflict analysis data */ 461 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 462 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 463 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 464 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */ 465 ); 466 467 /** returns the node selector associated with the given node priority queue */ 468 SCIP_NODESEL* SCIPtreeGetNodesel( 469 SCIP_TREE* tree /**< branch and bound tree */ 470 ); 471 472 /** sets the node selector used for sorting the nodes in the priority queue, and resorts the queue if necessary */ 473 SCIP_RETCODE SCIPtreeSetNodesel( 474 SCIP_TREE* tree, /**< branch and bound tree */ 475 SCIP_SET* set, /**< global SCIP settings */ 476 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 477 SCIP_STAT* stat, /**< problem statistics */ 478 SCIP_NODESEL* nodesel /**< node selector to use for sorting the nodes in the queue */ 479 ); 480 481 /** cuts off nodes with lower bound not better than given upper bound */ 482 SCIP_RETCODE SCIPtreeCutoff( 483 SCIP_TREE* tree, /**< branch and bound tree */ 484 SCIP_REOPT* reopt, /**< reoptimization data structure */ 485 BMS_BLKMEM* blkmem, /**< block memory */ 486 SCIP_SET* set, /**< global SCIP settings */ 487 SCIP_STAT* stat, /**< dynamic problem statistics */ 488 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 489 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 490 SCIP_LP* lp, /**< current LP data */ 491 SCIP_Real cutoffbound /**< cutoff bound: all nodes with lowerbound >= cutoffbound are cut off */ 492 ); 493 494 /** constructs the LP relaxation of the focus node */ 495 SCIP_RETCODE SCIPtreeLoadLP( 496 SCIP_TREE* tree, /**< branch and bound tree */ 497 BMS_BLKMEM* blkmem, /**< block memory */ 498 SCIP_SET* set, /**< global SCIP settings */ 499 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 500 SCIP_EVENTFILTER* eventfilter, /**< global event filter */ 501 SCIP_LP* lp, /**< current LP data */ 502 SCIP_Bool* initroot /**< pointer to store whether the root LP relaxation has to be initialized */ 503 ); 504 505 /** loads LP state for fork/subroot of the focus node */ 506 SCIP_RETCODE SCIPtreeLoadLPState( 507 SCIP_TREE* tree, /**< branch and bound tree */ 508 BMS_BLKMEM* blkmem, /**< block memory buffers */ 509 SCIP_SET* set, /**< global SCIP settings */ 510 SCIP_STAT* stat, /**< dynamic problem statistics */ 511 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 512 SCIP_LP* lp /**< current LP data */ 513 ); 514 515 /** calculates the node selection priority for moving the given variable's LP value to the given target value; 516 * this node selection priority can be given to the SCIPcreateChild() call 517 */ 518 SCIP_Real SCIPtreeCalcNodeselPriority( 519 SCIP_TREE* tree, /**< branch and bound tree */ 520 SCIP_SET* set, /**< global SCIP settings */ 521 SCIP_STAT* stat, /**< dynamic problem statistics */ 522 SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */ 523 SCIP_BRANCHDIR branchdir, /**< type of branching that was performed: upwards, downwards, or fixed 524 * fixed should only be used, when both bounds changed 525 */ 526 SCIP_Real targetvalue /**< new value of the variable in the child node */ 527 ); 528 529 /** calculates an estimate for the objective of the best feasible solution contained in the subtree after applying the given 530 * branching; this estimate can be given to the SCIPcreateChild() call 531 */ 532 SCIP_Real SCIPtreeCalcChildEstimate( 533 SCIP_TREE* tree, /**< branch and bound tree */ 534 SCIP_SET* set, /**< global SCIP settings */ 535 SCIP_STAT* stat, /**< dynamic problem statistics */ 536 SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */ 537 SCIP_Real targetvalue /**< new value of the variable in the child node */ 538 ); 539 540 /** branches on a variable x 541 * if x is a continuous variable, then two child nodes will be created 542 * (x <= x', x >= x') 543 * but if the bounds of x are such that their relative difference is smaller than epsilon, 544 * the variable is fixed to val (if not SCIP_INVALID) or a well chosen alternative in the current node, 545 * i.e., no children are created 546 * if x is not a continuous variable, then: 547 * if solution value x' is fractional, two child nodes will be created 548 * (x <= floor(x'), x >= ceil(x')), 549 * if solution value is integral, the x' is equal to lower or upper bound of the branching 550 * variable and the bounds of x are finite, then two child nodes will be created 551 * (x <= x", x >= x"+1 with x" = floor((lb + ub)/2)), 552 * otherwise (up to) three child nodes will be created 553 * (x <= x'-1, x == x', x >= x'+1) 554 * if solution value is equal to one of the bounds and the other bound is infinite, only two child nodes 555 * will be created (the third one would be infeasible anyway) 556 */ 557 SCIP_RETCODE SCIPtreeBranchVar( 558 SCIP_TREE* tree, /**< branch and bound tree */ 559 SCIP_REOPT* reopt, /**< reoptimization data structure */ 560 BMS_BLKMEM* blkmem, /**< block memory */ 561 SCIP_SET* set, /**< global SCIP settings */ 562 SCIP_STAT* stat, /**< problem statistics data */ 563 SCIP_PROB* transprob, /**< transformed problem after presolve */ 564 SCIP_PROB* origprob, /**< original problem */ 565 SCIP_LP* lp, /**< current LP data */ 566 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 567 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 568 SCIP_VAR* var, /**< variable to branch on */ 569 SCIP_Real val, /**< value to branch on or SCIP_INVALID for branching on current LP/pseudo solution. A branching value is required for branching on continuous variables */ 570 SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */ 571 SCIP_NODE** eqchild, /**< pointer to return the middle child with variable fixed, or NULL */ 572 SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */ 573 ); 574 575 /** branches a variable x using the given domain hole; two child nodes will be created (x <= left, x >= right) */ 576 SCIP_RETCODE SCIPtreeBranchVarHole( 577 SCIP_TREE* tree, /**< branch and bound tree */ 578 SCIP_REOPT* reopt, /**< reoptimization data structure */ 579 BMS_BLKMEM* blkmem, /**< block memory */ 580 SCIP_SET* set, /**< global SCIP settings */ 581 SCIP_STAT* stat, /**< problem statistics data */ 582 SCIP_PROB* transprob, /**< transformed problem after presolve */ 583 SCIP_PROB* origprob, /**< original problem */ 584 SCIP_LP* lp, /**< current LP data */ 585 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 586 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 587 SCIP_VAR* var, /**< variable to branch on */ 588 SCIP_Real left, /**< left side of the domain hole */ 589 SCIP_Real right, /**< right side of the domain hole */ 590 SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */ 591 SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */ 592 ); 593 594 /** n-ary branching on a variable x 595 * Branches on variable x such that up to n/2 children are created on each side of the usual branching value. 596 * The branching value is selected as in SCIPtreeBranchVar(). 597 * If n is 2 or the variables local domain is too small for a branching into n pieces, SCIPtreeBranchVar() is called. 598 * The parameters minwidth and widthfactor determine the domain width of the branching variable in the child nodes. 599 * If n is odd, one child with domain width 'width' and having the branching value in the middle is created. 600 * Otherwise, two children with domain width 'width' and being left and right of the branching value are created. 601 * Next further nodes to the left and right are created, where width is multiplied by widthfactor with increasing distance from the first nodes. 602 * The initial width is calculated such that n/2 nodes are created to the left and to the right of the branching value. 603 * If this value is below minwidth, the initial width is set to minwidth, which may result in creating less than n nodes. 604 * 605 * Giving a large value for widthfactor results in creating children with small domain when close to the branching value 606 * and large domain when closer to the current variable bounds. That is, setting widthfactor to a very large value and n to 3 607 * results in a ternary branching where the branching variable is mostly fixed in the middle child. 608 * Setting widthfactor to 1.0 results in children where the branching variable always has the same domain width 609 * (except for one child if the branching value is not in the middle). 610 */ 611 SCIP_RETCODE SCIPtreeBranchVarNary( 612 SCIP_TREE* tree, /**< branch and bound tree */ 613 SCIP_REOPT* reopt, /**< reoptimization data structure */ 614 BMS_BLKMEM* blkmem, /**< block memory */ 615 SCIP_SET* set, /**< global SCIP settings */ 616 SCIP_STAT* stat, /**< problem statistics data */ 617 SCIP_PROB* transprob, /**< transformed problem after presolve */ 618 SCIP_PROB* origprob, /**< original problem */ 619 SCIP_LP* lp, /**< current LP data */ 620 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 621 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 622 SCIP_VAR* var, /**< variable to branch on */ 623 SCIP_Real val, /**< value to branch on or SCIP_INVALID for branching on current LP/pseudo solution. 624 * A branching value is required for branching on continuous variables */ 625 int n, /**< attempted number of children to be created, must be >= 2 */ 626 SCIP_Real minwidth, /**< minimal domain width in children */ 627 SCIP_Real widthfactor, /**< multiplier for children domain width with increasing distance from val, must be >= 1.0 */ 628 int* nchildren /**< buffer to store number of created children, or NULL */ 629 ); 630 631 /** adds a diving bound change to the tree together with the information if this is a bound change 632 * for the preferred direction or not 633 */ 634 SCIP_RETCODE SCIPtreeAddDiveBoundChange( 635 SCIP_TREE* tree, /**< branch and bound tree */ 636 BMS_BLKMEM* blkmem, /**< block memory buffers */ 637 SCIP_VAR* var, /**< variable to apply the bound change to */ 638 SCIP_BRANCHDIR dir, /**< direction of the bound change */ 639 SCIP_Real value, /**< value to adjust this variable bound to */ 640 SCIP_Bool preferred /**< is this a bound change for the preferred child? */ 641 ); 642 643 /** get the dive bound change data for the preferred or the alternative direction */ 644 void SCIPtreeGetDiveBoundChangeData( 645 SCIP_TREE* tree, /**< branch and bound tree */ 646 SCIP_VAR*** variables, /**< pointer to store variables for the specified direction */ 647 SCIP_BRANCHDIR** directions, /**< pointer to store the branching directions */ 648 SCIP_Real** values, /**< pointer to store bound change values */ 649 int* ndivebdchgs, /**< pointer to store the number of dive bound changes */ 650 SCIP_Bool preferred /**< should the dive bound changes for the preferred child be output? */ 651 ); 652 653 /** clear the tree dive bound change data structure */ 654 void SCIPtreeClearDiveBoundChanges( 655 SCIP_TREE* tree /**< branch and bound tree */ 656 ); 657 658 /** switches to probing mode and creates a probing root */ 659 SCIP_RETCODE SCIPtreeStartProbing( 660 SCIP_TREE* tree, /**< branch and bound tree */ 661 BMS_BLKMEM* blkmem, /**< block memory */ 662 SCIP_SET* set, /**< global SCIP settings */ 663 SCIP_LP* lp, /**< current LP data */ 664 SCIP_RELAXATION* relaxation, /**< global relaxation data */ 665 SCIP_PROB* transprob, /**< transformed problem after presolve */ 666 SCIP_Bool strongbranching /**< is the probing mode used for strongbranching? */ 667 ); 668 669 /** creates a new probing child node in the probing path */ 670 SCIP_RETCODE SCIPtreeCreateProbingNode( 671 SCIP_TREE* tree, /**< branch and bound tree */ 672 BMS_BLKMEM* blkmem, /**< block memory */ 673 SCIP_SET* set, /**< global SCIP settings */ 674 SCIP_LP* lp /**< current LP data */ 675 ); 676 677 /** sets the LP state for the current probing node 678 * 679 * @note state and norms are stored at the node and later released by SCIP; therefore, the pointers are set 680 * to NULL by the method 681 * 682 * @note the pointers to state and norms must not be NULL; however, they may point to a NULL pointer if the 683 * respective information should not be set 684 */ 685 SCIP_RETCODE SCIPtreeSetProbingLPState( 686 SCIP_TREE* tree, /**< branch and bound tree */ 687 BMS_BLKMEM* blkmem, /**< block memory */ 688 SCIP_LP* lp, /**< current LP data */ 689 SCIP_LPISTATE** lpistate, /**< pointer to LP state information (like basis information) */ 690 SCIP_LPINORMS** lpinorms, /**< pointer to LP pricing norms information */ 691 SCIP_Bool primalfeas, /**< primal feasibility when LP state information was stored */ 692 SCIP_Bool dualfeas /**< dual feasibility when LP state information was stored */ 693 ); 694 695 /** loads the LP state for the current probing node */ 696 SCIP_RETCODE SCIPtreeLoadProbingLPState( 697 SCIP_TREE* tree, /**< branch and bound tree */ 698 BMS_BLKMEM* blkmem, /**< block memory buffers */ 699 SCIP_SET* set, /**< global SCIP settings */ 700 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 701 SCIP_LP* lp /**< current LP data */ 702 ); 703 704 /** marks the probing node to have a solved LP relaxation */ 705 SCIP_RETCODE SCIPtreeMarkProbingNodeHasLP( 706 SCIP_TREE* tree, /**< branch and bound tree */ 707 BMS_BLKMEM* blkmem, /**< block memory */ 708 SCIP_LP* lp /**< current LP data */ 709 ); 710 711 /** undoes all changes to the problem applied in probing up to the given probing depth; 712 * the changes of the probing node of the given probing depth are the last ones that remain active; 713 * changes that were applied before calling SCIPtreeCreateProbingNode() cannot be undone 714 */ 715 SCIP_RETCODE SCIPtreeBacktrackProbing( 716 SCIP_TREE* tree, /**< branch and bound tree */ 717 SCIP_REOPT* reopt, /**< reoptimization data structure */ 718 BMS_BLKMEM* blkmem, /**< block memory buffers */ 719 SCIP_SET* set, /**< global SCIP settings */ 720 SCIP_STAT* stat, /**< problem statistics */ 721 SCIP_PROB* transprob, /**< transformed problem */ 722 SCIP_PROB* origprob, /**< original problem */ 723 SCIP_LP* lp, /**< current LP data */ 724 SCIP_PRIMAL* primal, /**< primal data structure */ 725 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 726 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 727 SCIP_EVENTFILTER* eventfilter, /**< global event filter */ 728 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 729 int probingdepth /**< probing depth of the node in the probing path that should be reactivated */ 730 ); 731 732 /** switches back from probing to normal operation mode, frees all nodes on the probing path, restores bounds of all 733 * variables and restores active constraints arrays of focus node 734 */ 735 SCIP_RETCODE SCIPtreeEndProbing( 736 SCIP_TREE* tree, /**< branch and bound tree */ 737 SCIP_REOPT* reopt, /**< reoptimization data structure */ 738 BMS_BLKMEM* blkmem, /**< block memory buffers */ 739 SCIP_SET* set, /**< global SCIP settings */ 740 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 741 SCIP_STAT* stat, /**< problem statistics */ 742 SCIP_PROB* transprob, /**< transformed problem after presolve */ 743 SCIP_PROB* origprob, /**< original problem */ 744 SCIP_LP* lp, /**< current LP data */ 745 SCIP_RELAXATION* relaxation, /**< global relaxation data */ 746 SCIP_PRIMAL* primal, /**< primal LP data */ 747 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 748 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 749 SCIP_EVENTFILTER* eventfilter, /**< global event filter */ 750 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */ 751 ); 752 753 /** stores relaxation solution before diving or probing */ 754 SCIP_RETCODE SCIPtreeStoreRelaxSol( 755 SCIP_TREE* tree, /**< branch and bound tree */ 756 SCIP_SET* set, /**< global SCIP settings */ 757 SCIP_RELAXATION* relaxation, /**< global relaxation data */ 758 SCIP_PROB* transprob /**< transformed problem after presolve */ 759 ); 760 761 /** restores relaxation solution after diving or probing */ 762 SCIP_RETCODE SCIPtreeRestoreRelaxSol( 763 SCIP_TREE* tree, /**< branch and bound tree */ 764 SCIP_SET* set, /**< global SCIP settings */ 765 SCIP_RELAXATION* relaxation, /**< global relaxation data */ 766 SCIP_PROB* transprob /**< transformed problem after presolve */ 767 ); 768 769 770 /** gets number of children of the focus node */ 771 int SCIPtreeGetNChildren( 772 SCIP_TREE* tree /**< branch and bound tree */ 773 ); 774 775 /** gets number of siblings of the focus node */ 776 int SCIPtreeGetNSiblings( 777 SCIP_TREE* tree /**< branch and bound tree */ 778 ); 779 780 /** gets number of leaves in the tree (excluding children and siblings of focus nodes) */ 781 int SCIPtreeGetNLeaves( 782 SCIP_TREE* tree /**< branch and bound tree */ 783 ); 784 785 /** gets number of open nodes in the tree (children + siblings + leaves) */ 786 int SCIPtreeGetNNodes( 787 SCIP_TREE* tree /**< branch and bound tree */ 788 ); 789 790 /** returns whether the active path goes completely down to the focus node */ 791 SCIP_Bool SCIPtreeIsPathComplete( 792 SCIP_TREE* tree /**< branch and bound tree */ 793 ); 794 795 /** returns whether the current node is a temporary probing node */ 796 SCIP_Bool SCIPtreeProbing( 797 SCIP_TREE* tree /**< branch and bound tree */ 798 ); 799 800 /** returns the temporary probing root node, or NULL if the we are not in probing mode */ 801 SCIP_NODE* SCIPtreeGetProbingRoot( 802 SCIP_TREE* tree /**< branch and bound tree */ 803 ); 804 805 /** returns the current probing depth, i.e. the number of probing sub nodes existing in the probing path */ 806 int SCIPtreeGetProbingDepth( 807 SCIP_TREE* tree /**< branch and bound tree */ 808 ); 809 810 /** gets focus node of the tree */ 811 SCIP_NODE* SCIPtreeGetFocusNode( 812 SCIP_TREE* tree /**< branch and bound tree */ 813 ); 814 815 /** gets depth of focus node in the tree, or -1 if no focus node exists */ 816 int SCIPtreeGetFocusDepth( 817 SCIP_TREE* tree /**< branch and bound tree */ 818 ); 819 820 /** returns, whether the LP was or is to be solved in the focus node */ 821 SCIP_Bool SCIPtreeHasFocusNodeLP( 822 SCIP_TREE* tree /**< branch and bound tree */ 823 ); 824 825 /** sets mark to solve or to ignore the LP while processing the focus node */ 826 void SCIPtreeSetFocusNodeLP( 827 SCIP_TREE* tree, /**< branch and bound tree */ 828 SCIP_Bool solvelp /**< should the LP be solved in focus node? */ 829 ); 830 831 /** returns whether the LP of the focus node is already constructed */ 832 SCIP_Bool SCIPtreeIsFocusNodeLPConstructed( 833 SCIP_TREE* tree /**< branch and bound tree */ 834 ); 835 836 /** returns whether the focus node is already solved and only propagated again */ 837 SCIP_Bool SCIPtreeInRepropagation( 838 SCIP_TREE* tree /**< branch and bound tree */ 839 ); 840 841 /** gets current node of the tree, i.e. the last node in the active path, or NULL if no current node exists */ 842 SCIP_NODE* SCIPtreeGetCurrentNode( 843 SCIP_TREE* tree /**< branch and bound tree */ 844 ); 845 846 /** gets depth of current node in the tree, i.e. the length of the active path minus 1, or -1 if no current node exists */ 847 int SCIPtreeGetCurrentDepth( 848 SCIP_TREE* tree /**< branch and bound tree */ 849 ); 850 851 /** returns, whether the LP was or is to be solved in the current node */ 852 SCIP_Bool SCIPtreeHasCurrentNodeLP( 853 SCIP_TREE* tree /**< branch and bound tree */ 854 ); 855 856 /** returns the depth of the effective root node (i.e. the first depth level of a node with at least two children) */ 857 int SCIPtreeGetEffectiveRootDepth( 858 SCIP_TREE* tree /**< branch and bound tree */ 859 ); 860 861 /** gets the root node of the tree */ 862 SCIP_NODE* SCIPtreeGetRootNode( 863 SCIP_TREE* tree /**< branch and bound tree */ 864 ); 865 866 /** returns whether we are in probing and the objective value of at least one column was changed */ 867 SCIP_Bool SCIPtreeProbingObjChanged( 868 SCIP_TREE* tree /**< branch and bound tree */ 869 ); 870 871 /** marks the current probing node to have a changed objective function */ 872 void SCIPtreeMarkProbingObjChanged( 873 SCIP_TREE* tree /**< branch and bound tree */ 874 ); 875 876 #ifdef NDEBUG 877 878 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and 879 * speed up the algorithms. 880 */ 881 882 #define SCIPtreeGetNLeaves(tree) SCIPnodepqLen((tree)->leaves) 883 #define SCIPtreeGetNChildren(tree) ((tree)->nchildren) 884 #define SCIPtreeGetNSiblings(tree) ((tree)->nsiblings) 885 #define SCIPtreeGetNNodes(tree) \ 886 (SCIPtreeGetNChildren(tree) + SCIPtreeGetNSiblings(tree) + SCIPtreeGetNLeaves(tree)) 887 #define SCIPtreeIsPathComplete(tree) ((tree)->focusnode == NULL || (tree)->focusnode->depth < (tree)->pathlen) 888 #define SCIPtreeProbing(tree) ((tree)->probingroot != NULL) 889 #define SCIPtreeGetProbingRoot(tree) (tree)->probingroot 890 #define SCIPtreeGetProbingDepth(tree) (SCIPtreeGetCurrentDepth(tree) - SCIPnodeGetDepth((tree)->probingroot)) 891 #define SCIPtreeGetFocusNode(tree) (tree)->focusnode 892 #define SCIPtreeGetFocusDepth(tree) ((tree)->focusnode != NULL ? (int)(tree)->focusnode->depth : -1) 893 #define SCIPtreeHasFocusNodeLP(tree) (tree)->focusnodehaslp 894 #define SCIPtreeSetFocusNodeLP(tree,solvelp) ((tree)->focusnodehaslp = solvelp) 895 #define SCIPtreeIsFocusNodeLPConstructed(tree) (tree)->focuslpconstructed 896 #define SCIPtreeInRepropagation(tree) ((tree)->focusnode != NULL \ 897 && SCIPnodeGetType((tree)->focusnode) == SCIP_NODETYPE_REFOCUSNODE) 898 #define SCIPtreeGetCurrentNode(tree) ((tree)->pathlen > 0 ? (tree)->path[(tree)->pathlen-1] : NULL) 899 #define SCIPtreeGetCurrentDepth(tree) ((tree)->pathlen-1) 900 #define SCIPtreeHasCurrentNodeLP(tree) (SCIPtreeProbing(tree) ? (tree)->probingnodehaslp : SCIPtreeHasFocusNodeLP(tree)) 901 #define SCIPtreeGetEffectiveRootDepth(tree) ((tree)->effectiverootdepth) 902 #define SCIPtreeGetRootNode(tree) ((tree)->root) 903 #define SCIPtreeProbingObjChanged(tree) ((tree)->probingobjchanged) 904 #define SCIPtreeMarkProbingObjChanged(tree) ((tree)->probingobjchanged = TRUE) 905 906 #endif 907 908 909 /** gets the best child of the focus node w.r.t. the node selection priority assigned by the branching rule */ 910 SCIP_NODE* SCIPtreeGetPrioChild( 911 SCIP_TREE* tree /**< branch and bound tree */ 912 ); 913 914 /** gets the best sibling of the focus node w.r.t. the node selection priority assigned by the branching rule */ 915 SCIP_NODE* SCIPtreeGetPrioSibling( 916 SCIP_TREE* tree /**< branch and bound tree */ 917 ); 918 919 /** gets the best child of the focus node w.r.t. the node selection strategy */ 920 SCIP_NODE* SCIPtreeGetBestChild( 921 SCIP_TREE* tree, /**< branch and bound tree */ 922 SCIP_SET* set /**< global SCIP settings */ 923 ); 924 925 /** gets the best sibling of the focus node w.r.t. the node selection strategy */ 926 SCIP_NODE* SCIPtreeGetBestSibling( 927 SCIP_TREE* tree, /**< branch and bound tree */ 928 SCIP_SET* set /**< global SCIP settings */ 929 ); 930 931 /** gets the best leaf from the node queue w.r.t. the node selection strategy */ 932 SCIP_NODE* SCIPtreeGetBestLeaf( 933 SCIP_TREE* tree /**< branch and bound tree */ 934 ); 935 936 /** gets the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy */ 937 SCIP_NODE* SCIPtreeGetBestNode( 938 SCIP_TREE* tree, /**< branch and bound tree */ 939 SCIP_SET* set /**< global SCIP settings */ 940 ); 941 942 /** gets the minimal lower bound of all nodes in the tree */ 943 SCIP_Real SCIPtreeGetLowerbound( 944 SCIP_TREE* tree, /**< branch and bound tree */ 945 SCIP_SET* set /**< global SCIP settings */ 946 ); 947 948 /** gets the node with minimal lower bound of all nodes in the tree (child, sibling, or leaf) */ 949 SCIP_NODE* SCIPtreeGetLowerboundNode( 950 SCIP_TREE* tree, /**< branch and bound tree */ 951 SCIP_SET* set /**< global SCIP settings */ 952 ); 953 954 /** gets the average lower bound of all nodes in the tree */ 955 SCIP_Real SCIPtreeGetAvgLowerbound( 956 SCIP_TREE* tree, /**< branch and bound tree */ 957 SCIP_Real cutoffbound /**< global cutoff bound */ 958 ); 959 960 /** query if focus node was already branched on */ 961 SCIP_Bool SCIPtreeWasNodeLastBranchParent( 962 SCIP_TREE* tree, /**< branch and bound tree */ 963 SCIP_NODE* node /**< tree node, or NULL to check focus node */ 964 ); 965 966 #ifdef __cplusplus 967 } 968 #endif 969 970 #endif 971