-------- Original Message -------- Subject: Projection in the PPL Date: Tue, 14 Oct 2003 11:48:52 +0100 From: Axel Simon A.Simon@kent.ac.uk To: Roberto Bagnara roberto@spartacus.cs.unipr.it References: 200310131555.h9DFtbc03190@spartacus.cs.unipr.it
Hi Roberto,
I always thought that projection of polyhedra is done via Fourier Motzkin elimination. Is that true for the PPL library as well or is there a way to reformulate the projection operation on the generator set?
Just curious, Axel.
Roberto Bagnara wrote:
I always thought that projection of polyhedra is done via Fourier Motzkin elimination. Is that true for the PPL library as well or is there a way to reformulate the projection operation on the generator set?
Hello Axel,
No, the PPL does not use Fourier-Motzkin elimination for projection. And yes, it does define projection on the system of generators of the polyhedron. If the polyhedron happens to have such a system of generators up-to-date (as is the case, for instance, after a poly-hull operation), projection can be done much, much more efficiently that way than by using Fourier-Motzkin elimination. Experimentations conducted with the cTI system (http://www.cs.unipr.it/cTI/) showed speedups of up to two orders of magnitude that were essentially due to the increased efficiency of the projection operation. Details about the algorithms we employ are in the PPL code. Please, do not hesitate to ask if you need further explanations. Cheers,
Roberto
On Wed, Oct 15, 2003 at 11:12:38AM +0200, Roberto Bagnara wrote:
Roberto Bagnara wrote:
I always thought that projection of polyhedra is done via Fourier Motzkin elimination. Is that true for the PPL library as well or is there a way to reformulate the projection operation on the generator set?
Hello Axel,
No, the PPL does not use Fourier-Motzkin elimination for projection. And yes, it does define projection on the system of generators of the polyhedron. If the polyhedron happens to have such a system of generators up-to-date (as is the case, for instance, after a poly-hull operation), projection can be done much, much more efficiently that way than by using Fourier-Motzkin elimination.
Projection can increase the size of polyhedron if it is represented by a set of halfspaces. Can the size of a polyhedron represented by its generators increase as well?
Experimentations conducted with the cTI system (http://www.cs.unipr.it/cTI/) showed speedups of up to two orders of magnitude that were essentially due to the increased efficiency of the projection operation. Details about the algorithms we employ are in the PPL code.
Interesting. I looked at the code weeks ago and I figured that the only thing you do is removing the rows of those variables which should be projected out. Is that it? Is it that easy?!
Thanks, Axel.
Axel Simon wrote:
Projection can increase the size of polyhedron if it is represented by a set of halfspaces. Can the size of a polyhedron represented by its generators increase as well?
No. The number of generators will remain the same after projection. This is because we are lazy. An eager implementation may remove any generator that, due to the projection, has become a duplicate of another generator in the system. An even eager implementation may choose to apply full minimization to the obtained generator system.
Experimentations conducted with the cTI system (http://www.cs.unipr.it/cTI/) showed speedups of up to two orders of magnitude that were essentially due to the increased efficiency of the projection operation. Details about the algorithms we employ are in the PPL code.
Interesting. I looked at the code weeks ago and I figured that the only thing you do is removing the rows of those variables which should be projected out. Is that it? Is it that easy?!
Yes, we basically remove the _columns_ of those variables. It is _that_ easy, but do not forget that we have to compute a conversion from the constraint to the generator representation if the latter is not readily available. Clearly, if you need to project just after a poly-hull operation, then the generators will be already there and the projection will be really cheap.
Ciao, Enea.
participants (3)
-
Axel Simon -
Enea Zaffanella -
Roberto Bagnara