Module: ppl/ppl Branch: master Commit: 9037c88e5adb824dc896eeb3f65d7167d1536063 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=9037c88e5adb8... Author: Roberto Bagnara <bagnara@cs.unipr.it> Date: Sat Apr 25 14:48:38 2009 +0200 One obsolete item removed. Other items partially scheduled. --- TODO | 63 +++++++++++++++++++++++++++++++++------------------------------ 1 files changed, 33 insertions(+), 30 deletions(-) diff --git a/TODO b/TODO index 97a262f..c57a6cb 100644 --- a/TODO +++ b/TODO @@ -38,21 +38,6 @@ Enhancements for PPL 0.11 or later versions of the simplex solver. - Complete the implementation of the --enable-check configure option. Explain it in README.configure. -- 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 - of semantic domains for the case where we are only interested in integral - solutions (as is the case, e.g., in many program analyses). Then - cutting-plane methods (Gomory, Chvatal, ...) allow to shrink polyhedra - still not losing any integral solution. - See http://www.cs.unipr.it/ppl/Documentation/bibliography#NemhauserW88 - Check the work by Kent Andersen and Gerard Cornuejols on - reduce-and-split cuts. -- Consider the addition of "constraint-only" methods (e.g., computing - projections and upper bounds using the MIP solver). -- Consider extending the MIP solver to handle Parametric Integer - Programming. - Ensure the tests in tests/MIP_Problem/* cover every line of code in MIP_Problem.*. - Define functions rem() and remp() to compute the remainder of division @@ -92,6 +77,37 @@ Enhancements for PPL 0.11 or later versions is the one needed by users: in particular, see if it should take as an argument a generator system, instead of an abstract element. - Provide a generic implementation for the `widening with tokens'. +- Implement the extrapolation operators defined in HenzingerH95 + and HenzingerPW01. +- Implement void Polyhedron::envelope_assign(const Polyhedron& y). +- Provide support for strict inequalities in MIP problems. +- Pointset_Powerset and Partially_Reduced_Product domains: + Improve and add to the existing methods for the powerset and product domains + so that they can be subdomains of themselves and of each other; + tidy the tests directories for these domains and ensure the code + with all likely instantiations is fully tested; + add the same functionaity to the C, Java, OCaml and Prolog interfaces. +- Any_Pointset domain: check the interface for lacking or useless methods. + + +Enhancements for PPL 0.12 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 + of semantic domains for the case where we are only interested in integral + solutions (as is the case, e.g., in many program analyses). Then + cutting-plane methods (Gomory, Chvatal, ...) allow to shrink polyhedra + still not losing any integral solution. + See http://www.cs.unipr.it/ppl/Documentation/bibliography#NemhauserW88 + Check the work by Kent Andersen and Gerard Cornuejols on + reduce-and-split cuts. +- Consider the addition of "constraint-only" methods (e.g., computing + projections and upper bounds using the MIP solver). +- Consider extending the MIP solver to handle Parametric Integer + Programming. - In the OK() methods, instead of having all those #ifndef NDEBUG, it is probably worthwhile to use a suitable defined `barf' stream that does the right thing. @@ -99,14 +115,6 @@ Enhancements for PPL 0.11 or later versions "automatically". Consider whether it is worth doing it. - Provide a single, generic implementation to replace all our status classes. -- Implement the extrapolation operators defined in HenzingerH95 - and HenzingerPW01. -- Implement void Polyhedron::envelope_assign(const Polyhedron& y). -- Provide support for strict inequalities in MIP problems. -- See whether, using the techniques described in - ftp://ftp.ifor.math.ethz.ch/pub/fukuda/reports/polyunion001120.ps.gz - we can implement bool poly_hull_assign_if_exact(PH& p, const PH& q), - temporarily in algorithms.hh, more efficiently. - Provide optimized implementations of Polyhedron::expand_dimension() Polyhedron::fold_dimensions(). - Add an implementation of Minkowski addition. Check the algorithm @@ -117,13 +125,7 @@ Enhancements for PPL 0.11 or later versions of convex polytopes. J. Symbolic Comput., 38(4):1261-1272, 2004. -- Pointset_Powerset and Partially_Reduced_Product domains: - Improve and add to the existing methods for the powerset and product domains - so that they can be subdomains of themselves and of each other; - tidy the tests directories for these domains and ensure the code - with all likely instantiations is fully tested; - add the same functionaity to the C, Java, OCaml and Prolog interfaces. -- Any_Pointset domain: check the interface for lacking or useless methods. + Efficiency Issues ================= @@ -137,6 +139,7 @@ Efficiency Issues - Provide a better implementation of computing squares in MIP_Problem's steepest-edge to avoid big numbers. + Debian packaging ================