[PPL-devel] [GIT] ppl/ppl(pip): Added generation of non-parametric cuts.

[François Galea]

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

Author: François Galea <francois.galea at uvsq.fr>
Date:   Tue Oct  6 11:32:17 2009 +0200

Added generation of non-parametric cuts.

---

 src/PIP_Tree.cc |  121 ++++++++++++++++++++++++++++++-------------------------
 1 files changed, 66 insertions(+), 55 deletions(-)

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index 31a0120..e4ff584 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -1248,73 +1248,84 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref, const Matrix& ctx,
                   << "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());
-        context.add_zero_columns(1);
 
-        // Generate new artificial parameter
+        // Test if cut to be generated must be parametric or not
+        const Row& row_t1 = tableau.t[i];
+        for (j=1; j<num_params; ++j) {
+          if (row_t1[j] % d != 0) {
+            tableau.t.add_zero_columns(1);
+            context.add_zero_columns(1);
+            break;
+          }
+        }
+
         const Row& row_t = tableau.t[i];
-        Linear_Expression e;
-        Variables_Set::const_iterator p;
-        mod_assign(mod, row_t[0], d);
-        if (mod != 0)
-          e += (d-mod);
-        for (p=parameters.begin(), j=1; j<num_params; ++j, ++p) {
-          mod_assign(mod, row_t[j], d);
+        Row& cut_s = tableau.s[num_rows];
+        Row& cut_t = tableau.t[num_rows];
+
+        if (j < num_params) {
+          // Fractional parameter coefficient found: generate parametric cut
+          // Generate new artificial parameter
+          Linear_Expression e;
+          Variables_Set::const_iterator p;
+          mod_assign(mod, row_t[0], d);
           if (mod != 0)
-            e += (d-mod) * Variable(*p);
-        }
-        artificial_parameters.push_back(Artificial_Parameter(e, d));
-        parameters.insert(space_dimension);
+            e += (d-mod);
+          for (p=parameters.begin(), j=1; j<num_params; ++j, ++p) {
+            mod_assign(mod, row_t[j], d);
+            if (mod != 0)
+              e += (d-mod) * Variable(*p);
+          }
+          artificial_parameters.push_back(Artificial_Parameter(e, d));
+          parameters.insert(space_dimension);
 #ifdef NOISY_PIP
-        using namespace IO_Operators;
-        std::cout << "Creating new parameter " << Variable(space_dimension)
-                  << " = (" << e << ")/" << d
-                  << std::endl;
+          using namespace IO_Operators;
+          std::cout << "Creating new parameter " << Variable(space_dimension)
+                    << " = (" << e << ")/" << d
+                    << std::endl;
 #endif
-        ++space_dimension;
-
-        // Update current context with constraints on the new parameter
-        Row ctx1(num_params+1, Row::Flags());
-        Row ctx2(num_params+1, Row::Flags());
-        for (j=0; j<num_params; ++j) {
-          mod_assign(mod, row_t[j], d);
-          if (mod != 0) {
-            ctx1[j] = d - mod;
-            ctx2[j] = -ctx1[j];
-          } else {
-            ctx1[j] = 0;
-            ctx2[j] = 0;
+          ++space_dimension;
+
+          // Update current context with constraints on the new parameter
+          Row ctx1(num_params+1, Row::Flags());
+          Row ctx2(num_params+1, Row::Flags());
+          for (j=0; j<num_params; ++j) {
+            mod_assign(mod, row_t[j], d);
+            if (mod != 0) {
+              ctx1[j] = d - mod;
+              ctx2[j] = -ctx1[j];
+            } else {
+              ctx1[j] = 0;
+              ctx2[j] = 0;
+            }
           }
-        }
-        ctx1[num_params] = -d;
-        ctx2[num_params] = d;
-        ctx2[0] += d-1;
+          ctx1[num_params] = -d;
+          ctx2[num_params] = d;
+          ctx2[0] += d-1;
 #ifdef NOISY_PIP
-        {
-          Variables_Set::const_iterator p = parameters.begin();
-          Linear_Expression e1;
-          Linear_Expression e2;
-          for (j=1; j<=num_params; ++j, ++p) {
-            e1 += ctx1[j] * Variable(*p);
-            e2 += ctx2[j] * Variable(*p);
+          {
+            Variables_Set::const_iterator p = parameters.begin();
+            Linear_Expression e1;
+            Linear_Expression e2;
+            for (j=1; j<=num_params; ++j, ++p) {
+              e1 += ctx1[j] * Variable(*p);
+              e2 += ctx2[j] * Variable(*p);
+            }
+            e1 += ctx1[0];
+            e2 += ctx2[0];
+            std::cout << "Inserting into context: "
+                      << Constraint(e1 >= 0) << " ; "
+                      << Constraint(e2 >= 0) << std::endl;
           }
-          e1 += ctx1[0];
-          e2 += ctx2[0];
-          std::cout << "Inserting into context: "
-                    << Constraint(e1 >= 0) << " ; "
-                    << Constraint(e2 >= 0) << std::endl;
-        }
 #endif
-        context.add_row(ctx1);
-        context.add_row(ctx2);
+          context.add_row(ctx1);
+          context.add_row(ctx2);
+          cut_t[num_params] = d*d;
+        }
 
         // Generate new cut
-        Row& cut_s = tableau.s[num_rows];
-        Row& cut_t = tableau.t[num_rows];
-        //const Row& row_t = tableau.t[i];
         const Row& row_s = tableau.s[i];
         for (j=0; j<num_vars; ++j) {
           mod_assign(mod, row_s[j], d);
@@ -1327,9 +1338,9 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref, const Matrix& ctx,
           else
             cut_t[j] = 0;
         }
-        cut_t[num_params] = d*d;
 #ifdef NOISY_PIP
         {
+          using namespace IO_Operators;
           Linear_Expression e;
           dimension_type ti = 1;
           dimension_type si = 0;