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

Author: François Galea francois.galea@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; + } } } }