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