Module: ppl/ppl Branch: ppl-0_11-branch Commit: 3992ea8c7b4688f53fd7c7b60a8bcc6a6bf97bf0 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3992ea8c7b468... Author: Enea Zaffanella <zaffanella@cs.unipr.it> Date: Fri Feb 11 10:49:35 2011 +0100 Fixed a bug in the simplification of the solution tree. We were too eager in merging a single true child with its parent: if the true child happened to be a decision node with both childs, the merging was causing the violation of a PIP_Decision_Node invariant. --- src/PIP_Tree.cc | 53 ++++++++++++++++++++++++++++++++++++++++++++--------- 1 files changed, 44 insertions(+), 9 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 28cc5f8..c06545c 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -2224,15 +2224,50 @@ PIP_Solution_Node::solve(const PIP_Problem& pip, } } else if (f_node == 0) { - // t_node feasible, f_node unfeasible: - // restore cs and aps into t_node. - t_node->constraints_.swap(cs); - t_node->artificial_parameters.swap(aps); - // Add t_test to t_nodes's constraints. - t_node->add_constraint(t_test, all_params); - // It is now safe to release previously wrapped t_node pointer - // and return it to caller. - return wrapped_node.release(); + // t_node feasible, f_node unfeasible. + // NOTE: in principle, we could merge t_node into its parent. + // However, if t_node is a decision node having both childs, + // then we would obtain a node violating the PIP_Decision_Node + // invariant saying that t_node should have a single constraint: + // it will have, at least, the two splitting constraints. + PIP_Decision_Node* dn = dynamic_cast<PIP_Decision_Node*>(t_node); + if (dn != 0 && dn->false_child != 0) { + // Do NOT merge: create a new decision node. + PIP_Tree_Node* parent + = new PIP_Decision_Node(t_node->get_owner(), 0, t_node); + // Previously wrapped 't_node' is now safe: release it + // and protect new 'parent' node from exception safety issues. + wrapped_node.release(); + wrapped_node.reset(parent); + // Restore into parent `cs' and `aps'. + parent->constraints_.swap(cs); + parent->artificial_parameters.swap(aps); + // Add t_test to parent's constraints. + parent->add_constraint(t_test, all_params); + // It is now safe to release previously wrapped parent pointer + // and return it to caller. + return wrapped_node.release(); + } + else { + // Merge t_node with its parent: + // a) append into `cs' the constraints of t_node; + for (Constraint_System::const_iterator + i = t_node->constraints_.begin(), + i_end = t_node->constraints_.end(); i != i_end; ++i) + cs.insert(*i); + // b) append into `aps' the parameters of t_node; + aps.insert(aps.end(), + t_node->artificial_parameters.begin(), + t_node->artificial_parameters.end()); + // c) swap the updated `cs' and `aps' into t_node. + cs.swap(t_node->constraints_); + aps.swap(t_node->artificial_parameters); + // d) add t_test to t_nodes's constraints. + t_node->add_constraint(t_test, all_params); + // It is now safe to release previously wrapped t_node pointer + // and return it to caller. + return wrapped_node.release(); + } } // Here both t_node and f_node are feasible: