Detecting multiple solutions gams cplex

Archiver · December 30, 2015, 11:08am

Dear Gams users,

Does any of you how to detect if an lp model has more than one optimal solution in gams? I do not want to store all solutions, like in solution pool, instead I just want to see if there is more than one solution.

Thanks!!

Fede

–
To unsubscribe from this group and stop receiving emails from it, send an email to gamsworld+unsubscribe@googlegroups.com.
To post to this group, send email to gamsworld@googlegroups.com.
Visit this group at https://groups.google.com/group/gamsworld.
For more options, visit https://groups.google.com/d/optout.

Archiver · January 4, 2016, 10:58am

Fede,

Alternative solutions in LP and MIP are very different. You can easily detect that you have a degenerate solution or that alternative solutions exist, but getting them is a different thing. Here is a very nice and short tutorial about degeneracy and alternative solutions: http://ocw.mit.edu/courses/sloan-school-of-management/15-053-optimization-methods-in-management-science-spring-2013/tutorials/MIT15_053S13_tut07.pdf

So for alternate solutions you need a non-basic variable (or slack variable) with reduced cost 0. GAMS marks such items with an EPS in the marginal column. For example, with model library model trnsport (http://gams.com/modlib/libhtml/trnsport.htm) and solved with Cplex you get the following solution listing:

LOWER LEVEL UPPER MARGINAL
---- EQU cost . . . 1.000
cost define objective function

---- EQU supply observe supply limit at plant i
LOWER LEVEL UPPER MARGINAL
seattle -INF 350.000 350.000 EPS
san-diego -INF 550.000 600.000 .

---- EQU demand satisfy demand at market j
LOWER LEVEL UPPER MARGINAL
new-york 325.000 325.000 +INF 0.225
chicago 300.000 300.000 +INF 0.153
topeka 275.000 275.000 +INF 0.126

---- VAR x shipment quantities in cases
LOWER LEVEL UPPER MARGINAL
seattle .new-york . 50.000 +INF .
seattle .chicago . 300.000 +INF .
seattle .topeka . . +INF 0.036
san-diego.new-york . 275.000 +INF .
san-diego.chicago . . +INF 0.009
san-diego.topeka . 275.000 +INF .

LOWER LEVEL UPPER MARGINAL
---- VAR z -INF 153.675 +INF .
z total transportation costs in thousands of dollars

Because of the EPS in equation supply(‘seattle’) you see that you have a non-basic slack variable with reduced cost 0. You can pivot on this (without changing the objective value) and will get a different basis (and in this case) a different point. As I said there is no simple way using a black box LP solver to perform such a pivot step. In our case using a different LP solver gives us (by chance) a different basis (and solution). Here is the solution given by Xpress (where the EPS moved to x(‘seattle’,‘new-york’)):

LOWER LEVEL UPPER MARGINAL
---- EQU cost . . . 1.000
cost define objective function

---- EQU supply observe supply limit at plant i
LOWER LEVEL UPPER MARGINAL
seattle -INF 300.000 350.000 .
san-diego -INF 600.000 600.000 .