00001
00002
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
00023
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
00042
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
00063
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;
00079
00080
00081 };
00082
00083
00084
00085 class BCP_tm_stat {
00086 private:
00087 int num_lp;
00088
00089
00090 double* wait_time;
00091
00092
00093 double* sumQueueLength;
00094
00095
00096 int* numQueueLength;
00097 int cnt;
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:
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
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
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
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