00001
00002
00003 #ifndef _BCP_TM_NODE
00004 #define _BCP_TM_NODE
00005
00006
00007
00008 #include <map>
00009
00010 #include "CoinSearchTree.hpp"
00011 #include "CoinSmartPtr.hpp"
00012
00013 #include "BCP_math.hpp"
00014 #include "BCP_vector.hpp"
00015
00016 #include "BCP_message_tag.hpp"
00017 #include "BCP_obj_change.hpp"
00018 #include "BCP_node_change.hpp"
00019 #include "BCP_USER.hpp"
00020
00023 enum BCP_tm_node_status{
00025 BCP_DefaultNode,
00027 BCP_ProcessedNode,
00029 BCP_ActiveNode,
00031 BCP_PrunedNode_OverUB,
00033 BCP_PrunedNode_Infeas,
00035 BCP_PrunedNode_Discarded,
00037 BCP_CandidateNode,
00039 BCP_NextPhaseNode_OverUB,
00041 BCP_NextPhaseNode_Infeas
00042 };
00043
00044
00045
00046 class BCP_tm_node;
00047 class BCP_tm_prob;
00048
00049
00050
00051 class BCP_tm_node_data {
00052 public:
00053 Coin::SmartPtr<BCP_node_change> _desc;
00054 Coin::SmartPtr<BCP_user_data> _user;
00055 BCP_tm_node_data(BCP_node_change* d = NULL) : _desc(d), _user(0) {}
00056 };
00057
00058
00059
00060 class BCP_tm_node : public CoinTreeNode {
00061 private:
00065 BCP_tm_node(const BCP_tm_node&);
00067 BCP_tm_node& operator=(const BCP_tm_node&);
00070
00071 public:
00073 static int num_local_nodes;
00074 static int num_remote_nodes;
00075
00078 BCP_tm_node_status status;
00080 int _index;
00082 BCP_tm_node* _parent;
00083
00085 int _birth_index;
00087 BCP_vec<BCP_tm_node*> _children;
00089 int lp, cg, cp, vg, vp;
00091 int _processed_leaf_num;
00093 int _pruned_leaf_num;
00095 int _tobepriced_leaf_num;
00097 int _leaf_num;
00098
00099 int _core_storage:4;
00100 int _var_storage:4;
00101 int _cut_storage:4;
00102 int _ws_storage:4;
00103
00104 int _locally_stored:2;
00105
00106 int _data_location:30;
00107 BCP_tm_node_data _data;
00108
00111 public:
00115 BCP_tm_node(int level, BCP_node_change* desc);
00116
00118
00119
00121 ~BCP_tm_node()
00122 {
00123 if (_locally_stored) {
00124 --num_local_nodes;
00125 } else {
00126 --num_remote_nodes;
00127 }
00128 }
00134 inline int index() const { return _index; }
00136 inline int child_num() const { return _children.size(); }
00138 inline int birth_index() const { return _birth_index; }
00139
00141
00143 inline BCP_tm_node* child(int ind) { return _children[ind]; }
00145 inline BCP_tm_node* parent() { return _parent; }
00146
00148
00150 inline const BCP_tm_node* child(int ind) const { return _children[ind]; }
00152 inline const BCP_tm_node* parent() const { return _parent; }
00159
00160
00161
00162
00163
00164 int mark_descendants_for_deletion();
00166 void remove_child(BCP_tm_node* node);
00168 inline void reserve_child_num(int num) { _children.reserve(num); }
00170 inline void new_child(BCP_tm_node* node) { _children.push_back(node); }
00172 };
00173
00174
00175
00178 class BCP_tree {
00179 private:
00181 BCP_vec<BCP_tm_node*> _tree;
00183 int maxdepth_;
00184 int processed_;
00185
00186 public:
00190 BCP_tree() : _tree(), maxdepth_(0), processed_(0) {}
00192 ~BCP_tree() {
00193 for (int i = _tree.size() - 1; i >= 0; --i) {
00194 delete _tree[i];
00195 }
00196 }
00202 inline BCP_vec<BCP_tm_node*>::iterator begin() { return _tree.begin(); }
00204 inline BCP_vec<BCP_tm_node*>::iterator end() { return _tree.end(); }
00205
00207 inline BCP_tm_node* root() { return _tree.front(); }
00209 inline BCP_tm_node* operator[](int index) { return _tree[index]; }
00211 inline size_t size() const { return _tree.size(); }
00213 inline int maxdepth() const { return maxdepth_; }
00215 inline int processed() const { return processed_; }
00216 inline void increase_processed() { ++processed_; }
00222 double true_lower_bound(const BCP_tm_node* node) const;
00224 void enumerate_leaves(BCP_tm_node* node, const double obj_limit);
00226 inline void insert(BCP_tm_node* node) {
00227 node->_index = _tree.size();
00228 _tree.push_back(node);
00229 if (node->getDepth() > maxdepth_)
00230 maxdepth_ = node->getDepth();
00231 }
00232 inline void remove(int index) {
00233 _tree[index] = 0;
00234 }
00236 };
00237
00238
00239 class BCP_tm_node_to_send;
00240
00241 class BCP_tm_node_to_send
00242 {
00243 public:
00244 static std::map<int, BCP_tm_node_to_send*> waiting;
00245
00246 private:
00247 BCP_tm_prob& p;
00248
00250 BCP_message_tag msgtag;
00251
00254 const int ID;
00255
00256 const BCP_tm_node* node;
00259 const BCP_tm_node** root_path;
00261 int* child_index;
00264 BCP_tm_node_data* node_data_on_root_path;
00265
00267 int level;
00268
00270 int explicit_core_level;
00271 int explicit_var_level;
00272 int explicit_cut_level;
00273 int explicit_ws_level;
00274 int explicit_all_level;
00275
00277 int missing_desc_num;
00279 int missing_var_num;
00281 int missing_cut_num;
00282
00286 BCP_obj_set_change var_set;
00287 BCP_obj_set_change cut_set;
00290 BCP_vec<Coin::SmartPtr<BCP_var> > vars;
00291 BCP_vec<Coin::SmartPtr<BCP_cut> > cuts;
00292
00293 public:
00294
00295 BCP_tm_node_to_send(BCP_tm_prob& p, const BCP_tm_node* node,
00296 const BCP_message_tag tag);
00297 ~BCP_tm_node_to_send();
00298
00301 bool send();
00302
00306 bool receive_node_desc(BCP_buffer& buf);
00310 bool receive_vars(BCP_buffer& buf);
00314 bool receive_cuts(BCP_buffer& buf);
00315 };
00316
00317 #endif