[PPL-devel] [Fwd: Projection in the PPL]

[Enea Zaffanella]

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.

-- 
Enea Zaffanella
Dipartimento di Matematica, Universita` di Parma
mailto:zaffanella at cs.unipr.it