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:
- 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.
- Is this strategy correct?
- 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.