July 2009 - PPL-devel - BUGSENG Mailman

New deterministic timeout facilities of the PPL and PWL
by Roberto Bagnara 14 Jul '09

14 Jul '09

Sebastian Pop wrote: > On Thu, Jul 9, 2009 at 07:12, Michael > Classen<michael.classen(a)uni-passau.de> wrote: >> Maybe it could also be possible to use the Parma Watchdog Library >> (PWL) for providing a timeout for the precise method and falling back >> to the more conservative method once a certain timeout is reached? > > Not in GCC. > This would make the compiler non deterministic. We have uploaded a preview of PPL 0.11 at ftp://ftp.cs.unipr.it/pub/ppl/snapshots/ The new deterministic timeout facilities of the PPL and PWL (you need both) can be exploited (using the C language interface) by using the following functions: int ppl_set_deterministic_timeout(unsigned weight); int ppl_reset_deterministic_timeout(void); The first function sets a maximum computational "weight". After setting this weight threshold, some of the PPL library functions (namely, those that may take an exponential amount of time) will do the following: a) charge the overall computation with their computational weight; b) check, from time to time, whether the threshold has been reached. In such a case, the computation will stop before completion (causing no resource leaks) and the library function will return error code PPL_TIMEOUT_EXCEPTION. Independently from whether or not such an error code is obtained, the client code will need to dispose the threshold previously set by calling the second function above. Since the charged computation weights do not depend on actual elapsed time, the timeout triggering is independent from the given computational environment (CPU type, CPU speed, operating system, ...). As an example, the following code is taken from test file interfaces/C/tests/weightwatch1.c: for (i = 0; i <= max_dimension; ++i) { ppl_new_NNC_Polyhedron_from_space_dimension(&ph, i, 0); open_hypercube(i, ph); ppl_set_deterministic_timeout(weight); /* Setting threshold */ result = ppl_Polyhedron_get_generators(ph, &gs); ppl_reset_deterministic_timeout(); /* Resetting threshold */ ppl_delete_Polyhedron(ph); /* Check if the computation was stopped before completion. */ if (result == PPL_TIMEOUT_EXCEPTION) /* Deterministic timeout expired */ return; else if (result != 0) /* Unexpected error */ exit(1); } As said in the documentation: \warning The weight mechanism is under alpha testing. In particular, there is still no clear relation between the weight threshold and the actual computational complexity. As a consequence, client applications should be ready to reconsider the tuning of these weight thresholds when upgrading to newer version of the PPL. At the moment we cannot provide meaningful hints regarding the appropriate values to be given to these weight thresholds: they mainly depend on the particular application and on the particular problem instances considered. Some experimentation and tuning are unavoidable. Please test and let us know how it goes. If you think you want this in time for GCC 4.5.0, please advise so that our release schedule matches the one of GCC. Cheers, Roberto -- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:bagnara@cs.unipr.it

2 2

[GIT] ppl/ppl(master): Debugging prints improved.
by Roberto Bagnara 14 Jul '09

14 Jul '09

Module: ppl/ppl Branch: master Commit: 092abc98a2acfe93ecac11779f39199668b84bb9 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=092abc98a2ac… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Tue Jul 14 19:33:20 2009 +0200 Debugging prints improved. --- src/MIP_Problem.cc | 15 ++++++++++----- 1 files changed, 10 insertions(+), 5 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index bf5df34..202a5c8 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -1615,7 +1615,8 @@ PPL::MIP_Problem::solve_mip(bool& have_incumbent_solution, PPL_DIRTY_TEMP_COEFFICIENT(num); PPL_DIRTY_TEMP_COEFFICIENT(den); lp.evaluate_objective_function(p, num, den); - std::cout << "new value found: " << num << "/" << den + std::cout << "MIP_Problem::solve_mip(): " + << "new value found: " << num << "/" << den << "." << std::endl; #endif } @@ -1635,7 +1636,8 @@ PPL::MIP_Problem::solve_mip(bool& have_incumbent_solution, lp_aux.add_constraint(Variable(nonint_dim) <= tmp_coeff1); #if PPL_NOISY_SIMPLEX using namespace IO_Operators; - std::cout << "descending with: " + std::cout << "MIP_Problem::solve_mip(): " + << "descending with: " << (Variable(nonint_dim) <= tmp_coeff1) << "." << std::endl; #endif @@ -1646,7 +1648,8 @@ PPL::MIP_Problem::solve_mip(bool& have_incumbent_solution, lp.add_constraint(Variable(nonint_dim) >= tmp_coeff2); #if PPL_NOISY_SIMPLEX using namespace IO_Operators; - std::cout << "descending with: " + std::cout << "MIP_Problem::solve_mip(): " + << "descending with: " << (Variable(nonint_dim) >= tmp_coeff2) << "." << std::endl; #endif @@ -1790,8 +1793,10 @@ PPL::MIP_Problem::is_mip_satisfiable(MIP_Problem& lp, lp.add_constraint(Variable(nonint_dim) >= tmp_coeff2); #if PPL_NOISY_SIMPLEX using namespace IO_Operators; - std::cout << "descending with: " - << (Variable(nonint_dim) >= tmp_coeff2) << std::endl; + std::cout << "MIP_Problem::is_mip_satisfiable(): " + << "descending with: " + << (Variable(nonint_dim) >= tmp_coeff2) + << "." << std::endl; #endif bool satisfiable = is_mip_satisfiable(lp, i_vars, p); #if PPL_NOISY_SIMPLEX

1 0

[GIT] ppl/ppl(master): Weights adjusted. Added more debugging prints.
by Roberto Bagnara 14 Jul '09

14 Jul '09

Module: ppl/ppl Branch: master Commit: 55dda35b30c6153e8b47f2001ba4990e36df0343 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=55dda35b30c6… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Tue Jul 14 19:29:20 2009 +0200 Weights adjusted. Added more debugging prints. --- src/MIP_Problem.cc | 54 +++++++++++++++++++++++++-------------------------- 1 files changed, 26 insertions(+), 28 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 594a111..bf5df34 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -835,8 +835,8 @@ PPL::MIP_Problem::process_pending_constraints() { #if PPL_NOISY_SIMPLEX std::cout << "MIP_Problem::process_pending_constraints(): " - << "1st phase ended at iteration " - << num_iterations << "." << std::endl; + << "1st phase ended at iteration " << num_iterations + << "." << std::endl; #endif if (!first_phase_succesful || working_cost[0] != 0) { @@ -1188,8 +1188,8 @@ PPL::MIP_Problem::compute_simplex_using_steepest_edge_float() { #if PPL_NOISY_SIMPLEX ++num_iterations; if (num_iterations % 200 == 0) - std::cout << "Primal Simplex: iteration " - << num_iterations << "." << std::endl; + std::cout << "Primal simplex: iteration " << num_iterations + << "." << std::endl; #endif // If the following condition fails, probably there's a bug. PPL_ASSERT(challenger >= current); @@ -1255,8 +1255,8 @@ PPL::MIP_Problem::compute_simplex_using_exact_pricing() { #if PPL_NOISY_SIMPLEX ++num_iterations; if (num_iterations % 200 == 0) - std::cout << "Primal Simplex: iteration " - << num_iterations << "." << std::endl; + std::cout << "Primal simplex: iteration " << num_iterations + << "." << std::endl; #endif } } @@ -1460,7 +1460,8 @@ PPL::MIP_Problem::second_phase() { compute_generator(); #if PPL_NOISY_SIMPLEX std::cout << "MIP_Problem::second_phase(): 2nd phase ended at iteration " - << num_iterations << "." << std::endl; + << num_iterations + << "." << std::endl; #endif status = second_phase_successful ? OPTIMIZED : UNBOUNDED; PPL_ASSERT(OK()); @@ -1614,7 +1615,8 @@ PPL::MIP_Problem::solve_mip(bool& have_incumbent_solution, PPL_DIRTY_TEMP_COEFFICIENT(num); PPL_DIRTY_TEMP_COEFFICIENT(den); lp.evaluate_objective_function(p, num, den); - std::cout << "new value found: " << num << "/" << den << std::endl; + std::cout << "new value found: " << num << "/" << den + << "." << std::endl; #endif } return lp_status; @@ -1634,7 +1636,8 @@ PPL::MIP_Problem::solve_mip(bool& have_incumbent_solution, #if PPL_NOISY_SIMPLEX using namespace IO_Operators; std::cout << "descending with: " - << (Variable(nonint_dim) <= tmp_coeff1) << std::endl; + << (Variable(nonint_dim) <= tmp_coeff1) + << "." << std::endl; #endif solve_mip(have_incumbent_solution, incumbent_solution_value, incumbent_solution_point, lp_aux, i_vars); @@ -1644,7 +1647,8 @@ PPL::MIP_Problem::solve_mip(bool& have_incumbent_solution, #if PPL_NOISY_SIMPLEX using namespace IO_Operators; std::cout << "descending with: " - << (Variable(nonint_dim) >= tmp_coeff2) << std::endl; + << (Variable(nonint_dim) >= tmp_coeff2) + << "." << std::endl; #endif solve_mip(have_incumbent_solution, incumbent_solution_value, incumbent_solution_point, lp, i_vars); @@ -1766,7 +1770,13 @@ PPL::MIP_Problem::is_mip_satisfiable(MIP_Problem& lp, { MIP_Problem lp_aux = lp; lp_aux.add_constraint(Variable(nonint_dim) <= tmp_coeff1); -<<<<<<< HEAD:src/MIP_Problem.cc +#if PPL_NOISY_SIMPLEX + using namespace IO_Operators; + std::cout << "MIP_Problem::is_mip_satisfiable(): " + << "descending with: " + << (Variable(nonint_dim) <= tmp_coeff1) + << "." << std::endl; +#endif if (is_mip_satisfiable(lp_aux, i_vars, p)) { #if PPL_NOISY_SIMPLEX std::cout << "MIP_Problem::is_mip_satisfiable(): " @@ -1774,19 +1784,15 @@ PPL::MIP_Problem::is_mip_satisfiable(MIP_Problem& lp, << "." << std::endl; --mip_recursion_level; #endif -======= -#if PPL_NOISY_SIMPLEX - using namespace IO_Operators; - std::cout << "descending with: " - << (Variable(nonint_dim) <= tmp_coeff1) << std::endl; -#endif - if (is_mip_satisfiable(lp_aux, i_vars, p)) ->>>>>>> More weights adjusted. Added a couple of debugging prints.:src/MIP_Problem.cc return true; } } lp.add_constraint(Variable(nonint_dim) >= tmp_coeff2); -<<<<<<< HEAD:src/MIP_Problem.cc +#if PPL_NOISY_SIMPLEX + using namespace IO_Operators; + std::cout << "descending with: " + << (Variable(nonint_dim) >= tmp_coeff2) << std::endl; +#endif bool satisfiable = is_mip_satisfiable(lp, i_vars, p); #if PPL_NOISY_SIMPLEX std::cout << "MIP_Problem::is_mip_satisfiable(): " @@ -1795,14 +1801,6 @@ PPL::MIP_Problem::is_mip_satisfiable(MIP_Problem& lp, --mip_recursion_level; #endif return satisfiable; -======= -#if PPL_NOISY_SIMPLEX - using namespace IO_Operators; - std::cout << "descending with: " - << (Variable(nonint_dim) >= tmp_coeff2) << std::endl; -#endif - return is_mip_satisfiable(lp, i_vars, p); ->>>>>>> More weights adjusted. Added a couple of debugging prints.:src/MIP_Problem.cc } bool

1 0

[GIT] ppl/ppl(master): More weights adjusted. Added a couple of debugging prints.
by Roberto Bagnara 14 Jul '09

14 Jul '09

Module: ppl/ppl Branch: master Commit: 12ab9f366276985efb931bc52a75cd8770f1add7 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=12ab9f366276… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Tue Jul 14 19:14:50 2009 +0200 More weights adjusted. Added a couple of debugging prints. --- src/MIP_Problem.cc | 22 ++++++++++++++++++++-- 1 files changed, 20 insertions(+), 2 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 61f489c..594a111 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -918,7 +918,7 @@ PPL::MIP_Problem::steepest_edge_float_entering_index() const { current_value = challenger_value; entering_index = j; } - WEIGHT_ADD_MUL(1, tableau_num_rows); + WEIGHT_ADD_MUL(338, tableau_num_rows); } } return entering_index; @@ -1212,7 +1212,7 @@ PPL::MIP_Problem::compute_simplex_using_steepest_edge_float() { if (cost_sgn_coeff < 0) neg_assign(current_num); abs_assign(current_den, cost_sgn_coeff); - WEIGHT_ADD(1); + WEIGHT_ADD(566); } } @@ -1766,6 +1766,7 @@ PPL::MIP_Problem::is_mip_satisfiable(MIP_Problem& lp, { MIP_Problem lp_aux = lp; lp_aux.add_constraint(Variable(nonint_dim) <= tmp_coeff1); +<<<<<<< HEAD:src/MIP_Problem.cc if (is_mip_satisfiable(lp_aux, i_vars, p)) { #if PPL_NOISY_SIMPLEX std::cout << "MIP_Problem::is_mip_satisfiable(): " @@ -1773,10 +1774,19 @@ PPL::MIP_Problem::is_mip_satisfiable(MIP_Problem& lp, << "." << std::endl; --mip_recursion_level; #endif +======= +#if PPL_NOISY_SIMPLEX + using namespace IO_Operators; + std::cout << "descending with: " + << (Variable(nonint_dim) <= tmp_coeff1) << std::endl; +#endif + if (is_mip_satisfiable(lp_aux, i_vars, p)) +>>>>>>> More weights adjusted. Added a couple of debugging prints.:src/MIP_Problem.cc return true; } } lp.add_constraint(Variable(nonint_dim) >= tmp_coeff2); +<<<<<<< HEAD:src/MIP_Problem.cc bool satisfiable = is_mip_satisfiable(lp, i_vars, p); #if PPL_NOISY_SIMPLEX std::cout << "MIP_Problem::is_mip_satisfiable(): " @@ -1785,6 +1795,14 @@ PPL::MIP_Problem::is_mip_satisfiable(MIP_Problem& lp, --mip_recursion_level; #endif return satisfiable; +======= +#if PPL_NOISY_SIMPLEX + using namespace IO_Operators; + std::cout << "descending with: " + << (Variable(nonint_dim) >= tmp_coeff2) << std::endl; +#endif + return is_mip_satisfiable(lp, i_vars, p); +>>>>>>> More weights adjusted. Added a couple of debugging prints.:src/MIP_Problem.cc } bool

1 0

[GIT] ppl/ppl(master): Added printing of MIP solver recursion level for ( noisy) debugging.
by Enea Zaffanella 14 Jul '09

14 Jul '09

Module: ppl/ppl Branch: master Commit: b64d72bae2beaee734ba6f57657c9a9fdceeec8f URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b64d72bae2be… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Tue Jul 14 18:49:35 2009 +0200 Added printing of MIP solver recursion level for (noisy) debugging. --- src/MIP_Problem.cc | 45 +++++++++++++++++++++++++++++++++++++++------ 1 files changed, 39 insertions(+), 6 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 22603f7..61f489c 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -56,6 +56,8 @@ namespace { unsigned long num_iterations = 0; +unsigned mip_recursion_level = 0; + } // namespace #endif // PPL_NOISY_SIMPLEX @@ -233,6 +235,9 @@ PPL::MIP_Problem::is_satisfiable() const { RAII_Temporary_Real_Relaxation relaxed(x); Generator p = point(); relaxed.lp.is_lp_satisfiable(); +#if PPL_NOISY_SIMPLEX + mip_recursion_level = 0; +#endif if (is_mip_satisfiable(relaxed.lp, relaxed.i_vars, p)) { x.last_generator = p; x.status = SATISFIABLE; @@ -829,8 +834,9 @@ PPL::MIP_Problem::process_pending_constraints() { : compute_simplex_using_exact_pricing(); #if PPL_NOISY_SIMPLEX - std::cout << "MIP_Problem::solve: 1st phase ended at iteration " - << num_iterations << "." << std::endl; + std::cout << "MIP_Problem::process_pending_constraints(): " + << "1st phase ended at iteration " + << num_iterations << "." << std::endl; #endif if (!first_phase_succesful || working_cost[0] != 0) { @@ -1453,7 +1459,7 @@ PPL::MIP_Problem::second_phase() { : compute_simplex_using_exact_pricing(); compute_generator(); #if PPL_NOISY_SIMPLEX - std::cout << "MIP_Problem::solve: 2nd phase ended at iteration " + std::cout << "MIP_Problem::second_phase(): 2nd phase ended at iteration " << num_iterations << "." << std::endl; #endif status = second_phase_successful ? OPTIMIZED : UNBOUNDED; @@ -1703,11 +1709,24 @@ bool PPL::MIP_Problem::is_mip_satisfiable(MIP_Problem& lp, const Variables_Set& i_vars, Generator& p) { +#if PPL_NOISY_SIMPLEX + ++mip_recursion_level; + std::cout << "MIP_Problem::is_mip_satisfiable(): " + << "entering recursion level " << mip_recursion_level + << "." << std::endl; +#endif PPL_ASSERT(lp.integer_space_dimensions().empty()); // Solve the LP problem. - if (!lp.is_lp_satisfiable()) + if (!lp.is_lp_satisfiable()) { +#if PPL_NOISY_SIMPLEX + std::cout << "MIP_Problem::is_mip_satisfiable(): " + << "exiting from recursion level " << mip_recursion_level + << "." << std::endl; + --mip_recursion_level; +#endif return false; + } PPL_DIRTY_TEMP0(mpq_class, tmp_rational); PPL_DIRTY_TEMP_COEFFICIENT(tmp_coeff1); @@ -1747,11 +1766,25 @@ PPL::MIP_Problem::is_mip_satisfiable(MIP_Problem& lp, { MIP_Problem lp_aux = lp; lp_aux.add_constraint(Variable(nonint_dim) <= tmp_coeff1); - if (is_mip_satisfiable(lp_aux, i_vars, p)) + if (is_mip_satisfiable(lp_aux, i_vars, p)) { +#if PPL_NOISY_SIMPLEX + std::cout << "MIP_Problem::is_mip_satisfiable(): " + << "exiting from recursion level " << mip_recursion_level + << "." << std::endl; + --mip_recursion_level; +#endif return true; + } } lp.add_constraint(Variable(nonint_dim) >= tmp_coeff2); - return is_mip_satisfiable(lp, i_vars, p); + bool satisfiable = is_mip_satisfiable(lp, i_vars, p); +#if PPL_NOISY_SIMPLEX + std::cout << "MIP_Problem::is_mip_satisfiable(): " + << "exiting from recursion level " << mip_recursion_level + << "." << std::endl; + --mip_recursion_level; +#endif + return satisfiable; } bool

1 0

[GIT] ppl/ppl(master): Added some weights. Added some debugging prints.
by Roberto Bagnara 14 Jul '09

14 Jul '09

Module: ppl/ppl Branch: master Commit: a17f3bf228fb1388c7f9ab46a44928376f182da9 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a17f3bf228fb… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Tue Jul 14 17:36:47 2009 +0200 Added some weights. Added some debugging prints. --- src/Box.templates.hh | 2 +- src/MIP_Problem.cc | 20 +++++++++++++++----- 2 files changed, 16 insertions(+), 6 deletions(-) diff --git a/src/Box.templates.hh b/src/Box.templates.hh index a43a74f..e6a550d 100644 --- a/src/Box.templates.hh +++ b/src/Box.templates.hh @@ -2619,7 +2619,7 @@ Box<ITV> for (Constraint_System::const_iterator i = cs_begin; i != cs_end; ++i) propagate_constraint_no_check(*i); - WEIGHT_ADD_MUL(1, propagation_weight); + WEIGHT_ADD_MUL(40, propagation_weight); // Check if the client has requested abandoning all expensive // computations. If so, the exception specified by the client // is thrown now. diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 284ccb0..22603f7 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -940,7 +940,7 @@ PPL::MIP_Problem::steepest_edge_exact_entering_index() const { // `lcm_basis' will no longer be needed. lcm_basis *= lcm_basis; std::swap(squared_lcm_basis, lcm_basis); - WEIGHT_ADD_MUL(2, tableau_num_rows); + WEIGHT_ADD_MUL(444, tableau_num_rows); } // Defined here to avoid repeated (de-)allocations. @@ -988,7 +988,7 @@ PPL::MIP_Problem::steepest_edge_exact_entering_index() const { std::swap(current_den, challenger_den); entering_index = j; } - WEIGHT_ADD_MUL(1, tableau_num_rows); + WEIGHT_ADD_MUL(47, tableau_num_rows); } } return entering_index; @@ -1041,7 +1041,7 @@ PPL::MIP_Problem::linear_combine(Row& x, } x[k] = 0; x.normalize(); - WEIGHT_ADD_MUL(1, x_size); + WEIGHT_ADD_MUL(83, x_size); } // See pages 42-43 of [PapadimitriouS98]. @@ -1112,7 +1112,7 @@ PPL::MIP_Problem if (sign > 0 || (sign == 0 && base[i] < base[exiting_base_index])) exiting_base_index = i; - WEIGHT_ADD(1); + WEIGHT_ADD(1044); } } return exiting_base_index; @@ -1608,7 +1608,7 @@ PPL::MIP_Problem::solve_mip(bool& have_incumbent_solution, PPL_DIRTY_TEMP_COEFFICIENT(num); PPL_DIRTY_TEMP_COEFFICIENT(den); lp.evaluate_objective_function(p, num, den); - std::cerr << "new value found: " << num << "/" << den << std::endl; + std::cout << "new value found: " << num << "/" << den << std::endl; #endif } return lp_status; @@ -1625,11 +1625,21 @@ PPL::MIP_Problem::solve_mip(bool& have_incumbent_solution, { MIP_Problem lp_aux = lp; lp_aux.add_constraint(Variable(nonint_dim) <= tmp_coeff1); +#if PPL_NOISY_SIMPLEX + using namespace IO_Operators; + std::cout << "descending with: " + << (Variable(nonint_dim) <= tmp_coeff1) << std::endl; +#endif solve_mip(have_incumbent_solution, incumbent_solution_value, incumbent_solution_point, lp_aux, i_vars); } // TODO: change this when we will be able to remove constraints. lp.add_constraint(Variable(nonint_dim) >= tmp_coeff2); +#if PPL_NOISY_SIMPLEX + using namespace IO_Operators; + std::cout << "descending with: " + << (Variable(nonint_dim) >= tmp_coeff2) << std::endl; +#endif solve_mip(have_incumbent_solution, incumbent_solution_value, incumbent_solution_point, lp, i_vars); return have_incumbent_solution ? lp_status : UNFEASIBLE_MIP_PROBLEM;

1 0

[GIT] ppl/ppl(master): Todo items reorganized. Removed the one about NOT_EQUAL.
by Roberto Bagnara 14 Jul '09

14 Jul '09

Module: ppl/ppl Branch: master Commit: 01c5219d84f3b74f297be7a98b373592b9c0f1d4 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=01c5219d84f3… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Tue Jul 14 16:07:36 2009 +0200 Todo items reorganized. Removed the one about NOT_EQUAL. --- TODO | 15 +++++++-------- 1 files changed, 7 insertions(+), 8 deletions(-) diff --git a/TODO b/TODO index a94f7d4..1a63c8d 100644 --- a/TODO +++ b/TODO @@ -2,14 +2,8 @@ Enhancements for PPL 0.11 ========================= -- Add the domain of circular linear progressions. -- Finish the domain of intervals. - Make all the *affine*image() methods uniform as far as the specification is concerned. -- Check the use or the NOT_EQUAL Relation_Symbol everywhere. -- Intervals are best instantiated with checked numbers with - particular policies: review all the interfaced boxes, - augment the testsuite, and update the documentation. Commits to consider should we release PPL 0.10.3 @@ -35,6 +29,12 @@ This allows to use a non-installed build of GMP in DIR.) Enhancements for PPL 0.12 or later versions =========================================== +- Add the domain of circular linear progressions. +- Finish the domain of intervals. +- Intervals are best instantiated with checked numbers with + particular policies: review all the interfaced boxes, + augment the testsuite, and update the documentation. +- Make the library thread-safe. - Modify the Makefile.am's to extend silent mode to our own rules. - Reduce the number of FIXMEs to no more than 20. - Consider switching to MLGMPIDL for the OCaml interface @@ -98,10 +98,9 @@ Enhancements for PPL 0.12 or later versions - Any_Pointset domain: check the interface for lacking or useless methods. -Enhancements for PPL 0.12 or later versions +Enhancements for PPL 0.13 or later versions =========================================== -- Make the library thread-safe. - Find a way to let the GMP and checked-int versions of the PPL coexist so as to allow using them in the same application. - Provide methods computing approximations of the integer convex hull

1 0

[GIT] ppl/ppl(master): Version number bumped.
by Roberto Bagnara 14 Jul '09

14 Jul '09

Module: ppl/ppl Branch: master Commit: c5beb16e7b88521f7c34804b053fe0ac6b2ac83d URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c5beb16e7b88… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Tue Jul 14 16:05:30 2009 +0200 Version number bumped. --- configure.ac | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/configure.ac b/configure.ac index f5c46e1..17477dc 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.11pre2], [ppl-devel(a)cs.unipr.it], [ppl]) +AC_INIT([the Parma Polyhedra Library], [0.11pre3], [ppl-devel(a)cs.unipr.it], [ppl]) # Minimum Autoconf version required. AC_PREREQ(2.61)

1 0

[GIT] ppl/ppl(master): The *_and_minimize/N predicates have gone: remove residual references to them.
by Roberto Bagnara 14 Jul '09

14 Jul '09

Module: ppl/ppl Branch: master Commit: 456f042c8e04c55936c6da5560b4bca323c65332 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=456f042c8e04… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Tue Jul 14 14:39:00 2009 +0200 The *_and_minimize/N predicates have gone: remove residual references to them. --- interfaces/Prolog/Ciao/ciao_clpq.pl | 1 - interfaces/Prolog/Ciao/ciao_clpq2.pl | 1 - interfaces/Prolog/Ciao/ciao_pl_check.pl | 6 ------ interfaces/Prolog/XSB/xsb_clpq.P | 1 - interfaces/Prolog/XSB/xsb_clpq2.P | 1 - interfaces/Prolog/XSB/xsb_pl_check.P | 6 ------ 6 files changed, 0 insertions(+), 16 deletions(-) diff --git a/interfaces/Prolog/Ciao/ciao_clpq.pl b/interfaces/Prolog/Ciao/ciao_clpq.pl index 253ecb1..20486c9 100644 --- a/interfaces/Prolog/Ciao/ciao_clpq.pl +++ b/interfaces/Prolog/Ciao/ciao_clpq.pl @@ -39,7 +39,6 @@ site: http://www.cs.unipr.it/ppl/ . */ ppl_delete_Polyhedron/1, ppl_Polyhedron_space_dimension/2, ppl_Polyhedron_get_constraints/2, - ppl_Polyhedron_add_constraints_and_minimize/2, ppl_Polyhedron_add_space_dimensions_and_embed/2, ppl_Polyhedron_remove_higher_space_dimensions/2 ]). diff --git a/interfaces/Prolog/Ciao/ciao_clpq2.pl b/interfaces/Prolog/Ciao/ciao_clpq2.pl index c3804d3..226bd2d 100644 --- a/interfaces/Prolog/Ciao/ciao_clpq2.pl +++ b/interfaces/Prolog/Ciao/ciao_clpq2.pl @@ -39,7 +39,6 @@ site: http://www.cs.unipr.it/ppl/ . */ ppl_delete_Polyhedron/1, ppl_Polyhedron_space_dimension/2, ppl_Polyhedron_get_constraints/2, - ppl_Polyhedron_add_constraints_and_minimize/2, ppl_Polyhedron_add_space_dimensions_and_embed/2, ppl_Polyhedron_remove_space_dimensions/2, ppl_Polyhedron_remove_higher_space_dimensions/2 diff --git a/interfaces/Prolog/Ciao/ciao_pl_check.pl b/interfaces/Prolog/Ciao/ciao_pl_check.pl index 8a2527f..6e90092 100644 --- a/interfaces/Prolog/Ciao/ciao_pl_check.pl +++ b/interfaces/Prolog/Ciao/ciao_pl_check.pl @@ -87,17 +87,11 @@ site: http://www.cs.unipr.it/ppl/ . */ ppl_Polyhedron_equals_Polyhedron/2, ppl_Polyhedron_OK/1, ppl_Polyhedron_add_constraint/2, - ppl_Polyhedron_add_constraint_and_minimize/2, ppl_Polyhedron_add_generator/2, - ppl_Polyhedron_add_generator_and_minimize/2, ppl_Polyhedron_add_constraints/2, - ppl_Polyhedron_add_constraints_and_minimize/2, ppl_Polyhedron_add_generators/2, - ppl_Polyhedron_add_generators_and_minimize/2, ppl_Polyhedron_intersection_assign/2, - ppl_Polyhedron_intersection_assign_and_minimize/2, ppl_Polyhedron_poly_hull_assign/2, - ppl_Polyhedron_poly_hull_assign_and_minimize/2, ppl_Polyhedron_poly_difference_assign/2, ppl_Polyhedron_affine_image/4, ppl_Polyhedron_affine_preimage/4, diff --git a/interfaces/Prolog/XSB/xsb_clpq.P b/interfaces/Prolog/XSB/xsb_clpq.P index 6ff822b..c7892b9 100644 --- a/interfaces/Prolog/XSB/xsb_clpq.P +++ b/interfaces/Prolog/XSB/xsb_clpq.P @@ -35,7 +35,6 @@ site: http://www.cs.unipr.it/ppl/ . */ ppl_delete_Polyhedron/1, ppl_Polyhedron_space_dimension/2, ppl_Polyhedron_get_constraints/2, - ppl_Polyhedron_add_constraints_and_minimize/2, ppl_Polyhedron_add_space_dimensions_and_embed/2, ppl_Polyhedron_remove_higher_space_dimensions/2 from ppl_xsb. diff --git a/interfaces/Prolog/XSB/xsb_clpq2.P b/interfaces/Prolog/XSB/xsb_clpq2.P index 2bd6c8e..35f1fa3 100644 --- a/interfaces/Prolog/XSB/xsb_clpq2.P +++ b/interfaces/Prolog/XSB/xsb_clpq2.P @@ -35,7 +35,6 @@ site: http://www.cs.unipr.it/ppl/ . */ ppl_delete_Polyhedron/1, ppl_Polyhedron_space_dimension/2, ppl_Polyhedron_get_constraints/2, - ppl_Polyhedron_add_constraints_and_minimize/2, ppl_Polyhedron_add_space_dimensions_and_embed/2, ppl_Polyhedron_remove_space_dimensions/2, ppl_Polyhedron_remove_higher_space_dimensions/2 diff --git a/interfaces/Prolog/XSB/xsb_pl_check.P b/interfaces/Prolog/XSB/xsb_pl_check.P index 3d2e96c..9e1cb0f 100644 --- a/interfaces/Prolog/XSB/xsb_pl_check.P +++ b/interfaces/Prolog/XSB/xsb_pl_check.P @@ -83,17 +83,11 @@ site: http://www.cs.unipr.it/ppl/ . */ ppl_Polyhedron_equals_Polyhedron/2, ppl_Polyhedron_OK/1, ppl_Polyhedron_add_constraint/2, - ppl_Polyhedron_add_constraint_and_minimize/2, ppl_Polyhedron_add_generator/2, - ppl_Polyhedron_add_generator_and_minimize/2, ppl_Polyhedron_add_constraints/2, - ppl_Polyhedron_add_constraints_and_minimize/2, ppl_Polyhedron_add_generators/2, - ppl_Polyhedron_add_generators_and_minimize/2, ppl_Polyhedron_intersection_assign/2, - ppl_Polyhedron_intersection_assign_and_minimize/2, ppl_Polyhedron_poly_hull_assign/2, - ppl_Polyhedron_poly_hull_assign_and_minimize/2, ppl_Polyhedron_poly_difference_assign/2, ppl_Polyhedron_affine_image/4, ppl_Polyhedron_affine_preimage/4,

1 0

[GIT] ppl/ppl(master): Added WEIGHT_BEGIN and corrected WEIGHT_ADD_MUL macro.
by Enea Zaffanella 14 Jul '09

14 Jul '09

Module: ppl/ppl Branch: master Commit: 80fe52b084cfc50201ef046506e8a967c546d288 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=80fe52b084cf… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Tue Jul 14 15:05:11 2009 +0200 Added WEIGHT_BEGIN and corrected WEIGHT_ADD_MUL macro. --- src/Box.templates.hh | 4 +++- 1 files changed, 3 insertions(+), 1 deletions(-) diff --git a/src/Box.templates.hh b/src/Box.templates.hh index 76379b8..a43a74f 100644 --- a/src/Box.templates.hh +++ b/src/Box.templates.hh @@ -2607,17 +2607,19 @@ Box<ITV> const Constraint_System::const_iterator cs_begin = cs.begin(); const Constraint_System::const_iterator cs_end = cs.end(); const dimension_type cs_size = std::distance(cs_begin, cs_end); + const dimension_type propagation_weight = cs_size * space_dim; Sequence copy; bool changed; dimension_type num_iterations = 0; do { + WEIGHT_BEGIN(); ++num_iterations; copy = seq; for (Constraint_System::const_iterator i = cs_begin; i != cs_end; ++i) propagate_constraint_no_check(*i); - WEIGHT_ADD_MUL(cs_size, space_dim); + WEIGHT_ADD_MUL(1, propagation_weight); // Check if the client has requested abandoning all expensive // computations. If so, the exception specified by the client // is thrown now.

1 0