Has anyone developed a technique to generate a polytope given (possibly redundant) inequality constraints? I've found a few papers that deal with removing redundant inequality constraints for linear programs, but I'm just trying to find the vertices for a feasible region, given a set of inequality constraints.
For instance, if I have:
$$
0x_1  + x_2 \leq -1\\
0x_1  - x_2 \leq -1\\
-x_1  + 0x_2 \leq -2\\
x_1  + 0x_2 \leq -2
$$
I'd like to generate a 2x1 rectangle. But, I also want to be able to handle the situation where I have, for instance:
$$
0x_1  + x_2 \leq -1\\
0x_1  - x_2 \leq -1\\
-x_1  + 0x_2 \leq -2\\
x_1  + 0x_2 \leq -2\\
x_1  + 0x_2 \leq -6
$$
Where the last constraint is clearly redundant. 
I haven't been able to find much in my paper search - any suggestions?
 A: Suppose you have a system $Ax \leq b$, where $A$ is $m \times n$. Suppose also that $A$ has rank $n$, otherwise the feasible region has no vertices. To find all vertices, all you have to do is consider all subsets $I \subseteq \{ 1, \ldots, m \}$ with $n$ elements. Each such set $I$ gives a subsystem of $Ax \leq b$, lets call it $A_I x \leq b_I$, consisting of those rows with indices in $I$. Notice $A_I$ is a square $n \times n$ matrix; if it is nonsingular, then you can find $x_0$ such that $A_I x_0 = b_I$. Now, if $A x_0 \leq b$, then $x_0$ is a vertex of your polyhedron, and every vertex can be generated thus.
Notice this is independent of whether your system has redundancy or not. Of course, if you have a redundant system, then the above brute-force algorithm will take longer to run for no good reason.
To identify redundant inequalities, you can do as follows. You start with your full system $Ax \leq b$, and you pick some inequality $a^T x \leq \beta$ from it. Then you remove $a^T x \leq \beta$ from the system, obtaining the system $A'x \leq b'$. Then you solve the linear programming problem $\max\{ a^T x : A'x \leq b' \}$. If the optimal value is greater than $\beta$, then the inequality you removed was not redundant. If the optimal value is $\leq \beta$, then the inequality was redundant, and you can repeat the procedure with the smaller system by picking a new inequality, etc.
To solve an LP like the one above, you can use standard software like GLPK, which is freely available and can be called from C, C++, Python, etc.
Also take a look at the Sage (http://sagemath.org) mathematics software, which has tools to compute vertices of polyhedra given an inequality description (try the Polyhedron class, it is very easy to use!). Take a look also at polymake (http://www.polymake.org).
Hope this helps!
A: The magic words are "Motzkin's double description method"
