%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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"];