/home/coin/SVN-release/OS-2.4.1/Bcp/src/TM/BCP_tm_msg_node_send.cpp

Go to the documentation of this file.
00001 // Copyright (C) 2000, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 #include "CoinTime.hpp"
00004 #include "BCP_message.hpp"
00005 
00006 #include "BCP_enum_branch.hpp"
00007 #include "BCP_node_change.hpp"
00008 #include "BCP_warmstart.hpp"
00009 #include "BCP_var.hpp"
00010 #include "BCP_cut.hpp"
00011 
00012 #include "BCP_tm.hpp"
00013 #include "BCP_tm_user.hpp"
00014 #include "BCP_USER.hpp"
00015 #include "BCP_message_tag.hpp"
00016 
00017 //XXX
00018 #include "BCP_tm_functions.hpp"
00019 
00020 #ifndef BCP_DEBUG_PRINT
00021 #define BCP_DEBUG_PRINT 0
00022 #endif
00023 
00024 //#############################################################################
00025 
00026 std::map<int, BCP_tm_node_to_send*> BCP_tm_node_to_send::waiting;
00027 
00028 //#############################################################################
00029 
00030 BCP_tm_node_to_send::BCP_tm_node_to_send(BCP_tm_prob& prob,
00031                                          const BCP_tm_node* node_to_send,
00032                                          const BCP_message_tag tag) :
00033     p(prob),
00034     msgtag(tag),
00035     ID(node_to_send->_index),
00036     node(node_to_send),
00037     root_path(NULL),
00038     child_index(NULL),
00039     node_data_on_root_path(NULL),
00040     explicit_core_level(-1),
00041     explicit_var_level(-1),
00042     explicit_cut_level(-1),
00043     explicit_ws_level(-1),
00044     explicit_all_level(-1),
00045     missing_desc_num(-1),
00046     missing_var_num(-1),
00047     missing_cut_num(-1)
00048 {
00049     level = node->getDepth();
00050     const BCP_tm_node* n = node;
00051 
00052     root_path = new const BCP_tm_node*[level + 1];
00053     child_index = new int[level];;
00054     node_data_on_root_path = new BCP_tm_node_data[level+1];
00055     
00056     // the path to the root
00057     int i = level;
00058     while (explicit_core_level < 0 || explicit_var_level < 0 ||
00059            explicit_cut_level < 0 || explicit_ws_level < 0) {
00060         assert(i >= 0);
00061         root_path[i] = n;
00062         // some stuff is on other processes
00063         if (n->_locally_stored) {
00064             node_data_on_root_path[i] = n->_data;
00065         } else {
00066             node_data_on_root_path[i]._desc = NULL;
00067             node_data_on_root_path[i]._user = NULL;
00068         }
00069           
00070         if (n->_core_storage!=BCP_Storage_WrtParent && explicit_core_level<0) {
00071             explicit_core_level = i;
00072             explicit_all_level = i;
00073         }
00074         if (n->_var_storage!=BCP_Storage_WrtParent && explicit_var_level<0) {
00075             explicit_var_level = i;
00076             explicit_all_level = i;
00077         }
00078         if (n->_cut_storage!=BCP_Storage_WrtParent && explicit_cut_level<0) {
00079             explicit_cut_level = i;
00080             explicit_all_level = i;
00081         }
00082         if (n->_ws_storage!=BCP_Storage_WrtParent && explicit_ws_level<0) {
00083             explicit_ws_level = i;
00084             explicit_all_level = i;
00085         }
00086         --i;
00087         n = n->parent();
00088     }
00089     for (i = explicit_all_level + 1; i <= level; i++) {
00090         child_index[i-1] = root_path[i]->birth_index();
00091     }
00092     BCP_tm_node_to_send::waiting[ID] = this;
00093 }
00094 
00095 //#############################################################################
00096 
00097 BCP_tm_node_to_send::~BCP_tm_node_to_send()
00098 {
00099     delete[] root_path;
00100     delete[] child_index;
00101     delete[] node_data_on_root_path;
00102 }
00103 
00104 //#############################################################################
00105 
00106 bool
00107 BCP_tm_node_to_send::receive_node_desc(BCP_buffer& buf)
00108 {
00109     const bool def = p.param(BCP_tm_par::ReportWhenDefaultIsExecuted);
00110     int cnt, lclLevel, index;
00111     buf.unpack(cnt);
00112     missing_desc_num -= cnt;
00113     bool has_user_data = false;
00114     while (--cnt >= 0) {
00115         buf.unpack(lclLevel).unpack(index);
00116         assert(root_path[lclLevel]->_index == index);
00117         node_data_on_root_path[lclLevel]._desc =
00118             new BCP_node_change(p.packer, def, buf);
00119         buf.unpack(has_user_data);
00120         node_data_on_root_path[lclLevel]._user =
00121           has_user_data ? p.packer->unpack_user_data(buf) : 0;
00122     }
00123     assert(missing_desc_num >= 0);
00124     if (missing_desc_num == 0) {
00125         return send();
00126     }
00127     return false;
00128 }
00129 
00130 //#############################################################################
00131 
00132 bool
00133 BCP_tm_node_to_send::receive_vars(BCP_buffer& buf)
00134 {
00135     int cnt, pos, index;
00136     buf.unpack(cnt);
00137     missing_var_num -= cnt;
00138     while (--cnt >= 0) {
00139         buf.unpack(pos).unpack(index);
00140         vars[pos] = p.packer->unpack_var_algo(buf);
00141         assert(var_set._new_objs[pos] == vars[pos]->bcpind());
00142     }
00143     assert(missing_var_num >= 0);
00144     if (missing_var_num == 0 && missing_cut_num == 0) {
00145         return send();
00146     }
00147     return false;
00148 }
00149 
00150 //#############################################################################
00151 
00152 bool
00153 BCP_tm_node_to_send::receive_cuts(BCP_buffer& buf)
00154 {
00155     int cnt, pos, index;
00156     buf.unpack(cnt);
00157     missing_cut_num -= cnt;
00158     while (--cnt >= 0) {
00159         buf.unpack(pos).unpack(index);
00160         cuts[pos] = p.packer->unpack_cut_algo(buf);
00161         assert(cut_set._new_objs[pos] == cuts[pos]->bcpind());
00162     }
00163     assert(missing_cut_num >= 0);
00164     if (missing_var_num == 0 && missing_cut_num == 0) {
00165         return send();
00166     }
00167     return false;
00168 }
00169 
00170 //#############################################################################
00171 
00172 bool
00173 BCP_tm_node_to_send::send()
00174 {
00175     int i;
00176 
00177     if (missing_desc_num < 0) {
00178         missing_desc_num = 0;
00179         // collect what needs od be asked for
00180         std::map< int, BCP_vec<int> > tms_nodelevel;
00181         for (i = explicit_all_level; i <= level; i++) {
00182             if (node_data_on_root_path[i]._desc.IsNull()) {
00183                 tms_nodelevel[root_path[i]->_data_location].push_back(i);
00184                 ++missing_desc_num;
00185             }
00186         }
00187         BCP_buffer& buf = p.msg_buf;
00188         std::map< int, BCP_vec<int> >::const_iterator tms;
00189         BCP_vec<int> indices;
00190         for (tms = tms_nodelevel.begin(); tms != tms_nodelevel.end(); ++tms) {
00191             buf.clear();
00192             buf.pack(ID);
00193             const BCP_vec<int>& nodelevel = tms->second;
00194             indices.clear();
00195             const int size = nodelevel.size();
00196             indices.reserve(size);
00197             for (i = 0; i < size; ++i) {
00198                 indices.unchecked_push_back(root_path[nodelevel[i]]->_index);
00199             }
00200             buf.pack(nodelevel);
00201             buf.pack(indices);
00202             p.msg_env->send(tms->first, BCP_Msg_NodeListRequest, buf);
00203         }
00204     }
00205 
00206     if (missing_desc_num > 0) {
00207         return false;
00208     }
00209 
00210 #if 0
00211     // FIXME--DELETE (used to test Bonmin code)
00212     for (i = 0; i <= level; ++i) {
00213       assert(node_data_on_root_path[level]._desc.IsValid());
00214       assert(node_data_on_root_path[level]._user.IsValid());
00215     }
00216 #endif
00217 
00218     // OK, we have all the descriptions. Now if we haven't done so yet (which
00219     // is indicated by missing_var_num (and missing_cut_num) being negative)
00220     // we need to create the explicit parent description and the current node
00221     // description (vars/cuts will be present only with their bcpind). Also,
00222     // we need to create the full list of variables for the node itself (and
00223     // not for the parent).
00224     if (missing_var_num < 0) {
00225         missing_var_num = 0;
00226         missing_cut_num = 0;
00227         std::map< int, BCP_vec<int> > tms_pos;
00228         std::map< int, BCP_vec<int> >::const_iterator tms;
00229         std::map<int, int>::iterator remote;
00230         std::map<int, Coin::SmartPtr<BCP_var> >::iterator localvar;
00231         std::map<int, Coin::SmartPtr<BCP_cut> >::iterator localcut;
00232         BCP_buffer& buf = p.msg_buf;
00233         BCP_vec<int> indices;
00234 
00235         if (node->_var_storage == BCP_Storage_WrtParent) {
00236             for (i = explicit_var_level; i < level; ++i) {
00237                 var_set.update(node_data_on_root_path[i]._desc->var_change);
00238             }
00239             // FIXME: can it be BCP_Storage_NoData ???
00240             assert (var_set._storage == BCP_Storage_Explicit);
00241         }
00242         BCP_obj_set_change node_var_set = var_set;
00243         node_var_set.update(node_data_on_root_path[level]._desc->var_change);
00244         BCP_vec<int>& var_inds = node_var_set._new_objs;
00245         const int varnum = var_inds.size();
00246         vars.reserve(varnum);
00247         // check whether we have all the vars
00248         for (i = 0; i < varnum; ++i) {
00249             remote = p.vars_remote.find(var_inds[i]);
00250             if (remote != p.vars_remote.end()) {
00251                 tms_pos[remote->second].push_back(i);
00252                 vars.unchecked_push_back(NULL);
00253                 ++missing_var_num;
00254                 continue;
00255             }
00256             localvar = p.vars_local.find(var_inds[i]);
00257             if (localvar != p.vars_local.end()) {
00258                 // FIXME: cloning could be avoided by using smart pointers
00259                 vars.unchecked_push_back(localvar->second);
00260                 continue;
00261             }
00262             throw BCP_fatal_error("\
00263 TM: var in node description is neither local nor remote.\n");
00264         }
00265         for (tms = tms_pos.begin(); tms != tms_pos.end(); ++tms) {
00266             buf.clear();
00267             buf.pack(ID);
00268             const BCP_vec<int>& pos = tms->second;
00269             const int num = pos.size();
00270             indices.clear();
00271             indices.reserve(num);
00272             for (i = 0; i < num; ++i) {
00273                 indices.unchecked_push_back(var_inds[pos[i]]);
00274             }
00275             buf.pack(pos);
00276             buf.pack(indices);
00277             p.msg_env->send(tms->first, BCP_Msg_VarListRequest, buf);
00278         }
00279 
00280         if (node->_cut_storage == BCP_Storage_WrtParent) {
00281             for (i = explicit_cut_level; i < level; ++i) {
00282                 cut_set.update(node_data_on_root_path[i]._desc->cut_change);
00283             }
00284             // FIXME: can it be BCP_Storage_NoData ???
00285             assert (cut_set._storage == BCP_Storage_Explicit);
00286         }
00287         BCP_obj_set_change node_cut_set = cut_set;
00288         node_cut_set.update(node_data_on_root_path[level]._desc->cut_change);
00289         BCP_vec<int>& cut_inds = node_cut_set._new_objs;
00290         const int cutnum = cut_inds.size();
00291         cuts.reserve(cutnum);
00292         // check whether we have all the cuts
00293         tms_pos.clear();
00294         for (i = 0; i < cutnum; ++i) {
00295             remote =p.cuts_remote.find(cut_inds[i]);
00296             if (remote != p.cuts_remote.end()) {
00297                 tms_pos[remote->second].push_back(i);
00298                 cuts.unchecked_push_back(NULL);
00299                 ++missing_cut_num;
00300                 continue;
00301             }
00302             localcut = p.cuts_local.find(cut_inds[i]);
00303             if (localcut != p.cuts_local.end()) {
00304                 // FIXME: cloning could be avoided by using smart pointers
00305                 cuts.unchecked_push_back(localcut->second);
00306                 continue;
00307             }
00308             throw BCP_fatal_error("\
00309 TM: cut in node description is neither local nor remote.\n");
00310         }
00311         for (tms = tms_pos.begin(); tms != tms_pos.end(); ++tms) {
00312             buf.clear();
00313             buf.pack(ID);
00314             const BCP_vec<int>& pos = tms->second;
00315             const int num = pos.size();
00316             indices.clear();
00317             indices.reserve(num);
00318             for (i = 0; i < num; ++i) {
00319                 indices.unchecked_push_back(cut_inds[pos[i]]);
00320             }
00321             buf.pack(pos);
00322             buf.pack(indices);
00323             p.msg_env->send(tms->first, BCP_Msg_CutListRequest, buf);
00324         }
00325     }
00326 
00327     if (missing_var_num > 0 || missing_cut_num > 0) {
00328         return false;
00329     }
00330 
00331     //=========================================================================
00332     // Great! Now we have everything. Start to pack it up.
00333     const bool def = p.param(BCP_tm_par::ReportWhenDefaultIsExecuted);
00334     // The user will override at most one...
00335     p.user->display_node_information(p.search_tree, *node);
00336     p.user->display_node_information(p.search_tree, *node,
00337                                      false /*before processing*/);
00338 
00339     BCP_diving_status dive =
00340         (rand() < p.param(BCP_tm_par::UnconditionalDiveProbability)*RAND_MAX) ?
00341         BCP_DoDive : BCP_TestBeforeDive;
00342 
00343     // start with book-keeping data
00344     BCP_buffer& buf = p.msg_buf;
00345     buf.clear();
00346     buf.pack(p.current_phase_colgen).pack(node->index()).pack(level).
00347         pack(node->getQuality()).pack(node->getTrueLB()).pack(dive);
00348 
00349     // pack the process information
00350     buf.pack(node->cg).pack(node->cp).pack(node->vg).pack(node->vp);
00351 
00352     // pack how things are stored in node. this will influence what do we pack
00353     // in the parent, too.
00354     buf.pack(node->_core_storage).
00355         pack(node->_var_storage).
00356         pack(node->_cut_storage).
00357         pack(node->_ws_storage);
00358     
00359     // Now pack the parent if there's one
00360     if (level > 0) {
00361         p.msg_buf.pack(node->parent()->index());
00362         // start with the core
00363         if (node->_core_storage == BCP_Storage_WrtParent) {
00364             BCP_problem_core_change core;
00365             for (i = explicit_core_level; i < level; ++i) {
00366                 core.update(*p.core_as_change,
00367                             node_data_on_root_path[i]._desc->core_change);
00368             }
00369             core.make_wrtcore_if_shorter(*p.core_as_change);
00370             core.pack(p.msg_buf);
00371         }
00372 
00373         // next the variabless
00374         if (node->_var_storage == BCP_Storage_WrtParent) {
00375             var_set.pack(buf);
00376         }
00377 
00378         // now the cuts
00379         if (node->_cut_storage == BCP_Storage_WrtParent) {
00380             cut_set.pack(buf);
00381         }
00382 
00383         // finally warmstart
00384         if (node->_ws_storage == BCP_Storage_WrtParent) {
00385             BCP_warmstart* warmstart =
00386                 node_data_on_root_path[explicit_ws_level]._desc->warmstart->clone();
00387             for (i = explicit_ws_level + 1; i < level; ++i) {
00388                 warmstart->update(node_data_on_root_path[i]._desc->warmstart);
00389             }
00390             p.packer->pack_warmstart(warmstart, p.msg_buf, def);
00391             delete warmstart;
00392         }
00393     }
00394 
00395     // finally pack the changes in this node
00396     node_data_on_root_path[level]._desc->pack(p.packer, def, buf);
00397     
00398     // Now pack the full list of vars/cuts of the node
00399     int cnt = vars.size();
00400     buf.pack(cnt);
00401     for (i = 0; i < cnt; ++i) {
00402         p.pack_var(*vars[i]);
00403     }
00404     cnt = cuts.size();
00405     buf.pack(cnt);
00406     for (i = 0; i < cnt; ++i) {
00407         p.pack_cut(*cuts[i]);
00408     }
00409 
00410     const BCP_user_data* ud = node_data_on_root_path[level]._user.GetRawPtr();
00411     bool has_user_data = ud != 0;
00412     buf.pack(has_user_data);
00413     if (has_user_data) {
00414         p.packer->pack_user_data(ud, buf);
00415     }
00416 
00417 #if (BCP_DEBUG_PRINT != 0)
00418     //    const char* compName = p.candidate_list.getTree()->compName();
00419     printf("TM %.3lf: Sending to proc %i  node: %i  quality: %lf  pref: %s\n",
00420            CoinWallclockTime()-p.start_time,
00421            node->lp, node->_index, node->getQuality(), 
00422            node->getPreferred().str().c_str());
00423 
00424 #endif
00425 
00426     p.msg_env->send(node->lp, msgtag, buf);
00427     if (node->_index == 0) {
00428       p.root_node_sent_ = CoinGetTimeOfDay();
00429     }
00430 
00431 #ifdef BCP__DUMP_PROCINFO
00432 #if (BCP__DUMP_PROCINFO == 1)
00433     dump_procinfo(p, "BCP_tm_send_node()");
00434 #endif
00435 #endif
00436     return true;
00437 }

Generated on Thu Nov 10 03:05:39 2011 by  doxygen 1.4.7