trnssdp.gms : Solving the Transportation LP Problem using SDP

Description

```This problem finds a least cost shipping schedule that meets
requirements at markets and supplies at factories. The semidefinite
programming solver CSDP is used instead of traditional LP algorithm.
The communication with CSDP requires the setup of matrix data
structures. In a sense this GAMS model functions as a matrix generator.
```

Small Model of Type : GAMS

Category : GAMS Model library

Main file : trnssdp.gms   includes :  runcsdp.inc

``````\$title Solving the Transportation LP Problem using SDP (TRNSSDP,SEQ=340)

\$onText
This problem finds a least cost shipping schedule that meets
requirements at markets and supplies at factories. The semidefinite
programming solver CSDP is used instead of traditional LP algorithm.
The communication with CSDP requires the setup of matrix data
structures. In a sense this GAMS model functions as a matrix generator.

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

This formulation is described in detail in:
Rosenthal, R E, Chapter 2: A GAMS Tutorial. In GAMS: A User's Guide.
The Scientific Press, Redwood City, California, 1988.

The line numbers will not match those in the book because of these

Keywords: linear programming, transportation problem, scheduling, semidefinite
programming
\$offText

\$eolCom //

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

Parameter
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 freight 'freight in dollars per case per thousand miles' / 90 /;

Parameter cost(i,j) 'transport cost in thousands of dollars per case';
cost(i,j) = freight*d(i,j)/1000;

\$onText
maximize   -sum((i,j), c(i,j)*x(i,j))
s.t.
supply(i).. sum(j, x(i,j)) =l=  a(i)
demand(j).. sum(i, x(i,j)) =g=  b(j)
\$offText

\$eval imax card(i)
\$eval jmax card(j)
\$eval xmax %imax%*%jmax%

Set
n 'SDP variable space' / x1*x%xmax% /
m 'SDP constraints'    / #i,#j      /
mi(m)                  / #i         /
mj(m)                  /    #j      /
nmap(n,i,j)            / #n:(#i.#j) /;

Parameter
mLE(m)   'SDP constraints with =l='
mGE(m)   'SDP constraints with =g='
c(m)     'right hand side'
F0(n,n)  'cost coefficients'
F(m,n,n) 'constraint matrix'
Y(n,n)   'primal solution to transport problem'
xvec(m)  'dual solution to transport problem';

* Objective
F0(n,n)    = -sum(nmap(n,i,j), cost(i,j));

* supply
F(mi,n,n)  = sum(nmap(n,i,j)\$sameas(mi,i), 1);
c(mi)      = sum(i\$sameas(mi,i), a(i));
mLE(mi)    = yes;

* demand
F(mj,n,n)  = sum(nmap(n,i,j)\$sameas(mj,j), 1);
c(mj)      = sum(j\$sameas(mj,j), b(j));
mGE(mj)    = yes;

execute_unload 'csdpin.gdx' n, m, mLE, mGE, c, F, F0;
execute 'gams runcsdp.inc lo=%gams.lo% --strict=1';
abort\$errorLevel 'Problems running RunCSDP. Check listing file for details.';

execute_load 'csdpout.gdx', xvec, Y;

Parameter rep;
rep('ship', i, j)  = sum(nmap(n,i,j), Y(n,n));
rep('price',j,'')  = sum(mj\$sameas(mj,j), -xvec(mj));
rep('obj'  ,'','') = sum((i,j), cost(i,j)*rep('ship', i, j));
display rep;
``````
GAMS Development Corp.
GAMS Software GmbH

General Information and Sales
U.S. (+1) 202 342-0180
Europe: (+49) 221 949-9170