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

[Marco Poletti]

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

Author: Marco Poletti <poletti.marco at gmail.com>
Date:   Tue Sep 14 14:56:42 2010 +0200

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

---

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

diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc
index 9db9ffb..1b54d00 100644
--- a/src/MIP_Problem.cc
+++ b/src/MIP_Problem.cc
@@ -996,9 +996,13 @@ PPL::MIP_Problem::steepest_edge_float_entering_index() const {
 #if USE_PPL_SPARSE_MATRIX
 
   const dimension_type tableau_num_columns_minus_1 = tableau_num_columns - 1;
+  // This is static to improve performance.
   // A vector of <column_index, challenger_den> pairs, ordered by
   // column_index.
-  std::vector<std::pair<dimension_type, double> > columns;
+  static std::vector<std::pair<dimension_type, double> > columns;
+  columns.clear();
+  // (working_cost.size() - 2) is an upper bound only.
+  columns.reserve(working_cost.size() - 2);
   {
     working_cost_type::const_iterator i = working_cost.lower_bound(1);
     // Note that find() is used instead of lower_bound().
@@ -1020,12 +1024,14 @@ PPL::MIP_Problem::steepest_edge_float_entering_index() const {
       = columns.end();
     while (j != j_end && k != k_end) {
       const dimension_type column = j.index();
-      if (k->first != column) {
-        if (k->first < column)
-          ++k;
-        else
-          j = tableau_i.lower_bound(j, k->first);
+      while (k != k_end && column > k->first)
+        ++k;
+      if (k == k_end)
+        break;
+      if (k->first > column) {
+        j = tableau_i.lower_bound(j, k->first);
       } else {
+        PPL_ASSERT(k->first == column);
         Coefficient_traits::const_reference tableau_ij = *j;
         WEIGHT_BEGIN();
         if (tableau_ij != 0) {