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

$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:

image

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