scip_tree.c
Go to the documentation of this file.
43 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
62 * if we are in probing/diving mode this method returns the node in the tree where the probing/diving mode was started.
76 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetFocusNode", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
95 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetCurrentNode", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
114 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetRootNode", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
119 /** gets the effective root depth, i.e., the depth of the deepest node which is part of all paths from the root node
131 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetEffectiveRootDepth", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
150 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPinRepropagation", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
157 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
170 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetChildren", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
192 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNChildren", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
199 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
212 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetSiblings", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
234 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNSiblings", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
241 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
254 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetLeaves", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
276 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNLeaves", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
281 /** gets the best child of the focus node w.r.t. the node selection priority assigned by the branching rule
283 * @return the best child of the focus node w.r.t. the node selection priority assigned by the branching rule
292 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetPrioChild", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
297 /** gets the best sibling of the focus node w.r.t. the node selection priority assigned by the branching rule
299 * @return the best sibling of the focus node w.r.t. the node selection priority assigned by the branching rule
308 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetPrioSibling", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
324 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBestChild", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
340 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBestSibling", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
356 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBestLeaf", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
361 /** gets the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy
363 * @return the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy
372 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBestNode", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
388 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBestboundNode", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
408 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetOpenNodesData", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
428 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
439 SCIP_CALL( SCIPcheckStage(scip, "SCIPcutoffNode", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
441 SCIP_CALL( SCIPnodeCutoff(node, scip->set, scip->stat, scip->tree, scip->transprob, scip->origprob, scip->reopt,
447 /** removes all nodes from branch and bound tree that were marked to be cut off via SCIPcutoffNode()
449 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
461 SCIP_CALL( SCIPcheckStage(scip, "SCIPpruneTree", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
463 SCIP_CALL( SCIPtreeCutoff(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter,
469 /** marks the given node to be propagated again the next time a node of its subtree is processed
471 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
482 SCIP_CALL( SCIPcheckStage(scip, "SCIPrepropagateNode", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
500 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetCutoffdepth", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
516 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetRepropdepth", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
523 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
535 SCIP_VAR** branchvars; /* array of variables on which the branchings has been performed in all ancestors */
538 int* nodeswitches; /* marks, where in the arrays the branching decisions of the next node on the path start
539 * branchings performed at the parent of node always start at position 0. For single variable branching,
541 int nbranchvars; /* number of variables on which branchings have been performed in all ancestors
542 * if this is larger than the array size, arrays should be reallocated and method should be called again */
556 SCIPnodeGetAncestorBranchingPath(node, branchvars, branchbounds, boundtypes, &nbranchvars, branchvarssize, nodeswitches, &nnodes, nodeswitchsize );
558 /* if the arrays were to small, we have to reallocate them and recall SCIPnodeGetAncestorBranchingPath */
570 SCIPnodeGetAncestorBranchingPath(node, branchvars, branchbounds, boundtypes, &nbranchvars, branchvarssize, nodeswitches, &nnodes, nodeswitchsize);
593 SCIPmessageFPrintInfo(scip->messagehdlr, file, "<%s> %s %.1f",SCIPvarGetName(branchvars[i]), boundtypes[i] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", branchbounds[i]);
619 * @note In order to have an effect, this method needs to be called after a node is focused but before the LP is
630 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPsetFocusnodeLP", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
648 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNNodesLeft", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
653 /** gets depth of current node, or -1 if no current node exists; in probing, the current node is the last probing node,
656 * @return the depth of current node, or -1 if no current node exists; in probing, the current node is the last probing node,
674 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetDepth", FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE) );
679 /** gets depth of the focus node, or -1 if no focus node exists; the focus node is the currently processed node in the
682 * @return the depth of the focus node, or -1 if no focus node exists; the focus node is the currently processed node in the
700 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetFocusDepth", FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE) );
717 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetPlungeDepth", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
736 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPwasNodeLastBranchParent", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
public methods for branch and bound tree
internal methods for branch and bound tree
Definition: struct_scip.h:68
void SCIPtreeSetFocusNodeLP(SCIP_TREE *tree, SCIP_Bool solvelp)
Definition: tree.c:8355
public methods for memory management
SCIP_NODE * SCIPtreeGetLowerboundNode(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7294
SCIP_RETCODE SCIPgetLeaves(SCIP *scip, SCIP_NODE ***leaves, int *nleaves)
Definition: scip_tree.c:248
Definition: struct_var.h:207
SCIP_NODE * SCIPtreeGetBestNode(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7222
SCIP_RETCODE SCIPgetOpenNodesData(SCIP *scip, SCIP_NODE ***leaves, SCIP_NODE ***children, SCIP_NODE ***siblings, int *nleaves, int *nchildren, int *nsiblings)
Definition: scip_tree.c:398
SCIP_NODE * SCIPtreeGetBestChild(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7158
SCIP_Bool SCIPwasNodeLastBranchParent(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:731
public methods for problem variables
Definition: struct_tree.h:141
SCIP_RETCODE SCIPgetSiblings(SCIP *scip, SCIP_NODE ***siblings, int *nsiblings)
Definition: scip_tree.c:206
SCIP_RETCODE SCIPrepropagateNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:477
public methods for numerical tolerances
public methods for the branch-and-bound tree
SCIP_RETCODE SCIPnodeCutoff(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_REOPT *reopt, SCIP_LP *lp, BMS_BLKMEM *blkmem)
Definition: tree.c:1188
void SCIPnodeGetAncestorBranchingPath(SCIP_NODE *node, SCIP_VAR **branchvars, SCIP_Real *branchbounds, SCIP_BOUNDTYPE *boundtypes, int *nbranchvars, int branchvarssize, int *nodeswitches, int *nnodes, int nodeswitchsize)
Definition: tree.c:8094
SCIP_Bool SCIPtreeWasNodeLastBranchParent(SCIP_TREE *tree, SCIP_NODE *node)
Definition: tree.c:1042
SCIP_RETCODE SCIPgetChildren(SCIP *scip, SCIP_NODE ***children, int *nchildren)
Definition: scip_tree.c:164
Definition: type_lp.h:56
SCIP_RETCODE SCIPcheckStage(SCIP *scip, const char *method, SCIP_Bool init, SCIP_Bool problem, SCIP_Bool transforming, SCIP_Bool transformed, SCIP_Bool initpresolve, SCIP_Bool presolving, SCIP_Bool exitpresolve, SCIP_Bool presolved, SCIP_Bool initsolve, SCIP_Bool solving, SCIP_Bool solved, SCIP_Bool exitsolve, SCIP_Bool freetrans, SCIP_Bool freescip)
Definition: debug.c:2186
SCIP_NODE * SCIPtreeGetBestSibling(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7185
data structures for branch and bound tree
internal methods for node selectors and node priority queues
Definition: type_retcode.h:42
SCIP main data structure.
void SCIPnodePropagateAgain(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree)
Definition: tree.c:1248
int SCIPtreeGetEffectiveRootDepth(SCIP_TREE *tree)
Definition: tree.c:8442
methods for debugging
datastructures for block memory pools and memory buffers
datastructures for problem statistics
SCIP_RETCODE SCIPprintNodeRootPath(SCIP *scip, SCIP_NODE *node, FILE *file)
Definition: scip_tree.c:529
public methods for message output
void SCIPmessageFPrintInfo(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char *formatstr,...)
Definition: message.c:618
Definition: objbenders.h:43
SCIP_RETCODE SCIPtreeCutoff(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp, SCIP_Real cutoffbound)
Definition: tree.c:5135
memory allocation routines