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

Author: François Galea francois.galea@uvsq.fr Date: Mon Oct 5 08:46:45 2009 +0200

Added code for selection of the deepest cut.

---

src/PIP_Tree.cc | 22 +++++++++++++++++++++- 1 files changed, 21 insertions(+), 1 deletions(-)

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 0e7c211..bb47121 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -1213,11 +1213,32 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref, const Matrix& ctx, } else { /* The solution is non-integer. We have to generate a cut. */ + Coefficient mod; + /* Look for row which will generate the "deepest" cut */ + Coefficient score; + Coefficient best = 0; + dimension_type best_i = i; + for (i_ = i; i_ < num_rows; ++i_) { + const Row& row = tableau.t[i_]; + score = 0; + for (j = 0; j < num_params; ++j) { + mod_assign(mod, row[j], d); + if (mod != 0) + score += d - mod; + } + if (score > best) { + best = score; + best_i = i_; + } + } + i = best_i; + #ifdef NOISY_PIP std::cout << "Row " << i << " contains non-integer coefficients. " << "Cut generation required." << std::endl; #endif + tableau.t.add_zero_columns(1); tableau.s.add_zero_rows(1, Row::Flags()); tableau.t.add_zero_rows(1, Row::Flags()); @@ -1227,7 +1248,6 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref, const Matrix& ctx, const Row& row_t = tableau.t[i]; Linear_Expression e; Variables_Set::const_iterator p; - Coefficient mod; mod_assign(mod, row_t[0], d); if (mod != 0) e += (d-mod);