MAiNGO
babBrancher.h
Go to the documentation of this file.
1 
14  /**********************************************************************************
15  * Copyright (c) 2019 Process Systems Engineering (AVT.SVT), RWTH Aachen University
16  *
17  * This program and the accompanying materials are made available under the
18  * terms of the Eclipse Public License 2.0 which is available at
19  * http://www.eclipse.org/legal/epl-2.0.
20  *
21  * SPDX-License-Identifier: EPL-2.0
22  *
23  * @file babBrancher.h
24  *
25  * @brief File containing definition of the Branch-and-Bound brancher class.
26  *
27  **********************************************************************************/
28 
29 #pragma once
30 
31 #include "babException.h"
32 #include "babNode.h"
33 #include "babOptVar.h"
34 #include "babTree.h"
35 #include "babUtils.h"
36 
37 #include <functional>
38 
39 
40 namespace babBase {
41 
42 
62 class Brancher {
63 
64  public:
68  Brancher(const std::vector<OptimizationVariable>& variables);
69  // Virtual Destructor for the case of inheritance. However, the compiler now will not autogenarate the other constructors. So we tell it to:
70  virtual ~Brancher() = default;
71  Brancher(const Brancher&) = default;
72  Brancher& operator=(Brancher&) = default;
73  Brancher(Brancher&&) = default;
74  Brancher& operator=(Brancher&&) = default;
80  void set_branching_dimension_selection_strategy(const enums::BV branchingVarStratSelection);
81 
89  void set_node_selection_strategy(const enums::NS nodeSelectionStratType);
90 
98  void set_node_selection_score_function(std::function<double(const BabNode&, const std::vector<OptimizationVariable>&)> newNodeScoreFunction);
99 
111  void register_node_change(const int Id, const BabNode& nodeAfterProcessing);
112 
118  void insert_root_node(const BabNode& rootNode);
119 
139  std::pair<bool /*isFixed*/, bool /*canBeConsideredFixed*/> branch_on_node(const BabNode& parentNode, const std::vector<double>& relaxationSolutionPoint, double relaxationSolutionObjValue, unsigned& incumbentNodeId, double relNodeSizeTol = 0.0);
140 
145 
152 
157  void set_new_incumbent_point(std::vector<double> incumbentPoint)
158  {
159  this->_incumbentSolutionPoint = incumbentPoint;
161  } /* pruning_score may be LB but Threshold should be UB (!) thus the following would not work: _internalBranchAndBoundTree.decrease_pruning_score_threshold_to(incumbentIn.get_pruning_score());*/
162 
167 
172 
177  double decrease_pruning_score_threshold_to(const double newThreshold);
178 
184 
191 
195  std::vector<BabNode> get_all_nodes_from_strong_branching(const BabNode& parentNode, const std::vector<double>& relaxationSolutionPoint);
196 
197  private:
205  BabNodeWithInfo _create_node_with_info_from_node(BabNode normalNode, unsigned branchedVariable, BranchingHistoryInfo::BranchStatus branchStatus, double variableRelaxationSolutionPoint, double parentLowerBound, double parentUpperBound) const;
206 
207 
211  double _calculate_branching_point(double lowerBound, double upperBound, double relaxationValue) const;
215  std::pair<BabNodeWithInfo, BabNodeWithInfo> _create_children(unsigned branchVar, const BabNode& parentNode, double branchVariableRelaxSolutionPoint);
216 
225  unsigned _select_branching_dimension_pseudo_costs(const BabNode& parentNode, const std::vector<double>& relaxationSolutionPoint, const double relaxationSolutionObjValue, const std::vector<OptimizationVariable>& globalOptimizationVars) const;
226 
227 
228  std::function<double(const BabNode&, const std::vector<OptimizationVariable>&)> _node_score_calculating_function;
229  std::function<unsigned(const BabNode& parentNode, const std::vector<double>& relaxationSolutionPoint, double relaxationSolutionObjValue, const std::vector<OptimizationVariable>& globalOptimizationVars)> _select_branching_dimension;
231  std::vector<OptimizationVariable> _globalOptimizationVariables;
232  std::vector<double> _pseudocosts_up;
233  std::vector<double> _pseudocosts_down;
234  std::vector<int> _number_of_trials_up;
235  std::vector<int> _number_of_trials_down;
236  std::vector<std::tuple<unsigned /* id*/, double /*parentPruningScore*/, BranchingHistoryInfo>> _nodesWaitingForResponse;
237  std::vector<double> _incumbentSolutionPoint;
238 };
239 
248 unsigned select_branching_dimension_absdiam(const BabNode& parentNode, const std::vector<double>& relaxationSolutionPoint, const double relaxationSolutionObjValue, const std::vector<OptimizationVariable>& globalOptimizationVars);
249 
258 unsigned select_branching_dimension_reldiam(const BabNode& parentNode, const std::vector<double>& relaxationSolutionPoint, const double relaxationSolutionObjValue, const std::vector<OptimizationVariable>& globalOptimizationVars);
262 double relative_distance_to_closest_bound(double pointValue, double bound1, double bound2, const babBase::OptimizationVariable& variable);
263 
267 double low_pruning_score_first(const BabNode& candidate, const std::vector<OptimizationVariable>& globalVars);
271 double low_id_first(const BabNode& candidate, const std::vector<OptimizationVariable>& globalVars);
272 
276 double high_id_first(const BabNode& candidate, const std::vector<OptimizationVariable>& globalVars);
280 std::pair<double, double> calculate_pseudocost_multipliers_minus_and_plus(enums::VT varType, double lowerBound, double upperBound, double branchingPoint, double relaxationSolutionPoint);
281 
282 
283 } //end namespace babBase
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