[PPL-announce] Parma Polyhedra Library 0.6

[Roberto Bagnara]

We are very happy to announce the availability of PPL 0.6, the latest
release of the Parma Polyhedra Library.

More than a year has passed since the previous release.  During this
period we have been doing a considerable amount of research and
development work and this release, which is the first of a series of
official versions that we hope to publish in the very near future,
incorporates some of this work.

The main focus of this release is on complete support for powersets of
polyhedra.  This includes the customizable framework for the
definition of widening operators we have proposed at this year's VMCAI
conference.  Then there is support for summary dimensions as proposed
by Denis Gopan and colleagues in their TACAS 2004 paper.  We have
started adding demo programs to the library.  One of them, `ppl_lcdd',
is actually useful and is competitive with similar programs available
out there.  Many other improvements have been performed:
documentation, performance, portability and the configuration
machinery have all been improved.  A handful of bugfixes complete the
picture: see below for more details.

For more information, visit the PPL web site at

        http://www.cs.unipr.it/ppl/

The PPL development team:

       Roberto Bagnara  <bagnara at cs.unipr.it>
       Patricia M. Hill <hill at comp.leeds.ac.uk>
       Enea Zaffanella  <zaffanella at cs.unipr.it>


New and Changed Features
========================

o  New templatic classes Determinate, PowerSet, and Polyhedra_PowerSet.
    The first two classes realize, in a completely generic way, the
    determinate and powerset constructions described by Roberto Bagnara
    in his 1998, Science of Computer Programming paper.  The third class
    is a specialization of the powerset construction on polyhedra.
    The powerset construction comes with the generic widening technique
    proposed by Roberto Bagnara, Patricia Hill and Enea Zaffanella
    in their VMCAI 2004 paper.  Actually, the Polyhedra_PowerSet class
    provides the first genuine, non-trivial widening ever proposed
    (let alone made available) on a domain of sets of convex polyhedra.

o  New methods

      void Polyhedron::expand_dimension(Variable, dimension_type) and
      void Polyhedron::fold_dimensions(const Variables_Set&, Variable)

    allow the easy realization of summary dimensions as proposed
    by Denis Gopan and colleagues in their TACAS 2004 paper.

o  A new `demos' directory has been added.  In the `ppl_lcdd'
    subdirectory, this contains a sort of clone of the cddlib test
    program `lcdd', written using the PPL's C++ interface, together
    with several example polyhedra in the formats that the program can
    handle.  The `ppl_lpsol' subdirectory contains another demo program
    that solves linear programming problems by vertex/point
    enumeration.  This is written using the PPL's C interface and comes
    with several example problems in the Mathematical Programming
    System (MPS) format.  In order to read MPS files, `ppl_lpsol' uses
    the GNU Linear Programming Kit (GLPK); thus `ppl_lpsol' is only compiled
    if a suitable version of GLPK is available.

o  New macro PPL_VERSION expands to the version string of the library.

o  New file README.configure provides additional information about
    the configuration and compilation of the library.

o  The documentation has been improved in various ways.

o  The documentation for users, in PostScript, PDF and HTML formats,
    is now installed in a standard place by `make install'.

o  The variable `abandon_exponential_computations' has been renamed
    `abandon_expensive_computations'.

o  The methods

      void Polyhedron::add_constraints(ConSys& cs),
      void Polyhedron::add_generators(GenSys& gs),
      bool Polyhedron::add_constraints_and_minimize(ConSys& cs), and
      bool Polyhedron::add_generators_and_minimize(GenSys& gs)

    have been renamed

      void Polyhedron::add_recycled_constraints(ConSys& cs),
      void Polyhedron::add_recycled_generators(GenSys& gs),
      bool Polyhedron::add_recycled_constraints_and_minimize(ConSys& cs), and
      bool Polyhedron::add_recycled_generators_and_minimize(GenSys& gs),

    respectively.  At the same time, the methods

      void Polyhedron::add_constraints(const ConSys& cs),
      void Polyhedron::add_generators(const GenSys& gs),
      bool Polyhedron::add_constraints_and_minimize(const ConSys& cs), and
      bool Polyhedron::add_generators_and_minimize(const GenSys& gs)

    have been added.  Corresponding changes have been made to the C and
    Prolog interfaces.

o  New methods Polyhedron::maximize() and Polyhedron::minimize()
    for maximizing and minimizing a linear expression subject to the
    polyhedron.

o  New output operator in namespace IO_Operators:
    std::ostream& operator<<(std::ostream&, const LinExpression&).

o  The method Polyhedron::map_dimensions(const PartialFunction& pfunc)
    has been significantly optimized for the case when `pfunc' is a
    permutation.  A simple "renaming" of the dimensions is now
    extremely cheap.

o  The function Parma_Polyhedra_Library::max_space_dimension() has been
    given a new semantics and destiny: it returns the maximum space
    dimension that _all_ the abstractions provided by the library can
    handle.  Each individual abstraction provides its versions of this
    function.  Thus, e.g., NNC_Polyhedron::max_space_dimension()
    gives the maximum space dimensions an NNC_Polyhedron can handle.

o  The type of output functions for the class Variable,
    `Variable::Output_Function_Type', has been renamed
    `Variable::output_function_type' and is now defined as
    void output_function_type(std::ostream& s, const Variable& v).
    In other words, `v' is now passed by const reference and not by value.

o  Thanks to Bruno Haible, it is now possible to use versions of the
    GMP library installed into nonstandard places.  The new configure
    options --with-libgmp-prefix[=DIR] and --with-libgmpxx-prefix[=DIR]
    substitute the old (and not really working) options
    --with-gmp-includes=DIR and --with-gmp-dir=DIR.


Bugfixes
========

o  Fixed a bug in the C interface function ppl_Polyhedron_map_dimensions()
    whereby a wrong result was computed.

o  Fixed a bug in Polyhedron::poly_difference_assign(const Polyhedron&)
    whereby a wrong result was computed.

o  Fixed a bug in the Prolog interface predicate
    ppl_Polyhedron_get_bounding_box/3 whereby a wrong result was
    sometimes computed in the case of an empty polyhedron.

o  Fixed a bug in the Prolog interface predicate
    ppl_new_Polyhedron_from_bounding_box/3 whereby the predicate was
    failing when given an empty bounding box.

-- 
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara at cs.unipr.it