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

GAMS Model

$ontext   Enumerate all optimal LP bases   Use Cplex solution pool $offtext Sets      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.opt SolnPoolAGap = 0.0 SolnPoolIntensity = 4 PopulateLim = 10000 SolnPoolPop = 2 solnpoolmerge 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