February 2010 - PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(pip): More progress on PIP_Solution_Node::solve().
by Enea Zaffanella 03 Feb '10

03 Feb '10

Module: ppl/ppl Branch: pip Commit: 42bacf1180afc8db1d8a8bbf3eaf3353a67582c3 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=42bacf1180af… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Wed Feb 3 17:26:41 2010 +0100 More progress on PIP_Solution_Node::solve(). Identified places where the current implementation is not exception safe. --- src/PIP_Tree.cc | 261 +++++++++++++++++++++++++++++-------------------------- 1 files changed, 138 insertions(+), 123 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=42bacf11…

1 0

[GIT] ppl/ppl(pip): Further improved (huge) method PIP_Solution_Node::solve ().
by Enea Zaffanella 03 Feb '10

03 Feb '10

Module: ppl/ppl Branch: pip Commit: bcc9213813f993d30aae61cd74347c1ca3fd4efb URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=bcc9213813f9… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Wed Feb 3 14:33:00 2010 +0100 Further improved (huge) method PIP_Solution_Node::solve(). Added a couple of comments regarding parts where comments or code in unclear. --- src/PIP_Tree.cc | 625 +++++++++++++++++++++++++++++-------------------------- 1 files changed, 330 insertions(+), 295 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=bcc92138…

1 0

[GIT] ppl/ppl(pip): Improved method Tableau::is_better_pivot().
by Enea Zaffanella 03 Feb '10

03 Feb '10

Module: ppl/ppl Branch: pip Commit: 2649737035a99c2ebee2e55411f9a4a27eb936fd URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2649737035a9… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Wed Feb 3 08:50:28 2010 +0100 Improved method Tableau::is_better_pivot(). --- src/PIP_Tree.cc | 60 ++++++++++++++++++++++++++++++++---------------------- 1 files changed, 35 insertions(+), 25 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 9720f6f..d20b16f 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -744,34 +744,44 @@ bool PIP_Solution_Node::Tableau ::is_better_pivot(const std::vector<dimension_type>& mapping, const std::vector<bool>& basis, - const dimension_type i, - const dimension_type j, - const dimension_type i_, - const dimension_type j_) const { - dimension_type k; - dimension_type num_params = t.num_columns(); - dimension_type num_rows = s.num_rows(); - const Row& s_i = s[i]; - const Row& s_i_ = s[i_]; - const Row& t_i = t[i]; - const Row& t_i_ = t[i_]; - bool columns_are_different = false; - for (k=0; k<num_params; ++k) { - PPL_DIRTY_TEMP_COEFFICIENT(t_ikXs_i_j_); - PPL_DIRTY_TEMP_COEFFICIENT(t_i_kXs_ij); - t_ikXs_i_j_ = t_i[k] * s_i_[j_]; - t_i_kXs_ij = t_i_[k] * s_i[j]; - for (dimension_type x=0; x<num_rows; ++x) { - const Row& s_x = s[x]; - if (s_x[j] * t_ikXs_i_j_ != s_x[j_] * t_i_kXs_ij) { - columns_are_different = true; - goto endloop; + const dimension_type row_0, + const dimension_type col_0, + const dimension_type row_1, + const dimension_type col_1) const { + const dimension_type num_params = t.num_columns(); + const dimension_type num_rows = s.num_rows(); + const Row& s_0 = s[row_0]; + const Row& s_1 = s[row_1]; + const Coefficient& s_0_0 = s_0[col_0]; + const Coefficient& s_1_1 = s_1[col_1]; + const Row& t_0 = t[row_0]; + const Row& t_1 = t[row_1]; + PPL_DIRTY_TEMP_COEFFICIENT(coeff_0); + PPL_DIRTY_TEMP_COEFFICIENT(coeff_1); + PPL_DIRTY_TEMP_COEFFICIENT(product_0); + PPL_DIRTY_TEMP_COEFFICIENT(product_1); + // On exit from the loop, if j_mismatch == num_params then + // no column mismatch was found. + dimension_type j_mismatch = num_params; + for (dimension_type j = 0; j < num_params; ++j) { + coeff_0 = t_0[j] * s_1_1; + coeff_1 = t_1[j] * s_0_0; + for (dimension_type i = 0; i < num_rows; ++i) { + const Row& s_i = s[i]; + product_0 = coeff_0 * s_i[col_0]; + product_1 = coeff_1 * s_i[col_1]; + if (product_0 != product_1) { + // Mismatch found: exit from both loops. + j_mismatch = j; + goto end_loop; } } } -endloop: - return columns_are_different - && column_lower(s, mapping, basis, s_i, j, s_i_, j_, t_i[k], t_i_[k]); + + end_loop: + return (j_mismatch != num_params) + && column_lower(s, mapping, basis, s_0, col_0, s_1, col_1, + t_0[j_mismatch], t_1[j_mismatch]); } void

1 0

[GIT] ppl/ppl(pip): Started improving method PIP_Solution_Node::solve():
by Enea Zaffanella 03 Feb '10

03 Feb '10

Module: ppl/ppl Branch: pip Commit: c08098c36aa410996a0c0ed080669a81e40d095e URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c08098c36aa4… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Tue Feb 2 10:27:12 2010 +0100 Started improving method PIP_Solution_Node::solve(): - limit scope of variables; - try to use meaningful variable names. --- src/PIP_Tree.cc | 171 +++++++++++++++++++++++++++---------------------------- 1 files changed, 83 insertions(+), 88 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=c08098c3…

1 0

[GIT] ppl/ppl(pip): Minor improvements to PIP_Problem documentation and C interface.
by Enea Zaffanella 03 Feb '10

03 Feb '10

Module: ppl/ppl Branch: pip Commit: ff7e8d5afd59c8440045725bff0cac5e7644ab9c URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ff7e8d5afd59… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Mon Feb 1 19:23:18 2010 +0100 Minor improvements to PIP_Problem documentation and C interface. --- interfaces/C/ppl_c_header.h | 22 ++++++++--- interfaces/C/ppl_c_implementation_common.cc | 14 ------- src/PIP_Problem.defs.hh | 3 +- src/PIP_Tree.cc | 12 +++---- src/PIP_Tree.defs.hh | 53 ++++++++++++++------------- 5 files changed, 50 insertions(+), 54 deletions(-) diff --git a/interfaces/C/ppl_c_header.h b/interfaces/C/ppl_c_header.h index ac09559..f21626b 100644 --- a/interfaces/C/ppl_c_header.h +++ b/interfaces/C/ppl_c_header.h @@ -697,10 +697,20 @@ PPL_TYPE_DECLARATION(PIP_Problem) /*! \interface ppl_PIP_Tree_Node_tag \brief - Types and functions for PIP tree nodes. + Types and functions for generic PIP tree nodes. */ PPL_TYPE_DECLARATION(PIP_Tree_Node) + +/*! \interface ppl_PIP_Decision_Node_tag + \brief + Types and functions for PIP decision nodes. +*/ PPL_TYPE_DECLARATION(PIP_Decision_Node) + +/*! \interface ppl_PIP_Solution_Node_tag + \brief + Types and functions for PIP solution nodes. +*/ PPL_TYPE_DECLARATION(PIP_Solution_Node) /*! \interface ppl_Artificial_Parameter_tag @@ -2656,10 +2666,10 @@ PPL_PROTO((ppl_MIP_Problem_t mip, int value)); /*! \relates ppl_PIP_Problem_tag \brief Builds a trivial PIP problem of dimension \p d and writes an - handle to it at address \p pmip. + handle to it at address \p ppip. */ int -ppl_new_PIP_Problem_from_space_dimension PPL_PROTO((ppl_PIP_Problem_t* pmip, +ppl_new_PIP_Problem_from_space_dimension PPL_PROTO((ppl_PIP_Problem_t* ppip, ppl_dimension_type d)); /*! \relates ppl_PIP_Problem_tag \brief @@ -2744,7 +2754,7 @@ int ppl_PIP_Problem_clear PPL_PROTO((ppl_PIP_Problem_t pip)); /*! \relates ppl_PIP_Problem_tag \brief - Adds <CODE>m_pip_vars + m_pip_params</CODE> new space dimensions + Adds <CODE>pip_vars + pip_params</CODE> new space dimensions and embeds the PIP problem \p pip in the new vector space. \param pip @@ -2966,8 +2976,8 @@ PPL_PROTO((ppl_const_PIP_Solution_Node_t pip_sol, ppl_const_Linear_Expression_t* le)); /*! \relates ppl_PIP_Tree_Node_tag \brief - Writes to \p pip_tree a const pointer to the \p b (true or false) branch - of \p pip_dec. + Writes to \p pip_tree a const pointer to either the true branch + (if \p b is not zero) or the false branch (if \p b is zero) of \p pip_dec. */ int ppl_PIP_Decision_Node_get_child_node diff --git a/interfaces/C/ppl_c_implementation_common.cc b/interfaces/C/ppl_c_implementation_common.cc index 27e8227..e297492 100644 --- a/interfaces/C/ppl_c_implementation_common.cc +++ b/interfaces/C/ppl_c_implementation_common.cc @@ -2342,13 +2342,6 @@ ppl_PIP_Tree_Node_get_constraints(ppl_const_PIP_Tree_Node_t pip_tree, CATCH_ALL int -ppl_delete_PIP_Tree_Node(ppl_const_PIP_Tree_Node_t pip_tree) try { - delete to_const(pip_tree); - return 0; -} -CATCH_ALL - -int ppl_PIP_Tree_Node_OK(ppl_const_PIP_Tree_Node_t pip_tree) try { return to_const(pip_tree)->OK() ? 1 : 0; } @@ -2409,13 +2402,6 @@ ppl_PIP_Solution_Node_OK(ppl_const_PIP_Solution_Node_t pip_sol) try { CATCH_ALL int -ppl_delete_PIP_Decision_Node(ppl_const_PIP_Decision_Node_t pip_dec) try { - delete to_const(pip_dec); - return 0; -} -CATCH_ALL - -int ppl_PIP_Decision_Node_OK(ppl_const_PIP_Decision_Node_t pip_dec) try { return to_const(pip_dec)->OK() ? 1 : 0; } diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh index d9e52f1..f8a0f8a 100644 --- a/src/PIP_Problem.defs.hh +++ b/src/PIP_Problem.defs.hh @@ -449,8 +449,7 @@ public: //! Returns an optimizing solution for \p *this, if it exists. /*! \exception std::domain_error - Thrown if \p *this does not have an optimizing point, i.e., - if the PIP problem is unbounded or not satisfiable. + Thrown if the PIP problem is not satisfiable. */ PIP_Tree optimizing_solution() const; diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index ce5e455..b454246 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -1045,6 +1045,7 @@ PIP_Solution_Node::ascii_load(std::istream& s) { return true; } +// FIXME: this does not (yet) correspond to specification. const Linear_Expression& PIP_Solution_Node ::parametric_values(const Variable var, @@ -1062,13 +1063,10 @@ PIP_Solution_Node if (pos == all_parameters.end()) return solution[var.id()]; else { -#ifndef NDEBUG - if (*pos == var.id()) { - std::cerr << "PIP_Solution_Node::parametric_values(Variable): " - << "Supplied Variable corresponds to a parameter.\n"; - PPL_ASSERT(false); - } -#endif // #ifndef NDEBUG + if (*pos == var.id()) + throw std::invalid_argument("PIP_Solution_Node::" + "parametric_values(v, params): " + "variable v is a parameter."); const dimension_type dist = std::distance(all_parameters.begin(), pos); return solution[var.id() - dist]; } diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index b819b6e..9c9f412 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -260,10 +260,10 @@ public: parameters. \param v - the variable which is queried about + The variable which is queried about. \param parameters - a \c std::set of indices of the parameters in the problem constraints + A \c std::set of indices of the parameters in the problem constraints. \exception std::invalid_argument Thrown if \p v is dimension-incompatible with \p *this @@ -406,15 +406,18 @@ private: */ std::vector<dimension_type> mapping; - /*! \brief A vector of the variable identifiers associated to each row of - the simplex tableau. */ + /*! \brief + The variable identifiers associated to the rows of the simplex tableau. + */ std::vector<dimension_type> var_row; - /*! \brief A vector of the variable identifiers associated to each column - of the simplex tableau. */ + /*! \brief + The variable identifiers associated to the columns of the simplex tableau. + */ std::vector<dimension_type> var_column; - /*! \brief The variable number of the special inequality used for modelling + /*! \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 @@ -433,15 +436,14 @@ private: dimension_type special_equality_row; /*! \brief - The column number in the parametric part of the simplex tableau - which corresponds to the big parameter; \c not_a_dimension() - if not set. + The column index in the parametric part of the simplex tableau + corresponding to the big parameter; \c not_a_dimension() if not set. */ dimension_type big_dimension; //! The possible values for the sign of a parametric linear expression. enum Row_Sign { - //! Not computed yet (default) + //! Not computed yet (default). UNKNOWN, //! All row coefficients are zero. ZERO, @@ -449,7 +451,7 @@ private: POSITIVE, //! All nonzero row coefficients are negative. NEGATIVE, - //! The row contains positive and negative coefficients. + //! The row contains both positive and negative coefficients. MIXED }; @@ -462,12 +464,12 @@ private: //! An indicator for solution validity. bool solution_valid; - //! Determines the sign of given Row. + //! Returns the sign of row \p x. static Row_Sign row_sign(const Row& x, dimension_type big_dimension); /*! \brief - Checks whether a constraint is compatible with a context, ie. does not - make the context empty. + Checks whether a constraint is compatible with a context, + i.e., if it does not make the context unsatisfiable. The method consists in applying the revised dual simplex algorithm on a Matrix consisting in the original matrix with the constraint inserted. If @@ -518,30 +520,30 @@ protected: Update the solution values. \param parameters - a \c std::set of indices of the parameters in the constraints + A \c std::set of indices of the parameters in the constraints */ - virtual void update_solution(const Variables_Set& parameters); + void update_solution(const Variables_Set& parameters); /*! \brief Execute a parametric simplex on the tableau, under specified context. \param parent_ref - a pointer to the parent reference to \p this + A pointer to the parent reference to \p this. \param problem - the containing problem object + The containing problem object. \param context - the context, being a set of constraints on the parameters + The context, being a set of constraints on the parameters. \param params - local parameter set, including parent artificial parameters + The local set of parameters, including parent artificial parameters. \param space_dimension - space dimension of parent, including artificial parameters + Space dimension of parent, including artificial parameters. \return - An PIP_Problem_Status flag indicating the outcome of the optimization + A PIP_Problem_Status flag indicating the result of the optimization attempt (unfeasible or optimized problem). */ virtual PIP_Problem_Status solve(PIP_Tree_Node*& parent_ref, @@ -572,8 +574,9 @@ protected: Variables_Set& parameters, Matrix& context, dimension_type& space_dimension); - // FIXME: constructors to be decided. -}; + +}; // class PIP_Solution_Node + //! A tree node representing a decision in the space of solutions. class PIP_Decision_Node : public PIP_Tree_Node {

1 0

[GIT] ppl/ppl(pip): Got rid of error-prone Tableau::s_capacity() and Tableau::t_capacity().
by Enea Zaffanella 01 Feb '10

01 Feb '10

Module: ppl/ppl Branch: pip Commit: 052ec67e0d7c5c093b3cd7bf10d2654db46ad834 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=052ec67e0d7c… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Mon Feb 1 17:32:17 2010 +0100 Got rid of error-prone Tableau::s_capacity() and Tableau::t_capacity(). --- src/PIP_Tree.defs.hh | 6 ++---- src/PIP_Tree.inlines.hh | 10 ---------- 2 files changed, 2 insertions(+), 14 deletions(-) diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index be1a361..b819b6e 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -293,14 +293,12 @@ private: //! Destructor. ~Tableau(); - //! Returns the allocated capacity of each Row of the \p s Matrix. - dimension_type s_capacity() const; - //! Returns the allocated capacity of each Row of the \p t Matrix. - dimension_type t_capacity() const; //! Tests whether the matrix is integer, \e ie. the denominator is 1. bool is_integer() const; + //! Multiplies all coefficients and denominator with ratio. void scale(Coefficient_traits::const_reference ratio); + //! Normalizes the modulo of coefficients so that they are mutually prime. /*! Computes the Greatest Common Divisor (GCD) among the elements of diff --git a/src/PIP_Tree.inlines.hh b/src/PIP_Tree.inlines.hh index 1bb7cd6..2ea2d93 100644 --- a/src/PIP_Tree.inlines.hh +++ b/src/PIP_Tree.inlines.hh @@ -51,16 +51,6 @@ PIP_Solution_Node::Tableau::get_denominator() const { return denominator; } -inline dimension_type -PIP_Solution_Node::Tableau::s_capacity() const { - return compute_capacity(s.num_columns(), Matrix::max_num_columns()); -} - -inline dimension_type -PIP_Solution_Node::Tableau::t_capacity() const { - return compute_capacity(t.num_columns(), Matrix::max_num_columns()); -} - inline PIP_Tree_Node::~PIP_Tree_Node() { }

1 0

[GIT] ppl/ppl(pip): Improved method PIP_Solution_Node::update_tableau().
by Enea Zaffanella 01 Feb '10

01 Feb '10

Module: ppl/ppl Branch: pip Commit: a7326ef65ce9c3e929fa2ba9a22bdbb5014c1182 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a7326ef65ce9… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Mon Feb 1 17:29:34 2010 +0100 Improved method PIP_Solution_Node::update_tableau(). --- src/PIP_Tree.cc | 196 +++++++++++++++++++++++++++++++----------------------- 1 files changed, 112 insertions(+), 84 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=a7326ef6…

1 0

[GIT] ppl/ppl(pip): Improved implementation of PIP_Solution_Node:: compatibility_check().
by Enea Zaffanella 01 Feb '10

01 Feb '10

Module: ppl/ppl Branch: pip Commit: 476f754b5c37d2245316d6acfe3b09af3c5b8a32 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=476f754b5c37… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Mon Feb 1 14:12:04 2010 +0100 Improved implementation of PIP_Solution_Node::compatibility_check(). Besides readability and stylistic changes, the change should also immprove robustness and (to a lesser extent) performance. --- src/PIP_Tree.cc | 319 ++++++++++++++++++++++++++++-------------------------- 1 files changed, 165 insertions(+), 154 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=476f754b…

1 0