Module: ppl/ppl Branch: master Commit: 95009146c346328599abf0da6873e4d3572b6328 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=95009146c3463...
Author: Enea Zaffanella zaffanella@cs.unipr.it Date: Mon Feb 22 18:54:20 2010 +0100
Added tentative solution to bugs shown by pipproblem1 tests 16, 17 and 18.
---
src/PIP_Problem.cc | 38 +++++++++++++++++++++++++++++++++----- src/PIP_Tree.defs.hh | 8 +++++++- tests/PIP_Problem/pipproblem1.cc | 22 +++++++++++++++++++--- 3 files changed, 59 insertions(+), 9 deletions(-)
diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index 23a0503..8df7d1b 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -153,19 +153,47 @@ PPL::PIP_Problem::solve() const { { dimension_type i = 1; for (Variables_Set::const_iterator - pi = param_begin; pi != param_end; ++pi, ++i) - row[i] = c.coefficient(Variable(*pi)); + pi = param_begin; pi != param_end; ++pi, ++i) { + if (*pi < c_space_dim) + row[i] = c.coefficient(Variable(*pi)); + else + break; + } } // Adjust inhomogenous term if strict. if (c.is_strict_inequality()) --row[0]; - // Insert new row into context. - x.initial_context.add_row(row); + + // Check for compatibility. + if (PIP_Solution_Node::compatibility_check(initial_context, row)) + // Insert new row into initial context. + x.initial_context.add_row(row); + else { + // Problem found to be unfeasible. + delete x.current_solution; + x.current_solution = 0; + x.status = UNSATISFIABLE; + PPL_ASSERT(OK()); + return UNFEASIBLE_PIP_PROBLEM; + } + // If it is an equality, also insert its negation. if (c.is_equality()) { for (dimension_type i = new_num_cols; i-- > 0; ) neg_assign(row[i], row[i]); - x.initial_context.add_row(row); + + // Check for compatibility. + if (PIP_Solution_Node::compatibility_check(initial_context, row)) + // Insert new row into initial context. + x.initial_context.add_row(row); + else { + // Problem found to be unfeasible. + delete x.current_solution; + x.current_solution = 0; + x.status = UNSATISFIABLE; + PPL_ASSERT(OK()); + return UNFEASIBLE_PIP_PROBLEM; + } } }
diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index c51962c..87d4663 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -572,6 +572,10 @@ private:
The algorithm ensures the feasible solutions are integer, by applying a cut generation method when intermediate non-integer solutions are found. + + \note + It is assumed that matrix \p ctx and row \c cnst have the same + size and capacity; otherwise the behavior is undefined. */ static bool compatibility_check(const Matrix& ctx, const Row& cnst);
@@ -589,8 +593,10 @@ protected: */ PIP_Solution_Node(const PIP_Solution_Node& y, No_Constraints);
- // PIP_Problem ascii load method needs access set_owner. + // PIP_Problem::ascii load() method needs access set_owner(). friend bool PIP_Problem::ascii_load(std::istream& s); + // PIP_Problem::solve() method needs access compatibility_check(). + friend PIP_Problem_Status PIP_Problem::solve() const;
//! Sets the pointer to the PIP_Problem owning object. virtual void set_owner(const PIP_Problem* owner); diff --git a/tests/PIP_Problem/pipproblem1.cc b/tests/PIP_Problem/pipproblem1.cc index f41aced..9810c33 100644 --- a/tests/PIP_Problem/pipproblem1.cc +++ b/tests/PIP_Problem/pipproblem1.cc @@ -511,6 +511,22 @@ test17() { return ok; }
+bool +test18() { + PIP_Problem pip; + pip.add_space_dimensions_and_embed(0, 2); + // Adding unsatisfiable context constraints. + Variable n(0); + Variable m(1); + pip.add_constraint(n == 2); + pip.add_constraint(m == 2); + pip.add_constraint(n + m == 3); + bool ok = (pip.solve() == UNFEASIBLE_PIP_PROBLEM); + if (pip.solution() != 0) + pip.print_solution(nout); + return ok; +} + } // namespace
BEGIN_MAIN @@ -529,7 +545,7 @@ BEGIN_MAIN DO_TEST(test13); DO_TEST(test14); DO_TEST(test15); - // The following two tests show a bug in the PIP solver. - DO_TEST_F(test16); - DO_TEST_F(test17); + DO_TEST(test16); + DO_TEST(test17); + DO_TEST(test18); END_MAIN