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.



Linear programming - uniqueness of optimal solution
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.


