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

[Enea Zaffanella]

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.