[PPL-devel] [GIT] ppl/ppl(termination): Eventually perform solution tree simplifications after incremental addition of parameter constraints .
François Galea
francois.galea at uvsq.fr
Mon Mar 8 10:44:16 CET 2010
Module: ppl/ppl
Branch: termination
Commit: 2fad4a9428627c5d0ca8142567ac754ceab0e855
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2fad4a9428627c5d0ca8142567ac754ceab0e855
Author: François Galea <francois.galea at uvsq.fr>
Date: Sun Mar 7 21:13:37 2010 +0100
Eventually perform solution tree simplifications after incremental addition of parameter constraints.
---
src/PIP_Tree.cc | 65 +++++++++++++++++++++++++++++++++++++++++++++++--
src/PIP_Tree.defs.hh | 3 ++
2 files changed, 65 insertions(+), 3 deletions(-)
diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index a5a7915..d970067 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -557,6 +557,18 @@ PIP_Tree_Node
constraints_.insert(expr >= 0);
}
+void
+PIP_Tree_Node::parent_merge() {
+ const PIP_Decision_Node& parent = *parent_;
+
+ // Merge the parent's artificial parameters.
+ artificial_parameters.insert(artificial_parameters.begin(),
+ parent.art_parameter_begin(),
+ parent.art_parameter_end());
+
+ PPL_ASSERT(OK());
+}
+
bool
PIP_Solution_Node::OK() const {
#ifndef NDEBUG
@@ -689,10 +701,12 @@ PIP_Decision_Node::solve(const PIP_Problem& pip,
add_artificial_parameters(context_true, all_params, space_dim,
num_art_params);
merge_assign(context_true, constraints_, all_params);
+ bool has_false_child = (false_child != 0);
+ bool has_true_child = (true_child != 0);
true_child = true_child->solve(pip, check_feasible_context,
context_true, all_params, space_dim);
- if (false_child) {
+ if (has_false_child) {
// Decision nodes with false child must have exactly one constraint
PPL_ASSERT(1 == std::distance(constraints_.begin(), constraints_.end()));
// NOTE: modify context_true in place, complementing its last constraint.
@@ -704,8 +718,53 @@ PIP_Decision_Node::solve(const PIP_Problem& pip,
}
if (true_child != 0 || false_child != 0) {
- PPL_ASSERT(OK());
- return this;
+ PIP_Tree_Node* node = this;
+ if (has_false_child && false_child == 0) {
+ // False child has become unfeasible: merge this node's artificials with
+ // the true child, while removing the local parameter constraints, which
+ // are no longer discriminative.
+ true_child->parent_merge();
+ true_child->set_parent(parent());
+ node = true_child;
+ true_child = 0;
+ delete this;
+ }
+ else if (has_true_child && true_child == 0) {
+ // True child has become unfeasible: merge this node's artificials
+ // with the false child.
+ false_child->parent_merge();
+ false_child->set_parent(parent());
+ node = false_child;
+ false_child = 0;
+ delete this;
+ }
+ else if (check_feasible_context) {
+ // Test all constraints for redundancy with the context, and eliminate
+ // them if not necessary.
+ Constraint_System cs;
+ cs.swap(constraints_);
+ const Constraint_System::const_iterator end = cs.end();
+ for (Constraint_System::const_iterator ci = cs.begin(); ci != end; ++ci) {
+ Matrix ctx_copy(context);
+ merge_assign(ctx_copy, Constraint_System(*ci), all_params);
+ Row& last = ctx_copy[ctx_copy.num_rows()-1];
+ complement_assign(last, last, 1);
+ if (compatibility_check(ctx_copy)) {
+ // The constraint is not redundant with the context: we must keep it.
+ constraints_.insert(*ci);
+ }
+ }
+ // If the constraints set has become empty, only keep the true child.
+ if (constraints_.empty()) {
+ true_child->parent_merge();
+ true_child->set_parent(parent());
+ node = true_child;
+ true_child = 0;
+ delete this;
+ }
+ }
+ PPL_ASSERT(node->OK());
+ return node;
}
else {
delete this;
diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh
index ada4280..2d94c5f 100644
--- a/src/PIP_Tree.defs.hh
+++ b/src/PIP_Tree.defs.hh
@@ -212,6 +212,9 @@ protected:
//! Inserts a new parametric constraint in internal Row format
void add_constraint(const Row& x, const Variables_Set& parameters);
+ //! Merges parent's artificial parameters into \p *this.
+ void parent_merge();
+
//! Prints on \p s the tree rooted in \p *this.
/*!
\param s
More information about the PPL-devel
mailing list