## Saturday, January 2, 2016

### Finding all optimal LP solutions using the Cplex Solution Pool

In http://yetanothermathprogrammingconsultant.blogspot.com/2016/01/finding-all-optimal-lp-solutions.html a MIP formulation was presented to enumerate all optimal LP bases. A loop construct was used to find new basic feasible solutions. To top things off a cutting plane technique was implemented to prevent rediscovering solutions we already knew about.

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 xi,j followed by the slacks si and sj. The last row is the objective z. The second part reports the basis status. This table has first the decision variables xi,j followed by the slacks si and sj. Remember that a 1 indicates ‘basic’.

#### GAMS Model

 \$ontext  Enumerate all optimal LP bases  Use Cplex solution pool\$offtextSets     k                       /seattle, san-diego, new-york, chicago, topeka/     i(k)   canning plants   / seattle, san-diego /     j(k)   markets          / new-york, chicago, topeka /;Parameters     a(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 miles                  new-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 ;Scalars     nb  '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;Variables     x(i,j)  shipment quantities in cases     z       total transportation costs in thousands of dollars     s(k)       'slacks'     beta(*,*)  'basis';Positive Variable x,s;Binary Variable beta;Equations     cost        define objective function     supply(i)   observe supply limit at plant i     demand(j)   satisfy demand at market j     basisx(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.optSolnPoolAGap = 0.0SolnPoolIntensity = 4PopulateLim = 10000SolnPoolPop = 2solnpoolmerge solutions.gdx\$offechotransport.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