MAiNGO
babBase::Brancher Class Reference

This class contains the logic for branching on nodes in the B&B-Tree and selecting nodes to be processed. More...

#include <babBrancher.h>

Public Member Functions

 Brancher (const std::vector< OptimizationVariable > &variables)
 Constructor. More...
 
virtual ~Brancher ()=default
 
 Brancher (const Brancher &)=default
 
Brancheroperator= (Brancher &)=default
 
 Brancher (Brancher &&)=default
 
Brancheroperator= (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< BabNodeget_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...
 

Private Member Functions

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...
 

Private Attributes

std::function< double(const BabNode &, const std::vector< OptimizationVariable > &)> _node_score_calculating_function
 
std::function< unsigned(const BabNode &parentNode, const std::vector< double > &relaxationSolutionPoint, double relaxationSolutionObjValue, const std::vector< OptimizationVariable > &globalOptimizationVars)> _select_branching_dimension
 
BabTree _internalBranchAndBoundTree
 
std::vector< OptimizationVariable_globalOptimizationVariables
 
std::vector< double > _pseudocosts_up
 
std::vector< double > _pseudocosts_down
 
std::vector< int > _number_of_trials_up
 
std::vector< int > _number_of_trials_down
 
std::vector< std::tuple< unsigned, double, BranchingHistoryInfo > > _nodesWaitingForResponse
 
std::vector< double > _incumbentSolutionPoint
 

Detailed Description

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.

Constructor & Destructor Documentation

◆ Brancher() [1/3]

Brancher::Brancher ( const std::vector< OptimizationVariable > &  variables)

Constructor.

◆ ~Brancher()

virtual babBase::Brancher::~Brancher ( )
virtualdefault

◆ Brancher() [2/3]

babBase::Brancher::Brancher ( const Brancher )
default

Default copy constructor

◆ Brancher() [3/3]

babBase::Brancher::Brancher ( Brancher &&  )
default

Default r-value copy

Member Function Documentation

◆ _calculate_branching_point()

double Brancher::_calculate_branching_point ( double  lowerBound,
double  upperBound,
double  relaxationValue 
) const
private

calculates the branching point. Currently 0.5*(lb+ub);

◆ _create_children()

std::pair< BabNodeWithInfo, BabNodeWithInfo > Brancher::_create_children ( unsigned  branchVar,
const BabNode parentNode,
double  branchVariableRelaxSolutionPoint 
)
private

Helper function for creating nodes from parent node once branch variable has been decided.

◆ _create_node_with_info_from_node()

BabNodeWithInfo Brancher::_create_node_with_info_from_node ( BabNode  normalNode,
unsigned  branchedVariable,
BranchingHistoryInfo::BranchStatus  branchStatus,
double  variableRelaxationSolutionPoint,
double  parentLowerBound,
double  parentUpperBound 
) const
private

Creates a node with added information.

   Added information is the node selection score, the variable last branched on  and if it was branched up or down.
   Additionally, what the value of this variable was at the relaxation solution and what bounds the parent node had on that variable.
   The node selection score is calculated immediately.
   @returns A BabNodeWithInfo with all fields from BabNode copied.

◆ _select_branching_dimension_pseudo_costs()

unsigned Brancher::_select_branching_dimension_pseudo_costs ( const BabNode parentNode,
const std::vector< double > &  relaxationSolutionPoint,
const double  relaxationSolutionObjValue,
const std::vector< OptimizationVariable > &  globalOptimizationVars 
) const
private

Function for selecting the variable to branch on by choosing the one with the largest pseudocost.

Parameters
[in]parentNodeis the node thas should be branched on.
[in]relaxationSolutionPointis the vector of the solution point for the relaxed problem in the parentNode node
[in]relaxationSolutionObjValueis the objective function value corresponding to relaxationSolutionPoint
[in]globalOptimizationVarsis the vector of original optimization variables
Returns
branchVar is the index of the variable to branch on

◆ branch_on_node()

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]parentNodeNode to be branched on. Pruning Score is forwarded to children nodes.
[in]relaxationSolutionPointThe solution point of the relaxed problem for the parent node.
[in]relaxationSolutionObjValueThe objective function vaule corresponding to relaxationSolutionPoint.
[out]incumbentNodeIdIf one of the created child nodes contains the incumbent, its ID will be returned here.
[in]relNodeSizeTolThe 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.

◆ decrease_pruning_score_threshold_to()

double Brancher::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.

Returns
the lowest pruning score that lead to fathoming

◆ enable_pruning_with_rel_and_abs_tolerance()

void babBase::Brancher::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.

Parameters
[in]relTolrelativeTolerance
[in]absTolabsoluteTolerance (relative to pruningScoreThreshold)

◆ get_all_nodes_from_strong_branching()

std::vector< BabNode > Brancher::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.

◆ get_lowest_pruning_score()

double babBase::Brancher::get_lowest_pruning_score ( ) const
inline

Returns the lowest pruning score of all nodes in the tree.

◆ get_next_node()

BabNode Brancher::get_next_node ( )

Returns the next BabNode to process according to the node selection strategy and node selection scores.

Precondition
Tree is not empty. Can be checked with get_nodes_in_tree()>0
Exceptions
ABranchAndBoundBaseException if the precondition is not fullfilled.

◆ get_nodes_in_tree()

size_t babBase::Brancher::get_nodes_in_tree ( ) const
inline

Returns the number of nodes in the tree.

◆ get_pruning_score_gap()

double babBase::Brancher::get_pruning_score_gap ( ) const
inline

Returns the difference between lowest pruning score in the tree and the pruning score threshold.

◆ get_pruning_score_threshold()

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

Returns the pruning score threshold.

Returns
pruning_score_threshold No nodes with pruning score exceeding this value will be keept in the tree. Often represents lowest known upper bound.

◆ insert_root_node()

void Brancher::insert_root_node ( const BabNode rootNode)

Inserts the root node into the tree.

Parameters
rootNodeNode to be placed at the root. IDs are handled by BabTree and thus the ID member of rootNode will be replaced.
Precondition
The tree is empty. Can be checked by get_nodes_in_tree()==0.

◆ operator=() [1/2]

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

Default assignment

◆ operator=() [2/2]

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

Default r-value assignment

◆ register_node_change()

void Brancher::register_node_change ( const int  Id,
const BabNode nodeAfterProcessing 
)

Registers the changes made to a node during processing to extract information for branching heuristics.

Internally keeps track of all nodes given out for processing for which no change has been registered. This enables nodes to be processed in parallel or out of order. If the Id is invalid (not found in the list of nodes given out for processing), an BranchAndBoundBaseExeception will be thrown. If the Id is found on the list, it will be removed from that list after the function call.

Parameters
Idis the ID of the node that was received with get_next_node()
nodeAfterProcessingis the node after processing. The ID member of this node is ignored.
Exceptions
ABranchAndBoundBaseExeception if passed Id is invalid

◆ set_branching_dimension_selection_strategy()

void Brancher::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.

◆ set_new_incumbent_point()

void babBase::Brancher::set_new_incumbent_point ( std::vector< double >  incumbentPoint)
inline

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.

◆ set_node_selection_score_function()

void Brancher::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.

Currently only new nodes are scored with the new scoring function, meaning that this function is not suitable to change between different node selection strategies (e.g. lowest-pruning score to depth-first) during the search. For this us set_node_selection_strategy.

Parameters
newNodeScoreFunctionFunctor or function pointer or reference to function describing how selection scores should be calculated

◆ set_node_selection_strategy()

void Brancher::set_node_selection_strategy ( const enums::NS  nodeSelectionStratType)

Select the node selection strategy. Default is to select the node with highest node selection score.

It is easier but less efficient to select the other two provided options depth-first and breadth first via this function instead of selecting a different node selection score function with set_node_selection_score_function. However, this function may also be called during the search.

Member Data Documentation

◆ _globalOptimizationVariables

std::vector<OptimizationVariable> babBase::Brancher::_globalOptimizationVariables
private

Saves the global/original bounds and types of variables and their global branching score components

◆ _incumbentSolutionPoint

std::vector<double> babBase::Brancher::_incumbentSolutionPoint
private

Solution vector for the best found incumbent.

◆ _internalBranchAndBoundTree

BabTree babBase::Brancher::_internalBranchAndBoundTree
private

BranchAndBoundTree managing the nodes and their sorting.

◆ _node_score_calculating_function

std::function<double(const BabNode&, const std::vector<OptimizationVariable>&)> babBase::Brancher::_node_score_calculating_function
private

Saved function to calculate the node selection score of a node

◆ _nodesWaitingForResponse

std::vector<std::tuple<unsigned , double , BranchingHistoryInfo> > babBase::Brancher::_nodesWaitingForResponse
private

A list of all nodes that were given out and no change on them was yet registered, saves the variable that was branched on and if it was up or down.

◆ _number_of_trials_down

std::vector<int> babBase::Brancher::_number_of_trials_down
private

The number of times the pseudo cost for branching down has been updated. Used to incrementally calculate the average

◆ _number_of_trials_up

std::vector<int> babBase::Brancher::_number_of_trials_up
private

The number of times the pseudo cost for branching up has been updated. Used to incrementally calculate the average

◆ _pseudocosts_down

std::vector<double> babBase::Brancher::_pseudocosts_down
private

The pseudocosts for branching down on each of the variables

◆ _pseudocosts_up

std::vector<double> babBase::Brancher::_pseudocosts_up
private

The pseudocosts for branching up on each of the variables

◆ _select_branching_dimension

std::function<unsigned(const BabNode& parentNode, const std::vector<double>& relaxationSolutionPoint, double relaxationSolutionObjValue, const std::vector<OptimizationVariable>& globalOptimizationVars)> babBase::Brancher::_select_branching_dimension
private

Function for selecting the branching variable


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