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

Author: François Galea francois.galea@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_; } }