3
$\begingroup$

I have a standard basic linear program. Is there a polynomial-time algorithm that can return a vertex of the polytope that describes the feasible region?

I know that the ellipsoid method can give a feasible solution, but is it possible to obtain a solution that is a vertex?

Improve this question
$\endgroup$
  • $\begingroup$ As far as I understand: The first question asks about the feasibility region which is the intersection of constraints. The second question asks about the optimality criteria and is it always found on one of the vertices. In any case, you might better change the wording of the question. $\endgroup$ – user13838 Sep 25 '11 at 14:03
  • $\begingroup$ The set of vertices ($V$) is a subset of the feasible set ($F$). So, what do you want : $V$ or $F$? $\endgroup$ – Jacob Sep 25 '11 at 15:52
  • $\begingroup$ I'm looking for a vertex in V. The problem is that an optimal solution is not necessary uniquely at the vertex. So, my question is: how to get the vertex (which is of course also the optimal solution). $\endgroup$ – Michael Sep 26 '11 at 13:50
3
$\begingroup$

Yes: in fact, you can find a vertex which gives you the optimal solution in polynomial time using a simple modification of the ellipsoid algorithm. The full proof is a little messy to write down in its entirety; it can be found in this paper by Grotschel, Lovasz, and Schrijver. Below is an outline.

The key insight is that there is a limit to how big the denominators of the of entries of the vertices of the polytope can be. One first obtains an upper bound on these denominators - lets call it $D$ - then uses the ellipsoid algorithm to find a point that is close to optimality, and then one rounds the output of the ellipsoid algorithm to the closest rational point with denominator at most $D$. If there is a unique maximizing vertex, this works. If there isn't, then one first toys around with the objective function to make sure a unique maximizing vertex exists.

Improve this answer
$\endgroup$
  • $\begingroup$ Thank you for the answer. I just can't find the Theorem that states the above result. Could you please direct me to the appropriate part of the paper? Thanks again. $\endgroup$ – Michael Sep 26 '11 at 13:55
  • $\begingroup$ Is it possible that there is no objective function for which only one maximizing vertex exists? How can I obtain some vertex of the polytope if there are many optimal vertices for any objective function? $\endgroup$ – Michael Sep 26 '11 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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