5
$\begingroup$

I need to find the vertices of a polyhedron from the defining halfspaces. In a previous question libraries for enumerating all vertices were mentioned. However i have a very large polyhedron (~100,000 halfspaces and more) where enumerating all vertices would be prohibitively expensive. Even for pretty small problems (~500 halfspaces ~100 variables) using pypoman library for python the function compute_polytope_vertices doesn't return. I would like to use a streaming implementation where compute_polytope_vertices would return a generator of the vertices. Does such an implementation exist?

Any help would be appreciated.

EDIT I tested lrs library as suggested. For the simple example below pypoman runs very fast (~7ms) and lrs windows binary running slowly (~7s):

test
H-representation
begin
56 22 rational
 20  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1 
 0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1 
 40  -1  -1  -1  -1  0  0  0  0  0  1  0  0  0  0  0  0  0  1  0  0  0 
 -40  1  1  1  1  0  0  0  0  0  -1  0  0  0  0  0  0  0  -1  0  0  0 
 0  1  0  0  0  -1  -1  -1  0  0  0  1  0  0  0  0  0  0  0  1  0  0 
 0  -1  0  0  0  1  1  1  0  0  0  -1  0  0  0  0  0  0  0  -1  0  0 
 0  0  1  0  0  1  0  0  -1  -1  0  0  1  0  0  0  1  0  0  0  0  0 
 0  0  -1  0  0  -1  0  0  1  1  0  0  -1  0  0  0  -1  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  -1  -1  -1  -1  -1  -1  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1  0  0  0  0  0  0 
 0  0  0  1  0  0  1  0  0  0  0  0  0  1  0  0  -1  -1  0  0  1  0 
 0  0  0  -1  0  0  -1  0  0  0  0  0  0  -1  0  0  1  1  0  0  -1  0 
 0  0  0  0  0  0  0  1  1  0  0  0  0  0  1  0  0  1  -1  0  0  1 
 0  0  0  0  0  0  0  -1  -1  0  0  0  0  0  -1  0  0  -1  1  0  0  -1 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
end

For a slightly bigger example pypoman runs for ~350ms lrs hasn't finished after several minutes.

daniel test
H-representation
begin
72 29 rational
 20  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0 
 20  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1 
 0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1 
 80  -1  -1  -1  -1  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  1  0 
 -80  1  1  1  1  0  0  0  0  -1  0  0  0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  -1  0 
 0  1  0  0  0  -1  -1  -1  -1  0  0  1  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0 
 0  -1  0  0  0  1  1  1  1  0  0  -1  0  0  0  0  0  0  0  0  0  0  -1  0  0  0  0  0  0 
 0  0  0  0  0  1  0  0  0  -1  -1  0  1  0  0  0  0  0  1  0  0  0  0  1  0  0  0  0  1 
 0  0  0  0  0  -1  0  0  0  1  1  0  -1  0  0  0  0  0  -1  0  0  0  0  -1  0  0  0  0  -1 
 0  0  1  0  0  0  0  0  0  0  0  -1  -1  -1  -1  -1  0  0  0  0  0  0  0  0  1  0  0  0  0 
 0  0  -1  0  0  0  0  0  0  0  0  1  1  1  1  1  0  0  0  0  0  0  0  0  -1  0  0  0  0 
 0  0  0  0  0  0  1  0  0  0  1  0  0  1  0  0  -1  -1  0  1  0  0  0  0  0  1  0  0  0 
 0  0  0  0  0  0  -1  0  0  0  -1  0  0  -1  0  0  1  1  0  -1  0  0  0  0  0  -1  0  0  0 
 0  0  0  1  0  0  0  1  0  0  0  0  0  0  1  0  0  0  -1  -1  -1  -1  0  0  0  0  0  0  0 
 0  0  0  -1  0  0  0  -1  0  0  0  0  0  0  -1  0  0  0  1  1  1  1  0  0  0  0  0  0  0 
 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  -1  -1  -1  -1  -1  0  0 
 0  0  0  0  -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1  0  1  1  1  1  1  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
end

I want to run on much bigger instances and lrs just seems very slow.

$\endgroup$
5
  • $\begingroup$ A "pretty small" problem (500 halfspaces, 100 variables) could potentially have over $10^{100}$ vertices. Are you sure you want to stream all of them? $\endgroup$
    – prubin
    Aug 29 at 15:06
  • $\begingroup$ I don't want to stream all of them as you say that would be impossible. I want to get the beginning of the stream up to say 100,000 vertices. The problem is that the implementation I've seen returns all the vertices so if there are a lot of vertices it just doesn't return. $\endgroup$
    – Daniel
    Aug 29 at 20:10
  • $\begingroup$ Hello, thanks for your question! Generating all of those vertices would take many minutes, hours and potentially days. The potential generator would also be very costly to create the algorithm. Have you ever heard about computational complexity, it is one of the key points in Optimization Theory, and in many other algorithms (implementation) development. $\endgroup$
    – dozgunay
    Aug 30 at 17:45
  • $\begingroup$ The algorithm is supposed to enumerate the vertices efficiently (polynomial delay) so it should be able to produce a (relatively) fast stream. Obviously enuumerating all solutions would be impossible $\endgroup$
    – Daniel
    Aug 31 at 18:57
  • $\begingroup$ In this FAQ [Sec. 5, Page 27, Fukuda says that "Cddlib is efficient for highly degenerate cases, whereas Lrs is efficient for non-degenerate cases". $\endgroup$ Nov 6 at 23:03

1 Answer 1

2
+50
$\begingroup$

You can check the lrs software implemented by David Avis from McGill. The software implements the reverse search algorithm described in this serie of papers:

Since the output is never stored in memory, it can handle large-size instances. Moreover, you can stop the execution after a given number of iterations (it seems you don't need all of the vertices).

There is also a parallel implementation of reverse search called mplrs.

NOTE: The tools are available from the command line, and you access to the source code written in C (I am not aware of a Python interface).

$\endgroup$
5
  • $\begingroup$ I never used pypoman, but I had tried Polymake and Porta as alternatives. The parallel version mplrs on my desktop was performing quite well. I might have compiled the source code by myself, I don't remember, sorry. $\endgroup$ Sep 7 at 20:17
  • 2
    $\begingroup$ Thanks it does indeed stream the results. There is something strange - when i run it on an instance of size 72 constraints and 28 variables it doesn't finish running after more than 10 minutes where pypoman interface to cdd finished in a few seconds. Is this a slow implementation? $\endgroup$
    – Daniel
    Sep 7 at 20:18
  • $\begingroup$ Maybe you want to add a small non-trivial example to your question? $\endgroup$ Sep 7 at 20:18
  • 1
    $\begingroup$ I have cross-checked on my laptop, and indeed LRS on your two test instances is very slow (similar runtime to yours). Maybe you can try to contact the LRS authors, I don't know how to help here. $\endgroup$ Sep 10 at 9:45
  • 1
    $\begingroup$ My experience has been the same (LRS is very slow).. Perhaps I'll try to code the algorithm in this 2001 paper in the Nordic J. of Computing. $\endgroup$ Oct 31 at 1:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.