/home/coin/SVN-release/OS-2.4.2/Bcp/examples/MCF-3/TM/MCF3_tm.cpp

Go to the documentation of this file.
00001 #include "BCP_math.hpp"
00002 #include "BCP_solution.hpp"
00003 #include "MCF3_tm.hpp"
00004 
00005 using std::make_pair;
00006 
00007 //#############################################################################
00008 
00009 void
00010 MCF3_tm::init_new_phase(int phase,
00011                         BCP_column_generation& colgen,
00012                         CoinSearchTreeBase*& candidates)
00013 {
00014   // Let BCP initialize things (like creating the search tree)
00015   BCP_tm_user::init_new_phase(phase, colgen, candidates);
00016   // but override colgen
00017   colgen = BCP_GenerateColumns;
00018 }
00019 
00020 /*---------------------------------------------------------------------------*/
00021 
00022 void MCF3_tm::initialize_core(BCP_vec<BCP_var_core*>& vars,
00023                               BCP_vec<BCP_cut_core*>& cuts,
00024                               BCP_lp_relax*& matrix)
00025 {
00026   int i;
00027   // The core cuts are the cuts that specify that the sum of the flows must
00028   // not be out of bounds, and the convexity constraints for the generated
00029   // algo variables (flows). However, since there are no core variables, the
00030   // core matrix is empty.
00031   for (int i = 0; i < data.numarcs; ++i) {
00032     cuts.push_back(new BCP_cut_core(-BCP_DBL_MAX, data.arcs[i].ub));
00033   }
00034   for (i = 0; i < data.numcommodities; ++i) {
00035     cuts.push_back(new BCP_cut_core(1.0, 1.0));
00036   }
00037   matrix = new BCP_lp_relax;
00038 }
00039 
00040 /*---------------------------------------------------------------------------*/
00041 
00042 void MCF3_tm::create_root(BCP_vec<BCP_var*>& added_vars,
00043                           BCP_vec<BCP_cut*>& added_cuts,
00044                           BCP_user_data*& user_data)
00045 {
00046   // create a column (a flow) for each commodity
00047   if (par.entry(MCF3_par::AddDummySourceSinkArcs)) {
00048     // In this case just send all the demand through the artificial arc
00049     // for each commodity. That'll get the algorithm started.
00050     for (int i = 0; i < data.numcommodities; ++i) {
00051       int ind = data.numarcs-data.numcommodities+i;
00052       double val = data.commodities[i].demand;
00053       double w = data.commodities[i].demand * data.arcs[ind].weight;
00054       added_vars.push_back(new MCF3_var(i, CoinPackedVector(1, &ind, &val,
00055                                                             false), w));
00056     }
00057   } else {
00058     // Generate a flow for each commodity independently
00059     // *** excercise ***
00060 
00061     // Think of the consequences of not having the artificial arcs. After
00062     // branching the master problem may become infeasible, subproblems can
00063     // be infeasible, etc...
00064   }
00065 
00066   user_data = new MCF3_user(data.numcommodities);
00067 }
00068 
00069 /*---------------------------------------------------------------------------*/
00070 
00071 void MCF3_tm::display_feasible_solution(const BCP_solution* sol)
00072 {
00073   const BCP_solution_generic* gsol =
00074     dynamic_cast<const BCP_solution_generic*>(sol);
00075   const BCP_vec<BCP_var*>& vars = gsol->_vars;
00076   for (int i = vars.size()-1; i >= 0; --i) {
00077     const MCF3_var* v = dynamic_cast<const MCF3_var*>(vars[i]);
00078     printf("Flow of commodity %i:\n", v->commodity);
00079     const CoinPackedVector& f = v->flow;
00080     const int* ind = f.getIndices();
00081     const double* val = f.getElements();
00082     for (int j = 0; j < f.getNumElements(); ++j) {
00083       printf("    arc %6i  ( %5i -> %5i )     flow %i\n",
00084              ind[j], data.arcs[ind[j]].tail, data.arcs[ind[j]].head,
00085              static_cast<int>(val[j]));
00086     }
00087   }
00088 }
00089 
00090 /*---------------------------------------------------------------------------*/
00091 
00092 void MCF3_tm::pack_module_data(BCP_buffer& buf, BCP_process_t ptype)
00093 {
00094   switch (ptype) {
00095   case BCP_ProcessType_LP:
00096     par.pack(buf);
00097     data.pack(buf);
00098     break;
00099   default:
00100     throw BCP_fatal_error("In this example we have only an LP process!\n");
00101   }
00102 }               

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