[PPL-devel] [GIT] ppl/ppl(sparse_matrices): MIP_Problem: optimize further steepest_edge_exact_entering_index() for sparse working_cost rows.

[Marco Poletti]

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

Author: Marco Poletti <poletti.marco at 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;
+      }
     }
   }