Coverage for moptipyapps / ttp / __init__.py: 100%

1""" 

2The Traveling Tournament Problem (TTP). 

3 

4The Traveling Tournament Problem (TTP) models the logistics of a sports 

5league, where each game is defined as two teams playing against each other. 

6In each time slot (let's call that "day") of the tournament, each team has 

7one game against one other team. One of the two teams of each game will play 

8"at home," the other "away." 

9 

10In order to have each of the `n` teams play once against each of the `n-1` 

11other teams, we need to have `n - 1` "days". So in one round of the 

12tournament, there are `n - 1` time slots so that each of the teams can play 

13exactly `n - 1` games, i.e., once against every other team. 

14 

15If the tournament has two rounds (i.e., is a double round-robin tournament), 

16then each game appears twice, but with home and away team switched. There are 

17also constraints for the minimum and maximum number of games at home in a row 

18and away in a row. There are also constraints for the minimum and maximum 

19number in between repeating a game (with home/away team switched). 

20 

211. David Van Bulck. Minimum Travel Objective Repository. *RobinX: An 

22 XML-driven Classification for Round-Robin Sports Timetabling.* Faculty of 

23 Economics and Business Administration at Ghent University, Belgium. 

24 https://robinxval.ugent.be/. In this repository, you can also find the 

25 original instance data, useful descriptions, and many links to related 

26 works. 

272. Kelly Easton, George L. Nemhauser, and Michael K. Trick. The Traveling 

28 Tournament Problem Description and Benchmarks. In *Principles and Practice 

29 of Constraint Programming (CP'01),* November 26 - December 1, 2001, Paphos, 

30 Cyprus, pages 580-584, Berlin/Heidelberg, Germany: Springer. 

31 ISBN: 978-3-540-42863-3. https://doi.org/10.1007/3-540-45578-7_43. 

32 https://www.researchgate.net/publication/220270875. 

333. Celso C. Ribeiro and Sebastián Urrutia. Heuristics for the Mirrored 

34 Traveling Tournament Problem. *European Journal of Operational Research* 

35 (EJOR) 179(3):775-787, June 16, 2007. 

36 https://doi.org/10.1016/j.ejor.2005.03.061. 

37 https://optimization-online.org/wp-content/uploads/2004/04/851.pdf. 

384. Sebastián Urrutia and Celso C. Ribeiro. Maximizing Breaks and Bounding 

39 Solutions to the Mirrored Traveling Tournament Problem. 

40 *Discrete Applied Mathematics* 154(13):1932-1938, August 15, 2006. 

41 https://doi.org/10.1016/j.dam.2006.03.030. 

42 

43So far, the following components have been implemented: 

44 

451. :mod:`~moptipyapps.ttp.instance` provides the data of a TTP instance, 

46 including the number of teams, the constraints, and the distance matrix. 

47 Notice that it is an extension of the Traveling Salesperson Problem 

48 :mod:`~moptipyapps.tsp.instance` instance data, from which it inherits the 

49 distance matrix. This data basically describes the starting situation and 

50 the input data when we try to solve a TTP instance. Also, the module 

51 provides several of the benchmark instances from 

52 <https://robinxval.ugent.be/>. 

532. :mod:`~moptipyapps.ttp.game_plan` provides a class for holding one 

54 candidate solution to the TTP, i.e., a game plan. The game plan states, for 

55 each day and each team, against which other team it will plan (if any). The 

56 game plan may contain errors, which need to be sorted out by optimization. 

573. :mod:`~moptipyapps.ttp.game_plan_space` offers the 

58 `moptipy` `Space` functionality for such game plans. In other words, it 

59 allows us to instantiate game plans in a uniform way and to convert them to 

60 and from strings (which is used when writing log files). 

614. :mod:`~moptipyapps.ttp.game_encoding` allows us to decode a permutation 

62 (potentially with repetitions, see :mod:`~moptipy.spaces.permutations`) 

63 into a game plan. We therefore can use optimization algorithms and 

64 operators working on the well-understood space of permutations to produce 

65 game plans. However, the decoded game plans may have errors, e.g., slots 

66 without games or violations of the maximum or minimum streak length 

67 constraints. 

685. :mod:`~moptipyapps.ttp.errors` offers an objective function that counts the 

69 number of such constraint violations in a game plan. If we can minimize it 

70 to zero, then the game plan is feasible. 

71 

72This is code is part of the research work of Mr. Xiang CAO (曹翔), a Master's 

73student at the Institute of Applied Optimization (应用优化研究所) of 

74the School of Artificial Intelligence and Big Data 

75(人工智能与大数据学院) at Hefei University (合肥大学) 

76in Hefei, Anhui, China (中国安徽省合肥市) under the supervision of 

77Prof. Dr. Thomas Weise (汤卫思教授). 

78"""