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
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
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.';