Coverage for moptipyapps / ttp / errors.py: 15%

1""" 

2An objective that counts constraint violations. 

3 

4The idea is that we will probably not be able to always produce game plans 

5that adhere to all the constraints imposed by a Traveling Tournament Problem 

6:mod:`~moptipyapps.ttp` :mod:`~moptipyapps.ttp.instance`, so we will instead 

7probably usually generate game plans that may contain errors. 

8 

9We will hope that optimization can take care of this by applying this 

10objective function here to get rid of them. In the documentation of function 

11:func:`~moptipyapps.ttp.errors.count_errors`, we explain the different types 

12of errors that may occur and that are counted. 

13 

14This objective function plays thus well with encodings that produce infeasible 

15schedules, such as the very simple :mod:`~moptipyapps.ttp.game_encoding`. 

16""" 

17 

18 

19from typing import Final 

20 

21import numba # type: ignore 

22import numpy as np 

23from moptipy.api.objective import Objective 

24from moptipy.utils.nputils import int_range_to_dtype 

25from pycommons.types import type_error 

26 

27from moptipyapps.ttp.game_plan import GamePlan 

28from moptipyapps.ttp.instance import Instance 

29 

30 

31@numba.njit(cache=True, inline="always", fastmath=True, boundscheck=False) 

32def count_errors(y: np.ndarray, home_streak_min: int, 

33 home_streak_max: int, away_streak_min: int, 

34 away_streak_max: int, separation_min: int, 

35 separation_max: int, temp_1: np.ndarray, 

36 temp_2: np.ndarray) -> int: 

37 """ 

38 Compute the number of errors in a game plan. 

39 

40 This method counts the total number of the violations of any of the 

41 following constraints over `D = (n - 1) * rounds` days for `n`-team 

42 tournaments, where `rounds == 2` for double-round robin. The following 

43 kinds of errors are counted: 

44 

45 1. If a team `A` plays a team `B` on a given day, then `B` must play 

46 against `A` on that day and if `A` plays at home, then `B` must play 

47 away. If not, then that's an error. This can result in at most 

48 `D * n` errors, because each of the `n` teams has (at most) one game 

49 on each of the `D` days and if the *other* team could play against 

50 the wrong team (or does not play at all), then that's one error. 

51 2. If a team has no other team assigned to play with, this is designated 

52 by value `0` and causes 1 error. This error also ends all ongoing 

53 streaks, i.e., may additionally lead to a streak violation of at 

54 most `max(home_streak_min, away_streak_min) - 1`. However, this 

55 cannot be more then two errors in sum per day (minus 1, for the 

56 first day). Also, this error is mutually exclusive with error 1. 

57 This can result in at most `D * n + (D - 1) * n = (2*D - 1) * n` 

58 errors. Since this error is also mutually exclusive with the errors 

59 from constraints 3 to 8 below, this gives us an upper bound of 

60 `(2*D - 1) * n` errors for all of the constraints (1-8) together. 

61 3. A team has a home streak shorter than `home_streak_min`. No such error 

62 can occur on the first day. This error is mutually exclusive with 

63 error 2, as the streak violation is already counted there. 

64 This can result in at most `(D - 1) * n` errors, but this number is 

65 shared with the following constraints (4-6), because a streak can only 

66 either be a home streak or an away streak but not both and it can 

67 either be too short or too long, but not both. 

68 4. A team has a home streak longer than `home_streak_max`. No such error 

69 can occur on the first day. This error is mutually exclusive with 

70 error 2. 

71 5. A team has an away streak shorter than `away_streak_min`. No such 

72 error can occur on the first day. This error is mutually exclusive 

73 with error 2, as the streak violation is already counted there. 

74 6. A team has an away streak longer than `away_streak_max`. No such 

75 error can occur on the first day. This error is mutually exclusive 

76 with error 2. 

77 7. Team `A` plays team `B` *again* before the team has played at least 

78 `separation_min` games against other teams. This error cannot occur 

79 on the first day and is mutually exclusive with error 2. 

80 There can be most 1 such error per day for any pairing of teams and 

81 there are `n//2` pairings per day, giving us an upper bound of 

82 `D * n//2` errors in total. This error is mutually exclusive with 

83 the next constraint 8 (and constraint 2). 

84 8. Team `A` plays team `B` *again* after the team has played more than 

85 `separation_max` games against other teams. This error cannot occur 

86 on the first day and is mutually exclusive with error 2. 

87 There can be most 1 such error per day for any pairing of teams and 

88 there are `n//2` pairings per day, giving us an upper bound of 

89 `D * n//2` errors in total. This error is mutually exclusive with 

90 the previous constraint 7 (and constraint 2). 

91 9. If team `A` plays team `B` at home `a` times, then team `B` must play 

92 team `A` at home at least `a-1` and at most `a+1` times. 

93 In total, we have `D*n` games. There cannot be more than `(D*n) - 1` 

94 such errors. Notice that this kind of error can never occur if we use 

95 our :mod:`~moptipyapps.ttp.game_encoding` as representation. 

96 10. Each pairing of teams occurs as same as often, namely `rounds` times, 

97 with `rounds = 2` for double-round robin. 

98 In total, we have `D*n` games. There cannot be more than `D*n` such 

99 errors. Notice that this kind of error can never occur if we use 

100 our :mod:`~moptipyapps.ttp.game_encoding` as representation. 

101 

102 The violations are counted on a per-day basis. For example, if 

103 `home_streak_max` is `3` and a team has a home streak of length `5`, then 

104 this counts as `2` errors. However, the errors are also counted in a 

105 non-redundant fashion: If a team `A` violates `separation_min` by, say, 

106 two days, then this counts as two errors. However, in this case, its 

107 opposing team `B` would have necessarily incured the exactly same 

108 violations. These are then not counted. 

109 

110 As upper bound for the number of errors, we therefore have to add those of 

111 constraints 2, 9, and 10 and get `(2*D - 1) * n + D*n - 1 + D*n`, which 

112 gives us `(4*D - 1) * n - 1, where `D = (n - 1) * rounds`. 

113 The lower bound is obviously `0`. 

114 

115 :param y: the game plan 

116 :param home_streak_min: the minimum permitted home streak length 

117 :param home_streak_max: the maximum permitted home streak length 

118 :param away_streak_min: the minimum permitted away streak length 

119 :param away_streak_max: the maximum permitted away streak length 

120 :param separation_min: the minimum number of games between a repetition 

121 :param separation_max: the maximum number games between a repetition 

122 :param temp_1: a temporary `n*(n-1)/2` integer array, which is used to 

123 hold, for each pairing, when the last game was played 

124 :param temp_2: a temporary `n,n` integer array, which is used to hold, 

125 how often each team played each other team 

126 :returns: the total number of errors. `0` if the game plan is feasible 

127 

128 >>> count_errors(np.array([[-2, 1], [2, -1]], int), 

129 ... 1, 3, 1, 3, 1, 2, np.empty(1, int), 

130 ... np.empty((2, 2), int)) 

131 1 

132 >>> count_errors(np.array([[2, -1], [-2, 1]], int), 

133 ... 1, 3, 1, 3, 1, 2, np.empty(1, int), 

134 ... np.empty((2, 2), int)) 

135 1 

136 >>> count_errors(np.array([[ 2, -1, 4, -3], 

137 ... [ 4, 3, -2, -1], 

138 ... [-2, 1, -4, 3], 

139 ... [-4, -3, 2, 1], 

140 ... [ 3, 4, -1, -2], 

141 ... [-3, -4, 1, 2]], int), 

142 ... 1, 3, 1, 3, 1, 2, np.empty(6, int), 

143 ... np.empty((4, 4), int)) 

144 2 

145 >>> count_errors(np.array([[ 2, -1, 4, -3], 

146 ... [ 4, 3, -2, -1], 

147 ... [-2, 1, -4, 3], 

148 ... [ 3, 4, -1, -2], 

149 ... [-4, -3, 2, 1], 

150 ... [-3, -4, 1, 2]], int), 

151 ... 1, 3, 1, 3, 1, 2, np.empty(6, int), 

152 ... np.empty((4, 4), int)) 

153 0 

154 >>> count_errors(np.array([[ 2, -1, 4, -3], 

155 ... [ 4, 3, -2, -1], 

156 ... [ 3, 4, -1, -2], 

157 ... [-2, 1, -4, 3], 

158 ... [-4, -3, 2, 1], 

159 ... [-3, -4, 1, 2]], int), 

160 ... 1, 3, 1, 3, 1, 2, np.empty(6, int), 

161 ... np.empty((4, 4), int)) 

162 0 

163 >>> count_errors(np.array([[ 2, -1, 4, -3], 

164 ... [ 4, 3, -2, -1], 

165 ... [ 3, 4, -1, -2], 

166 ... [-2, 1, -4, 3], 

167 ... [-4, -3, 2, 1], 

168 ... [-3, -4, 1, 2]], int), 

169 ... 1, 2, 1, 3, 1, 2, np.empty(6, int), 

170 ... np.empty((4, 4), int)) 

171 3 

172 >>> count_errors(np.array([[ 2, -1, 4, -3], 

173 ... [ 4, 3, -2, -1], 

174 ... [ 3, 4, -1, -2], 

175 ... [-2, 1, -4, 3], 

176 ... [-4, -3, 2, 1], 

177 ... [-3, -4, 1, 2]], int), 

178 ... 1, 2, 1, 2, 1, 2, np.empty(6, int), 

179 ... np.empty((4, 4), int)) 

180 6 

181 >>> count_errors(np.array([[ 2, -1, 4, -3], 

182 ... [ 4, 3, -2, -1], 

183 ... [ 3, 4, -1, -2], 

184 ... [-2, 1, -4, 3], 

185 ... [-4, -3, 2, 1], 

186 ... [-3, -4, 1, 2]], int), 

187 ... 1, 3, 1, 3, 1, 1, np.empty(6, int), 

188 ... np.empty((4, 4), int)) 

189 6 

190 """ 

191 days, teams = y.shape # get the number of days and teams 

192 errors: int = 0 # the error counter 

193 temp_1.fill(-1) # last time the teams played each other 

194 temp_2.fill(0) 

195 for team_1 in range(teams): 

196 col = y[:, team_1] 

197 team_1_id: int = team_1 + 1 

198 is_in_home_streak: bool = False 

199 home_streak_len: int = -1 

200 is_in_away_streak: bool = False 

201 away_streak_len: int = -1 

202 

203 for day, team_2_id in enumerate(col): 

204 if team_2_id == 0: # is there no game on this day? 

205 errors += 1 # no game on this day == 1 error 

206 

207 if is_in_away_streak: # this ends away streaks 

208 is_in_away_streak = False 

209 if away_streak_len < away_streak_min: 

210 errors += (away_streak_min - away_streak_len) 

211 away_streak_len = -1 

212 elif is_in_home_streak: # this ends home streaks, too 

213 is_in_home_streak = False 

214 if home_streak_len < home_streak_min: 

215 errors += (home_streak_min - home_streak_len) 

216 home_streak_len = -1 

217 continue # nothing more to do here 

218 

219 if team_2_id > 0: # our team plays a home game 

220 

221 # If team_2 > 0, this is a home game. So the other team 

222 # must have the corresponding index. 

223 team_2 = team_2_id - 1 

224 if y[day, team_2] != -team_1_id: 

225 errors += 1 

226 # increase number of home games of team 1 against team 2 

227 temp_2[team_1, team_2] += 1 

228 

229 if is_in_home_streak: # if we are in a home streak... 

230 home_streak_len += 1 # ...it continues 

231 if home_streak_len > home_streak_max: 

232 errors += 1 # too long? add to errors 

233 else: # if we are not in home streak, it begins 

234 is_in_home_streak = True 

235 home_streak_len = 1 

236 # if a home streak begins, any away streak ends 

237 if is_in_away_streak: 

238 if away_streak_len < away_streak_min: 

239 errors += (away_streak_min - away_streak_len) 

240 away_streak_len = -1 

241 is_in_away_streak = False 

242 else: # else: team_2 < 0 --> team_2 at home, team_1 away 

243 team_2 = (-team_2_id) - 1 

244 

245 # This is an away game, so the other team must have the 

246 # corresponding id 

247 if y[day, team_2] != team_1_id: 

248 errors += 1 

249 

250 if is_in_away_streak: # if we are in an away streak... 

251 away_streak_len += 1 # ...the streak continues 

252 if away_streak_len > away_streak_max: 

253 errors += 1 # away streak too long? add to error 

254 else: # team_1 away, but not in away streak 

255 is_in_away_streak = True 

256 away_streak_len = 1 

257 if is_in_home_streak: 

258 if home_streak_len < home_streak_min: 

259 errors += (home_streak_min - home_streak_len) 

260 is_in_home_streak = False 

261 home_streak_len = 0 

262 

263 # now we need to check for the game separation difference 

264 idx: int = ((team_1 * (team_1 - 1) // 2) + team_2) \ 

265 if team_1 > team_2 \ 

266 else ((team_2 * (team_2 - 1) // 2) + team_1) 

267 last_time: int = temp_1[idx] 

268 if last_time >= 0: 

269 if last_time < day: 

270 difference = day - last_time - 1 

271 if difference < separation_min: 

272 errors += (separation_min - difference) 

273 elif difference > separation_max: 

274 errors += (difference - separation_max) 

275 else: 

276 continue 

277 temp_1[idx] = day 

278 

279 # sum up the team games 

280 games_per_combo: Final[int] = days // (teams - 1) 

281 for i in range(teams): 

282 for j in range(i): 

283 ij = temp_2[i, j] 

284 ji = temp_2[j, i] 

285 errors += abs(ij + ji - games_per_combo) 

286 diff = abs(ij - ji) 

287 if diff > 1: 

288 errors += diff - 1 

289 

290 return int(errors) 

291 

292 

293class Errors(Objective): 

294 """ 

295 Compute the errors in a game plan. 

296 

297 This objective function encompasses all the constraints imposed on 

298 standard TTP instances in one summarizing number. See the documentation 

299 of :func:`count_errors` for more information. 

300 """ 

301 

302 def __init__(self, instance: Instance) -> None: 

303 """ 

304 Initialize the errors objective function. 

305 

306 :param instance: the TTP instance 

307 """ 

308 if not isinstance(instance, Instance): 

309 raise type_error(instance, "instance", Instance) 

310 super().__init__() 

311 

312 #: the TTP instance 

313 self.instance: Final[Instance] = instance 

314 n: Final[int] = instance.n_cities 

315 # the data type for the temporary arrays 

316 dtype: Final[np.dtype] = int_range_to_dtype( 

317 -1, (n - 1) * instance.rounds) 

318 #: the internal temporary array 1 

319 self.__temp_1: Final[np.ndarray] = np.empty(n * (n - 1) // 2, dtype) 

320 #: the internal temporary array 2 

321 self.__temp_2: Final[np.ndarray] = np.empty((n, n), dtype) 

322 

323 def evaluate(self, x: GamePlan) -> int: 

324 """ 

325 Count the errors in a game plan as objective value. 

326 

327 :param x: the game plan 

328 :return: the number of errors in the plan 

329 """ 

330 inst: Final[Instance] = x.instance 

331 return count_errors(x, inst.home_streak_min, inst.home_streak_max, 

332 inst.away_streak_min, inst.away_streak_max, 

333 inst.separation_min, inst.separation_max, 

334 self.__temp_1, self.__temp_2) 

335 

336 def lower_bound(self) -> int: 

337 """ 

338 Obtain the lower bound for errors: `0`, which means error-free. 

339 

340 :return: `0` 

341 """ 

342 return 0 

343 

344 def upper_bound(self) -> int: 

345 """ 

346 Compute upper bound for errors: `(4*D - 1) * n - 1`. 

347 

348 Here `D` is the number of days, `n` is the number of teams, and 

349 `D = (n - 1) * rounds`. See the documentation of :func:`count_errors`. 

350 

351 :return: `(4*D - 1) * n - 1` 

352 """ 

353 n: Final[int] = self.instance.n_cities 

354 rounds: Final[int] = self.instance.rounds 

355 days: Final[int] = (n - 1) * rounds 

356 return (4 * days - 1) * n - 1 

357 

358 def is_always_integer(self) -> bool: 

359 """ 

360 State that this objective function is always integer-valued. 

361 

362 :return: `True` 

363 """ 

364 return True 

365 

366 def __str__(self) -> str: 

367 """Get the name of this objective function.""" 

368 return "errors"