Linear programming - uniqueness of optimal solution Is it possible to build such an objective function for a given set of constraints, so that there will be only one optimal solution?
My general problem is to get any vertex of a polytope formed by a set of given linear constraints. I need this in polynomial time.
If I use the ellipsoid method, I'll get an optimal solution for any objective function in polynomial time, BUT, this solution won't be necessary a vertex.
 A: A random objective will work. I don't think there is any (cheap) deterministic way of doing this. On the other hand, I don't really understand your issue with the ellipsoid method. Your solution will be on a lower-dimensional face of your polytope, so iterating your ellipsoid method at most $d$ times you will get a vertex, so you stay polynomial.
A: It you add a quadratic perturbation to the linear objective, then you will end up getting a unique solution. This idea is described more rigorously in Normal solutions of linear programs
In a nutshell, say the objective function is $c^Tx$. To this we add $\epsilon x^Tx$ as the perturbation, then (here comes the catch), for small enough $\epsilon$, the perturbed problem solves the original problem. In fact, from among all the solutions to the original LP, the perturbed problem picks one of smallest $\ell_2$-norm.
A: You can still use simplex algorithm. More precisely, its phase I produces a vertex by solving another linear programming problem by simplex algorithm (but there an initial solution is trivial).
Of course, worst-case complexity of simplex algorithm is exponential but it is polynomial on average and you should be unlucky to encounter the worst case.
