[PPL-devel] [GIT] ppl/ppl(pip): Added code for selection of the deepest cut.

[François Galea]

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

Author: François Galea <francois.galea at 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);