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@cs.unipr.it http://www.cs.unipr.it/mailman/listinfo/ppl-devel