[PPL-devel] Closed versus NNC polyhedra

[Roberto Bagnara]

Michael Classen wrote:
> Hello Roberto,
> 
> this is basically what I was referring to:

Hi Michael,

thanks for clarifying.  I need to understand more about what you
mean by:

>> I basically just want to know if I can get correct integer results
>> when using this combination of datatypes. I want to use operations
>> like union, intersection, projection, basically most standard
>> operations you want to use on polytopes.

What do you mean by "correct integer results"?

What I am worried about is that you may believe the PPL supports
the computation of the integer hull of a convex rational polyhedron
(i.e., the smallest polyhedron containing only the integer points
of the given rational polyhedron).  The PPL does not provide an
algorithm to solve this (difficult!) problem.

What the PPL provides is:

1) the C_Polyhedron class that you know;
2) the Grid class that is able, in particular, to express
    the integer lattice;
3) a generic Partially_Reduced_Product class that allows
    to combine two domains, given a reduction procedure
    that propagates _some_ information from one to the
    other.  I am wondering if this is the same notion
    of "combination" you use above.

In point (3) the key words are "partially" and "some".
If _all_ the information was propagated from the Grid
component to the C_Polyhedron component, we would be
able to compute the integer hull, but this is not the
case.

Going back to the expression "correct integer results",
a Partially_Reduced_Product among a C_Polyhedron and
a Grid encoding the integer lattice provides (as far as
we know) correct, but possibly (and often) imprecise
results.
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