decomp.gms : Decomposition Principle - Animated

Description

```The coordinator of a Central Agency must procure tanker services
to assist his distribution. A subcontractor handles all the
shipping details. This scenario is used to demonstrate the
decomposition principle. For details see chapter 23-2 of Dantzig's
original text on Linear Programming.
```

Small Model of Type : LP

Category : GAMS Model library

Main file : decomp.gms

``````\$title Decomposition Principle - Animated (DECOMP,SEQ=164)

\$onText
The coordinator of a Central Agency must procure tanker services
to assist his distribution. A subcontractor handles all the
shipping details. This scenario is used to demonstrate the
decomposition principle. For details see chapter 23-2 of Dantzig's
original text on Linear Programming.

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

Keywords: linear programming, decomposition, distribution problem, transportation
problem, shipping
\$offText

Set
i 'plants'    / plant-1, plant-2 /
j 'terminals' / term-1*term-4    /;

Table c(i,j) 'cost matrix'
term-1  term-2  term-3  term-4
plant-1       3       6       6       5
plant-2       8       1       3       6;

Table t(i,j) 'tankers required'
term-1  term-2  term-3  term-4
plant-1                       2
plant-2               2                ;

Parameter
a(i)   'availability'  / plant-1 9, plant-2 8 /
b(j)   'requirements'  / term-1 2, term-2 7, term-3 3, term-4 5 /
ctank  'tanker cost'
cship  'shipping cost';

Variable
cost   'total cost'
tank   'total tankers used'
ship   'shipping cost'
x(i,j) 'shipments';

Positive Variable x;

Equation
defcost   'cost definition'
defship   'shipping cost'
deftank   'tanker usage'
supply(i) 'supply balance'
demand(j) 'demand balance';

defcost..   cost =e= cship*ship + ctank*tank;

defship..   ship =e= sum((i,j), c(i,j)*x(i,j));

deftank..   tank =e= sum((i,j), t(i,j)*x(i,j));

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

demand(j).. sum(i, x(i,j)) =g= b(j);

Model sub / defcost, defship, deftank, demand, supply /;

Set
ss    'master column labels' / 1*10 /
s(ss) 'active columns';

Parameter
mcost(ss) 'cost solutions'
mtank(ss) 'tanker solutions';

Variable
mobj
lam(ss) 'column selection';

Positive Variable lam;

Equation
cbal   'cost balance'
tbal   'tanker balance'
convex 'combination';

cbal..   mobj =e= sum(s, mcost(s)*lam(s));

tbal..   sum(s, mtank(s)*lam(s)) =l= 9;

convex.. sum(s, lam(s)) =e= 1;

Model master / cbal, tbal, convex /;

Parameter rep(ss,*);

* get first solution with zero cost for tankers
cship = 1;
ctank = 0;

solve sub using lp minimizing cost;
mcost('1') = ship.l;
mtank('1') = tank.l;

* get second solution with zero cost for tankers
option limCol = 0, limRow = 0;

solve sub using lp minimizing tank;
mcost('2') = ship.l;
mtank('2') = tank.l;

* solve first master problem
s('1') = yes;
s('2') = yes;

solve master using lp minimizing mobj;
rep('2','obj')  =  mobj.l;
rep('2','s-pi') =  convex.m;
rep('2','t-pi') = -tbal.m;
rep('2','gap')  =  inf;

* now we are ready to iterate between master and sub problem;
loop(ss\$((not s(ss)) and (rep(ss-1,'gap') > .01)),
ctank = -tbal.m;

solve sub using lp minimizing cost;
mcost(ss) = ship.l;
mtank(ss) = tank.l;
s(ss)     = yes;

solve master using lp minimizing mobj;
rep(ss,'obj')  =  mobj.l;
rep(ss,'s-pi') =  convex.m;
rep(ss,'t-pi') = -tbal.m;
rep(ss,'bnd')  =  rep(ss-1,'obj') - rep(ss-1,'s-pi') + mcost(ss) + mtank(ss)*rep(ss - 1,'t-pi');
rep(ss,'best-bnd') = max(rep(ss - 1,'best-bnd'),rep(ss,'bnd'));
rep(ss,'gap')      = rep(ss,'obj') - rep(ss,'best-bnd');
);

display mcost, mtank, rep;
``````
GAMS Development Corp.
GAMS Software GmbH

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