/home/coin/SVN-release/Bcp-1.2.1/Bcp/src/include/BCP_tm.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_H
00004 #define _BCP_TM_H
00005 
00006 #include <queue>
00007 #include <map>
00008 
00009 #include "CoinSearchTree.hpp"
00010 #include "CoinSmartPtr.hpp"
00011 
00012 #include "BCP_math.hpp"
00013 #include "BCP_buffer.hpp"
00014 #include "BCP_enum.hpp"
00015 #include "BCP_enum_process_t.hpp"
00016 #include "BCP_tm_node.hpp"
00017 
00018 #include "BCP_tm_param.hpp"
00019 #include "BCP_lp_param.hpp"
00020 #include "BCP_cg_param.hpp"
00021 #include "BCP_vg_param.hpp"
00022 //#include "BCP_cp_param.hpp"
00023 //#include "BCP_vp_param.hpp"
00024 #include "BCP_parameters.hpp"
00025 #include "BCP_tmstorage.hpp"
00026 
00027 #include "BCP_buffer.hpp"
00028 #include "BCP_message.hpp"
00029 #include "BCP_process.hpp"
00030 
00031 #include "BCP_var.hpp"
00032 #include "BCP_cut.hpp"
00033 
00034 //#############################################################################
00035 class BCP_warmstart;
00036 class BCP_solution;
00037 
00038 class BCP_tm_user;
00039 class BCP_user_pack;
00040 
00041 //class BCP_var;
00042 //class BCP_cut;
00043 
00044 class BCP_obj_set_change;
00045 
00046 class BCP_problem_core;
00047 class BCP_problem_core_change;
00048 
00049 class BCP_lp_statistics;
00050 
00051 //#############################################################################
00052 
00053 #define BCP_ONLY_LP_PROCESS_HANDLING_WORKS
00054 
00057 struct BCP_slave_params {
00059   BCP_parameter_set<BCP_ts_par> ts;
00061   BCP_parameter_set<BCP_lp_par> lp;
00062   //   BCP_parameter_set<BCP_cp_par> cp;
00063   //   BCP_parameter_set<BCP_vp_par> vp;
00065   BCP_parameter_set<BCP_cg_par> cg;
00067   BCP_parameter_set<BCP_vg_par> vg;
00068 };
00069 
00070 //-----------------------------------------------------------------------------
00071 
00074 struct BCP_tm_flags {
00078   bool root_pricing_unpacked; // set if the result of root pricing is already
00079   // unpacked. important in a single process
00080   // environment, so we don't unpack things twice
00081 };
00082 
00083 //-----------------------------------------------------------------------------
00084 
00085 class BCP_tm_stat {
00086 private:
00087   int num_lp;
00088   // An array whose i-th entry indicates what was the totel wait time when
00089   // exactly i LP processes were working
00090   double* wait_time;
00091   // An array whose i-th entry indicates what was the totel queue length when
00092   // exactly i LP processes were working
00093   double* sumQueueLength;
00094   // An array whose i-th entry indicates how many times we have sampled the
00095   // queue length when exactly i LP processes were working
00096   int* numQueueLength;
00097   int cnt; // how many times we have printed stats
00098 public:
00099   BCP_tm_stat() :
00100       num_lp(0),
00101       wait_time(NULL),
00102       sumQueueLength(NULL),
00103       numQueueLength(NULL),
00104       cnt(0) {}
00105   ~BCP_tm_stat() {
00106     delete[] wait_time;
00107     delete[] sumQueueLength;
00108     delete[] numQueueLength;
00109   }
00110   void set_num_lp(int num) {
00111     delete[] wait_time;
00112     delete[] sumQueueLength;
00113     delete[] numQueueLength;
00114     num_lp = num;
00115     wait_time = new double[num+1];
00116     sumQueueLength = new double[num+1];
00117     numQueueLength = new int[num+1];
00118     for (int i = 0; i <= num_lp; ++i) {
00119       wait_time[i] = 0;
00120       sumQueueLength[i] = 0;
00121       numQueueLength[i] = 0;
00122     }
00123   }
00124   void update_wait_time(int i, double t) { wait_time[i] += t; }
00125   void update_queue_length(int i, int len) {
00126     sumQueueLength[i] += len;
00127     ++numQueueLength[i];
00128   }
00129   void print(bool final, double t);
00130 };
00131 
00132 //-----------------------------------------------------------------------------
00133 
00136 class BCP_tm_prob : public BCP_process {
00137 private:
00141   BCP_tm_prob(const BCP_tm_prob&);
00143   BCP_tm_prob& operator=(const BCP_tm_prob&);
00146   //-------------------------------------------------------------------------
00147 public: // Data members
00151   BCP_tm_user* user;
00153   BCP_user_pack* packer;
00154 
00156   BCP_message_environment* msg_env;
00160   BCP_lp_statistics* lp_stat;
00161 
00163   BCP_solution* feas_sol;
00164 
00168   BCP_parameter_set<BCP_tm_par> par;
00170   BCP_slave_params slave_pars;
00175   // flags to signal various things
00177   BCP_tm_flags flags;
00183   BCP_buffer msg_buf;
00185   std::vector<int> ts_procs;
00186   std::vector<int> lp_procs;
00188   BCP_scheduler lp_scheduler;
00191   double root_node_sent_;
00192   double root_node_received_;
00195   //-------------------------------------------------------------------------
00197   double upper_bound;
00199   double start_time;
00200   //-------------------------------------------------------------------------
00204   BCP_problem_core* core;
00206   BCP_problem_core_change* core_as_change;
00210   int phase;
00212   BCP_column_generation current_phase_colgen;
00213 
00214   // *FIXME*: maybe hash_map better for the next four?
00216   std::map<int, Coin::SmartPtr<BCP_var> > vars_local; 
00218   std::map<int, int>      vars_remote;
00220   std::map<int, Coin::SmartPtr<BCP_cut> > cuts_local;
00222   std::map<int, int>      cuts_remote;
00223 
00225   int next_cut_index_set_start;
00227   int next_var_index_set_start;
00228 
00229   //-------------------------------------------------------------------------
00230   bool need_a_TS;
00231   std::map<int, int> ts_space;
00232   
00233   //-------------------------------------------------------------------------
00235   BCP_tree search_tree;
00237   std::map<int, BCP_tm_node*> active_nodes;
00239   CoinSearchTreeManager candidate_list;
00240 
00242   std::map<int, BCP_tm_node_to_send*> nodes_to_send;
00243     
00244   // BCP_node_queue candidates;
00246   BCP_vec<BCP_tm_node*> next_phase_nodes;
00248   BCP_vec<BCP_tm_node*> nodes_to_free;
00249 
00250   //-------------------------------------------------------------------------
00255   BCP_vec< std::pair<int, int> > leaves_per_cp;
00257   BCP_vec< std::pair<int, int> > leaves_per_vp;
00260   //-------------------------------------------------------------------------
00261   BCP_tm_stat stat;
00262 
00263 public:
00267   BCP_tm_prob();
00269   virtual ~BCP_tm_prob();
00272 public:
00276   void pack_var(const BCP_var& var);
00278   BCP_var* unpack_var_without_bcpind(BCP_buffer& buf);
00280   int unpack_var();
00282   void pack_cut(const BCP_cut& cut);
00284   BCP_cut* unpack_cut_without_bcpind(BCP_buffer& buf);
00286   int unpack_cut();
00288   //-------------------------------------------------------------------------
00289 
00293   inline char
00294   param(BCP_tm_par::chr_params key) const        { return par.entry(key); }
00296   inline int
00297   param(BCP_tm_par::int_params key) const        { return par.entry(key); }
00299   inline double
00300   param(BCP_tm_par::dbl_params key) const        { return par.entry(key); }
00302   inline const BCP_string&
00303   param(BCP_tm_par::str_params key) const        { return par.entry(key); }
00305   inline const BCP_vec<BCP_string>&
00306   param(BCP_tm_par::str_array_params key) const  { return par.entry(key); }
00307 
00309   inline double granularity() const {
00310     return param(BCP_tm_par::Granularity);
00311   }
00312 
00313   //-------------------------------------------------------------------------
00315   inline bool has_ub() const { return upper_bound < BCP_DBL_MAX / 10; }
00317   inline double ub() const { return upper_bound; }
00319   inline bool ub(double new_ub) {
00320     if (new_ub < upper_bound){
00321       upper_bound = new_ub;
00322       return true;
00323     }
00324     return false;
00325   }
00327   inline bool over_ub(const double lb) const {
00328     return lb > upper_bound - param(BCP_tm_par::Granularity);
00329   }
00331   //-------------------------------------------------------------------------
00332   virtual BCP_buffer& get_message_buffer() { return msg_buf; }
00333   virtual void process_message();
00334 };
00335 
00336 //#############################################################################
00337 
00338 #endif
00339 

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