%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Traveling Tournament Problem with Predefined Venues % % Compact single round robin schedule minimizing total travel distance % The venue of each game has already been decided % Specialized for CIRC instances (circular distances) % % Author: Gilles Pesant %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% include "globals.mzn"; int: nbTeams; int: nbRounds = nbTeams-1; set of int: Teams = 1..nbTeams; set of int: Rounds = 1..nbRounds; set of int: Travels = 1..nbRounds+1; % predefined venue: pv[i][j] = 1 iff i is playing at home against j array[Teams,Teams] of 1..2: pv; % circular distances: for i>=j, distance[i][j]=min{i-j,j-i+nbTeams} array[Teams,Teams] of int: distance = array2d(Teams,Teams,[ if i>=j then (if i-j < j-i+nbTeams then i-j else j-i+nbTeams endif) else (if j-i < i-j+nbTeams then j-i else i-j+nbTeams endif) endif | i,j in Teams]); % output related int: digs = ceil(log(10.0,int2float(nbTeams))); %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % decision variables: in round k, team i plays against team opponent[i,k] array[Teams,Rounds] of var Teams: opponent; % auxiliary variables: venue[i,k] = 1 iff team i plays at home in round k array[Teams,Rounds] of var 1..2: venue; constraint forall (i in Teams, k in Rounds) (venue[i,k] = pv[i,opponent[i,k]]); % auxiliary variables: travel[i,k] is the distance travelled by team i to go play in round k (includes travelling back home after last round) array[Teams,Travels] of var 0..(nbTeams div 2): travel; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % a team cannot play against itself constraint forall (i in Teams, k in Rounds) (opponent[i,k] != i); % in round k, i plays j means j plays i constraint forall (i in Teams, k in Rounds) (opponent[opponent[i,k],k] = i); % for each team i, all opponents are different constraint forall (i in Teams) (alldifferent([opponent[i,k] | k in Rounds])); % for each round k, all opponents are different (implied constraint) constraint forall (k in Rounds) (alldifferent([opponent[i,k] | i in Teams])); % for each team i, there can be at most 3 consecutive home games and at most 3 consecutive away games int: nbStates = 7; set of int: States = 1..nbStates; array[States,1..2] of int: delta = [| 2, 5 | 3, 5 | 4, 5 | 0, 5 | 2, 6 | 2, 7 | 2, 0 |]; constraint forall (i in Teams) (regular( [venue[i,k] | k in Rounds], nbStates, 2, delta, 1, States)); % symmetry breaking: distances are symmetric so reversing the rounds yields a schedule of same cost constraint (opponent[1,1] < opponent[1,nbRounds]); % define travel variables wrt venues of current- and next-round games constraint forall (i in Teams) ( (venue[i,1]=1 -> travel[i,1] = 0) /\ (venue[i,1]=2 -> travel[i,1] = distance[i,opponent[i,1]]) ); constraint forall (i in Teams, k in 1..nbRounds-1) ( ((venue[i,k]=1 /\ venue[i,k+1]=1) -> travel[i,k+1] = 0) /\ ((venue[i,k]=2 /\ venue[i,k+1]=1) -> travel[i,k+1] = distance[opponent[i,k],i]) /\ ((venue[i,k]=1 /\ venue[i,k+1]=2) -> travel[i,k+1] = distance[i,opponent[i,k+1]]) /\ ((venue[i,k]=2 /\ venue[i,k+1]=2) -> travel[i,k+1] = distance[opponent[i,k],opponent[i,k+1]]) ); constraint forall (i in Teams) ( (venue[i,nbRounds]=1 -> travel[i,nbRounds+1] = 0) /\ (venue[i,nbRounds]=2 -> travel[i,nbRounds+1] = distance[opponent[i,nbRounds],i]) ); %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% var int: totalTravel; constraint totalTravel = sum (i in Teams, k in Travels) (travel[i,k]); solve minimize totalTravel; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% output ["SCHEDULE\n"] ++ [ if fix(venue[i,k]) == 1 then " " else "@" endif ++ show_int(digs,opponent[i,k]) ++ " " ++ if k == nbRounds /\ i != nbTeams then "\n" else "" endif | i in Teams, k in Rounds ] ++ ["\n"] ++ ["total travel = "] ++ [show(totalTravel)] ++ ["\n"];