I need to find a list of all the extreme points of a polytope given by a matrix relation Ax <= b, with x being non-negative. I know that 100% of the time, the polytope is non degenerate. The first solution I used was to generate a random non negative vector and run an LP with the vector being the objective function (so basically; optimizing in a random direction). This of course has many problems: take an insane amount of time and in the end I can't be sure the solution is correct.
Then I tried using the polytope toolbox; with the 'extreme' function. I ran it on an instance I already know well:
import numpy as np
import polytope as pc
A = np.array([[0,1,0,1,0], [0,0,1,0,1], [1,0,0,0,1], [0,1,1,0,0], [1,0,0,0,0]])
K = A - A.transpose()
C = np.vstack( (K, -np.eye(5) , [1]*5)
p = pc.Polytope(C, [0]*10+[1])
print(pc.extreme(p))
The output I expect is (.5, .5, 0, 0, 0), (0, 1/3, 1/3, 1/3, 0) and (0, 0, 0, 0, 0). However, I only get a None. I saw there is an example in the repository on the use of extreme() but I don't see what I did wrong.
On a side note, if you have an other library to recommand that can solve this problem (find extremal points in polyhedras) I'd be happy to take it.
Your question is not clear (cf my comment) but you should use pycddlib. I tried and I got something close to your expectation:
import numpy as np
import cdd as pcdd
A = np.array([[0,1,0,1,0], [0,0,1,0,1], [1,0,0,0,1], [0,1,1,0,0], [1,0,0,0,0]])
K = A - A.transpose()
C = np.vstack( (K, -np.eye(5), [1]*5) )
b = [[0]]*10 + [[1]]
M = np.hstack( (b, -C) )
mat = pcdd.Matrix(M, linear=False, number_type="fraction")
mat.rep_type = pcdd.RepType.INEQUALITY
poly = pcdd.Polyhedron(mat)
ext = poly.get_generators()
print(ext)
which gives:
1 1/3 0 1/3 1/3 0
1 0 0 0 1/2 1/2
1 0 0 0 0 0
A "1" in the first column means the row represents an extreme point.