$Title Cplex Solution Pool for a Simple Facility Location Problem (SOLNPOOL,SEQ=326)
$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 individual solutions in GDX
containers/files which can then be further used by other programs or the same
GAMS run. Cplex will name these GDX containers 'soln_loc_pNN.gdx', where NN
will be the serial number of the solution found. To manage the different
solutions, the names of the GDX containers created by Cplex will be stored
in solnpool.gdx in the set 'index' using the set elements 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 /file1*file1000/
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
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%; loc.savepoint = 1;
* 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;
cardsoln = card(solnpool); display cardsoln;
oaX(soln,i,j) = 0; owX(soln,i) = 0; xcostX(soln,u) = 0;
loop(solnpool(soln),
put_utility fsoln 'gdxin' / solnpool.te(soln);
execute_loadpoint;
oaX(soln,i,j) = round(oa.l(i,j));
owX(soln,i) = round(ow.l(i));
xcostX(soln,'totcost') = totcost.l;
xcostX(soln,'tcost') = tcost.l;
xcostX(soln,'fcost') = fcost.l;
xcostX(soln,'fcost^0.96') = fcost.l**0.96;
);
* Restore the solution reported to GAMS
execute_loadpoint 'loc_p.gdx';
$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 'solnpool 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.
putclose fcpx 'solnpool solnpool.gdx' / '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 'solnpool solnpool.gdx' / '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. The option
* solnpoolintensity instructs Cplex in the populate procedure to look with
* different intensity for solutions. Value 4 means to look for all
* solutions with the desired gap.
putclose fcpx 'solnpool solnpool.gdx' / 'solnpoolpop 2'
/ 'solnpoolintensity 4' / '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 'solnpool solnpool.gdx' / '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 'solnpool solnpool.gdx' / '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 'solnpool solnpool.gdx' / '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 'solnpool solnpool.gdx' / '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');
