MAiNGO
babBase::BabTree Class Reference

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
 
BabTreeoperator= (BabTree &)=default
 
 BabTree (BabTree &&)=default
 
BabTreeoperator= (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
 

Detailed Description

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.

Constructor & Destructor Documentation

◆ BabTree() [1/3]

BabTree::BabTree ( )

Default constructor for BabTree, threshold set to INF.

◆ ~BabTree()

virtual babBase::BabTree::~BabTree ( )
virtualdefault

◆ BabTree() [2/3]

babBase::BabTree::BabTree ( const BabTree )
default

Default copy constructor

◆ BabTree() [3/3]

babBase::BabTree::BabTree ( BabTree &&  )
default

Default r-value constructor

Member Function Documentation

◆ _fathom_nodes_exceeding_pruning_threshold()

double BabTree::_fathom_nodes_exceeding_pruning_threshold ( const double  newThreshold,
const double  relTol,
const double  absTol 
)
private

Removes all nodes from the tree having a pruning score greater than (or within the tolerances of) pruning threshold.

Parameters
[in]newThresholdthe new threshold to enforce
[in]relTolRelative tolerance to the new threshold. Describes by which fraction pruning score can be lower than the new threshold and still lead to fathoming
[in]absTolAbsolute value by which pruning score can be lower than the new threshold and still lead to fathoming
Returns
return the lowest pruning score that still lead to fathoming

◆ add_node()

void BabTree::add_node ( BabNodeWithInfo  node)

Add node to the list of nodes to process.

◆ delete_element()

void BabTree::delete_element ( std::vector< BabNodeWithInfo >::iterator  targetNodeIt)
private

Removes a node from the tree.

◆ enable_pruning_with_rel_and_abs_tolerance()

void babBase::BabTree::enable_pruning_with_rel_and_abs_tolerance ( const double  relTol,
const double  absTol 
)
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
Parameters
[in]relTolrelativeTolerance
[in]absTolabsoluteTolerance (relative to pruningScoreThreshold)

◆ get_lowest_pruning_score()

double BabTree::get_lowest_pruning_score ( ) const

Return the lowest pruning score. Returns infinity if tree is empty.

◆ get_nodes_left()

size_t babBase::BabTree::get_nodes_left ( ) const
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.

◆ get_pruning_score_gap()

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.

◆ get_pruning_score_threshold()

double babBase::BabTree::get_pruning_score_threshold ( ) const
inline

Query the the pruning score threshold.

◆ get_valid_id()

unsigned babBase::BabTree::get_valid_id ( )
inline

Returns a valid Id for the next node.

Returns
Returns an Id different from all previous returned.
Note
Not ready for parallel use

◆ operator=() [1/2]

BabTree& babBase::BabTree::operator= ( BabTree )
default

Default assignment

◆ operator=() [2/2]

BabTree& babBase::BabTree::operator= ( BabTree &&  )
default

Default r-value assignment

◆ pop_next_node()

BabNodeWithInfo BabTree::pop_next_node ( )

Return the node according to the node selection strategy and removes it from the tree.

Precondition
Tree is not empty. Can be checked by get_nodes_left()!=0.
Note
No check of the precondition is guaranteed. Violating it results in undefined behavior.

◆ remove_has_incumbent_from_all_nodes()

void babBase::BabTree::remove_has_incumbent_from_all_nodes ( )
inline

Remove the hasIncumbent flag from all nodes.

Note
Not called automatically when updating pruning score, since that would only be correct if pruning score threshold equals upperbound

◆ set_node_selection_strategy()

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.

◆ set_pruning_score_threshold()

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.

Returns
The lowest pruning score of all pruned nodes

Member Data Documentation

◆ _absPruningTol

double babBase::BabTree::_absPruningTol = 0.0
private

Absolute tolerance applied to the pruning process, nodes with pruning score > PT - _absPruningTol will be also pruned.

◆ _Id

unsigned babBase::BabTree::_Id
private

Node id

◆ _nodesLeft

size_t babBase::BabTree::_nodesLeft
private

Number of nodes left in the tree

◆ _nodeVector

std::vector<BabNodeWithInfo> babBase::BabTree::_nodeVector
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

◆ _pruningScoreThreshold

double babBase::BabTree::_pruningScoreThreshold
private

Represents the lowest known upper bound. Every node with a pruning score above this treshold will be pruned.

◆ _relPruningTol

double babBase::BabTree::_relPruningTol = 0.0
private

Relative tolerance applied to the pruning process, nodes with pruning score > PT - |PT|* _relativePruningTol will be also pruned (PT= _pruningScoreThreshhold).

◆ _select_node

std::function<std::vector<BabNodeWithInfo>::const_iterator(const std::vector<BabNodeWithInfo>& nodeVectorIN)> babBase::BabTree::_select_node
private

Saved function that is used to select the next node to process.


The documentation for this class was generated from the following files: