[PPL-devel] [GIT] ppl/ppl(pip): Added a rule to the cut methods to always choose the simplest parametric part .

[François Galea]

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

Author: François Galea <francois.galea at uvsq.fr>
Date:   Thu Nov 19 15:20:58 2009 +0100

Added a rule to the cut methods to always choose the simplest parametric part.

This tends to provide simpler solution trees on some problems.

---

 src/PIP_Tree.cc |   52 +++++++++++++++++++++++++++++++++++++++++++++-------
 1 files changed, 45 insertions(+), 7 deletions(-)

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index 138a215..e868427 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -1736,14 +1736,36 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref,
         PPL_DIRTY_TEMP_COEFFICIENT(mod);
         if (problem.control_parameters[PIP_CUTTING_STRATEGY]
             == PIP_CUTTING_STRATEGY_FIRST) {
-          /* Just choose the row corresponding to variable i */
-          i = mapping[i];
+          // Find the first row with simplest parametric part.
+          dimension_type best_i = n_a_d;
+          dimension_type best_pcount = n_a_d;
+          dimension_type pcount;
+          for (i_ = 0; i_ < num_vars; ++i_) {
+            if (basis[i_])
+              continue;
+            i = mapping[i_];
+            const Row& row_t = tableau.t[i];
+            pcount = 0;
+            for (j = 0; j < num_params; ++j) {
+              mod_assign(mod, row_t[j], d);
+              if (mod != 0)
+                ++pcount;
+            }
+            if (pcount != 0 && (best_i == n_a_d || (pcount < best_pcount))) {
+              best_pcount = pcount;
+              best_i = i;
+            }
+          }
+          i = best_i;
         } else /* PIP_CUTTING_STRATEGY_DEEPEST */ {
-          /* Look for the row which will generate the "deepest" cut */
+          /* Find the row with simplest parametric part which will generate
+            the "deepest" cut */
           PPL_DIRTY_TEMP_COEFFICIENT(score);
           PPL_DIRTY_TEMP_COEFFICIENT(score2);
-          Coefficient best = 0;
+          Coefficient best_score = 0;
           dimension_type best_i = n_a_d;
+          dimension_type best_pcount = n_a_d;
+          dimension_type pcount;
           for (i_ = 0; i_ < num_vars; ++i_) {
             if (basis[i_])
               continue;
@@ -1751,10 +1773,13 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref,
             const Row& row_t = tableau.t[i];
             const Row& row_s = tableau.s[i];
             score = 0;
+            pcount = 0;
             for (j = 0; j < num_params; ++j) {
               mod_assign(mod, row_t[j], d);
-              if (mod != 0)
+              if (mod != 0) {
                 score += d - mod;
+                ++pcount;
+              }
             }
             score2 = 0;
             for (j = 0; j < num_vars; ++j) {
@@ -1762,8 +1787,21 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref,
               score2 += d - mod;
             }
             score *= score2;
-            if (best_i == n_a_d || score > best) {
-              best = score;
+            /* Choose row i if:
+              row i is non-integer
+              AND (no row has been chosen yet
+                   OR row i has number of non-integer parameter
+                      coefficients lower than the current best row
+                   OR row i has the same number of non-integer parameter
+                      coefficients as the current best row, and its score is
+                      better)
+            */
+            if (pcount != 0
+                && (best_i == n_a_d
+                    || (pcount < best_pcount)
+                    || (pcount == best_pcount && score > best_score))) {
+              best_score = score;
+              best_pcount = pcount;
               best_i = i;
             }
           }