$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;