Bcp  1.4.4
BCP_tm_node.hpp
Go to the documentation of this file.
1 // Copyright (C) 2000, International Business Machines
2 // Corporation and others. All Rights Reserved.
3 #ifndef _BCP_TM_NODE
4 #define _BCP_TM_NODE
5 
6 //#include <cfloat>
7 
8 #include <map>
9 
10 #include "CoinSearchTree.hpp"
11 #include "CoinSmartPtr.hpp"
12 
13 #include "BCP_math.hpp"
14 #include "BCP_vector.hpp"
15 
16 #include "BCP_message_tag.hpp"
17 #include "BCP_obj_change.hpp"
18 #include "BCP_node_change.hpp"
19 #include "BCP_USER.hpp"
20 
42 };
43 
44 //#############################################################################
45 
46 class BCP_tm_node;
47 class BCP_tm_prob;
48 
49 //#############################################################################
50 
52 public:
56 };
57 
58 //=============================================================================
59 
60 class BCP_tm_node : public CoinTreeNode {
61 private:
65  BCP_tm_node(const BCP_tm_node&);
67  BCP_tm_node& operator=(const BCP_tm_node&);
70  // NOTE: deleting a tree_node deletes the whole subtree below!
71 public:
73  static int num_local_nodes;
74  static int num_remote_nodes;
75  // *FIXME* break into groups
80  int _index;
83 
89  int lp, cg, cp, vg, vp;
97  int _leaf_num;
98 
102  int _ws_storage:4;
103 
105  // Exactly one of the next two is always irrelevant */
108 
111 public:
115  BCP_tm_node(int level, BCP_node_change* desc);
116 
118 // BCP_tm_node(int level, BCP_node_change* desc,
119 // BCP_tm_node* parent, int index);
122  {
123  if (_locally_stored) {
124  --num_local_nodes;
125  } else {
127  }
128  }
134  inline int index() const { return _index; }
136  inline int child_num() const { return _children.size(); }
138  inline int birth_index() const { return _birth_index; }
139 
141  // inline BCP_user_data* user_data() { return _data._user; }
143  inline BCP_tm_node* child(int ind) { return _children[ind]; }
145  inline BCP_tm_node* parent() { return _parent; }
146 
148  // inline const BCP_user_data* user_data() const { return _data._user; }
150  inline const BCP_tm_node* child(int ind) const { return _children[ind]; }
152  inline const BCP_tm_node* parent() const { return _parent; }
159  // Marking the descendants for deletion means that their _index fields are
160  // set to -1. The reason is that some book-keeping must be one with the CP,
161  // VP processes; with the next phase list, with the priority queue of the
162  // current phase (and maybe sthing else?). So this function only marks, and
163  // the data will be deleted later.
166  void remove_child(BCP_tm_node* node);
168  inline void reserve_child_num(int num) { _children.reserve(num); }
170  inline void new_child(BCP_tm_node* node) { _children.push_back(node); }
172 };
173 
174 //#############################################################################
175 
178 class BCP_tree {
179 private:
181  BCP_vec<BCP_tm_node*> _tree;
183  int maxdepth_;
184  int processed_;
185 
186 public:
190  BCP_tree() : _tree(), maxdepth_(0), processed_(0) {}
193  for (int i = _tree.size() - 1; i >= 0; --i) {
194  delete _tree[i];
195  }
196  }
202  inline BCP_vec<BCP_tm_node*>::iterator begin() { return _tree.begin(); }
204  inline BCP_vec<BCP_tm_node*>::iterator end() { return _tree.end(); }
205 
207  inline BCP_tm_node* root() { return _tree.front(); }
209  inline BCP_tm_node* operator[](int index) { return _tree[index]; }
211  inline size_t size() const { return _tree.size(); }
213  inline int maxdepth() const { return maxdepth_; }
215  inline int processed() const { return processed_; }
216  inline void increase_processed() { ++processed_; }
222  double true_lower_bound(const BCP_tm_node* node) const;
224  void enumerate_leaves(BCP_tm_node* node, const double obj_limit);
226  inline void insert(BCP_tm_node* node) {
227  node->_index = _tree.size();
228  _tree.push_back(node);
229  if (node->getDepth() > maxdepth_)
230  maxdepth_ = node->getDepth();
231  }
232  inline void remove(int index) {
233  _tree[index] = 0;
234  }
236 };
237 
238 //#############################################################################
239 class BCP_tm_node_to_send;
240 
242 {
243 public:
244  static std::map<int, BCP_tm_node_to_send*> waiting;
245 
246 private:
247  BCP_tm_prob& p;
248 
250  BCP_message_tag msgtag;
251 
254  const int ID;
255 
256  const BCP_tm_node* node;
259  const BCP_tm_node** root_path;
261  int* child_index;
264  BCP_tm_node_data* node_data_on_root_path;
265 
267  int level;
268 
270  int explicit_core_level;
271  int explicit_var_level;
272  int explicit_cut_level;
273  int explicit_ws_level;
274  int explicit_all_level;
275 
277  int missing_desc_num;
279  int missing_var_num;
281  int missing_cut_num;
282 
286  BCP_obj_set_change var_set;
287  BCP_obj_set_change cut_set;
292 
293 public:
294 
296  const BCP_message_tag tag);
298 
301  bool send();
302 
306  bool receive_node_desc(BCP_buffer& buf);
310  bool receive_vars(BCP_buffer& buf);
314  bool receive_cuts(BCP_buffer& buf);
315 };
316 
317 #endif
BCP_tm_node::status
BCP_tm_node_status status
Definition: BCP_tm_node.hpp:78
BCP_vector.hpp
BCP_tm_node::_parent
BCP_tm_node * _parent
Definition: BCP_tm_node.hpp:82
CoinTreeNode
BCP_tm_node_status
BCP_tm_node_status
Node status in the Tree Manager.
Definition: BCP_tm_node.hpp:23
BCP_tm_node::vp
int vp
Definition: BCP_tm_node.hpp:89
BCP_tm_node_to_send::~BCP_tm_node_to_send
~BCP_tm_node_to_send()
BCP_tm_node::cg
int cg
Definition: BCP_tm_node.hpp:89
BCP_vec::front
reference front()
Return a reference to the first entry.
Definition: BCP_vector.hpp:129
BCP_NextPhaseNode_OverUB
@ BCP_NextPhaseNode_OverUB
Definition: BCP_tm_node.hpp:39
BCP_tm_node_data::BCP_tm_node_data
BCP_tm_node_data(BCP_node_change *d=NULL)
Definition: BCP_tm_node.hpp:55
BCP_tree::begin
BCP_vec< BCP_tm_node * >::iterator begin()
Definition: BCP_tm_node.hpp:202
BCP_message_tag
BCP_message_tag
This enumerative constant describes the message tags different processes of BCP understand.
Definition: BCP_message_tag.hpp:11
BCP_tm_node_to_send::waiting
static std::map< int, BCP_tm_node_to_send * > waiting
Definition: BCP_tm_node.hpp:244
BCP_tm_node::_tobepriced_leaf_num
int _tobepriced_leaf_num
Definition: BCP_tm_node.hpp:95
BCP_DefaultNode
@ BCP_DefaultNode
Definition: BCP_tm_node.hpp:25
BCP_node_change
Definition: BCP_node_change.hpp:19
BCP_tree::remove
void remove(int index)
Definition: BCP_tm_node.hpp:232
CoinSmartPtr.hpp
BCP_tree::size
size_t size() const
Definition: BCP_tm_node.hpp:211
BCP_tm_node::_data
BCP_tm_node_data _data
Definition: BCP_tm_node.hpp:107
BCP_tm_node_data::_desc
Coin::SmartPtr< BCP_node_change > _desc
Definition: BCP_tm_node.hpp:53
BCP_vec< BCP_tm_node * >
BCP_tm_node_data::_user
Coin::SmartPtr< BCP_user_data > _user
Definition: BCP_tm_node.hpp:54
BCP_ActiveNode
@ BCP_ActiveNode
Definition: BCP_tm_node.hpp:29
BCP_tm_node::new_child
void new_child(BCP_tm_node *node)
Definition: BCP_tm_node.hpp:170
BCP_tm_node::_birth_index
int _birth_index
Definition: BCP_tm_node.hpp:85
BCP_vec::size
size_t size() const
Return the current number of entries.
Definition: BCP_vector.hpp:116
BCP_tm_node::child_num
int child_num() const
Definition: BCP_tm_node.hpp:136
BCP_tm_node_to_send::receive_cuts
bool receive_cuts(BCP_buffer &buf)
return true if has everything to send the thing off to the LP.
BCP_tm_node::vg
int vg
Definition: BCP_tm_node.hpp:89
BCP_tm_node::parent
BCP_tm_node * parent()
Definition: BCP_tm_node.hpp:145
BCP_ProcessedNode
@ BCP_ProcessedNode
Definition: BCP_tm_node.hpp:27
BCP_NextPhaseNode_Infeas
@ BCP_NextPhaseNode_Infeas
Definition: BCP_tm_node.hpp:41
BCP_tm_node::num_remote_nodes
static int num_remote_nodes
Definition: BCP_tm_node.hpp:74
BCP_tm_node_to_send::send
bool send()
return true or false depending on whether the node was really sent out or it's still waiting for some...
BCP_tm_node::_locally_stored
int _locally_stored
Definition: BCP_tm_node.hpp:104
BCP_tm_node::index
int index() const
Definition: BCP_tm_node.hpp:134
BCP_tree::enumerate_leaves
void enumerate_leaves(BCP_tm_node *node, const double obj_limit)
BCP_obj_change.hpp
BCP_tm_node::mark_descendants_for_deletion
int mark_descendants_for_deletion()
BCP_CandidateNode
@ BCP_CandidateNode
Definition: BCP_tm_node.hpp:37
BCP_tm_node::_processed_leaf_num
int _processed_leaf_num
Definition: BCP_tm_node.hpp:91
BCP_math.hpp
BCP_vec::begin
iterator begin()
Return an iterator to the beginning of the object.
Definition: BCP_vector.hpp:99
BCP_tm_node::_var_storage
int _var_storage
Definition: BCP_tm_node.hpp:100
BCP_tree::processed
int processed() const
Definition: BCP_tm_node.hpp:215
BCP_vec::push_back
void push_back(const_reference x)
Append x to the end of the vector.
Definition: BCP_vector_general.hpp:300
BCP_tree::~BCP_tree
~BCP_tree()
Definition: BCP_tm_node.hpp:192
BCP_PrunedNode_Discarded
@ BCP_PrunedNode_Discarded
Definition: BCP_tm_node.hpp:35
BCP_tree::true_lower_bound
double true_lower_bound(const BCP_tm_node *node) const
Return the worst true lower bound in the search tree.
BCP_tm_node::child
const BCP_tm_node * child(int ind) const
Definition: BCP_tm_node.hpp:150
BCP_tree::end
BCP_vec< BCP_tm_node * >::iterator end()
Definition: BCP_tm_node.hpp:204
BCP_tm_node::_core_storage
int _core_storage
Definition: BCP_tm_node.hpp:99
Coin::SmartPtr< BCP_node_change >
BCP_tm_node::_ws_storage
int _ws_storage
Definition: BCP_tm_node.hpp:102
BCP_tm_node
Definition: BCP_tm_node.hpp:60
BCP_tm_prob
NO OLD DOC.
Definition: BCP_tm.hpp:136
BCP_tm_node::remove_child
void remove_child(BCP_tm_node *node)
BCP_tm_node_to_send::receive_vars
bool receive_vars(BCP_buffer &buf)
return true if has everything to send the thing off to the LP.
BCP_PrunedNode_Infeas
@ BCP_PrunedNode_Infeas
Definition: BCP_tm_node.hpp:33
BCP_PrunedNode_OverUB
@ BCP_PrunedNode_OverUB
Definition: BCP_tm_node.hpp:31
BCP_tree::increase_processed
void increase_processed()
Definition: BCP_tm_node.hpp:216
BCP_tm_node::birth_index
int birth_index() const
Definition: BCP_tm_node.hpp:138
CoinSearchTree.hpp
BCP_vec::reserve
void reserve(const size_t n)
Reallocate the object to make space for n entries.
Definition: BCP_vector_general.hpp:112
BCP_tree::root
BCP_tm_node * root()
Definition: BCP_tm_node.hpp:207
BCP_tm_node::num_local_nodes
static int num_local_nodes
Definition: BCP_tm_node.hpp:73
BCP_tm_node::_index
int _index
Definition: BCP_tm_node.hpp:80
BCP_tm_node::_leaf_num
int _leaf_num
Definition: BCP_tm_node.hpp:97
BCP_tm_node::_cut_storage
int _cut_storage
Definition: BCP_tm_node.hpp:101
BCP_tm_node::~BCP_tm_node
~BCP_tm_node()
Definition: BCP_tm_node.hpp:121
BCP_tree::insert
void insert(BCP_tm_node *node)
Definition: BCP_tm_node.hpp:226
BCP_tm_node::_children
BCP_vec< BCP_tm_node * > _children
Definition: BCP_tm_node.hpp:87
BCP_tm_node::child
BCP_tm_node * child(int ind)
Definition: BCP_tm_node.hpp:143
BCP_message_tag.hpp
BCP_USER.hpp
BCP_tree::BCP_tree
BCP_tree()
Definition: BCP_tm_node.hpp:190
BCP_tm_node::cp
int cp
Definition: BCP_tm_node.hpp:89
BCP_vec::end
iterator end()
Return an iterator to the end of the object.
Definition: BCP_vector.hpp:104
BCP_tm_node::_data_location
int _data_location
Definition: BCP_tm_node.hpp:106
BCP_tm_node_data
Definition: BCP_tm_node.hpp:51
BCP_tm_node_to_send::receive_node_desc
bool receive_node_desc(BCP_buffer &buf)
return true if has everything to send the thing off to the LP.
CoinTreeNode::getDepth
int getDepth() const
BCP_buffer
This class describes the message buffer used for all processes of BCP.
Definition: BCP_buffer.hpp:39
BCP_tree::maxdepth
int maxdepth() const
Definition: BCP_tm_node.hpp:213
BCP_tm_node::_pruned_leaf_num
int _pruned_leaf_num
Definition: BCP_tm_node.hpp:93
BCP_tree::operator[]
BCP_tm_node * operator[](int index)
Definition: BCP_tm_node.hpp:209
BCP_tree
NO OLD DOC.
Definition: BCP_tm_node.hpp:178
BCP_tm_node::parent
const BCP_tm_node * parent() const
Definition: BCP_tm_node.hpp:152
BCP_tm_node::lp
int lp
Definition: BCP_tm_node.hpp:89
BCP_tm_node::reserve_child_num
void reserve_child_num(int num)
Definition: BCP_tm_node.hpp:168
BCP_node_change.hpp
BCP_tm_node_to_send
Definition: BCP_tm_node.hpp:241
BCP_tm_node_to_send::BCP_tm_node_to_send
BCP_tm_node_to_send(BCP_tm_prob &p, const BCP_tm_node *node, const BCP_message_tag tag)
BCP_obj_set_change
This class stores data about how an object set (set of vars or set of cuts) changes.
Definition: BCP_obj_change.hpp:57