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