Description

Dantzig's original transportation model TRNSPORT (in GAMS Model Library) is
reformulated using EMP's bilevel programming.

Dantzig, G B, Chapter 3.3. In Linear Programming and Extensions.
Princeton University Press, Princeton, New Jersey, 1963.

Additional features:
  The fixed demand b(j) is replaced by a function:
    g(j) = max(b(j),y(j))
  with an outer objective function that tries to force y to be close to a
  target value (400). The max function is modeled using Variational Inequalties.

  The original trnsport model is the lower level problem.

Contributor: Michael Ferris, December 2009

Small Model of Type : BP

Category : GAMS EMP library

Main file : transbp.gms

$title Transportation model with variable demand function using bilevel programming (TRANSBP,SEQ=26)

$onText
Dantzig's original transportation model TRNSPORT (in GAMS Model Library) is
reformulated using EMP's bilevel programming.

Dantzig, G B, Chapter 3.3. In Linear Programming and Extensions.
Princeton University Press, Princeton, New Jersey, 1963.

Additional features:
  The fixed demand b(j) is replaced by a function:
    g(j) = max(b(j),y(j))
  with an outer objective function that tries to force y to be close to a
  target value (400). The max function is modeled using Variational Inequalties.

  The original trnsport model is the lower level problem.

Contributor: Michael Ferris, December 2009
$offText

Parameter report(*,*,*)  summary report;

Sets
     i   canning plants   / seattle, san-diego /
     j   markets          / new-york, chicago, topeka / ;

Parameters

     a(i)  capacity of plant i in cases
       /    seattle     350
            san-diego   600  /

     b(j)  demand at market j in cases
       /    new-york    325
            chicago     300
            topeka      275  / ;

Table d(i,j)  distance in thousands of miles
                  new-york       chicago      topeka
    seattle          2.5           1.7          1.8
    san-diego        2.5           1.8          1.4  ;

Scalar f  freight in dollars per case per thousand miles  /90/ ;

Parameter c(i,j)  transport cost in thousands of dollars per case ;

          c(i,j) = f * d(i,j) / 1000 ;

Variables
     x(i,j)  shipment quantities in cases
     z       total transportation costs in thousands of dollars
     g(j)    generated demand;

Positive Variable x ;

Equations
     cost        define objective function
     supply(i)   observe supply limit at plant i
     demand(j)   satisfy demand at market j ;

cost ..        z  =e=  sum((i,j), c(i,j)*x(i,j)) ;

supply(i) ..   sum(j, x(i,j))  =l=  a(i) ;

* --- Note: the fixed the demand b(j) was replaced by a variable demand g(j)
demand(j) ..   sum(i, x(i,j))  =g=  g(j) ;

Model transport /all/ ;

* --- Now we solve the original fixed price trnsport model
g.fx(j) = b(j);
Solve transport using lp minimizing z ;
report(i,j,'fixed') = x.l(i,j);

Variables
     obj,
     y(j) 'external demand function';

Equation
     outerobj,
     extdem(j);

outerobj..  obj =e= sum(j, sqr((y(j) - 400)/b(j)));

extdem(j).. g(j) =g= y(j);

model emp bilevel trnsport model / all /;

g.up(j) = inf;  g.lo(j) = b(j);

* use the EMP info file to define the model
file fx / '%emp.info%' /;
put fx   'bilevel y' /;
put      ' min z x cost supply demand' /;
putclose ' vi extdem g' /;

* --- Now we solve the bilevel trnsport model using EMP
solve emp us emp min obj;
report(i,j,"bilevel")        = x.l(i,j);

Display report;