[PPL-devel] [GIT] ppl/ppl(pip): Improved the support for equality constraints.

[François Galea]

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

Author: François Galea <francois.galea at uvsq.fr>
Date:   Thu Nov  5 09:11:38 2009 +0100

Improved the support for equality constraints.

---

 src/PIP_Tree.cc      |   47 +++++++++++++++++++++++++++++++++++++----------
 src/PIP_Tree.defs.hh |   26 ++++++++++++++++++++++----
 2 files changed, 59 insertions(+), 14 deletions(-)

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index 6a26215..e6766bd 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -46,6 +46,14 @@ add_assign(Row& x, const Row& y, Coefficient_traits::const_reference c) {
     add_mul_assign(x[i], c, y[i]);
 }
 
+// Compute x -= y
+void
+sub_assign(Row& x, const Row& y) {
+  PPL_ASSERT(x.size() == y.size());
+  for (dimension_type i = x.size(); i-- > 0; )
+    x[i] -= y[i];
+}
+
 // Merge constraint system to a Matrix-form context such as x = x U y
 void
 merge_assign(Matrix& x,
@@ -202,6 +210,7 @@ PIP_Solution_Node::PIP_Solution_Node()
     mapping(),
     var_row(),
     var_column(),
+    special_equality_row(0),
     sign(),
     solution(),
     solution_valid(false) {
@@ -214,6 +223,7 @@ PIP_Solution_Node::PIP_Solution_Node(const PIP_Solution_Node &x)
     mapping(x.mapping),
     var_row(x.var_row),
     var_column(x.var_column),
+    special_equality_row(0),
     sign(x.sign),
     solution(x.solution),
     solution_valid(x.solution_valid) {
@@ -227,6 +237,7 @@ PIP_Solution_Node::PIP_Solution_Node(const PIP_Solution_Node &x,
     mapping(x.mapping),
     var_row(x.var_row),
     var_column(x.var_column),
+    special_equality_row(x.special_equality_row),
     sign(x.sign),
     solution(x.solution),
     solution_valid(x.solution_valid) {
@@ -949,6 +960,8 @@ PIP_Solution_Node::update_tableau(dimension_type external_space_dim,
         for (j = var_column.size(); j-- > 0; )
           if (var_column[j] >= column)
             ++var_column[j];
+        if (special_equality_row > 0)
+          ++special_equality_row;
       }
       var_column.push_back(column);
     }
@@ -998,16 +1011,30 @@ PIP_Solution_Node::update_tableau(dimension_type external_space_dim,
       mapping.push_back(row_id);
       var_row.push_back(var_id);
       if (cst->is_equality()) {
-        ++var_id;
-        ++row_id;
-        negate_assign(var, var, 0);
-        negate_assign(param, param, 0);
-        tableau.s.add_row(var);
-        tableau.t.add_row(param);
-        sign.push_back(row_sign(param));
-        basis.push_back(false);
-        mapping.push_back(row_id);
-        var_row.push_back(var_id);
+        /* Handle equality constraints. After having added the f_i(x,p) >= 0
+          constraint, we must add -f_i(x,p) to the special equality row */
+        if (special_equality_row == 0 || basis[special_equality_row]) {
+          // The special constraint has not been created yet
+          /* FIXME: for now, we don't handle the case where the variable is
+            basic, and create a new row. This might be faster however. */
+          ++var_id;
+          ++row_id;
+          negate_assign(var, var, 0);
+          negate_assign(param, param, 0);
+          tableau.s.add_row(var);
+          tableau.t.add_row(param);
+          sign.push_back(row_sign(param));
+          special_equality_row = mapping.size();
+          basis.push_back(false);
+          mapping.push_back(row_id);
+          var_row.push_back(var_id);
+        } else {
+          // The special constraint already exists and is nonbasic
+          std::cout << "bla\n";
+          dimension_type row = mapping[special_equality_row];
+          sub_assign(tableau.s[row], var);
+          sub_assign(tableau.t[row], param);
+        }
       }
     }
   }
diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh
index e9746df..5711c8f 100644
--- a/src/PIP_Tree.defs.hh
+++ b/src/PIP_Tree.defs.hh
@@ -325,14 +325,32 @@ private:
   */
   std::vector<dimension_type> mapping;
 
-  /*! A vector of the variable identifiers associated to each row of the
-     simplex tableau. */
+  /*! \brief A vector of the variable identifiers associated to each row of
+     the simplex tableau. */
   std::vector<dimension_type> var_row;
 
-  /*! A vector of the variable identifiers associated to each column of the
-     simplex tableau. */
+  /*! \brief A vector of the variable identifiers associated to each column
+     of the simplex tableau. */
   std::vector<dimension_type> var_column;
 
+  /*! \brief The variable number of the special inequality used for modelling
+    equality constraints.
+
+    The subset of equality constraints in a specific problem can be expressed
+    as: \f$f_i(x,p) = 0 ; 1 \leq i \leq n\f$. As the dual simplex standard form
+    requires constraints to be inequalities, the following constraints can be
+    modelized the following way:
+
+     - \f$f_i(x,p) \geq 0 ; 1 \leq i \leq n\f$
+
+     - \f$\sum\limits_{i=1}^n f_i(x,p) \leq 0\f$
+
+    The \p special_equality_row value stores the variable number of the
+    specific constraint which is used to modelize the latter sum of
+    constraints. If no such constraint exists, the value is set to \p 0.
+  */
+  dimension_type special_equality_row;
+
   //! The possible values for the sign of a parametric linear expression.
   enum Row_Sign {
     //! Not computed yet (default)