March 2010 - PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(sparse_matrices): PIP_Tree.cc: prepare compatibility_check_find_pivot_in_set() for optimizations (#1).
by Marco Poletti 12 Mar '10

12 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 3279a83d2092672dff199460b6d507519893478c URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3279a83d2092… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Mar 12 21:17:28 2010 +0100 PIP_Tree.cc: prepare compatibility_check_find_pivot_in_set() for optimizations (#1). --- src/PIP_Tree.cc | 99 +++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 files changed, 92 insertions(+), 7 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index e54b797..4d91e57 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -630,19 +630,104 @@ compatibility_check_find_pivot_in_set(std::set<std::pair<dimension_type, const std::vector<dimension_type>& mapping, const std::vector<bool>& basis) { - dimension_type pi = s.num_rows(); // pi is the pivot's row index. - dimension_type pj = 0; // pj is the pivot's column index. + dimension_type pi; // pi is the pivot's row index. + dimension_type pj; // pj is the pivot's column index. typedef std::set<std::pair<dimension_type,dimension_type> > candidates_t; candidates_t::iterator i = candidates.begin(); candidates_t::iterator i_end = candidates.end(); - for ( ; i!=i_end; ++i) { + PPL_ASSERT(i != i_end); + pi = i->first; + pj = i->second; + for (++i; i!=i_end; ++i) { PIP_Tree_Node::matrix_row_const_reference_type s_i = s[i->first]; // Update pair (pi, pj) if they are still unset or // if the challenger pair (i, j) is better in the ordering. - if (pj == 0 - || column_lower(s, mapping, basis, - s[pi], pj, s_i, i->second, - s[pi].get(0), s_i.get(0))) { + bool found_better_pivot; + /* + found_better_pivot = column_lower(s, mapping, basis, + s[pi], pj, s_i, i->second, + , ); + */ + + PIP_Tree_Node::matrix_row_const_reference_type pivot_a = s[pi]; + const dimension_type ja = pj; + PIP_Tree_Node::matrix_row_const_reference_type pivot_b = s_i; + const dimension_type jb = i->second; + Coefficient_traits::const_reference cst_a = s[pi].get(0); + Coefficient_traits::const_reference cst_b = s_i.get(0); + + const Coefficient& sij_a = pivot_a.get(ja); + const Coefficient& sij_b = pivot_b.get(jb); + PPL_ASSERT(sij_a > 0); + PPL_ASSERT(sij_b > 0); + + PPL_DIRTY_TEMP_COEFFICIENT(lhs_coeff); + PPL_DIRTY_TEMP_COEFFICIENT(rhs_coeff); + lhs_coeff = cst_a * sij_b; + rhs_coeff = cst_b * sij_a; + + if (ja == jb) { + // Same column: just compare the ratios. + // This works since all columns are lexico-positive. + // return cst_a * sij_b > cst_b * sij_a; + found_better_pivot = lhs_coeff > rhs_coeff; + } else { + + PPL_DIRTY_TEMP_COEFFICIENT(lhs); + PPL_DIRTY_TEMP_COEFFICIENT(rhs); + const dimension_type num_vars = mapping.size(); + dimension_type k = 0; + // While loop guard is: (k < num_rows && lhs == rhs). + // Return value is false, if k >= num_rows; lhs < rhs, otherwise. + // Try to optimize the computation of lhs and rhs. + while (true) { + const dimension_type mk = mapping[k]; + const bool in_base = basis[k]; + if (++k >= num_vars) { + found_better_pivot = false; + break; + } + if (in_base) { + // Reconstitute the identity submatrix part of tableau. + if (mk == ja) { + // Optimizing for: lhs == lhs_coeff && rhs == 0; + if (lhs_coeff == 0) + continue; + else { + found_better_pivot = lhs_coeff > 0; + break; + } + } + if (mk == jb) { + // Optimizing for: lhs == 0 && rhs == rhs_coeff; + if (rhs_coeff == 0) + continue; + else { + found_better_pivot = 0 > rhs_coeff; + break; + } + } + // Optimizing for: lhs == 0 && rhs == 0; + continue; + } else { + // Not in base. + PIP_Tree_Node::matrix_row_const_reference_type t_mk = s[mk]; + const Coefficient* t_mk_ja; + const Coefficient* t_mk_jb; + t_mk.get2(ja,jb,t_mk_ja,t_mk_jb); + lhs = lhs_coeff * *t_mk_ja; + rhs = rhs_coeff * *t_mk_jb; + if (lhs == rhs) + continue; + else { + found_better_pivot = lhs > rhs; + break; + } + } + } + } + + if (found_better_pivot) { pi = i->first; pj = i->second; }

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Tree.cc: fix comment in find_lexico_minimum_column_in_set().
by Marco Poletti 12 Mar '10

12 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 0eba4e70249005856bb09e6f647e2db00c6895b5 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0eba4e702490… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Mar 12 20:45:34 2010 +0100 PIP_Tree.cc: fix comment in find_lexico_minimum_column_in_set(). --- src/PIP_Tree.cc | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 595e1e0..e54b797 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -541,7 +541,7 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, break; } // lhs is actually the left-hand side with toggled sign. - // rhs is actually the left-hand side with toggled sign. + // rhs is actually the right-hand side with toggled sign. lhs = *sij_b * *row_ja; rhs = sij_a * *row_jb; if (lhs == rhs)

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Tree.cc: optimize find_lexico_minimum_column_in_set().
by Marco Poletti 12 Mar '10

12 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 8ee0ea5363e3037cc44b4172b660dbcf2003c004 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8ee0ea5363e3… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Mar 12 20:45:07 2010 +0100 PIP_Tree.cc: optimize find_lexico_minimum_column_in_set(). --- src/PIP_Tree.cc | 105 +++++++++++++++++++++++++++++++++++++++---------------- 1 files changed, 75 insertions(+), 30 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 98422b0..595e1e0 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -443,14 +443,19 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, if (i == i_end) // Only one candidate left, so it is the minimum. break; - PIP_Tree_Node::matrix_const_row_const_iterator last_itr - = pivot_row.lower_bound(min_column); - const Coefficient* sij_b = &(pivot_row.get(min_column)); + PIP_Tree_Node::matrix_const_row_const_iterator pivot_itr + = pivot_row.find(min_column); + PIP_Tree_Node::matrix_const_row_const_iterator pivot_end + = pivot_row.end(); + PPL_ASSERT(pivot_itr != pivot_end); + const Coefficient* sij_b = &((*pivot_itr).second); const dimension_type row_index = mapping[var_index]; const bool in_base = basis[var_index]; if (in_base) { for ( ; i!=i_end; ++i) { - const Coefficient& sij_a = pivot_row.get(*i); + pivot_itr = pivot_row.find(*i,pivot_itr); + PPL_ASSERT(pivot_itr != pivot_end); + const Coefficient& sij_a = (*pivot_itr).second; PPL_ASSERT(sij_a > 0); PPL_ASSERT(*sij_b > 0); @@ -485,33 +490,73 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, } } else { // Not in base. - for ( ; i!=i_end; ++i) { - const Coefficient& sij_a = pivot_row.get(*i); - PPL_ASSERT(sij_a > 0); - PPL_ASSERT(*sij_b > 0); - - PPL_DIRTY_TEMP_COEFFICIENT(lhs); - PPL_DIRTY_TEMP_COEFFICIENT(rhs); - bool found_better_candidate = false; - PIP_Tree_Node::matrix_row_const_reference_type t_mk = tableau[row_index]; - const Coefficient* t_mk_ja; - const Coefficient* t_mk_jb; - t_mk.get2(*i,min_column,t_mk_ja,t_mk_jb); - // lhs is actually the left-hand side with toggled sign. - // rhs is actually the left-hand side with toggled sign. - lhs = *sij_b * *t_mk_ja; - rhs = sij_a * *t_mk_jb; - if (lhs == rhs) - new_candidates.insert(*i); - else { - if (lhs < rhs) - found_better_candidate = true; + PIP_Tree_Node::matrix_row_const_reference_type row = tableau[row_index]; + PIP_Tree_Node::matrix_const_row_const_iterator row_last_itr + = row.find(min_column); + PIP_Tree_Node::matrix_const_row_const_iterator row_itr = row_last_itr; + PIP_Tree_Node::matrix_const_row_const_iterator row_end = row.end(); + const Coefficient* row_jb; + if (row_itr == row_end) { + // Found a zero element, keep only zero elements in the current row. + for (++i; i!=i_end; ++i) { + row_itr = row.find(*i,row_last_itr); + if (row_itr != row_end) { + row_last_itr = row_itr; + if ((*row_itr).second == 0) + new_candidates.insert(*i); + } else + new_candidates.insert(*i); } - if (found_better_candidate) { - new_candidates.clear(); - min_column = *i; - sij_b = &sij_a; - new_candidates.insert(min_column); + } else { + row_jb = &((*row_itr).second); + for ( ; i!=i_end; ++i) { + pivot_itr = pivot_row.find(*i,pivot_itr); + PPL_ASSERT(pivot_itr != pivot_end); + const Coefficient& sij_a = (*pivot_itr).second; + PPL_ASSERT(sij_a > 0); + PPL_ASSERT(*sij_b > 0); + + PPL_DIRTY_TEMP_COEFFICIENT(lhs); + PPL_DIRTY_TEMP_COEFFICIENT(rhs); + bool found_better_candidate = false; + row_itr = row.find(*i,row_last_itr); + const Coefficient* row_ja; + if (row_itr != row_end) { + row_last_itr = row_itr; + row_ja = &((*row_itr).second); + } else { + // Found a zero element, keep only zero elements in the current + // row. + new_candidates.clear(); + new_candidates.insert(*i); + for (++i; i!=i_end; ++i) { + row_itr = row.find(*i,row_last_itr); + if (row_itr != row_end) { + row_last_itr = row_itr; + if ((*row_itr).second == 0) + new_candidates.insert(*i); + } else + new_candidates.insert(*i); + } + break; + } + // lhs is actually the left-hand side with toggled sign. + // rhs is actually the left-hand side with toggled sign. + lhs = *sij_b * *row_ja; + rhs = sij_a * *row_jb; + if (lhs == rhs) + new_candidates.insert(*i); + else { + if (lhs < rhs) + found_better_candidate = true; + } + if (found_better_candidate) { + new_candidates.clear(); + min_column = *i; + row_jb = row_ja; + sij_b = &sij_a; + new_candidates.insert(min_column); + } } } }

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Tree.cc: some optimization and a fix to find_lexico_minimum_column_in_set().
by Marco Poletti 12 Mar '10

12 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 3727fe448996c44d2117f4301c9985ea24a626e2 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3727fe448996… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Mar 12 15:09:04 2010 +0100 PIP_Tree.cc: some optimization and a fix to find_lexico_minimum_column_in_set(). --- src/PIP_Tree.cc | 81 +++++++++++++++++++++++++++++++++--------------------- 1 files changed, 49 insertions(+), 32 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 18d9dc5..98422b0 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -440,21 +440,23 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, new_candidates.insert(*i); dimension_type min_column = *i; ++i; + if (i == i_end) + // Only one candidate left, so it is the minimum. + break; + PIP_Tree_Node::matrix_const_row_const_iterator last_itr + = pivot_row.lower_bound(min_column); const Coefficient* sij_b = &(pivot_row.get(min_column)); - for ( ; i!=i_end; ++i) { - const Coefficient& sij_a = pivot_row.get(*i); - PPL_ASSERT(sij_a > 0); - PPL_ASSERT(*sij_b > 0); - - PPL_DIRTY_TEMP_COEFFICIENT(lhs); - PPL_DIRTY_TEMP_COEFFICIENT(rhs); - dimension_type k = var_index; - const dimension_type mk = mapping[k]; - const bool in_base = basis[k]; - bool found_better_candidate = false; - if (in_base) { + const dimension_type row_index = mapping[var_index]; + const bool in_base = basis[var_index]; + if (in_base) { + for ( ; i!=i_end; ++i) { + const Coefficient& sij_a = pivot_row.get(*i); + PPL_ASSERT(sij_a > 0); + PPL_ASSERT(*sij_b > 0); + + bool found_better_candidate = false; // Reconstitute the identity submatrix part of tableau. - if (mk == *i) { + if (row_index == *i) { // Optimizing for: lhs == lhs_coeff && rhs == 0; if (*sij_b == 0) new_candidates.insert(*i); @@ -462,21 +464,36 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, if (*sij_b < 0) found_better_candidate = true; } - } - if (mk == min_column) { - // Optimizing for: lhs == 0 && rhs == rhs_coeff; - if (sij_a == 0) + } else + if (row_index == min_column) { + // Optimizing for: lhs == 0 && rhs == rhs_coeff; + if (sij_a == 0) + new_candidates.insert(*i); + else { + if (0 < sij_a) + found_better_candidate = true; + } + } else + // Optimizing for: lhs == 0 && rhs == 0; new_candidates.insert(*i); - else { - if (0 < sij_a) - found_better_candidate = true; - } + if (found_better_candidate) { + new_candidates.clear(); + min_column = *i; + sij_b = &sij_a; + new_candidates.insert(min_column); } - // Optimizing for: lhs == 0 && rhs == 0; - new_candidates.insert(*i); - } else { - // Not in base. - PIP_Tree_Node::matrix_row_const_reference_type t_mk = tableau[mk]; + } + } else { + // Not in base. + for ( ; i!=i_end; ++i) { + const Coefficient& sij_a = pivot_row.get(*i); + PPL_ASSERT(sij_a > 0); + PPL_ASSERT(*sij_b > 0); + + PPL_DIRTY_TEMP_COEFFICIENT(lhs); + PPL_DIRTY_TEMP_COEFFICIENT(rhs); + bool found_better_candidate = false; + PIP_Tree_Node::matrix_row_const_reference_type t_mk = tableau[row_index]; const Coefficient* t_mk_ja; const Coefficient* t_mk_jb; t_mk.get2(*i,min_column,t_mk_ja,t_mk_jb); @@ -490,12 +507,12 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, if (lhs < rhs) found_better_candidate = true; } - } - if (found_better_candidate) { - new_candidates.clear(); - min_column = *i; - sij_b = &sij_a; - new_candidates.insert(min_column); + if (found_better_candidate) { + new_candidates.clear(); + min_column = *i; + sij_b = &sij_a; + new_candidates.insert(min_column); + } } } std::swap(candidates,new_candidates);

1 0

[GIT] ppl/ppl(sparse_matrices): Delete file PIP_Tree.cc. master added by mistake.
by Marco Poletti 12 Mar '10

12 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: b8eeddf5ccdc255e6be751e84c424f7b1d510810 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b8eeddf5ccdc… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Mar 12 14:18:30 2010 +0100 Delete file PIP_Tree.cc.master added by mistake. --- src/PIP_Tree.cc.master | 2707 ------------------------------------------------ 1 files changed, 0 insertions(+), 2707 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=b8eeddf5…

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Tree.cc: some little optimizations to find_lexico_minimum_column_in_set().
by Marco Poletti 12 Mar '10

12 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 0a92d18cae3f6b93a4e8d3209269962b45407558 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0a92d18cae3f… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Mar 12 14:15:48 2010 +0100 PIP_Tree.cc: some little optimizations to find_lexico_minimum_column_in_set(). --- src/PIP_Tree.cc | 26 ++++++++++++-------------- 1 files changed, 12 insertions(+), 14 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 491a6e3..18d9dc5 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -440,16 +440,11 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, new_candidates.insert(*i); dimension_type min_column = *i; ++i; + const Coefficient* sij_b = &(pivot_row.get(min_column)); for ( ; i!=i_end; ++i) { const Coefficient& sij_a = pivot_row.get(*i); - const Coefficient& sij_b = pivot_row.get(min_column); PPL_ASSERT(sij_a > 0); - PPL_ASSERT(sij_b > 0); - - PPL_DIRTY_TEMP_COEFFICIENT(lhs_coeff); - PPL_DIRTY_TEMP_COEFFICIENT(rhs_coeff); - lhs_coeff = -sij_b; - rhs_coeff = -sij_a; + PPL_ASSERT(*sij_b > 0); PPL_DIRTY_TEMP_COEFFICIENT(lhs); PPL_DIRTY_TEMP_COEFFICIENT(rhs); @@ -461,19 +456,19 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, // Reconstitute the identity submatrix part of tableau. if (mk == *i) { // Optimizing for: lhs == lhs_coeff && rhs == 0; - if (lhs_coeff == 0) + if (*sij_b == 0) new_candidates.insert(*i); else { - if (lhs_coeff > 0) + if (*sij_b < 0) found_better_candidate = true; } } if (mk == min_column) { // Optimizing for: lhs == 0 && rhs == rhs_coeff; - if (rhs_coeff == 0) + if (sij_a == 0) new_candidates.insert(*i); else { - if (0 > rhs_coeff) + if (0 < sij_a) found_better_candidate = true; } } @@ -485,18 +480,21 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, const Coefficient* t_mk_ja; const Coefficient* t_mk_jb; t_mk.get2(*i,min_column,t_mk_ja,t_mk_jb); - lhs = lhs_coeff * *t_mk_ja; - rhs = rhs_coeff * *t_mk_jb; + // lhs is actually the left-hand side with toggled sign. + // rhs is actually the left-hand side with toggled sign. + lhs = *sij_b * *t_mk_ja; + rhs = sij_a * *t_mk_jb; if (lhs == rhs) new_candidates.insert(*i); else { - if (lhs > rhs) + if (lhs < rhs) found_better_candidate = true; } } if (found_better_candidate) { new_candidates.clear(); min_column = *i; + sij_b = &sij_a; new_candidates.insert(min_column); } }

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Tree.cc: prepare find_lexico_minimum_column_in_set() for optimization (#2).
by Marco Poletti 12 Mar '10

12 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: e9854a3c37f53b0edaa43b4ca0970b007b7bb281 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e9854a3c37f5… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Mar 12 14:03:09 2010 +0100 PIP_Tree.cc: prepare find_lexico_minimum_column_in_set() for optimization (#2). --- src/PIP_Tree.cc | 86 +++++++++++++++++++++++++++---------------------------- 1 files changed, 42 insertions(+), 44 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 0d0d95d..491a6e3 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -429,81 +429,79 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, const std::vector<bool>& basis, PIP_Tree_Node:: matrix_row_const_reference_type pivot_row) { - std::set<dimension_type>::iterator i = candidates.begin(); - std::set<dimension_type>::iterator i_end = candidates.end(); + const dimension_type num_vars = mapping.size(); PPL_ASSERT(!candidates.empty()); - dimension_type min_index = *i; - ++i; - for ( ; i!=i_end; ++i) { - bool found_better_candidate; - const Coefficient& sij_a = pivot_row.get(*i); - const Coefficient& sij_b = pivot_row.get(min_index); - PPL_ASSERT(sij_a > 0); - PPL_ASSERT(sij_b > 0); - - PPL_DIRTY_TEMP_COEFFICIENT(lhs_coeff); - PPL_DIRTY_TEMP_COEFFICIENT(rhs_coeff); - lhs_coeff = -sij_b; - rhs_coeff = -sij_a; - - PPL_DIRTY_TEMP_COEFFICIENT(lhs); - PPL_DIRTY_TEMP_COEFFICIENT(rhs); - const dimension_type num_vars = mapping.size(); - dimension_type k = 0; - // While loop guard is: (k < num_rows && lhs == rhs). - // Return value is false, if k >= num_rows; lhs < rhs, otherwise. - // Try to optimize the computation of lhs and rhs. - while (true) { + for (dimension_type var_index = 0; var_index < num_vars; ++var_index) { + std::set<dimension_type> new_candidates; + std::set<dimension_type>::iterator i = candidates.begin(); + std::set<dimension_type>::iterator i_end = candidates.end(); + PPL_ASSERT(!candidates.empty()); + new_candidates.insert(*i); + dimension_type min_column = *i; + ++i; + for ( ; i!=i_end; ++i) { + const Coefficient& sij_a = pivot_row.get(*i); + const Coefficient& sij_b = pivot_row.get(min_column); + PPL_ASSERT(sij_a > 0); + PPL_ASSERT(sij_b > 0); + + PPL_DIRTY_TEMP_COEFFICIENT(lhs_coeff); + PPL_DIRTY_TEMP_COEFFICIENT(rhs_coeff); + lhs_coeff = -sij_b; + rhs_coeff = -sij_a; + + PPL_DIRTY_TEMP_COEFFICIENT(lhs); + PPL_DIRTY_TEMP_COEFFICIENT(rhs); + dimension_type k = var_index; const dimension_type mk = mapping[k]; const bool in_base = basis[k]; - if (++k >= num_vars) { - found_better_candidate = false; - break; - } + bool found_better_candidate = false; if (in_base) { // Reconstitute the identity submatrix part of tableau. if (mk == *i) { // Optimizing for: lhs == lhs_coeff && rhs == 0; if (lhs_coeff == 0) - continue; + new_candidates.insert(*i); else { - found_better_candidate = lhs_coeff > 0; - break; + if (lhs_coeff > 0) + found_better_candidate = true; } } - if (mk == min_index) { + if (mk == min_column) { // Optimizing for: lhs == 0 && rhs == rhs_coeff; if (rhs_coeff == 0) - continue; + new_candidates.insert(*i); else { - found_better_candidate = 0 > rhs_coeff; - break; + if (0 > rhs_coeff) + found_better_candidate = true; } } // Optimizing for: lhs == 0 && rhs == 0; - continue; + new_candidates.insert(*i); } else { // Not in base. PIP_Tree_Node::matrix_row_const_reference_type t_mk = tableau[mk]; const Coefficient* t_mk_ja; const Coefficient* t_mk_jb; - t_mk.get2(*i,min_index,t_mk_ja,t_mk_jb); + t_mk.get2(*i,min_column,t_mk_ja,t_mk_jb); lhs = lhs_coeff * *t_mk_ja; rhs = rhs_coeff * *t_mk_jb; if (lhs == rhs) - continue; + new_candidates.insert(*i); else { - found_better_candidate = lhs > rhs; - break; + if (lhs > rhs) + found_better_candidate = true; } } + if (found_better_candidate) { + new_candidates.clear(); + min_column = *i; + new_candidates.insert(min_column); + } } - if (found_better_candidate) - min_index = *i; + std::swap(candidates,new_candidates); } - candidates.clear(); - candidates.insert(min_index); } /* Find the column j in revised simplex tableau such as

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Tree.cc: prepare find_lexico_minimum_column_in_set() for optimization.
by Marco Poletti 12 Mar '10

12 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 8611bb81ec29979c5b5c3c4b95437a615888eab6 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8611bb81ec29… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Mar 12 13:37:16 2010 +0100 PIP_Tree.cc: prepare find_lexico_minimum_column_in_set() for optimization. --- src/PIP_Tree.cc | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 files changed, 66 insertions(+), 3 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index b0ead97..0d0d95d 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -435,10 +435,73 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, PPL_ASSERT(!candidates.empty()); dimension_type min_index = *i; ++i; - for ( ; i!=i_end; ++i) - if (column_lower(tableau, mapping, basis, - pivot_row, *i, pivot_row, min_index)) + for ( ; i!=i_end; ++i) { + bool found_better_candidate; + const Coefficient& sij_a = pivot_row.get(*i); + const Coefficient& sij_b = pivot_row.get(min_index); + PPL_ASSERT(sij_a > 0); + PPL_ASSERT(sij_b > 0); + + PPL_DIRTY_TEMP_COEFFICIENT(lhs_coeff); + PPL_DIRTY_TEMP_COEFFICIENT(rhs_coeff); + lhs_coeff = -sij_b; + rhs_coeff = -sij_a; + + PPL_DIRTY_TEMP_COEFFICIENT(lhs); + PPL_DIRTY_TEMP_COEFFICIENT(rhs); + const dimension_type num_vars = mapping.size(); + dimension_type k = 0; + // While loop guard is: (k < num_rows && lhs == rhs). + // Return value is false, if k >= num_rows; lhs < rhs, otherwise. + // Try to optimize the computation of lhs and rhs. + while (true) { + const dimension_type mk = mapping[k]; + const bool in_base = basis[k]; + if (++k >= num_vars) { + found_better_candidate = false; + break; + } + if (in_base) { + // Reconstitute the identity submatrix part of tableau. + if (mk == *i) { + // Optimizing for: lhs == lhs_coeff && rhs == 0; + if (lhs_coeff == 0) + continue; + else { + found_better_candidate = lhs_coeff > 0; + break; + } + } + if (mk == min_index) { + // Optimizing for: lhs == 0 && rhs == rhs_coeff; + if (rhs_coeff == 0) + continue; + else { + found_better_candidate = 0 > rhs_coeff; + break; + } + } + // Optimizing for: lhs == 0 && rhs == 0; + continue; + } else { + // Not in base. + PIP_Tree_Node::matrix_row_const_reference_type t_mk = tableau[mk]; + const Coefficient* t_mk_ja; + const Coefficient* t_mk_jb; + t_mk.get2(*i,min_index,t_mk_ja,t_mk_jb); + lhs = lhs_coeff * *t_mk_ja; + rhs = rhs_coeff * *t_mk_jb; + if (lhs == rhs) + continue; + else { + found_better_candidate = lhs > rhs; + break; + } + } + } + if (found_better_candidate) min_index = *i; + } candidates.clear(); candidates.insert(min_index); }

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Tree.cc: revert optimizations in find_lexico_minimum_column_in_set().
by Marco Poletti 12 Mar '10

12 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 03b2447d787362554a1ebd786f9dd5216a782308 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=03b2447d7873… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Mar 12 13:28:11 2010 +0100 PIP_Tree.cc: revert optimizations in find_lexico_minimum_column_in_set(). --- src/PIP_Tree.cc | 70 +-- src/PIP_Tree.cc.master | 2707 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 2718 insertions(+), 59 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=03b2447d…

1 0

[GIT] ppl/ppl(floating_point): New commits
by Roberto Bagnara 12 Mar '10

12 Mar '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6060bda39a0f… Author: François Galea <francois.galea(a)uvsq.fr> Date: Thu Mar 11 19:58:03 2010 +0100 Documentation fixes. Added a paragraph about optimizing a linear cost function. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ed91bdf10a46… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Wed Mar 10 18:29:05 2010 +0100 Improved checks in PIP_Decision_Node::OK() method. There is no reason to have Artificial_Parameter::OK() inlined. Added a couple of comments on code that should be normally unreachable. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=61b4c1817137… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Wed Mar 10 18:27:08 2010 +0100 Fixed documentation reference. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=374f46632936… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Wed Mar 10 17:14:26 2010 +0100 Fixed the value of INPUT doxygen configuration variable. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=65156364caa2… Author: François Galea <francois.galea(a)uvsq.fr> Date: Tue Mar 9 20:28:29 2010 +0100 Added two paragraphs about uses of the big parameter in the documentation. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2d43c54ada25… Author: François Galea <francois.galea(a)uvsq.fr> Date: Mon Mar 8 07:56:00 2010 +0100 Documentation fixes. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=114f0e384745… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Tue Mar 9 13:36:12 2010 +0400 Updated. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f06b3826db77… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Tue Mar 9 13:31:49 2010 +0400 Missing files added. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4e2cacd97386… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Tue Mar 9 08:52:23 2010 +0400 Restored line erased by mistake.

1 0