Enhancements for PPL 0.7
========================

- Allow the specification of alternative coefficient implementations.
- Clearly explain, in the documentation, how (not) to use
  set_GMP_memory_allocation_functions().  More generally, explain how
  to have memory-guarded computations.
- Completely rewrite the handling of temporary coefficients.
- Implement the -t option of ppl_lcdd.
- Make sure ppl_lcdd is able to parse problems produced by lrs, i.e.,
  where the number of rows of the matrix is omitted and replaced by
  "*****".


Enhancements for PPL 0.8 or later versions
==========================================

- Implement void Polyhedron::envelope_assign(const Polyhedron& y).
- Implement the extrapolation operators defined in HenzingerH95
  and HenzingerPW01.
- 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.


Constructions on Polyhedra
==========================

Since version 0.6, the PPL supports the determinate and powerset
constructions of the constraint system hierarchy described in

  R. Bagnara.
  A hierarchy of constraint systems for data-flow analysis
  of constraint logic-based languages.
  Science of Computer Programming 30, 1-2 (January 1998), pp. 119-155.
  Available at http://www.cs.unipr.it/~bagnara/Papers/Abstracts/SCP98

The implementation consists in a generic implementation (in the form
of C++ templates) of the hierarchy, plus a specialization of the
powerset construction on polyhedra.  What is missing now is the
ask-and-tell construction.  We have some old code implementing it
but it requires extensive work.


Efficiency Issues
=================

- There must be a more efficient way to implement
  bool Polyhedron::is_disjoint_from(const Polyhedron&).

- There must be a more efficient way to compute convex
  differences.

- We are being rather careless about the creation of temporaries
  as far as the classes LinExpression, Constraint and Generator
  are concerned.

- In Polyhedron::strongly_minimize_constraints(), after the removal
  of eps-redundant constraints, find an efficient way to test whether
  or not the eps_leq_one constraint is needed to obtain an upper bound
  on the epsilon dimension.


Cutting-Plane Methods
=====================

Suppose we are only interested in integral solutions (as is the
case, e.g., in most termination analyses).  Then cutting-plane methods
(Gomory, Chvátal, ...) allow to shrink polyhedra still not losing any
integral solution.
See http://www.cs.unipr.it/ppl/Documentation/bibliography#NemhauserW88


Z-Polyhedra
===========

We plan to extend the PPL to deal with Z-polyhedra [Ancourt91th].
Z-polyhedra are intersections and other representations for discrete sets.

  C. Ancourt.
  Génération automatique de codes de transfert pour
  multiprocesseurs à mémoires locales.
  PhD thesis, Université de Paris VI, March 1991.