3
$\begingroup$

I have a set of 73 linear non-strict inequalities that describe a convex polytope in the 36-dimensional space. All but one of the inequalities are of the form $x>=b$ or $x<=b$. In every but one inequality, there is only one variable. Furthermore, every variable has a lower and an upper bound defined by an inequality (they all lie between 0 and 1). The last inequality states that the sum of all variables must be equal to or lower than one.

I know that those inequalities describe a convex polyhedron (polytope) by its H-representation. I need to transfrom it to its V-representation, thus I need to find the convex hull. So far I used the python wrapper pycddlib of the library cddlib. This library uses the double description method and is far too slow for my problem.

I was therefore wondering if there is another approach that can be used in python that is faster, especially in my case. For example, is there an algorithm that works better if you know in advance that your polyhedron is convex and you therefore do not need to compute the rays but only the vertices of the V-representation?

Another idea are algorithms for fixed dimensions. Bernard Chazelle created such an optimal algorithm, but I couldn't find any implementations of his idea so far.

I also came across the "reverse search method", which seems to be implemented in lrs (in ANSI C). However, it seems that this library does not work with Python.

Does anyone have a suggestion other than Parma Polyhedra Library (which also uses the double description method) how to solve my vertex enumeration problem the fastest way possible? Especially in my case, is there anything about its simplicity that allows for a simpler solution than cddlibs double description implementation?

Thank you very much for your effort!

$\endgroup$
1
  • 1
    $\begingroup$ Isn't Python a way of gluing together C libraries written long ago? Have you tried using something like shared objects? $\endgroup$ Sep 19, 2022 at 15:19

1 Answer 1

0
$\begingroup$

I don't know if it is faster, but I used the pypoman library. You can encode your problem as a matrix A and vector b, such that Ax ≤ b. From there, you can solve the vertex enumeration problem by calling pypoman.compute_polytope_vertices(A,b). To find the convex hull from this set of points, I used scipy.spatial.ConvexHull.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .