[PPL-devel] Technical questions on how to extend a polyhedron

[giuseppe lipari]

Dear Enea,

thanks a lot for the prompt response. Indeed, all variables are non 
negative,
and the polyhedron is bounded. We will try to do some test, and let you 
know.

Giuseppe Lipari

On 01/31/2013 02:54 PM, Enea Zaffanella wrote:
> On 01/30/2013 07:22 PM, giuseppe lipari wrote:
>> Dear all,
>>
>> we are using the PPL (C++ version) to model a parametric real-time
>> scheduling problem.
>> At some point in our methodology, we obtain a region of space
>> constrained by a C_Polyhedron that describes a subset of valid solutions
>> for our problem.
>>
>> Our problem has also this nice property: if X=(x_1, ..., x_n) is a
>> vector contained in the C_Polyhedron, then any Y = (y_1, ...., y_n) with
>>
>>     forall i 0<= y_i <= x_i,
>>
>> is also a valid solution.
>>
>> Therefore we would like to extend the C_Polyhedron to include all
>> vectors   0<= Y <= X.
>>
>> So, our questions are:
>>
>> 1) Is there any simple way of doing it in PPL?
>>
>> In 2D we thought of the following simple strategy: add points (0,0)
>> (x1,0) (0, x2) to the set of generators of the polyhedron, then minimize
>> it.
>>
>> 2) Is this strategy correct?
>> 3) How can we extend it to N dimension?
>>
>> Thanks in advance for your kind response
>>
>> Giuseppe Lipari
>> Laboratoire Spécification et Vérification,
>> Ecole Normale Supérieure de Cachan
>
>
> Hello Giuseppe.
>
> There is something which is unclear (at least to me) in your 
> description of the class of polyhedra of interest.
>
> Do the points in your polyhedra always have non-negative coordinates?
> In the following I am assuming this property holds.
> (I think that, without this additional property, the minimal set 
> containing your polyhedron and satisfying the requirement above might 
> be a non-convex set.)
>
>
> Regarding question 1, it depends on the notion of "simpler".
> From the point of view of the programmer, the following approach might 
> be simpler:
>   * first, for each space dimension i, add the ray
>        Generator::ray(-Variable(i));
>   * then, for each space dimension i, add the constraint
>        Constraint(Variable(i) >= 0);
> If N is the space dimension, this means adding N generators, minimize 
> (done implicitly), adding N constraints, minimize (if you want a 
> non-redundant constraint description).
>
>
> Regarding question 2:
> the approach you propose seems to be correct for *bounded* polyhedra 
> (i.e., polytopes). If the polyhedron is unbounded, we can build a 
> counter-example:
>
> Consider the polyhedron defined by constraints
>    x1 >= 0, x2 >= 0, x1 == x2.
> Its generator system will contain a ray (1, 1) and a point (0, 0) in 
> the origin of the vector space. Using your approach, the polyhedron 
> will be left unchanged ... which is wrong, as you want to obtain the 
> whole non-negative quadrant.
>
> That said, the fix seems to be simple: first check for boundedness; if 
> it is unbounded, return the non-negative quadrant; if it is bounded, 
> use the proposed approach.
>
>
> Regarding question 3:
> the approach should be easily generalizable by using an inner loop:
>
>   for each generating point p {
>     for each space dimension i {
>       add a point which is the same of p
>       except that it has a zero for coordinate i
>     }
>   }
>   add the origin of the vector space
>
> Now, if your polyhedron has M points (could be M >> N), this will 
> cause the addition of M*N + 1 generating points, followed by a single 
> minimization.
>
> It is quite difficult to predict whether or not this approach is going 
> to be more efficient than the one proposed above. I recommend doing 
> some efficiency tests.
>
> Regards,
> Enea Zaffanella.