/home/coin/SVN-release/OS-2.4.0/Bcp/src/LP/BCP_lp_main_loop.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_message.hpp"
00006 #include "BCP_error.hpp"
00007 #include "BCP_lp_node.hpp"
00008 #include "BCP_lp.hpp"
00009 #include "BCP_lp_user.hpp"
00010 #include "BCP_lp_functions.hpp"
00011 #include "BCP_lp_result.hpp"
00012 #include "BCP_warmstart.hpp"
00013 #include "BCP_solution.hpp"
00014 
00015 void BCP_lp_main_loop(BCP_lp_prob& p)
00016 {
00017     BCP_lp_result& lpres = *p.lp_result;
00018     // argument flag for a number of functions. of course, here we invoke those
00019     // functions from the main loop, but this flag must be tru if the functions
00020     // are invoked from repricing. hence the flag is set here to false.
00021     const bool from_repricing = false; 
00022 
00023     /*-----------------------------------------------------------------------*
00024      * The main loop -- continue solving relaxations until no new cuts
00025      * are found
00026      *-----------------------------------------------------------------------*/
00027     bool varset_changed = true;
00028     bool cutset_changed = true;
00029     double time0;
00030 
00031     double nodeStart = CoinCpuTime();
00032 
00033     p.user->print(p.param(BCP_lp_par::LpVerb_ProcessedNodeIndex), "\n");
00034     p.user->print(p.param(BCP_lp_par::LpVerb_ProcessedNodeIndex),
00035                   "LP: **** Processing NODE %i on LEVEL %i (from TM) ****\n",
00036                   p.node->index, p.node->level);
00037     // let the user do whatever she wants before the new node starts
00038     BCP_lp_prepare_for_new_node(p);
00039 
00040     while (true){
00041         ++p.node->iteration_count;
00042 
00043         BCP_lp_purge_slack_pool(p);
00044 
00045         p.user->print(p.param(BCP_lp_par::LpVerb_IterationCount), "\n");
00046         p.user->print(p.param(BCP_lp_par::LpVerb_IterationCount),
00047                       "LP: *** Starting iteration %i ***\n",
00048                       p.node->iteration_count);
00049 
00050         // Solve the lp relaxation and get the results
00051         time0 = CoinCpuTime();
00052         BCP_lp_check_ub(p);
00053         // Whether primal/dual feasibility was affected at the end of an
00054         // iteration. See doc of BCP_lp_user::modify_lp_parameters
00055         const int changeType = (varset_changed ? 2:0) + (cutset_changed ? 1:0);
00056 
00057         p.user->modify_lp_parameters(p.lp_solver, changeType, false);
00058 #if 0
00059         char fname[1000];
00060         sprintf(fname, "matrix-%i.%i.%i",
00061                 p.node->level, p.node->index, p.node->iteration_count);
00062         p.lp_solver->writeMps(fname, "mps");
00063 #endif
00064         p.lp_solver->resolve();
00065         lpres.get_results(*p.lp_solver);
00066         const int tc = lpres.termcode();
00067         p.stat.time_lp_solving += CoinCpuTime() - time0;
00068 
00069         if (varset_changed) {
00070             p.node->lb_at_cutgen.clear();
00071             p.node->lb_at_cutgen.insert(p.node->lb_at_cutgen.end(),
00072                                         p.node->cuts.size(), lpres.objval());
00073         }
00074 
00075         // Display the matrix solution value
00076         if (p.param(BCP_lp_par::LpVerb_LpSolutionValue)) {
00077             p.user->print(true, "LP:   Matrix size: %i vars x %i cuts\n",
00078                           static_cast<int>(p.node->vars.size()),
00079                           static_cast<int>(p.node->cuts.size()));
00080             p.user->print(true, "LP:   Solution value: %.4f / %i , %i \n",
00081                           lpres.objval(), tc, lpres.iternum());
00082         }
00083 
00084         // Display the relaxed solution if needed
00085         if (p.param(BCP_lp_par::LpVerb_RelaxedSolution)) {
00086             p.user->display_lp_solution(lpres, p.node->vars, p.node->cuts,
00087                                         false);
00088         }
00089       
00090         // Test feasibility (note that it might be infeasible, but the user
00091         // might want to generate a heur feas sol anyway)
00092         time0 = CoinCpuTime();
00093         p.node->quality = lpres.objval();
00094 
00095         BCP_lp_process_result(p, lpres);
00096 
00097         BCP_lp_test_feasibility(p, lpres);
00098         p.stat.time_feas_testing += CoinCpuTime() - time0;
00099 
00100         // Update the lower bound
00101         const double tlb = BCP_lp_compute_lower_bound(p, lpres);
00102         if (tlb > p.node->true_lower_bound)
00103             p.node->true_lower_bound = tlb;
00104 
00105         if (p.over_ub(p.node->true_lower_bound)) {
00106             BCP_lp_perform_fathom(p, "\
00107 LP:   Terminating and fathoming due to proven high cost.\n",
00108                                   BCP_Msg_NodeDescription_OverUB_Pruned);
00109             return;
00110         }
00111 
00112         // If we get here then we either
00113         // - do not generate columns AND the lp value is below the ub
00114         // - generate columns
00115 
00116         if (tc & BCP_ProvenPrimalInf) {
00117             p.user->print(p.param(BCP_lp_par::LpVerb_FathomInfo),
00118                           "LP:   Primal feasibility lost.\n");
00119             if (BCP_lp_fathom(p, from_repricing)) {
00120                 return;
00121             }
00122             varset_changed = true;
00123             continue;
00124         }
00125 
00126         if (tc & (BCP_ProvenDualInf | BCP_PrimalObjLimReached | BCP_TimeLimit)){
00127             // *FIXME* : for now just throw an exception, but *THINK*
00128             p.user->print(true, "LP: ############ Unexpected termcode: %i\n",
00129                           lpres. termcode());
00130             throw BCP_fatal_error("Unexpected termcode in BCP_lp_main_loop!\n");
00131         }
00132 
00133         // We came here, therefore termcode must have been optimal and the
00134         // cost cannot be too high. OR, the LP solver has abandoned things and
00135         // we want to branch through.
00136 
00137         if (! (tc & BCP_Abandoned)) {
00138           // So termcode must have been optimal and the cost cannot be too
00139           // high.
00140 
00141           // So far we haven't generated any new variables.
00142           varset_changed = false;
00143 
00144           if (BCP_lp_fix_vars(p) ||
00145               (p.lp_solver->canDoSimplexInterface() &&
00146                !p.lp_solver->basisIsAvailable())) {
00147             // during variable fixing primal feasibility is lost (must be due
00148             // to logical fixing by the user) OR we can do simplex, but for
00149             // some reason the basis is lost (generally when the LP solver
00150             // discards the basis if bounds are changed). Go back and resolve,
00151             // but keep the same iteration number
00152             --p.node->iteration_count;
00153             continue;
00154           }
00155 
00156           p.no_more_cuts_cnt = 0;
00157           p.no_more_vars_cnt = 0;
00158           if (! p.param(BCP_lp_par::MessagePassingIsSerial)) {
00159             // If the message passing environment is really parallel (i.e.,
00160             // while the CG/CP are working we can do something else) then:
00161             // send the current solution to CG, and also to CP if either
00162             //  - lb_at_cutgen was reset, i.e., we are at the beginning of a
00163             //    chain, or columns were generated. (This way we'll check the
00164             //    pool at the top of the root, too, which is unnecessary, but
00165             //    it doesn't hurt and no big time is lost.)
00166             //  - or this is the cut_pool_check_freq-th iteration.
00167             if (p.node->cg != -1 || p.node->cp != -1) {
00168               const BCP_message_tag msgtag = BCP_lp_pack_for_cg(p);
00169               if (p.node->cg != -1) {
00170                 ++p.no_more_cuts_cnt;
00171                 p.msg_env->send(p.node->cg, msgtag, p.msg_buf);
00172               }
00173               if (p.node->cp != -1) {
00174                 if (! (p.node->iteration_count %
00175                        p.param(BCP_lp_par::CutPoolCheckFrequency))
00176                     || varset_changed) {
00177                   ++p.no_more_cuts_cnt;
00178                   p.msg_env->send(p.node->cp, msgtag, p.msg_buf);
00179                 }
00180               }
00181             }
00182             // Similarly, send stuff to the VG/VP
00183             if (p.node->vg != -1 || p.node->vp != -1) {
00184               const BCP_message_tag msgtag = BCP_lp_pack_for_vg(p);
00185               if (p.node->vg != -1) {
00186                 ++p.no_more_vars_cnt;
00187                 p.msg_env->send(p.node->vg, msgtag, p.msg_buf);
00188               }
00189               if (p.node->vp != -1) {
00190                 if (! (p.node->iteration_count %
00191                        p.param(BCP_lp_par::VarPoolCheckFrequency))
00192                     || cutset_changed) {
00193                   ++p.no_more_vars_cnt;
00194                   p.msg_env->send(p.node->cp, msgtag, p.msg_buf);
00195                 }
00196               }
00197             }
00198           }
00199 
00200           BCP_lp_adjust_row_effectiveness(p);
00201 
00202           // Generate and receive the cuts
00203           const int cuts_to_add_cnt =
00204             BCP_lp_generate_cuts(p, varset_changed, from_repricing);
00205           // Generate and receive the vars
00206           const int vars_to_add_cnt =
00207             BCP_lp_generate_vars(p, cutset_changed, from_repricing);
00208 
00209           time0 = CoinCpuTime();
00210           BCP_solution* sol =
00211             p.user->generate_heuristic_solution(lpres,
00212                                                 p.node->vars, p.node->cuts);
00213           p.stat.time_heuristics += CoinCpuTime() - time0;
00214           // If the sol is a generic sol then look through the vars in it, and
00215           // if any of them has 0 bcpindex then assign an index to it.
00216           BCP_solution_generic* gsol = dynamic_cast<BCP_solution_generic*>(sol);
00217           if (gsol) {
00218             const int size = gsol->_vars.size();
00219             for (int i = 0; i < size; ++i) {
00220               if (gsol->_vars[i]->bcpind() == 0 &&
00221                   gsol->_vars[i]->obj_type() == BCP_AlgoObj)
00222                 gsol->_vars[i]->set_bcpind(-BCP_lp_next_var_index(p));
00223             }
00224           }
00225 
00226           if (sol != NULL) {
00227             p.user->send_feasible_solution(sol);
00228             delete sol;
00229             if (p.over_ub(p.node->true_lower_bound)) {
00230               BCP_lp_perform_fathom(p, "\
00231 LP:   Terminating and fathoming due to proven high cost (good heur soln!).\n",
00232                                     BCP_Msg_NodeDescription_OverUB_Pruned);
00233               return;
00234             }
00235           }
00236 
00237           const bool verb_cut = p.param(BCP_lp_par::LpVerb_GeneratedCutCount);
00238           const bool verb_var = p.param(BCP_lp_par::LpVerb_GeneratedVarCount);
00239           // Report how many have been generated
00240           if (verb_cut && ! verb_var) {
00241             p.user->print(true, "LP:   In iteration %i BCP generated",
00242                           p.node->iteration_count);
00243             p.user->print(true, " %i cuts before calling branch()\n",
00244                           cuts_to_add_cnt);
00245           } else if (! verb_cut && verb_var) {
00246             p.user->print(true, "LP:   In iteration %i BCP generated",
00247                           p.node->iteration_count);
00248             p.user->print(true, " %i vars before calling branch()\n",
00249                           vars_to_add_cnt);
00250           } else if (verb_cut && verb_var) {
00251             p.user->print(true, "LP:   In iteration %i BCP generated",
00252                           p.node->iteration_count);
00253             p.user->print(true," %i cuts , %i vars before calling branch()\n",
00254                           cuts_to_add_cnt, vars_to_add_cnt);
00255           }
00256           
00257           if (cuts_to_add_cnt == 0 && vars_to_add_cnt == 0 &&
00258               p.param(BCP_lp_par::LpVerb_FinalRelaxedSolution)){
00259             // Display solution if nothing is generated
00260             p.user->display_lp_solution(lpres,
00261                                         p.node->vars, p.node->cuts, true);
00262           }
00263         }
00264 
00265         // Try to branch
00266         switch (BCP_lp_branch(p)){
00267         case BCP_BranchingFathomedThisNode:
00268             p.user->print(p.param(BCP_lp_par::LpVerb_NodeTime),
00269                           "BCP_lp: Time spent in this node: %15.4f seconds\n",
00270                           CoinCpuTime() - nodeStart);
00271             // Note that BCP_lp_branch() has already sent the node description
00272             // to the TM, info is printed, node is cleaned up, so just return
00273             return;
00274 
00275         case BCP_BranchingDivedIntoNewNode:
00276             p.user->print(p.param(BCP_lp_par::LpVerb_NodeTime),
00277                           "BCP_lp: Time spent in this node: %15.4f seconds\n",
00278                           CoinCpuTime() - nodeStart);
00279             nodeStart = CoinCpuTime();
00280             p.user->print(p.param(BCP_lp_par::LpVerb_ProcessedNodeIndex),"\n");
00281             p.user->print(p.param(BCP_lp_par::LpVerb_ProcessedNodeIndex),
00282                           "LP: **** Processing NODE %i on LEVEL %i (dived) ****\n",
00283                           p.node->index, p.node->level);
00284             // let the user do whatever she wants before the new node starts
00285             BCP_lp_prepare_for_new_node(p);
00286             // here we don't have to delete cols and rows, it's done as part of
00287             // the cleanup during branching.
00288             varset_changed = true;
00289             cutset_changed = true;
00290             
00291             break;
00292 
00293         case BCP_BranchingContinueThisNode:
00294             // got to add things from the local pools
00295             const int added_cuts = BCP_lp_add_from_local_cut_pool(p);
00296             const int added_vars = BCP_lp_add_from_local_var_pool(p);
00297             const bool added_cut = p.param(BCP_lp_par::LpVerb_AddedCutCount);
00298             const bool added_var = p.param(BCP_lp_par::LpVerb_AddedVarCount);
00299             p.user->print(added_cut && ! added_var,
00300                           "LP:  In iteration %i BCP added %i cuts.\n",
00301                           p.node->iteration_count, added_cuts);
00302             p.user->print(! added_cut && added_var,
00303                           "LP:  In iteration %i BCP added %i vars.\n",
00304                           p.node->iteration_count, added_vars);
00305             p.user->print(added_cut && added_var,
00306                           "LP:  In iteration %i BCP added %i cuts, %i vars.\n",
00307                           p.node->iteration_count, added_cuts, added_vars);
00308             varset_changed = (added_vars > 0);
00309             cutset_changed = (added_cuts > 0);
00310             // the args are: (p, col_indices, row_indices, force_delete).
00311             // Here we don't have col/row_indices to compress, we are not from
00312             // fathom and we don't want to force deletion.
00313             BCP_lp_delete_cols_and_rows(p, 0, 0, 0, false, false);
00314             break;
00315         }
00316     }
00317 }

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