MAiNGO
babTree.h
Go to the documentation of this file.
1 /**********************************************************************************
2  * Copyright (c) 2019 Process Systems Engineering (AVT.SVT), RWTH Aachen University
3  *
4  * This program and the accompanying materials are made available under the
5  * terms of the Eclipse Public License 2.0 which is available at
6  * http://www.eclipse.org/legal/epl-2.0.
7  *
8  * SPDX-License-Identifier: EPL-2.0
9  *
10  * @file babTree.h
11  *
12  * @brief File containing definition of the Branch-and-Bound tree class.
13  *
14  **********************************************************************************/
15 
16 #pragma once
17 
18 #include "babException.h"
19 #include "babNode.h"
20 #include "babUtils.h"
21 
22 #include <algorithm>
23 #include <cassert>
24 #include <limits>
25 #include <utility>
26 
27 
28 namespace babBase {
29 
30 
40  enum class BranchStatus {
41  wasBranchedUp = 1,
43  wasNotBranched // this last case happens e.g. for fixed nodes that are only readded to the tree
44  } branchStatus;
46  int branchVar = -1;
51 };
65 
66  public:
73  BabNodeWithInfo(BabNode nodeIn, double selScoreIn):
74  node(nodeIn), _nodeSelectionScore(selScoreIn) {}
75 
81  operator BabNode const&() const& { return node; }
82 
86  operator BabNode &&() && { return std::move(node); } //note the ref-qualifiers
87 
91  double get_node_selection_score() const { return _nodeSelectionScore; }
92 
96  void set_node_selection_score(double newScore) { _nodeSelectionScore = newScore; }
97 
101  double get_pruning_score() const { return node.get_pruning_score(); }
102 
106  unsigned get_ID() const { return node.get_ID(); };
107 
115 
116  private:
118 };
119 
120 
134 class BabTree {
135  public:
139  BabTree();
140  // Virtual Destructor for the case of inheritance. However, the compiler now will not autogenarate the other constructors. So we tell it to:
141  virtual ~BabTree() = default;
142  BabTree(const BabTree&) = default;
143  BabTree& operator=(BabTree&) = default;
144  BabTree(BabTree&&) = default;
145  BabTree& operator=(BabTree&&) = default;
151  size_t get_nodes_left() const
152  {
153  assert(_nodesLeft == _nodeVector.size());
154  return _nodesLeft;
155  };
156 
162  unsigned get_valid_id() { return ++_Id; }; //increment should be declared atomic for parallel use!
163 
167  void add_node(BabNodeWithInfo node);
168 
175 
179  double get_lowest_pruning_score() const;
180 
186  double get_pruning_score_gap() const;
187 
192  double set_pruning_score_threshold(const double newThreshold);
193 
199  {
200  std::for_each(_nodeVector.begin(), _nodeVector.end(), [](BabNodeWithInfo& b) { b.node.set_holds_incumbent(false); });
201  }
202 
207 
215  void enable_pruning_with_rel_and_abs_tolerance(const double relTol, const double absTol)
216  {
217  _relPruningTol = relTol;
218  _absPruningTol = absTol;
219  };
220 
227  void set_node_selection_strategy(enums::NS nodeSelectionStrategyType);
228 
229  private:
233  void delete_element(std::vector<BabNodeWithInfo>::iterator targetNodeIt);
234 
242  double _fathom_nodes_exceeding_pruning_threshold(const double newThreshold, const double relTol, const double absTol);
243 
246  double _relPruningTol = 0.0;
247  double _absPruningTol = 0.0;
249  size_t _nodesLeft;
250  unsigned _Id;
253  // Function has to accept a vector of BabNodes and return a const_iterator to the selected node. No assumption can be made about the ordering of the passed vector, except that the .front() entry is the one with the largest nodeSelectionScore
254  std::function<std::vector<BabNodeWithInfo>::const_iterator(const std::vector<BabNodeWithInfo>& nodeVectorIN)> _select_node;
255  std::vector<BabNodeWithInfo> _nodeVector;
256 };
257 
258 
260 std::vector<BabNodeWithInfo>::const_iterator select_node_highest_priority(const std::vector<BabNodeWithInfo>& nodeVectorIN);
261 
263 std::vector<BabNodeWithInfo>::const_iterator select_node_breadthfirst(const std::vector<BabNodeWithInfo>& nodeVectorIN);
264 
266 std::vector<BabNodeWithInfo>::const_iterator select_node_depthfirst(const std::vector<BabNodeWithInfo>& nodeVectorIN);
267 
276 
284  bool operator()(const BabNodeWithInfo& a, const BabNodeWithInfo& b) const
285  {
287  };
288 };
289 
290 
299 
307  bool operator()(const BabNodeWithInfo& a, const BabNodeWithInfo& b) const
308  {
309  return a.get_pruning_score() < b.get_pruning_score();
310  };
311 };
312 
313 
314 } //end namespace babBase
double _relPruningTol
Definition: babTree.h:246
bool operator()(const BabNodeWithInfo &a, const BabNodeWithInfo &b) const
() operator for comparing
Definition: babTree.h:284
NS
Enum for selecting the Node Selection heuristic.
Definition: babUtils.h:143
int get_ID() const
Function for querying the node ID.
Definition: babNode.h:100
Functor for comparing pruning scores.
Definition: babTree.h:298
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
Class representing a node in the Branch-and-Bound tree.
Definition: babNode.h:35
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 ...
Definition: babTree.cpp:171
BranchingHistoryInfo branchingInfo
Object storing the branching history.
Definition: babTree.h:106
enum babBase::BranchingHistoryInfo::BranchStatus branchStatus
BranchStatus
Enum for distinguishing a branching status.
Definition: babTree.h:40
void remove_has_incumbent_from_all_nodes()
Remove the hasIncumbent flag from all nodes.
Definition: babTree.h:198
std::function< std::vector< BabNodeWithInfo >::const_iterator(const std::vector< BabNodeWithInfo > &nodeVectorIN)> _select_node
Definition: babTree.h:254
BabTree()
Default constructor for BabTree, threshold set to INF.
Definition: babTree.cpp:24
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
std::vector< BabNodeWithInfo >::const_iterator select_node_breadthfirst(const std::vector< BabNodeWithInfo > &nodeVectorIN)
Returns the node added least recently to the tree.
Definition: babTree.cpp:223
double relaxationSolutionPointForBranchingVariable
Definition: babTree.h:48
double _pruningScoreThreshold
Definition: babTree.h:244
std::vector< BabNodeWithInfo >::const_iterator select_node_highest_priority(const std::vector< BabNodeWithInfo > &nodeVectorIN)
Returns the node with the highest priority.
Definition: babTree.cpp:200
double get_lowest_pruning_score() const
Return the lowest pruning score. Returns infinity if tree is empty.
Definition: babTree.cpp:116
BabNodeWithInfo(BabNode nodeIn, double selScoreIn)
Constructor.
Definition: babTree.h:73
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
unsigned get_valid_id()
Returns a valid Id for the next node.
Definition: babTree.h:162
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 _absPruningTol
Definition: babTree.h:247
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 fathom...
Definition: babTree.cpp:139
int branchVar
Definition: babTree.h:46
void delete_element(std::vector< BabNodeWithInfo >::iterator targetNodeIt)
Removes a node from the tree.
Definition: babTree.cpp:60
Functor for comparing node priorities.
Definition: babTree.h:275
void set_node_selection_score(double newScore)
Sets the node selection score of the node.
Definition: babTree.h:96
BabNode node
Definition: babTree.h:76
std::vector< BabNodeWithInfo > _nodeVector
Definition: babTree.h:255
unsigned get_ID() const
Returns the ID of the node.
Definition: babTree.h:106
std::vector< BabNodeWithInfo >::const_iterator select_node_depthfirst(const std::vector< BabNodeWithInfo > &nodeVectorIN)
Returns the node added most recently to the tree.
Definition: babTree.cpp:209
double parentLowerBound
Definition: babTree.h:49
BabNodeWithInfo pop_next_node()
Return the node according to the node selection strategy and removes it from the tree.
Definition: babTree.cpp:74
double parentUpperBound
Definition: babTree.h:50
virtual ~BabTree()=default
double get_pruning_score_threshold() const
Query the the pruning score threshold.
Definition: babTree.h:206
Represents the B&B-Tree, manages the way nodes are saved and retrieved and pruned.
Definition: babTree.h:134
void add_node(BabNodeWithInfo node)
Add node to the list of nodes to process.
Definition: babTree.cpp:41
size_t _nodesLeft
Definition: babTree.h:249
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) pru...
Definition: babTree.cpp:149
double get_pruning_score() const
Returns the pruning score of the node.
Definition: babTree.h:101
double _nodeSelectionScore
Definition: babTree.h:117
BabTree & operator=(BabTree &)=default
double get_pruning_score() const
Function for querying the pruning score within this node.
Definition: babNode.h:80
bool operator()(const BabNodeWithInfo &a, const BabNodeWithInfo &b) const
() opeartor for comparing
Definition: babTree.h:307
double get_node_selection_score() const
Returns the node selection score of the node.
Definition: babTree.h:91
unsigned _Id
Definition: babTree.h:250