[PPL-devel] [GIT] ppl/ppl(master): Corrected bug in th ehandling of trivially satisfiable PIP problems.
Enea Zaffanella
zaffanella at cs.unipr.it
Thu Feb 18 16:08:57 CET 2010
Module: ppl/ppl
Branch: master
Commit: 0e480f958e85f6d0c50b57835aaaa8f4ba9026ab
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0e480f958e85f6d0c50b57835aaaa8f4ba9026ab
Author: Enea Zaffanella <zaffanella at 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
More information about the PPL-devel
mailing list