# Formulating a linear program s.t. only extreme point solutions are found

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?

• 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.
– Raphael
Oct 16 '12 at 7:22

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$.