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

Generated on Thu Sep 22 03:05:52 2011 by  doxygen 1.4.7