[PPL-devel] [GIT] ppl/ppl(pip): Added mechanism for fetching parametric values for variables.

[François Galea]

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

Author: François Galea <francois.galea at uvsq.fr>
Date:   Tue Sep 22 09:31:27 2009 +0200

Added mechanism for fetching parametric values for variables.

---

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

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index b81d10b..9d8197c 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -89,7 +89,9 @@ PIP_Solution_Node::PIP_Solution_Node(PIP_Problem* p)
     tableau(),
     basis(),
     mapping(),
-    sign() {
+    sign(),
+    solution(),
+    solution_valid(false) {
 }
 
 PIP_Solution_Node::PIP_Solution_Node(const PIP_Solution_Node &x)
@@ -97,7 +99,9 @@ PIP_Solution_Node::PIP_Solution_Node(const PIP_Solution_Node &x)
     tableau(x.tableau),
     basis(x.basis),
     mapping(x.mapping),
-    sign(x.sign) {
+    sign(x.sign),
+    solution(x.solution),
+    solution_valid(x.solution_valid) {
 }
 
 PIP_Solution_Node::PIP_Solution_Node(const PIP_Solution_Node &x,
@@ -106,7 +110,9 @@ PIP_Solution_Node::PIP_Solution_Node(const PIP_Solution_Node &x,
     tableau(x.tableau),
     basis(x.basis),
     mapping(x.mapping),
-    sign(x.sign) {
+    sign(x.sign),
+    solution(x.solution),
+    solution_valid(x.solution_valid) {
   if (!empty_constraints)
     constraints_ = x.constraints_;
 }
@@ -407,10 +413,35 @@ PIP_Solution_Node::ascii_load(std::istream& s) {
   if (!tableau.t.ascii_load(s))
     return false;
 
+  solution_valid = false;
   PPL_ASSERT(OK());
   return true;
 }
 
+const Linear_Expression&
+PIP_Solution_Node::parametric_values(Variable v) {
+  update_solution();
+  Variables_Set& parameters = problem->parameters;
+  dimension_type id = v.id();
+  dimension_type j;
+  Variables_Set::iterator location = parameters.lower_bound(id);
+  if (location == parameters.end())
+    j = id;
+  else {
+    if (*location == id) {
+#ifndef NDEBUG
+      std::cerr << "PIP_Solution_Node::parametric_values(Variable): "
+                   "Supplied Variable corresponds to a parameter"
+                << std::endl;
+#endif
+      j = not_a_dimension();
+    } else
+      j = id - std::distance(parameters.begin(),location) - 1;
+  }
+
+  return solution[j];
+}
+
 PIP_Solution_Node::Row_Sign
 PIP_Solution_Node::row_sign(const Row &x) {
   PIP_Solution_Node::Row_Sign sign = ZERO;
@@ -581,6 +612,30 @@ PIP_Solution_Node::update_tableau(PIP_Tree_Node ** /* parent_ref */,
   // FIXME: decide emptiness detection (and node removal)
 }
 
+void
+PIP_Solution_Node::update_solution() {
+  if (solution_valid)
+    return;
+  dimension_type num_vars = tableau.s.num_columns();
+  if (solution.size() != num_vars)
+    solution.resize(num_vars);
+  for (dimension_type i = num_vars; i-- > 0; ) {
+    Linear_Expression &sol = solution[i];
+    if (basis[i]) {
+      sol = Linear_Expression(0);
+    } else {
+      Row &row = tableau.t[mapping[i]];
+      sol = Linear_Expression(row[0]);
+      dimension_type k;
+      Variables_Set::iterator j;
+      Variables_Set::iterator j_end = problem->parameters.end();
+      for (j = problem->parameters.begin(), k = 1; j != j_end; ++j, ++k)
+        sol += row[k] * Variable(*j);
+    }
+  }
+  solution_valid = true;
+}
+
 PIP_Problem_Status
 PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref,
                          const Matrix& ctx) {
@@ -802,6 +857,7 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref,
         }
         c /= sij;
       }
+      solution_valid = false;
     }
 
     /* Otherwise, we have found a row i__ with mixed parameter sign. */
diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh
index fcbd62e..238ef5b 100644
--- a/src/PIP_Tree.defs.hh
+++ b/src/PIP_Tree.defs.hh
@@ -276,6 +276,12 @@ private:
   //! A cache for computed sign values of constraint parametric RHS.
   std::vector<Row_Sign> sign;
 
+  //! Parametric values for the solution.
+  std::vector<Linear_Expression> solution;
+
+  //! An indicator for solution validity.
+  bool solution_valid;
+
   //! Determines the sign of given Row.
   static Row_Sign row_sign(const Row &x);
 
@@ -322,6 +328,9 @@ protected:
                               const Constraint_Sequence &input_cs,
                               const Variables_Set &parameters);
 
+  //! Update the solution values.
+  virtual void update_solution();
+
   /*! \brief
     Execute a parametric simplex on the tableau, under specified context.