0
$\begingroup$

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

  • 0
    Here is an example of a problem with multiple solutions from the book Linear Programming Methods and Applications: http://books.google.ca/books?id=QpAxEnViv_kC&pg=PA31&lpg=PA31&dq=%22linear+programming%22+%22multiple+optimal+solutions%22&source=bl&ots=wd-WJj25SS&sig=vgZF2Fg7B_X6k8ZQ8_4XRq3HASE&hl=en&sa=X&ei=JkhNUIXOLsn-4QSth4Eg&ved=0CDEQ6AEwAA#v=onepage&q=%22linear%20programming%22%20%22multiple%20optimal%20solutions%22&f=false2012-09-10

1 Answers 1

2

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.