Use scipy to get any vertex of polytope

Question

I need to get just a random vertex of a polytope. Any will do. The only way I can do this now is to pick a random function (say 0s) to maximize with scipy.optimize.linprog. However, this is wasteful, because I really don't care which vertex I get. I saw something in the docs about getting the internal state of the solver with a callback function, but I don't know enough about the simplex algorithm to understand which paramater I need. How can I just extract the vertex scipy found during Phase 1 and then abort the calculation?

Answer 1

If you use a 0 objective function, then the solver should stop as soon as it encounters a feasible solution (because that solution will be optimal.) If the solver is using a 2-phase primal simplex method it will stop immediately after the first phase and the solution will be a vertex of the polyhedron.

In practice, LP feasibility problems like this really aren't much easier than optimization problems with a nonzero objective. You might be able to adjust the parameters of the solver so that it finds a primal feasible solution more quickly, but that would depend on the details of the solver that you're using.