moptipyapps.ttp package¶
The Traveling Tournament Problem (TTP).
The Traveling Tournament Problem (TTP) models the logistics of a sports league, where each game is defined as two teams playing against each other. In each time slot (let’s call that “day”) of the tournament, each team has one game against one other team. One of the two teams of each game will play “at home,” the other “away.”
In order to have each of the n teams play once against each of the n-1 other teams, we need to have n - 1 “days”. So in one round of the tournament, there are n - 1 time slots so that each of the teams can play exactly n - 1 games, i.e., once against every other team.
If the tournament has two rounds (i.e., is a double round-robin tournament), then each game appears twice, but with home and away team switched. There are also constraints for the minimum and maximum number of games at home in a row and away in a row. There are also constraints for the minimum and maximum number in between repeating a game (with home/away team switched).
David Van Bulck. Minimum Travel Objective Repository. RobinX: An XML-driven Classification for Round-Robin Sports Timetabling. Faculty of Economics and Business Administration at Ghent University, Belgium. https://robinxval.ugent.be/. In this repository, you can also find the original instance data, useful descriptions, and many links to related works.
Kelly Easton, George L. Nemhauser, and Michael K. Trick. The Traveling Tournament Problem Description and Benchmarks. In Principles and Practice of Constraint Programming (CP’01), November 26 - December 1, 2001, Paphos, Cyprus, pages 580-584, Berlin/Heidelberg, Germany: Springer. ISBN: 978-3-540-42863-3. https://doi.org/10.1007/3-540-45578-7_43. https://www.researchgate.net/publication/220270875.
Celso C. Ribeiro and Sebastián Urrutia. Heuristics for the Mirrored Traveling Tournament Problem. European Journal of Operational Research (EJOR) 179(3):775-787, June 16, 2007. https://doi.org/10.1016/j.ejor.2005.03.061. https://optimization-online.org/wp-content/uploads/2004/04/851.pdf.
Sebastián Urrutia and Celso C. Ribeiro. Maximizing Breaks and Bounding Solutions to the Mirrored Traveling Tournament Problem. Discrete Applied Mathematics 154(13):1932-1938, August 15, 2006. https://doi.org/10.1016/j.dam.2006.03.030.
So far, the following components have been implemented:
instanceprovides the data of a TTP instance, including the number of teams, the constraints, and the distance matrix. Notice that it is an extension of the Traveling Salesperson Probleminstanceinstance data, from which it inherits the distance matrix. This data basically describes the starting situation and the input data when we try to solve a TTP instance. Also, the module provides several of the benchmark instances from <https://robinxval.ugent.be/>.game_planprovides a class for holding one candidate solution to the TTP, i.e., a game plan. The game plan states, for each day and each team, against which other team it will plan (if any). The game plan may contain errors, which need to be sorted out by optimization.game_plan_spaceoffers the moptipy Space functionality for such game plans. In other words, it allows us to instantiate game plans in a uniform way and to convert them to and from strings (which is used when writing log files).game_encodingallows us to decode a permutation (potentially with repetitions, seepermutations) into a game plan. We therefore can use optimization algorithms and operators working on the well-understood space of permutations to produce game plans. However, the decoded game plans may have errors, e.g., slots without games or violations of the maximum or minimum streak length constraints.errorsoffers an objective function that counts the number of such constraint violations in a game plan. If we can minimize it to zero, then the game plan is feasible.
This is code is part of the research work of Mr. Xiang Cao (曹翔), a Master’s student at the Institute of Applied Optimization (应用优化研究所, http://iao.hfuu.edu.cn) of the School of Artificial Intelligence and Big Data (人工智能与大数据学院) at Hefei University (合肥学院) in Hefei, Anhui, China (中国安徽省合肥市) under the supervision of Prof. Dr. Thomas Weise (汤卫思教授). An objective that counts constraint violations. The idea is that we will probably not be able to always produce game plans that adhere to all the constraints imposed by a Traveling Tournament Problem We will hope that optimization can take care of this by applying this objective function here to get rid of them. In the documentation of function This objective function plays thus well with encodings that produce infeasible schedules, such as the very simple Bases: Compute the errors in a game plan. This objective function encompasses all the constraints imposed on standard TTP instances in one summarizing number. See the documentation of State that this objective function is always integer-valued. True Obtain the lower bound for errors: 0, which means error-free. 0 Compute upper bound for errors: (4*D - 1) * n - 1. Here D is the number of days, n is the number of teams, and D = (n - 1) * rounds. See the documentation of (4*D - 1) * n - 1 Compute the number of errors in a game plan. This method counts the total number of the violations of any of the following constraints over D = (n - 1) * rounds days for n-team tournaments, where rounds == 2 for double-round robin. The following kinds of errors are counted: If a team A plays a team B on a given day, then B must play against A on that day and if A plays at home, then B must play away. If not, then that’s an error. This can result in at most D * n errors, because each of the n teams has (at most) one game on each of the D days and if the other team could play against the wrong team (or does not play at all), then that’s one error. If a team has no other team assigned to play with, this is designated by value 0 and causes 1 error. This error also ends all ongoing streaks, i.e., may additionally lead to a streak violation of at most max(home_streak_min, away_streak_min) - 1. However, this cannot be more then two errors in sum per day (minus 1, for the first day). Also, this error is mutually exclusive with error 1. This can result in at most D * n + (D - 1) * n = (2*D - 1) * n errors. Since this error is also mutually exclusive with the errors from constraints 3 to 8 below, this gives us an upper bound of (2*D - 1) * n errors for all of the constraints (1-8) together. A team has a home streak shorter than home_streak_min. No such error can occur on the first day. This error is mutually exclusive with error 2, as the streak violation is already counted there. This can result in at most (D - 1) * n errors, but this number is shared with the following constraints (4-6), because a streak can only either be a home streak or an away streak but not both and it can either be too short or too long, but not both. A team has a home streak longer than home_streak_max. No such error can occur on the first day. This error is mutually exclusive with error 2. A team has an away streak shorter than away_streak_min. No such error can occur on the first day. This error is mutually exclusive with error 2, as the streak violation is already counted there. A team has an away streak longer than away_streak_max. No such error can occur on the first day. This error is mutually exclusive with error 2. Team A plays team B again before the team has played at least separation_min games against other teams. This error cannot occur on the first day and is mutually exclusive with error 2. There can be most 1 such error per day for any pairing of teams and there are n//2 pairings per day, giving us an upper bound of D * n//2 errors in total. This error is mutually exclusive with the next constraint 8 (and constraint 2). Team A plays team B again after the team has played more than separation_max games against other teams. This error cannot occur on the first day and is mutually exclusive with error 2. There can be most 1 such error per day for any pairing of teams and there are n//2 pairings per day, giving us an upper bound of D * n//2 errors in total. This error is mutually exclusive with the previous constraint 7 (and constraint 2). If team A plays team B at home a times, then team B must play team A at home at least a-1 and at most a+1 times. In total, we have D*n games. There cannot be more than (D*n) - 1 such errors. Notice that this kind of error can never occur if we use our Each pairing of teams occurs as same as often, namely rounds times, with rounds = 2 for double-round robin. In total, we have D*n games. There cannot be more than D*n such errors. Notice that this kind of error can never occur if we use our The violations are counted on a per-day basis. For example, if home_streak_max is 3 and a team has a home streak of length 5, then this counts as 2 errors. However, the errors are also counted in a non-redundant fashion: If a team A violates separation_min by, say, two days, then this counts as two errors. However, in this case, its opposing team B would have necessarily incured the exactly same violations. These are then not counted. As upper bound for the number of errors, we therefore have to add those of constraints 2, 9, and 10 and get (2*D - 1) * n + D*n - 1 + D*n, which gives us (4*D - 1) * n - 1, where `D = (n - 1) * rounds. The lower bound is obviously 0. y ( home_streak_min ( home_streak_max ( away_streak_min ( away_streak_max ( separation_min ( separation_max ( temp_1 ( temp_2 ( the total number of errors. 0 if the game plan is feasible A permutation-with-repetition-based encoding based on games. A point in the search space is a permutation (potentially with repetitions) that can be translated to a A game schedule for any round-robin tournament with any given number of rounds can then be represented as permutation (potentially with repetitions) of these game values. In the decoding procedure, it is processed from beginning to end each game is then placed into the earliest slot not already occupied by another game. In other words, it is placed at the earliest day at which both involved teams do not yet have other games. If no such slot is available, this game is not placed at all. In this case, there will be some zeros in the game plan after the encoding. No other constraint is considered at this stage. In other words, this encoding may produce game plans that violate constraints. It does not care about the streak length constraints. It does not ensure that each team always has a game. Therefore, it should only be used in conjunction with objective functions that force the search towards feasible solutions, such as the Bases: An encoding that transforms strings of games to game plans. Create a proper search space for this game-based encoding. The search space is a set of the search space Translate a permutation of games to a game plan. This is a straightforward decoding that places the games into the map one by one. Each game is placed at the earliest slot in which it can be placed. If a game cannot be placed, it is ignored. This will lead to many errors, which can be counted via the Create a proper search space for the given number of teams and rounds. If the instance prescribes a double-round robin tournament, then this is just the If an odd number of rounds is played, then it is not possible that all teams have the same number of games at home and away. Then, the permutation is generated such that, if the highest numbers of games at home for any team is k, no other team has less than k - 1 games at home. If the number of rounds is even, then all teams will have the same number of home and away games, that is, the number of teams divided by two and multiplied by the number of rounds. the search space A game plan assigns teams to games. A game plan is a two-dimensional matrix G. The rows are the time slots. There is one column for each time. If G has value v at row i and column j, then this means: at the time slot i … no team if v == 0, at home against the team v if v > 0, i.e., team v travels to the home stadium of team j+1 away against the team -v if v < 0, i.e., team j+1 travels to the home stadium of team -v and plays against them there Indices in matrices are zero-based, i.e., the lowest index for a row i is 0 and the lowest index for a column j is also 0. However, team names are one-based, i.e., that with 1. Therefore, we need to translate the zero-based column index j to a team name by adding 1 to it. This is just a numerical variant of the game plan representation given at <https://robinxval.ugent.be/RobinX/travelRepo.php>. Indeed, the str(…) representation of a game plan is exactly the table shown there. Of course, if G[i, j] = v, then G[i, v - 1] = -(j + 1) should hold if v > 0, for example. Vice versa, if v < 0 and G[i, j] = v, then G[i, (-v) - 1] = j + 1 should hold. Such constraints are checked by the The corresponding space implementation, Here we provide a The bin game plans object is defined in module Bases: An implementation of the Space API of for game plans. Create a game plan without assigning items to locations. the (empty, uninitialized) packing object Convert a string to a packing. Check if two bin game plans have the same contents. True if both game plans are for the same instance and have the same structure Log the parameters of the space to the given logger. logger ( Get the number of game plans. The values in a game plan go from -n..n, including zero, and we have days*n values. This gives (2n + 1) ** (days * n), where days equals (n - 1) * rounds and rounds is the number of rounds. In total, this gives (2n + 1) ** ((n - 1) * rounds * n). the number of possible game plans Check if a game plan is an instance of the right object. This method performs a superficial feasibility check, as in the TTP, we try to find feasible game plans and may have infeasible ones. All we check here is that the object is of the right type and dimensions and that it does not contain some out-of-bounds value. x ( TypeError – if any component of the game plan is of the wrong type ValueError – if the game plan is not feasible An instance of the Traveling Tournament Problem (TTP). The Traveling Tournament Problem (TTP) describes the logistics of a sports league. In this league, n teams compete. In each time slot, each team plays against one other team. In each game, one team plays at home and one team plays away with the other team. In each round, every team plays once against every other team. The league may have multiple David Van Bulck of the Sports Scheduling Research group, part of the Faculty of Economics and Business Administration at Ghent University, Belgium, maintains “RobinX: An XML-driven Classification for Round-Robin Sports Timetabling”, a set of benchmark data instances and results of the TTP. We provide some of these instances as resources here. You can also download them directly at <https://robinxval.ugent.be/RobinX/travelRepo.php>. Also, see <https://robinxval.ugent.be/> for more information. David Van Bulck. Minimum Travel Objective Repository. RobinX: An XML-driven Classification for Round-Robin Sports Timetabling. Faculty of Economics and Business Administration at Ghent University, Belgium. https://robinxval.ugent.be/ Kelly Easton, George L. Nemhauser, and Michael K. Trick. The Traveling Tournament Problem Description and Benchmarks. In Principles and Practice of Constraint Programming (CP’01), November 26 - December 1, 2001, Paphos, Cyprus, pages 580-584, Berlin/Heidelberg, Germany: Springer. ISBN: 978-3-540-42863-3. https://doi.org/10.1007/3-540-45578-7_43 https://www.researchgate.net/publication/220270875 Bases: An instance of Traveling Tournament Problem (TTP). Read a TTP instance from a robinX formatted XML file. the instance Load a TTP instance from a resource. Get lower and upper bounds in which the optimal plan length resides. These are the bounds for the optimal tour length of feasible solutions. If we know the feasible solution with the smallest possible tour length, then the Get a tuple of all the TTP instances available as resource. All instances of the robinX set provided here are symmetric. the tuple with the instance names Log the parameters of the instance to the given logger. logger ( An objective computing the total travel length of all teams in a game plan. This objective function takes a game plan as argument and computes the total travel length for all teams. A The total game plan length is computed as follows: the total length = 0 start at the current location = home if the opponent number is negative, the next location is the opponent’s hometown; else if the opponent number is positive, the next location is the own hometown; else (if the opponent number is 0): add the bye penalty to the total length and jump to the next iteration add the distance from the current to the next location to the total length set the current location = the next location if the current location != own hometown, add the travel distance back from the current location to the hometown to the total travel length. As penalty for the bye situation where no game is scheduled, we use twice the maximum distance between any two teams plus 1. The logic is that if a bye (i.e., a 0) inserted into a game plan, it replaces one game. Since it replaces one game, it affects up to two travels, namely from the previous location to the game location and from the game location to the next location. So the optimization process could sneakily try to cut longer legs of the tournament by inserting a bye. The longest imaginable travel would be between the two cities that are farthest away from each other and back. By making the penalty for a bye exactly one distance unit longer than this longest imaginable distance, we ensure that the travel length can never be reduced by inserting a bye. Thus, having a bye is always more costly than any other travel it could replace. Bases: Compute the total travel length of a game plan. This objective function sums up all the travel lengths over all teams. Days without game (bye) are penalized. State that this objective function is always integer-valued. True Log the parameters of the instance to the given logger. logger ( Compute the total travel length of a game plan. the total plan lengthSubpackages¶
Submodules¶
moptipyapps.ttp.errors module¶
ttp instance, so we will instead probably usually generate game plans that may contain errors.count_errors(), we explain the different types of errors that may occur and that are counted.game_encoding.Objectivecount_errors() for more information.count_errors().game_encoding as representation.game_encoding as representation.ndarray) – the game planint) – the minimum permitted home streak lengthint) – the maximum permitted home streak lengthint) – the minimum permitted away streak lengthint) – the maximum permitted away streak lengthint) – the minimum number of games between a repetitionint) – the maximum number games between a repetitionndarray) – a temporary n*(n-1)/2 integer array, which is used to hold, for each pairing, when the last game was playedndarray) – a temporary n,n integer array, which is used to hold, how often each team played each other team>>> count_errors(np.array([[-2, 1], [2, -1]], int),
... 1, 3, 1, 3, 1, 2, np.empty(1, int),
... np.empty((2, 2), int))
1
>>> count_errors(np.array([[2, -1], [-2, 1]], int),
... 1, 3, 1, 3, 1, 2, np.empty(1, int),
... np.empty((2, 2), int))
1
>>> count_errors(np.array([[ 2, -1, 4, -3],
... [ 4, 3, -2, -1],
... [-2, 1, -4, 3],
... [-4, -3, 2, 1],
... [ 3, 4, -1, -2],
... [-3, -4, 1, 2]], int),
... 1, 3, 1, 3, 1, 2, np.empty(6, int),
... np.empty((4, 4), int))
2
>>> count_errors(np.array([[ 2, -1, 4, -3],
... [ 4, 3, -2, -1],
... [-2, 1, -4, 3],
... [ 3, 4, -1, -2],
... [-4, -3, 2, 1],
... [-3, -4, 1, 2]], int),
... 1, 3, 1, 3, 1, 2, np.empty(6, int),
... np.empty((4, 4), int))
0
>>> count_errors(np.array([[ 2, -1, 4, -3],
... [ 4, 3, -2, -1],
... [ 3, 4, -1, -2],
... [-2, 1, -4, 3],
... [-4, -3, 2, 1],
... [-3, -4, 1, 2]], int),
... 1, 3, 1, 3, 1, 2, np.empty(6, int),
... np.empty((4, 4), int))
0
>>> count_errors(np.array([[ 2, -1, 4, -3],
... [ 4, 3, -2, -1],
... [ 3, 4, -1, -2],
... [-2, 1, -4, 3],
... [-4, -3, 2, 1],
... [-3, -4, 1, 2]], int),
... 1, 2, 1, 3, 1, 2, np.empty(6, int),
... np.empty((4, 4), int))
3
>>> count_errors(np.array([[ 2, -1, 4, -3],
... [ 4, 3, -2, -1],
... [ 3, 4, -1, -2],
... [-2, 1, -4, 3],
... [-4, -3, 2, 1],
... [-3, -4, 1, 2]], int),
... 1, 2, 1, 2, 1, 2, np.empty(6, int),
... np.empty((4, 4), int))
6
>>> count_errors(np.array([[ 2, -1, 4, -3],
... [ 4, 3, -2, -1],
... [ 3, 4, -1, -2],
... [-2, 1, -4, 3],
... [-4, -3, 2, 1],
... [-3, -4, 1, 2]], int),
... 1, 3, 1, 3, 1, 1, np.empty(6, int),
... np.empty((4, 4), int))
6
moptipyapps.ttp.game_encoding module¶
GamePlan. Each value v in the permutation represents a game to be played by two of the n teams. There are n(n-1) possible games between n teams, distinguishing home and away teams. Given a value v from 0..n(n-1)-1, we can get the zero-based index of the home team as home_idx = (game // (n - 1)) % n. The away index is computed in two steps, first we set away_idx = game % (n - 1) and if away_idx >= home_idx, we do away_idx = away_idy + 1. (Because a team can never play against itself, the situation that home_idx == away_idx does not need to be represented, so we can “skip” over this possible value by doing the away_idx = away_idy + 1 and thus get a more “compact” numeric range for the permutation elements.)errors objective.Encodingpermutations that represents all the games that can take place in the tournament. Depending on the number of rounds in the tournament, some games may appear multiple times. Home and away games are distributed in a fair and deterministic mannner between the teams.>>> inst = Instance.from_resource("circ4")
>>> inst.n_cities
4
>>> inst.rounds
2
>>> ";".join(map(str, GameEncoding(inst).search_space().blueprint))
'0;1;2;3;4;5;6;7;8;9;10;11'
>>> inst = Instance(inst.name, inst, inst.teams, inst.rounds,
... inst.home_streak_min, inst.home_streak_max,
... inst.away_streak_min, inst.away_streak_max,
... inst.separation_min, inst.separation_max)
>>> inst.rounds = 1 # modify number of rounds for copied instance
>>> ";".join(map(str, GameEncoding(inst).search_space().blueprint))
'1;2;3;7;8;10'
>>> inst.rounds = 3 # modify number of rounds for copied instance
>>> ";".join(map(str, GameEncoding(inst).search_space().blueprint))
'0;1;1;2;2;3;3;4;5;6;7;7;8;8;9;10;10;11'
>>> inst.rounds = 4 # modify number of rounds for copied instance
>>> ";".join(map(str, GameEncoding(inst).search_space().blueprint))
'0;0;1;1;2;2;3;3;4;4;5;5;6;6;7;7;8;8;9;9;10;10;11;11'
>>> inst.rounds = 5 # modify number of rounds for copied instance
>>> ";".join(map(str, GameEncoding(inst).search_space().blueprint))
'0;0;1;1;1;2;2;2;3;3;3;4;4;5;5;6;6;7;7;7;8;8;8;9;9;10;10;10;11;11'
errors objective.>>> from moptipy.utils.nputils import int_range_to_dtype
>>> teams = 2
>>> rounds = 2
>>> perm = search_space_for_n_and_rounds(teams, rounds).blueprint
>>> dest = np.empty((rounds * (teams - 1), teams),
... int_range_to_dtype(-teams, teams))
>>> map_games(perm, dest)
>>> print(dest)
[[ 2 -1]
[-2 1]]
>>> teams = 4
>>> rounds = 2
>>> perm = search_space_for_n_and_rounds(teams, rounds).blueprint
>>> dest = np.empty((rounds * (teams - 1), teams),
... int_range_to_dtype(-teams, teams))
>>> map_games(perm, dest)
>>> print(dest)
[[ 2 -1 4 -3]
[ 3 4 -1 -2]
[ 4 3 -2 -1]
:rtype: :sphinx_autodoc_typehints_type:`\:py\:obj\:\`None\``
[-2 1 -4 3]
[-3 -4 1 2]
[-4 -3 2 1]]
standard() permutations set. Otherwise, it will be a permutation where some elements are omitted (for rounds == 1) or duplicated (if rounds > 2).>>> ";".join(map(str, search_space_for_n_and_rounds(2, 2).blueprint))
'0;1'
>>> ";".join(map(str, search_space_for_n_and_rounds(2, 3).blueprint))
'0;1;1'
>>> ";".join(map(str, search_space_for_n_and_rounds(2, 4).blueprint))
'0;0;1;1'
>>> ";".join(map(str, search_space_for_n_and_rounds(2, 5).blueprint))
'0;0;1;1;1'
>>> ";".join(map(str, search_space_for_n_and_rounds(3, 1).blueprint))
'1;2;5'
>>> ";".join(map(str, search_space_for_n_and_rounds(3, 2).blueprint))
'0;1;2;3;4;5'
>>> ";".join(map(str, search_space_for_n_and_rounds(3, 3).blueprint))
'0;1;1;2;2;3;4;5;5'
>>> ";".join(map(str, search_space_for_n_and_rounds(4, 1).blueprint))
'1;2;3;7;8;10'
>>> ";".join(map(str, search_space_for_n_and_rounds(4, 2).blueprint))
'0;1;2;3;4;5;6;7;8;9;10;11'
>>> ";".join(map(str, search_space_for_n_and_rounds(4, 3).blueprint))
'0;1;1;2;2;3;3;4;5;6;7;7;8;8;9;10;10;11'
>>> ";".join(map(str, search_space_for_n_and_rounds(4, 4).blueprint))
'0;0;1;1;2;2;3;3;4;4;5;5;6;6;7;7;8;8;9;9;10;10;11;11'
>>> ";".join(map(str, search_space_for_n_and_rounds(4, 5).blueprint))
'0;0;1;1;1;2;2;2;3;3;3;4;4;5;5;6;6;7;7;7;8;8;8;9;9;10;10;10;11;11'
>>> ";".join(map(str, search_space_for_n_and_rounds(5, 1).blueprint))
'1;2;4;7;9;10;13;15;16;18'
>>> ";".join(map(str, search_space_for_n_and_rounds(5, 2).blueprint))
'0;1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;18;19'
>>> ";".join(map(str, search_space_for_n_and_rounds(5, 3).blueprint))
'0;1;1;2;2;3;4;4;5;6;7;7;8;9;9;10;10;11;12;13;13;14;15;15;16;16;17;18;18;19'
moptipyapps.ttp.game_plan module¶
errors objective function.game_plan_space, offers the functionality to convert strings to game plans as well as to instantiate them in a black-box algorithm.moptipyapps.ttp.game_plan_space module¶
Space of bin game plans.game_plan. Basically, it is a two-dimensional numpy array holding, for each day (or time slot) for each team the opposing team.Space>>> inst = Instance.from_resource("circ8")
>>> space = GamePlanSpace(inst)
>>> x = space.create()
>>> print(inst.rounds)
2
>>> print(inst.n_cities)
8
>>> x.shape
(14, 8)
>>> x.instance is inst
True
>>> type(x)
<class 'moptipyapps.ttp.game_plan.GamePlan'>
>>> inst = Instance.from_resource("circ6")
>>> space = GamePlanSpace(inst)
>>> y1 = space.create()
>>> y1.fill(0)
>>> y2 = space.from_str(space.to_str(y1))
>>> space.is_equal(y1, y2)
True
>>> y1 is y2
False
>>> inst = Instance.from_resource("circ4")
>>> space = GamePlanSpace(inst)
>>> y1 = space.create()
>>> y1.fill(0)
>>> y2 = space.create()
>>> y2.fill(0)
>>> space.is_equal(y1, y2)
True
>>> y1 is y2
False
>>> y1[0, 0] = 1
>>> space.is_equal(y1, y2)
False
KeyValueLogSection) – the logger for the parameters>>> space = GamePlanSpace(Instance.from_resource("circ6"))
>>> print((2 * 6 + 1) ** ((6 - 1) * 2 * 6))
6864377172744689378196133203444067624537070830997366604446306636401
>>> space.n_points()
6864377172744689378196133203444067624537070830997366604446306636401
>>> space = GamePlanSpace(Instance.from_resource("circ4"))
>>> space.n_points()
79766443076872509863361
>>> print((2 * 4 + 1) ** ((4 - 1) * 2 * 4))
79766443076872509863361
GamePlan) – the game planmoptipyapps.ttp.instance module¶
rounds. If there are two rounds, then each team plays against each other team once at home and once abroad. If a team plays at home (or abroad) several times in a row, this is called a “streak”. There are minimum and maximum streak length constraints defined, for both at home and abroad. Additionally, if team A plays a team B in one time slot, then the exact inverse game cannot take place in the next time slot. A minimum number of games must take place in between for separation. There can also be a maximum separation length.Instance>>> from os.path import dirname
>>> inst = Instance.from_file(dirname(__file__) + "/robinx/con20.xml")
>>> inst.name
'con20'
>>> insta = Instance.from_resource("bra24")
>>> insta.n_cities
24
>>> insta.name
'bra24'
>>> insta.teams[0]
'Atl.Mineiro'
>>> insta.teams[1]
'Atl.Paranaense'
>>> insta.rounds
2
>>> insta.home_streak_min
1
>>> insta.home_streak_max
3
>>> insta.away_streak_min
1
>>> insta.away_streak_max
3
>>> insta.separation_min
1
>>> insta.separation_max
46
game_plan objective function would return a value within these limits for this solution. The limits for the RobinX instance have been taken from https://robinxval.ugent.be/RobinX/travelRepo.php on 2024-05-10.>>> len(Instance.list_resources())
118
>>> len(Instance.list_resources(False, True))
0
>>> len(Instance.list_resources(True, False))
118
KeyValueLogSection) – the logger for the parameters>>> from moptipy.utils.logger import InMemoryLogger
>>> with InMemoryLogger() as l:
... with l.key_values("I") as kv:
:rtype: :sphinx_autodoc_typehints_type:`\:py\:obj\:\`None\``
... Instance.from_resource("gal4").log_parameters_to(kv)
... print(repr('@'.join(l.get_log())))
'BEGIN_I@name: gal4@class: moptipyapps.ttp.instance.Instance@nCities: 4@tourLengthLowerBound: 67@tourLengthUpperBound: 160@symmetric: T@dtype: h@rounds: 2@homeStreakMin: 1@homeStreakMax: 3@awayStreakMin: 1@awayStreakMax: 3@separationMin: 1@separationMax: 6@gamePlanDtype: b@END_I'
moptipyapps.ttp.plan_length module¶
game_plan is basically a matrix that, for each day (first dimension) stores against which each team (second dimension) plays. If a team plays at home (has a home game), its opponent is stored as a positive number. If the team has an away game, i.e., needs to visit the opponent, then this opponent is stored as a negative number. Team IDs go from 1 to n, i.e., a value in 1..n indicates a home game and a value in -n..-1 indicates an away game. The value 0 denotes a bye, i.e., that no game is scheduled for a team at the given day.ObjectiveKeyValueLogSection) – the logger for the parameters>>> yy = np.array([[ 2, -1, 4, -3],
... [-2, 1, -4, 3],
... [ 3, 4, -1, -2],
... [-3, -4, 1, 2],
... [ 4, 3, -2, -1],
... [-4, -3, 2, 1]], int)
>>> dd = np.array([[ 0, 1, 2, 3],
... [ 7, 0, 4, 5],
... [ 8, 10, 0, 6],
... [ 9, 11, 12, 0]], int)
>>> 0 + 1 + 7 + 2 + 8 + 3 + 9 # team 1
30
>>> 7 + 1 + 0 + 5 + 11 + 4 + 10 # team 2
38
>>> 0 + 6 + 9 + 2 + 10 + 4 # team 3
31
>>> 12 + 6 + 11 + 5 + 9 + 3 # team 4
46
>>> 30 + 38 + 31 + 46 # total sum
145
>>> game_plan_length(yy, dd, 0)
145
>>> yy[1, 0] = 0 # add a bye
>>> 0 + 25 + 0 + 2 + 8 + 3 + 9 # team 1
47
>>> game_plan_length(yy, dd, 2 * 12 + 1)
162