solmpool.gms : Cplex Solution Pool for a Simple Facility Location Problem with Merged Solution File

Description

A simple version of a facility location problem is used to show how the
solution pool and the tools associated with it work. This example is taken
from the Cplex 11 User's Manual (ILOG, Cplex 11 User's Manual, 2007)

A company is considering opening as many as four warehouses in order to serve
nine different regions. The goal is to minimize the sum of fixed costs
associated with opening warehouses as well as the various transportation
costs incurred to ship goods from the warehouses to the regions.

Whether or not to open a warehouse is represented by binary variable ow.
Whether or not to ship goods from warehouse i to region j is represented
by binary variable oa.

Each region needs a specified amount of goods, and each warehouse can store
only a limited quantity of goods. In addition, each region must be served
by exactly one warehouse.


Reference

  • ILOG, CPLEX 11 User's Manual, 2007.

Small Model of Type : MIP


Category : GAMS Model library


Main file : solmpool.gms

$Title Cplex Solution Pool for a Simple Facility Location Problem with Merged GDX Solution File (SOLNPOOL,SEQ=394)
$Ontext

A simple version of a facility location problem is used to show how the
solution pool and the tools associated with it work. This example is taken
from the Cplex 11 User's Manual (ILOG, Cplex 11 User's Manual, 2007)

A company is considering opening as many as four warehouses in order to serve
nine different regions. The goal is to minimize the sum of fixed costs
associated with opening warehouses as well as the various transportation
costs incurred to ship goods from the warehouses to the regions.

Whether or not to open a warehouse is represented by binary variable ow.
Whether or not to ship goods from warehouse i to region j is represented
by binary variable oa.

Each region needs a specified amount of goods, and each warehouse can store
only a limited quantity of goods. In addition, each region must be served
by exactly one warehouse.


The following GAMS program demonstrates a number of different
approaches to collecting solution pools. GAMS will store the solutions
in a merged GDX files which can then be further used by other programs
or the same GAMS run. GAMS/Cplex will have the variables with an extra
index as parameters in the merged solution file.

Eight examples are solved in this gams run.


$offtext

Set i    warehouses   / w1*w4 /
    j    regions      / r1*r9 /
Parameters
    f(i) fixed costs  / w1 130, w2 150, w3 170, w4 180 /
    c(i) capacity     / w1  90, w2 110, w3 130, w4 150 /
    d(j) demand       / r1 10, r2 10, r3 12, r4 15, r5 15,
                        r6 15, r7 20, r8 20, r9 30 /;

Table t(j,i) transport costs
        w1   w2   w3   w4
    r1  10   30   25   55
    r2  10   25   25   45
    r3  20   23   30   40
    r4  25   10   26   40
    r5  28   12   20   29
    r6  36   19   16   22
    r7  40   39   22   27
    r8  75   65   55   35
    r9  34   43   41   62;

Variables
    totcost    total cost
    fcost      fixed cost
    tcost      transportation cost
    ow(i)      indicator for open warehouse
    oa(i,j)    indicator for open shipment arc warehouse to region
Binary variables ow, oa;

Equations
    deftotcost definition total cost
    deffcost   definition fixed cost
    deftcost   definition transportation cost
    defwcap(i) limit utilization of warehouse by its capacity
    onew(j)    only one warehouse per region
    defow(i,j) warehouse open if shipment from i to j;

deftotcost.. totcost =e= fcost + tcost;

deffcost..   fcost =e= sum(i, f(i)*ow(i));

deftcost..   tcost =e= sum((i,j), t(j,i)*oa(i,j));

defwcap(i).. sum(j, d(j)*oa(i,j)) =l= c(i);

onew(j)..    sum(i, oa(i,j)) =e= 1;

defow(i,j).. ow(i) =g= oa(i,j);

Model loc /all/ ;


* --- Define sets, parameters and files to hold solutions

Sets soln           possible solutions in the solution pool /soln_loc_p1*soln_loc_p1000/
     solnpool(soln) actual solutions;
Scalar cardsoln     number of solutions in the pool;
Alias (soln,s1,s2), (*,u);
Parameters
    owX(soln,i)    warehouse indicator by solution
    oaX(soln,i,j)  arc indicator by solution
    totcostX(soln) total cost by solution
    tcostX(soln)   transportation cost by solution
    fcostX(soln)   fixed cost by solution
    xcostX(soln,*) cost structure by solution;
files fsoln, fcpx / cplex.opt /;
option limrow=0, limcol=0, optcr=0, mip=cplex;
loc.optfile=1; loc.solprint=%solprint.Quiet%;

* The code to load different solution from gdx files will be used
* several times in this program and we therefore copy it into an include file.
$onecho > readsoln.gms
execute_load 'solnpool.gdx', solnpool=index, oaX=oa, owX=ow, totcostX=totcost, tcostX=tcost, fcostX=fcost;
cardsoln = card(solnpool); display cardsoln;
xcostX(soln,u) = 0;
xcostX(solnpool,'totcost')    = totcostX(solnpool);
xcostX(solnpool,'tcost')      = tcostX(solnpool);
xcostX(solnpool,'fcost')      = fcostX(solnpool);
xcostX(solnpool,'fcost^0.96') = fcostX(solnpool)**0.96;
$offecho


*  1. Collect the incumbents found during the regular optimize procedure
*     The Cplex option 'solnpool' triggers the collection of solutions in
*     the GDX container solnpool.
putclose fcpx 'solnpoolmerge solnpool.gdx';
solve loc min totcost using mip;
$include readsoln
display xcostX;


*  2. Use the populate procedure instead of regular optimize procedure (option
*     'solnpoolpop 2'). By default we will generate 20 solutions determined by
*     the default of option populatelim. This is a simple model which is quickly
*     solved with heuristics and cuts, so we need to let Cplex retain sufficient
*     exploration space to find alternative solutions. This is done with option
*     'solnpoolintensity 4'. With solutions where the optimal solution can not 
*     so quickly be found, the default for this option should be suffict.
putclose fcpx 'solnpoolmerge solnpool.gdx' / 'solnpoolintensity 4' / 'solnpoolpop 2';
solve loc min totcost using mip;
$include readsoln
display xcostX;

*  3. Now it gets more complicated. After the first call to populate we instruct
*     the GAMS/Cplex link to execute a GAMS program 'simple.gms' that decides if
*     the populate procedure should be called again. Moreover, we will instruct
*     Cplex to delete the solution 11 to 15 from the pool. After this two rounds
*     we will have 35 solutions in the pool. Note the use of %ncall% which expands
*     to an integer counting the number of previous execution of 'simple.gms'.
*     A nonzero return code of the gams run called by Cplex will signal to
*     Cplex that this is was the final call.
putclose fcpx 'solnpoolmerge solnpool.gdx' / 'solnpoolintensity 4' / 'solnpoolpop 2'
            / 'solnpoolpoprepeat simple.gms'
            / 'solnpoolpopdel delsol.txt';
$onechoV > simple.gms
$ife %ncalls%>0 abort 'Terminate search'
file f /delsol.txt/; put f '11 12 13 14 15';
$offecho
solve loc min totcost using mip;
$include readsoln
abort$(cardsoln <> 35) 'Expected to get 35 solutions';
display xcostX;


*  4. Next we call the populate procedure, but we want solutions that are
*     within 3% of the optimum. If we find more than 20, we are willing to
*     call the populate procedure once more. It turns out that there are 11
*     solutions of this quality, so no need to call populate again.
putclose fcpx 'solnpoolmerge solnpool.gdx' / 'solnpoolintensity 4' / 'solnpoolpop 2'
            / 'solnpoolpoprepeat simple.gms'
            / 'solnpoolgap 0.03';
solve loc min totcost using mip;
$include readsoln
display xcostX;


*  5. Lets look at the diversity of the solution by counting the differences
*     between the shipment indicator variables. Lets limit the number of
*     solutions in the pool by 10 and require solution within 10% of the
*     optimum.
putclose fcpx 'solnpoolmerge solnpool.gdx' / 'solnpoolintensity 4' / 'solnpoolpop 2'
            / 'solnpoolcapacity 10'        / 'solnpoolgap 0.1';
solve loc min totcost using mip;
$include readsoln
Scalar aggdiff aggregated differences /0/;
loop((s1,s2)$(not sameas(s1,s2) and solnpool(s1) and solnpool(s2)),
   aggdiff = aggdiff + sum((i,j), oaX(s1,i,j) xor oaX(s2,i,j));
); display aggdiff;


*  6. We repeat the experiment by now setting the solution pool replacement
*     strategy to 'diversity' and let the populate procedure find many more
*     solutions, we should see an increase in the aggregated difference
putclose fcpx 'solnpoolmerge solnpool.gdx' / 'solnpoolintensity 4' / 'solnpoolpop 2'
            / 'solnpoolcapacity 10'        / 'solnpoolgap 0.1'
            / 'populatelim 10000'          / 'solnpoolreplace 2';
solve loc min totcost using mip;
$include readsoln
Scalar aggdiffX aggregated differences /0/;
loop((s1,s2)$(not sameas(s1,s2) and solnpool(s1) and solnpool(s2)),
  aggdiffX = aggdiffX + sum((i,j), oaX(s1,i,j) xor oaX(s2,i,j));
); display aggdiffX;
abort$(aggdiffX < aggdiff) 'We expected *more* diversity';

*  7. We can fine tune diversity by using a diversity filter. Suppose that
*     facilities w1 and w2 are open. Let a solution keeping those two facilities
*     open be the reference. We use a diversity filter to stipulate that any
*     solution added to the solution pool must differ from the reference by
*     decisions to open or close at least two other facilities. The following
*     filter enforces this diversity by specifying a minimum diversity of 2.
*     Note that the reference solution becomes the incumbent and is reported as
*     the first solution in the pool.
put fcpx 'solnpoolmerge solnpool.gdx' / 'solnpoolintensity 4' / 'solnpoolpop 2'
       / 'divfltlo 2'                 / 'writeflt ow2.flt';
parameter owrefsol(i) / w1 1, w2 1, w3 0, w4 0 /;
loop(i, put / 'ow.divflt("' i.tl:0 '") ' owrefsol(i):0:0); putclose fcpx;
solve loc min totcost using mip;
$include readsoln
display owX;
loop(solnpool(soln)$(ord(soln)>1),
  abort$(sum(i,abs(owX(soln,i) - owrefsol(i)))<2) 'solution differs to little');


*  8. We can also implement more complicated filters using the incumbent filter.
*     For example, we want to enforce that transportation cost is less than
*     fixedcost**0.96. The incumbent filter is implemented as part of the BCH
*     facility (http://www.gams.com/docs/bch.htm). Whenever a new incumbent is
*     found by Cplex, Cplex will run the GAMS program 'incbflt'. The incumbent
*     is provided in a GDX container called 'bchout_i'. The GAMS program can
*     inspect and decide if the incumbent should be accepted or rejected by
*     Cplex. A nonzero return code of the gams run called by Cplex will signal
*     to Cplex that the incumbent is accecpted.

putclose fcpx 'solnpoolmerge solnpool.gdx' / 'solnpoolintensity 4' / 'solnpoolpop 2'
            / 'userincbcall incbflt.gms';
$onecho > incbflt.gms
variables tcost, fcost;
$gdxin bchout_i
$load tcost fcost
abort$(tcost.l < fcost.l**0.96) 'Accept';
$offecho
solve loc min totcost using mip;
$include readsoln
display xcostX;
loop(solnpool(soln),
  abort$(xcostX(soln,'tcost')>=xcostX(soln,'fcost')) 'tcost too big');


*  9. We might sometimes want to order the solutions, for example, best
*     to worst. For this we can use the gdxrank utility. Note that gdxrank
*     returns the sorted indices.

putclose fcpx 'solnpoolmerge solnpool.gdx' / 'solnpoolintensity 4' / 'solnpoolpop 2';
solve loc min totcost using mip;
$include readsoln

Parameter
   uval(soln) unsorted objective values
   idx(soln) sorted index position;

uval(soln)=xcostX(soln,'totcost');

* sort solutions via gdxrank
$libinclude rank uval solnpool idx
file fsorted / 'sorted.txt' /; put fsorted 'Sorted solutions:';

* Get the best five in a file
loop(solnpool(soln),
  if (idx(soln) <= 5,
     put #(idx(soln)+1) @1 soln.tl:0 ':' @10 uval(soln)
  );
);
putclose;

* Get all solutions sorted in a new parameter
parameter sval(soln) sorted objective values;
sval(soln + (idx(soln)- Ord(soln)))$solnpool(soln) = uval(soln);
display sval;