68 Brancher(
const std::vector<OptimizationVariable>& variables);
139 std::pair<
bool ,
bool >
branch_on_node(
const BabNode& parentNode,
const std::vector<double>& relaxationSolutionPoint,
double relaxationSolutionObjValue,
unsigned& incumbentNodeId,
double relNodeSizeTol = 0.0);
215 std::pair<BabNodeWithInfo, BabNodeWithInfo>
_create_children(
unsigned branchVar,
const BabNode& parentNode,
double branchVariableRelaxSolutionPoint);
225 unsigned _select_branching_dimension_pseudo_costs(
const BabNode& parentNode,
const std::vector<double>& relaxationSolutionPoint,
const double relaxationSolutionObjValue,
const std::vector<OptimizationVariable>& globalOptimizationVars)
const;
229 std::function<unsigned(
const BabNode& parentNode,
const std::vector<double>& relaxationSolutionPoint,
double relaxationSolutionObjValue,
const std::vector<OptimizationVariable>& globalOptimizationVars)>
_select_branching_dimension;
248 unsigned select_branching_dimension_absdiam(
const BabNode& parentNode,
const std::vector<double>& relaxationSolutionPoint,
const double relaxationSolutionObjValue,
const std::vector<OptimizationVariable>& globalOptimizationVars);
258 unsigned select_branching_dimension_reldiam(
const BabNode& parentNode,
const std::vector<double>& relaxationSolutionPoint,
const double relaxationSolutionObjValue,
const std::vector<OptimizationVariable>& globalOptimizationVars);
271 double low_id_first(
const BabNode& candidate,
const std::vector<OptimizationVariable>& globalVars);
276 double high_id_first(
const BabNode& candidate,
const std::vector<OptimizationVariable>& globalVars);
Brancher & operator=(Brancher &)=default
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.
Definition: babBrancher.cpp:394
Brancher(const std::vector< OptimizationVariable > &variables)
Constructor.
Definition: babBrancher.cpp:24
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 a...
Definition: babBrancher.cpp:465
NS
Enum for selecting the Node Selection heuristic.
Definition: babUtils.h:143
std::vector< double > _pseudocosts_down
Definition: babBrancher.h:233
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.
Definition: babBrancher.cpp:233
std::vector< int > _number_of_trials_down
Definition: babBrancher.h:235
std::vector< int > _number_of_trials_up
Definition: babBrancher.h:234
std::vector< double > _pseudocosts_up
Definition: babBrancher.h:232
std::vector< std::tuple< unsigned, double, BranchingHistoryInfo > > _nodesWaitingForResponse
Definition: babBrancher.h:236
std::vector< double > _incumbentSolutionPoint
Definition: babBrancher.h:237
size_t get_nodes_left() const
Returns the number of nodes left in the tree. The private member _nodesLeft is used instead of nodeVe...
Definition: babTree.h:151
double _calculate_branching_point(double lowerBound, double upperBound, double relaxationValue) const
calculates the branching point. Currently 0.5*(lb+ub);
Definition: babBrancher.cpp:320
Class representing a node in the Branch-and-Bound tree.
Definition: babNode.h:35
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 relati...
Definition: babBrancher.cpp:361
double get_pruning_score_gap() const
Returns the difference between lowest pruning score in the tree and the pruning score threshold.
Definition: babBrancher.h:171
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.
Definition: babBrancher.cpp:72
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.
Definition: babBrancher.cpp:205
BranchStatus
Enum for distinguishing a branching status.
Definition: babTree.h:40
BabNode get_next_node()
Returns the next BabNode to process according to the node selection strategy and node selection score...
Definition: babBrancher.cpp:308
void remove_has_incumbent_from_all_nodes()
Remove the hasIncumbent flag from all nodes.
Definition: babTree.h:198
std::function< unsigned(const BabNode &parentNode, const std::vector< double > &relaxationSolutionPoint, double relaxationSolutionObjValue, const std::vector< OptimizationVariable > &globalOptimizationVars)> _select_branching_dimension
Definition: babBrancher.h:229
BV
Enum for selecting the Branching Variable selection heuristic.
Definition: babUtils.h:153
BabTree _internalBranchAndBoundTree
Definition: babBrancher.h:230
namespace holding all essentials of the babBase submodule
Definition: babBrancher.h:40
Struct for collecting all information that must be saved about a node, so that after it is retrieved ...
Definition: babTree.h:35
This class contains the logic for branching on nodes in the B&B-Tree and selecting nodes to be proces...
Definition: babBrancher.h:62
std::vector< OptimizationVariable > _globalOptimizationVariables
Definition: babBrancher.h:231
Class for representing an optimization variable specified by the user.
Definition: babOptVar.h:100
size_t get_nodes_in_tree() const
Returns the number of nodes in the tree.
Definition: babBrancher.h:144
double get_lowest_pruning_score() const
Return the lowest pruning score. Returns infinity if tree is empty.
Definition: babTree.cpp:116
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.
Definition: babBrancher.cpp:277
double decrease_pruning_score_threshold_to(const double newThreshold)
Decreases the pruning score threshold to the supplied value. Nodes with pruning score exceeding the n...
Definition: babBrancher.cpp:294
This class represents an node in the B&B-Tree with additional information attached that is used in se...
Definition: babTree.h:64
double get_pruning_score_gap() const
Query the largest gap between the pruning threshold and the the pruning scores of the nodes....
Definition: babTree.cpp:130
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.
Definition: babTree.h:215
double high_id_first(const BabNode &candidate, const std::vector< OptimizationVariable > &globalVars)
Function for DFS, possible choice for calculating the node selection score.
Definition: babBrancher.cpp:493
void register_node_change(const int Id, const BabNode &nodeAfterProcessing)
Registers the changes made to a node during processing to extract information for branching heuristic...
Definition: babBrancher.cpp:82
void insert_root_node(const BabNode &rootNode)
Inserts the root node into the tree.
Definition: babBrancher.cpp:132
double get_lowest_pruning_score() const
Returns the lowest pruning score of all nodes in the tree.
Definition: babBrancher.h:166
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 w...
Definition: babBrancher.cpp:40
std::function< double(const BabNode &, const std::vector< OptimizationVariable > &)> _node_score_calculating_function
Definition: babBrancher.h:228
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.
Definition: babBrancher.h:190
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.
Definition: babBrancher.cpp:484
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.
Definition: babBrancher.cpp:141
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.
Definition: babBrancher.cpp:329
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...
Definition: babBrancher.h:157
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.
Definition: babBrancher.cpp:63
double get_pruning_score_threshold() const
Query the the pruning score threshold.
Definition: babTree.h:206
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.
Definition: babBrancher.cpp:445
Represents the B&B-Tree, manages the way nodes are saved and retrieved and pruned.
Definition: babTree.h:134
virtual ~Brancher()=default
double get_pruning_score_threshold() const
Returns the pruning score threshold.
Definition: babBrancher.h:183
VT
Enum for representing the Variable Type of an optimization variable as specified by the user.
Definition: babOptVar.h:40
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 select...
Definition: babBrancher.cpp:475