[PPL-devel] [GIT] ppl/ppl(pip): Integrated the solve method in the different PIP_Tree node classes.
François Galea
francois.galea at uvsq.fr
Thu Sep 10 14:51:14 CEST 2009
Module: ppl/ppl
Branch: pip
Commit: 2219c62d25286754de2df17ef5efc2cbd83c3085
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2219c62d25286754de2df17ef5efc2cbd83c3085
Author: François Galea <francois.galea at 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;
More information about the PPL-devel
mailing list