Coverage for moptipyapps / ttp / plan_length.py: 52%
52 statements
« prev ^ index » next coverage.py v7.13.0, created at 2025-12-11 04:40 +0000
1"""
2An objective computing the total travel length of all teams in a game plan.
4This objective function takes a game plan as argument and computes the total
5travel length for all teams.
6A :mod:`~moptipyapps.ttp.game_plan` is basically a matrix that, for each day
7(first dimension) stores against which each team (second dimension) plays.
8If a team plays at home (has a home game), its opponent is stored as a
9positive number.
10If the team has an away game, i.e., needs to visit the opponent, then this
11opponent is stored as a negative number.
12Team IDs go from `1` to `n`, i.e., a value in `1..n` indicates a home game
13and a value in `-n..-1` indicates an away game.
14The value `0` denotes a `bye`, i.e., that no game is scheduled for a team
15at the given day.
17The total game plan length is computed as follows:
191. the total length = 0
202. for each team,
21 1. start at the current location = home
22 2. for each day,
23 1. if the opponent number is negative, the next location is the
24 opponent's hometown;
25 2. else if the opponent number is positive, the next location is the
26 own hometown;
27 3. else (if the opponent number is 0): add the `bye penalty` to the
28 total length and jump to the next iteration
29 4. add the distance from the current to the next location to the total
30 length
31 5. set the current location = the next location
32 3. if the current location != own hometown, add the travel distance back
33 from the current location to the hometown to the total travel length.
35As penalty for the `bye` situation where no game is scheduled, we use twice
36the maximum distance between any two teams plus 1.
37The logic is that if a `bye` (i.e., a `0`) inserted into a game plan, it
38replaces one game. Since it replaces one game, it affects up to two travels,
39namely from the previous location to the game location and from the game
40location to the next location.
41So the optimization process could sneakily try to cut longer legs of the
42tournament by inserting a `bye`.
43The longest imaginable travel would be between the two cities that are
44farthest away from each other and back.
45By making the penalty for a `bye` exactly one distance unit longer than
46this longest imaginable distance, we ensure that the travel length can
47never be reduced by inserting a `bye`.
48Thus, having a `bye` is always more costly than any other travel it could
49replace.
50"""
53from typing import Final
55import numba # type: ignore
56import numpy as np
57from moptipy.api.objective import Objective
58from moptipy.utils.logger import KeyValueLogSection
59from pycommons.types import type_error
61from moptipyapps.ttp.game_plan import GamePlan
62from moptipyapps.ttp.instance import Instance
65@numba.njit(cache=True, inline="always", fastmath=True, boundscheck=False)
66def game_plan_length(
67 y: np.ndarray, distances: np.ndarray, bye_penalty: int) -> int:
68 """
69 Compute the total travel length of a game plan.
71 :param y: the game plan
72 :param distances: the distance matrix
73 :param bye_penalty: the penalty for `bye = 0` entries, i.e., days where
74 no game is scheduled
75 :returns: the total plan length
77 >>> yy = np.array([[ 2, -1, 4, -3],
78 ... [-2, 1, -4, 3],
79 ... [ 3, 4, -1, -2],
80 ... [-3, -4, 1, 2],
81 ... [ 4, 3, -2, -1],
82 ... [-4, -3, 2, 1]], int)
83 >>> dd = np.array([[ 0, 1, 2, 3],
84 ... [ 7, 0, 4, 5],
85 ... [ 8, 10, 0, 6],
86 ... [ 9, 11, 12, 0]], int)
87 >>> 0 + 1 + 7 + 2 + 8 + 3 + 9 # team 1
88 30
89 >>> 7 + 1 + 0 + 5 + 11 + 4 + 10 # team 2
90 38
91 >>> 0 + 6 + 9 + 2 + 10 + 4 # team 3
92 31
93 >>> 12 + 6 + 11 + 5 + 9 + 3 # team 4
94 46
95 >>> 30 + 38 + 31 + 46 # total sum
96 145
97 >>> game_plan_length(yy, dd, 0)
98 145
100 >>> yy[1, 0] = 0 # add a bye
101 >>> 0 + 25 + 0 + 2 + 8 + 3 + 9 # team 1
102 47
103 >>> game_plan_length(yy, dd, 2 * 12 + 1)
104 162
105 """
106 days, teams = y.shape # get the number of days and teams
107 length: int = 0
109 for team in range(teams): # for each team
110 current_location: int = team # start at home
111 for day in range(days): # for each day
112 next_location: int = y[day, team]
113 if next_location < 0: # away game at other team
114 next_location = (-next_location) - 1
115 elif next_location > 0: # home game at home
116 next_location = team
117 else: # bye = no game = penalty
118 length += bye_penalty
119 continue # team stays in current location
120 if current_location == next_location:
121 continue # no move
122 length += distances[current_location, next_location]
123 current_location = next_location
125 if current_location != team: # go back home
126 length += distances[current_location, team]
128 return int(length)
131class GamePlanLength(Objective):
132 """
133 Compute the total travel length of a game plan.
135 This objective function sums up all the travel lengths over all teams.
136 Days without game (`bye`) are penalized.
137 """
139 def __init__(self, instance: Instance) -> None:
140 """
141 Initialize the game plan length objective function.
143 :param instance: the TTP instance
144 """
145 if not isinstance(instance, Instance):
146 raise type_error(instance, "instance", Instance)
147 super().__init__()
149 #: the TTP instance
150 self.instance: Final[Instance] = instance
151 #: the bye penalty
152 self.bye_penalty: Final[int] = (2 * int(instance.max())) + 1
154 def evaluate(self, x: GamePlan) -> int:
155 """
156 Count the errors in a game plan as objective value.
158 :param x: the game plan
159 :return: the number of errors in the plan
160 """
161 return game_plan_length(x, x.instance, self.bye_penalty)
163 def lower_bound(self) -> int:
164 """
165 Obtain the lower bound for the travel length.
167 :return: `0`
168 """
169 return 0
171 def upper_bound(self) -> int:
172 """
173 Compute upper bound for the travel length: All `n*days*bye_penalty`.
175 :returns: `n * days * self.bye_penalty`
176 """
177 n: Final[int] = self.instance.n_cities
178 rounds: Final[int] = self.instance.rounds
179 days: Final[int] = (n - 1) * rounds
180 return n * days * self.bye_penalty
182 def is_always_integer(self) -> bool:
183 """
184 State that this objective function is always integer-valued.
186 :return: `True`
187 """
188 return True
190 def __str__(self) -> str:
191 """Get the name of this objective function."""
192 return "planLength"
194 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
195 """
196 Log the parameters of the instance to the given logger.
198 :param logger: the logger for the parameters
199 """
200 super().log_parameters_to(logger)
201 logger.key_value("byePenalty", self.bye_penalty)