[PPL-devel] Powerset of a set of convex sets.

[Enea Zaffanella]

Amit Bhatia wrote:
> Hello,
>  I am a new user of PPL, and am trying to do the following using PPL.
> I have a bunch of convex sets (represented as intersection of half
> spaces), and would like to find the non empty elements of the powerset
> of this set of convex sets.  It involves checking set intersections. I
 > am wondering if PPL provides an elegant and efficient way to do this?

I am not sure I understand what you mean by
    "powerset of this set of convex sets".

Let me try and rephrase:
   - you have a set of n polyhedra S = { ph_1, ..., ph_n };
   - you consider its powerset P(S), having 2^n elements;
   - each element in P(S) is interpreted conjunctively (not 
disjunctively), i.e., its meaning is the *intersection* (rather than the 
union) of the ph_i contained in it.

Then, you would like to list *all* elements in P(S) that have a 
non-empty meaning, assuming the interpretation above.
Is that correct?

Well, the PPL has no direct way of implementing this specific 
requirement, however it provides most (all?) of the functionality needed 
to write some ad hoc code doing it.

> The only other option I can think of is to consider every possible
> subset of the set, and then check for intersection by checking for
> feasibility using linear programming.

Using linear programming (which is provided by the PPL via class 
MIP_Problem) is likely to be a good starting point, since you have a 
constraint representation and you just want to compute intersection and 
test for satisfiability.

However, I suspect that much of the effort should be devoted in finding 
a good generate&test pattern: as soon as you discover that a powerset 
element is empty, all of its supersets will be trivially empty too and 
should not be checked explicitly. You should also pay attention to 
incrementality in the computation: if you know that the powerset element 
P1 is feasible and later want to check if P2 is feasible and P2 contains 
P1 ... then you can start from the feasible solution computed for P1, 
rather than from scratch.

Cheers,
Enea.


> thanks,
> amit.
> _______________________________________________
> PPL-devel mailing list
> PPL-devel at cs.unipr.it
> http://www.cs.unipr.it/mailman/listinfo/ppl-devel
> 
>