/home/coin/SVN-release/OS-2.4.2/Bcp/src/LP/BCP_lp_generate_vars.cpp

Go to the documentation of this file.
00001 // Copyright (C) 2000, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 #include <cstdio>
00004 #include "CoinTime.hpp"
00005 #include "BCP_lp_functions.hpp"
00006 #include "BCP_enum.hpp"
00007 #include "BCP_lp_result.hpp"
00008 #include "BCP_lp_pool.hpp"
00009 #include "BCP_lp_user.hpp"
00010 #include "BCP_lp.hpp"
00011 #include "BCP_lp_node.hpp"
00012 
00013 int BCP_lp_generate_vars(BCP_lp_prob& p,
00014                          bool cutset_changed, const bool from_repricing)
00015 {
00016    double time0 = CoinCpuTime();
00017 
00018    BCP_lp_result& lpres = *p.lp_result;
00019    BCP_lp_var_pool& vp = *p.local_var_pool;
00020    int prev_size = vp.size();
00021 
00022    if (prev_size > 0 && ! vp.cols_are_valid()){
00023       // we must regenerate the cols from the variables
00024       // first delete the old cols then expand the vars again
00025 
00026       // these will hold vars and cols expanded from the vars
00027       BCP_vec<BCP_var*> vars;
00028       BCP_vec<BCP_col*> cols;
00029 
00030       vars.reserve(prev_size);
00031       int i;
00032       for (i = 0; i < prev_size; ++i) {
00033          vp[i]->delete_col();
00034          vars.unchecked_push_back(vp[i]->var());
00035       }
00036       // now expand
00037       cols.reserve(prev_size);
00038       p.user->vars_to_cols(p.node->cuts, vars, cols,
00039                            lpres, BCP_Object_Leftover, false);
00040       for (i = 0; i < prev_size; ++i) {
00041          vp[i]->set_col(cols[i]);
00042       }
00043       cols.clear();
00044    }
00045    vp.cols_are_valid(true);
00046 
00047    if (p.param(BCP_lp_par::LpVerb_ReportLocalVarPoolSize))
00048       printf("LP:   Number of leftover vars: %i\n", prev_size);
00049 
00050    // Generate vars within the LP process
00051    BCP_vec<BCP_var*> new_vars;
00052    BCP_vec<BCP_col*> new_cols;
00053    BCP_price_vars(p, false /* not from fathom */, new_vars, new_cols);
00054    if (new_vars.size() > 0) {
00055       const int new_size = new_vars.size();
00056       vp.reserve(vp.size() + new_size);
00057       for (int i = 0; i < new_size; ++i) {
00058          new_vars[i]->set_bcpind(-BCP_lp_next_var_index(p));
00059          vp.unchecked_push_back(new BCP_lp_waiting_col(new_vars[i],
00060                                                        new_cols[i]));
00061       }
00062       new_cols.clear();
00063       new_vars.clear();
00064       if (p.param(BCP_lp_par::LpVerb_ReportLocalVarPoolSize))
00065          printf("LP:   Number of vars generated in the LP process: %i\n",
00066                 new_size);
00067       prev_size = vp.size();
00068    }
00069 
00070    // Compute the reduced cost for everything in the local var pool and throw
00071    // out the ones with positive reduced cost
00072    if (prev_size > 0) {
00073       vp.compute_red_costs(lpres, vp.begin(), vp.end());
00074       //      char dumpname[200];
00075       //sprintf(dumpname, "reducedcosts-%i-%i",
00076       //      p.node->index, p.node->iteration_count);
00077       //FILE* dumpfile = fopen(dumpname, "w");
00078       //for (int i = 0; i < prev_size; ++i) {
00079       //         fprintf(dumpfile, "%.6f\n", vp[i]->red_cost());
00080       //}
00081       //fclose(dumpfile);
00082       double detol = 0.0;
00083       p.lp_solver->getDblParam(OsiDualTolerance, detol);
00084       const int cnt = vp.remove_positives(detol);
00085       if (p.param(BCP_lp_par::LpVerb_ReportLocalVarPoolSize))
00086          printf("LP:   Positive rc (hence removed): %i\n", cnt);
00087       prev_size = vp.size();
00088    }
00089 
00090    if (p.param(BCP_lp_par::MessagePassingIsSerial)) {
00091       // If the message passing environment is not really parallel (i.e., while
00092       // the VG/VP are working the LP stops and also the LP must immediately
00093       // process any vars sent back then this is the place to send the lp
00094       // solution to the VG/VP.
00095       // send the current solution to VG, and also to VP if we are either
00096       //  - at the beginning of a chain (but not in the root in the
00097       //    first phase)
00098       //  - or this is the var_pool_check_freq-th iteration.
00099       if (p.node->vg != -1 || p.node->vp != -1) {
00100          const BCP_message_tag msgtag = BCP_lp_pack_for_vg(p);
00101          if (p.node->vg != -1) {
00102             ++p.no_more_vars_cnt;
00103             p.msg_env->send(p.node->vg, msgtag, p.msg_buf);
00104          }
00105          if (p.node->vp != -1) {
00106             if (! (p.node->iteration_count %
00107                    p.param(BCP_lp_par::VarPoolCheckFrequency))
00108                 || cutset_changed) {
00109                ++p.no_more_vars_cnt;
00110                p.msg_env->send(p.node->vp, msgtag, p.msg_buf);
00111             }
00112          }
00113       }
00114    }
00115 
00116    if (p.no_more_vars_cnt > 0){
00117       // Receive vars if we have sent out the lp solution somewhere.
00118       // set the timeout (all the times are in microseconds).
00119       double first_var_time_out = cutset_changed ?
00120          p.param(BCP_lp_par::FirstLP_FirstVarTimeout) :
00121          p.param(BCP_lp_par::LaterLP_FirstVarTimeout);
00122       double all_vars_time_out = cutset_changed ?
00123          p.param(BCP_lp_par::FirstLP_AllVarsTimeout) :
00124          p.param(BCP_lp_par::LaterLP_AllVarsTimeout);
00125       double tout = vp.size() == 0 ? first_var_time_out : all_vars_time_out;
00126       double tin = CoinCpuTime();
00127 
00128       while(true){
00129          p.msg_buf.clear();
00130          p.msg_env->receive(BCP_AnyProcess, BCP_Msg_AnyMessage,
00131                             p.msg_buf, tout);
00132          if (p.msg_buf.msgtag() == BCP_Msg_NoMessage){
00133             // check that everyone is still alive
00134             if (! p.msg_env->alive(p.get_parent() /*tree_manager*/))
00135                throw BCP_fatal_error("LP:   The TM has died -- LP exiting\n");
00136             if (p.node->cg != -1 && ! p.msg_env->alive(p.node->cg))
00137                throw BCP_fatal_error("LP:   The CG has died -- LP exiting\n");
00138             if (p.node->cp != -1 && ! p.msg_env->alive(p.node->cp))
00139                throw BCP_fatal_error("LP:   The CP has died -- LP exiting\n");
00140             if (p.node->vg != -1 && ! p.msg_env->alive(p.node->vg))
00141                throw BCP_fatal_error("LP:   The VG has died -- LP exiting\n");
00142             if (p.node->vp != -1 && ! p.msg_env->alive(p.node->vp))
00143                throw BCP_fatal_error("LP:   The VP has died -- LP exiting\n");
00144             // now the message queue is empty and received_message has
00145             // returned, i.e., we have waited enough
00146             if (p.param(BCP_lp_par::LpVerb_ReportVarGenTimeout))
00147                printf("LP:   Receive vars timed out after %f secs\n",
00148                       (prev_size != static_cast<int>(vp.size())?
00149                        all_vars_time_out : first_var_time_out));
00150             break;
00151          }
00152          p.process_message();
00153          // break out if no more vars can come
00154          if (p.no_more_vars_cnt == 0)
00155             break;
00156 
00157          // reset the timeout
00158          tout = vp.size() == 0 ? first_var_time_out : all_vars_time_out;
00159          if (tout >= 0){
00160             // with this tout we'll read out the rest of the message queue
00161             // even if var generation times out.
00162             tout = std::max<double>(0.0, tout - (CoinCpuTime() - tin));
00163          }
00164       }
00165    }
00166    // reset no_more_vars_cnt to 0
00167    p.no_more_vars_cnt = 0;
00168 
00169    if (p.param(BCP_lp_par::LpVerb_ReportLocalVarPoolSize)) {
00170       printf("LP:   Number of vars received from VG: %i\n",
00171              static_cast<int>(vp.size() - prev_size));
00172       printf("LP:   Total number of vars in local pool: %i\n",
00173              static_cast<int>(vp.size()));
00174    }
00175 
00176    if (vp.size() > 0) {
00177       const int oldsize = vp.size();
00178       double detol = 0.0;
00179       p.lp_solver->getDblParam(OsiDualTolerance, detol);
00180       const int cnt = vp.remove_positives(detol);
00181       if (cnt > 0) {
00182          printf("\
00183 LP: *WARNING*: There are vars with positive red cost in the local VP\n\
00184                at the end of var generation.\n\
00185                Discarding %i variables out of %i.\n", cnt, oldsize);
00186       }
00187    }
00188 
00189    p.stat.time_var_generation += CoinCpuTime() - time0;
00190 
00191    return vp.size();
00192 }

Generated on Wed Nov 30 03:03:49 2011 by  doxygen 1.4.7