/home/coin/SVN-release/OS-2.0.1/Bcp/src/TM/BCP_tm_msg_node_rec.cpp

Go to the documentation of this file.
00001 // Copyright (C) 2000, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 #include <cstdlib>
00004 #include <algorithm>
00005 
00006 #include "CoinTime.hpp"
00007 
00008 #include "BCP_os.hpp"
00009 #include "BCP_USER.hpp"
00010 #include "BCP_node_change.hpp"
00011 #include "BCP_warmstart.hpp"
00012 #include "BCP_branch.hpp"
00013 #include "BCP_enum_branch.hpp"
00014 #include "BCP_message.hpp"
00015 #include "BCP_vector.hpp"
00016 #include "BCP_tm.hpp"
00017 #include "BCP_tm_user.hpp"
00018 #include "BCP_tm_functions.hpp"
00019 
00020 #ifndef BCP_DEBUG_PRINT
00021 #define BCP_DEBUG_PRINT 0
00022 #endif
00023 
00024 static int
00025 BCP_tm_unpack_node_description(BCP_tm_prob& p, BCP_buffer& buf);
00026 static void
00027 BCP_tm_create_core_change(BCP_node_change* desc,
00028                           const int bvarnum, const int bcutnum,
00029                           const BCP_internal_brobj* brobj, const int childind);
00030 static void
00031 BCP_tm_create_var_change(BCP_node_change* desc,
00032                          const BCP_node_change* parentdesc, const int bvarnum,
00033                          const BCP_internal_brobj* brobj, const int childind);
00034 static void
00035 BCP_tm_create_cut_change(BCP_node_change* desc,
00036                          const BCP_node_change* parentdesc, const int bcutnum,
00037                          const BCP_internal_brobj* brobj, const int childind);
00038 static void
00039 BCP_tm_unpack_branching_info(BCP_tm_prob& p, BCP_buffer& buf,
00040                              BCP_tm_node* node);
00041 static inline BCP_diving_status
00042 BCP_tm_shall_we_dive(BCP_tm_prob& p, const double quality);
00043 
00044 //#############################################################################
00045 
00046 static void
00047 BCP_tm_print_info_line(BCP_tm_prob& p, BCP_tm_node& node)
00048 {
00049     const int freq = p.param(BCP_tm_par::TmVerb_SingleLineInfoFrequency);
00050     if (freq == 0)
00051         return;
00052 
00053     static int lines = 0;
00054 
00055     if ((lines % 41) == 0) {
00056         ++lines;
00057         printf("\n");
00058         printf("BCP: ");
00059         printf(" Nodes  ");
00060         printf(" Proc'd ");
00061         printf("  BestUB   ");
00062         printf(" LowestQ   ");
00063         /*
00064         printf("AboveUB ");
00065         printf("BelowUB ");
00066         */
00067         printf("\n");
00068     }
00069     const int processed = p.search_tree.processed();
00070     if ((processed % freq) == 0 || processed == 1) {
00071         ++lines;
00072         printf("BCP: ");                                           // 5
00073         printf("%7i ", (int)p.search_tree.size());                 // 8
00074         printf("%7i ", processed);                                 // 8
00075         printf("%10g ", p.ub());                                   // 11
00076         if (p.candidate_list.empty()) {
00077             printf("%10g ", 0.0);                                  // 11
00078         } else {
00079             printf("%10g ", p.candidate_list.bestQuality());       // 11
00080         }
00081         /*
00082         int quality_above_UB;
00083         int quality_below_UB;
00084         p.candidates.compare_to_UB(quality_above_UB, quality_below_UB);
00085         printf("%7i ", quality_above_UB);                          // 8
00086         printf("%7i ", quality_below_UB);                          // 8
00087         */
00088         printf("\n");
00089     }
00090 }
00091 
00092 //#############################################################################
00093 
00094 void BCP_print_memusage(BCP_tm_prob& p)
00095 {
00096 #if 0
00097     static int cnt = 0;
00098     ++cnt;
00099     if ((cnt % 100) == 0) {
00100         long usedheap = BCP_used_heap();
00101         if (usedheap > 0) {
00102             printf("    mallinfo used: %li\n", usedheap);
00103         }
00104     }
00105 #endif
00106 }
00107 
00108 //#############################################################################
00109 
00110 static int
00111 BCP_tm_unpack_node_description(BCP_tm_prob& p, BCP_buffer& buf)
00112 {
00113     // the first thing is the index of the node
00114     int index;
00115     buf.unpack(index);
00116     // get a pointer to this node
00117     BCP_tm_node* node = p.search_tree[index];
00118     p.search_tree.increase_processed();
00119 TMDBG;
00120 
00121     // XXX
00122     const int lp_id = node->lp;
00123     if (node != p.active_nodes[lp_id]) {
00124         throw BCP_fatal_error("\
00125 BCP_tm_unpack_node_description: received node is different from processed.\n");
00126     }
00127 
00128     // get the quality and new lb for this node
00129     double q, tlb;
00130 TMDBG;
00131     buf.unpack(q).unpack(tlb);
00132     node->setQuality(q);
00133     node->setTrueLB(tlb);
00134 TMDBG;
00135 
00136     // wipe out any previous description of this node and create a new one if
00137     // the description is sent over
00138     if (node->_locally_stored) {
00139         node->_data._desc = NULL;
00140         node->_data._user = NULL;
00141     } else {
00142         BCP_buffer b;
00143 TMDBG;
00144         BCP_vec<int> indices(1, index);
00145         b.pack(indices);
00146         p.msg_env->send(node->_data_location, BCP_Msg_NodeListDelete, b);
00147         --BCP_tm_node::num_remote_nodes;
00148         ++BCP_tm_node::num_local_nodes;
00149 TMDBG;
00150         node->_locally_stored = true;
00151     }
00152 
00153     bool desc_sent = false;
00154     buf.unpack(desc_sent);
00155 
00156 TMDBG;
00157     if (desc_sent) {
00158         BCP_node_change* desc = new BCP_node_change;
00159 
00160         // unpack core_change
00161         if (p.core->varnum() + p.core->cutnum() > 0)
00162             desc->core_change.unpack(buf);
00163 
00164         int cnt;
00165         // get the variables. first unpack the new vars. those with negative
00166         // bcpind has not yet been sent to the TM from this LP process, but
00167         // they may have been sent here by another (if CP is used). those with
00168         // positive bcpind have already been sent to the TM, receiving such
00169         // var again is an error.
00170         buf.unpack(cnt);
00171         while (--cnt >= 0) {
00172             p.unpack_var();
00173         }
00174         // Now unpack the change data.
00175 TMDBG;
00176         desc->var_change.unpack(buf);
00177 
00178         // same for cuts
00179         buf.unpack(cnt);
00180         while (--cnt >= 0) {
00181             p.unpack_cut();
00182         }
00183 TMDBG;
00184         desc->cut_change.unpack(buf);
00185             
00186         // warmstart info
00187         bool has_data;
00188 TMDBG;
00189         switch (p.param(BCP_tm_par::WarmstartInfo)) {
00190         case BCP_WarmstartNone:
00191           break;
00192         case BCP_WarmstartRoot:
00193           // nothing needs to be done even in this case as the WS has been
00194           // sent in a separate message
00195           break;
00196         case BCP_WarmstartParent:
00197           buf.unpack(has_data);
00198           if (has_data) {
00199             const bool def = p.param(BCP_tm_par::ReportWhenDefaultIsExecuted);
00200             desc->warmstart = p.packer->unpack_warmstart(buf, def);
00201           }
00202           break;
00203         }
00204 TMDBG;
00205         // user data
00206         buf.unpack(has_data);
00207 TMDBG;
00208         BCP_user_data* udata = has_data ? p.packer->unpack_user_data(buf) : 0;
00209 
00210         node->_data._desc = desc;
00211         node->_data._user = udata;
00212         node->_core_storage = desc->core_change.storage();
00213         node->_var_storage = desc->var_change.storage();
00214         node->_cut_storage = desc->cut_change.storage();
00215         node->_ws_storage =
00216             desc->warmstart ? desc->warmstart->storage() : BCP_Storage_NoData;
00217 TMDBG;
00218     } else {
00219         node->_core_storage = BCP_Storage_NoData;
00220         node->_var_storage = BCP_Storage_NoData;
00221         node->_cut_storage = BCP_Storage_NoData;
00222         node->_ws_storage = BCP_Storage_NoData;
00223     }
00224 
00225     p.active_nodes.erase(lp_id);
00226 TMDBG;
00227 
00228     return index;
00229 }
00230 
00231 //#############################################################################
00232 
00233 static inline BCP_diving_status
00234 BCP_tm_shall_we_dive(BCP_tm_prob& p, const double quality)
00235 {
00236     if (rand() < p.param(BCP_tm_par::UnconditionalDiveProbability) * RAND_MAX)
00237         return BCP_DoDive;
00238 
00239     const double ratio = p.has_ub() ?
00240         p.param(BCP_tm_par::QualityRatioToAllowDiving_HasUB) :
00241         p.param(BCP_tm_par::QualityRatioToAllowDiving_NoUB);
00242 
00243     if (ratio < 0)
00244         return BCP_DoNotDive;
00245 
00246     if (p.candidate_list.empty())
00247         return BCP_TestBeforeDive;
00248 
00249     const double topq = p.candidate_list.bestQuality();
00250 
00251     if (quality <= topq)
00252         return BCP_TestBeforeDive;
00253 
00254     if (topq > 0.05) {
00255         return (quality / topq < ratio) ? BCP_TestBeforeDive : BCP_DoNotDive;
00256     }
00257     if (topq >= -0.05) {
00258         return (quality < ratio) ? BCP_TestBeforeDive : BCP_DoNotDive;
00259     }
00260     /* must be topq < -0.05 */
00261     return (quality < 0 && topq / quality < ratio) ?
00262             BCP_TestBeforeDive : BCP_DoNotDive;
00263 }
00264 
00265 //#############################################################################
00266 
00267 static void
00268 BCP_tm_create_core_change(BCP_node_change* desc,
00269                           const int bvarnum, const int bcutnum,
00270                           const BCP_internal_brobj* brobj, const int childind)
00271 {
00272     if (bvarnum + bcutnum == 0) {
00273         desc->core_change._storage = BCP_Storage_NoData;
00274         return;
00275     }
00276 
00277     desc->core_change._storage = BCP_Storage_WrtParent;
00278     if (bvarnum > 0 && brobj->affected_varnum() > 0) {
00279         // First count how many of them are affecting core vars
00280         int affected_core = 0;
00281         BCP_vec<int>::const_iterator posi = brobj->var_positions().begin();
00282         BCP_vec<int>::const_iterator lastposi = brobj->var_positions().end();
00283         while (posi != lastposi) {
00284             if (*posi < bvarnum)
00285                 ++affected_core;
00286             ++posi;
00287         }
00288       
00289         if (affected_core > 0) {
00290             BCP_vec<int>& var_pos = desc->core_change.var_pos;
00291             BCP_vec<BCP_obj_change>& var_ch = desc->core_change.var_ch;
00292             var_pos.reserve(affected_core);
00293             var_ch.reserve(affected_core);
00294             posi = brobj->var_positions().begin();
00295             BCP_vec<double>::const_iterator boundsi =
00296                 brobj->var_bounds_child(childind);
00297             while (posi != lastposi) {
00298                 if (*posi < bvarnum) {
00299                     var_pos.unchecked_push_back(*posi);
00300                     const double lb = *boundsi;
00301                     const double ub = *(boundsi+1);
00302                     var_ch.unchecked_push_back(BCP_obj_change(lb, ub,
00303                                                               BCP_ObjNotRemovable));
00304                 }
00305                 ++posi;
00306                 boundsi += 2;
00307             }
00308         }
00309     }
00310 
00311     if (bcutnum > 0 && brobj->affected_cutnum() > 0) {
00312         // First count how many of them are affecting core cuts
00313         int affected_core = 0;
00314         BCP_vec<int>::const_iterator posi = brobj->cut_positions().begin();
00315         BCP_vec<int>::const_iterator lastposi = brobj->cut_positions().end();
00316         while (posi != lastposi) {
00317             if (*posi < bcutnum)
00318                 ++affected_core;
00319             ++posi;
00320         }
00321 
00322         if (affected_core > 0) {
00323             BCP_vec<int>& cut_pos = desc->core_change.cut_pos;
00324             BCP_vec<BCP_obj_change>& cut_ch = desc->core_change.cut_ch;
00325             cut_pos.reserve(affected_core);
00326             cut_ch.reserve(affected_core);
00327             posi = brobj->cut_positions().begin();
00328             BCP_vec<double>::const_iterator boundsi =
00329                 brobj->cut_bounds_child(childind);
00330             while (posi != lastposi) {
00331                 if (*posi < bcutnum) {
00332                     cut_pos.unchecked_push_back(*posi);
00333                     const double lb = *boundsi;
00334                     const double ub = *(boundsi+1);
00335                     cut_ch.unchecked_push_back(BCP_obj_change(lb, ub,
00336                                                               BCP_ObjNotRemovable));
00337                 }
00338                 ++posi;
00339                 boundsi += 2;
00340             }
00341         }
00342     }
00343 }
00344 
00345 //#############################################################################
00346 
00347 static void
00348 BCP_tm_create_var_change(BCP_node_change* desc,
00349                          const BCP_node_change* parentdesc, const int bvarnum,
00350                          const BCP_internal_brobj* brobj, const int childind)
00351 {
00352     // check first how many added var has changed in brobj
00353     int affected_added = 0;
00354     BCP_vec<int>::const_iterator posi = brobj->var_positions().begin();
00355     BCP_vec<int>::const_iterator lastposi = brobj->var_positions().end();
00356     while (posi != lastposi) {
00357         if (*posi >= bvarnum)
00358             ++affected_added;
00359         ++posi;
00360     }
00361 
00362     if (affected_added == 0) {
00363         if (parentdesc->var_change.storage() == BCP_Storage_Explicit &&
00364             parentdesc->var_change.added_num() == 0) {
00365             desc->var_change._storage = BCP_Storage_Explicit;
00366         } else {
00367             desc->var_change._storage = BCP_Storage_WrtParent;
00368         }
00369         return;
00370     }
00371 
00372     desc->var_change._storage = BCP_Storage_WrtParent;
00373     BCP_vec<int>& dc_pos = desc->var_change._del_change_pos;
00374     BCP_vec<BCP_obj_change>& ch = desc->var_change._change;
00375     dc_pos.reserve(affected_added);
00376     ch.reserve(affected_added);
00377     posi = brobj->var_positions().begin();
00378     BCP_vec<double>::const_iterator boundsi = brobj->var_bounds_child(childind);
00379     while (posi != lastposi) {
00380         if (*posi >= bvarnum) {
00381             dc_pos.unchecked_push_back(*posi - bvarnum);
00382             const double lb = *boundsi;
00383             const double ub = *(boundsi+1);
00384             ch.unchecked_push_back(BCP_obj_change(lb, ub, BCP_ObjNotRemovable));
00385         }
00386         ++posi;
00387         boundsi += 2;
00388     }
00389 }
00390 
00391 //#############################################################################
00392 
00393 static void
00394 BCP_tm_create_cut_change(BCP_node_change* desc,
00395                          const BCP_node_change* parentdesc, const int bcutnum,
00396                          const BCP_internal_brobj* brobj, const int childind)
00397 {
00398     // check first how many added cut has changed in brobj
00399     int affected_added = 0;
00400     BCP_vec<int>::const_iterator posi = brobj->cut_positions().begin();
00401     BCP_vec<int>::const_iterator lastposi = brobj->cut_positions().end();
00402     while (posi != lastposi) {
00403         if (*posi >= bcutnum)
00404             ++affected_added;
00405         ++posi;
00406     }
00407 
00408     if (affected_added == 0) {
00409         if (parentdesc->cut_change.storage() == BCP_Storage_Explicit &&
00410             parentdesc->cut_change.added_num() == 0) {
00411             desc->cut_change._storage = BCP_Storage_Explicit;
00412         } else {
00413             desc->cut_change._storage = BCP_Storage_WrtParent;
00414         }
00415         return;
00416     }
00417 
00418     desc->cut_change._storage = BCP_Storage_WrtParent;
00419     BCP_vec<int>& dc_pos = desc->cut_change._del_change_pos;
00420     BCP_vec<BCP_obj_change>& ch = desc->cut_change._change;
00421     dc_pos.reserve(affected_added);
00422     ch.reserve(affected_added);
00423     posi = brobj->cut_positions().begin();
00424     BCP_vec<double>::const_iterator boundsi = brobj->cut_bounds_child(childind);
00425     while (posi != lastposi) {
00426         if (*posi >= bcutnum) {
00427             dc_pos.unchecked_push_back(*posi - bcutnum);
00428             const double lb = *boundsi;
00429             const double ub = *(boundsi+1);
00430             ch.unchecked_push_back(BCP_obj_change(lb, ub, BCP_ObjNotRemovable));
00431         }
00432         ++posi;
00433         boundsi += 2;
00434     }
00435 }
00436 
00437 //#############################################################################
00438 
00439 static BCP_tm_node*
00440 BCP_tm_create_child(BCP_tm_prob& p, const int child_ind,
00441                     BCP_tm_node* node,
00442                     const BCP_internal_brobj* brobj,
00443                     const BCP_vec<BCP_child_action>& action,
00444                     const BCP_vec<BCP_user_data*>& user_data,
00445                     const BCP_vec<double>& true_lb,
00446                     const BCP_vec<double>& qualities)
00447 {
00448     // generate the children
00449     const int bvarnum = p.core->varnum();
00450     const int bcutnum = p.core->cutnum();
00451     const int depth = node->getDepth() + 1;
00452     const BitVector128 nodePref = node->getPreferred();
00453 
00454     // nodedesc exists, because when we unpack the barnching info we just
00455     // received back the description of the node
00456     const BCP_node_change* nodedesc = node->_data._desc.GetRawPtr();
00457 
00458     BCP_node_change* desc = new BCP_node_change;
00459     BCP_tm_create_core_change(desc, bvarnum, bcutnum, brobj, child_ind);
00460     BCP_tm_create_var_change(desc, nodedesc, bvarnum, brobj, child_ind);
00461     BCP_tm_create_cut_change(desc, nodedesc, bcutnum, brobj, child_ind);
00462     if (nodedesc->warmstart)
00463       // If the parent has warmstart info then 
00464       desc->warmstart = nodedesc->warmstart->empty_wrt_this();
00465 
00466     BCP_tm_node* child = new BCP_tm_node(node->getDepth() + 1, desc);
00467     child->_core_storage = desc->core_change.storage();
00468     child->_var_storage = desc->var_change.storage();
00469     child->_cut_storage = desc->cut_change.storage();
00470     child->_ws_storage =
00471       desc->warmstart ? desc->warmstart->storage() : BCP_Storage_NoData;
00472 
00473     p.search_tree.insert(child); // this sets _index
00474     child->_data._user = user_data[child_ind];
00475     child->_parent = node;
00476     child->_birth_index = node->child_num();
00477     /* Fill out the fields in CoinTreeNode */
00478     child->setDepth(depth);
00479     child->setQuality(qualities[child_ind]);
00480     child->setTrueLB(true_lb[child_ind]);
00481     if (child_ind > 0 && depth <= 127) {
00482       BitVector128 pref = nodePref;
00483       pref.setBit(127-depth);
00484       child->setPreferred(pref);
00485     } else {
00486       child->setPreferred(nodePref);
00487     }
00488     /* Add the child to the list of children in the parent */
00489     node->new_child(child);
00490     // _children  initialized to be empty -- OK
00491     switch (action[child_ind]){
00492     case BCP_ReturnChild:
00493       child->status = BCP_CandidateNode;
00494       break;
00495     case BCP_KeepChild:
00496       child->status = BCP_CandidateNode; // be conservative
00497       break;
00498     case BCP_FathomChild:
00499       child->status = BCP_PrunedNode_Discarded;
00500       break;
00501     }
00502     // inherit var/cut pools
00503     child->vp = node->vp;
00504     child->cp = node->cp;
00505     // lp, cg, vg  initialized to -1 -- OK, none assigned yet
00506 #if (BCP_DEBUG_PRINT != 0)
00507     printf("TM %.3lf: parent: %i  sibling: %i  siblingind: %i  depth: %i  quality: %lf  pref: %s\n",
00508            tt, node->_index, i, child->_index, depth, child->getQuality(),
00509            child->getPreferred().str().c_str());
00510 #endif
00511     return child;
00512 }
00513 
00514 //#############################################################################
00515 
00516 static void
00517 BCP_tm_unpack_branching_info(BCP_tm_prob& p, BCP_buffer& buf,
00518                              BCP_tm_node* node)
00519 {
00520 TMDBG;
00521     BCP_diving_status dive; // the old diving status
00522 
00523     BCP_vec<BCP_child_action> action;
00524     BCP_vec<BCP_user_data*> user_data;
00525     BCP_vec<double> true_lb;
00526     BCP_vec<double> qualities;
00527 
00528 TMDBG;
00529     buf.unpack(dive);
00530 TMDBG;
00531     buf.unpack(action);
00532 TMDBG;
00533     buf.unpack(qualities);
00534 TMDBG;
00535     buf.unpack(true_lb);
00536 TMDBG;
00537 
00538     const int child_num = action.size();
00539     user_data.insert(user_data.end(), child_num, 0);
00540     bool has_user_data = false;
00541     for (int i = 0; i < child_num; ++i) {
00542         buf.unpack(has_user_data);
00543         if (has_user_data) {
00544             user_data[i] = p.packer->unpack_user_data(buf);
00545         }
00546     }
00547 TMDBG;
00548 
00549     BCP_internal_brobj* brobj = new BCP_internal_brobj;
00550     brobj->unpack(buf);
00551 
00552     node->reserve_child_num(brobj->child_num());
00553     int keep = -1;
00554     BCP_tm_node* child = 0;
00555     int i;
00556 
00557     // fix the number of leaves assigned to the CP/VP
00558     if (node->cp != -1) {
00559         BCP_vec< std::pair<int, int> >::iterator proc =
00560             BCP_tm_identify_process(p.leaves_per_cp, node->cp);
00561         if (proc == p.leaves_per_cp.end()) {
00562             node->cp = -1; 
00563         } else {
00564             proc->second += node->child_num() - 1;
00565         }
00566     }
00567     if (node->vp != -1) {
00568         BCP_vec< std::pair<int, int> >::iterator proc =
00569             BCP_tm_identify_process(p.leaves_per_vp, node->vp);
00570         if (proc == p.leaves_per_vp.end()) {
00571             node->vp = -1; 
00572         } else {
00573             proc->second += node->child_num() - 1;
00574         }
00575     }
00576 
00577     CoinTreeNode** children = new CoinTreeNode*[child_num];
00578     int numChildrenAdded = 0;
00579 #if (BCP_DEBUG_PRINT != 0)
00580     const double tt = CoinWallclockTime()-p.start_time;
00581     if (p.candidate_list.size() == 0) {
00582       printf("TM %.3lf: parent: %i  cand_list empty\n", tt, node->_index);
00583     } else {
00584       printf("TM %.3lf: parent: %i  cand_list top pref: %s\n",
00585              tt, node->_index,
00586              p.candidate_list.top()->getPreferred().str().c_str());
00587     }
00588 #endif
00589     // First find out if the LP process should keep any of the children to
00590     // dive into.
00591     for (i = 0; i < child_num; ++i) {
00592       if (action[i] == BCP_KeepChild) {
00593         assert(keep == -1);
00594         keep = i;
00595       }
00596     }
00597     if (keep >= 0) {
00598       children[numChildrenAdded++] = BCP_tm_create_child(p, keep, node, brobj,
00599                                                          action, user_data,
00600                                                          true_lb, qualities);
00601     }
00602     for (i = 0; i < child_num; ++i) {
00603       if (i != keep) {
00604         children[numChildrenAdded++] = BCP_tm_create_child(p, i, node, brobj,
00605                                                            action, user_data,
00606                                                            true_lb, qualities);
00607       }
00608     }
00609 
00610     if (numChildrenAdded > 0) {
00611       CoinTreeSiblings siblings(numChildrenAdded, children);
00612 
00613       BCP_print_memusage(p);
00614       p.need_a_TS = ! BCP_tm_is_data_balanced(p);
00615 
00616       // check the one that's proposed to be kept if there's one
00617       if (keep >= 0) {
00618         // The kept child was pushed into the node first.
00619         child = node->child(0);
00620         if (dive == BCP_DoDive || dive == BCP_TestBeforeDive){
00621           // we've got to answer
00622           buf.clear();
00623           if (p.need_a_TS) {
00624             /* Force no diving if we need a TS process */
00625             dive = BCP_DoNotDive;
00626           } else {
00627             if (dive == BCP_TestBeforeDive)
00628               dive = BCP_tm_shall_we_dive(p, child->getQuality());
00629           }
00630           buf.pack(dive);
00631           if (dive != BCP_DoNotDive){
00632             p.user->display_node_information(p.search_tree, *child);
00633             child->status = BCP_ActiveNode;
00634             // if diving then send the new index and var/cut_names
00635             buf.pack(child->index());
00636             siblings.advanceNode();
00637           }
00638           p.candidate_list.push(siblings);
00639           p.user->change_candidate_heap(p.candidate_list, false);
00640           p.msg_env->send(node->lp, BCP_Msg_DivingInfo, buf);
00641         } else {
00642           p.candidate_list.push(siblings);
00643           p.user->change_candidate_heap(p.candidate_list, false);
00644         }
00645       } else {
00646         p.candidate_list.push(siblings);
00647         p.user->change_candidate_heap(p.candidate_list, false);
00648         dive = BCP_DoNotDive;
00649       }
00650 
00651       if (dive == BCP_DoNotDive){
00652         // lp,cg,vg becomes free (zeroes out node->{lp,cg,vg})
00653         BCP_tm_free_procs_of_node(p, node);
00654       } else {
00655         // if diving then the child takes over the parent's lp,cg,vg
00656         // XXX
00657         if (child != node->child(0)) {
00658           throw BCP_fatal_error("\
00659 BCP_tm_unpack_branching_info: the value of child is messed up!\n");
00660         }
00661         if (node->lp == -1) {
00662           throw BCP_fatal_error("\
00663 BCP_tm_unpack_branching_info: the (old) node has no LP associated with!\n");
00664         }
00665         child->lp = node->lp;
00666         child->cg = node->cg;
00667         child->vg = node->vg;
00668         p.active_nodes[node->lp] = child;
00669         node->lp = node->cg = node->vg = -1;
00670       }
00671     }
00672     delete[] children;
00673 
00674     // and the node is done
00675     node->status = BCP_ProcessedNode;
00676 
00677     delete brobj;
00678 
00679 #ifdef BCP__DUMP_PROCINFO
00680 #if (BCP__DUMP_PROCINFO == 1)
00681     dump_procinfo(p, "BCP_tm_unpack_branching_info()");
00682 #endif
00683 #endif
00684 }
00685 
00686 //#############################################################################
00687 
00688 void BCP_tm_unpack_node_with_branching_info(BCP_tm_prob& p, BCP_buffer& buf)
00689 {
00690     const int index = BCP_tm_unpack_node_description(p, buf);
00691     /* In the middle of BCP_tm_unpack_branching_info we check for data
00692        balancing just before we (may) allow diving.*/
00693     BCP_tm_unpack_branching_info(p, buf, p.search_tree[index]);
00694     BCP_tm_print_info_line(p, *p.search_tree[index]);
00695     // BCP_tm_list_candidates(p);
00696 
00697     p.need_a_TS = BCP_tm_balance_data(p);
00698 }
00699 
00700 //#############################################################################
00701 
00702 BCP_tm_node* BCP_tm_unpack_node_no_branching_info(BCP_tm_prob& p,
00703                                                   BCP_buffer& buf)
00704 {
00705     const int index = BCP_tm_unpack_node_description(p, buf);
00706 
00707     BCP_print_memusage(p);
00708     p.need_a_TS = ! BCP_tm_is_data_balanced(p);
00709 
00710     // Mark the lp/cg/vg processes of the node as free
00711     BCP_tm_node* node = p.search_tree[index];
00712     BCP_tm_print_info_line(p, *node);
00713     BCP_tm_free_procs_of_node(p, node);
00714 
00715     p.need_a_TS = BCP_tm_balance_data(p);
00716 
00717     return node;
00718 }

Generated on Thu Oct 8 03:02:52 2009 by  doxygen 1.4.7