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?

  • 0
    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).2011-09-26

1 Answers 1

2

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.

  • 0
    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?2011-09-26