3
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.