1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 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" ]; |