[PPL-devel] Implementation of convex hull for C_Polyhedron using only constraints

[Enea Zaffanella]

Hi Tushar.

There is one implementation of the convex hull for C_Polyhedra in the 
PPL, based on the "usual" double description conversion procedure. In 
principle, many alternative implementations can be obtained by using 
finer granularity operators. However, no sensible advice can be given 
for the "general case", since the efficiency is known to be highly 
dependent on the specific input.

You can also have a look to the following paper, where (among other 
things) there is a comparison of the performance of many polyhedra 
libraries on the convex hull problem:

B. Assarf, E. Gawrilow, K. Herr, M. Joswig, B. Lorenz, A. Paffenholz, 
and T. Rehn. polymake in linear and integer programming. Technical 
Report arXiv:1408.4653 [math.CO], August 2014.

      http://arxiv.org/abs/1408.4653

Regards,
Enea Zaffanella.


On 01/29/2016 08:31 PM, Tushar Sharma wrote:
>
> Hi all,
>
>
> I am using C_Polyhedron to perform abstract interpretation. The 
> polyhedrons I am dealing with take a lot of time to perform convex 
> hull. The convex hull spends a lot of time in add_and_minimize 
> operation. I was wondering if there is an alternate implementation in 
> PPL 1.1 (or some other unstable version), that performs hull operation 
> using CLP so that I can compare the two implementations.
>
>
> Thanks,
>
> Tushar Sharma
>
> Graduate Student
>
> Computer Sciences
>
> University of Wisconsin-Madison
>
>
>
> _______________________________________________
> PPL-devel mailing list
> PPL-devel at cs.unipr.it
> http://www.cs.unipr.it/mailman/listinfo/ppl-devel

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.cs.unipr.it/pipermail/ppl-devel/attachments/20160130/a06d444d/attachment.htm>