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
Coin::SmartPtr< BCP_user_data > _user
Definition: BCP_tm_node.hpp:54
static int num_remote_nodes
Definition: BCP_tm_node.hpp:74
BCP_tm_node_to_send(BCP_tm_prob &p, const BCP_tm_node *node, const BCP_message_tag tag)
int child_num() const
NO OLD DOC.
This class stores data about how an object set (set of vars or set of cuts) changes.
int mark_descendants_for_deletion()
static std::map< int, BCP_tm_node_to_send * > waiting
size_t size() const
bool receive_cuts(BCP_buffer &buf)
return true if has everything to send the thing off to the LP.
BCP_tm_node_data(BCP_node_change *d=NULL)
Definition: BCP_tm_node.hpp:55
int maxdepth() const
void increase_processed()
int getDepth() const
void push_back(const_reference x)
Append x to the end of the vector.
void insert(BCP_tm_node *node)
const BCP_tm_node * parent() const
This class describes the message buffer used for all processes of BCP.
Definition: BCP_buffer.hpp:39
int processed() const
bool send()
return true or false depending on whether the node was really sent out or it's still waiting for some...
BCP_message_tag
This enumerative constant describes the message tags different processes of BCP understand.
BCP_vec< BCP_tm_node * >::iterator end()
NO OLD DOC.
Definition: BCP_tm.hpp:136
int _pruned_leaf_num
Definition: BCP_tm_node.hpp:93
const BCP_tm_node * child(int ind) const
BCP_tm_node_status status
Definition: BCP_tm_node.hpp:78
BCP_tm_node * child(int ind)
bool receive_vars(BCP_buffer &buf)
return true if has everything to send the thing off to the LP.
static int num_local_nodes
Definition: BCP_tm_node.hpp:73
void new_child(BCP_tm_node *node)
void reserve(const size_t n)
Reallocate the object to make space for n entries.
iterator end()
Return an iterator to the end of the object.
Definition: BCP_vector.hpp:104
Coin::SmartPtr< BCP_node_change > _desc
Definition: BCP_tm_node.hpp:53
BCP_tm_node_status
Node status in the Tree Manager.
Definition: BCP_tm_node.hpp:23
int _tobepriced_leaf_num
Definition: BCP_tm_node.hpp:95
BCP_vec< BCP_tm_node * > _children
Definition: BCP_tm_node.hpp:87
BCP_tm_node * operator[](int index)
int birth_index() const
size_t size() const
Return the current number of entries.
Definition: BCP_vector.hpp:116
BCP_tm_node * _parent
Definition: BCP_tm_node.hpp:82
void remove(int index)
void reserve_child_num(int num)
reference front()
Return a reference to the first entry.
Definition: BCP_vector.hpp:129
BCP_tm_node_data _data
iterator begin()
Return an iterator to the beginning of the object.
Definition: BCP_vector.hpp:99
BCP_vec< BCP_tm_node * >::iterator begin()
BCP_tm_node * parent()
int index() const
int _processed_leaf_num
Definition: BCP_tm_node.hpp:91
BCP_tm_node * root()
double true_lower_bound(const BCP_tm_node *node) const
Return the worst true lower bound in the search tree.
void remove_child(BCP_tm_node *node)
bool receive_node_desc(BCP_buffer &buf)
return true if has everything to send the thing off to the LP.
void enumerate_leaves(BCP_tm_node *node, const double obj_limit)