This class contains the logic for branching on nodes in the B&B-Tree and selecting nodes to be processed.
More...
|
| Brancher (const std::vector< OptimizationVariable > &variables) |
| Constructor. More...
|
|
virtual | ~Brancher ()=default |
|
| Brancher (const Brancher &)=default |
|
Brancher & | operator= (Brancher &)=default |
|
| Brancher (Brancher &&)=default |
|
Brancher & | operator= (Brancher &&)=default |
|
void | set_branching_dimension_selection_strategy (const enums::BV branchingVarStratSelection) |
| Select a strategy for choosing a variable/dimension to branch on. Currently selecting the dimension with largest absolute or relative diameter is implemented. More...
|
|
void | set_node_selection_strategy (const enums::NS nodeSelectionStratType) |
| Select the node selection strategy. Default is to select the node with highest node selection score. More...
|
|
void | set_node_selection_score_function (std::function< double(const BabNode &, const std::vector< OptimizationVariable > &)> newNodeScoreFunction) |
| Change the scoring function for the selection score of nodes. More...
|
|
void | register_node_change (const int Id, const BabNode &nodeAfterProcessing) |
| Registers the changes made to a node during processing to extract information for branching heuristics. More...
|
|
void | insert_root_node (const BabNode &rootNode) |
| Inserts the root node into the tree. More...
|
|
std::pair< bool, bool > | branch_on_node (const BabNode &parentNode, const std::vector< double > &relaxationSolutionPoint, double relaxationSolutionObjValue, unsigned &incumbentNodeId, double relNodeSizeTol=0.0) |
| Function that branches on a node and (normally) adds two new children to the BranchAndBoundTree. More...
|
|
size_t | get_nodes_in_tree () const |
| Returns the number of nodes in the tree. More...
|
|
BabNode | get_next_node () |
| Returns the next BabNode to process according to the node selection strategy and node selection scores. More...
|
|
void | set_new_incumbent_point (std::vector< double > incumbentPoint) |
| Informs the instance that a new feasible solution has been found. Only needed because of hasIncumbent All nodes in the tree will get the hasIncumbent field set to false. More...
|
|
double | get_lowest_pruning_score () const |
| Returns the lowest pruning score of all nodes in the tree. More...
|
|
double | get_pruning_score_gap () const |
| Returns the difference between lowest pruning score in the tree and the pruning score threshold. More...
|
|
double | decrease_pruning_score_threshold_to (const double newThreshold) |
| Decreases the pruning score threshold to the supplied value. Nodes with pruning score exceeding the new threshold are fathomed. More...
|
|
double | get_pruning_score_threshold () const |
| Returns the pruning score threshold. More...
|
|
void | enable_pruning_with_rel_and_abs_tolerance (const double relTol, const double absTol) |
| Enables pruning of nodes even when they have pruning scores slightly below the threshold. More...
|
|
std::vector< BabNode > | get_all_nodes_from_strong_branching (const BabNode &parentNode, const std::vector< double > &relaxationSolutionPoint) |
| Branches once on all variables and does not add the nodes to the tree, but returns them immediately. More...
|
|
|
BabNodeWithInfo | _create_node_with_info_from_node (BabNode normalNode, unsigned branchedVariable, BranchingHistoryInfo::BranchStatus branchStatus, double variableRelaxationSolutionPoint, double parentLowerBound, double parentUpperBound) const |
| Creates a node with added information. More...
|
|
double | _calculate_branching_point (double lowerBound, double upperBound, double relaxationValue) const |
| calculates the branching point. Currently 0.5*(lb+ub); More...
|
|
std::pair< BabNodeWithInfo, BabNodeWithInfo > | _create_children (unsigned branchVar, const BabNode &parentNode, double branchVariableRelaxSolutionPoint) |
| Helper function for creating nodes from parent node once branch variable has been decided. More...
|
|
unsigned | _select_branching_dimension_pseudo_costs (const BabNode &parentNode, const std::vector< double > &relaxationSolutionPoint, const double relaxationSolutionObjValue, const std::vector< OptimizationVariable > &globalOptimizationVars) const |
| Function for selecting the variable to branch on by choosing the one with the largest pseudocost. More...
|
|
This class contains the logic for branching on nodes in the B&B-Tree and selecting nodes to be processed.
The Brancher class is meant to be used to manage the nodes of the branch and bound tree. Internally nodes are associated with two properties, their pruning score and their selection score. The pruning score usually represents the lower bound (minimization) and is used to exclude nodes from the tree. No nodes are kept in the tree with a pruning score exceeding pruning_score_threshold (and possibly also below pruning_score_threshold by no more than the relative and absolute tolerances). The selection score is used to decide the next node to be processed. With default settings, the node with the HIGHEST selection score is selected. How selection scores are calculated can be customized with set_node_selection_score_function. By default the node with the smallest pruning score has the highest selection score. For efficiency depth first search or breadth first search can be selected by using set_node_selection_strategy in which case selection scores are ignored.
The next node to process can be extracted by calling get_next_node(). After the node is processed, the user is expected to call register_node_change() with the processed node, which will allow collecting information for certain branching heuristics. To branch on a node, this node is passed to branch_on_node() which normaly will add two new children to the B&B-Tree. Currently, the branching decision is dependant on the current incumbent point. The brancher can be informed about a new incumbent point with set_new_incumbent_point(). The brancher also needs to be informed of new pruning score threshold which might represent upper bounds by calling decrease_pruning_score_threshold_to.
std::pair< bool, bool > Brancher::branch_on_node |
( |
const BabNode & |
parentNode, |
|
|
const std::vector< double > & |
relaxationSolutionPoint, |
|
|
double |
relaxationSolutionObjValue, |
|
|
unsigned & |
incumbentNodeId, |
|
|
double |
relNodeSizeTol = 0.0 |
|
) |
| |
Function that branches on a node and (normally) adds two new children to the BranchAndBoundTree.
It uses the branching strategy from _select_branching_dimension to decide which variable to branch on. relNodeSizeTol may be specified to not branch on nodes where all dimensions have a smaller size relative to the original bounds. In this case, if all optimization variables are integer, the node is added to the tree unchanged to be processed/ solved a final time, otherwise the node is discarded.
- Parameters
-
[in] | parentNode | Node to be branched on. Pruning Score is forwarded to children nodes. |
[in] | relaxationSolutionPoint | The solution point of the relaxed problem for the parent node. |
[in] | relaxationSolutionObjValue | The objective function vaule corresponding to relaxationSolutionPoint. |
[out] | incumbentNodeId | If one of the created child nodes contains the incumbent, its ID will be returned here. |
[in] | relNodeSizeTol | The relative tolerance for bound differences (relative to the original bounds). |
- Returns
- pair<isFixed, canBeConsideredFixed> isFixed is true if all variables are fixed which should only happen for pure integer problems. In this case parentNode is simply added to the tree. canBeConsideredFixed is true if all variables are fixed up to the relNodeSizeTol. In this case parentNode is discarded.
- Postcondition
- Either both returned bools (isFixed and canBeConsideredFixed) are false, or two new nodes are added to the tree with the same pruning score as parentNode.
-
If the parentNode had hasIncumbent set to true, this field is also set to true for the child node which still has the incumbent inside his bounds.