Module: ppl/ppl Branch: pip Commit: 0bc03d5786735188f81bd47ef078fa0bbedd44a3 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0bc03d5786735... Author: François Galea <francois.galea@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)