November 2009 - PPL-devel - BUGSENG Mailman

Problem comiling ppl 0.10.2
by Pierre 07 Nov '09

07 Nov '09

# make make all-recursive make[1]: Entering directory `/tmp/ppl-0.10.2' Making all in . make[2]: Entering directory `/tmp/ppl-0.10.2' make[2]: Nothing to be done for `all-am'. make[2]: Leaving directory `/tmp/ppl-0.10.2' Making all in utils make[2]: Entering directory `/tmp/ppl-0.10.2/utils' make[2]: Nothing to be done for `all'. make[2]: Leaving directory `/tmp/ppl-0.10.2/utils' Making all in src make[2]: Entering directory `/tmp/ppl-0.10.2/src' g++ -DHAVE_CONFIG_H -I. -I.. -I.. -I../src -Winvalid-pch -g -O2 -march=x86 -frounding-math -s -O3 -march=i686 -W -Wall -xc++-header -o ppl.hh.gch ppl.hh ppl.hh: In function `void Parma_Polyhedra_Library::restore_pre_PPL_rounding()': ppl.hh:1002: error: `Parma_Polyhedra_Library::fpu_rounding_direction_type Parma_Polyhedra_Library::Init::old_rounding_direction' is private ppl.hh:1801: error: within this context ppl.hh:4678: confused by earlier errors, bailing out make[2]: *** [ppl.hh.gch] Error 1 make[2]: Leaving directory `/tmp/ppl-0.10.2/src' make[1]: *** [all-recursive] Error 1 make[1]: Leaving directory `/tmp/ppl-0.10.2' make: *** [all] Error 2

2 1

[GIT] ppl/ppl(pip): Fixed a bug.
by François Galea 05 Nov '09

05 Nov '09

Module: ppl/ppl Branch: pip Commit: b102f42050ad134d111fdaf9e92127e2a91ff927 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b102f42050ad… Author: François Galea <francois.galea(a)uvsq.fr> Date: Thu Nov 5 14:40:39 2009 +0100 Fixed a bug. --- src/PIP_Tree.cc | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 6228597..24cc78b 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -223,7 +223,7 @@ PIP_Solution_Node::PIP_Solution_Node(const PIP_Solution_Node &x) mapping(x.mapping), var_row(x.var_row), var_column(x.var_column), - special_equality_row(0), + special_equality_row(x.special_equality_row), sign(x.sign), solution(x.solution), solution_valid(x.solution_valid) {

1 0

Re: [PPL-devel] [GIT] ppl/ppl(pip): Added a standalone PIP solver demo program.
by Sven Verdoolaege 05 Nov '09

05 Nov '09

Perhaps you could also add a demo program with an interface like piplib's "example". That would make it easier to compare your solver to other pip solvers such as barvinok's lexmin and isl's isl_pip. skimo

3 13

[GIT] ppl/ppl(pip): Removed temporary debug code.
by François Galea 05 Nov '09

05 Nov '09

Module: ppl/ppl Branch: pip Commit: 09665b7e6410de11d9cebb7fbd93bd1c9f527223 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=09665b7e6410… Author: François Galea <francois.galea(a)uvsq.fr> Date: Thu Nov 5 14:19:36 2009 +0100 Removed temporary debug code. --- src/PIP_Tree.cc | 1 - 1 files changed, 0 insertions(+), 1 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index e6766bd..6228597 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -1030,7 +1030,6 @@ PIP_Solution_Node::update_tableau(dimension_type external_space_dim, var_row.push_back(var_id); } else { // The special constraint already exists and is nonbasic - std::cout << "bla\n"; dimension_type row = mapping[special_equality_row]; sub_assign(tableau.s[row], var); sub_assign(tableau.t[row], param);

1 0

[GIT] ppl/ppl(pip): Improved the support for equality constraints.
by François Galea 05 Nov '09

05 Nov '09

Module: ppl/ppl Branch: pip Commit: 0bc03d5786735188f81bd47ef078fa0bbedd44a3 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0bc03d578673… Author: François Galea <francois.galea(a)uvsq.fr> Date: Thu Nov 5 09:11:38 2009 +0100 Improved the support for equality constraints. --- src/PIP_Tree.cc | 47 +++++++++++++++++++++++++++++++++++++---------- src/PIP_Tree.defs.hh | 26 ++++++++++++++++++++++---- 2 files changed, 59 insertions(+), 14 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 6a26215..e6766bd 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -46,6 +46,14 @@ add_assign(Row& x, const Row& y, Coefficient_traits::const_reference c) { add_mul_assign(x[i], c, y[i]); } +// Compute x -= y +void +sub_assign(Row& x, const Row& y) { + PPL_ASSERT(x.size() == y.size()); + for (dimension_type i = x.size(); i-- > 0; ) + x[i] -= y[i]; +} + // Merge constraint system to a Matrix-form context such as x = x U y void merge_assign(Matrix& x, @@ -202,6 +210,7 @@ PIP_Solution_Node::PIP_Solution_Node() mapping(), var_row(), var_column(), + special_equality_row(0), sign(), solution(), solution_valid(false) { @@ -214,6 +223,7 @@ PIP_Solution_Node::PIP_Solution_Node(const PIP_Solution_Node &x) mapping(x.mapping), var_row(x.var_row), var_column(x.var_column), + special_equality_row(0), sign(x.sign), solution(x.solution), solution_valid(x.solution_valid) { @@ -227,6 +237,7 @@ PIP_Solution_Node::PIP_Solution_Node(const PIP_Solution_Node &x, mapping(x.mapping), var_row(x.var_row), var_column(x.var_column), + special_equality_row(x.special_equality_row), sign(x.sign), solution(x.solution), solution_valid(x.solution_valid) { @@ -949,6 +960,8 @@ PIP_Solution_Node::update_tableau(dimension_type external_space_dim, for (j = var_column.size(); j-- > 0; ) if (var_column[j] >= column) ++var_column[j]; + if (special_equality_row > 0) + ++special_equality_row; } var_column.push_back(column); } @@ -998,16 +1011,30 @@ PIP_Solution_Node::update_tableau(dimension_type external_space_dim, mapping.push_back(row_id); var_row.push_back(var_id); if (cst->is_equality()) { - ++var_id; - ++row_id; - negate_assign(var, var, 0); - negate_assign(param, param, 0); - tableau.s.add_row(var); - tableau.t.add_row(param); - sign.push_back(row_sign(param)); - basis.push_back(false); - mapping.push_back(row_id); - var_row.push_back(var_id); + /* Handle equality constraints. After having added the f_i(x,p) >= 0 + constraint, we must add -f_i(x,p) to the special equality row */ + if (special_equality_row == 0 || basis[special_equality_row]) { + // The special constraint has not been created yet + /* FIXME: for now, we don't handle the case where the variable is + basic, and create a new row. This might be faster however. */ + ++var_id; + ++row_id; + negate_assign(var, var, 0); + negate_assign(param, param, 0); + tableau.s.add_row(var); + tableau.t.add_row(param); + sign.push_back(row_sign(param)); + special_equality_row = mapping.size(); + basis.push_back(false); + mapping.push_back(row_id); + var_row.push_back(var_id); + } else { + // The special constraint already exists and is nonbasic + std::cout << "bla\n"; + dimension_type row = mapping[special_equality_row]; + sub_assign(tableau.s[row], var); + sub_assign(tableau.t[row], param); + } } } } diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index e9746df..5711c8f 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -325,14 +325,32 @@ private: */ std::vector<dimension_type> mapping; - /*! A vector of the variable identifiers associated to each row of the - simplex tableau. */ + /*! \brief A vector of the variable identifiers associated to each row of + the simplex tableau. */ std::vector<dimension_type> var_row; - /*! A vector of the variable identifiers associated to each column of the - simplex tableau. */ + /*! \brief A vector of the variable identifiers associated to each column + of the simplex tableau. */ std::vector<dimension_type> var_column; + /*! \brief The variable number of the special inequality used for modelling + equality constraints. + + The subset of equality constraints in a specific problem can be expressed + as: \f$f_i(x,p) = 0 ; 1 \leq i \leq n\f$. As the dual simplex standard form + requires constraints to be inequalities, the following constraints can be + modelized the following way: + + - \f$f_i(x,p) \geq 0 ; 1 \leq i \leq n\f$ + + - \f$\sum\limits_{i=1}^n f_i(x,p) \leq 0\f$ + + The \p special_equality_row value stores the variable number of the + specific constraint which is used to modelize the latter sum of + constraints. If no such constraint exists, the value is set to \p 0. + */ + dimension_type special_equality_row; + //! The possible values for the sign of a parametric linear expression. enum Row_Sign { //! Not computed yet (default)

1 0

Re: [PPL-devel] Modified PPL 0.10.2 source distribution for Solaris
by alanpae＠ilkda.com 05 Nov '09

05 Nov '09

> Hi Alan, > > it seems the compiler you are using is buggy: according to the C++ > standard, size_t has to be provided by <cstddef> and <cstddef> is > included by globals.types.hh prior to the first reference to size_t. > All the best, > > Roberto Ok, the gmp that comes with OpenSolaris is not compatible with your program. So I downloaded the recent tarball and rebuilt it using your instructions in README.configure. ./configure on your program runs through with no errors. To avoid the Sun Studio issue I switched back to gcc. gcc --version gcc (GCC) 3.4.3 (csl-sol210-3_4-20050802) Copyright (C) 2004 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. This generates a new error. gmake all-am gmake[3]: Entering directory `/build/ppl-0.10.2/src' /bin/sh ../libtool --tag=CXX --mode=compile g++ -DHAVE_CONFIG_H -I. -I.. -I.. -I../src -I/opt/gmp/include -g -O2 -frounding-math -W -Wall -MT Box.lo -MD -MP -MF .deps/Box.Tpo -c -o Box.lo Box.cc libtool: compile: g++ -DHAVE_CONFIG_H -I. -I.. -I.. -I../src -I/opt/gmp/include -g -O2 -frounding-math -W -Wall -MT Box.lo -MD -MP -MF .deps/Box.Tpo -c Box.cc -fPIC -DPIC -o .libs/Box.o In file included from checked.defs.hh:595, from Checked_Number.defs.hh:27, from Coefficient.types.hh:15, from Coefficient.defs.hh:26, from Box.defs.hh:28, from Box.cc:24: checked.inlines.hh: In function `Parma_Polyhedra_Library::Result Parma_Polyhedra_Library::Checked::input_generic(Type&, std::istream&, Parma_Polyhedra_Library::Rounding_Dir)': checked.inlines.hh:607: internal compiler error: in invert_truthvalue, at fold-const.c:2695 Please submit a full bug report, with preprocessed source if appropriate. See <URL:http://gcc.gnu.org/bugs.html> for instructions. gmake[3]: *** [Box.lo] Error 1 gmake[3]: Leaving directory `/build/ppl-0.10.2/src' gmake[2]: *** [all] Error 2 gmake[2]: Leaving directory `/build/ppl-0.10.2/src' gmake[1]: *** [all-recursive] Error 1 gmake[1]: Leaving directory `/build/ppl-0.10.2' gmake: *** [all] Error 2 alan

2 1

[GIT] ppl/ppl(pip): Added coherency checks in PIP_Solution_Node.
by François Galea 04 Nov '09

04 Nov '09

Module: ppl/ppl Branch: pip Commit: 43721277fe737cf7f18c821f86cb04b41aeefd12 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=43721277fe73… Author: François Galea <francois.galea(a)uvsq.fr> Date: Wed Nov 4 08:56:45 2009 +0100 Added coherency checks in PIP_Solution_Node. --- src/PIP_Tree.cc | 62 ++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 files changed, 61 insertions(+), 1 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index f8cd682..c18ab54 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -364,7 +364,6 @@ PIP_Tree_Node bool PIP_Solution_Node::OK() const { - /* FIXME: finish me! */ #ifndef NDEBUG using std::endl; using std::cerr; @@ -377,6 +376,64 @@ PIP_Solution_Node::OK() const { if (!tableau.OK()) return false; + // Check coherency of basis, mapping, var_row and var_column + if (basis.size() != mapping.size()) { +#ifndef NDEBUG + cerr << "The PIP_Solution_Node::basis and PIP_Solution_Node::mapping " + << "vectors do not have the same number of elements." + << endl; +#endif + return false; + } + if (basis.size() != var_row.size() + var_column.size()) { +#ifndef NDEBUG + cerr << "The sum of number of elements in the PIP_Solution_Node::var_row " + << "and PIP_Solution_Node::var_column vectors is different from the " + << "number of elements in the PIP_Solution_Node::basis vector." + << endl; +#endif + return false; + } + if (var_column.size() != tableau.s.num_columns()) { +#ifndef NDEBUG + cerr << "The number of elements in the PIP_Solution_Node::var_column " + << "vector is different from the number of columns in the " + << "PIP_Solution_Node::tableau.s Matrix." + << endl; +#endif + return false; + } + if (var_row.size() != tableau.s.num_rows()) { +#ifndef NDEBUG + cerr << "The number of elements in the PIP_Solution_Node::var_row " + << "vector is different from the number of rows in the " + << "PIP_Solution_Node::tableau.s Matrix." + << endl; +#endif + return false; + } + for (dimension_type i = mapping.size(); i-- > 0; ) { + dimension_type rowcol = mapping[i]; + if (basis[i] && var_column[rowcol] != i) { +#ifndef NDEBUG + cerr << "Variable " << i << " is basic and corresponds to column " + << rowcol << " but PIP_Solution_Node::var_column[" << rowcol + << "] does not correspond to variable " << i << "." + << endl; +#endif + return false; + } + if (!basis[i] && var_row[rowcol] != i) { +#ifndef NDEBUG + cerr << "Variable " << i << " is nonbasic and corresponds to row " + << rowcol << " but PIP_Solution_Node::var_row[" << rowcol + << "] does not correspond to variable " << i << "." + << endl; +#endif + return false; + } + } + return true; } @@ -421,6 +478,7 @@ PIP_Decision_Node::update_tableau(dimension_type external_space_dim, first_pending_constraint, input_cs, parameters); + PPL_ASSERT(OK()); } PIP_Problem_Status @@ -949,6 +1007,7 @@ PIP_Solution_Node::update_tableau(dimension_type external_space_dim, } } } + PPL_ASSERT(OK()); } void @@ -997,6 +1056,7 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref, const Matrix& ctx, dimension_type num_vars = tableau.s.num_columns(); dimension_type num_params = tableau.t.num_columns(); Row_Sign s; + PPL_ASSERT(OK()); #ifdef NOISY_PIP tableau.ascii_dump(std::cout);

1 0

[GIT] ppl/ppl(pip): Improved basis handling in compatibility_check.
by François Galea 04 Nov '09

04 Nov '09

Module: ppl/ppl Branch: pip Commit: a2812b97dfea19043e0efe733684688e0f4efd61 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a2812b97dfea… Author: François Galea <francois.galea(a)uvsq.fr> Date: Wed Nov 4 11:51:36 2009 +0100 Improved basis handling in compatibility_check. --- src/PIP_Tree.cc | 48 ++++++++++++++++++++++++++---------------------- 1 files changed, 26 insertions(+), 22 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index c18ab54..6a26215 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -758,7 +758,6 @@ PIP_Solution_Node::compatibility_check(const Matrix &ctx, const Row &cnst) { dimension_type num_rows = s.num_rows(); dimension_type num_cols = s.num_columns(); dimension_type num_vars = num_cols-1; - const dimension_type n_a_d = not_a_dimension(); std::vector<Coefficient> scaling(num_rows, 1); PPL_DIRTY_TEMP_COEFFICIENT(sij); PPL_DIRTY_TEMP_COEFFICIENT(mult); @@ -766,9 +765,21 @@ PIP_Solution_Node::compatibility_check(const Matrix &ctx, const Row &cnst) { PPL_DIRTY_TEMP_COEFFICIENT(scale_factor); PPL_DIRTY_TEMP_COEFFICIENT(scaling_i); std::vector<dimension_type> mapping; - std::vector<bool> basis(num_vars, true); - for (j=1; j<=num_vars; ++j) + std::vector<bool> basis; + std::vector<dimension_type> var_row; + std::vector<dimension_type> var_column; + // Column 0 is the constant term, not a variable + var_column.push_back(not_a_dimension()); + for (j=1; j<=num_vars; ++j) { + basis.push_back(true); mapping.push_back(j); + var_column.push_back(j-1); + } + for (i=0; i<num_rows; ++i) { + basis.push_back(false); + mapping.push_back(i); + var_row.push_back(i+num_vars); + } Row p(num_cols, compute_capacity(num_cols, Matrix::max_num_columns()), Row::Flags()); @@ -815,6 +826,9 @@ PIP_Solution_Node::compatibility_check(const Matrix &ctx, const Row &cnst) { return true; } // Generate a new cut + var_row.push_back(mapping.size()); + basis.push_back(false); + mapping.push_back(num_rows); s.add_zero_rows(1, Row::Flags()); const Row& row = s[i_]; Row& cut = s[num_rows++]; @@ -827,26 +841,16 @@ PIP_Solution_Node::compatibility_check(const Matrix &ctx, const Row &cnst) { } // Now we have a positive s[i][j] pivot - var_j = n_a_d; - var_i = n_a_d; - for (j_=0; j_<num_vars; ++j_) { - if (basis[j_]) { - if (mapping[j_] == j) - var_j = j_; - } else { - if (mapping[j_] == i) - var_i = j_; - } - } + /* update basis */ - if (var_j != n_a_d) { - basis[var_j] = false; - mapping[var_j] = i; - } - if (var_i != n_a_d) { - basis[var_i] = true; - mapping[var_i] = j; - } + var_j = var_column[j]; + var_i = var_row[i]; + basis[var_j] = false; + mapping[var_j] = i; + basis[var_i] = true; + mapping[var_i] = j; + var_column[j] = var_i; + var_row[i] = var_j; /* create the identity matrix row corresponding to basic variable j */ for (j_=0; j_<num_cols; ++j_)

1 0

[GIT] ppl/ppl(pip): Improved basis handling with support for slack variables and bijective variable mapping .
by François Galea 04 Nov '09

04 Nov '09

Module: ppl/ppl Branch: pip Commit: 3c4cfb2bdf11e8a0c2064b5e4c71513d65625b62 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3c4cfb2bdf11… Author: François Galea <francois.galea(a)uvsq.fr> Date: Wed Nov 4 08:45:20 2009 +0100 Improved basis handling with support for slack variables and bijective variable mapping. --- src/PIP_Tree.cc | 69 ++++++++++++++++++++++++++++++++++---------------- src/PIP_Tree.defs.hh | 19 +++++++++++++ 2 files changed, 66 insertions(+), 22 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 4c47ff5..f8cd682 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -200,6 +200,8 @@ PIP_Solution_Node::PIP_Solution_Node() tableau(), basis(), mapping(), + var_row(), + var_column(), sign(), solution(), solution_valid(false) { @@ -210,6 +212,8 @@ PIP_Solution_Node::PIP_Solution_Node(const PIP_Solution_Node &x) tableau(x.tableau), basis(x.basis), mapping(x.mapping), + var_row(x.var_row), + var_column(x.var_column), sign(x.sign), solution(x.solution), solution_valid(x.solution_valid) { @@ -221,6 +225,8 @@ PIP_Solution_Node::PIP_Solution_Node(const PIP_Solution_Node &x, tableau(x.tableau), basis(x.basis), mapping(x.mapping), + var_row(x.var_row), + var_column(x.var_column), sign(x.sign), solution(x.solution), solution_valid(x.solution_valid) { @@ -862,9 +868,27 @@ PIP_Solution_Node::update_tableau(dimension_type external_space_dim, if (parameters.count(i) == 1) tableau.t.add_zero_columns(1); else { + dimension_type column = tableau.s.num_columns(); tableau.s.add_zero_columns(1); - basis.push_back(true); - mapping.push_back(tableau.s.num_columns()-1); + if (tableau.s.num_rows() == 0) { + // No rows have been added yet + basis.push_back(true); + mapping.push_back(column); + } else { + /* Need to insert the original variable id before the slack variable + id's to respect variable ordering */ + dimension_type j; + basis.insert(basis.begin()+column, true); + mapping.insert(mapping.begin()+column, column); + // update variable id's of slack variables + for (j = var_row.size(); j-- > 0; ) + if (var_row[j] >= column) + ++var_row[j]; + for (j = var_column.size(); j-- > 0; ) + if (var_column[j] >= column) + ++var_column[j]; + } + var_column.push_back(column); } } internal_space_dim = external_space_dim; @@ -903,15 +927,25 @@ PIP_Solution_Node::update_tableau(dimension_type external_space_dim, /* parametric-only constraints have already been inserted in initial context, so no need to insert them in the tableau */ + dimension_type var_id = mapping.size(); + dimension_type row_id = tableau.s.num_rows(); tableau.s.add_row(var); tableau.t.add_row(param); sign.push_back(row_sign(param)); + basis.push_back(false); + mapping.push_back(row_id); + var_row.push_back(var_id); if (cst->is_equality()) { + ++var_id; + ++row_id; negate_assign(var, var, 0); negate_assign(param, param, 0); tableau.s.add_row(var); tableau.t.add_row(param); sign.push_back(row_sign(param)); + basis.push_back(false); + mapping.push_back(row_id); + var_row.push_back(var_id); } } } @@ -1123,27 +1157,15 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref, const Matrix& ctx, /* ** Perform pivot operation ** */ - /* Check if column j_ or row i_ correspond to a problem variable */ - dimension_type var_j = n_a_d; - dimension_type var_i = n_a_d; - for (j=0; j<num_vars; ++j) { - if (basis[j]) { - if (mapping[j] == j_) - var_j = j; - } else { - if (mapping[j] == i_) - var_i = j; - } - } /* update basis */ - if (var_j != n_a_d) { - basis[var_j] = false; - mapping[var_j] = i_; - } - if (var_i != n_a_d) { - basis[var_i] = true; - mapping[var_i] = j_; - } + dimension_type var_j = var_column[j_]; + dimension_type var_i = var_row[i_]; + basis[var_j] = false; + mapping[var_j] = i_; + var_row[i_] = var_j; + basis[var_i] = true; + mapping[var_i] = j_; + var_column[j_] = var_i; /* create the identity matrix row corresponding to basic variable j_ */ Row prs(num_vars, tableau.s_capacity(), Row::Flags()); @@ -1548,6 +1570,9 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref, const Matrix& ctx, << std::endl; } #endif + var_row.push_back(num_rows+num_vars); + basis.push_back(false); + mapping.push_back(num_rows); sign.push_back(NEGATIVE); } } diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index c9d3d1d..e9746df 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -296,6 +296,17 @@ private: /*! \brief A boolean vector for identifying the basic variables. + Variable identifiers are numbered from 0 to <tt>n+m-1</tt>, where \p n + is the number of columns in the simplex tableau corresponding to variables, + and \p m is the number of rows. + + Indices from 0 to <tt>n-1</tt> correspond to the original variables. + + Indices from \p n to <tt>n+m-1</tt> correspond to the slack variables + associated to the internal constraints, which do not strictly correspond + to original constraints, since these may have been transformed to fit the + standard form of the dual simplex. + The value for <tt>basis[i]</tt> is: - \b true if variable \p i is basic, - \b false if variable \p i is nonbasic. @@ -314,6 +325,14 @@ private: */ std::vector<dimension_type> mapping; + /*! A vector of the variable identifiers associated to each row of the + simplex tableau. */ + std::vector<dimension_type> var_row; + + /*! A vector of the variable identifiers associated to each column of the + simplex tableau. */ + std::vector<dimension_type> var_column; + //! The possible values for the sign of a parametric linear expression. enum Row_Sign { //! Not computed yet (default)

1 0

[GIT] ppl/ppl(pip): Implemented an example of solution tree spanning and display using
by François Galea 03 Nov '09

03 Nov '09

Module: ppl/ppl Branch: pip Commit: f09897ddab17ad111ac6a79d4334cee8256f73fa URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f09897ddab17… Author: François Galea <francois.galea(a)uvsq.fr> Date: Tue Nov 3 09:54:58 2009 +0100 Implemented an example of solution tree spanning and display using the C interface. --- interfaces/C/tests/pip_test.c | 121 ++++++++++++++++++++++++++++++++++++++++- 1 files changed, 120 insertions(+), 1 deletions(-) diff --git a/interfaces/C/tests/pip_test.c b/interfaces/C/tests/pip_test.c index ab56dbf..60471a1 100644 --- a/interfaces/C/tests/pip_test.c +++ b/interfaces/C/tests/pip_test.c @@ -25,6 +25,7 @@ site: http://www.cs.unipr.it/ppl/ . */ #include <stdio.h> #include <stdlib.h> #include <stdarg.h> +#include <string.h> static const char* program_name = 0; @@ -45,6 +46,124 @@ fatal(const char* format, ...) { my_exit(1); } +static void +display_solution_i(ppl_const_PIP_Tree_Node_t node, + ppl_dimension_type n_vars, + ppl_dimension_type n_params, + const ppl_dimension_type vars[], + const ppl_dimension_type params[], + int indent) { + if (!node) { + printf("%*s_|_\n", indent*2, ""); + } else { + ppl_dimension_type space_dimension = n_vars + n_params; + ppl_dimension_type new_params; + ppl_dimension_type* parameters; + ppl_const_Constraint_System_t constraints; + ppl_const_PIP_Decision_Node_t dn; + int constraints_empty; + ppl_PIP_Tree_Node_number_of_artificials(node, &new_params); + parameters = malloc((n_params+new_params)*sizeof(ppl_dimension_type)); + memcpy(parameters, params, n_params*sizeof(ppl_dimension_type)); + if (new_params > 0) { + ppl_Artificial_Parameter_Sequence_const_iterator_t i, i_end; + ppl_PIP_Tree_Node_insert_artificials(node, parameters, n_params, + space_dimension); + ppl_new_Artificial_Parameter_Sequence_const_iterator(&i); + ppl_new_Artificial_Parameter_Sequence_const_iterator(&i_end); + ppl_PIP_Tree_Node_begin(node, i); + ppl_PIP_Tree_Node_end(node, i_end); + while (!ppl_Artificial_Parameter_Sequence_const_iterator_equal_test + (i,i_end)) { + ppl_const_Artificial_Parameter_t ap; + ppl_Artificial_Parameter_Sequence_const_iterator_dereference(i, &ap); + printf("%*sParameter ", indent*2, ""); + ppl_io_print_variable(space_dimension++); + printf(" = "); + ppl_io_print_Artificial_Parameter(ap); + printf("\n"); + ppl_Artificial_Parameter_Sequence_const_iterator_increment(i); + } + ppl_delete_Artificial_Parameter_Sequence_const_iterator(i_end); + ppl_delete_Artificial_Parameter_Sequence_const_iterator(i); + } + + ppl_PIP_Tree_Node_get_constraints(node, &constraints); + constraints_empty = ppl_Constraint_System_empty(constraints); + if (!constraints_empty) { + int notfirst = 0; + ppl_Constraint_System_const_iterator_t end, i; + ppl_new_Constraint_System_const_iterator(&i); + ppl_new_Constraint_System_const_iterator(&end); + ppl_Constraint_System_begin(constraints, i); + ppl_Constraint_System_end(constraints, end); + printf("%*sif ", indent*2, ""); + for (; !ppl_Constraint_System_const_iterator_equal_test(i,end); + ppl_Constraint_System_const_iterator_increment(i)) { + ppl_const_Constraint_t c; + if (notfirst) + printf(" and "); + ppl_Constraint_System_const_iterator_dereference(i, &c); + ppl_io_print_Constraint(c); + notfirst = 1; + } + printf(" then\n"); + } + ppl_PIP_Tree_Node_as_decision(node, &dn); + n_params += new_params; + if (dn) { + ppl_const_PIP_Tree_Node_t child; + ppl_PIP_Decision_Node_get_child_node(dn, 1, &child); + display_solution_i(child, n_vars, n_params, vars, parameters, indent+1); + printf("%*selse\n", indent*2, ""); + ppl_PIP_Decision_Node_get_child_node(dn, 0, &child); + display_solution_i(child, n_vars, n_params, vars, parameters, indent+1); + } else { + int notfirst = 0; + ppl_const_PIP_Solution_Node_t sn; + ppl_dimension_type i; + ppl_const_Linear_Expression_t le; + ppl_PIP_Tree_Node_as_solution(node, &sn); + printf("%*s{", indent*2+(constraints_empty?0:2), ""); + for (i=0; i<n_vars; ++i) { + if (notfirst) + printf(" ; "); + ppl_PIP_Solution_Node_get_parametric_values(sn, vars[i], parameters, + n_params, &le); + ppl_io_print_Linear_Expression(le); + notfirst = 1; + } + printf("}\n"); + if (!constraints_empty) + printf("%*selse\n%*s_|_\n", indent*2, "", indent*2+2, ""); + } + free(parameters); + } +} + +void +display_solution(ppl_const_PIP_Tree_Node_t node, + ppl_dimension_type n_vars, + ppl_dimension_type n_params, + const ppl_dimension_type params[]) { + ppl_dimension_type* vars; + ppl_dimension_type i, j, k, dim; + vars = malloc(n_vars*sizeof(ppl_dimension_type)); + dim = n_vars+n_params; + + /* construct the array of variable space indices. This requires the params + array to be sorted in ascending order. + */ + for (i=0, j=0, k=0; i<dim; ++i) { + if (k == n_params || i < params[k]) + vars[j++] = i; + else + ++k; + } + display_solution_i(node, n_vars, n_params, vars, params, 0); + free(vars); +} + #define N_VARS 2 #define N_PARAMETERS 2 #define N_CONSTRAINTS 4 @@ -105,7 +224,7 @@ main(int argc, char **argv) { ppl_const_PIP_Tree_Node_t solution; ppl_PIP_Problem_space_dimension(pip, &dim); ppl_PIP_Problem_solution(pip, &solution); - /* display_solution(solution, N_VARS, N_PARAMETERS, parameter_dim); */ + display_solution(solution, N_VARS, N_PARAMETERS, parameter_dim); } ppl_delete_PIP_Problem(pip);

1 0