Module: ppl/ppl Branch: master Commit: 802e03131e75ff1962b42a6b071afca7cdf65b85 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=802e03131e75f...

Author: Enea Zaffanella zaffanella@cs.unipr.it Date: Mon Mar 1 23:58:07 2010 +0100

Method PIP_Tree_Node::solve() now checks context feasibility when needed.

---

src/PIP_Problem.cc | 1 + src/PIP_Tree.cc | 24 ++++++++++++++++++++---- src/PIP_Tree.defs.hh | 7 +++++++ 3 files changed, 28 insertions(+), 4 deletions(-)

diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index 953ed23..1acb759 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -207,6 +207,7 @@ PPL::PIP_Problem::solve() const {

// Actually solve problem. x.current_solution = x.current_solution->solve(*this, + check_feasible_context, initial_context, parameters, external_space_dim); diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 5a0aafd..45427ae 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -678,6 +678,7 @@ PIP_Decision_Node::update_tableau(const PIP_Problem& pip,

PIP_Tree_Node* PIP_Decision_Node::solve(const PIP_Problem& pip, + const bool check_feasible_context, const Matrix& context, const Variables_Set& params, dimension_type space_dim) { @@ -688,7 +689,8 @@ PIP_Decision_Node::solve(const PIP_Problem& pip, add_artificial_parameters(context_true, all_params, space_dim, num_art_params); merge_assign(context_true, constraints_, all_params); - true_child = true_child->solve(pip, context_true, all_params, space_dim); + true_child = true_child->solve(pip, check_feasible_context, + context_true, all_params, space_dim);

if (false_child) { // Decision nodes with false child must have exactly one constraint @@ -697,7 +699,8 @@ PIP_Decision_Node::solve(const PIP_Problem& pip, Matrix& context_false = context_true; Row& last = context_false[context_false.num_rows()-1]; complement_assign(last, last, 1); - false_child = false_child->solve(pip, context_false, all_params, space_dim); + false_child = false_child->solve(pip, check_feasible_context, + context_false, all_params, space_dim); }

if (true_child != 0 || false_child != 0) { @@ -1603,6 +1606,7 @@ PIP_Solution_Node::update_tableau(const PIP_Problem& pip,

PIP_Tree_Node* PIP_Solution_Node::solve(const PIP_Problem& pip, + const bool check_feasible_context, const Matrix& ctx, const Variables_Set& params, dimension_type space_dim) { @@ -1614,6 +1618,16 @@ PIP_Solution_Node::solve(const PIP_Problem& pip, const dimension_type num_art_params = artificial_parameters.size(); add_artificial_parameters(context, all_params, space_dim, num_art_params); merge_assign(context, constraints_, all_params); + + // If needed, (re-)check feasibility of context. + if (check_feasible_context) { + Matrix ctx_copy(context); + if (!compatibility_check(ctx_copy)) { + delete this; + return 0; + } + } + const dimension_type not_a_dim = not_a_dimension();

// Main loop of the simplex algorithm. @@ -2001,7 +2015,8 @@ PIP_Solution_Node::solve(const PIP_Problem& pip, // Add parametric constraint to context. context.add_row(t_test); // Recusively solve true node wrt updated context. - t_node = t_node->solve(pip, context, all_params, space_dim); + t_node = t_node->solve(pip, check_feasible_context, + context, all_params, space_dim);

// Modify *this in place to become the "false" version of current node. PIP_Tree_Node* f_node = this; @@ -2016,7 +2031,8 @@ PIP_Solution_Node::solve(const PIP_Problem& pip, complement_assign(f_test, t_test, 1);

// Recusively solve false node wrt updated context. - f_node = f_node->solve(pip, context, all_params, space_dim); + f_node = f_node->solve(pip, check_feasible_context, + context, all_params, space_dim);

// Case analysis on recursive resolution calls outcome. if (t_node == 0) { diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index 54fcde9..ef6e23a 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -190,6 +190,10 @@ protected: \param pip The PIP_Problem object containing this node.

+ \param check_feasible_context + Whether the resolution process should (re-)check feasibility of + context (since the initial context may have been modified). + \param context The context, being a set of constraints on the parameters.

@@ -200,6 +204,7 @@ protected: The space dimension of parent, including artificial parameters. */ virtual PIP_Tree_Node* solve(const PIP_Problem& pip, + bool check_feasible_context, const Matrix& context, const Variables_Set& params, dimension_type space_dim) = 0; @@ -632,6 +637,7 @@ protected:

//! Implements pure virtual method PIP_Tree_Node::solve. virtual PIP_Tree_Node* solve(const PIP_Problem& pip, + bool check_feasible_context, const Matrix& context, const Variables_Set& params, dimension_type space_dim); @@ -765,6 +771,7 @@ protected:

//! Implements pure virtual method PIP_Tree_Node::solve. virtual PIP_Tree_Node* solve(const PIP_Problem& pip, + bool check_feasible_context, const Matrix& context, const Variables_Set& params, dimension_type space_dim);