[PPL-devel] [GIT] ppl/ppl(pip): Added additional check in simplex, leading to simpler decision trees.

[François Galea]

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

Author: François Galea <francois.galea at uvsq.fr>
Date:   Thu Sep 24 11:55:41 2009 +0200

Added additional check in simplex, leading to simpler decision trees.

---

 src/PIP_Tree.cc                 |   33 +++++++++++++++++++++++++++++++++
 tests/PIP_Problem/pipproblem.cc |   11 +++++++----
 2 files changed, 40 insertions(+), 4 deletions(-)

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index 1f904eb..1012838 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -713,6 +713,39 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref,
       }
     }
 
+    /* If there remains a row i with undetermined sign and at least one
+       positive S_ij coefficient, where constraint t_i(z) > 0 is not
+       compatible with the context, the row parameter can be considered
+       negative
+    */
+    if (i_ == n_a_d && i__ != n_a_d) {
+      for (i=i__; i<num_rows; ++i) {
+        if (sign[i] != MIXED)
+          continue;
+        bool found = false;
+        const Row &p = tableau.s[i];
+        for (j=0; j<num_vars; ++j)
+          if (p[j] > 0) {
+            found = true;
+            break;
+          }
+        if (!found)
+          continue;
+        Row row(tableau.t[i]);
+        row[0] -= 1;
+        if (compatibility_check(context, row)) {
+          if (i__ == n_a_d)
+            i__ = i;
+        } else {
+          sign[i] = NEGATIVE;
+          if (i_ == n_a_d)
+            i_ = i;
+          if (i__ == i)
+            i__ = n_a_d;
+        }
+      }
+    }
+
     /* If we have found a row i_ with negative parameters :
        Either the problem is empty, or a pivoting step is required
     */
diff --git a/tests/PIP_Problem/pipproblem.cc b/tests/PIP_Problem/pipproblem.cc
index 8d84a95..6050cd0 100644
--- a/tests/PIP_Problem/pipproblem.cc
+++ b/tests/PIP_Problem/pipproblem.cc
@@ -32,7 +32,8 @@ display_solution(const PIP_Tree pip, const Variables_Set &vars, int indent=0) {
     nout << setw(indent*2) << "" << "_|_" << endl;
   } else {
     const Constraint_System &constraints = pip->constraints();
-    if (!constraints.empty()) {
+    bool constraints_empty = constraints.empty();
+    if (!constraints_empty) {
       nout << setw(indent*2) << "" << "if ";
       Constraint_System::const_iterator begin = constraints.begin();
       Constraint_System::const_iterator end = constraints.end();
@@ -51,12 +52,14 @@ display_solution(const PIP_Tree pip, const Variables_Set &vars, int indent=0) {
       Variables_Set::const_iterator begin = vars.begin();
       Variables_Set::const_iterator end = vars.end();
       Variables_Set::const_iterator i;
-      nout << setw(indent*2+2) << "" << "{";
+      nout << setw(indent*2+(constraints_empty?0:2)) << "" << "{";
       for (i=begin; i!=end; ++i)
         nout << ((i==begin)?"":" ; ") << sn->parametric_values(Variable(*i));
       nout << "}" << endl;
-      nout << setw(indent*2) << "" << "else" << endl;
-      nout << setw(indent*2+2) << "" << "_|_" << endl;
+      if (!constraints_empty) {
+        nout << setw(indent*2) << "" << "else" << endl;
+        nout << setw(indent*2+2) << "" << "_|_" << endl;
+      }
     }
   }
 }