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@cs.unipr.it http://www.cs.unipr.it/mailman/listinfo/ppl-devel