/home/coin/SVN-release/OS-2.0.0/Bcp/src/LP/BCP_lp_msgproc.cpp

Go to the documentation of this file.
00001 // Copyright (C) 2000, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 #include <functional>
00004 
00005 #include "BCP_message.hpp"
00006 #include "BCP_lp_user.hpp"
00007 #include "BCP_lp_node.hpp"
00008 #include "BCP_lp_pool.hpp"
00009 #include "BCP_lp.hpp"
00010 #include "BCP_lp_functions.hpp"
00011 
00012 //#############################################################################
00013 
00014 void BCP_lp_check_ub(BCP_lp_prob& p)
00015 {
00016   while (true){
00017     // call receive with 0 timeout => nonblocking
00018     p.msg_buf.clear();
00019     p.msg_env->receive(BCP_AnyProcess, BCP_Msg_UpperBound, p.msg_buf, 0);
00020     if (p.msg_buf.msgtag() == BCP_Msg_NoMessage)
00021       break;
00022     BCP_lp_process_ub_message(p, p.msg_buf);
00023   }
00024 }
00025 
00026 //#############################################################################
00027 
00028 void
00029 BCP_lp_prob::process_message()
00030 {
00031   BCP_cut* cut;
00032   BCP_var* var;
00033   const int cpid = node->cp;
00034   const int vpid = node->vp;
00035 
00036   int node_index;
00037   int node_itcnt;
00038 
00039   switch (msg_buf.msgtag()){
00040   case BCP_Msg_User:
00041     user->process_message(msg_buf);
00042     break;
00043 
00044   case BCP_Msg_InitialUserInfo:
00045     throw BCP_fatal_error("\
00046 LP: BCP_Msg_InitialUserInfo arrived in BCP_lp_prob::process_message().\n");
00047 
00048   case BCP_Msg_CutIndexSet:
00049     msg_buf.unpack(next_cut_index).unpack(last_cut_index);
00050     break;
00051 
00052   case BCP_Msg_VarIndexSet:
00053     msg_buf.unpack(next_var_index).unpack(last_var_index);
00054     break;
00055 
00056   case BCP_Msg_CutDescription:
00057     cut = unpack_cut();
00058     if (param(BCP_lp_par::CompareNewCutsToOldOnes)){
00059       // check if we already have this cut in the local cut pool
00060       BCP_lp_cut_pool::iterator oldcut = local_cut_pool->begin();
00061       BCP_lp_cut_pool::iterator lastoldcut = local_cut_pool->end();
00062       while (oldcut != lastoldcut){
00063         switch (user->compare_cuts((*oldcut)->cut(), cut)){
00064         case BCP_FirstObjIsBetter:
00065         case BCP_ObjsAreSame:
00066           delete cut;   cut = 0;
00067           msg_buf.clear();
00068           return;
00069         case BCP_SecondObjIsBetter:
00070         case BCP_DifferentObjs:
00071           ++oldcut;
00072           break;
00073         }
00074       }
00075     }
00076 
00077     if (no_more_cuts_cnt >= 0){ // we are waiting for cuts
00078       const bool from_pool = (cpid == msg_buf.sender());
00079       BCP_lp_cut_pool& cp = *local_cut_pool;
00080       const int old_cp_size = cp.size();
00081       BCP_vec<BCP_row*> rows;
00082       rows.reserve(1);
00083       BCP_vec<BCP_cut*> cuts(1, cut);
00084       user->cuts_to_rows(node->vars, cuts, rows, *lp_result,
00085                          cpid == msg_buf.sender() ?
00086                          BCP_Object_FromPool : BCP_Object_FromGenerator,
00087                          true);
00088       const int cutnum = cuts.size();
00089       for (int i = 0; i < cutnum; ++i) {
00090         cut = cuts[i];
00091         if (! from_pool) 
00092           cut->set_bcpind(-BCP_lp_next_cut_index(*this));
00093         cut->dont_send_to_pool(cpid == -1 || from_pool);
00094         cp.push_back(new BCP_lp_waiting_row(cut, rows[i]));
00095       }
00096       // compute the violation(s)
00097       cp.compute_violations(*lp_result, cp.entry(old_cp_size), cp.end());
00098     }else{ // the cut arrived while we are waiting for new LP
00099       local_cut_pool->push_back(new BCP_lp_waiting_row(cut));
00100     }
00101     break;
00102 
00103   case BCP_Msg_NoMoreCuts:
00104     // no more cuts can be generated for the current LP solution and hence
00105     // calculation can resume
00106     double cutgen_time;
00107     msg_buf.unpack(node_index).unpack(node_itcnt).unpack(cutgen_time);
00108     stat.time_cut_generation += cutgen_time;
00109     if (no_more_cuts_cnt >= 0 &&
00110         node->index == node_index && node->iteration_count == node_itcnt)
00111       no_more_cuts_cnt--;
00112     break;
00113 
00114   case BCP_Msg_VarDescription:
00115     var = unpack_var();
00116     if (param(BCP_lp_par::CompareNewVarsToOldOnes)){
00117       // check if we already have this var in the local var pool
00118       BCP_lp_var_pool::iterator oldvar = local_var_pool->begin();
00119       BCP_lp_var_pool::iterator lastoldvar = local_var_pool->end();
00120       while (oldvar != lastoldvar){
00121         switch (user->compare_vars((*oldvar)->var(), var)){
00122         case BCP_FirstObjIsBetter:
00123         case BCP_ObjsAreSame:
00124           delete var;   var = 0;
00125           msg_buf.clear();
00126           return;
00127         case BCP_SecondObjIsBetter:
00128         case BCP_DifferentObjs:
00129           ++oldvar;
00130           break;
00131         }
00132       }
00133     }
00134 
00135     if (no_more_vars_cnt >= 0){ // we are waiting for vars
00136       const bool from_pool = (vpid == msg_buf.sender());
00137       BCP_lp_var_pool& vp = *local_var_pool;
00138       const int old_vp_size = vp.size();
00139       BCP_vec<BCP_col*> cols;
00140       cols.reserve(1);
00141       BCP_vec<BCP_var*> vars(1, var);
00142       user->vars_to_cols(node->cuts, vars, cols, *lp_result,
00143                          vpid == msg_buf.sender() ?
00144                          BCP_Object_FromPool : BCP_Object_FromGenerator,
00145                          true);
00146       const int varnum = vars.size();
00147       for (int i = 0; i < varnum; ++i) {
00148         var = vars[i];
00149         if (! from_pool) 
00150           var->set_bcpind(-BCP_lp_next_var_index(*this));
00151         var->dont_send_to_pool(vpid == -1 || from_pool);
00152         vp.push_back(new BCP_lp_waiting_col(var, cols[i]));
00153       }
00154       // compute the reduced_cost(s)
00155       vp.compute_red_costs(*lp_result, vp.entry(old_vp_size), vp.end());
00156     }else{ // the var arrived while we are waiting for new LP
00157       local_var_pool->push_back(new BCP_lp_waiting_col(var));
00158     }
00159     break;
00160 
00161   case BCP_Msg_NoMoreVars:
00162     // no more vars can be generated for the current LP solution and hence
00163     // calculation can resume
00164     double vargen_time;
00165     msg_buf.unpack(node_index).unpack(node_itcnt).unpack(vargen_time);
00166     stat.time_var_generation += vargen_time;
00167     if (no_more_vars_cnt >= 0 &&
00168         node->index == node_index && node->iteration_count == node_itcnt)
00169       no_more_vars_cnt--;
00170     break;
00171 
00172   case BCP_Msg_UpperBound:
00173     BCP_lp_process_ub_message(*this, msg_buf);
00174     break;
00175 
00176   case BCP_Msg_WarmstartRoot:
00177     {
00178       BCP_warmstart* ws = packer->unpack_warmstart(msg_buf);
00179       delete warmstartRoot;
00180       warmstartRoot = ws->convert_to_CoinWarmStart();
00181       delete ws;
00182     }
00183     break;
00184 
00185   case BCP_Msg_ActiveNodeData:
00186     BCP_lp_unpack_active_node(*this, msg_buf);
00187     // load the lp formulation into the lp solver
00188     lp_solver = master_lp->clone();
00189     if (node->colgen != BCP_GenerateColumns) {
00190       // FIXME: If we had a flag in the node that indicates not to
00191       // generate cols in it and in its descendants then the dual obj
00192       // limit could still be set...
00193       lp_solver->setDblParam(OsiDualObjectiveLimit, ub() - granularity());
00194     }
00195     BCP_lp_create_lp(*this);
00196     BCP_lp_main_loop(*this);
00197     delete lp_solver;
00198     lp_solver = NULL;
00199     break;
00200 
00201   case BCP_Msg_DivingInfo:
00202     BCP_lp_unpack_diving_info(*this, msg_buf);
00203     break;
00204 
00205   case BCP_Msg_NextPhaseStarts:
00206     msg_buf.clear();
00207     // First send back timing data for the previous phase
00208     stat.pack(msg_buf);
00209     msg_env->send(get_parent() /*ree_manager*/,
00210                   BCP_Msg_LpStatistics, msg_buf);
00211     phase++;
00212     break;
00213 
00214   case BCP_Msg_FinishedBCP:
00215     // No need to clean up anything since the destructor of 'p' will do that.
00216     // However, send back the statistics.
00217     stat.pack(msg_buf);
00218     msg_env->send(get_parent() /*ree_manager*/,
00219                   BCP_Msg_LpStatistics, msg_buf);
00220     return;
00221 
00222   default:
00223     printf("Unknown message type arrived to LP: %i\n", msg_buf.msgtag());
00224     break;
00225   }
00226 
00227   msg_buf.clear();
00228 }
00229 
00230 //#############################################################################
00231 
00232 int
00233 BCP_lp_next_var_index(BCP_lp_prob& p)
00234 {
00235   if (p.next_var_index == p.last_var_index) {
00236     BCP_buffer& buf = p.msg_buf;
00237     // get new set of indices
00238     buf.clear();
00239     p.msg_env->send(p.get_parent() /*ree_manager*/,
00240                     BCP_Msg_RequestVarIndexSet);
00241     // In a single process environment the new index range has already
00242     // been received (and unpacked), thus we've got to receive it only if
00243     // the range still has length 0.
00244     if (p.next_var_index == p.last_var_index) {
00245       p.msg_env->receive(p.get_parent() /*ree_manager*/,
00246                          BCP_Msg_VarIndexSet, buf, -1);
00247       p.process_message();
00248     }
00249   }
00250   const int tmp = p.next_var_index++;
00251   return tmp;
00252 }
00253 
00254 //#############################################################################
00255 
00256 int
00257 BCP_lp_next_cut_index(BCP_lp_prob& p)
00258 {
00259   if (p.next_cut_index == p.last_cut_index) {
00260     BCP_buffer& buf = p.msg_buf;
00261     // get new set of indices
00262     buf.clear();
00263     p.msg_env->send(p.get_parent() /*ree_manager*/,
00264                     BCP_Msg_RequestCutIndexSet);
00265     // In a single process environment the new index range has already
00266     // been received (and unpacked), thus we've got to receive it only if
00267     // the range still has length 0.
00268     if (p.next_cut_index == p.last_cut_index) {
00269       p.msg_env->receive(p.get_parent() /*ree_manager*/,
00270                          BCP_Msg_CutIndexSet, buf, -1);
00271       p.process_message();
00272     }
00273   }
00274   const int tmp = p.next_cut_index++;
00275   return tmp;
00276 }
00277 
00278 //#############################################################################
00279 
00280 void BCP_lp_process_ub_message(BCP_lp_prob& p, BCP_buffer& buf)
00281 {
00282   double new_ub;
00283   buf.unpack(new_ub);
00284   if (p.ub(new_ub) && p.lp_solver && p.node &&
00285       p.node->colgen != BCP_GenerateColumns) {
00286     // FIXME: If we had a flag in the node that indicates not to
00287     // generate cols in it and in its descendants then the dual obj
00288     // limit could still be set...
00289     p.lp_solver->setDblParam(OsiDualObjectiveLimit,new_ub-p.granularity());
00290   }
00291 }
00292 
00293 //#############################################################################
00294 
00295 void BCP_lp_send_cuts_to_cp(BCP_lp_prob& p, const int eff_cnt_limit)
00296 {
00297   if (p.node->cp != -1) // go back if no cut pool exists
00298     return;
00299 
00300   BCP_cut_set& cuts = p.node->cuts;
00301   BCP_cut_set::iterator cuti = cuts.entry(p.core->cutnum());
00302   const BCP_cut_set::const_iterator lastcuti = cuts.end();
00303   BCP_cut* cut;
00304   int cnt;
00305 
00306   // First count how many to send
00307   for (cnt = 0; cuti != lastcuti; ++cuti) {
00308     cut = *cuti;
00309     if (cut->effective_count() >= eff_cnt_limit &&
00310         ! cut->dont_send_to_pool())
00311       ++cnt;
00312   }
00313 
00314   if (cnt > 0){
00315     BCP_buffer& buf = p.msg_buf;
00316     buf.clear();
00317     buf.pack(cnt);
00318     // whatever is sent to the CP must have been generated at this level
00319     buf.pack(p.node->level);
00320     // pack the cuts
00321     cuti = cuts.entry(p.core->cutnum());
00322     for ( ; cuti != lastcuti; ++cuti) {
00323       cut = *cuti;
00324       if (cut->effective_count() >= eff_cnt_limit &&
00325           ! cut->dont_send_to_pool())
00326         p.pack_cut(*cut);
00327       cut->dont_send_to_pool(true);
00328     }
00329 
00330     if (p.node->cp != -1) {
00331       p.msg_env->send(p.node->cp, BCP_Msg_CutsToCutPool, buf);
00332       if (p.param(BCP_lp_par::LpVerb_CutsToCutPoolCount))
00333         printf("LP:   %i cuts sent to cutpool\n", cnt);
00334     }
00335   }
00336 }
00337 
00338 //#############################################################################
00339 
00340 void BCP_lp_unpack_diving_info(BCP_lp_prob& p, BCP_buffer& buf)
00341 {
00342   buf.unpack(p.node->dive); // what's the new diving status?
00343   if (p.node->dive != BCP_DoNotDive){
00344     // do dive
00345     buf.unpack(p.node->index);
00346     // finally, a little cleaning for the new node
00347     p.node->level++;
00348     p.node->iteration_count = 0;
00349   } else {
00350     p.node->index = -1;
00351   }
00352 }

Generated on Mon Aug 3 03:02:15 2009 by  doxygen 1.4.7