# Is there a polynomial-time algorithm returning a vertex of the feasible region?

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?

• 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. – user13838 Sep 25 '11 at 14:03
• The set of vertices ($V$) is a subset of the feasible set ($F$). So, what do you want : $V$ or $F$? – Jacob Sep 25 '11 at 15:52
• 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). – Michael Sep 26 '11 at 13:50

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.