Module: ppl/ppl Branch: pip Commit: 2219c62d25286754de2df17ef5efc2cbd83c3085 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2219c62d25286... Author: François Galea <francois.galea@uvsq.fr> Date: Thu Sep 10 14:48:21 2009 +0200 Integrated the solve method in the different PIP_Tree node classes. --- src/PIP_Problem.cc | 6 ++-- src/PIP_Problem.defs.hh | 2 +- src/PIP_Tree.cc | 40 ++++++++++++++++++++++++-- src/PIP_Tree.defs.hh | 71 +++++++++++++++++++++++++++++++++++++++++++++- 4 files changed, 109 insertions(+), 10 deletions(-) diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index f1b4977..86777f5 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -85,9 +85,9 @@ PPL::PIP_Problem::solve() const { input_cs, parameters); - //FIXME: implement the simplex algorithm - - return_value = OPTIMIZED_PIP_PROBLEM; + Constraint_System initial_context; + return_value = x.current_solution->solve(&x.current_solution, + initial_context); switch (return_value) { case UNFEASIBLE_PIP_PROBLEM: diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh index c1f69eb..58ebff5 100644 --- a/src/PIP_Problem.defs.hh +++ b/src/PIP_Problem.defs.hh @@ -322,7 +322,7 @@ private: dimension_type first_pending_constraint; /*! \brief - A set containing all the indexes of space dimensions that are + A set containing all the indices of space dimensions that are interpreted as problem parameters. */ Variables_Set parameters; diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index fc6e1db..db52260 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -79,19 +79,46 @@ PIP_Decision_Node::update_tableau(PIP_Tree_Node **parent_ref, dimension_type first_pending_constraint, const Constraint_Sequence &input_cs, const Variables_Set ¶meters) { - true_child->update_tableau(parent_ref, + true_child->update_tableau(&true_child, external_space_dim, first_pending_constraint, input_cs, parameters); if (false_child) - false_child->update_tableau(parent_ref, + false_child->update_tableau(&false_child, external_space_dim, first_pending_constraint, input_cs, parameters); } +PIP_Problem_Status +PIP_Decision_Node::solve(PIP_Tree_Node **parent_ref, + const Constraint_System& context) { + PIP_Problem_Status return_status; + PIP_Problem_Status stt; + PIP_Problem_Status stf = UNFEASIBLE_PIP_PROBLEM; + Constraint_System context_true(context); + //FIXME: not implemented yet (merging of constraint systems) + //context_true.merge(_constraints); + stt = true_child->solve(&true_child, context_true); + if (false_child) { + // Decision nodes with false child must have exactly one constraint + PPL_ASSERT(_constraints.num_rows() == 1); + Constraint_System context_false(context); + //FIXME: not implemented yet (constraint negation) + //context_false.insert(!_constraints[0]); + stf = false_child->solve(&false_child, context_false); + } + + if (stt == UNFEASIBLE_PIP_PROBLEM && stf == UNFEASIBLE_PIP_PROBLEM) { + return_status = UNFEASIBLE_PIP_PROBLEM; + *parent_ref = 0; + delete this; + return UNFEASIBLE_PIP_PROBLEM; + } + return OPTIMIZED_PIP_PROBLEM; +} void PIP_Solution_Node::Rational_Matrix::normalize() { @@ -153,8 +180,6 @@ PIP_Solution_Node::update_tableau(PIP_Tree_Node **parent_ref, dimension_type i, j; dimension_type n_params = parameters.size(); dimension_type n_vars = external_space_dim - n_params; - dimension_type n_vars_int = tableau.s.num_columns(); - dimension_type n_constr_int = tableau.s.num_rows(); dimension_type internal_space_dim = tableau.t.num_columns()-1; Constraint_Sequence::const_iterator cst; @@ -218,4 +243,11 @@ PIP_Solution_Node::update_tableau(PIP_Tree_Node **parent_ref, // FIXME: decide emptiness detection (and node removal) } +PIP_Problem_Status +PIP_Solution_Node::solve(PIP_Tree_Node **parent_ref, + const Constraint_System& context) { + //FIXME + return OPTIMIZED_PIP_PROBLEM; +} + } // namespace Parma_Polyhedra_Library diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index bf46c8e..64debe6 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -89,6 +89,22 @@ protected: dimension_type first_pending_constraint, const Constraint_Sequence &input_cs, const Variables_Set ¶meters) = 0; + + /*! \brief + Execute a parametric simplex on the tableau, under specified context. + + \param parent_ref + a pointer to the parent reference to \p this + + \param context + the context, being a set of constraints on the parameters + + \return + An PIP_Problem_Status flag indicating the outcome of the optimization + attempt (unfeasible or optimized problem). + */ + virtual PIP_Problem_Status solve(PIP_Tree_Node **parent_ref, + const Constraint_System& context) = 0; }; //! A tree node representing part of the space of solutions. @@ -114,7 +130,14 @@ public: */ const Linear_Expression& parametric_values(Variable v); - //! Returns the constraints (on variables and parameters) of \p *this. + /*! \brief + Returns the system of parameter constraints controlling \p *this. + + The column indices in the constraints are numbered from \c 0 to + <tt>np-1</tt>, where \c np is the total number of parameters. They are + ordered with the same order as the parameter indices in the original + problem. + */ const Constraint_System& constraints(); void ascii_dump(std::ostream& s) const; @@ -200,6 +223,9 @@ private: */ std::vector<dimension_type> mapping; + //! The local system of parameter constraints + Constraint_System _constraints; + protected: /*! \brief Populates the parametric simplex tableau using external data, if necessary @@ -226,6 +252,21 @@ protected: const Constraint_Sequence &input_cs, const Variables_Set ¶meters); + /*! \brief + Execute a parametric simplex on the tableau, under specified context. + + \param parent_ref + a pointer to the parent reference to \p this + + \param context + the context, being a set of constraints on the parameters + + \return + An PIP_Problem_Status flag indicating the outcome of the optimization + attempt (unfeasible or optimized problem). + */ + virtual PIP_Problem_Status solve(PIP_Tree_Node **parent_ref, + const Constraint_System& context); // FIXME: constructors to be decided. }; @@ -247,7 +288,14 @@ public: //! Returns a pointer to the \p v (true or false) branch of \p *this. PIP_Tree_Node* child_node(bool v); - //! Returns the system of constraints controlling \p *this. + /*! \brief + Returns the system of parameter constraints controlling \p *this. + + The column indices in the constraints are numbered from \c 0 to + <tt>np-1</tt>, where \c np is the total number of parameters. They are + ordered with the same order as the parameter indices in the original + problem. + */ const Constraint_System& constraints(); private: @@ -257,6 +305,9 @@ private: //! Pointer to the "false" child of \p *this. PIP_Tree_Node* false_child; + //! The local system of parameter constraints + Constraint_System _constraints; + /*! \brief Constructs if \p cs then \p tcp \p else \p fcp. @@ -318,6 +369,22 @@ protected: dimension_type first_pending_constraint, const Constraint_Sequence &input_cs, const Variables_Set ¶meters); + + /*! \brief + Execute a parametric simplex on the tableau, under specified context. + + \param parent_ref + a pointer to the parent reference to \p this + + \param context + the context, being a set of constraints on the parameters + + \return + An PIP_Problem_Status flag indicating the outcome of the optimization + attempt (unfeasible or optimized problem). + */ + virtual PIP_Problem_Status solve(PIP_Tree_Node **parent_ref, + const Constraint_System& context); }; typedef const PIP_Tree_Node* PIP_Tree;