[PPL-devel] integer versus rational solutions

[Roberto Bagnara]

Tobias Grosser wrote:
> @Roberto:
> Can you give us some hints, what is really expensive and what should we
> avoid when constructing polyhedrons in the PPL?

You should take into account that many algorithms are exponential in
the space dimension, both in space and in time.  Additionally, there
is no upper bound to the number of constraints and generators a
polyhedron can have: so, if your application tends to build complex
polyhedra (even if the space dimension is small) you may have problems.
On top of all this, the dimensions of the coefficients involved plays
a (usually minor) role.

To summarize, do not use general polyhedra without:

1) making sure your application does not generate polyhedra with
    high dimension or that are very complex in terms of the number
    of constraints or generators; and/or

2) guard all polyhedra computation with complexity watchdogs.

In our own work, we use a combination of 1 and 2.

Concerning 2) now the PPL can exploit the deterministic timeout
facilities offered by the PWL (Parma Watchdog Library, distributed
along with the PPL).  I will write about that in a few hours.
Cheers,

     Roberto

-- 
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