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