4
$\begingroup$

If there are many solutions to a linear program s.t. the objective function is minimized/maximized (= optimal solutions are on an edge of the polytope), how can I force an LP solver to find only an extreme point solution?

$\endgroup$
  • 2
    $\begingroup$ Don't they always do so? At least, Simplex does so and I seem to remember that it's "easy" to get to a optimal basic solution from any optimal solution. No need to change the linear program. $\endgroup$ – Raphael Oct 16 '12 at 7:22
3
$\begingroup$

Perturb the vector of the objective function slightly. If you got multiple optimal solutions than this vector is orthogonal to a facet $F$ of the polytope that defines the feasible area of the LP. Notice that $F$ could be an edge, but also a higher dimensional flat. By changing the objective function slightly you will get an extreme point that lies on the boundary of $F$.

You might want to check that the perturbation was small enough. So check the computed point with the original objective function, if it produces the optimum.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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