
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.

Enea Zaffanella wrote:
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).
This is why we have a Status class in the first place: to make it simple to add new introspective capabilities to the polyhedra classes. The idea of distinguishing between minimization and NNC-minimization looks promising (even though the name "NNC-minimization" is horrible ;-)
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 ?
We never assume that consciously (i.e., if the actual code happens to rely on that assumptiom, then it is a bug).
Roberto

Roberto Bagnara wrote:
Enea Zaffanella wrote:
[...]
This is why we have a Status class in the first place: to make it simple to add new introspective capabilities to the polyhedra classes. The idea of distinguishing between minimization and NNC-minimization looks promising (even though the name "NNC-minimization" is horrible ;-)
Well, choosing the right name was not the top item in my priority list. Any better idea is welcome ...
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 ?
We never assume that consciously (i.e., if the actual code happens to rely on that assumptiom, then it is a bug).
Good. 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.
ciao, Enea.

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.
participants (2)
-
Enea Zaffanella
-
Roberto Bagnara