[PPL-devel] [GIT] ppl/ppl(pip): Added support for adding constraints in initial context .
François Galea
francois.galea at uvsq.fr
Tue Sep 29 17:01:35 CEST 2009
Module: ppl/ppl
Branch: pip
Commit: 233be8bdca82973ae4f3ac475c9f672b861c7540
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=233be8bdca82973ae4f3ac475c9f672b861c7540
Author: François Galea <francois.galea at 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);
More information about the PPL-devel
mailing list