September 2009 - PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(pip): Implemented simplex basis and tableau initialization in PIP solver.
by François Galea 04 Sep '09

04 Sep '09

Module: ppl/ppl Branch: pip Commit: 2690fc065429c1855d3188958dd843aef6a13875 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2690fc065429… Author: François Galea <francois.galea(a)uvsq.fr> Date: Fri Sep 4 14:53:38 2009 +0200 Implemented simplex basis and tableau initialization in PIP solver. --- src/PIP_Problem.cc | 95 +++++++++++++++++++++++++++++++++++++++++- src/PIP_Problem.defs.hh | 12 ++++- src/PIP_Problem.inlines.hh | 12 +++++- src/PIP_Problem.templates.hh | 1 + 4 files changed, 115 insertions(+), 5 deletions(-) diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index 5a561a9..dece4ef 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -40,6 +40,7 @@ PPL::PIP_Problem::PIP_Problem(dimension_type dim) : external_space_dim(dim), internal_space_dim(0), tableau(), + basis(), status(PARTIALLY_SATISFIABLE), initialized(false), input_cs(), @@ -57,6 +58,7 @@ PPL::PIP_Problem::PIP_Problem(const PIP_Problem &y) : external_space_dim(y.external_space_dim), internal_space_dim(y.internal_space_dim), tableau(y.tableau), + basis(y.basis), status(y.status), initialized(y.initialized), input_cs(y.input_cs), @@ -67,8 +69,97 @@ PPL::PIP_Problem::PIP_Problem(const PIP_Problem &y) PPL::PIP_Problem_Status PPL::PIP_Problem::solve() const { - //FIXME - return OPTIMIZED_PIP_PROBLEM; + switch (status) { + case UNSATISFIABLE: + PPL_ASSERT(OK()); + return UNFEASIBLE_PIP_PROBLEM; + case OPTIMIZED: + PPL_ASSERT(OK()); + return OPTIMIZED_PIP_PROBLEM; + case SATISFIABLE: + // Intentionally fall through + case PARTIALLY_SATISFIABLE: + { + PIP_Problem& x = const_cast<PIP_Problem&>(*this); + PIP_Problem_Status return_value; + + x.update_tableau(); + //FIXME: implement the simplex algorithm + + return_value = OPTIMIZED_PIP_PROBLEM; + + switch (return_value) { + case UNFEASIBLE_PIP_PROBLEM: + x.status = UNSATISFIABLE; + break; + case OPTIMIZED_PIP_PROBLEM: + x.status = OPTIMIZED; + break; + } + PPL_ASSERT(OK()); + return return_value; + } + } + // We should not be here! + throw std::runtime_error("PPL internal error"); +} + +void +PPL::PIP_Problem::update_tableau() { + dimension_type i; + dimension_type n_params = parameters.size(); + dimension_type n_vars = external_space_dim - n_params; + dimension_type n_vars_int = tableau.s.num_columns(); + dimension_type n_constr_int = tableau.s.num_rows(); + const_iterator cst; + + if (tableau.t.num_columns() == 0) { + // Create the parameter column, corresponding to the constant term + tableau.t.add_zero_columns(1); + } + + for (i=internal_space_dim; i<external_space_dim; ++i) { + // add new columns to the tableau + if (parameters.count(i) == 1) + tableau.t.add_zero_columns(1); + else + tableau.s.add_zero_columns(1); + } + internal_space_dim = external_space_dim; + + Coefficient denom_s = tableau.s.get_denominator(); + Coefficient denom_t = tableau.t.get_denominator(); + + for (cst = constraints_begin() + first_pending_constraint; + cst < constraints_end(); ++cst) { + // FIXME: must handle nonbasic variables aswell + int v = 0; + int p = 1; + Row var(n_vars, Row::Flags()); + Row param(n_params+1, Row::Flags()); + Coefficient cnst_term = -cst->inhomogeneous_term(); + if (cst->is_strict_inequality()) + // convert c > 0 <=> c-1 >= 0 + cnst_term -= 1; + param[0] = cnst_term * denom_t; + for (i=0; i<internal_space_dim; i++) { + if (parameters.count(i) == 1) { + param[p] = cst->coefficient(Variable(i)) * denom_t; + ++p; + } else { + var[v] = cst->coefficient(Variable(i)) * denom_s; + ++v; + } + } + //FIXME: must handle equality constraints + tableau.s.add_row(var); + tableau.t.add_row(param); + } + + // update current basis with newly inserted variables + dimension_type next_var = n_vars_int + n_constr_int; + for (i=n_vars_int; i<n_vars; ++i) + basis.insert(next_var++); } diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh index 818f785..e724c7e 100644 --- a/src/PIP_Problem.defs.hh +++ b/src/PIP_Problem.defs.hh @@ -320,8 +320,8 @@ private: */ void normalize(); - //! Tests whether the matrix is integer,�\e ie. the denominator is 1. - bool is_integer(); + //! Tests whether the matrix is integer, \e ie. the denominator is 1. + bool is_integer() const; //! Returns the value of the denominator. const Coefficient &get_denominator() const; @@ -344,6 +344,9 @@ private: //! The parametric simplex tableau. Tableau tableau; + //! A set containing the internal indices of the basic variables + Variables_Set basis; + //! An enumerated type describing the internal status of the PIP problem. enum Status { //! The PIP problem is unsatisfiable. @@ -381,6 +384,11 @@ private: interpreted as problem parameters. */ Variables_Set parameters; + + /*! \brief + Populates the parametric simplex tableau using external data, if necessary + */ + void update_tableau(); }; namespace std { diff --git a/src/PIP_Problem.inlines.hh b/src/PIP_Problem.inlines.hh index 4dcb55b..c064ae9 100644 --- a/src/PIP_Problem.inlines.hh +++ b/src/PIP_Problem.inlines.hh @@ -46,7 +46,7 @@ PIP_Problem::Rational_Matrix::Rational_Matrix(const Rational_Matrix& y) } inline bool -PIP_Problem::Rational_Matrix::is_integer() { +PIP_Problem::Rational_Matrix::is_integer() const { return denominator == 1; } @@ -64,6 +64,16 @@ PIP_Problem::max_space_dimension() { return Constraint::max_space_dimension(); } +inline PIP_Problem::const_iterator +PIP_Problem::constraints_begin() const { + return input_cs.begin(); +} + +inline PIP_Problem::const_iterator +PIP_Problem::constraints_end() const { + return input_cs.end(); +} + } // namespace Parma_Polyhedra_Library namespace std { diff --git a/src/PIP_Problem.templates.hh b/src/PIP_Problem.templates.hh index 3f474d2..76e8ecf 100644 --- a/src/PIP_Problem.templates.hh +++ b/src/PIP_Problem.templates.hh @@ -35,6 +35,7 @@ PIP_Problem::PIP_Problem(dimension_type dim, : external_space_dim(dim), internal_space_dim(0), tableau(), + basis(), status(PARTIALLY_SATISFIABLE), initialized(false), input_cs(),

1 0

[GIT] ppl/ppl(pip): Included the PIP_Problem and PIP_Tree classes in the devref documentation.
by François Galea 04 Sep '09

04 Sep '09

Module: ppl/ppl Branch: pip Commit: 00627ff6a98497a9f01972edcfeefe04c58114fc URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=00627ff6a984… Author: François Galea <francois.galea(a)uvsq.fr> Date: Fri Sep 4 12:23:45 2009 +0200 Included the PIP_Problem and PIP_Tree classes in the devref documentation. --- doc/devref.doxyconf-html.in | 8 ++++++++ 1 files changed, 8 insertions(+), 0 deletions(-) diff --git a/doc/devref.doxyconf-html.in b/doc/devref.doxyconf-html.in index e0a297d..cd1b4a3 100644 --- a/doc/devref.doxyconf-html.in +++ b/doc/devref.doxyconf-html.in @@ -314,6 +314,14 @@ INPUT = @srcdir@/definitions.dox \ @srcdir@/../src/Octagonal_Shape.inlines.hh \ @srcdir@/../src/Octagonal_Shape.templates.hh \ @srcdir@/../src/Octagonal_Shape.cc \ + @srcdir@/../src/PIP_Problem.cc \ + @srcdir@/../src/PIP_Problem.defs.hh \ + @srcdir@/../src/PIP_Problem.inlines.hh \ + @srcdir@/../src/PIP_Problem.templates.hh \ + @srcdir@/../src/PIP_Problem.types.hh \ + @srcdir@/../src/PIP_Tree.defs.hh \ + @srcdir@/../src/PIP_Tree.inlines.hh \ + @srcdir@/../src/PIP_Tree.types.hh \ @srcdir@/gpl.dox \ @srcdir@/fdl.dox INPUT_ENCODING = UTF-8

1 0

[GIT] ppl/ppl(floating_point): Added a workaround for the fact that we don' t have an explicit way to
by Fabio Bossi 04 Sep '09

04 Sep '09

Module: ppl/ppl Branch: floating_point Commit: 663dfab0dee076d37deb1f0afadb7dbcf4bebd42 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=663dfab0dee0… Author: Fabio Bossi <bossi(a)cs.unipr.it> Date: Fri Sep 4 11:16:05 2009 +0200 Added a workaround for the fact that we don't have an explicit way to divide a Linear_Form by an Interval. --- ...Division_Floating_Point_Expression.templates.hh | 14 ++++++++++---- 1 files changed, 10 insertions(+), 4 deletions(-) diff --git a/src/Division_Floating_Point_Expression.templates.hh b/src/Division_Floating_Point_Expression.templates.hh index 5fcfab9..ca464f0 100644 --- a/src/Division_Floating_Point_Expression.templates.hh +++ b/src/Division_Floating_Point_Expression.templates.hh @@ -43,10 +43,16 @@ typename Division_Floating_Point_Expression<FP_Interval_Type, FP_Format> FP_Interval_Type abs_error(-this->absolute_error); // FIXME: this may be incorrect for some policies. abs_error.join_assign(this->absolute_error); - FP_Linear_Form result = linearized_first_operand / intervalized_second_operand - + relative_error(linearized_first_operand) / intervalized_second_operand - + abs_error; - + /* + FIXME: since we currently lack an explicit way to divide a linear form + by a scalar, we temporarily multiply by 1/scalar. + */ + FP_Interval_Type reversed_intervalized_second_operand = + (FP_Interval_Type(boundary_type(1)) / intervalized_second_operand); + FP_Linear_Form result = linearized_first_operand * + reversed_intervalized_second_operand + + relative_error(linearized_first_operand) * + reversed_intervalized_second_operand + abs_error; return result; }

1 0

[GIT] ppl/ppl(floating_point): Fixed various errors.
by Fabio Bossi 04 Sep '09

04 Sep '09

Module: ppl/ppl Branch: floating_point Commit: 99ff3b447a38287010701980fc33173dbc521133 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=99ff3b447a38… Author: Fabio Bossi <bossi(a)cs.unipr.it> Date: Fri Sep 4 10:43:37 2009 +0200 Fixed various errors. --- ...Division_Floating_Point_Expression.templates.hh | 4 ++-- src/Floating_Point_Expression.templates.hh | 2 +- ...lication_Floating_Point_Expression.templates.hh | 8 ++++---- 3 files changed, 7 insertions(+), 7 deletions(-) diff --git a/src/Division_Floating_Point_Expression.templates.hh b/src/Division_Floating_Point_Expression.templates.hh index 49be890..5fcfab9 100644 --- a/src/Division_Floating_Point_Expression.templates.hh +++ b/src/Division_Floating_Point_Expression.templates.hh @@ -31,8 +31,8 @@ typename Division_Floating_Point_Expression<FP_Interval_Type, FP_Format> ::FP_Linear_Form Division_Floating_Point_Expression<FP_Interval_Type, FP_Format> ::linearize(const FP_Interval_Abstract_Store& store) const { - FP_Interval_Type intervalized_second_operand = intervalize( - second_operand->linearize(store)); + FP_Interval_Type intervalized_second_operand = this->intervalize( + second_operand->linearize(store), store); // Check if we may divide by zero. // FIXME: check the assumption that boundary_type is comparable with zero. if (intervalized_second_operand.lower() <= 0 && diff --git a/src/Floating_Point_Expression.templates.hh b/src/Floating_Point_Expression.templates.hh index 9321527..d2b0093 100644 --- a/src/Floating_Point_Expression.templates.hh +++ b/src/Floating_Point_Expression.templates.hh @@ -73,7 +73,7 @@ Floating_Point_Expression<FP_Interval_Type, FP_Format> next_variable_value = store.find(i); if (next_variable_value != store.end()) { FP_Interval_Type current_coefficient = lf.coefficient(Variable(i)); - result += current_coefficient * (*next_variable_value); + result += current_coefficient * next_variable_value->second; } } diff --git a/src/Multiplication_Floating_Point_Expression.templates.hh b/src/Multiplication_Floating_Point_Expression.templates.hh index fcd8d9b..61d2918 100644 --- a/src/Multiplication_Floating_Point_Expression.templates.hh +++ b/src/Multiplication_Floating_Point_Expression.templates.hh @@ -43,11 +43,11 @@ typename Multiplication_Floating_Point_Expression<FP_Interval_Type, FP_Format> // true if we intervalize the first form, false if we intervalize the second. bool intervalize_first; FP_Linear_Form linearized_first_operand = first_operand->linearize(store); - FP_Interval_Type intervalized_first_operand = intervalize( - linearized_first_operand); + FP_Interval_Type intervalized_first_operand = this->intervalize( + linearized_first_operand, store); FP_Linear_Form linearized_second_operand = second_operand->linearize(store); - FP_Interval_Type intervalized_second_operand = intervalize( - linearized_second_operand); + FP_Interval_Type intervalized_second_operand = this->intervalize( + linearized_second_operand, store); boundary_type first_interval_size, second_interval_size; // FIXME: we are not sure that what we do here is policy-proof. if (intervalized_first_operand.is_bounded()) {

1 0

[GIT] ppl/ppl(floating_point): Fixed bad use of constructor.
by Fabio Bossi 04 Sep '09

04 Sep '09

Module: ppl/ppl Branch: floating_point Commit: 41a927e39c1b9ae298ade0ffd8f92d5db884c95b URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=41a927e39c1b… Author: Fabio Bossi <bossi(a)cs.unipr.it> Date: Fri Sep 4 09:56:13 2009 +0200 Fixed bad use of constructor. --- src/Variable_Floating_Point_Expression.inlines.hh | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/src/Variable_Floating_Point_Expression.inlines.hh b/src/Variable_Floating_Point_Expression.inlines.hh index fa4eda3..b88af52 100644 --- a/src/Variable_Floating_Point_Expression.inlines.hh +++ b/src/Variable_Floating_Point_Expression.inlines.hh @@ -50,7 +50,7 @@ inline typename Variable_Floating_Point_Expression<FP_Interval_Type, FP_Format>::FP_Linear_Form Variable_Floating_Point_Expression<FP_Interval_Type, FP_Format> ::linearize(const FP_Interval_Abstract_Store& store) const { - FP_Linear_Form result(Variable(variable_index)); + FP_Linear_Form result = FP_Linear_Form(Variable(variable_index)); return result; }

1 0

[GIT] ppl/ppl(pip): Listed François Galea among the current contributors .
by Roberto Bagnara 04 Sep '09

04 Sep '09

Module: ppl/ppl Branch: pip Commit: dc2606ea40c56bdb1572d51ac9d753d99c5854b3 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=dc2606ea40c5… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Fri Sep 4 08:46:37 2009 +0200 Listed François Galea among the current contributors. --- CREDITS | 5 +++++ 1 files changed, 5 insertions(+), 0 deletions(-) diff --git a/CREDITS b/CREDITS index 7316d9b..9234cc9 100644 --- a/CREDITS +++ b/CREDITS @@ -40,6 +40,10 @@ Current Contributors: solver, and also most of the Java and OCaml interfaces. + François Galea [*] (University of Versailles) is working + at the implementation of the Parametric Integer + Programming solver. + Katy Dobson [4] (University of Leeds) is working on the formalization and definition of algorithms for rational grids and products of grids and @@ -345,6 +349,7 @@ projects and organizations: [1] http://www.cs.unipr.it/~bagnara/ [2] http://www.comp.leeds.ac.uk/hill/ [3] http://www.cs.unipr.it/~zaffanella/ + [*] http://www.prism.uvsq.fr/~fgalea/ [4] http://www.comp.leeds.ac.uk/katyd/ [5] http://www.lsi.upc.edu/~erodri/ [6] http://www.math.unipr.it/~zaccagni/

1 0

[GIT] ppl/ppl(pip): Drafted implementation for ascii_dump and ascii_load methods.
by Enea Zaffanella 04 Sep '09

04 Sep '09

Module: ppl/ppl Branch: pip Commit: 68aad9bf5bd2c263a3a5ee871eaf6a391be7a10b URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=68aad9bf5bd2… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Thu Sep 3 16:10:55 2009 +0200 Drafted implementation for ascii_dump and ascii_load methods. --- src/PIP_Problem.cc | 154 +++++++++++++++++++++++++++++++++++++++++++++++ src/PIP_Problem.defs.hh | 3 + 2 files changed, 157 insertions(+), 0 deletions(-) diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index 2a1089d..5a561a9 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -77,3 +77,157 @@ PPL::PIP_Problem::OK() const { //FIXME return true; } + +void +PPL::PIP_Problem::ascii_dump(std::ostream& s) const { + using namespace IO_Operators; + s << "\nexternal_space_dim: " << external_space_dim << " \n"; + s << "\ninternal_space_dim: " << internal_space_dim << " \n"; + + const dimension_type input_cs_size = input_cs.size(); + + s << "\ninput_cs( " << input_cs_size << " )\n"; + for (dimension_type i = 0; i < input_cs_size; ++i) + input_cs[i].ascii_dump(s); + + s << "\nfirst_pending_constraint: " << first_pending_constraint + << std::endl; + + s << "\ninitialized: " << (initialized ? "YES" : "NO") << "\n"; + + s << "\nstatus: "; + switch (status) { + case UNSATISFIABLE: + s << "UNSATISFIABLE"; + break; + case SATISFIABLE: + s << "SATISFIABLE"; + break; + case OPTIMIZED: + s << "OPTIMIZED"; + break; + case PARTIALLY_SATISFIABLE: + s << "PARTIALLY_SATISFIABLE"; + break; + } + s << "\n"; + + s << "\nparameters"; + parameters.ascii_dump(s); + + s << "\nsimplex_tableau\n"; + tableau.s.ascii_dump(s); + + s << "\nparameter_tableau\n"; + tableau.t.ascii_dump(s); +} + +PPL_OUTPUT_DEFINITIONS(PIP_Problem) + +bool +PPL::PIP_Problem::ascii_load(std::istream& s) { + std::string str; + if (!(s >> str) || str != "external_space_dim:") + return false; + + if (!(s >> external_space_dim)) + return false; + + if (!(s >> str) || str != "internal_space_dim:") + return false; + + if (!(s >> internal_space_dim)) + return false; + + if (!(s >> str) || str != "input_cs(") + return false; + + dimension_type input_cs_size; + + if (!(s >> input_cs_size)) + return false; + + if (!(s >> str) || str != ")") + return false; + + Constraint c(Constraint::zero_dim_positivity()); + for (dimension_type i = 0; i < input_cs_size; ++i) { + if (!c.ascii_load(s)) + return false; + input_cs.push_back(c); + } + + if (!(s >> str) || str != "first_pending_constraint:") + return false; + + if (!(s >> first_pending_constraint)) + return false; + + if (!(s >> str) || str != "initialized:") + return false; + if (!(s >> str)) + return false; + if (str == "YES") + initialized = true; + else if (str == "NO") + initialized = false; + else + return false; + + if (!(s >> str) || str != "status:") + return false; + + if (!(s >> str)) + return false; + + if (str == "UNSATISFIABLE") + status = UNSATISFIABLE; + else if (str == "SATISFIABLE") + status = SATISFIABLE; + else if (str == "OPTIMIZED") + status = OPTIMIZED; + else if (str == "PARTIALLY_SATISFIABLE") + status = PARTIALLY_SATISFIABLE; + else + return false; + + if (!(s >> str) || str != "parameters") + return false; + + if (!parameters.ascii_load(s)) + return false; + + if (!(s >> str) || str != "simplex_tableau") + return false; + if (!tableau.s.ascii_load(s)) + return false; + + if (!(s >> str) || str != "parameter_tableau") + return false; + if (!tableau.t.ascii_load(s)) + return false; + + PPL_ASSERT(OK()); + return true; +} + +void +PPL::PIP_Problem::Rational_Matrix::ascii_dump(std::ostream& s) const { + s << "denominator " << denominator << "\n"; + Matrix::ascii_dump(s); +} + +bool +PPL::PIP_Problem::Rational_Matrix::ascii_load(std::istream& s) { + std::string str; + if (!(s >> str) || str != "denominator") + return false; + Coefficient den; + if (!(s >> den)) + return false; + denominator = den; + + return Matrix::ascii_load(s); +} + + diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh index 5a0ce38..818f785 100644 --- a/src/PIP_Problem.defs.hh +++ b/src/PIP_Problem.defs.hh @@ -326,6 +326,9 @@ private: //! Returns the value of the denominator. const Coefficient &get_denominator() const; + void ascii_dump(std::ostream& s) const; + bool ascii_load(std::istream& s); + protected: Coefficient denominator; };

1 0

[GIT] ppl/ppl(pip): Do perform PIP_Problem tests first.
by Enea Zaffanella 04 Sep '09

04 Sep '09

Module: ppl/ppl Branch: pip Commit: 56c76f2f522079257e30d4738ed32ee2b7b43287 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=56c76f2f5220… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Thu Sep 3 14:34:15 2009 +0200 Do perform PIP_Problem tests first. --- tests/Makefile.am | 2 +- tests/PIP_Problem/pipproblem.cc | 13 +++++-------- 2 files changed, 6 insertions(+), 9 deletions(-) diff --git a/tests/Makefile.am b/tests/Makefile.am index 88addab..536a586 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -22,11 +22,11 @@ SUBDIRS = \ . \ +PIP_Problem \ Powerset \ Partially_Reduced_Product \ Box \ MIP_Problem \ -PIP_Problem \ Octagonal_Shape \ BD_Shape \ Polyhedron \ diff --git a/tests/PIP_Problem/pipproblem.cc b/tests/PIP_Problem/pipproblem.cc index 51af374..df9f96f 100644 --- a/tests/PIP_Problem/pipproblem.cc +++ b/tests/PIP_Problem/pipproblem.cc @@ -20,13 +20,12 @@ Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA. For the most up-to-date information see the Parma Polyhedra Library site: http://www.cs.unipr.it/ppl/ . */ -//#define NOISY 1 - #include "ppl_test.hh" namespace { -bool test01() { +bool +test01() { Variable X1(0); Variable X2(1); Variable I0(2); @@ -41,13 +40,11 @@ bool test01() { cs.insert(-X1 - I0 + N >= 0); cs.insert(X2 + J0 - N - 1 >= 0); - PIP_Problem pip = PIP_Problem(cs.space_dimension(), cs.begin(), cs.end(), - params); + PIP_Problem pip(cs.space_dimension(), cs.begin(), cs.end(), params); - if (pip.solve() != OPTIMIZED_PIP_PROBLEM) - return false; + bool ok = (pip.solve() == OPTIMIZED_PIP_PROBLEM); - return true; + return ok; } } // namespace

1 0

[GIT] ppl/ppl(pip): Minor coding style improvements.
by Enea Zaffanella 04 Sep '09

04 Sep '09

Module: ppl/ppl Branch: pip Commit: 22718e3dda0d714a43a79c8f5b2b4b99510da5bf URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=22718e3dda0d… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Thu Sep 3 14:28:12 2009 +0200 Minor coding style improvements. --- src/PIP_Problem.cc | 3 +-- src/PIP_Problem.defs.hh | 21 +++++++++++---------- src/PIP_Problem.inlines.hh | 23 ++++++++++++++--------- 3 files changed, 26 insertions(+), 21 deletions(-) diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index 7fbb239..2a1089d 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -47,8 +47,7 @@ PPL::PIP_Problem::PIP_Problem(dimension_type dim) parameters() { // Check for space dimension overflow. if (dim > max_space_dimension()) - throw std::length_error("PPL::PIP_Problem:: PIP_Problem(dim, first, " - "last, p_vars):\n" + throw std::length_error("PPL::PIP_Problem:: PIP_Problem(dim):\n" "dim exceeds the maximum allowed" "space dimension."); PPL_ASSERT(OK()); diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh index a9b666a..5a0ce38 100644 --- a/src/PIP_Problem.defs.hh +++ b/src/PIP_Problem.defs.hh @@ -287,7 +287,7 @@ private: dimension_type internal_space_dim; //! A rational matrix, with a common nenominator - class Rational_Matrix: public Matrix { + class Rational_Matrix : public Matrix { public: //! Builds an empty matrix. /*! @@ -330,15 +330,16 @@ private: Coefficient denominator; }; - //! The parametric simplex tableau - /*! - Consists in two rational matrices, represented as an integer tableau - and a common denominator. The \p s matrix is the matrix of simplex - coefficients, and the \p t matrix is the matrix of parameter coefficients. - */ - struct { - Rational_Matrix s, t; - } tableau; + //! The type for parametric simplex tableau. + struct Tableau { + //! The matrix of simplex coefficients. + Rational_Matrix s; + //! The matrix of parameter coefficients. + Rational_Matrix t; + }; + + //! The parametric simplex tableau. + Tableau tableau; //! An enumerated type describing the internal status of the PIP problem. enum Status { diff --git a/src/PIP_Problem.inlines.hh b/src/PIP_Problem.inlines.hh index 4064d0a..4dcb55b 100644 --- a/src/PIP_Problem.inlines.hh +++ b/src/PIP_Problem.inlines.hh @@ -25,23 +25,28 @@ site: http://www.cs.unipr.it/ppl/ . */ namespace Parma_Polyhedra_Library { -inline PIP_Problem::Rational_Matrix::Rational_Matrix(): - Matrix(), denominator(1) { +inline +PIP_Problem::Rational_Matrix::Rational_Matrix() + : Matrix(), + denominator(1) { } -inline PIP_Problem::Rational_Matrix::Rational_Matrix( - dimension_type n_rows, dimension_type n_columns, Row::Flags row_flags): - Matrix(n_rows, n_columns, row_flags), +inline +PIP_Problem::Rational_Matrix::Rational_Matrix(dimension_type n_rows, + dimension_type n_columns, + Row::Flags row_flags) + : Matrix(n_rows, n_columns, row_flags), denominator(1) { } -inline PIP_Problem::Rational_Matrix::Rational_Matrix( - const Rational_Matrix& y): - Matrix(y), +inline +PIP_Problem::Rational_Matrix::Rational_Matrix(const Rational_Matrix& y) + : Matrix(y), denominator(1) { } -inline bool PIP_Problem::Rational_Matrix::is_integer() { +inline bool +PIP_Problem::Rational_Matrix::is_integer() { return denominator == 1; }

1 0

[GIT] ppl/ppl(pip): Started the implementation of the PIP_Problem class.
by François Galea 04 Sep '09

04 Sep '09

Module: ppl/ppl Branch: pip Commit: d542fbbddbc2a46bf8d9856dd65d2a890d8d204e URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d542fbbddbc2… Author: François Galea <francois.galea(a)uvsq.fr> Date: Wed Sep 2 17:57:15 2009 +0200 Started the implementation of the PIP_Problem class. In particular: - defined the PIP_Problem constructors; - added the definition of the rational matrix class; - added the definition of simplex tableau; - created a test program. --- configure.ac | 1 + src/PIP_Problem.cc | 48 ++++++++++++++++++++++ src/PIP_Problem.defs.hh | 58 ++++++++++++++++++++++++++- src/PIP_Problem.inlines.hh | 34 ++++++++++++++++ src/PIP_Problem.templates.hh | 84 +++++++++++++++++++++++++++++++++++++++ tests/Makefile.am | 1 + tests/PIP_Problem/Makefile.am | 84 +++++++++++++++++++++++++++++++++++++++ tests/PIP_Problem/pipproblem.cc | 57 ++++++++++++++++++++++++++ 8 files changed, 365 insertions(+), 2 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=d542fbbd…

1 0