/home/coin/SVN-release/Bcp-1.2.1/Bcp/src/include/BCP_tm_node.hpp

Go to the documentation of this file.
00001 // Copyright (C) 2000, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 #ifndef _BCP_TM_NODE
00004 #define _BCP_TM_NODE
00005 
00006 //#include <cfloat>
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     // NOTE: deleting a tree_node deletes the whole subtree below!
00071 public:
00073     static int num_local_nodes;
00074     static int num_remote_nodes;
00075     // *FIXME* break into groups 
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     // Exactly one of the next two is always irrelevant */
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 //     BCP_tm_node(int level, BCP_node_change* desc,
00119 //              BCP_tm_node* parent, int index);
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     //    inline BCP_user_data* user_data() { return _data._user; }
00143     inline BCP_tm_node* child(int ind) { return _children[ind]; }
00145     inline BCP_tm_node* parent() { return _parent; }
00146 
00148     //    inline const BCP_user_data* user_data() const { return _data._user; }
00150     inline const BCP_tm_node* child(int ind) const { return _children[ind]; }
00152     inline const BCP_tm_node* parent() const { return _parent; }
00159     // Marking the descendants for deletion means that their _index fields are
00160     // set to -1. The reason is that some book-keeping must be one with the CP,
00161     // VP processes; with the next phase list, with the priority queue of the
00162     // current phase (and maybe sthing else?). So this function only marks, and
00163     // the data will be deleted later.
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

Generated on Thu Jan 15 03:00:59 2009 for coin-Bcp by  doxygen 1.4.7