Module: ppl/ppl Branch: master Commit: 2fad4a9428627c5d0ca8142567ac754ceab0e855 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2fad4a9428627... Author: François Galea <francois.galea@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