Sports timetables need to satisfy a usually large set of constraints \(C\), which is partitioned into hard constraints \(C_{\text{hard}}\) and soft constraints \(C_\text{soft}\).
- Hard constraints represent fundamental properties of the timetable that can never be violated.
- Soft constraints, in contrast, rather represent preferences that should be satisfied whenever possible.
The validation of each constraint \(c\in C\) results in a vector \(D_c\) of \(n_c\) integral numbers, called the deviation vector \(D_c=[d_1 d_2 {\dots} d_{n_c}]\).
If a constraint is satisfied, all elements of its deviation vector are equal to zero.
Contrarily, the deviation vector of a violated constraint contains one or more strictly positive elements.
Apart from a description of how to calculate the deviation vector, each constraint features a cost function \(f_c\) and weight \(w_c\).
If constraint \(c\) is hard, i.e. under no conditions the constraint can be violated, a penalty \(p_c\) is added to the infeasibility value of the schedule.
If the constraint is soft, i.e. the constraint is desirable but not strictly necessarily, a penalty \(p_c\) is added to the objective value of the schedule.
Each constraint \(c\in C\) with weight \(w_c\) and penalty function \(f_c\) results in a penalty:
$$p_c=w_c\cdot f_c(D_c)$$
The software currently allows to specify the following five cost functions:
| Function |
Return value |
Description |
| Sum |
Sum of all deviations |
\(f_c^\mathrm{sum}(D_c) = \sum_{1\leq i \leq n_c} d_i\) |
| Sum-square |
Sum of all squared deviations |
\(f_c^\mathrm{sq-sum}(D_c) = (\sum_{1\leq i \leq n_c} d_i)^2\) |
| Square-sum |
Squared sum of all deviations |
\(f_c^\mathrm{sum-sq}(D_c) = \sum_{1\leq i \leq n_c} d_i^2\) |
| Minimum |
Minimum deviation |
\(f_c^\mathrm{min}(D_c) = \min_{1\leq i \leq n_c} d_i\) |
| Maximum |
Maximum deviation |
\(f_c^\mathrm{max}(D_c) = \max_{1\leq i \leq n_c} d_i\) |
The β-field lists around 20 constraints partitioned into five constraint groups that classify the vast majority of the constraints from the literature.
Base constraints (BA) are implicitly hard and always present and are therefore not mentioned in the beta field unless they are soft.
BA1
All specified games must be scheduled.
Each pair of teams \((i,j)\) triggers a deviation equal to the absolute difference of the number of required games \(g_{i,j}\) minus the number of scheduled games.
\(∀ i\in U, j\in U\setminus{\{i\}}: d_{i,j}= |g_{i,j}-\sum_{s\in P}x_{i,j,s}|\)
BA2
A team should play at most one game per time slot.
Each team triggers a deviation for every time slot equal to the number of games it plays more than one.
\(∀ i\in U, s\in P: d_{i,s} = max(0,\sum_{j\in U\setminus{\{i\}}}(x_{i,j,s}+x_{j,i,s})-1)\)
Capacity constraints (CA) force a team to play home or away and regulate the total number of games played by a team or team group.
CA1
Each team in team group \(T\) plays at least \(k_{min}\) and at most \(k_{max}\) {home games, away games, games} in time group \(S\).
Each team in \(T\) triggers a deviation equal to the number of home games in \(S\) less than \(k_{min}\) or more than \(k_{max}\).
\(∀ i\in T: d_i = \max (k_{\min}-\sum\limits_{j\in U}\sum\limits_{s\in S} x_{i,j,s}; \sum\limits_{j\in U}\sum\limits_{s\in S} x_{i,j,s} - k_{\max};0)\)
CA2
Each team in team group \(T_1\) plays at least \(k_{min}\) and at most \(k_{max}\) {home games, away games, games} against {teams, each team} in team group \(T_2\) in time group \(S\).
Each team in \(T_1\) triggers a deviation equal to the number of home games against teams in \(T_2\) in \(S\) less than \(k_{min}\) or more than \(k_{max}\).
\(∀ i\in T_1: d_i = \max (k_{\min}-\sum\limits_{j\in T_2}\sum\limits_{s\in S} x_{i,j,s}; \sum\limits_{j\in T_2}\sum\limits_{s\in S} x_{i,j,s} - k_{\max};0)\)
CA3
Each team in team group \(T_1\) plays at least \(k_{min}\) and at most \(k_{max}\) {home games, away games, games} against teams in team group \(T_2\) in each sequence of \(k\) {time slots, games}.
Each team in \(T_1\) triggers a deviation equal to the sum of the number of home games against teams in \(T_2\) less than \(k_{min}\) or more than \(k_{max}\) for each sequence of \(k\) time slots.
\(∀ i\in T_1: d_i =\sum\limits_{l=1}^{|P|-k+1}(\max(k_{\min}-\sum\limits_{j\in T_2}\sum\limits_{s=l}^{l+k-1}x_{i,j,s};\sum\limits_{j\in T_2}\sum\limits_{s=l}^{l+k-1}x_{i,j,s}-k_{\max};0))\)
CA4
Teams in team group \(T_1\) play at least \(k_{min}\) and at most \(k_{max}\) {home games, away games, games} against teams in team group \(T_2\) in {time group, each time slot of time group} \(S\).
Time group \(S\) triggers a deviation equal to the number of games with a home team in \(T_1\) and a team in \(T_2\) less than \(k_{min}\) or more than \(k_{max}\).
\(d=\max(k_{\min}-\sum\limits_{i\in T_1}\sum\limits_{j\in T_2}\sum\limits_{s\in S} x_{i,j,s}; \sum\limits_{i\in T_1}\sum\limits_{j\in T_2}\sum\limits_{s\in S} x_{i,j,s}-k_{\max};0)\)
CA5
Each team in team group \(T_1\) plays at least \(k_{min}\) and at most \(k_{max}\) away games against a team in team group \(T_2\) when it consecutively plays away during time group \(S\).
Each team in \(T_1\) triggers a deviation equal to the sum of the number of away games against teams in \(T_2\) less than \(k_{min}\) or more than \(k_{max}\) for each sequence of away games in \(S\).
\(∀ i\in T_1: d_i= \sum\limits_{s_1\in S}\sum\limits_{s_2\in S:s_2>s_1} a_{i,s_1,s_2}\max(k_{min}-\sum\limits_{j\in T_2}\sum\limits_{s_3=s_1}^{s_2}x_{j,i,s_3}; \sum\limits_{j\in T_2}\sum\limits_{s_3=s_1}^{s_2}x_{j,i,s_3}-k_{max};0)\)
Game constraints (GA) enforce or forbid specific assignments of a game to time slots.
GA1
At least \(k_{min}\) and at most \(k_{max}\) games from \(G = {(i_1, j_1), (i_2, j_2),\dots}\) take place in time group \(S\).
Time group \(S\) triggers a deviation equal to the number of games in \(G\) less than \(k_{\min}\) or more than \(k_{\max}\).
\(d=\max(k_{\min}-\sum\limits_{(i,j)\in G}\sum\limits_{s\in S}x_{i,j,s};\sum\limits_{(i,j)\in G}\sum\limits_{s\in S}x_{i,j,s}-k_{\max};0)\)
GA2
If a team from team group \(T_1\) plays a {home game, away game, game} against a team from team group \(T_2\) in time group \(S_1\) , then a team from team group \(T_3\) {plays, does not play} a {home game, away game, game} against a team from team group \(T_4\) in time group \(S_2\) .
Time group \(S_2\) triggers a deviation of 1 if a team in \(T_1\) plays a home game against a team in \(T_2\) in \(S_1\) but no team in \(T_3\) plays a home game against a team in \(T_4\) in \(S_2\), and 0 otherwise.
\(d=\max(\min(\sum\limits_{i\in T_1}\sum\limits_{j\in T_2}\sum\limits_{s\in S_1}x_{i,j,s},1)-\min(\sum\limits_{k\in T_3}\sum\limits_{l\in T_4}\sum\limits_{s\in S_2}x_{k,l,s}; 1);0)\)
Break constraints (BR) regulate the frequency and timing of breaks in a competition. Team \(i\) has a home break (resp. away) at time slot \(s\) if it plays home (resp. away) on time slot \(s\) and if \(i\)'s last game before \(s\) was also a home game (resp. away game), irrespective of the number of byes since its last game.
A team has a home stand in time group \(S\) if it plays multiple home games in a row and is on a road trip in \(S\) when it plays multiple away games in a row.
Unlike road trips and home stands, which are defined relative to \(S\), breaks are defined relative only to \(P\), the set of all time slots.
BR1
Each team in team group \(T\) has {exactly, no more than} \(k\) {home breaks, away breaks, breaks} in time group \(S\).
Each team in \(T\) triggers a deviation equal to the difference in the sum of home breaks in \(S\) and \(k\).
\(∀ i\in T: d_i= | k - \sum\limits_{s\in S} b_{i,s}h_{i,s}|\)
BR2
The sum over all {home, away, home or away} breaks of teams in team group \(T\) is {exactly, no more than} \(k\) in time group \(S\).
Team group \(T\) triggers a deviation equal to the difference in the sum of home breaks in \(S\) and \(k\).
\(d=|k-\sum\limits_{i\in T}\sum\limits_{s\in S} b_{i,s}h_{i,s}|\)
BR3
Each pair of teams in team group \(T\) has a difference in {home breaks, away breaks, breaks} that is not larger than \(k\).
Each pair of teams in \(T\) triggers a deviation equal to the difference in the number of home breaks more than \(k\).
\(∀ i,j\in T, i < j: d_{i,j}= \max(|\sum\limits_{s\in P}b_{i,s}h_{i,s} - \sum\limits_{s\in P}b_{j,s}h_{j,s}|-k,0)\)
BR4
Each team in team group \(T\) has at least \(k\) road trips in time group \(S\).
Each team in \(T\) triggers a deviation equal to the number of road trips in \(S\) less than \(k\).
\(∀ i\in T: d_i=\max(k-\sum\limits_{s_1\in S}\sum\limits_{\substack{s_2\in S: s_2>s_1}} a_{i,s_1,s_2};0)\)
The following constraints increase the fairness or attractiveness (FA) of competitions.
FA1
Each team in team group \(T\) has a difference in played home and away games that is not larger than \(k\) after each time slot in \(S\).
Each team in \(T\) triggers a deviation equal to the largest difference in played home and away games more than \(k\) over all time slots in \(S\).\
\(∀ i\in T: d_i = \max\limits_{s\in S}(|\sum\limits_{j\in T}\sum\limits_{1\leq p\leq s}(x_{i,j,p}-x_{j,i,p})|-k;0)\)
FA2
Each pair of teams in team group \(T\) has a difference in played {home games, away games, games} that is not larger than \(k\) after each time slot in \(S\).
Each pair of teams in \(T\) triggers a deviation equal to the largest difference in played home games more than \(k\) over all time slots in \(S\).
\(∀ i,j\in T, i < j: d_{i,j} = \max\limits_{s\in S}(|\sum\limits_{t\in T}\sum\limits_{1\leq p \leq s}(x_{i,t,p}-x_{j,t,p})|-k;0)\)
FA3
Each pair of teams in team group \(T\) plays each other at home and in turn away.
Each pair of teams in team group \(T\) triggers a deviation equal to the total number of times the two teams play consecutively with the same home-away assignment.
\(∀ i,j\in T, i < j: d_{i,j} = \sum\limits_{k=1}^{g_{i,j}+g_{j,i}-1} (1-|h_{i,j,k}-h_{i,j,k+1}|)\)
FA4
Team group \(T\) has a {weighted coe, coe} value of at most \(k\).
Team group \(T\) triggers a deviation equal to the weighted coe-value more than \(k\).
\(d = \max(\sum\limits_{i\in T}\sum\limits_{j\in T} w_{i,j}\, c_{i,j}^2 - k;0)\)
FA5
The total distance traveled by all teams in team group \(T\) during time group \(S\) is at most \(k\).
Team group \(T\) triggers a penalty equal to the total distance traveled more than \(k\).
\(d = \max(\sum\limits_{i\in T}\sum\limits_{s\in S}e_{i,s}-k;0)\)
FA6
The total cost associated with all games played during time group \(S\) is at most \(k\).
Time group \(S\) triggers a penalty equal to the total cost more than \(k\).
\(d = \max(\sum\limits_{i\in T}\sum\limits_{j\in T}\sum\limits_{s\in S}c_{i,j,s}x_{i,j,s}-k;0)\)
Finally, separation constraints regulate the number of time slots between consecutive games involving the same teams and regulate the symmetry of the timetable.
SE1
Each pair of teams in team group \(T\) has at least \(m_{min}\) and at most \(m_{max}\) {time slots, games} between two consecutive mutual games.
Time slot mode: Each pair of teams in \(T\) triggers a deviation equal to the sum of the number of time slots less than \(k\) for all consecutive mutual games. Game mode: Each pair of teams in \(T\) triggers a deviation equal to the sum of the number of games that team \(i\) has less than \(k\) for all consecutive mutual games and the sum of the number of games that team \(j\) has less than \(k\) for all consecutive mutual games.
Time slot mode: \(∀ i,j\in T, i < j: d_{i,j} = \sum\limits_{s_1\in P}\sum\limits_{s_1+1\leq s_2 \leq |P|} y_{i,j,s_1,s_2}\max(k-(s_2-s_1);0)\) Game mode: \(∀ i,j\in T, i < j: d_{i,j} = \sum_{s_1\in P} \sum_{s_1+1<= s_2 <= |P|} y_{i,j,s_1,s_2}(max(k-m_{i,s_1,s_2}; 0) + max(k-m_{j,s_1,s_2}; 0))\), with \(m_{i,s_1,s_2}=\sum_{j\in U\setminus{\{i\}}}\sum_{s3=s_1+1}^{s2-1}(x_{i,j,s_3}+x_{j,i,s_3})\).
SE2
If a pair of teams in team group \(T\) meets in one time slot of a pair of time slots in \(Q=\{\{s_1, s_2\}, \{s_3, s_4\}, \dots\}\), it also meets in the other time slot.
Each pair of time slots in \(Q\) triggers a deviation equal to the number of pairs of teams that play in one time slot but not in the other time slot.
\(∀ \{s_1,s_2\}\in Q: d_{\{s_1,s_2\}} = \sum\limits_{\{i,j\}\in T} |(x_{i,j,s_1}+x_{j,i,s_1})-(x_{i,j,s_2}+x_{j,i,s_2})|\)