00001
00002
00003 #ifndef _BCP_TM_NODE
00004 #define _BCP_TM_NODE
00005
00006
00007
00008 #include "BCP_math.hpp"
00009 #include "BCP_vector.hpp"
00010
00011
00014 enum BCP_tm_node_status{
00016 BCP_DefaultNode,
00018 BCP_ProcessedNode,
00020 BCP_ActiveNode,
00022 BCP_PrunedNode_OverUB,
00024 BCP_PrunedNode_Infeas,
00026 BCP_PrunedNode_Discarded,
00028 BCP_CandidateNode,
00030 BCP_NextPhaseNode_OverUB,
00032 BCP_NextPhaseNode_Infeas
00033 };
00034
00035
00036
00037 class BCP_proc_id;
00038 class BCP_node_change;
00039 class BCP_user_data;
00040
00041 class BCP_tm_node;
00042 class BCP_tm_prob;
00043
00044
00045
00048 class BCP_tm_node {
00049 private:
00053 BCP_tm_node(const BCP_tm_node&);
00055 BCP_tm_node& operator=(const BCP_tm_node&);
00058
00059 public:
00061
00064 BCP_tm_node_status status;
00066 int _index;
00068 int _level;
00070 double _quality;
00072 double _true_lower_bound;
00074 BCP_node_change* _desc;
00076 BCP_tm_node* _parent;
00078 BCP_user_data* _user_data;
00080 int _birth_index;
00082 BCP_vec<BCP_tm_node*> _children;
00084 BCP_proc_id* lp;
00086 BCP_proc_id* cg;
00088 BCP_proc_id* cp;
00090 BCP_proc_id* vg;
00092 BCP_proc_id* vp;
00094 int _processed_leaf_num;
00096 int _pruned_leaf_num;
00098 int _tobepriced_leaf_num;
00100 int _leaf_num;
00103 public:
00107 BCP_tm_node(int level, BCP_node_change* desc) :
00108 status(BCP_DefaultNode),
00109 _index(0),
00110 _level(level),
00111 _quality(-BCP_DBL_MAX),
00112 _true_lower_bound(-BCP_DBL_MAX),
00113 _desc(desc),
00114 _parent(0),
00115 _user_data(0),
00116 _birth_index(-1),
00117 _children(),
00118 lp(0), cg(0), cp(0), vg(0), vp(0),
00119 _processed_leaf_num(0),
00120 _pruned_leaf_num(0),
00121 _tobepriced_leaf_num(0),
00122 _leaf_num(0)
00123 {}
00124
00126 BCP_tm_node(int level, BCP_node_change* desc,
00127 BCP_tm_node* parent, int index) :
00128 status(BCP_DefaultNode),
00129 _index(0),
00130 _level(level),
00131 _quality(-BCP_DBL_MAX),
00132 _true_lower_bound(-BCP_DBL_MAX),
00133 _desc(desc),
00134 _parent(0),
00135 _user_data(0),
00136 _birth_index(-1),
00137 _children(),
00138 lp(0), cg(0), cp(0), vg(0), vp(0),
00139 _processed_leaf_num(0),
00140 _pruned_leaf_num(0),
00141 _tobepriced_leaf_num(0),
00142 _leaf_num(0)
00143 {}
00144
00146 ~BCP_tm_node();
00152 inline int index() const { return _index; }
00154 inline int level() const { return _level; }
00156 inline int child_num() const { return _children.size(); }
00158 inline double quality() const { return _quality; }
00160 inline double true_lower_bound() const { return _true_lower_bound; }
00162 inline int birth_index() const { return _birth_index; }
00163
00165 inline BCP_user_data* user_data() { return _user_data; }
00167 inline BCP_tm_node* child(int ind) { return _children[ind]; }
00169 inline BCP_tm_node* parent() { return _parent; }
00170
00172 inline const BCP_user_data* user_data() const { return _user_data; }
00174 inline const BCP_tm_node* child(int ind) const { return _children[ind]; }
00176 inline const BCP_tm_node* parent() const { return _parent; }
00183
00184
00185
00186
00187
00188 int mark_descendants_for_deletion();
00190 void remove_child(BCP_tm_node* node);
00192 inline void reserve_child_num(int num) { _children.reserve(num); }
00194 inline void new_child(BCP_tm_node* node) { _children.push_back(node); }
00196 };
00197
00198
00199
00202 class BCP_tree {
00203 private:
00205 BCP_vec<BCP_tm_node*> _tree;
00207 int maxdepth_;
00208 int processed_;
00209
00210 public:
00214 BCP_tree() : _tree(), maxdepth_(0), processed_(0) {}
00216 ~BCP_tree() {
00217 for (int i = _tree.size() - 1; i >= 0; --i) {
00218 delete _tree[i];
00219 }
00220 }
00226 inline BCP_vec<BCP_tm_node*>::iterator begin() { return _tree.begin(); }
00228 inline BCP_vec<BCP_tm_node*>::iterator end() { return _tree.end(); }
00229
00231 inline BCP_tm_node* root() { return _tree.front(); }
00233 inline BCP_tm_node* operator[](int index) { return _tree[index]; }
00235 inline size_t size() const { return _tree.size(); }
00237 inline int maxdepth() const { return maxdepth_; }
00239 inline int processed() const { return processed_; }
00240 inline void increase_processed() { ++processed_; }
00246 double true_lower_bound(const BCP_tm_node* node) const;
00248 void enumerate_leaves(BCP_tm_node* node, const double obj_limit);
00250 inline void insert(BCP_tm_node* node) {
00251 node->_index = _tree.size();
00252 _tree.push_back(node);
00253 if (node->_level > maxdepth_)
00254 maxdepth_ = node->_level;
00255 }
00256 inline void remove(int index) {
00257 _tree[index] = 0;
00258 }
00260 };
00261
00262
00263
00264 class BCP_node_queue {
00265 private:
00266 BCP_node_queue();
00267 BCP_node_queue(const BCP_node_queue&);
00268 BCP_node_queue& operator=(const BCP_node_queue&);
00269
00270 private:
00275 BCP_tm_prob& _p;
00280 BCP_vec<BCP_tm_node*> _pq;
00283 public:
00287 BCP_node_queue(BCP_tm_prob& p) : _p(p), _pq() { _pq.push_back(NULL); }
00289 ~BCP_node_queue() {}
00293 inline bool empty() const { return _pq.size() == 1; }
00294
00296 BCP_tm_node* top() const { return _pq[1]; }
00297
00299 void pop();
00300
00302 void insert(BCP_tm_node* node);
00303
00306 void compare_to_UB(int& quality_above_UB, int& quality_below_UB);
00307 };
00308
00309
00310
00311 #endif