I have a polyhedron which is defined by the following system of inequalities:
$$ \left\{ \begin{array}{c} x \leq 2 \\ y \leq 1 \\ x + y + z \leq 1\\ x + y + 2z \leq 1 \end{array} \right. $$ I want to write a general algorithm that can find the vertices of this polyhedron. This is my best solution so far:
0) Get in the form $Ax \leq b$
1) Since it is in $\mathbb{R}^3$, iterate through combinations of 3 rows of A, and see if the rank = 3 for those sub matrices. this tells us that the inequalities intersect.
2) For each of those combinations that have rank = 3, solve the system $A' x=b'$ where $A'$ and $b'$ are truncated versions of $A$ and $b$ just for the combination at hand.
3) Use this solution $x'$ to see if it is inside the polyhedron. If so, then a vertex is found.
I have not seen this process documented anywhere, and it seems to work on the cases i have tried. am I missing anything in this algorithm?
With CAS Maxima and my package "gt" (game theory):
Function "ext" compute extreme points of polyhedron.