Module: ppl/ppl Branch: pip Commit: caaa126b56ccb07884217b33b6cc8c1f79e7f6ca URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=caaa126b56ccb...
Author: Enea Zaffanella zaffanella@cs.unipr.it Date: Fri Feb 4 17:22:07 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 | 55 ++++++++++++++++++++++++++++++++++++++++++++++--------- 1 files changed, 46 insertions(+), 9 deletions(-)
diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index e167ea3..1a21047 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -2880,19 +2880,56 @@ 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); + // t_node feasible, f_node unfeasible. #ifdef NOISY_PIP_TREE_STRUCTURE indent_and_print(std::cerr, indent_level, "=== EXIT: THEN BRANCH FEASIBLE\n"); #endif - // It is now safe to release previously wrapped t_node pointer - // and return it to caller. - return wrapped_node.release(); + // 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); + /* FIXME: delete this; */ + // 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 { + /* FIXME: delete this; */ + // 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: