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 .

---- 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 . . +INF EPS

seattle .chicago . 300.000 +INF .

seattle .topeka . . +INF 0.036

san-diego.new-york . 325.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

Hope this helps,

Michael Bussieck - GAMSWorld Coordinator

On Sunday, January 3, 2016 at 1:23:48 PM UTC-5, fedperea wrote:

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.