cbenders.gms : Cplex Benders for a Simple Facility Location Problem

**Description**

A simple version of a facility location problem is used to show how the Benders decompostion works with Cplex 12.7. The model includes a small example and can be started with a double dash parameter --wmax to set an arbitrary number of warehouses. The remaining set and data items will be computed from this wmax. There are three ways of running Cplex' Benders driving by the BendersStrategy parameters. The lower the BendersStrategy number the more information needs to be provided by the user. Note that the problem can also be solved as an RMIP but since Benders does not provide dual information, the Cplex log will have a few lines that look like errors but can be safely ignored. 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 :** cbenders.gms

```
$Title Cplex Benders for a Simple Facility Location Problem (CBENDERS,SEQ=415)
$Ontext
A simple version of a facility location problem is used to show how the
Benders decompostion works with Cplex 12.7. The model includes a small
example and can be started with a double dash parameter --wmax to set an
arbitrary number of warehouses. The remaining set and data items will be
computed from this wmax.
There are three ways of running Cplex' Benders driving by the BendersStrategy
parameters. The lower the BendersStrategy number the more information needs
to be provided by the user.
Note that the problem can also be solved as an RMIP but since Benders does not
provide dual information, the Cplex log will have a few lines that look like
errors but can be safely ignored.
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.
$offtext
$ifthen not set wmax
Set i warehouses / w1*w4 /
j regions / r1*r9 /
k goods / k1*k3 /
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;
$else
* Generate large random examples
$eval rmax %wmax%*5
$eval kmax round(%wmax%/3)
Set i warehouses / w1*w%wmax% /
j regions / r1*r%rmax% /
k goods / k1*k%kmax% /
Parameters
f(i) fixed costs
c(i) capacity
d(j) demand
t(j,i) transport cost;
f(i) = uniformInt(100,200);
c(i) = uniformInt(200,300);
d(j) = uniformInt(20,60);
t(j,i) = uniformInt(5,100);
$endif
Parameters
ck(i,k), dk(j,k);
ck(i,k) = round(c(i)*uniform(0.5,1.8));
dk(j,k) = round(d(j)*uniform(0.5,1.8));
Variables
totcost total cost
fcost fixed cost
tcost(k) transportation cost
ow(i) indicator for open warehouse
oa(i,j) indicator for open shipment arc warehouse to region
x(i,j,k) shipment of good k for open shipment arc warehouse to region
Binary variables ow, oa;
Positive variable x;
Equations
deftotcost definition total cost
deffcost definition fixed cost
deftcost(k) definition transportation cost
defwcap(i,k) limit utilization of warehouse by its capacity
defwdem(j,k) demand satisfaction in region j for good k
twow(j) only two warehouses per region
defow(i,j) warehouse open if shipment from i to j
defx(i,j,k) shipment only if link open bteween i to j;
deftotcost.. totcost =e= fcost + sum(k, tcost(k));
deffcost.. fcost =e= sum(i, f(i)*ow(i));
deftcost(k).. tcost(k) =e= sum((i,j), t(j,i)*x(i,j,k));
defwcap(i,k).. sum(j, x(i,j,k)) =l= ck(i,k);
defwdem(j,k).. sum(i, x(i,j,k)) =g= dk(j,k);
twow(j).. sum(i, oa(i,j)) =l= 2;
defow(i,j).. ow(i) =g= oa(i,j);
defx(i,j,k).. ck(i,k)*oa(i,j) =g= x(i,j,k);
Model loc /all/ ;
file fopt / cplexd.opt /;
put fopt 'BendersStrategy 1'
/ 'variables.BendersPartition 0'
loop(k, put / "x.BendersPartition(*,*,'" k.tl:0 "') " ord(k):0:0
/ "tcost.BendersPartition('" k.tl:0 "') " ord(k):0:0);
putclose fopt;
$onecho > cplexd.op2
BendersStrategy 2
variables.BendersPartition 0
x.BendersPartition 1
tcost.BendersPartition 1
$offecho
$onecho > cplexd.op3
BendersStrategy 3
$offecho
$onecho > cplexd.op4
BendersPartitionInStage 1
BendersStrategy 1
$offecho
totcost.stage = 0;
fcost.stage = 1;
tcost.stage(k) = ord(k)+1;
x.stage(i,j,k) = ord(k)+1;
option solver=cplexd, optCR=0, limRow=0, limCol=0, solPrint=off, solveLink=%solveLink.loadLibrary%;
scalar cpxOptFile;
for (cpxOptFile=1 to 4,
loc.optfile = cpxOptFile;
solve loc min totcost using mip;
abort$(loc.modelstat<>%modelstat.Optimal%) 'expect model status optimal';
abort$(abs(totcost.l-11661)>1e-6) 'expect objective to be 11661';
);
```