Module: ppl/ppl Branch: sparse_matrices Commit: 856f1052f1a7a81f6ca924ca6e692900552017ad URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=856f1052f1a7a...

Author: Marco Poletti poletti.marco@gmail.com Date: Wed Sep 15 11:41:44 2010 +0200

MIP_Problem: optimize further steepest_edge_exact_entering_index() for sparse working_cost rows.

---

src/MIP_Problem.cc | 54 ++++++++++++++++++++++++++++++++++----------------- 1 files changed, 36 insertions(+), 18 deletions(-)

diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 58c2112..b27e021 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -1204,25 +1204,43 @@ PPL::MIP_Problem::steepest_edge_exact_entering_index() const { k = columns.rbegin(); std::vector<std::pair<dimension_type, Coefficient> >::reverse_iterator k_end = columns.rend(); + working_cost_type::const_iterator itr = working_cost.end(); for ( ; k != k_end; ++k) { - Coefficient_traits::const_reference cost_j = working_cost[k->first]; - // We cannot compute the (exact) square root of abs(\Delta x_j). - // The workaround is to compute the square of `cost[j]'. - challenger_num = cost_j * cost_j; - // Initialization during the first loop. - if (entering_index == 0) { - std::swap(current_num, challenger_num); - std::swap(current_den, k->second); - entering_index = k->first; - continue; - } - challenger_value = challenger_num * current_den; - current_value = current_num * k->second; - // Update the values, if the challenger wins. - if (challenger_value > current_value) { - std::swap(current_num, challenger_num); - std::swap(current_den, k->second); - entering_index = k->first; + itr = working_cost.lower_bound(itr, k->first); + if (itr != working_cost.end() && itr.index() == k->first) { + // We cannot compute the (exact) square root of abs(\Delta x_j). + // The workaround is to compute the square of `cost[j]'. + challenger_num = (*itr) * (*itr); + // Initialization during the first loop. + if (entering_index == 0) { + std::swap(current_num, challenger_num); + std::swap(current_den, k->second); + entering_index = k->first; + continue; + } + challenger_value = challenger_num * current_den; + current_value = current_num * k->second; + // Update the values, if the challenger wins. + if (challenger_value > current_value) { + std::swap(current_num, challenger_num); + std::swap(current_den, k->second); + entering_index = k->first; + } + } else { + PPL_ASSERT(working_cost.get(k->first) == 0); + // Initialization during the first loop. + if (entering_index == 0) { + current_num = 0; + std::swap(current_den, k->second); + entering_index = k->first; + continue; + } + // Update the values, if the challenger wins. + if (0 > sgn(current_num) * sgn(k->second)) { + current_num = 0; + std::swap(current_den, k->second); + entering_index = k->first; + } } }