[PPL-devel] [GIT] ppl/ppl(pip): Implemented simplex basis and tableau initialization in PIP solver.
François Galea
francois.galea at uvsq.fr
Fri Sep 4 15:20:42 CEST 2009
Module: ppl/ppl
Branch: pip
Commit: 2690fc065429c1855d3188958dd843aef6a13875
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2690fc065429c1855d3188958dd843aef6a13875
Author: François Galea <francois.galea at uvsq.fr>
Date: Fri Sep 4 14:53:38 2009 +0200
Implemented simplex basis and tableau initialization in PIP solver.
---
src/PIP_Problem.cc | 95 +++++++++++++++++++++++++++++++++++++++++-
src/PIP_Problem.defs.hh | 12 ++++-
src/PIP_Problem.inlines.hh | 12 +++++-
src/PIP_Problem.templates.hh | 1 +
4 files changed, 115 insertions(+), 5 deletions(-)
diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc
index 5a561a9..dece4ef 100644
--- a/src/PIP_Problem.cc
+++ b/src/PIP_Problem.cc
@@ -40,6 +40,7 @@ PPL::PIP_Problem::PIP_Problem(dimension_type dim)
: external_space_dim(dim),
internal_space_dim(0),
tableau(),
+ basis(),
status(PARTIALLY_SATISFIABLE),
initialized(false),
input_cs(),
@@ -57,6 +58,7 @@ PPL::PIP_Problem::PIP_Problem(const PIP_Problem &y)
: external_space_dim(y.external_space_dim),
internal_space_dim(y.internal_space_dim),
tableau(y.tableau),
+ basis(y.basis),
status(y.status),
initialized(y.initialized),
input_cs(y.input_cs),
@@ -67,8 +69,97 @@ PPL::PIP_Problem::PIP_Problem(const PIP_Problem &y)
PPL::PIP_Problem_Status
PPL::PIP_Problem::solve() const {
- //FIXME
- return OPTIMIZED_PIP_PROBLEM;
+ switch (status) {
+ case UNSATISFIABLE:
+ PPL_ASSERT(OK());
+ return UNFEASIBLE_PIP_PROBLEM;
+ case OPTIMIZED:
+ PPL_ASSERT(OK());
+ return OPTIMIZED_PIP_PROBLEM;
+ case SATISFIABLE:
+ // Intentionally fall through
+ case PARTIALLY_SATISFIABLE:
+ {
+ PIP_Problem& x = const_cast<PIP_Problem&>(*this);
+ PIP_Problem_Status return_value;
+
+ x.update_tableau();
+ //FIXME: implement the simplex algorithm
+
+ return_value = OPTIMIZED_PIP_PROBLEM;
+
+ switch (return_value) {
+ case UNFEASIBLE_PIP_PROBLEM:
+ x.status = UNSATISFIABLE;
+ break;
+ case OPTIMIZED_PIP_PROBLEM:
+ x.status = OPTIMIZED;
+ break;
+ }
+ PPL_ASSERT(OK());
+ return return_value;
+ }
+ }
+ // We should not be here!
+ throw std::runtime_error("PPL internal error");
+}
+
+void
+PPL::PIP_Problem::update_tableau() {
+ dimension_type i;
+ 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();
+ const_iterator cst;
+
+ if (tableau.t.num_columns() == 0) {
+ // Create the parameter column, corresponding to the constant term
+ tableau.t.add_zero_columns(1);
+ }
+
+ for (i=internal_space_dim; i<external_space_dim; ++i) {
+ // add new columns to the tableau
+ if (parameters.count(i) == 1)
+ tableau.t.add_zero_columns(1);
+ else
+ tableau.s.add_zero_columns(1);
+ }
+ internal_space_dim = external_space_dim;
+
+ Coefficient denom_s = tableau.s.get_denominator();
+ Coefficient denom_t = tableau.t.get_denominator();
+
+ for (cst = constraints_begin() + first_pending_constraint;
+ cst < constraints_end(); ++cst) {
+ // FIXME: must handle nonbasic variables aswell
+ int v = 0;
+ int p = 1;
+ Row var(n_vars, Row::Flags());
+ Row param(n_params+1, Row::Flags());
+ Coefficient cnst_term = -cst->inhomogeneous_term();
+ if (cst->is_strict_inequality())
+ // convert c > 0 <=> c-1 >= 0
+ cnst_term -= 1;
+ param[0] = cnst_term * denom_t;
+ for (i=0; i<internal_space_dim; i++) {
+ if (parameters.count(i) == 1) {
+ param[p] = cst->coefficient(Variable(i)) * denom_t;
+ ++p;
+ } else {
+ var[v] = cst->coefficient(Variable(i)) * denom_s;
+ ++v;
+ }
+ }
+ //FIXME: must handle equality constraints
+ tableau.s.add_row(var);
+ tableau.t.add_row(param);
+ }
+
+ // update current basis with newly inserted variables
+ dimension_type next_var = n_vars_int + n_constr_int;
+ for (i=n_vars_int; i<n_vars; ++i)
+ basis.insert(next_var++);
}
diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh
index 818f785..e724c7e 100644
--- a/src/PIP_Problem.defs.hh
+++ b/src/PIP_Problem.defs.hh
@@ -320,8 +320,8 @@ private:
*/
void normalize();
- //! Tests whether the matrix is integer, \e ie. the denominator is 1.
- bool is_integer();
+ //! Tests whether the matrix is integer, \e ie. the denominator is 1.
+ bool is_integer() const;
//! Returns the value of the denominator.
const Coefficient &get_denominator() const;
@@ -344,6 +344,9 @@ private:
//! The parametric simplex tableau.
Tableau tableau;
+ //! A set containing the internal indices of the basic variables
+ Variables_Set basis;
+
//! An enumerated type describing the internal status of the PIP problem.
enum Status {
//! The PIP problem is unsatisfiable.
@@ -381,6 +384,11 @@ private:
interpreted as problem parameters.
*/
Variables_Set parameters;
+
+ /*! \brief
+ Populates the parametric simplex tableau using external data, if necessary
+ */
+ void update_tableau();
};
namespace std {
diff --git a/src/PIP_Problem.inlines.hh b/src/PIP_Problem.inlines.hh
index 4dcb55b..c064ae9 100644
--- a/src/PIP_Problem.inlines.hh
+++ b/src/PIP_Problem.inlines.hh
@@ -46,7 +46,7 @@ PIP_Problem::Rational_Matrix::Rational_Matrix(const Rational_Matrix& y)
}
inline bool
-PIP_Problem::Rational_Matrix::is_integer() {
+PIP_Problem::Rational_Matrix::is_integer() const {
return denominator == 1;
}
@@ -64,6 +64,16 @@ PIP_Problem::max_space_dimension() {
return Constraint::max_space_dimension();
}
+inline PIP_Problem::const_iterator
+PIP_Problem::constraints_begin() const {
+ return input_cs.begin();
+}
+
+inline PIP_Problem::const_iterator
+PIP_Problem::constraints_end() const {
+ return input_cs.end();
+}
+
} // namespace Parma_Polyhedra_Library
namespace std {
diff --git a/src/PIP_Problem.templates.hh b/src/PIP_Problem.templates.hh
index 3f474d2..76e8ecf 100644
--- a/src/PIP_Problem.templates.hh
+++ b/src/PIP_Problem.templates.hh
@@ -35,6 +35,7 @@ PIP_Problem::PIP_Problem(dimension_type dim,
: external_space_dim(dim),
internal_space_dim(0),
tableau(),
+ basis(),
status(PARTIALLY_SATISFIABLE),
initialized(false),
input_cs(),
More information about the PPL-devel
mailing list