00001
00002
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
00019
00020
00021 const bool from_repricing = false;
00022
00023
00024
00025
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
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
00051 time0 = CoinCpuTime();
00052 BCP_lp_check_ub(p);
00053
00054
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
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
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
00091
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
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
00113
00114
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
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
00134
00135
00136
00137 if (! (tc & BCP_Abandoned)) {
00138
00139
00140
00141
00142 varset_changed = false;
00143
00144 if (BCP_lp_fix_vars(p) ||
00145 (p.lp_solver->canDoSimplexInterface() &&
00146 !p.lp_solver->basisIsAvailable())) {
00147
00148
00149
00150
00151
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
00160
00161
00162
00163
00164
00165
00166
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
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
00203 const int cuts_to_add_cnt =
00204 BCP_lp_generate_cuts(p, varset_changed, from_repricing);
00205
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
00215
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
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
00260 p.user->display_lp_solution(lpres,
00261 p.node->vars, p.node->cuts, true);
00262 }
00263 }
00264
00265
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
00272
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
00285 BCP_lp_prepare_for_new_node(p);
00286
00287
00288 varset_changed = true;
00289 cutset_changed = true;
00290
00291 break;
00292
00293 case BCP_BranchingContinueThisNode:
00294
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
00311
00312
00313 BCP_lp_delete_cols_and_rows(p, 0, 0, 0, false, false);
00314 break;
00315 }
00316 }
00317 }