[PPL-devel] Again on NNC minimization.

[Enea Zaffanella]

Hi all.

You might have noted that the current implementation of NNC minimization
only works starting from generators, meaning that in order to obtain
an NNC-minimized set of constraints you have to call once again the
(standard) minimize method ... or the update_constraints() method,
which is basically the same, since we have generators already minimized.

I now think that a _similar_ minimization process can be applied
also to constraints, exploiting "a kind of" duality principle,
so that it is possible to avoid the second minimization process
if ONLY the constraints are needed. I will try and implement such
a method, so that we can start doing experiments with it.

For the time being, I would like to better explain what I mean when
I say "a kind of" duality principle, in order to obtain some feedback
from you.

Consider an n-dimension-space NNC polyhedron, which is encoded using
an (n+1)-dimension-space _closed_ polyhedron.

The standard minimization process is representation preserving,
meaning that the input (redundant) and output (reduced) systems
do represent the same (n+1)-dimension-space closed polyhedron.

In contrast, the NNC minimization process,
while being "semantic" preserving (i.e., the NNC-redundant and NNC-reduced
systems do encode the same n-space-dimension NNC polyhedron),
it is not representation preserving, because the NNC-reduced system
(in general) will represent a _different_ (n+1)-dimension-space closed 
polyhedron.

This fact has consequences when we do want to be lazy.
Consider the following scenario:

We have a NNC-polyhedron having only constraints up-to-date and we do
want to obtain the NNC-reduced system of generators. We can do the 
following:

1) update the generators (using the standard algorithm), obtaining as 
by-product
both the sat_c matrix and a minimized con_sys.
2) use the first part of the NNC_minimize() method (i.e., without the 
last call
to minimize()) to compute the NNC-reduced system of generators.

At this point we have that:

a) both the con_sys and the gen_sys do represent the same NNC-polyhedron
b) the gen_sys is NNC-minimized
c) the con_sys is minimized, but it might be NNC-redundant
d) gen_sys and con_sys might represent DIFFERENT (n+1-space-dim) closed 
polyhedra.

Note in particular points a) and d). This situation could be exploited
positively: we could add further status flags to the polyhedron, to remember
that the con_sys is both up-to-date and minimized, but it is not 
NNC-minimized,
while the gen_sys is NNC-minimized (which implies the other two).
Clearly, we have to be careful with this "partial" misalignment of 
con_sys and
gen_sys ... they are NOT the dual of each other!
In particular, in such a situation the saturation matrices will NOT be 
up-to-date
(as far as I can see).

So, a first question for Elisa: as things are now, do we ever "assume" that
whenever both con_sys and gen_sys are minimized, then the saturation 
matrices
are up-to-date ?
(Such an assumption is no longer valid in the scenario above.)

Enea.