[PPL-devel] [GIT] ppl/ppl(pip): Fixed a bug in the simplification of the solution tree.

[Enea Zaffanella]

Module: ppl/ppl
Branch: pip
Commit: caaa126b56ccb07884217b33b6cc8c1f79e7f6ca
URL:    http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=caaa126b56ccb07884217b33b6cc8c1f79e7f6ca

Author: Enea Zaffanella <zaffanella at 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: