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.

Keywords: mixed integer linear programming, Benders decomposition, facility
          location problem

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.

Keywords: mixed integer linear programming, Benders decomposition, facility
          location problem
$offText

$ifThen not set wmax
   Set
      i 'warehouses' / w1*w4 /
      j 'regions'    / r1*r9 /
      k 'goods'      / k1*k3 /;

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

   Parameter
      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

Parameter 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));

Variable
   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   Variable ow, oa;
Positive Variable x;

Equation
   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 / cplex.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 > cplex.op2
BendersStrategy 2
variables.BendersPartition 0
x.BendersPartition 1
tcost.BendersPartition 1
$offEcho

$onEcho > cplex.op3
BendersStrategy 3
$offEcho

$onEcho > cplex.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 = cplex, optCr = 0, limRow = 0, limCol = 0, solPrint = off, solveLink = %solveLink.loadLibrary%;

Scalar cpxOptFile;
for(cpxOptFile = 1 to 4,
   loc.optFile = cpxOptFile;
   solve loc minimizing totcost using mip;
   abort$(loc.modelStat <> %modelStat.optimal%) 'expect model status optimal';
   abort$(abs(totcost.l - 11661) > 1e-6) 'expect objective to be 11661';
);

* solve again with SCIP while passing on decomposition info
option solver = scip;
loc.optfile = 0;
* starting with the optimal solution is too easy
x.l(i,j,k) = 0;
solve loc minimizing totcost using mip;
abort$(loc.modelStat <> %modelStat.optimal%) 'expect model status optimal';
abort$(abs(totcost.l - 11661) > 1e-6) 'expect objective to be 11661';