![]() |
MAiNGO
|
Represents the B&B-Tree, manages the way nodes are saved and retrieved and pruned. More...
#include <babTree.h>
Public Member Functions | |
BabTree () | |
Default constructor for BabTree, threshold set to INF. More... | |
virtual | ~BabTree ()=default |
BabTree (const BabTree &)=default | |
BabTree & | operator= (BabTree &)=default |
BabTree (BabTree &&)=default | |
BabTree & | operator= (BabTree &&)=default |
size_t | get_nodes_left () const |
Returns the number of nodes left in the tree. The private member _nodesLeft is used instead of nodeVector.size() so that places which change the number of nodes in the tree are easier to search in case this needs to be logged at a later date. More... | |
unsigned | get_valid_id () |
Returns a valid Id for the next node. More... | |
void | add_node (BabNodeWithInfo node) |
Add node to the list of nodes to process. More... | |
BabNodeWithInfo | pop_next_node () |
Return the node according to the node selection strategy and removes it from the tree. More... | |
double | get_lowest_pruning_score () const |
Return the lowest pruning score. Returns infinity if tree is empty. More... | |
double | get_pruning_score_gap () const |
Query the largest gap between the pruning threshold and the the pruning scores of the nodes. Returns -infinity if tree is empty. _pruningScoreThreshold-lowest pruning score of all nodes left in the tree. If pruningScore = nodeSelectionScore, this could be done much more efficently. More... | |
double | set_pruning_score_threshold (const double newThreshold) |
Update the pruning score threshold, e.g. after a new incumbent has been found, also fathom now fathomable nodes in tree. More... | |
void | remove_has_incumbent_from_all_nodes () |
Remove the hasIncumbent flag from all nodes. More... | |
double | get_pruning_score_threshold () const |
Query the 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... | |
void | set_node_selection_strategy (enums::NS nodeSelectionStrategyType) |
Allows to set the node selection strategy. Default is to return the node with largest node selection score. More... | |
Private Member Functions | |
void | delete_element (std::vector< BabNodeWithInfo >::iterator targetNodeIt) |
Removes a node from the tree. More... | |
double | _fathom_nodes_exceeding_pruning_threshold (const double newThreshold, const double relTol, const double absTol) |
Removes all nodes from the tree having a pruning score greater than (or within the tolerances of) pruning threshold. More... | |
Private Attributes | |
double | _pruningScoreThreshold |
double | _relPruningTol = 0.0 |
double | _absPruningTol = 0.0 |
size_t | _nodesLeft |
unsigned | _Id |
std::function< std::vector< BabNodeWithInfo >::const_iterator(const std::vector< BabNodeWithInfo > &nodeVectorIN)> | _select_node |
std::vector< BabNodeWithInfo > | _nodeVector |
Represents the B&B-Tree, manages the way nodes are saved and retrieved and pruned.
The BabTree class is meant to be used to abstract the storage and node selection implementation. It makes sure that nodes are returned according to the node selection strategy. The default returns the node with the highest node selection score. Another invariant is that nodes whose pruning score exceeds the set pruning score threshold are never keept inside the tree. A added node that violates that invariant is immediately discarded and nodes already in the tree will be deleted when the pruning score threshold is lowered below there pruning score. The BabTree class is also in charge of giving out valid IDs as to keep them unique. IDs of Nodes added to the tree should therefore be retrieved from the tree.
BabTree::BabTree | ( | ) |
Default constructor for BabTree, threshold set to INF.
|
virtualdefault |
|
default |
Default copy constructor
|
default |
Default r-value constructor
|
private |
Removes all nodes from the tree having a pruning score greater than (or within the tolerances of) pruning threshold.
[in] | newThreshold | the new threshold to enforce |
[in] | relTol | Relative tolerance to the new threshold. Describes by which fraction pruning score can be lower than the new threshold and still lead to fathoming |
[in] | absTol | Absolute value by which pruning score can be lower than the new threshold and still lead to fathoming |
void BabTree::add_node | ( | BabNodeWithInfo | node | ) |
Add node to the list of nodes to process.
|
private |
Removes a node from the tree.
|
inline |
Enables pruning of nodes even when they have pruning scores slightly below the threshold.
Takes only effect at next call to set_pruning_score_threshold or when nodes are added
[in] | relTol | relativeTolerance |
[in] | absTol | absoluteTolerance (relative to pruningScoreThreshold) |
double BabTree::get_lowest_pruning_score | ( | ) | const |
Return the lowest pruning score. Returns infinity if tree is empty.
|
inline |
Returns the number of nodes left in the tree. The private member _nodesLeft is used instead of nodeVector.size() so that places which change the number of nodes in the tree are easier to search in case this needs to be logged at a later date.
double BabTree::get_pruning_score_gap | ( | ) | const |
Query the largest gap between the pruning threshold and the the pruning scores of the nodes. Returns -infinity if tree is empty. _pruningScoreThreshold-lowest pruning score of all nodes left in the tree. If pruningScore = nodeSelectionScore, this could be done much more efficently.
|
inline |
Query the the pruning score threshold.
|
inline |
Returns a valid Id for the next node.
BabNodeWithInfo BabTree::pop_next_node | ( | ) |
Return the node according to the node selection strategy and removes it from the tree.
|
inline |
Remove the hasIncumbent flag from all nodes.
void BabTree::set_node_selection_strategy | ( | enums::NS | nodeSelectionStrategyType | ) |
Allows to set the node selection strategy. Default is to return the node with largest node selection score.
This should be used to set other strategies when the goal is to change the strategy during the algorithm. For a permanent strategy, it is much more efficient to give the nodes a corresponding node selection priority.
double BabTree::set_pruning_score_threshold | ( | const double | newThreshold | ) |
Update the pruning score threshold, e.g. after a new incumbent has been found, also fathom now fathomable nodes in tree.
|
private |
Absolute tolerance applied to the pruning process, nodes with pruning score > PT - _absPruningTol will be also pruned.
|
private |
Node id
|
private |
Number of nodes left in the tree
|
private |
Internal storage of the nodes, currently maintained as a heap of node selection score. The node with the highest nodeSelectionScore will be ensured to be at front of _nodeVector
|
private |
Represents the lowest known upper bound. Every node with a pruning score above this treshold will be pruned.
|
private |
Relative tolerance applied to the pruning process, nodes with pruning score > PT - |PT|* _relativePruningTol will be also pruned (PT= _pruningScoreThreshhold).
|
private |
Saved function that is used to select the next node to process.