Here we show a GAMS model that uses the Cplex solution pool. This is a somewhat esoteric option in Cplex. For a discussion of this option see: http://orinanobworld.blogspot.com/2013/01/finding-all-mip-optima-cplex-solution.html. Using this technique will simplify the process as we now only have a single solve. The solution looks very similar. The only thing that is different is the order of the solutions.

Solutions found with Cplex solution pool technology |

The table has the same layout as the one in the earlier post. The first part shows the values. First we have the values for the decision variables *x _{i,j}* followed by the slacks

*s*and

_{i}*s*. The last row is the objective

_{j}*z*. The second part reports the basis status. This table has first the decision variables

*x*followed by the slacks

_{i,j}*s*and

_{i}*s*. Remember that a 1 indicates ‘basic’.

_{j}#### GAMS Model

$ontext $offtext Setsk /seattle, san-diego, new-york, chicago, topeka/ i(k) canning plants / seattle, san-diego /j(k) markets / new-york, chicago, topeka /; Parametersa(i) capacity of plant i in cases/ seattle 350 san-diego 600 / b(j) demand at market j in cases/ new-york 325 chicago 300 topeka 275 / ; Table d(i,j) distance in thousands of milesnew-york chicago topeka seattle 2.5 1.7 1.8 san-diego 2.5 1.8 1.4 ; Scalar f freight in dollars per case per thousand miles /90/ ;Parameter c(i,j) transport cost in thousands of dollars per case ;c(i,j) = f * d(i,j) / 1000 ; Scalarsnb 'number of basic variables'nnb 'number of non-basic variables'; nb = card(i)+card(j);nnb = card(i)*card(j);parameter Mx(i,j), Mk(k);Mx(i,j) = min(a(i),b(j)); Mk(i) = a(i); Mk(j) = b(j); set bs(*,*);bs(i,j)= yes;bs('-',k) = yes;Variablesx(i,j) shipment quantities in casesz total transportation costs in thousands of dollarss(k) 'slacks'beta(*,*) 'basis'; Positive Variable x,s;Binary Variable beta;Equationscost define objective functionsupply(i) observe supply limit at plant idemand(j) satisfy demand at market jbasisx(i,j) 'x=nb => x=0'basiss(k) 's=nb => s=0'basis 'basis accounting'; cost .. z =e= sum((i,j), c(i,j)*x(i,j)) ;supply(i) .. sum(j, x(i,j)) + s(i) =e= a(i) ;demand(j) .. sum(i, x(i,j)) - s(j) =e= b(j) ;basis.. sum(bs,beta(bs)) =e= nb;basisx(i,j).. x(i,j) =l= Mx(i,j)*beta(i,j); basiss(k).. s(k) =l= Mk(k)*beta('-',k); Model transport /all/ ;option optcr=0;option mip=cplex;$onecho > cplex.opt SolnPoolAGap = 0.0SolnPoolIntensity = 4PopulateLim = 10000SolnPoolPop = 2solnpoolmerge solutions.gdx$offecho transport.optfile=1; Solve transport using mip minimizing z ; |

Note: the solutions will be written to the GDX file **solutions.gdx**.

##### Performance

The Cplex solution pool shows some amazing performance. To test this we duplicate the above model tenfold by adding an index to all variables and equations. Essentially we create a staircase model:

In our version we have 10 of those blocks and they are all identical. This gives us a model with many, many optimal bases. We set a limit of 10k solutions (**PopulateLim**). To find all these 10x models takes just 23 seconds (total turnaround time of the whole GAMS job).

##### Reference

Emilie Danna, Mary Fenelon, Zonghao Gu, Roland Wunderling, “*Generating Multiple Solutions for Mixed Integer Programming Problems,*" Proceedings IPCO '07 Proceedings of the 12th international conference on Integer Programming and Combinatorial Optimization, Pages 280 - 294, Springer, 2007