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

[Marco Poletti]

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

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

MIP_Problem: optimize process_pending_constraints() for sparse working_cost rows.

---

 src/MIP_Problem.cc |   14 +++++++++++---
 1 files changed, 11 insertions(+), 3 deletions(-)

diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc
index 784880d..9db9ffb 100644
--- a/src/MIP_Problem.cc
+++ b/src/MIP_Problem.cc
@@ -871,9 +871,17 @@ PPL::MIP_Problem::process_pending_constraints() {
   working_cost[last_obj_index] = 1;
 
   // Express the problem in terms of the variables in base.
-  for (dimension_type i = tableau_num_rows; i-- > 0; )
-    if (working_cost.get(base[i]) != 0)
-      linear_combine(working_cost, tableau[i], base[i]);
+  {
+    working_cost_type::const_iterator itr = working_cost.end();
+    for (dimension_type i = tableau_num_rows; i-- > 0; ) {
+      itr = working_cost.lower_bound(itr, base[i]);
+      if (itr != working_cost.end() && itr.index() == base[i] && *itr != 0) {
+        linear_combine(working_cost, tableau[i], base[i]);
+        // itr has been invalidated by the call to linear_combine().
+        itr = working_cost.end();
+      }
+    }
+  }
 
   // Deal with zero dimensional problems.
   if (space_dimension() == 0) {