This is an old revision of the document!
Q: I have the following problem.I am trying to organize a schedule for a set of team games. Here are the rules: * there are 7 teams: A,B,C,D,E,F,G * a game requires 3 teams * each team must play each other in all combinations exactly once Obviously this requires 35 games. So. * 5 games will be played each week, requiring 7 weeks, * one team will play 3 times * and the other 6 teams will each play two games The team that plays 3 times must play each of the other teams the team that plays 3 times changes each week I can iterate all of the required games, but I cannot come up with an algorithm that will solve this problem.
Look at this model:
set t teams /a,b,c,d,e,f,g/, n game number /game-1*game-5/, w week number /week-1*week-7/; alias (t,t1,t2,t3,s); set g(t,t1,t2) games ; g(t,t1,t2)$((ord(t) lt ord(t1)) and (ord(t1) lt ord(t2))) = yes; * g now contains only tuples (t,t1,t2) such that * there are no duplicates (i.e. a.b.c and c.b.a) * and no repetitions (i.e. a.b.a). You can check * that the cardinality of this set (card(g)) is * indeed 35. set isg(t, t1,t2,t3); isg(t, t ,t2,t3)$g(t ,t2,t3) = yes; isg(t, t1,t ,t3)$g(t1,t ,t3) = yes; isg(t, t1,t2,t )$g(t1,t2,t ) = yes; * isg(t, t1,t2,t3) provides a mapping * between team t and all the games * (t1,t2,t3) it plays. * For instance if one would like to * know which games are played by team d, * use something like: * * set gd(t1,t2,t3); * gd(t1,t2,t3)$isg(’d’, t1,t2,t3) = yes; * display gd; set map(t,w); map(t,w)$(ord(t) eq ord(w)) = yes; * we let team a play 3 times in week 1 * etc. This means we have a direct mapping * between weeks and teams. This mapping * map takes care of that. variables x(t1,t2,t3,w) schedule, dummy; binary variables x; * x is declared over (t1,t2,t3, w) but we will * use it only over (g, w). I.e. there are * card(g)*card(w) binary variables. equations obj just a dummy objective vert(t1,t2,t3) assignment constraints hori(w) assignment constraints count(t,w) two or three games each week forbid(t,w,s) ; obj.. dummy =e= 1; vert(g).. sum(w, x(g,w)) =e= 1; hori(w).. sum(g, x(g,w)) =e= 5; * these are normal assignment constraints: assign * games to weeks. count(t,w).. sum(g$isg(t,g),x(g,w) ) =e= 2 + 1$map(t,w); * 3 games for the team selected for this week (via map) * and 2 games for all the other teams forbid(t,w,s)$((not map(t,w))*map(s,w)).. sum(g$(isg(s,g)*isg(t,g)), x(g,w))=e=1 ; * the team that plays 3 times in week w is team s. Its opponents are t. We * have to make sure that s sees all t during this week. model m /all/; option iterlim=10000; solve m using mip minimizing dummy; * display results in nicer format parameter r(w, t1, t2, t3); r(w,g) = x.l(g,w); option r:1:0:1; display r;