2 from __future__ import print_function
5 from ortools.sat.python import cp_model
9 num_groups = 2 # NOTE: 2 is hard-coded in some places.
10 num_teams_per_group = 6
11 num_teams = num_teams_per_group * num_groups
12 num_rounds = (num_teams_per_group * (num_teams_per_group - 1)) // 2
13 num_matches = num_rounds * num_groups
15 class SolutionPrinterWithObjective(cp_model.CpSolverSolutionCallback):
16 def __init__(self, home_teams, away_teams, matchnums, objective):
17 cp_model.CpSolverSolutionCallback.__init__(self)
18 self.__solution_count = 0
19 self.__start_time = time.time()
20 self.__home_teams = home_teams
21 self.__away_teams = away_teams
22 self.__matchnums = matchnums
23 self.__objective = objective
25 def OnSolutionCallback(self):
26 current_time = time.time()
27 self.__solution_count += 1
28 print('Solution %i, time = %f s, objective = %d' %
29 (self.__solution_count, current_time - self.__start_time, self.Value(self.__objective)))
30 num_times_on_stream = [0 for team_idx in range(num_teams)]
31 num_times_tired = [0 for team_idx in range(num_teams)]
32 recently_played_0 = [False for team_idx in range(num_teams)]
33 recently_played_1 = [False for team_idx in range(num_teams)]
34 recently_played_2 = [False for team_idx in range(num_teams)]
35 recently_played_3 = [False for team_idx in range(num_teams)]
36 for i in range(num_matches // num_groups):
37 recently_played_4 = [False for team_idx in range(num_teams)]
38 print("%2d. " % (i), end='')
39 for g in range(num_groups):
40 j = i * num_groups + g
41 home_team = self.Value(self.__home_teams[j])
42 away_team = self.Value(self.__away_teams[j])
43 matchnum = self.Value(self.__matchnums[j])
46 num_times_on_stream[home_team] = num_times_on_stream[home_team] + 1
47 num_times_on_stream[away_team] = num_times_on_stream[away_team] + 1
50 if recently_played_2[home_team]:
51 tiredness = tiredness + 1
52 num_times_tired[home_team] = num_times_tired[home_team] + 1
53 if recently_played_0[home_team]:
54 tiredness = tiredness + 100
55 if recently_played_2[away_team]:
56 tiredness = tiredness + 1
57 num_times_tired[away_team] = num_times_tired[away_team] + 1
58 if recently_played_0[away_team]:
59 tiredness = tiredness + 100
60 recently_played_4[home_team] = True
61 recently_played_4[away_team] = True
63 print("%s vs. %s (matchnum %2d, excitedness %d*%2d, tiredness %3d) " % (team_name(home_team), team_name(away_team), matchnum, excitedness[matchnum], excitedness_weight(j), tiredness), end='')
65 recently_played_0 = recently_played_1
66 recently_played_1 = recently_played_2
67 recently_played_2 = recently_played_3
68 recently_played_3 = recently_played_4
70 print("Number of times on stream: ", end='')
71 print(", ".join(["%s %d" % (team_name(team_idx), num_times_on_stream[team_idx]) for team_idx in range(num_teams)]))
72 print("Number of times tired: ", end='')
73 print(", ".join(["%s %d" % (team_name(team_idx), num_times_tired[team_idx]) for team_idx in range(num_teams)]))
74 print("Stream opponents for non-top-teams:")
75 for team_idx in (2, 3, 4, 5, 8, 9, 10, 11):
77 for i in range(num_matches // num_groups):
78 home_team = self.Value(self.__home_teams[i * 2])
79 away_team = self.Value(self.__away_teams[i * 2])
81 if abs(home_team - away_team) == 1:
83 if team_idx == home_team:
84 opp.append(team_name(away_team) + mark)
85 if team_idx == away_team:
86 opp.append(team_name(home_team) + mark)
87 print(" %s: %s" % (team_name(team_idx), ", ".join(sorted(opp))))
90 def excitedness_weight(match_idx):
91 field = match_idx % num_groups
92 match_order = match_idx // num_groups
94 return match_order + 5
98 def team_name(team_idx):
99 if team_idx < num_teams_per_group:
100 return "A%d" % (team_idx)
102 return "B%d" % (team_idx - num_teams_per_group)
104 model = cp_model.CpModel()
106 # Create match variables.
108 for match_idx in range(num_matches):
109 matchnums.append(model.NewIntVar(0, num_matches - 1, "matchnum(%i)" % (match_idx)))
110 model.AddAllDifferent(matchnums)
112 # Create list of matches.
115 home_teams_for_match_num = []
116 away_teams_for_match_num = []
117 for group in range(num_groups):
118 for team_idx_1 in range(num_teams_per_group):
119 for team_idx_2 in range(num_teams_per_group):
120 if team_idx_2 > team_idx_1:
121 real_team_idx_1 = team_idx_1 + num_teams_per_group * group
122 real_team_idx_2 = team_idx_2 + num_teams_per_group * group
123 home_teams_for_match_num.append(real_team_idx_1)
124 away_teams_for_match_num.append(real_team_idx_2)
125 if team_idx_2 - team_idx_1 == 1:
126 excitedness.append(5)
127 elif team_idx_2 - team_idx_1 == 2:
128 excitedness.append(2)
130 excitedness.append(0)
131 print("matchnum %2d: %2d vs. %2d, excited: %d" % (match_idx, real_team_idx_1, real_team_idx_2, excitedness[match_idx]))
132 match_idx = match_idx + 1
134 # Create match variables.
137 for match_idx in range(num_matches):
138 home_teams.append(model.NewIntVar(0, num_teams - 1, "home_team_match%i" % (match_idx)))
139 away_teams.append(model.NewIntVar(0, num_teams - 1, "away_team_match%i" % (match_idx)))
140 matches_flat = home_teams + away_teams
142 for match_idx in range(num_matches):
143 model.AddElement(matchnums[match_idx], home_teams_for_match_num, home_teams[match_idx])
144 model.AddElement(matchnums[match_idx], away_teams_for_match_num, away_teams[match_idx])
147 home_team_in_match_x_is_y = [[
148 model.NewBoolVar('home_team_in_match_%d_is_%d' % (match_idx, team_idx)) for team_idx in range(num_teams)
149 ] for match_idx in range(num_matches)]
151 away_team_in_match_x_is_y = [[
152 model.NewBoolVar('away_team_in_match_%d_is_%d' % (match_idx, team_idx)) for team_idx in range(num_teams)
153 ] for match_idx in range(num_matches)]
155 match_x_has_num_y = [[
156 model.NewBoolVar('match_%d_has_number_%d' % (a, b)) for a in range(num_matches)
157 ] for b in range(num_matches)]
159 for match_idx in range(num_matches):
160 model.AddMapDomain(matchnums[match_idx], match_x_has_num_y[match_idx])
161 model.AddMapDomain(home_teams[match_idx], home_team_in_match_x_is_y[match_idx])
162 model.AddMapDomain(away_teams[match_idx], away_team_in_match_x_is_y[match_idx])
164 # Fields always play opposing groups (FIXME?)
165 for round_idx in range(num_rounds):
166 field_0_is_group_0 = model.NewBoolVar('field_0_round_%d_is_group_0' % (round_idx))
167 model.AddMaxEquality(field_0_is_group_0, [match_x_has_num_y[round_idx * 2 + 0][match_idx] for match_idx in range(num_rounds)])
168 field_1_is_group_0 = model.NewBoolVar('field_1_round_%d_is_group_0' % (round_idx))
169 model.AddMaxEquality(field_1_is_group_0, [match_x_has_num_y[round_idx * 2 + 1][match_idx] for match_idx in range(num_rounds)])
170 model.AddBoolXOr([field_0_is_group_0, field_1_is_group_0])
172 # A team can never play on the same field at the same time
173 #for team_idx in range(num_teams):
174 # for round_idx in range(num_rounds):
175 # plays_on_field_0 = model.NewBoolVar('plays_on_field0_t%d_r%d' % (team_idx, round_idx))
176 # model.AddMaxEquality(plays_on_field_0, [
177 # home_team_in_match_x_is_y[round_idx * 2 + 0][team_idx],
178 # away_team_in_match_x_is_y[round_idx * 2 + 0][team_idx]])
179 # plays_on_field_1 = model.NewBoolVar('plays_on_field1_t%d_r%d' % (team_idx, round_idx))
180 # model.AddMaxEquality(plays_on_field_1, [
181 # home_team_in_match_x_is_y[round_idx * 2 + 1][team_idx],
182 # away_team_in_match_x_is_y[round_idx * 2 + 1][team_idx]])
183 # model.AddBoolOr([plays_on_field_0.Not(), plays_on_field_1.Not()])
186 for team_idx in range(num_teams):
187 plays_in_round[team_idx] = {}
188 for round_idx in range(num_rounds):
189 plays_in_round[team_idx][round_idx] = model.NewBoolVar('plays_in_round_t%d_r%d' % (team_idx, round_idx))
190 model.AddMaxEquality(plays_in_round[team_idx][round_idx], [
191 home_team_in_match_x_is_y[round_idx * 2 + 0][team_idx],
192 home_team_in_match_x_is_y[round_idx * 2 + 1][team_idx],
193 away_team_in_match_x_is_y[round_idx * 2 + 0][team_idx],
194 away_team_in_match_x_is_y[round_idx * 2 + 1][team_idx]])
196 # A team can never play two matches in a row
197 for round_idx in range(num_rounds - 1):
198 for team_idx in range(num_teams):
199 model.AddBoolOr([plays_in_round[team_idx][round_idx].Not(), plays_in_round[team_idx][round_idx + 1].Not()])
201 # Also, double-tired is not cool
202 #for round_idx in range(num_rounds - 4):
203 # for team_idx in range(num_teams):
204 # model.AddBoolOr([plays_in_round[team_idx][round_idx].Not(), plays_in_round[team_idx][round_idx + 2].Not(), plays_in_round[team_idx][round_idx + 4].Not()])
206 # More waiting time is good
208 #for round_idx in range(num_rounds - 2):
209 # for team_idx in range(num_teams):
210 # tired = model.NewBoolVar('team_%d_is_tired_in_round_%d' % (team_idx, round_idx))
211 # model.AddMinEquality(tired, [plays_in_round[team_idx][round_idx], plays_in_round[team_idx][round_idx + 2]])
212 # tired_matches.append(tired)
213 #sum_tiredness = sum(tired_matches)
215 # Each team gets play-rest-play exactly once, for fairness
216 for team_idx in range(num_teams):
218 for round_idx in range(num_rounds - 2):
219 tired = model.NewBoolVar('team_%d_is_tired_in_round_%d' % (team_idx, round_idx))
220 model.AddMinEquality(tired, [plays_in_round[team_idx][round_idx], plays_in_round[team_idx][round_idx + 2]])
221 tired_matches.append(tired)
222 model.Add(sum(tired_matches) <= 1)
225 # TFK can not play the first two matches
226 model.AddBoolAnd([plays_in_round[0][0].Not(), plays_in_round[0][1].Not()])
228 # Group finals come last, and on the stream field.
229 model.AddBoolOr([match_x_has_num_y[num_matches - 2][0], match_x_has_num_y[num_matches - 2][num_rounds]])
230 model.AddBoolOr([match_x_has_num_y[num_matches - 4][0], match_x_has_num_y[num_matches - 4][num_rounds]])
232 # Count how many times each team has been on stream.
233 stream_penalties = []
234 for team_idx in range(num_teams):
235 playing_on_stream = []
236 for round_idx in range(num_rounds):
237 s = model.NewBoolVar('team_%d_plays_on_stream_in_round_%d' % (team_idx, round_idx))
238 model.AddMaxEquality(s, [
239 home_team_in_match_x_is_y[round_idx * 2 + 0][team_idx],
240 away_team_in_match_x_is_y[round_idx * 2 + 0][team_idx]])
241 playing_on_stream.append(s)
242 times_on_stream_this_team = sum(playing_on_stream)
243 model.Add(times_on_stream_this_team >= 1)
245 times_stream_var = model.NewIntVar(0, num_teams_per_group, "team_%d_stream_count" % (team_idx))
246 model.Add(times_stream_var == times_on_stream_this_team)
247 #model.Add(times_on_stream_this_team <= 4)
249 is_n_times_on_stream = [
250 model.NewBoolVar('team_%d_is_%d_times_on_stream' % (team_idx, i)) for i in range(num_teams_per_group)
252 model.AddMapDomain(times_stream_var, is_n_times_on_stream)
253 stream_penalties.append(is_n_times_on_stream[1] * -50)
254 stream_penalties.append(is_n_times_on_stream[4] * -10)
255 stream_penalties.append(is_n_times_on_stream[5] * -50)
257 # Make sure each team has at least one exciting match on stream.
258 #for team_idx in range(team_idx):
259 # stream_matches_for_this_team = []
260 # for round_idx in range(num_rounds):
261 # stream_matches_for_this_team.append(home_team_in_match_x_is_y[round_idx * 2 + 0][team_idx] * excitedness_weight(round_idx * 2 + 0))
262 # stream_matches_for_this_team.append(away_team_in_match_x_is_y[round_idx * 2 + 0][team_idx] * excitedness_weight(round_idx * 2 + 0))
264 # Put the more exciting games later, and on stream fields
266 for round_idx in range(num_rounds):
267 for match_idx in range(match_idx):
268 excitement.append(match_x_has_num_y[round_idx * 2 + 0][match_idx] * excitedness[match_idx] * excitedness_weight(round_idx * 2 + 0))
269 excitement.append(match_x_has_num_y[round_idx * 2 + 1][match_idx] * excitedness[match_idx] * excitedness_weight(round_idx * 2 + 1))
270 sum_excitement = sum(excitement)
271 objective = sum_excitement - 30 * sum_tiredness + 3 * sum(stream_penalties)
272 model.Maximize(objective)
274 solver = cp_model.CpSolver()
275 solution_printer = SolutionPrinterWithObjective(home_teams, away_teams, matchnums, objective)
276 status = solver.SolveWithSolutionCallback(model, solution_printer)