SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
|
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
tree.h
Go to the documentation of this file.
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
64 SCIP_Real estimate /**< estimate for (transformed) objective value of best feasible solution in subtree */
125 /** marks node, that propagation should be applied again the next time, a node of its subtree is focused */
141 /** adds constraint locally to the node and captures it; activates constraint, if node is active;
142 * if a local constraint is added to the root node, it is automatically upgraded into a global constraint
154 /** locally deletes constraint at the given node by disabling its separation, enforcing, and propagation capabilities
167 /** adds bound change with inference information to focus node, child of focus node, or probing node;
250 /** if given value is larger than the node's lower bound, sets the node's lower bound to the new value */
291 /** propagates implications of binary fixings at the given node triggered by the implication graph and the clique table */
397 /** sets the node selector used for sorting the nodes in the priority queue, and resorts the queue if necessary */
416 SCIP_Real cutoffbound /**< cutoff bound: all nodes with lowerbound >= cutoffbound are cut off */
428 SCIP_Bool* initroot /**< pointer to store whether the root LP relaxation has to be initialized */
442 /** calculates the node selection priority for moving the given variable's LP value to the given target value;
451 SCIP_BRANCHDIR branchdir, /**< type of branching that was performed: upwards, downwards, or fixed
457 /** calculates an estimate for the objective of the best feasible solution contained in the subtree after applying the given
473 * the variable is fixed to val (if not SCIP_INVALID) or a well chosen alternative in the current node,
483 * if solution value is equal to one of the bounds and the other bound is infinite, only two child nodes
498 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 */
499 SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
504 /** branches a variable x using the given domain hole; two child nodes will be created (x <= left, x >= right) */
519 SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
524 * Branches on variable x such that up to n/2 children are created on each side of the usual branching value.
526 * If n is 2 or the variables local domain is too small for a branching into n pieces, SCIPtreeBranchVar() is called.
527 * The parameters minwidth and widthfactor determine the domain width of the branching variable in the child nodes.
528 * If n is odd, one child with domain width 'width' and having the branching value in the middle is created.
529 * Otherwise, two children with domain width 'width' and being left and right of the branching value are created.
530 * Next further nodes to the left and right are created, where width is multiplied by widthfactor with increasing distance from the first nodes.
531 * The initial width is calculated such that n/2 nodes are created to the left and to the right of the branching value.
532 * If this value is below minwidth, the initial width is set to minwidth, which may result in creating less than n nodes.
534 * Giving a large value for widthfactor results in creating children with small domain when close to the branching value
535 * and large domain when closer to the current variable bounds. That is, setting widthfactor to a very large value and n to 3
536 * results in a ternary branching where the branching variable is mostly fixed in the middle child.
537 * Setting widthfactor to 1.0 results in children where the branching variable always has the same domain width
552 SCIP_Real val, /**< value to branch on or SCIP_INVALID for branching on current LP/pseudo solution.
556 SCIP_Real widthfactor, /**< multiplier for children domain width with increasing distance from val, must be >= 1.0 */
598 * the changes of the probing node of the given probing depth are the last ones that remain active;
613 int probingdepth /**< probing depth of the node in the probing path that should be reactivated */
616 /** switches back from probing to normal operation mode, frees all nodes on the probing path, restores bounds of all
677 /** returns the current probing depth, i.e. the number of probing sub nodes existing in the probing path */
720 /** gets current node of the tree, i.e. the last node in the active path, or NULL if no current node exists */
726 /** 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 */
738 /** returns the depth of the effective root node (i.e. the first depth level of a node with at least two children) */
752 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
761 #define SCIPtreeIsPathComplete(tree) ((tree)->focusnode == NULL || (tree)->focusnode->depth < (tree)->pathlen)
764 #define SCIPtreeGetProbingDepth(tree) (SCIPtreeGetCurrentDepth(tree) - SCIPnodeGetDepth((tree)->probingroot))
772 #define SCIPtreeGetCurrentNode(tree) ((tree)->pathlen > 0 ? (tree)->path[(tree)->pathlen-1] : NULL)
774 #define SCIPtreeHasCurrentNodeLP(tree) (SCIPtreeProbing(tree) ? (tree)->probingnodehaslp : SCIPtreeHasFocusNodeLP(tree))
781 /** gets the best child of the focus node w.r.t. the node selection priority assigned by the branching rule */
787 /** gets the best sibling of the focus node w.r.t. the node selection priority assigned by the branching rule */
813 /** gets the best node from the tree (child, sibling, or leaf) w.r.t. the node selection strategy */
|
