February 2010 - PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(master): Adding no space dims should not invalidate previously computed solution.
by Enea Zaffanella 20 Feb '10

20 Feb '10

Module: ppl/ppl Branch: master Commit: 511e9e86f96884b311d7b053aac33afb977129bb URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=511e9e86f968… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sat Feb 20 12:52:19 2010 +0100 Adding no space dims should not invalidate previously computed solution. --- src/PIP_Problem.cc | 5 +++++ tests/PIP_Problem/pipproblem2.cc | 13 +++++++++++++ 2 files changed, 18 insertions(+), 0 deletions(-) diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index 8dbae6d..6c3609e 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -510,6 +510,11 @@ void PPL::PIP_Problem ::add_space_dimensions_and_embed(const dimension_type m_vars, const dimension_type m_params) { + // Adding no space dims at all is a no-op: + // this avoids invalidating problem status (if it was optimized). + if (m_vars == 0 && m_params == 0) + return; + // The space dimension of the resulting PIP problem should not // overflow the maximum allowed space dimension. dimension_type available = max_space_dimension() - space_dimension(); diff --git a/tests/PIP_Problem/pipproblem2.cc b/tests/PIP_Problem/pipproblem2.cc index 8a20535..777c3bc 100644 --- a/tests/PIP_Problem/pipproblem2.cc +++ b/tests/PIP_Problem/pipproblem2.cc @@ -286,6 +286,18 @@ test14() { return ok; } +bool +test15() { + PIP_Problem pip; + bool ok = (pip.solve() == OPTIMIZED_PIP_PROBLEM); + // Adding no space dimension at all is a no-op: + // it does not invalidate the solution computed before. + pip.add_space_dimensions_and_embed(0, 0); + // This would throw an exception if the solution was invalidated. + pip.print_solution(nout); + return ok; +} + } // namespace BEGIN_MAIN @@ -303,4 +315,5 @@ BEGIN_MAIN DO_TEST(test12); DO_TEST(test13); DO_TEST(test14); + DO_TEST(test15); END_MAIN

1 0

[GIT] ppl/ppl(master): Got rid of non-const PIP_Tree_Node as_decision() and as_solution() methods.
by Enea Zaffanella 20 Feb '10

20 Feb '10

Module: ppl/ppl Branch: master Commit: 28dc8bb7f4c03855c8581516b3948650bea22e3b URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=28dc8bb7f4c0… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sat Feb 20 12:30:19 2010 +0100 Got rid of non-const PIP_Tree_Node as_decision() and as_solution() methods. --- src/PIP_Problem.cc | 14 ++++++++------ src/PIP_Tree.cc | 48 ++++++++++++++++-------------------------------- src/PIP_Tree.defs.hh | 12 ------------ 3 files changed, 24 insertions(+), 50 deletions(-) diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index ad234eb..8dbae6d 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -352,12 +352,12 @@ PPL::PIP_Problem::ascii_dump(std::ostream& s) const { s << "\ncurrent_solution: "; if (current_solution == 0) s << "BOTTOM\n"; - else if (PIP_Decision_Node* dec = current_solution->as_decision()) { + else if (const PIP_Decision_Node* dec = current_solution->as_decision()) { s << "DECISION\n"; dec->ascii_dump(s); } else { - PIP_Solution_Node* sol = current_solution->as_solution(); + const PIP_Solution_Node* sol = current_solution->as_solution(); PPL_ASSERT(sol != 0); s << "SOLUTION\n"; sol->ascii_dump(s); @@ -470,13 +470,15 @@ PPL::PIP_Problem::ascii_load(std::istream& s) { if (str == "BOTTOM") current_solution = 0; else if (str == "DECISION") { - current_solution = new PIP_Decision_Node(0, 0); - if (!current_solution->as_decision()->ascii_load(s)) + PIP_Decision_Node* dec = new PIP_Decision_Node(0, 0); + current_solution = dec; + if (!dec->ascii_load(s)) return false; } else if (str == "SOLUTION") { - current_solution = new PIP_Solution_Node(); - if (!current_solution->as_solution()->ascii_load(s)) + PIP_Solution_Node* sol = new PIP_Solution_Node; + current_solution = sol; + if (!sol->ascii_load(s)) return false; } else diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index deaeb15..ee05538 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -423,41 +423,21 @@ PIP_Tree_Node::as_solution() const { return 0; } -PIP_Solution_Node* -PIP_Tree_Node::as_solution() { - return 0; -} - const PIP_Decision_Node* PIP_Tree_Node::as_decision() const { return 0; } -PIP_Decision_Node* -PIP_Tree_Node::as_decision() { - return 0; -} - const PIP_Solution_Node* PIP_Solution_Node::as_solution() const { return this; } -PIP_Solution_Node* -PIP_Solution_Node::as_solution() { - return this; -} - const PIP_Decision_Node* PIP_Decision_Node::as_decision() const { return this; } -PIP_Decision_Node* -PIP_Decision_Node::as_decision() { - return this; -} - dimension_type PIP_Tree_Node::insert_artificials(Variables_Set& params, const dimension_type space_dimension) const { @@ -708,12 +688,12 @@ PIP_Decision_Node::ascii_dump(std::ostream& s) const { s << "\ntrue_child: "; if (true_child == 0) s << "BOTTOM\n"; - else if (PIP_Decision_Node* dec = true_child->as_decision()) { + else if (const PIP_Decision_Node* dec = true_child->as_decision()) { s << "DECISION\n"; dec->ascii_dump(s); } else { - PIP_Solution_Node* sol = true_child->as_solution(); + const PIP_Solution_Node* sol = true_child->as_solution(); PPL_ASSERT(sol != 0); s << "SOLUTION\n"; sol->ascii_dump(s); @@ -723,12 +703,12 @@ PIP_Decision_Node::ascii_dump(std::ostream& s) const { s << "\nfalse_child: "; if (false_child == 0) s << "BOTTOM\n"; - else if (PIP_Decision_Node* dec = false_child->as_decision()) { + else if (const PIP_Decision_Node* dec = false_child->as_decision()) { s << "DECISION\n"; dec->ascii_dump(s); } else { - PIP_Solution_Node* sol = false_child->as_solution(); + const PIP_Solution_Node* sol = false_child->as_solution(); PPL_ASSERT(sol != 0); s << "SOLUTION\n"; sol->ascii_dump(s); @@ -755,13 +735,15 @@ PIP_Decision_Node::ascii_load(std::istream& s) { if (str == "BOTTOM") true_child = 0; else if (str == "DECISION") { - true_child = new PIP_Decision_Node(0, 0); - if (!true_child->as_decision()->ascii_load(s)) + PIP_Decision_Node* dec = new PIP_Decision_Node(0, 0); + true_child = dec; + if (!dec->ascii_load(s)) return false; } else if (str == "SOLUTION") { - true_child = new PIP_Solution_Node(); - if (!true_child->as_solution()->ascii_load(s)) + PIP_Solution_Node* sol = new PIP_Solution_Node; + true_child = sol; + if (!sol->ascii_load(s)) return false; } else @@ -780,13 +762,15 @@ PIP_Decision_Node::ascii_load(std::istream& s) { if (str == "BOTTOM") false_child = 0; else if (str == "DECISION") { - false_child = new PIP_Decision_Node(0, 0); - if (!false_child->as_decision()->ascii_load(s)) + PIP_Decision_Node* dec = new PIP_Decision_Node(0, 0); + false_child = dec; + if (!dec->ascii_load(s)) return false; } else if (str == "SOLUTION") { - false_child = new PIP_Solution_Node(); - if (!false_child->as_solution()->ascii_load(s)) + PIP_Solution_Node* sol = new PIP_Solution_Node; + false_child = sol; + if (!sol->ascii_load(s)) return false; } else diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index a8cc6a9..12b1292 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -64,15 +64,9 @@ public: //! Returns \p this if \p *this is a solution node, 0 otherwise. virtual const PIP_Solution_Node* as_solution() const; - //! Returns \p this if \p *this is a solution node, 0 otherwise. - virtual PIP_Solution_Node* as_solution(); - //! Returns \p this if \p *this is a decision node, 0 otherwise. virtual const PIP_Decision_Node* as_decision() const; - //! Returns \p this if \p *this is a decision node, 0 otherwise. - virtual PIP_Decision_Node* as_decision(); - /*! \brief Returns the system of parameter constraints controlling \p *this. @@ -327,9 +321,6 @@ public: //! Returns \p this. virtual const PIP_Solution_Node* as_solution() const; - //! Returns \p this. - virtual PIP_Solution_Node* as_solution(); - //! Prints on \p s the tree rooted in \p *this. virtual void print_tree(std::ostream& s, unsigned indent, @@ -694,9 +685,6 @@ public: //! Returns \p this. virtual const PIP_Decision_Node* as_decision() const; - //! Returns \p this. - virtual PIP_Decision_Node* as_decision(); - //! Returns a const pointer to the \p b (true or false) branch of \p *this. const PIP_Tree_Node* child_node(bool b) const;

1 0

[GIT] ppl/ppl(master): Achieve full code coverage for the output operator.
by Enea Zaffanella 20 Feb '10

20 Feb '10

Module: ppl/ppl Branch: master Commit: 77df3ea039c2673fa1e94d79edaf6c81d1923cad URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=77df3ea039c2… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sat Feb 20 11:17:25 2010 +0100 Achieve full code coverage for the output operator. --- tests/PIP_Problem/pipproblem2.cc | 3 +++ 1 files changed, 3 insertions(+), 0 deletions(-) diff --git a/tests/PIP_Problem/pipproblem2.cc b/tests/PIP_Problem/pipproblem2.cc index 9c16066..8a20535 100644 --- a/tests/PIP_Problem/pipproblem2.cc +++ b/tests/PIP_Problem/pipproblem2.cc @@ -106,6 +106,9 @@ test04() { pip.set_big_parameter_dimension(5); ok &= (pip.get_big_parameter_dimension() == 5); + using namespace IO_Operators; + nout << pip; + return ok; }

1 0

[GIT] ppl/ppl(master): Document and test exception thrown by PIP_Problem:: print_solution().
by Enea Zaffanella 20 Feb '10

20 Feb '10

Module: ppl/ppl Branch: master Commit: e890db63f60fa120d9fc6ba046b5ffa24072ae67 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e890db63f60f… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sat Feb 20 10:05:36 2010 +0100 Document and test exception thrown by PIP_Problem::print_solution(). --- src/PIP_Problem.cc | 4 ++-- src/PIP_Problem.defs.hh | 11 +++++++++++ tests/PIP_Problem/exceptions1.cc | 17 +++++++++++++++++ 3 files changed, 30 insertions(+), 2 deletions(-) diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index aa34943..ad234eb 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -666,8 +666,8 @@ PPL::PIP_Problem::print_solution(std::ostream& s, unsigned indent) const { break; case PARTIALLY_SATISFIABLE: - throw std::domain_error("PIP_Problem::print_solution():\n" - "the PIP problem has not been solved."); + throw std::logic_error("PIP_Problem::print_solution():\n" + "the PIP problem has not been solved."); } } diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh index b4c6081..0015aac 100644 --- a/src/PIP_Problem.defs.hh +++ b/src/PIP_Problem.defs.hh @@ -456,6 +456,17 @@ public: bool OK() const; //! Prints on \p s the solution computed for \p *this. + /*! + \param s + The output stream. + + \param indent + An indentation parameter (default value 0). + + \exception std::logic_error + Thrown if trying to print the solution when the PIP problem + still has to be solved. + */ void print_solution(std::ostream& s, unsigned indent = 0) const; PPL_OUTPUT_DECLARATIONS diff --git a/tests/PIP_Problem/exceptions1.cc b/tests/PIP_Problem/exceptions1.cc index 3f01ab1..d9c5966 100644 --- a/tests/PIP_Problem/exceptions1.cc +++ b/tests/PIP_Problem/exceptions1.cc @@ -276,6 +276,22 @@ test12() { return false; } +bool +test13() { + PIP_Problem pip; + try { + // Printing the solution before trying to solve the problem. + pip.print_solution(nout); + } + catch (std::logic_error& e) { + nout << "logic_error: " << e.what() << endl << endl; + return true; + } + catch (...) { + } + return false; +} + } // namespace BEGIN_MAIN @@ -291,4 +307,5 @@ BEGIN_MAIN DO_TEST(test10); DO_TEST(test11); DO_TEST(test12); + DO_TEST(test13); END_MAIN

1 0

[GIT] ppl/ppl(master): Test 09 overflows when using 8-bit coefficients.
by Enea Zaffanella 20 Feb '10

20 Feb '10

Module: ppl/ppl Branch: master Commit: fce6b4f6fe1ec900db28bbceada267707d48c1c7 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=fce6b4f6fe1e… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sat Feb 20 09:46:35 2010 +0100 Test 09 overflows when using 8-bit coefficients. --- tests/PIP_Problem/ascii_dump_load1.cc | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/tests/PIP_Problem/ascii_dump_load1.cc b/tests/PIP_Problem/ascii_dump_load1.cc index b8cc8b1..5bc8041 100644 --- a/tests/PIP_Problem/ascii_dump_load1.cc +++ b/tests/PIP_Problem/ascii_dump_load1.cc @@ -287,5 +287,5 @@ BEGIN_MAIN DO_TEST(test06); DO_TEST(test07); DO_TEST(test08); - DO_TEST(test09); + DO_TEST_F8(test09); END_MAIN

1 0

[GIT] ppl/ppl(master): A couple of tests marked as known to fail.
by Enea Zaffanella 20 Feb '10

20 Feb '10

Module: ppl/ppl Branch: master Commit: 8fc67ca6012164360c1c0301f29f46d979157cbe URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8fc67ca60121… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sat Feb 20 09:40:15 2010 +0100 A couple of tests marked as known to fail. These shows a bug in the solver, which fails to detect an unfeasible initial context. --- tests/PIP_Problem/pipproblem1.cc | 18 +++++++++++++++++- 1 files changed, 17 insertions(+), 1 deletions(-) diff --git a/tests/PIP_Problem/pipproblem1.cc b/tests/PIP_Problem/pipproblem1.cc index 29b9d93..ac9fa11 100644 --- a/tests/PIP_Problem/pipproblem1.cc +++ b/tests/PIP_Problem/pipproblem1.cc @@ -501,6 +501,20 @@ test16() { return ok; } +bool +test17() { + PIP_Problem pip; + pip.add_space_dimensions_and_embed(0, 1); + // Adding unsatisfiable context constraints. + Variable n(0); + pip.add_constraint(n <= 5); + pip.add_constraint(n >= 10); + bool ok = (pip.solve() == UNFEASIBLE_PIP_PROBLEM); + if (pip.solution() != 0) + pip.print_solution(nout); + return ok; +} + } // namespace BEGIN_MAIN @@ -519,5 +533,7 @@ BEGIN_MAIN DO_TEST(test13); DO_TEST(test14); DO_TEST(test15); - // DO_TEST(test16); + // The following two tests show a bug in the PIP solver. + DO_TEST_F(test16); + DO_TEST_F(test17); END_MAIN

1 0

[GIT] ppl/ppl(master): Put under git control.
by Enea Zaffanella 20 Feb '10

20 Feb '10

Module: ppl/ppl Branch: master Commit: 12d4e15ef5bea675156c7b8068655f73597d6c1f URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=12d4e15ef5be… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sat Feb 20 08:52:24 2010 +0100 Put under git control. These test exercise the incremental PIP solver (still buggy). --- tests/PIP_Problem/pipproblem3.cc | 158 ++++++++++++++++++++++++++++++++++++++ 1 files changed, 158 insertions(+), 0 deletions(-) diff --git a/tests/PIP_Problem/pipproblem3.cc b/tests/PIP_Problem/pipproblem3.cc new file mode 100644 index 0000000..03bf580 --- /dev/null +++ b/tests/PIP_Problem/pipproblem3.cc @@ -0,0 +1,158 @@ +/* Test the PIP_Problem class. + Copyright (C) 2001-2010 Roberto Bagnara <bagnara(a)cs.unipr.it> + +This file is part of the Parma Polyhedra Library (PPL). + +The PPL is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by the +Free Software Foundation; either version 3 of the License, or (at your +option) any later version. + +The PPL is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with this program; if not, write to the Free Software Foundation, +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/ . */ + +#include "ppl_test.hh" + +namespace { + +bool +test01() { + Variable i(0); + Variable j(1); + Variable n(2); + Variable m(3); + + PIP_Problem pip; + pip.add_space_dimensions_and_embed(2, 0); + + Constraint_System cs; + cs.insert(3*j >= -2*i+8); + cs.insert(j <= 4*i - 4); + + pip.add_constraints(cs); + + bool ok = (pip.solve() == OPTIMIZED_PIP_PROBLEM); + if (!ok) + return ok; + + { + const PIP_Tree solution = pip.solution(); + ok &= solution->OK(); + pip.print_solution(nout); + nout << endl; + } + + pip.add_space_dimensions_and_embed(0, 2); + pip.add_constraint(j <= m); + pip.add_constraint(i <= n); + + ok &= (pip.solve() == OPTIMIZED_PIP_PROBLEM); + if (ok) { + const PIP_Tree solution = pip.solution(); + ok &= solution->OK(); + pip.print_solution(nout); + } + return ok; +} + +bool +test02() { + // NOTE_ changing the order of insertion of variables. + Variable i(0); + Variable n(1); + Variable j(2); + Variable m(3); + + PIP_Problem pip; + pip.add_space_dimensions_and_embed(1, 1); + + Constraint_System cs; + pip.add_constraint(i <= n); + + pip.add_constraints(cs); + + bool ok = (pip.solve() == OPTIMIZED_PIP_PROBLEM); + if (!ok) + return ok; + + { + const PIP_Tree solution = pip.solution(); + ok &= solution->OK(); + pip.print_solution(nout); + nout << endl; + } + + pip.add_space_dimensions_and_embed(1, 1); + pip.add_constraint(3*j >= -2*i+8); + pip.add_constraint(j <= 4*i - 4); + pip.add_constraint(j <= m); + + ok &= (pip.solve() == OPTIMIZED_PIP_PROBLEM); + if (ok) { + const PIP_Tree solution = pip.solution(); + ok &= solution->OK(); + pip.print_solution(nout); + } + return ok; +} + +bool +test03() { + Variable i(0); + Variable j(1); + Variable n(2); + Variable m(3); + + PIP_Problem pip; + pip.add_space_dimensions_and_embed(2, 2); + + Constraint_System cs; + cs.insert(3*j >= -2*i+8); + cs.insert(j <= 4*i - 4); + pip.add_constraint(j <= m); + pip.add_constraint(i <= n); + + pip.add_constraints(cs); + + bool ok = (pip.solve() == OPTIMIZED_PIP_PROBLEM); + if (!ok) + return ok; + + { + const PIP_Tree solution = pip.solution(); + ok &= solution->OK(); + pip.print_solution(nout); + nout << endl; + } + + Variable k(4); + Variable p(5); + pip.add_space_dimensions_and_embed(1, 1); + pip.add_constraint(k <= i + p); + pip.add_constraint(p <= n + 2); + + ok &= (pip.solve() == OPTIMIZED_PIP_PROBLEM); + if (ok) { + const PIP_Tree solution = pip.solution(); + ok &= solution->OK(); + pip.print_solution(nout); + } + return ok; +} + +} // namespace + +BEGIN_MAIN + DO_TEST_F8(test01); + DO_TEST_F8(test02); + // DO_TEST_F8(test03); +END_MAIN

1 0

[GIT] ppl/ppl(master): Check fir and avoid space dimension mismatches in merge_assign().
by Enea Zaffanella 20 Feb '10

20 Feb '10

Module: ppl/ppl Branch: master Commit: 084cb1f825471435bd1e1b0bb1eb0ed8eabd368d URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=084cb1f82547… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sat Feb 20 08:50:53 2010 +0100 Check fir and avoid space dimension mismatches in merge_assign(). --- src/PIP_Tree.cc | 10 ++++++++-- 1 files changed, 8 insertions(+), 2 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 222efeb..deaeb15 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -69,7 +69,9 @@ merge_assign(Matrix& x, return; const dimension_type old_num_rows = x.num_rows(); x.add_zero_rows(new_rows, Row::Flags()); + // Compute once for all. + const dimension_type cs_space_dim = y.space_dimension(); const Variables_Set::const_iterator param_begin = parameters.begin(); const Variables_Set::const_iterator param_end = parameters.end(); @@ -81,8 +83,12 @@ merge_assign(Matrix& x, x_i[0] = y_i->inhomogeneous_term(); Variables_Set::const_iterator pj; dimension_type j = 1; - for (pj = param_begin; pj != param_end; ++pj, ++j) - x_i[j] = y_i->coefficient(Variable(*pj)); + for (pj = param_begin; pj != param_end; ++pj, ++j) { + Variable vj(*pj); + if (vj.space_dimension() > cs_space_dim) + break; + x_i[j] = y_i->coefficient(vj); + } } }

1 0

[GIT] ppl/ppl(master): Started working on incrementality.
by Enea Zaffanella 19 Feb '10

19 Feb '10

Module: ppl/ppl Branch: master Commit: 3cb3ce1f0be968a3a73804e7f63837e0d10aee96 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3cb3ce1f0be9… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Fri Feb 19 22:32:24 2010 +0100 Started working on incrementality. Dealt with a FIXME in PIP_Solution_Node::update_tableau(): when adding new problem variables and parameters, the columns of the existing artificial parameters are moved to the right of the tableau.t matrix. --- src/PIP_Tree.cc | 82 ++++++++++++++++++++++++++-------------- src/PIP_Tree.defs.hh | 9 +++- tests/PIP_Problem/Makefile.am | 3 +- 3 files changed, 61 insertions(+), 33 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index b13e3a2..222efeb 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -1429,48 +1429,73 @@ PIP_Solution_Node::update_tableau(const PIP_Problem& problem, const dimension_type first_pending_constraint, const Constraint_Sequence& input_cs, const Variables_Set& parameters) { - dimension_type initial_space_dim; - if (tableau.t.num_columns() > 0) - initial_space_dim = tableau.s.num_columns() + tableau.t.num_columns() - 1; - else { - // Create parameter column, corresponding to the constant term. + // Make sure a parameter column exists, for the inhomogeneous term. + if (tableau.t.num_columns() == 0) tableau.t.add_zero_columns(1); - initial_space_dim = 0; + + // NOTE: here 'params' stands for problem (i.e., non artificial) parameters. + const dimension_type old_num_vars = tableau.s.num_columns(); + const dimension_type old_num_params + = problem.internal_space_dim - old_num_vars; + const dimension_type num_added_dims + = problem.external_space_dim - problem.internal_space_dim; + const dimension_type new_num_params = parameters.size(); + const dimension_type num_added_params = new_num_params - old_num_params; + const dimension_type num_added_vars = num_added_dims - num_added_params; + + const dimension_type old_num_art_params + = tableau.t.num_columns() - 1 - old_num_params; + + // Resize the two tableau matrices. + if (num_added_vars > 0) + tableau.s.add_zero_columns(num_added_vars); + if (num_added_params > 0) + tableau.t.add_zero_columns(num_added_params); + + if (num_added_params > 0 && old_num_art_params > 0) { + // Shift to the right the columns of artificial parameters. + std::vector<dimension_type> swaps; + swaps.reserve(3*old_num_art_params); + const dimension_type first_ap = 1 + old_num_params; + for (dimension_type i = 0; i < old_num_art_params; ++i) { + dimension_type old_ap = first_ap + i; + dimension_type new_ap = old_ap + num_added_params; + swaps.push_back(old_ap); + swaps.push_back(new_ap); + swaps.push_back(0); + } + tableau.t.permute_columns(swaps); } - // Add new columns to the tableau. - /* FIXME: when the node or its parents have artificial parameters, we - must insert new parameter columns before the columns corresponding to - the artificial parameters. Meanwhile parameter insertion after a first - solve (incremental solving) is broken. */ + dimension_type new_var_column = old_num_vars; + const dimension_type initial_space_dim = old_num_vars + old_num_params; for (dimension_type i = initial_space_dim; i < external_space_dim; ++i) { - if (parameters.count(i) == 1) - // A new parameter. - tableau.t.add_zero_columns(1); - else { - // A new variable. - const dimension_type new_column = tableau.s.num_columns(); - tableau.s.add_zero_columns(1); + if (parameters.count(i) == 0) { + // A new problem variable. if (tableau.s.num_rows() == 0) { // No rows have been added yet basis.push_back(true); - mapping.push_back(new_column); - } else { - /* Need to insert the original variable id before the slack variable - id's to respect variable ordering */ - basis.insert(basis.begin() + new_column, true); - mapping.insert(mapping.begin() + new_column, new_column); - // update variable id's of slack variables + mapping.push_back(new_var_column); + } + else { + /* + Need to insert the original variable id + before the slack variable id's to respect variable ordering. + */ + basis.insert(basis.begin() + new_var_column, true); + mapping.insert(mapping.begin() + new_var_column, new_var_column); + // Update variable id's of slack variables. for (dimension_type j = var_row.size(); j-- > 0; ) - if (var_row[j] >= new_column) + if (var_row[j] >= new_var_column) ++var_row[j]; for (dimension_type j = var_column.size(); j-- > 0; ) - if (var_column[j] >= new_column) + if (var_column[j] >= new_var_column) ++var_column[j]; if (special_equality_row > 0) ++special_equality_row; } - var_column.push_back(new_column); + var_column.push_back(new_var_column); + ++new_var_column; } } @@ -1487,7 +1512,6 @@ PIP_Solution_Node::update_tableau(const PIP_Problem& problem, c_iter = input_cs.begin() + first_pending_constraint, c_end = input_cs.end(); c_iter != c_end; ++c_iter) { const Constraint& constraint = *c_iter; - // (Tentatively) Add new rows to s and t matrices. // These will be removed at the end if they turn out to be useless. const dimension_type row_id = tableau.s.num_rows(); diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index 81a000f..a8cc6a9 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -36,9 +36,12 @@ site: http://www.cs.unipr.it/ppl/ . */ namespace Parma_Polyhedra_Library { -/*! \brief - The base class for the nodes of the trees representing the solutions - of PIP problems. +//! A node of the PIP solution tree. +/*! + This is the base class for the nodes of the binary trees representing + the solutions of PIP problems. From this one, two classes are derived: + - PIP_Decision_Node, for the internal nodes of the tree; + - PIP_Solution_Node, for the leaves of the tree. */ class PIP_Tree_Node { protected: diff --git a/tests/PIP_Problem/Makefile.am b/tests/PIP_Problem/Makefile.am index 19ea24e..f9d2598 100644 --- a/tests/PIP_Problem/Makefile.am +++ b/tests/PIP_Problem/Makefile.am @@ -52,7 +52,7 @@ $(top_builddir)/src/libppl.la \ TESTS = \ ascii_dump_load1 \ exceptions1 \ -pipproblem1 pipproblem2 +pipproblem1 pipproblem2 pipproblem3 XFAIL_TESTS = @@ -68,6 +68,7 @@ exceptions1_SOURCES = exceptions1.cc pipproblem1_SOURCES = pipproblem1.cc pipproblem2_SOURCES = pipproblem2.cc +pipproblem3_SOURCES = pipproblem3.cc check_PROGRAMS = \ $(TESTS) \

1 0

[GIT] ppl/ppl(master): Little code coverage improvement.
by Enea Zaffanella 19 Feb '10

19 Feb '10

Module: ppl/ppl Branch: master Commit: e191bf79e2f4228ba5e1f3ace0ad1cfae3ba1674 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e191bf79e2f4… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Fri Feb 19 22:31:37 2010 +0100 Little code coverage improvement. --- tests/PIP_Problem/ascii_dump_load1.cc | 32 ++++++++++++++++++++++++++++++++ tests/PIP_Problem/pipproblem2.cc | 2 +- 2 files changed, 33 insertions(+), 1 deletions(-) diff --git a/tests/PIP_Problem/ascii_dump_load1.cc b/tests/PIP_Problem/ascii_dump_load1.cc index d0cbceb..b8cc8b1 100644 --- a/tests/PIP_Problem/ascii_dump_load1.cc +++ b/tests/PIP_Problem/ascii_dump_load1.cc @@ -245,6 +245,37 @@ test08() { return ok; } +bool +test09() { + Variable i(0); + Variable j(1); + Variable n(2); + Variable m(3); + Variables_Set params(n, m); + + Constraint_System cs; + cs.insert(3*j >= -2*i+8); + cs.insert(j <= 4*i - 4); + cs.insert(j <= m); + cs.insert(i <= n); + + PIP_Problem pip(cs.space_dimension(), cs.begin(), cs.end(), params); + (void) pip.solve(); + + std::stringstream ss; + pip.ascii_dump(ss); + + PIP_Problem pip2; + bool ok = pip2.ascii_load(ss); + + std::stringstream ss2; + pip2.ascii_dump(ss2); + + ok &= (ss.str() == ss2.str()); + + return ok; +} + } // namespace BEGIN_MAIN @@ -256,4 +287,5 @@ BEGIN_MAIN DO_TEST(test06); DO_TEST(test07); DO_TEST(test08); + DO_TEST(test09); END_MAIN diff --git a/tests/PIP_Problem/pipproblem2.cc b/tests/PIP_Problem/pipproblem2.cc index 5c747f5..9c16066 100644 --- a/tests/PIP_Problem/pipproblem2.cc +++ b/tests/PIP_Problem/pipproblem2.cc @@ -264,7 +264,7 @@ test14() { ok &= (ap0 == ap1) && (ap2.denominator() == 1); using namespace IO_Operators; - nout << ap1; + nout << ap1 << endl; ok &= (ap1.external_memory_in_bytes() < ap1.total_memory_in_bytes());

1 0