Description
Given N balls out of which n1 are of color 1, n2 are of color 2, ... nk are of color k, find an assignment of the N balls to N ordered slots such that balls of any one color are as much evenly spaced as possible. The paper by Bollapragada, Bussieck and Mallik lists 25 examples. Use the command line option --curid n to select the nth example. If --curid is missing we select problem number 12. Adding the option --sparse 1 creates a sparse flow graph which might result in an approximate solution only. More information on this problem can be found at http://www.gams.com/~bussieck/isci
Large Model of Type : MIP
Category : GAMS Model library
Main file : tvcsched.gms
$title Flow Formulation of the ISCI Rotator Problem (TVCSCHED,SEQ=247)
$onText
Given N balls out of which n1 are of color 1, n2 are of color 2, ...
nk are of color k, find an assignment of the N balls to N ordered
slots such that balls of any one color are as much evenly spaced as
possible.
The paper by Bollapragada, Bussieck and Mallik lists 25 examples. Use the
command line option --curid n to select the nth example. If --curid is
missing we select problem number 12.
Adding the option --sparse 1 creates a sparse flow graph which might
result in an approximate solution only.
More information on this problem can be found at http://www.gams.com/~bussieck/isci
Bollapragada, S, Bussieck, M.R., and Mallik, S, Scheduling Commercial
Videotapes in Broadcast Television. Operations Research, 2003
Bollapragada, S, Cheng, H, Phillips, M, and Garbiras, M,
NBC's Optimization Systems Increase Its Revenues and Productivity.
Interfaces 31, 1 (2002).
Keywords: mixed integer linear programming, assignment problem, scheduling
commercial videotapes, broadcast television
$offText
$if not set curid $set curid 12
Set
sp 'slots plus initial' / 0*100 /
s(sp) 'slots'
c 'colors' / R 'red', B 'blue', W 'white', G 'green', Y 'yellow' /
id 'test set id' / 1*25 /;
Table idc(id,c) 'number of colors'
R B W G Y
1 5 3
2 4 2 2
3 5 3 2
4 6 3 2
5 6 4 2
6 4 3 3 2
7 6 4 4
8 6 5 4
9 8 3 3 2
10 7 6 4
11 8 7 5
12 8 7 3 2
13 5 5 5 4 1
14 8 6 6 5
15 7 6 5 4 3
16 10 8 7 5
17 9 7 6 5 3
18 17 10 8 5
19 16 15 14
20 25 13 12
21 21 16 13
22 26 12 10 2
23 25 23 12
24 27 25 14 9
25 33 25 21 15 6;
Set preplace(id,sp,c) 'preplaced balls'
/ 1. (6.B, 8.R)
2. (1.R, 2.B, 3.W)
3. (1.B, 2.W)
4. (1.B, 5.W, 6.B)
5. (1.R, 3.B)
6. (2.R, 3.R, 4.B, 6.W)
7. (1.R, 6.B, 14.W)
8. (1.B, 4.W, 7.R)
9. (1.R, 3.W, 5.G)
10. (1.B, 2.B, 15.W)
11. (1.W, 5.R, 10.B)
12. (1.W, 5.R, 10.B, 20.G)
13. (2.R, 10.R, 17.B)
14. (1.R, 6.G, 25.W)
15. (1.R, 5.R, 6.G, 25.W)
16. (3.R, 9.G, 15.B)
17. (3.R, 9.G, 15.B)
18. (1.W, 9.G, 17.R, 38.R)
19. (1.B, 5.B, 6.W)
20. (7.R, 15.B, 17.B, 20.W, 39.W)
21. (7.R, 15.B, 17.B, 20.W, 39.W)
22. (1.B, 9.R, 10.G, 20.R)
23. (1.W, 17.R, 30.B)
24. (1.R, 5.B, 11.G, 15.B, 25.G)
25. (1.B, 5.G, 6.R, 25.W, 41.Y) /;
Parameter nc(c) 'number of colors';
nc(c) = idc('%curid%',c);
Scalar n 'number of commercial';
n = sum(c,nc(c));
Parameter dc(c) 'ideal distance';
dc(c)$nc(c) = n/nc(c);
Alias (sp,i,j);
s(sp+1) = ord(sp) <= n;
* Build network
Set net(c,i,j) 'network connecting slots';
Parameter dev(c,i,j) 'deviation of distance i and j to ideal distance';
Scalar
isf 'initial span factor' / 2 /
msf 'middle span factor range' / 0.1 /
sf 'span factor';
$if set sparse $goto dosparse
* Dense graph
loop(c$nc(c),
loop(i$(ord(i) <= n+1),
net(c,i,j)$(ord(j) > ord(i)) = yes;
);
);
$label dosparse
loop(c$nc(c),
net(c,'0',j)$(ord(j) > 1 and ord(j) <= min(n+1,1+isf*dc(c))) = yes;
sf = msf;
if(sf*dc(c) < 5, sf = 5/dc(c));
loop(i$(ord(i) > 1 and ord(i) <= n+1),
net(c,i,j)$(ord(j) > max(ord(i),ord(i)+(1-sf)*dc(c)) and
ord(j) <= min(n+1,ord(i)+(1+sf)*dc(c))) = yes;
);
);
* The arcs back to the source
net(c,s,'0') = yes;
dev(net(c,i,j))$(ord(i) > 1 and ord(j) > 1) = abs(ord(j) - ord(i) - dc(c));
* option dev:5:0:1; display dev;
* Model
Variable
f(c,i,j) 'flow variable'
p(c,i) 'placement variable'
obj 'objective variable';
Binary Variable p;
Positive Variable f;
Equation
bal(c,i) 'flow balance equation'
balinit(c) 'flow balance for node 0'
defopen(c,i) 'close slots for different colors'
defsump(c) 'number of open slots'
covslot(i) 'slot cover requirement'
defobj 'objective function';
bal(c,s)$nc(c).. sum(net(c,j,s), f(net)) - sum(net(c,s,j), f(net)) =e= 0;
balinit(c)$nc(c).. sum(net(c,'0',j), f(net)) =e= 1;
defopen(c,s)$nc(c).. sum(net(c,s,j), f(net)) =e= p(c,s);
defsump(c)$nc(c).. sum(s, p(c,s)) =e= nc(c);
covslot(s).. sum(c$nc(c), p(c,s)) =e= 1;
defobj.. obj =e= sum(net, dev(net)*f(net));
Model commercial / all /;
option optCr = 0, resLim = 300;
Set sol 'solution reporting set';
Parameter solrep;
* Try priorities
commercial.priorOpt = 1;
p.prior(c,s) = nc(c);
* Solve the preplaced model first
p.lo(c,s)$preplace('%curid%',s,c) = 1;
solve commercial min obj using mip;
sol('%curid%','PRE',s,c) = p.l(c,s);
solrep('PRE','obj') = obj.l;
solrep('PRE','bnd') = commercial.objEst;
solrep('PRE','res') = commercial.resUsd;
* Release the preplaced balls
p.lo(c,s)$preplace('%curid%',s,c) = 0;
* Lets start with the pre fixed solution if using CPLEX
* (uncomment next three lines)
* File fcpx / cplex.opt /;
* putClose fcpx 'mipStart 1';
* commercial.optFile = 1;
solve commercial min obj using mip;
sol('%curid%','FREE',s,c) = p.l(c,s);
solrep('FREE','obj') = obj.l;
solrep('FREE','bnd') = commercial.objEst;
solrep('FREE','res') = commercial.resUsd;
display sol, solrep;
* If you want a report with times, objs, and bnd useful for batchruns,
* uncomment the $exit
$exit
File fsol / allsol.txt /;
* Append to solution file, but not for the first one
fsol.ap$(not sameas('%curid%','1')) = 1;
put fsol 'Solution for Instance %curid%: obj_pre: ' solrep('PRE','obj'):12:5
' obj_free: ' solrep('FREE','obj'):12:5 /
'Slot pre free' /;
loop(s(sp),
put (ord(sp)-1):3:0 ' '
loop(c$sol('%curid%','PRE' ,s,c), put c.tl:1 ' ';);
loop(c$sol('%curid%','FREE',s,c), put c.tl:1 /;);
);
File ftim / alltim.txt /;
* Append to time file, but not for the first one
ftim.ap$(not sameas('%curid%','1')) = 1;
* put a header for the first one
put$sameas('%curid%','1') ftim
' Preplace balls no preplaced balls' /
'id obj bnd res obj bnd res'/;
put ftim (%curid%):2:0 solrep('PRE','obj'):12:5
solrep('PRE','bnd'):12:5
solrep('PRE','res'):12:5
solrep('FREE','obj'):12:5
solrep('FREE','bnd'):12:5
solrep('FREE','res'):12:5 /;