[PPL-devel] [GIT] ppl/ppl(pip): Implemented additional steps of the simplex algorithm.

[François Galea]

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

Author: François Galea <francois.galea at uvsq.fr>
Date:   Wed Sep 16 15:24:24 2009 +0200

Implemented additional steps of the simplex algorithm.
 - handling of simplex rows with mixed parameter sign;
 - handling of tautology expressions;
 - handling of splitting a solution according to a test parametric expression.

---

 src/PIP_Tree.cc      |  112 ++++++++++++++++++++++++++++++++++++++++++++++++-
 src/PIP_Tree.defs.hh |    3 +
 2 files changed, 112 insertions(+), 3 deletions(-)

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index edc073f..d528d37 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -74,7 +74,8 @@ PIP_Tree_Node::PIP_Tree_Node(const PIP_Tree_Node &x)
 
 PIP_Decision_Node::~PIP_Decision_Node() {
   delete true_child;
-  delete false_child;
+  if (false_child)
+    delete false_child;
 }
 
 PIP_Solution_Node::~PIP_Solution_Node() {
@@ -196,6 +197,14 @@ PIP_Tree_Node::OK() const {
   return true;
 }
 
+void
+PIP_Tree_Node::add_constraint(const Row &row) {
+  Linear_Expression e;
+  for (dimension_type j=row.size(); j-- > 1; )
+    e += row[j] * Variable(j-1);
+  constraints_.insert(e + row[0] >= 0);
+}
+
 bool
 PIP_Solution_Node::OK() const {
   /* FIXME: finish me! */
@@ -526,7 +535,7 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref,
 
   // Main loop of the simplex algorithm
   for(;;) {
-    dimension_type i;
+    dimension_type i, j;
     dimension_type i_ = n_a_d;
     dimension_type i__ = n_a_d;
     dimension_type num_rows = tableau.t.num_rows();
@@ -590,7 +599,7 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref,
       std::cout << "Found row with negative parameters: " << i_
                 << std::endl;
 #endif
-      dimension_type j, k;
+      dimension_type k;
       Coefficient z(0);
       Coefficient sij, cij, cij_;
       Coefficient c;
@@ -738,6 +747,103 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref,
         c /= sij;
       }
     }
+
+    /* Otherwise, we have found a row i__ with mixed parameter sign. */
+    else if (i__ != n_a_d) {
+      dimension_type neg = n_a_d;
+      Coefficient ns, score;
+
+      /* Look for a constraint with mixed parameter sign with no positive
+       * variable coefficients */
+      for (i=i__; i<num_rows; ++i) {
+        if (sign[i] != MIXED)
+          continue;
+        for (j=0; j<num_vars; ++j) {
+          if (tableau.s[i][j] > 0)
+            break;
+        }
+        /* Choose row with lowest score, potentially eliminating
+         * implicated tautologies if some exist */
+        if (j == num_vars) {
+          score = 0;
+          for (j=0; j<num_params; ++j)
+            score += tableau.t[i][j];
+          if (neg == n_a_d || score < ns) {
+            neg = i;
+            ns = score;
+          }
+        }
+      }
+      if (neg != n_a_d) {
+        i = neg;
+#ifdef NOISY_PIP
+        std::cout << "Found row with unknown parameter sign and negative "
+                     "variable coefficients: " << i
+                  << std::endl;
+#endif
+        Row &r = tableau.t[i];
+        context.add_row(r);
+        add_constraint(r);
+#ifdef NOISY_PIP
+        Linear_Expression e;
+        for (j=1; j<num_params; ++j)
+          e += r[j] * Variable(j-1);
+        Constraint c(e + r[0] >= 0);
+        std::cout << "Adding tautology: " << c
+                  << std::endl;
+#endif
+      } else {
+#ifdef NOISY_PIP
+        std::cout << "Found row with mixed parameter sign: " << i__
+                  << std::endl
+                  << "Solution depends on the sign of parameter"
+                  << std::endl;
+#endif
+        Row test(tableau.t[i__]);
+
+        /* Create a solution Node to become "true" version of current Node */
+        PIP_Tree_Node *tru = new PIP_Solution_Node(*this, true);
+        context.add_row(test);
+        PIP_Problem_Status status_t = tru->solve(tru, context);
+
+        /* Modify *this to become "false" version */
+        Constraint_System cs;
+        cs.swap(constraints_);
+        PIP_Tree_Node *fals = this;
+        Row &testf = context[context.num_rows()-1];
+        negate_assign(testf, test);
+        PIP_Problem_Status status_f = solve(fals, context);
+
+        if (status_t == UNFEASIBLE_PIP_PROBLEM
+            && status_f == UNFEASIBLE_PIP_PROBLEM) {
+          parent_ref = 0;
+          return UNFEASIBLE_PIP_PROBLEM;
+        } else if (status_t == UNFEASIBLE_PIP_PROBLEM) {
+          cs.swap(constraints_);
+          add_constraint(testf);
+          return OPTIMIZED_PIP_PROBLEM;
+        } else if (status_f == UNFEASIBLE_PIP_PROBLEM) {
+          cs.swap(tru->constraints_);
+          tru->add_constraint(test);
+          parent_ref = tru;
+          return OPTIMIZED_PIP_PROBLEM;
+        }
+
+        /* Create a decision Node to become parent of current Node */
+        PIP_Decision_Node *parent = new PIP_Decision_Node(fals, tru);
+        parent->add_constraint(test);
+
+        if (!cs.empty()) {
+          /* If node to be solved had tautologies, store them in a new
+             decision node */
+          parent = new PIP_Decision_Node(0, parent);
+          cs.swap(parent->constraints_);
+        }
+
+        parent_ref = parent;
+        return OPTIMIZED_PIP_PROBLEM;
+      }
+    }
     //FIXME: to be finished
 
   } // Main loop of the simplex algorithm
diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh
index cb41f49..f23bf31 100644
--- a/src/PIP_Tree.defs.hh
+++ b/src/PIP_Tree.defs.hh
@@ -129,6 +129,9 @@ protected:
   */
   virtual PIP_Problem_Status solve(PIP_Tree_Node*& parent_ref,
                                    const Matrix& context) = 0;
+
+  //! Inserts a new parametric constraint in internal Row format
+  void add_constraint(const Row &x);
 };
 
 //! A tree node representing part of the space of solutions.