$ontext

   A famous difficult to solve fixed-charge transportation model
   Optimal objective : 3712.

   Erwin Kalvelagen, April 2002

   See:
   http://www.in.tu-clausthal.de/~gottlieb/benchmarks/fctp/

$offtext


set i 'sources' /i1*i14/;
set j 'demands' /j1*j18/;

parameter supply(i) /
   i1 21
   i2 19
   i3 24
   i4 10
   i5 27
   i6 25
   i7 10
   i8 16
   i9 17
  i10 38
  i11 22
  i12 33
  i13 22
  i14 26
/;


parameter demand(j) /
   j1  6
   j2 13
   j3 21
   j4 11
   j5 20
   j6  4
   j7 35
   j8 13
   j9 20
  j10  9
  j11  7
  j12 18
  j13 14
  j14 22
  j15 33
  j16 45
  j17 11
  j18  8
/;


table c(i,j) 'variable cost'
       j1    j2    j3    j4    j5    j6    j7    j8    j9   j10   j11   j12
i1    4.0   4.0  10.0   3.0   4.0   9.0  10.0   9.0   3.0  10.0   5.0  10.0
i2    7.0   1.0   7.0   4.0   6.0   7.0   7.0   1.0   4.0   4.0  10.0   1.0
i3   10.0  10.0   4.0  10.0   3.0   2.0   3.0   8.0   3.0   7.0   1.0   5.0
i4    7.0   1.0   1.0   1.0  10.0   1.0   7.0   6.0   6.0   2.0   5.0   5.0
i5    4.0  10.0   2.0   1.0   7.0   8.0   1.0   2.0   4.0   5.0   9.0   2.0
i6    3.0   7.0   4.0  10.0   8.0  10.0   9.0   9.0   6.0   8.0   9.0   5.0
i7    2.0   7.0  10.0  10.0   4.0  10.0   6.0   8.0   6.0   6.0   6.0   8.0
i8    1.0   7.0  10.0   1.0   7.0   3.0   1.0  10.0  10.0   6.0   2.0   9.0
i9   10.0   7.0   4.0   1.0   1.0   1.0   8.0   4.0   4.0   3.0   2.0   4.0
i10   4.0   7.0   1.0   3.0   3.0   1.0   3.0   3.0   5.0   9.0   9.0   2.0
i11   4.0   1.0   1.0   2.0   1.0   4.0   6.0   8.0   2.0   4.0   2.0   5.0
i12   7.0   4.0   1.0   3.0  10.0   3.0   1.0   5.0   2.0   5.0   1.0   5.0
i13   4.0   7.0   1.0  10.0   3.0   8.0   2.0   9.0   9.0   6.0   6.0   9.0
i14   6.0   4.0   8.0   1.0   2.0   3.0   4.0   9.0   9.0   2.0   6.0   2.0

+     j13   j14   j15   j16   j17   j18
i1    9.0  10.0   5.0   8.0   9.0   8.0
i2    7.0   5.0   8.0   3.0   3.0   1.0
i3    5.0   6.0   1.0   8.0   3.0   8.0
i4    7.0   9.0   6.0   3.0   3.0   5.0
i5    8.0   7.0   2.0   8.0   5.0   3.0
i6    5.0   6.0   1.0   4.0   9.0   5.0
i7    2.0   3.0   6.0   9.0   7.0   5.0
i8    1.0   6.0   5.0   8.0   6.0   5.0
i9    6.0   6.0   8.0   3.0   6.0   6.0
i10   6.0   8.0   2.0   4.0   3.0   6.0
i11   5.0   8.0   7.0   4.0   6.0   9.0
i12   6.0   6.0   3.0   9.0   9.0   3.0
i13   7.0   7.0   9.0   1.0   3.0  10.0
i14   5.0   7.0   8.0  10.0  10.0   2.0
;



table f(i,j) 'fixed cost'
        j1     j2     j3     j4     j5     j6     j7     j8   j9      j10
i1   202.0  222.0  100.0  174.0  116.0  253.0  252.0  113.0  261.0  240.0
i2   190.0  158.0  243.0  175.0  191.0  243.0  162.0  251.0  248.0  213.0
i3   229.0  112.0  107.0  193.0  214.0  120.0  154.0  150.0   94.0   74.0
i4   190.0  198.0  130.0  118.0  135.0   91.0  243.0  258.0   98.0   78.0
i5   154.0  217.0  156.0   91.0  233.0  191.0  172.0  157.0  202.0  212.0
i6   141.0  149.0  234.0  230.0  126.0  113.0  101.0  240.0  138.0   87.0
i7   131.0  256.0  147.0  252.0  107.0  112.0  165.0  255.0   71.0  244.0
i8   211.0   85.0  124.0  171.0  139.0  115.0   65.0  253.0  217.0  178.0
i9   147.0  149.0  214.0  105.0  132.0  131.0  202.0  213.0   81.0  234.0
i10  249.0  126.0  145.0  235.0  234.0   92.0  201.0  142.0  106.0  113.0
i11   95.0  251.0  145.0  131.0  130.0  222.0  192.0  179.0  183.0  234.0
i12  109.0  234.0   78.0  115.0  136.0  221.0  252.0  129.0   80.0   94.0
i13  107.0  233.0   91.0  112.0  261.0  150.0  119.0  102.0  207.0  138.0
i14  191.0  154.0  101.0   66.0  156.0  128.0  234.0   75.0   86.0  210.0

+      j11    j12    j13    j14    j15    j16  j17      j18
i1   106.0  146.0   76.0  169.0  247.0  194.0  208.0  242.0
i2   123.0   65.0   73.0  246.0  181.0  132.0   91.0  264.0
i3   104.0  152.0   94.0  258.0  264.0   88.0  262.0  220.0
i4   188.0  129.0  162.0  208.0  110.0  186.0  262.0  223.0
i5   169.0  173.0  150.0   96.0  210.0  194.0  106.0  221.0
i6   242.0  189.0   93.0  204.0  184.0  176.0  148.0  140.0
i7   192.0  168.0  250.0  132.0  177.0  195.0   98.0  105.0
i8   186.0   87.0  119.0  137.0   82.0  208.0  205.0  223.0
i9   226.0  202.0  138.0  245.0  148.0  209.0  177.0  152.0
i10  134.0   90.0  138.0  114.0  239.0  222.0  262.0  205.0
i11  196.0  106.0  200.0  147.0   72.0  176.0  231.0  160.0
i12   65.0  177.0  258.0  137.0  185.0  242.0  181.0  132.0
i13   71.0  122.0  125.0  166.0  168.0  144.0  174.0  241.0
i14  231.0   79.0  105.0  166.0  147.0  171.0  241.0   80.0

;

*
* check supply-demand balance
*
scalar totdemand, totsupply;
totdemand = sum(j, demand(j));
totsupply = sum(i, supply(i));
abort$(abs(totdemand-totsupply)>0.001) "Supply does not equal demand.";

*
* for big-M formulation we need tightest possible upperbounds on x
*
parameter xup(i,j) 'tight upperbounds for x(i,j)';
xup(i,j) = min(supply(i),demand(j));

variables
   cost   'objective variable'
   x(i,j) 'shipments'
   y(i,j) 'on-off indicator for link'
;
positive variable x;
binary variable y;

equations
   obj      'objective'
   cap(i)   'capacity constraint'
   dem(j)   'demand equation'
   xy(i,j)  'x=0 for off links'
;

obj..      cost =e= sum((i,j), f(i,j)*y(i,j) + c(i,j)*x(i,j));
cap(i)..   sum(j, x(i,j)) =e= supply(i);
dem(j)..   sum(i, x(i,j)) =e= demand(j);
xy(i,j)..  x(i,j) =l= xup(i,j)*y(i,j);

option optcr=0;
option iterlim=10000000;
option reslim=3600;

model m /all/;
solve m minimizing cost using mip;