Module: ppl/ppl Branch: pip Commit: 233be8bdca82973ae4f3ac475c9f672b861c7540 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=233be8bdca829... Author: François Galea <francois.galea@uvsq.fr> Date: Tue Sep 29 16:25:02 2009 +0200 Added support for adding constraints in initial context. --- src/PIP_Problem.cc | 50 +++++++++++++++++++++++++++++++++++-- src/PIP_Problem.defs.hh | 7 +++++ src/PIP_Problem.templates.hh | 3 +- src/PIP_Tree.cc | 11 ++++++-- tests/PIP_Problem/pipproblem1.cc | 2 + 5 files changed, 66 insertions(+), 7 deletions(-) diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index a772079..4186408 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -39,7 +39,8 @@ PPL::PIP_Problem::PIP_Problem(dimension_type dim) initialized(false), input_cs(), first_pending_constraint(0), - parameters() { + parameters(), + initial_context() { // Check for space dimension overflow. if (dim > max_space_dimension()) throw std::length_error("PPL::PIP_Problem:: PIP_Problem(dim):\n" @@ -56,7 +57,8 @@ PPL::PIP_Problem::PIP_Problem(const PIP_Problem &y) initialized(y.initialized), input_cs(y.input_cs), first_pending_constraint(y.first_pending_constraint), - parameters(y.parameters) { + parameters(y.parameters), + initial_context(y.initial_context) { PPL_ASSERT(OK()); } @@ -83,6 +85,40 @@ PPL::PIP_Problem::solve() const { return OPTIMIZED_PIP_PROBLEM; } + //look for constraints with only parameter coefficients + Constraint_Sequence::const_iterator c; + Constraint_Sequence::const_iterator c_end = input_cs.end(); + Variables_Set::iterator param_begin = parameters.begin(); + Variables_Set::iterator param_end = parameters.end(); + Variables_Set::iterator pi; + dimension_type i; + + // resize context matrix properly + dimension_type num_params = parameters.size()+1; + dimension_type num_cols = initial_context.num_columns(); + if (num_cols < num_params) + x.initial_context.add_zero_columns(num_params-num_cols); + + for (c = input_cs.begin()+first_pending_constraint; c != c_end; ++c) { + dimension_type width = c->space_dimension(); + if (external_space_dim < width) + x.external_space_dim = width; + for (i = 0; i < width; ++i) { + if (c->coefficient(Variable(i)) != 0 && parameters.count(i) == 0) + /* nonzero variable coefficient, constraint not to be inserted + in context */ + break; + } + if (i == width) { + // At this point, the constraint must be translated into context row + Row row(num_params, Row::Flags()); + for (pi = param_begin, i = 1; pi != param_end; ++pi, ++i) + row[i] = c->coefficient(Variable(*pi)); + row[0] = c->inhomogeneous_term(); + x.initial_context.add_row(row); + } + } + x.current_solution->update_tableau(external_space_dim, first_pending_constraint, input_cs, @@ -90,7 +126,6 @@ PPL::PIP_Problem::solve() const { x.internal_space_dim = external_space_dim; x.first_pending_constraint = input_cs.size(); - Matrix initial_context(0, parameters.size()+1); return_value = x.current_solution->solve(x.current_solution, initial_context); @@ -162,6 +197,9 @@ PPL::PIP_Problem::ascii_dump(std::ostream& s) const { s << "\nparameters"; parameters.ascii_dump(s); + + s << "\ninitial_context"; + initial_context.ascii_dump(s); } PPL_OUTPUT_DEFINITIONS(PIP_Problem) @@ -239,6 +277,12 @@ PPL::PIP_Problem::ascii_load(std::istream& s) { if (!parameters.ascii_load(s)) return false; + if (!(s >> str) || str != "initial_context") + return false; + + if (!initial_context.ascii_load(s)) + return false; + PPL_ASSERT(OK()); return true; } diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh index 3accf0e..a8317bc 100644 --- a/src/PIP_Problem.defs.hh +++ b/src/PIP_Problem.defs.hh @@ -327,6 +327,13 @@ private: interpreted as problem parameters. */ Variables_Set parameters; + + /*! \brief + The initial context + + Contains problem constraints on parameters only + */ + Matrix initial_context; }; namespace std { diff --git a/src/PIP_Problem.templates.hh b/src/PIP_Problem.templates.hh index 8e8c22f..6594990 100644 --- a/src/PIP_Problem.templates.hh +++ b/src/PIP_Problem.templates.hh @@ -39,7 +39,8 @@ PIP_Problem::PIP_Problem(dimension_type dim, initialized(false), input_cs(), first_pending_constraint(0), - parameters(p_vars) { + parameters(p_vars), + initial_context() { // Check that integer Variables_Set does not exceed the space dimension // of the problem. if (p_vars.space_dimension() > external_space_dim) { diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index b16c902..66d05be 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -615,9 +615,14 @@ PIP_Solution_Node::update_tableau(dimension_type external_space_dim, } } // FIXME: must handle equality constraints - tableau.s.add_row(var); - tableau.t.add_row(param); - sign.push_back(row_sign(param)); + if (row_sign(var) != ZERO) { + /* parametric-only constraints have already been inserted in initial + context, so no need to insert them in the tableau + */ + tableau.s.add_row(var); + tableau.t.add_row(param); + sign.push_back(row_sign(param)); + } } } diff --git a/tests/PIP_Problem/pipproblem1.cc b/tests/PIP_Problem/pipproblem1.cc index 5d0f563..4895eb8 100644 --- a/tests/PIP_Problem/pipproblem1.cc +++ b/tests/PIP_Problem/pipproblem1.cc @@ -79,6 +79,8 @@ test01() { cs.insert(X1 + I0 - N >= 0); cs.insert(-X1 - I0 + N >= 0); cs.insert(X2 + J0 - N - 1 >= 0); + cs.insert(I0 >= 1); + cs.insert(N >= 1); PIP_Problem pip(cs.space_dimension(), cs.begin(), cs.end(), params);