Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a (generalized) Linear Programming problem to solve. I anticipate exactly two equally valid optimizations of my objective function. I would be happy if I could receive both these points; it wouldn't be hard to figure out which one I really want. My question: can standard Linear Programming algorithms be modified to return both points instead of just one? Do they sacrifice their polynomial runtime to do so?

And for extra credit: how, exactly, would we modify these algorithms?

Edit: made the title more relevant to the question

share|improve this question
    
Here is an example of a problem with multiple solutions from the book Linear Programming Methods and Applications: books.google.ca/… –  Emmad Kareem Sep 10 '12 at 1:58

1 Answer 1

up vote 2 down vote accepted

For a linear programming problem, the set of optima is always a convex polyhedron. Therefore, if there are two optimal solutions, then the line segment connecting these solutions is also optimal. I am therefore a bit surprised to read that you expect exactly two optima.

In general, if there are multiple solutions, there is no telling which one will be found. If there is more than one and you want to find all the corner solutions, you could perturb the objective function (randomly, just a little). This should give you corner solutions of the original problem, with probability 1.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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