How to enumerate all vertices of a polyhedron as a stream

Question

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.

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? — prubin, Aug 29 '22 at 15:06
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. — Daniel, Aug 29 '22 at 20:10
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. — dozgunay, Aug 30 '22 at 17:45
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 — Daniel, Aug 31 '22 at 18:57
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". — Shuxue Jiaoshou, Nov 06 '22 at 23:03

Stefano Gualandi · Accepted Answer · 2022-09-05T20:42:05.633

2

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:

Reverse Search: Origins

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).

edited Sep 05 '22 at 20:42

answered Sep 05 '22 at 20:32

Stefano Gualandi

1,750
1
13
26

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. – Stefano Gualandi Sep 07 '22 at 20:17
2

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? – Daniel Sep 07 '22 at 20:18
Maybe you want to add a small non-trivial example to your question? – Stefano Gualandi Sep 07 '22 at 20:18
1

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. – Stefano Gualandi Sep 10 '22 at 09:45
1

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. – Shuxue Jiaoshou Oct 31 '22 at 01:33

How to enumerate all vertices of a polyhedron as a stream

1 Answers1