MAiNGO
babBase Namespace Reference

namespace holding all essentials of the babBase submodule More...

Namespaces

 enums
 namespace holding all enums used for branching and B&B reporting
 

Classes

struct  BabLog
 Struct storing logging information during B&B prodcedure. More...
 
class  BabNode
 Class representing a node in the Branch-and-Bound tree. More...
 
class  BabNodeWithInfo
 This class represents an node in the B&B-Tree with additional information attached that is used in selecting nodes or branching variables. More...
 
class  BabTree
 Represents the B&B-Tree, manages the way nodes are saved and retrieved and pruned. More...
 
struct  Bounds
 Auxiliary struct for representing bounds on an optimization variable. More...
 
class  BranchAndBoundBaseException
 This class defines the exceptions thrown by BranchAndBoundBase. More...
 
class  Brancher
 This class contains the logic for branching on nodes in the B&B-Tree and selecting nodes to be processed. More...
 
struct  BranchingHistoryInfo
 Struct for collecting all information that must be saved about a node, so that after it is retrieved from the tree and processed, pseudocosts can be calculated. More...
 
struct  NodePriorityComparator
 Functor for comparing node priorities. More...
 
class  OptimizationVariable
 Class for representing an optimization variable specified by the user. More...
 
class  OutVar
 Helper class that can be used to enforce the caller to explicitly state that the variable he passed may be changed. More...
 
struct  PruningScoreComparator
 Functor for comparing pruning scores. More...
 

Functions

unsigned select_branching_dimension_absdiam (const BabNode &parentNode, const std::vector< double > &relaxationSolutionPoint, const double relaxationSolutionObjValue, const std::vector< OptimizationVariable > &globalOptimizationVars)
 Function for selecting the variable to branch on by choosing the one with the largest diameter. More...
 
unsigned select_branching_dimension_reldiam (const BabNode &parentNode, const std::vector< double > &relaxationSolutionPoint, const double relaxationSolutionObjValue, const std::vector< OptimizationVariable > &globalOptimizationVars)
 Function for selecting the variable to branch on by choosing the one with the largest diameter relative to the original one. More...
 
double relative_distance_to_closest_bound (double pointValue, double bound1, double bound2, const babBase::OptimizationVariable &variable)
 Helper function for tiebracking in branching (akin to most fractional although this is only as good as random) More...
 
double low_pruning_score_first (const BabNode &candidate, const std::vector< OptimizationVariable > &globalVars)
 Function for BFS or lowPruning Score First (default), possible choice for calculating the node selection score. More...
 
double low_id_first (const BabNode &candidate, const std::vector< OptimizationVariable > &globalVars)
 Function for Breadth-First-Search possible choice for calculating the node selection score. More...
 
double high_id_first (const BabNode &candidate, const std::vector< OptimizationVariable > &globalVars)
 Function for DFS, possible choice for calculating the node selection score. More...
 
std::pair< double, double > calculate_pseudocost_multipliers_minus_and_plus (enums::VT varType, double lowerBound, double upperBound, double branchingPoint, double relaxationSolutionPoint)
 Calculate the multiplier for calculation of pseudocosts. More...
 
std::ostream & operator<< (std::ostream &out, const BabNode &node)
 operator << overloaded for BabNode for easier output More...
 
std::vector< BabNodeWithInfo >::const_iterator select_node_highest_priority (const std::vector< BabNodeWithInfo > &nodeVectorIN)
 Returns the node with the highest priority. More...
 
std::vector< BabNodeWithInfo >::const_iterator select_node_breadthfirst (const std::vector< BabNodeWithInfo > &nodeVectorIN)
 Returns the node added least recently to the tree. More...
 
std::vector< BabNodeWithInfo >::const_iterator select_node_depthfirst (const std::vector< BabNodeWithInfo > &nodeVectorIN)
 Returns the node added most recently to the tree. More...
 
template<class T >
std::enable_if<!std::numeric_limits< T >::is_integer, bool >::type almost_equal (T x, T y, int ulp=2)
 compares if two floating numbers are very close to each other from:https://en.cppreference.com/w/cpp/types/numeric_limits/epsilon More...
 
bool larger_or_equal_within_rel_and_abs_tolerance (const double LBD, const double UBD, const double epsilonR, const double epsilonA)
 Function for checking if LBD is larger than UBD, or smaller by not more than the specified tolerance. More...
 
template<typename T >
OutVar< T > out_par (T &arr)
 Function for casting to OutVar<type T> More...
 

Detailed Description

namespace holding all essentials of the babBase submodule

Function Documentation

◆ almost_equal()

template<class T >
std::enable_if<!std::numeric_limits<T>::is_integer, bool>::type babBase::almost_equal ( x,
y,
int  ulp = 2 
)

compares if two floating numbers are very close to each other from:https://en.cppreference.com/w/cpp/types/numeric_limits/epsilon

Parameters
[in]xfirst object
[in]ysecond object
[in]ulpunits in last place

◆ calculate_pseudocost_multipliers_minus_and_plus()

std::pair< double, double > babBase::calculate_pseudocost_multipliers_minus_and_plus ( enums::VT  varType,
double  lowerBound,
double  upperBound,
double  branchingPoint,
double  relaxationSolutionPoint 
)

Calculate the multiplier for calculation of pseudocosts.

◆ high_id_first()

double babBase::high_id_first ( const BabNode candidate,
const std::vector< OptimizationVariable > &  globalVars 
)

Function for DFS, possible choice for calculating the node selection score.

◆ larger_or_equal_within_rel_and_abs_tolerance()

bool babBase::larger_or_equal_within_rel_and_abs_tolerance ( const double  LBD,
const double  UBD,
const double  epsilonR,
const double  epsilonA 
)
inline

Function for checking if LBD is larger than UBD, or smaller by not more than the specified tolerance.

Parameters
[in]LBDis the lower bound
[in]UBDis the upper bound
[in]epsilonRis the relative tolerance
[in]epsilonAis the absolute tolerance

◆ low_id_first()

double babBase::low_id_first ( const BabNode candidate,
const std::vector< OptimizationVariable > &  globalVars 
)

Function for Breadth-First-Search possible choice for calculating the node selection score.

◆ low_pruning_score_first()

double babBase::low_pruning_score_first ( const BabNode candidate,
const std::vector< OptimizationVariable > &  globalVars 
)

Function for BFS or lowPruning Score First (default), possible choice for calculating the node selection score.

◆ operator<<()

std::ostream& babBase::operator<< ( std::ostream &  out,
const BabNode node 
)
inline

operator << overloaded for BabNode for easier output

Overloaded operator for easier output. Definition of this operator is in bab.cpp.

Parameters
[out]outis the outstream to be written to
[in]nodeis the B&B node to be printed

◆ out_par()

template<typename T >
OutVar<T> babBase::out_par ( T &  arr)

Function for casting to OutVar<type T>

Parameters
[in]arris the argument to be casted

◆ relative_distance_to_closest_bound()

double babBase::relative_distance_to_closest_bound ( double  pointValue,
double  bound1,
double  bound2,
const babBase::OptimizationVariable variable 
)

Helper function for tiebracking in branching (akin to most fractional although this is only as good as random)

◆ select_branching_dimension_absdiam()

unsigned babBase::select_branching_dimension_absdiam ( const BabNode parentNode,
const std::vector< double > &  relaxationSolutionPoint,
const double  relaxationSolutionObjValue,
const std::vector< OptimizationVariable > &  globalOptimizationVars 
)

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

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

◆ select_branching_dimension_reldiam()

unsigned babBase::select_branching_dimension_reldiam ( const BabNode parentNode,
const std::vector< double > &  relaxationSolutionPoint,
const double  relaxationSolutionObjValue,
const std::vector< OptimizationVariable > &  globalOptimizationVars 
)

Function for selecting the variable to branch on by choosing the one with the largest diameter relative to the original one.

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

◆ select_node_breadthfirst()

std::vector< BabNodeWithInfo >::const_iterator babBase::select_node_breadthfirst ( const std::vector< BabNodeWithInfo > &  nodeVectorIN)

Returns the node added least recently to the tree.

◆ select_node_depthfirst()

std::vector< BabNodeWithInfo >::const_iterator babBase::select_node_depthfirst ( const std::vector< BabNodeWithInfo > &  nodeVectorIN)

Returns the node added most recently to the tree.

◆ select_node_highest_priority()

std::vector< BabNodeWithInfo >::const_iterator babBase::select_node_highest_priority ( const std::vector< BabNodeWithInfo > &  nodeVectorIN)

Returns the node with the highest priority.