Module: ppl/ppl Branch: master Commit: 0e480f958e85f6d0c50b57835aaaa8f4ba9026ab URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0e480f958e85f... Author: Enea Zaffanella <zaffanella@cs.unipr.it> Date: Thu Feb 18 16:07:39 2010 +0100 Corrected bug in th ehandling of trivially satisfiable PIP problems. Test 16 in pipproblem1.cc (currently disabled) shows a bug in the handling of trivially unfeasible PIP problems. --- src/PIP_Problem.cc | 32 ++++++------- src/PIP_Tree.cc | 33 ++++++++------ tests/PIP_Problem/pipproblem1.cc | 91 ++++++++++++++++++++++++++++++++++++++ 3 files changed, 125 insertions(+), 31 deletions(-) diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index f24043f..aa34943 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -109,23 +109,19 @@ PPL::PIP_Problem::solve() const { case PARTIALLY_SATISFIABLE: { PIP_Problem& x = const_cast<PIP_Problem&>(*this); + // Allocate PIP solution tree root, if needed. if (current_solution == 0) x.current_solution = new PIP_Solution_Node(); - if (input_cs.empty()) { - // No constraints: solution = {0}. - x.status = OPTIMIZED; - return OPTIMIZED_PIP_PROBLEM; - } // Properly resize context matrix. - const dimension_type num_params = parameters.size() + 1; - const dimension_type num_cols = initial_context.num_columns(); - if (num_cols < num_params) - x.initial_context.add_zero_columns(num_params - num_cols); + const dimension_type new_num_cols = parameters.size() + 1; + const dimension_type old_num_cols = initial_context.num_columns(); + if (old_num_cols < new_num_cols) + x.initial_context.add_zero_columns(new_num_cols - old_num_cols); // Computed once for all (to be used inside loop). - const Variables_Set::iterator param_begin = parameters.begin(); - const Variables_Set::iterator param_end = parameters.end(); + const Variables_Set::const_iterator param_begin = parameters.begin(); + const Variables_Set::const_iterator param_end = parameters.end(); // Go through all pending constraints. for (Constraint_Sequence::const_iterator @@ -150,12 +146,14 @@ PPL::PIP_Problem::solve() const { continue; // Translate constraint into context row. - Row row(num_params, Row::Flags()); + Row row(new_num_cols, Row::Flags()); row[0] = c.inhomogeneous_term(); - dimension_type i = 1; - for (Variables_Set::iterator - pi = param_begin; pi != param_end; ++pi, ++i) - row[i] = c.coefficient(Variable(*pi)); + { + dimension_type i = 1; + for (Variables_Set::const_iterator + pi = param_begin; pi != param_end; ++pi, ++i) + row[i] = c.coefficient(Variable(*pi)); + } // Adjust inhomogenous term if strict. if (c.is_strict_inequality()) --row[0]; @@ -163,7 +161,7 @@ PPL::PIP_Problem::solve() const { x.initial_context.add_row(row); // If it is an equality, also insert its negation. if (c.is_equality()) { - for (dimension_type i = num_params; i-- > 0; ) + for (dimension_type i = new_num_cols; i-- > 0; ) neg_assign(row[i], row[i]); x.initial_context.add_row(row); } diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 67986a1..8ef8d21 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -1583,23 +1583,28 @@ void PIP_Solution_Node::update_solution(const Variables_Set& parameters) { if (solution_valid) return; - dimension_type num_vars = tableau.s.num_columns(); - const Coefficient& d = tableau.get_denominator(); + + const dimension_type num_vars = tableau.s.num_columns(); if (solution.size() != num_vars) solution.resize(num_vars); + + // Compute once for all outside loop. + const dimension_type num_params = parameters.size(); + const Variables_Set::const_reverse_iterator p_rbegin = parameters.rbegin(); + const Variables_Set::const_reverse_iterator p_rend = parameters.rend(); + + const Coefficient& den = tableau.get_denominator(); for (dimension_type i = num_vars; i-- > 0; ) { - Linear_Expression& sol = solution[i]; - if (basis[i]) { - sol = Linear_Expression(0); - } else { - Row& row = tableau.t[mapping[i]]; - sol = Linear_Expression(row[0]/d); - dimension_type k; - Variables_Set::const_iterator j; - Variables_Set::const_iterator j_end = parameters.end(); - for (j = parameters.begin(), k = 1; j != j_end; ++j, ++k) - sol += (row[k]/d) * Variable(*j); - } + Linear_Expression& sol_i = solution[i]; + sol_i = Linear_Expression(0); + if (basis[i]) + continue; + Row& row = tableau.t[mapping[i]]; + dimension_type k = num_params; + for (Variables_Set::const_reverse_iterator + pj = p_rbegin; pj != p_rend; ++pj, --k) + add_mul_assign(sol_i, row[k]/den, Variable(*pj)); + sol_i += row[0]/den; } solution_valid = true; } diff --git a/tests/PIP_Problem/pipproblem1.cc b/tests/PIP_Problem/pipproblem1.cc index 7fb57ea..a30b89b 100644 --- a/tests/PIP_Problem/pipproblem1.cc +++ b/tests/PIP_Problem/pipproblem1.cc @@ -311,6 +311,91 @@ test10() { return ok; } +bool +test11() { + // 0-dimension trivial PIP problem. + PIP_Problem pip; + + bool ok = (pip.solve() == OPTIMIZED_PIP_PROBLEM); + if (ok) { + const PIP_Tree solution = pip.solution(); + ok &= solution->OK(); + pip.print_solution(nout); + } + return ok; +} + +bool +test12() { + // Trivial PIP problem, but with 4 parameters. + PIP_Problem pip; + pip.add_space_dimensions_and_embed(0, 4); + + bool ok = (pip.solve() == OPTIMIZED_PIP_PROBLEM); + if (ok) { + const PIP_Tree solution = pip.solution(); + ok &= solution->OK(); + pip.print_solution(nout); + } + return ok; +} + +bool +test13() { + // Trivial PIP problem with 4 variables. + PIP_Problem pip; + pip.add_space_dimensions_and_embed(4, 0); + + bool ok = (pip.solve() == OPTIMIZED_PIP_PROBLEM); + if (ok) { + const PIP_Tree solution = pip.solution(); + ok &= solution->OK(); + pip.print_solution(nout); + } + return ok; +} + +bool +test14() { + // Trivial PIP problem with 4 variables and 4 parameters. + PIP_Problem pip; + pip.add_space_dimensions_and_embed(4, 4); + + bool ok = (pip.solve() == OPTIMIZED_PIP_PROBLEM); + if (ok) { + const PIP_Tree solution = pip.solution(); + ok &= solution->OK(); + pip.print_solution(nout); + } + return ok; +} + +bool +test15() { + PIP_Problem pip; + // Adding trivial satisfiable constraint. + pip.add_constraint(Linear_Expression(5) == 5); + + bool ok = (pip.solve() == OPTIMIZED_PIP_PROBLEM); + if (ok) { + const PIP_Tree solution = pip.solution(); + ok &= solution->OK(); + pip.print_solution(nout); + } + return ok; +} + +bool +test16() { + PIP_Problem pip; + // Adding trivial unsatisfiable constraint. + pip.add_constraint(Linear_Expression(0) == 1); + bool ok = (pip.solve() == UNFEASIBLE_PIP_PROBLEM); + if (pip.solution() != 0) + pip.print_solution(nout); + return ok; +} + } // namespace BEGIN_MAIN @@ -324,4 +409,10 @@ BEGIN_MAIN DO_TEST_F8(test08); DO_TEST_F8(test09); DO_TEST_F8(test10); + DO_TEST(test11); + DO_TEST(test12); + DO_TEST(test13); + DO_TEST(test14); + DO_TEST(test15); + // DO_TEST(test16); END_MAIN