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/ ;

loc.optcr = 0;
loc.optfile = 1;
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

option mip=cplexd;

solve loc min totcost using mip;