User Tools

Site Tools


gams:a_team_scheduling_problem

A Team Scheduling problem

$ontext
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.
$offtext
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;
gams/a_team_scheduling_problem.txt · Last modified: 2007/10/21 04:30 by franz