3
$\begingroup$

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?

$\endgroup$

closed as off-topic by Alex Degtyarev, Marco Golla, Per Alexandersson, Yoav Kallus, Chris Godsil Aug 22 '15 at 4:04

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Alex Degtyarev, Per Alexandersson
If this question can be reworded to fit the rules in the help center, please edit the question.

3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ I should be a bit clearer - I don't have an objective function, I'm just looking to prune inequalities. Should I just pick a general objective function and repeatedly solve the LP as you described? $\endgroup$ – Nick Sweet Aug 24 '15 at 15:22
  • 1
    $\begingroup$ @Nick Sweet: Notice that the LP I described $\max\{ a^T x : A'x \leq b' \}$ has as objective function the left-hand side of one of the inequalities of the original system ($a^T x \leq \beta$) that you are trying to prune. $\endgroup$ – Fernando Aug 25 '15 at 14:14
  • $\begingroup$ My mistake - I missed that aspect. I do worry that if I have $n$ inequalities, I'll have to solve $n$ LPs, though. $\endgroup$ – Nick Sweet Aug 25 '15 at 20:12
  • $\begingroup$ Well, you already want to find all vertices anyway, so solving $n$ LPs is not that bad. You could think of working with the dual, because then to obtain each LP you have to set a variable to zero and change the right-hand side. A smart solver might use this to save some work... $\endgroup$ – Fernando Aug 27 '15 at 0:11
0
$\begingroup$

The magic words are "Motzkin's double description method"

$\endgroup$

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