October 2009 - PPL-devel - BUGSENG Mailman

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

23 Oct '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

1 0

[GIT] ppl/ppl(master): Refer to PPL 0.11, not 0.10.
by Roberto Bagnara 22 Oct '09

22 Oct '09

Module: ppl/ppl Branch: master Commit: f6f503bc22cddf805e959ed26f53f5825ffd763e URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f6f503bc22cd… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Thu Oct 22 22:19:52 2009 +0200 Refer to PPL 0.11, not 0.10. --- README | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/README b/README index b9ed107..67dde44 100644 --- a/README +++ b/README @@ -63,7 +63,7 @@ See http://www.cs.unipr.it/ppl/ for more information on the PPL. For any additional questions you might have, please do not hesitate to write to ppl-devel(a)cs.unipr.it. -Here is the contents of the PPL 0.10 source distribution +Here is the contents of the PPL 0.11 source distribution (41 directories, 1446 files): ppl-0.11

1 0

[GIT] ppl/ppl(pip): Version number bumped.
by Roberto Bagnara 22 Oct '09

22 Oct '09

Module: ppl/ppl Branch: pip Commit: 3abd93298e88587401f5394bac6d39628e291bd7 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3abd93298e88… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Thu Oct 22 22:18:26 2009 +0200 Version number bumped. --- configure.ac | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/configure.ac b/configure.ac index 0998629..7da6e56 100644 --- a/configure.ac +++ b/configure.ac @@ -23,7 +23,7 @@ # Process this file with Autoconf to produce a configure script. # Every other copy of the package version number gets its value from here. -AC_INIT([the Parma Polyhedra Library], [0.11pre6], [ppl-devel(a)cs.unipr.it], [ppl]) +AC_INIT([the Parma Polyhedra Library], [0.11pre7], [ppl-devel(a)cs.unipr.it], [ppl]) # Minimum Autoconf version required. AC_PREREQ(2.61)

1 0

[GIT] ppl/ppl(pip): Ditribute also MIP_Problem.types.hh, PIP_Tree.types. hh and PIP_Problem.types.hh.
by Roberto Bagnara 22 Oct '09

22 Oct '09

Module: ppl/ppl Branch: pip Commit: 4e5c81beb8e9e05d2dac40a9fe05c90f756b524c URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4e5c81beb8e9… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Thu Oct 22 22:07:38 2009 +0200 Ditribute also MIP_Problem.types.hh, PIP_Tree.types.hh and PIP_Problem.types.hh. --- src/Makefile.am | 3 +++ 1 files changed, 3 insertions(+), 0 deletions(-) diff --git a/src/Makefile.am b/src/Makefile.am index 2160973..55b750e 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -269,11 +269,14 @@ Grid_Generator_System.inlines.hh \ Congruence_System.inlines.hh \ Scalar_Products.defs.hh \ Scalar_Products.inlines.hh \ +MIP_Problem.types.hh \ MIP_Problem.defs.hh \ MIP_Problem.inlines.hh \ MIP_Problem.templates.hh \ +PIP_Tree.types.hh \ PIP_Tree.defs.hh \ PIP_Tree.inlines.hh \ +PIP_Problem.types.hh \ PIP_Problem.defs.hh \ PIP_Problem.inlines.hh \ PIP_Problem.templates.hh \

1 0

[GIT] ppl/ppl(pip): Adapted to the checking of ppl_pips.
by Roberto Bagnara 22 Oct '09

22 Oct '09

Module: ppl/ppl Branch: pip Commit: 068eaef2c633461d481e2b5593d02f4b1591c3d7 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=068eaef2c633… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Thu Oct 22 18:16:20 2009 +0200 Adapted to the checking of ppl_pips. --- demos/ppl_pips/Makefile.am | 46 +++++++++++-------------------------------- 1 files changed, 12 insertions(+), 34 deletions(-) diff --git a/demos/ppl_pips/Makefile.am b/demos/ppl_pips/Makefile.am index ba0e34c..75037a0 100644 --- a/demos/ppl_pips/Makefile.am +++ b/demos/ppl_pips/Makefile.am @@ -45,16 +45,16 @@ piplib_lcdd: piplib_lcdd.o $(CXXLINK) $< -lpip -lgmpxx -lgmp $(top_builddir)/utils/libppl_utils.a EXTRA_DIST = \ -expected_mpz \ -expected_mpz_a \ -expected_int8 \ -expected_int8_a \ -expected_int16 \ -expected_int16_a \ -expected_int32 \ -expected_int32_a \ -expected_int64 \ -expected_int64_a +expected_mpz +# expected_mpz_a \ +# expected_int8 \ +# expected_int8_a \ +# expected_int16 \ +# expected_int16_a \ +# expected_int32 \ +# expected_int32_a \ +# expected_int64 \ +# expected_int64_a if HAVE_MD5SUM @@ -62,19 +62,7 @@ COEFFICIENT_MNEMONIC = @coefficient_mnemonic@ if ASSERTIONS_ENABLED -TOUGH_EXAMPLES_IF_ASSERTIONS_ENABLED = \ -ccc6.ext \ -ccp6.ext \ -cut32_16.ext \ -cyclic16-10.ext \ -reg600-5_m.ext \ -cyclic17_8.ine \ -in6.ine \ -in7.ine \ -kq20_11_m.ine \ -mit31-20.ine \ -sampleh8.ine \ -trunc10.ine +TOUGH_EXAMPLES_IF_ASSERTIONS_ENABLED = EXPECTED = expected_$(COEFFICIENT_MNEMONIC)_a @@ -85,23 +73,13 @@ EXPECTED = expected_$(COEFFICIENT_MNEMONIC) endif !ASSERTIONS_ENABLED TOUGH_EXAMPLES = \ -cp7.ext \ -cyclic25_13.ext \ -prodst62.ext \ -cp6.ine \ -mit.ine \ -mit288-281.ine \ -mit41-16.ine \ -mit708-9.ine \ -mit71-61.ine \ -mit90-86.ine \ $(TOUGH_EXAMPLES_IF_ASSERTIONS_ENABLED) check-local: ppl_pips$(EXEEXT) echo $(TOUGH_EXAMPLES) >tough_examples echo $(ECHO_N) "$(ECHO_C)" >obtained export LC_ALL=C; \ - for path in $(srcdir)/examples/*.ext $(srcdir)/examples/*.ine; \ + for path in $(srcdir)/examples/*.dat; \ do \ file=`basename $$path`; \ $(FGREP) $$file tough_examples >/dev/null 2>&1 && continue; \

1 0

[GIT] ppl/ppl(pip): Put under Git control.
by Roberto Bagnara 22 Oct '09

22 Oct '09

Module: ppl/ppl Branch: pip Commit: 7771850394ed5b1289f08c9cef5b1a872e7f7e6e URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=7771850394ed… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Thu Oct 22 18:16:03 2009 +0200 Put under Git control. --- demos/ppl_pips/expected_mpz | 1 + 1 files changed, 1 insertions(+), 0 deletions(-) diff --git a/demos/ppl_pips/expected_mpz b/demos/ppl_pips/expected_mpz new file mode 100644 index 0000000..e30f88a --- /dev/null +++ b/demos/ppl_pips/expected_mpz @@ -0,0 +1 @@ +test02.dat cd5fa1529845aacfac7b36ecad8d1c93 -

1 0

[GIT] ppl/ppl(pip): Removed invalid optimization in context compatibility check.
by François Galea 22 Oct '09

22 Oct '09

Module: ppl/ppl Branch: pip Commit: b96565a81906e2b6d4e57613cdd0ed32ff4b715e URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b96565a81906… Author: François Galea <francois.galea(a)uvsq.fr> Date: Thu Oct 22 11:32:19 2009 +0200 Removed invalid optimization in context compatibility check. --- src/PIP_Tree.cc | 2 -- 1 files changed, 0 insertions(+), 2 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 6f04139..1047be0 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -686,8 +686,6 @@ PIP_Solution_Node::row_sign(const Row &x) { bool PIP_Solution_Node::compatibility_check(const Matrix &ctx, const Row &cnst) { - if (ctx.num_rows() == 0) - return true; Matrix s(ctx); s.add_row(cnst); dimension_type i, i_, j, k, j_, j__, var_i, var_j;

1 0

[GIT] ppl/ppl(pip): Added a standalone PIP solver demo program.
by François Galea 22 Oct '09

22 Oct '09

Module: ppl/ppl Branch: pip Commit: 7c4cc0826009158541d76a0c9bc95df1ef693141 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=7c4cc0826009… Author: François Galea <francois.galea(a)uvsq.fr> Date: Wed Oct 21 19:42:21 2009 +0200 Added a standalone PIP solver demo program. --- configure.ac | 20 ++ demos/Makefile.am | 6 +- demos/ppl_pips/Makefile.am | 125 +++++++ demos/ppl_pips/examples/Makefile.am | 26 ++ demos/ppl_pips/examples/test02.dat | 20 ++ demos/ppl_pips/ppl_pips.cc | 642 +++++++++++++++++++++++++++++++++++ 6 files changed, 838 insertions(+), 1 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=7c4cc082…

1 0

[GIT] ppl/ppl(pip): Context compatibility check now searches for valid integer solutions.
by François Galea 21 Oct '09

21 Oct '09

Module: ppl/ppl Branch: pip Commit: 9d6df94a8a65aa86474a9e2f26322e3954c36e7d URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=9d6df94a8a65… Author: François Galea <francois.galea(a)uvsq.fr> Date: Wed Oct 21 12:39:17 2009 +0200 Context compatibility check now searches for valid integer solutions. --- src/PIP_Tree.cc | 32 +++++++++++++++++++++++++++++--- src/PIP_Tree.defs.hh | 3 +++ tests/PIP_Problem/pipproblem1.cc | 2 +- 3 files changed, 33 insertions(+), 4 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 355f8f1..6f04139 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -686,6 +686,8 @@ PIP_Solution_Node::row_sign(const Row &x) { bool PIP_Solution_Node::compatibility_check(const Matrix &ctx, const Row &cnst) { + if (ctx.num_rows() == 0) + return true; Matrix s(ctx); s.add_row(cnst); dimension_type i, i_, j, k, j_, j__, var_i, var_j; @@ -732,8 +734,32 @@ PIP_Solution_Node::compatibility_check(const Matrix &ctx, const Row &cnst) { } if (j == 0) { - // No negative RHS: optimum found - return true; + // No negative RHS: fractional optimum found. If it is integer, then + // the test is successful. Otherwise, generate a new cut. + for (i=0; i<num_vars; ++i) { + if (basis[i]) + // basic variable = 0 -> integer + continue; + // nonbasic variable + i_ = mapping[i]; + if (s[i_][0] % scaling[i_] != 0) + // constant term is not integer + break; + } + if (i==num_vars) { + // Found an integer solution, thus the check is successful + return true; + } + // Generate a new cut + s.add_zero_rows(1, Row::Flags()); + const Row& row = s[i_]; + Row& cut = s[num_rows++]; + scaling.push_back(1); + const Coefficient& sc = scaling[i_]; + for (j=0; j<num_cols; ++j) + mod_assign(cut[j], row[j], sc); + cut[0] -= sc; + continue; } // Now we have a positive s[i][j] pivot @@ -1340,7 +1366,7 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref, const Matrix& ctx, } /* Otherwise, all parameters are positive: we have found a continuous - * solution. If the solution happens to be integer, then it is a + * solution. If the solution happens to be integer, then it is the * solution of the integer problem. Otherwise, we may need to generate * a new cut to try and get back into the integer case. */ else { diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index c2a8186..8c3704f 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -335,6 +335,9 @@ private: Matrix consisting in the original matrix with the constraint inserted. If the simplex terminates with a feasible (optimal) solution, then the restrained context is not empty. Otherwise, it is. + + The algorithm ensures the feasible solutions are integer, by applying a + cut generation method when intermediate non-integer solutions are found. */ static bool compatibility_check(const Matrix &ctx, const Row &cnst); diff --git a/tests/PIP_Problem/pipproblem1.cc b/tests/PIP_Problem/pipproblem1.cc index 65b58aa..f250ccb 100644 --- a/tests/PIP_Problem/pipproblem1.cc +++ b/tests/PIP_Problem/pipproblem1.cc @@ -241,7 +241,7 @@ test06() { PIP_Problem pip(cs.space_dimension(), cs.begin(), cs.end(), params); - bool ok = (pip.solve() == OPTIMIZED_PIP_PROBLEM); + bool ok = (pip.solve() == UNFEASIBLE_PIP_PROBLEM); if (ok) { const PIP_Tree solution = pip.solution(); display_solution(solution, params, Variables_Set(i),

1 0

[GIT] ppl/ppl(pi): Context compatibility check now searches for valid integer solutions.
by François Galea 21 Oct '09

21 Oct '09

Module: ppl/ppl Branch: pi Commit: 9d6df94a8a65aa86474a9e2f26322e3954c36e7d URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=9d6df94a8a65… Author: François Galea <francois.galea(a)uvsq.fr> Date: Wed Oct 21 12:39:17 2009 +0200 Context compatibility check now searches for valid integer solutions. --- src/PIP_Tree.cc | 32 +++++++++++++++++++++++++++++--- src/PIP_Tree.defs.hh | 3 +++ tests/PIP_Problem/pipproblem1.cc | 2 +- 3 files changed, 33 insertions(+), 4 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 355f8f1..6f04139 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -686,6 +686,8 @@ PIP_Solution_Node::row_sign(const Row &x) { bool PIP_Solution_Node::compatibility_check(const Matrix &ctx, const Row &cnst) { + if (ctx.num_rows() == 0) + return true; Matrix s(ctx); s.add_row(cnst); dimension_type i, i_, j, k, j_, j__, var_i, var_j; @@ -732,8 +734,32 @@ PIP_Solution_Node::compatibility_check(const Matrix &ctx, const Row &cnst) { } if (j == 0) { - // No negative RHS: optimum found - return true; + // No negative RHS: fractional optimum found. If it is integer, then + // the test is successful. Otherwise, generate a new cut. + for (i=0; i<num_vars; ++i) { + if (basis[i]) + // basic variable = 0 -> integer + continue; + // nonbasic variable + i_ = mapping[i]; + if (s[i_][0] % scaling[i_] != 0) + // constant term is not integer + break; + } + if (i==num_vars) { + // Found an integer solution, thus the check is successful + return true; + } + // Generate a new cut + s.add_zero_rows(1, Row::Flags()); + const Row& row = s[i_]; + Row& cut = s[num_rows++]; + scaling.push_back(1); + const Coefficient& sc = scaling[i_]; + for (j=0; j<num_cols; ++j) + mod_assign(cut[j], row[j], sc); + cut[0] -= sc; + continue; } // Now we have a positive s[i][j] pivot @@ -1340,7 +1366,7 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref, const Matrix& ctx, } /* Otherwise, all parameters are positive: we have found a continuous - * solution. If the solution happens to be integer, then it is a + * solution. If the solution happens to be integer, then it is the * solution of the integer problem. Otherwise, we may need to generate * a new cut to try and get back into the integer case. */ else { diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index c2a8186..8c3704f 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -335,6 +335,9 @@ private: Matrix consisting in the original matrix with the constraint inserted. If the simplex terminates with a feasible (optimal) solution, then the restrained context is not empty. Otherwise, it is. + + The algorithm ensures the feasible solutions are integer, by applying a + cut generation method when intermediate non-integer solutions are found. */ static bool compatibility_check(const Matrix &ctx, const Row &cnst); diff --git a/tests/PIP_Problem/pipproblem1.cc b/tests/PIP_Problem/pipproblem1.cc index 65b58aa..f250ccb 100644 --- a/tests/PIP_Problem/pipproblem1.cc +++ b/tests/PIP_Problem/pipproblem1.cc @@ -241,7 +241,7 @@ test06() { PIP_Problem pip(cs.space_dimension(), cs.begin(), cs.end(), params); - bool ok = (pip.solve() == OPTIMIZED_PIP_PROBLEM); + bool ok = (pip.solve() == UNFEASIBLE_PIP_PROBLEM); if (ok) { const PIP_Tree solution = pip.solution(); display_solution(solution, params, Variables_Set(i),

1 0