[PPL-devel] [GIT] ppl/ppl(pip): Changed the pivot row selection algorithm in compatibility_check.

[François Galea]

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

Author: François Galea <francois.galea at uvsq.fr>
Date:   Thu Nov 26 08:36:17 2009 +0100

Changed the pivot row selection algorithm in compatibility_check.
It now selects the row which maximizes the lexico-minimal pivot column.

---

 src/PIP_Tree.cc |   29 +++++++++++++----------------
 1 files changed, 13 insertions(+), 16 deletions(-)

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index 70526cb..a181521 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -1051,22 +1051,19 @@ PIP_Solution_Node::compatibility_check(const Matrix &ctx, const Row &cnst) {
     // Look for a negative RHS (=constant term, stored in matrix column 0)
     i = num_rows;
     j = 0;
-    for (i_=0; i_<num_rows; ++i_) {
-      const Row& rs = s[i_];
-      if (rs[0] < 0) {
-        if (i == num_rows)
-          i = i_;
-        for (j_=1; j_<num_cols; ++j_) {
-          // Search for first least nonnegative pivot candidate
-          const Coefficient& c = rs[j_];
-          if (c > 0 && (j == 0 || c < rs[j]))
-            j = j_;
-        }
-        if (j == 0) {
-          // No positive pivot candidate: empty problem
-          return false;
-        }
-        break;
+
+    // Find Pivot row i and pivot column j, by maximizing the pivot column
+    for (i_ = 0; i_ < num_rows; ++i_) {
+      if (s[i_][0] >= 0)
+        continue;
+      if (!find_lexico_minimum_column(s, mapping, basis, s[i_], 1, j_)) {
+        // No positive pivot candidate: empty problem
+        return false;
+      }
+      if (j == 0 || column_lower(s, mapping, basis,
+                    s[i], j, s[i_], j_, s[i][0], s[i_][0])) {
+        i = i_;
+        j = j_;
       }
     }