[PPL-devel] Again on NNC minimization.

[Enea Zaffanella]

Enea Zaffanella wrote:

> However, in the method update_sat_X, we DO assume that if both con_sys and
> gen_sys are minimized, then they are the dual of each other.
> Such an assumption, which was completely legal before, will have to be 
> relaxed
> if we adopt the above scenario.


Well, probably this sentence needs a bit of justification.
What I was thinking at is an extension of the Status field
so that three new flags are handled (in the case of an NNC_Polyhedron):

- constraints_are_strongly_minimized()
- generators_are_strongly_minimized()
- is_dual_description()

The meaning of the first two flags should be clear enough
(provided one thinks that the name "strong_minimization"
is a better enough alternative to "NNC-minimization" ;) ).
Clearly,

    constraints_are_strongly-minimized()
      ==>
        constraints_are_minimized()
          ==>
            constraints_are_up-to-date()

and the same will hold for generators.

The third flag will remember whether or not the two descriptions
actually are the dual of each other. This assertion is, as far as
I can see, completely independent from assertions regarding the
(strong) minimization of the systems.
The following implications will hold:

    sat_c_is_up_to_date() || sat_g_is_up_to_date()
      ==>
        is_dual_description()
          ==>
            constraints_are_up_to_date() && generators_are_up_to_date().

Now, whenever we apply the standard minimization process,
we will obtain both con_sys and gen_sys minimized and they
will form a dual-description; but they won't necessarily be
strongly minimized.

Whenever we apply one of the one-side strong-minimization methods,
we will obtain ONE of the systems strongly-minimized;
the other one will remain in its previous state and we will have
to clear the is_double_description() flag (unless the strong-minimization
process happens to do nothing).

When we apply the full strong-minimization process,
working on both matrices, then we will obtain both systems
strongly minimized and forming a dual-description.

In principle we could also have BOTH systems strongly minimized
but without being one the dual of the other. But I think that this
cannot happen if we use the currently available methods ...

Enea.