How to know if my LP has alternative optimal solution?

[yyu]

Hi,

I am just wondering if there is a way to detect the existence of
alternative optimal solution for LP. I don't have to enumerate it, so
I think AMPL supposes to have a simply way to check it.

Thanks a lot!


Regards,

Yang

[edadk]

Hi

It is not really the job of AMPL to tell whether an LP has alternative
solutions. That is something you need an algorithm for.
Sensitivity analysis can help you answer the question. I suggest you
read about sensitivity analysis in your favorite classical LP text
book.
Some optimizers such as MOSEK that I know can provide sensitivity
information in AMPL.

[Robert Fourer]

For the simple case in which all variables have zero lower bound and no
upper bound, and an optimal basic solution is known, there are a few things
one can say. If all reduced costs are strictly positive, then the optimal
solution is unique. If any reduced cost is zero and all basic variables are
strictly positive, then there does exist an alternative optimal basic
solution.

Also if you run an interior-point method (without a crossover to a basic
solution at the end) and the optimal solution has more positive variables
than constraints, you can conclude that there exist alternative optimal
solutions.

In general, due to degeneracy in the solution it's not possible to determine
whether there are alternative optimal solutions, without doing some
nontrivial computations, which are not automatically performed by any
solver. Also the rules are a little more complicated when there are general
lower and upper bounds on the variables.

Bob Fourer
4...@ampl.com