1 Introduction
Round-robin tournaments are abundantly used in all kinds of sport competitions, both in professional leagues, and in amateur leagues. The setting where each pair of teams meets once (single round robin (SRR)), or twice (double round robin (DRR)) has proven to be a very popular format to arrive at a ranking of the participating teams Goossens and Spieksma (2012). Very often, each team has a venue, and a match between two teams takes place at the venue of one of the two teams, meaning that one team plays home (H), while the other team plays away (A). Deciding upon the matches to be played in each round of a single or double round-robin tournament is known to be of great practical importance in scheduling professional leagues such as soccer competitions. Indeed, scheduling a round-robin tournament has attracted a lot of attention in the scientific literature Kendall et al. (2010), Van Bulck et al. (2020); a popular approach to do so is known as a first-break, then-schedule approach Nemhauser and Trick (1998). The relevance of the first-break, then-schedule approach is strengthened by the observation that, when scheduling multiple leagues consecutively, first-break then-schedule is able to take capacity considerations of clubs that have teams playing in different leagues, into account Davari et al. (2020). We now informally describe this approach (see Sect. 2 for more precise terminology).
First-break, then-schedule is a hierarchical approach consisting of two phases. In the first phase, each team receives a home-away pattern (HAP), i.e., it is specified for each round whether the team plays at its home venue, or not. Next, in the second phase, each match that needs to be played is assigned to a round; of course, for such an assignment of matches to be feasible, it must hold that each team plays at most one match in each round and that the assignment is compatible with the patterns from phase 1. In such a hierarchical approach, it is clear that the scheduling decision (which matches to play in which round) crucially depends on the HAP-set that is chosen in the first phase. For instance, it is conceivable that in the second phase, a set of constraints is revealed that are incompatible with the given HAP-set. This would need to be solved by either changing the HAP-set, or putting energy into mitigating the effects of violating that specific set of constraints.
Advertisement
The theme of this contribution is that not all HAP-sets have the same risk of leading to incompatible constraints. Indeed, some HAP-sets are more flexible than others. In Sect. 2, we give a number of definitions, and in Sect. 3 we introduce our measures for the flexibility of a HAP-set. We also show how single-break HAP-sets, in particular the canonical pattern set, behave with respect to these measures. In Sect. 4, we describe how to compute these measures using integer programming; we conclude in Sect. 5.
2 Preliminaries
We consider a time-constrained SRR with an even number of teams, denoted by \(2n, n \in {\mathbb {N}}\). To avoid trivialities, we assume \(2n \ge 4\). A match between two distinct teams i and j is denoted by an unordered pair \(\{i,j\}\), \(1 \le i \ne j \le 2n\). Every team plays every other team exactly once. A schedule is a specification of all \(\left( {\begin{array}{c}2n\\ 2\end{array}}\right) \) matches in \(2n-1\) rounds, including the venues. Thus, in a schedule every match \(\{i,j\}\) is assigned to a specific round, the venue of the match is specified, and every team must play exactly one match in every round. For a survey of round-robin scheduling, we refer to Rasmussen and Trick (2008) and Drexl and Knust (2007).
Although we restrict our analysis to SRRs, we claim that many of the ideas can be generalized to DRRs as well (or k-round-robin settings with \(k \ge 2\)). In particular, the definitions of the measures (see Sect. 3) can be generalized to DRRs. However, we want to point out that a match in a DRR tournament is generally seen as an ordered pair (i, j), rather than an unordered pair of teams. Indeed, whereas in a single round-robin tournament, the home advantage is to be decided in the schedule, a double round-robin tournament typically assumes that each team plays at home against each other team exactly once. Moreover, very often it is required that one encounter between a pair of teams occurs in the first half, whereas the other encounter occurs in the second half of the schedule; these two encounters should be separated by a given number of rounds. Taking such issues into account would impact the corresponding definitions for DRR tournaments. We now proceed with defining our terminology.
Definition 2.1
(based on Rasmussen and Trick 2008) A Home-away pattern (HAP) is a vector \(h = (h_1, h_2, \ldots ,\)\( h_{2n-1})\), where \(h_r \in \{H,A\}\) specifies whether a team that plays according to pattern h plays home or away in round r, with \(r = 1,2,\ldots ,2n-1\).
Advertisement
An important property of a HAP is formed by the occurrence of so-called breaks: the presence of two consecutive symbols that are identical (see de Werra 1981 and Goossens and Spieksma 2011). To simplify notation, we take a circular view of a HAP, i.e., we define \(h_0 \equiv h_{2n-1}\).
Definition 2.2
(based on Rasmussen and Trick 2008) A Home-Away Pattern h has a break in round r if \(h_{r-1} = h_r\), with \(r = 1,2, \ldots , 2n-1\). In case \(h_{r-1} = h_r = A\), we call the break an away-break, otherwise we call it a home-break.
Notice that, since \(2n-1\) is odd, and given our circular view of a HAP, any HAP has at least one break. Indeed, observe that a HAP that consists of alternating H’s and A’s has a single break in round 1. In fact, motivated by practice, we are interested in the number of breaks present in a HAP, and we define the break number of a HAP, denoted by bn(h), to capture this number.
Definition 2.3
The break-number of home-away pattern h equals \(bn(h) = |\{r:~h_{r-1}=h_r, r = 1,2, \ldots , 2n-1\}|\).
Definition 2.4
A home-away pattern h is called a single-break pattern if \(bn(h) = 1\).
Definition 2.5
(based on Rasmussen and Trick 2008) Two home-away patterns \(h^1, h^2\) are called complementary iff \(h_r^1 \ne h_r^2\) for each \(r = 1,2, \ldots , 2n-1\).
Notice that an entire HAP h is determined by the rounds in which its breaks occur and by its value in the final round. Thus, we can write a HAP h as follows: \(P^H(r_1,r_2, \ldots , r_{bn(h)})\), where h denotes a HAP that has (i) bn(h) breaks occurring in rounds \(r_1, r_2, \ldots , r_{bn(h)}\), and (ii) an H in the final round. In case HAP h has an A in its final round and has breaks in rounds \(r_1, r_2, \ldots , r_{bn(h)}\), we write \(P^A(r_1, r_2, \ldots , r_{bn(h)})\). Clearly, \(P^H(r_1,r_2, \ldots ,r_{bn(h)})\) and \(P^A(r_1,r_2, \ldots ,r_{bn(h)})\) are complementary patterns.
We sometimes omit the distinction between \(P^H,P^A\) and simply use P. When discussing complementary pairs of patterns, we denote by \(P^c\) the complement of HAP P.
Table 1
HAPs for the 2019–2020 top Dutch male tennis league
Round 1 | Round 2 | Round 3 | Round 4 | Round 5 | Round 6 | Round 7 | ||
|---|---|---|---|---|---|---|---|---|
Team 1 (Lewabo) | A | H | A | H | A | H | H | \(P^H(7)\) |
Team 2 (Spijkenisse) | A | H | A | H | H | A | H | \(P^H(5)\) |
Team 3 (Suthwalda) | H | A | H | A | H | A | H | \(P^H(1)\) |
Team 4 (Nieuwekerk) | H | A | H | A | A | H | A | \(P^A(5)\) |
Team 5 (Arnolduspark) | H | A | H | A | H | A | A | \(P^A(7)\) |
Team 6 (Leimonias) | A | H | A | H | H | A | A | \(P^A(5,7)\) |
Team 7 (Naaldwijk) | A | H | A | H | A | H | A | \(P^A(1)\) |
Team 8 (Kimbria) | H | A | H | A | A | H | H | \(P^H(5,7)\) |
As a real-life example illustrating this terminology, we consider the HAPs used by the professional Dutch tennis competition for teams in 2019, organized by the Royal Dutch Tennis Association. This is a competition between 8 teams who play a single round robin, according to the HAPs given in Table 1 (for the precise schedule, we refer to the KNLTB 2019). The first column shows the team’s names, and the next 7 columns describe the home-away patterns. The final column gives the corresponding description of the particular pattern.
We remark that many other real-life examples of SRR tournaments exist. For instance, the TATA Steel Chess tournament is organized as a single round robin, where playing with white (black) can be regarded as playing home (away) Lambers et al. (2020).
We now turn our attention to sets of HAPs; we define a HAP-set as follows:
Definition 2.6
A set of 2n HAPs of length \(2n-1\), denoted by \(F_{2n}\), is called a HAP-set. We call 2n the order of \(F_{2n}\).
A schedule is called compatible with a HAP-set if the set of HAPs implied by the schedule coincides with the given HAP-set. We formally define the following notions:
Definition 2.7
For each \(2n \ge 4\):
-
A HAP-set \(F_{2n}\) is feasible if there exists a schedule compatible with \(F_{2n}\).
-
A HAP-set \(F_{2n}\) is complementary, if for every pattern \(P(r_1,\dots ,r_b) \in F_{2n}\), also the complementary pattern \(P^c(r_1,\dots ,r_b) \in F_{2n}\).
-
A HAP-set \(F_{2n}\) is called single-break if each pattern \(h \in F_{2n}\) is a single-break pattern.
The HAP-set given in Table 1 is an example of a complementary HAP-set; 6 of the 8 HAPs are single-break, the remaining two patterns each have two breaks.
Identifying whether a given HAP-set is feasible is known as the pattern set feasibility problem. As far as we are aware, the complexity status of this problem is not settled; Miyashiro et al. (2003) describe a necessary condition for feasibility, see also Briskorn (2008), Horbach (2010). In addition, observe that when given a schedule compatible with a certain HAP-set for a SRR, one can (i) interchange any two rounds and (ii) change in a single round each H to an A, and vice versa, and arrive at another HAP-set that must be feasible.
We are primarily interested in feasible HAP-sets that consist of patterns with a limited number of breaks, as witnessed by the following definition.
Definition 2.8
For each \(2n \ge 4\), \(k \ge 1\), we define
$$\begin{aligned} {\mathcal {H}}_{2n,k} = \{F_{2n}: bn(h) \le k \text{ for } \text{ each } h \in F_{2n}, ~ F_{2n} \text { feasible}\}. \end{aligned}$$
In particular, \({\mathcal {H}}_{2n,1}\) is the collection of single-break HAP-sets of order 2n.
Finally, we point out that Definitions 2.1-2.8 can be generalized to double round-robin tournaments by using \(4n-2\) (instead of \(2n-1\)) rounds.
2.1 About single-break HAP-sets
Single-break HAP-sets are of special interest. de Werra (1981) showed that a feasible single-break HAP-set exists for any 2n teams. Furthermore, for single-break HAP-sets, the conditions of Miyashiro et al. (2003) have been (experimentally) shown to be sufficient for \(2n \le 26\) Miyashiro et al. (2003). de Werra (1981) showed that each feasible single-break HAP-set for 2n teams is complementary; as a consequence, in each round either 0 or 2 HAPs will feature a break. Notice that two teams with identical HAPs \(h^1,h^2 \in F_{2n}\) are never able to play against each other.
We can describe a feasible, single-break HAP-set \(F_{2n}\) quite compactly as follows. It follows from de Werra (1981) that out of the \(2n-1\) rounds, there are n pairwise distinct rounds in which two patterns have a break, one team having an away break, and the other having a home break. Let us denote these n rounds by \(r_i\), \(i=1, \ldots , n\).
We sort these \(r_i\)’s in increasing order. Next, we define the difference between consecutive rounds as follows: \(d_i = r_{i+1} - r_{i}\), \(i=1, \ldots , n\), where we use \(r_{n+1} \equiv r_1+2n-1\). So the sequence \(D=(d_1, d_2, \ldots , d_n)\) gives the break-gaps, i.e., the number of rounds between two consecutive breaks (notice that \(d_i \geqslant 1\), \(i=1, \ldots , n\)). We refer to this representation of a feasible, single-break HAP-set as the break-gap representation or D-notation (see also de Werra 1981 and Knust and Lücking 2009).
Not only can a feasible, single-break HAP-set \(F_{2n}\) be represented by a sequence \((d_1, d_2, \ldots , d_{n})\), it is also true that any set of n positive integers that sum to \(2n-1\) corresponds to a (set of) single-break HAP-sets (which is not necessarily feasible). Although a HAP-set, when specified in terms of \(r_i\) values, uniquely determines a corresponding D sequence, a D sequence can correspond to multiple HAP-sets with different \(r_i\)’s. Consider, for instance, \(n=2\) and the following two distinct HAP-sets: \(\{HAA, HHA, AHH, AAH\}\) and \(\{HAH, HHA, AHA, AAH\}\). The first one has \(r_1=2\) and \(r_2=3\) leading to \(D=(1,2)\), while the second one has \(r_1=1\) and \(r_2=2\), also leading to \(D=(1,2)\).
Furthermore, de Werra (1981) shows that a sequence D is feasible if and only if all cyclic permutations of D are feasible. Hence, without loss of generality, when dealing with single-break HAP-sets \(F_{2n}\), we will assume that the two (complementary) patterns with a break in round 1 are always present in \(F_{2n}\), and we restrict ourselves to the lexicographically largest sequence among this set of equivalent sequences.
A number of observations follow, where we identify a pattern with a team:
Observation 2.1
If two patterns \(h^1, h^2\) in a single-break HAP-set \(F_{2n}\) that start with the same symbol (i.e., \(h^1_1 = h^2_1\)) have their break in rounds \(r,r+1\), respectively, then in any feasible schedule, the corresponding match is played in round r.
This is explained in the following way. As \(h^1,h^2\) start with the same symbol, until round \(r-1\), we have \(h^1_j=h^2_j\), \(j=1, \ldots , r-1\). Then, since \(h^1\) has a break in round r, we get \(h^1_r\ne h^2_r\). However, as \(h^2\) has a break in round \(r+1\), we see that \(h^1_{r+1}=h^2_{r+1}\) and as both patterns are single break, \(h^1_{j}=h^2_{j}\) for \(r+1 \le j \le 2n-1\). Ergo, \(h^1,h^2\) can only play each other in round r.
Observation 2.2
If three patterns \(h^1, h^2, h^3\) in a single-break HAP-set \(F_{2n}\) that start with the same symbol (i.e., \(h^1_1 = h^2_1=h^3_1\)) have their break in rounds \(r,r+1,r+2\), respectively (so their breaks are consecutive), there is no feasible schedule. This can be seen because all three teams can only play each other in rounds \(r+1,r+2\), while they should play 3 matches in total. (This also follows from the condition in Miyashiro et al. 2003.)
Observation 2.3
If there is no team with a break in round \(r+1\), then round \(r+1\) is opposite to round r, i.e., for each \(h \in F_{2n}\), we have \(h_r \ne h_{r+1}\). Then, in every feasible schedule, the matches scheduled in round r can all be played in round \(r+1\), and vice versa (provided that we invert the team playing home and the team playing away).
One of the most popular single-break HAP-sets in practice is the canonical pattern set (CPS) of order 2n (see de Werra 1980); it is defined as follows.
Definition 2.9
The canonical pattern set of order 2n (\(CPS_{2n}\)) is the following single-break HAP-set: \(CPS_{2n} = \{P^A(2i-1), P^H(2i-1) : i = 1,\dots ,n\}\); its break-gap representation is \(D = (2,2, \ldots , 2, 1)\).
In other words, we can order the teams whose HAPs start with an H (A) such that the break-gap is 2 for any two consecutive teams, except for one pair of teams, for which the break-gap equals 1. This is indeed a possible representation, since \(\sum _i d_i = 2n-1\).
3 Measuring the flexibility of a HAP-set
Given a HAP-set \(F_{2n}\), we are interested in the diversity of the schedules that are compatible with \(F_{2n}\) (\(2n \ge 4\)). To make this concrete, we introduce three distinct measures called the width (Sect. 3.1), the fixed part (Sect. 3.2), and the spread (Sect. 3.3), and we show how the CPS fares on these measures.
3.1 Measure 1: the width
We call two schedules, each compatible with a given HAP-set \(F_{2n}\), distinct when there exists a match that is played in one round in schedule 1 and in another round in schedule 2. Let us define here a stronger notion of distinctness.
Definition 3.1
Two schedules, each compatible with a given HAP-set \(F_{2n}\), are match-distinct when each match is played in a different round (when comparing schedule 1 with schedule 2).
Using Definition 3.1, we define the width of a HAP-set:
Definition 3.2
The width of a HAP-set \(F_{2n}\), denoted by \(width(F_{2n})\), is the number of pairwise match-distinct schedules compatible with \(F_{2n}\).
For instance, if \(F_{2n}\) is infeasible, \(width(F_{2n})=0\), and if a HAP-set has width 2 (or higher), then there exist two schedules such that each match occurs in different rounds in the two schedules. As an example, the width of the HAP-set given in Table 1 equals 1, implying that no pair of match-distinct schedules compatible with that HAP-set exists. Further, we refer to Table 2 (right) for an example of a HAP-set with width 2.
We remark here that, in order to generalize the definition of width to DRR tournaments, it suffices to make a distinction between matches (i, j) and (j, i).
Single-break HAP-sets do not allow large width; in fact, there are always matches that must be played in a particular round, as witnessed by the following theorem.
Theorem 3.1
For each \(2n \ge 4\): width(\(F_{2n}) = 1\) for each \(F_{2n} \in {\mathcal {H}}_{2n,1}.\)
Proof
Consider the break-gap representation of any feasible single-break HAP-set \(F_{2n}\); as discussed in Sect. 2, it follows that the corresponding entries must sum to \(2n-1\). Clearly, when choosing n positive integers that sum up to \(2n-1\), there must be at least one ‘1’ among them. Since \(F_{2n}\) is complementary (de Werra 1981), there exist two pairs of patterns which have breaks in consecutive rounds. Then, Observation 2.1 shows that, in any schedule compatible with \(F_{2n}\), the corresponding two matches each have only one round where they can be played. Thus, \(\text{ width }(F_{2n}) = 1\), for each \(2n \ge 4\). \(\square \)
In fact, the argument above implies that any feasible HAP-set \(F_{2n}\) which contains two single-break patterns of the form \(P^H(r)\) and \(P^H(s)\) (or \(P^A(r)\) and \(P^A(s)\)) with \(|r-s|=1\) has width 1.
Theorem 3.1 is tight in the following sense: even when all patterns except one are single-break patterns, HAP-sets with width 2 exist. In fact, even for \(2n=4\), it is possible to find a HAP-set with width equal to 2 containing only one pattern that is not a single-break pattern. Such a HAP-set consisting of 4 teams is given by Q in the following example.
Table 2
On the left CPS\(_4\), on the right HAP-set Q
Team | R1 | R2 | R3 | Team | R1 | R2 | R3 |
|---|---|---|---|---|---|---|---|
1 | H | A | H | 1 | H | H | H |
2 | H | A | A | 2 | H | A | A |
3 | A | H | A | 3 | A | H | A |
4 | A | H | H | 4 | A | A | H |
The HAP-set on the left is \(CPS_4\); the HAP-set on the right differs from \(CPS_4\) in two entries and is given by \(Q=\{P^H(1,2,3), P^A(3), P^A(1), P^H(2)\}\). Both HAP-sets are compatible with two distinct schedules; however, there are two schedules compatible with HAP-set Q that are match-distinct, while this is not the case for \(CPS_4\). Table 3 displays two schedules compatible with \(CPS_4\), and two that are compatible with Q.
Table 3
S1, S2 are compatible with \(CPS_4\); S3, S4 are compatible with Q
Round | S1 | S2 | Round | S3 | S4 |
|---|---|---|---|---|---|
R1 | (1,3),(2,4) | (1,4),(2,3) | 1 | (1,3),(2,4) | (1,4),(2,3) |
R2 | (4,1),(3,2) | (3,1),(4,2) | 2 | (1,4),(3,2) | (1,2),(3,4) |
R3 | (1,2),(4,3) | (1,2),(4,3) | 3 | (1,2),(4,3) | (1,3),(4,2) |
Thus, while \(CPS_4\) has width 1, the HAP-set Q has width 2.
3.2 Measure 2: the fixed part
As can be deduced from Theorem 3.1, the width is a measure that does not differentiate between feasible single-break HAP-sets. Still, different feasible, single-break HAP-sets are not necessarily equal when it comes to the number of matches that must take place in the same round. Therefore, we introduce here a more refined measure that is able to do so.
Definition 3.3
The fixed part of a feasible HAP-set \(F_{2n}\), denoted by \(FP(F_{2n})\), is the number of matches that are played in the same round in every schedule compatible with \(F_{2n}\), for each \(2n \ge 4\).
Notice that if there is just a single schedule compatible with \(F_{2n}\), the value of this measure equals \(\left( {\begin{array}{c}2n\\ 2\end{array}}\right) \). Notice also that if the width of a HAP-set \(F_{2n}\) equals 2, it follows that \(FP(F_{2n}) = 0\). For example, the fixed part of the HAP-set given in Table 1 is 4. More in particular, it consists of the matches Team 1 - Team 7, Team 2 - Team 6, Team 3 - Team 5, and Team 4 - Team 8, which all have to be played in round 7.
The following lower and upper bounds for \(\text{ FP }(F_{2n})\) are readily obtained. Given a feasible, single-break HAP-set, let \((d_1, d_2, \ldots , d_n)\) be its break-gap representation. We use \(I = |i:d_i=1|\).
Lemma 3.1
For any feasible, single-break HAP-set \(F_{2n}\) (\(2n \ge 4\)), we have: \(2I \le FP(F_{2n}) \le nI\).
Proof
The lower bound follows from Observation 2.1 and the fact that a feasible, single-break HAP-set is complementary. To see the upper bound, consider a round in which no team has a break, say round r is such a round in a feasible HAP-set \(F_{2n}\). Since the HAP-set is feasible, there exists a schedule compatible with it. Since no team has a break in round r, we can interchange all matches in round \(r-1\) with all matches in round r (while inverting the home-away assignment) and arrive at another feasible schedule. Each occurrence of \(d_i=1\) reveals the presence of a round r in which two teams have a break, followed by a round \(r+1\) in which two other teams have a break. The interchange argument does not hold for the n matches in round r. \(\square \)
3.2.1 The FP of the CPS
We now proceed by investigating the FP of the CPS. We start by recalling the following definition and insights that come from Miyashiro et al. (2003).
Definition 3.4
Let \(U \subseteq F_{2n}\) be a subset of patterns of order 2n. We define, for each \(r \in \{1, \ldots , 2n-1\}\):
\(H_r(U)=|\{h \in U|~h_r = H\}|\),
\(A_r(U)=|\{h \in U|~h_r = A\}|\),
\(m^-_r(U)=\min \{H_r(U),A_r(U)\}\),
\(m^+_r(U)=\max \{H_r(U),A_r(U)\}\),
\(M^-_r(U)=\arg \min \{H_r(U),A_r(U)\}\).
Notice that the teams of a set U all have to play each other once in a feasible schedule, thus resulting in a total amount of \(\frac{|U|(|U|-1)}{2}\) matches that have to be scheduled between the teams of U. We introduce \(A(U)=\sum _r m^-_r(U)\), summing the maximum number of the matches within U that can be scheduled per round. Next, we define \(\alpha (U) = A(U)-\frac{|U|(|U|-1)}{2}\) and as observed in Miyashiro et al. (2003), if \(\alpha (U)<0\), the HAP-set is infeasible, since not all matches within U can be scheduled.
If \(\alpha (U)=0\), we say that U is tight, meaning that in every round r, exactly \(m^-_r(U)\) matches between teams in U have to be scheduled and that all teams \(t \in M^-_r(U)\) have to be scheduled against other teams of \(U\setminus M^-_r(U)\).
Now, to facilitate our analysis, we first identify subsets of patterns (teams) from the CPS that are tight.
Definition 3.5
For \(i=1, \ldots , \lfloor \frac{n}{2} \rfloor \):
$$\begin{aligned} U_i&= \{P^A(2n-(2i-1)), \ldots , P^A(2n\\&\qquad -1), P^H(1), P^H(3), \ldots , P^H(2i-1)\}, \\ U^c_i&= \{P^H(2n-(2i-1)), \ldots , P^H(2n\\&\qquad -1), P^A(1), P^A(3), \ldots , P^A(2i-1)\}. \end{aligned}$$
Notice that \(\{P^A(2n-1), P^H(1)\}=U_1 \subset U_2 \subset \ldots \subset U_{\lfloor \frac{n}{2} \rfloor }\) and that \(|U_i| = |U^c_i| = 2i\), \(1 \le i \le \lfloor \frac{n}{2} \rfloor \). We also identify a set of rounds as follows:
Definition 3.6
For \(i=1, \ldots , \lfloor \frac{n}{2} \rfloor \):
\(R_i = \{2n-2i+1, 2n-2i+2, \ldots , 2n-2\} \cup \{2n-1\} \cup \{1,2,\ldots , 2i-3, 2i-2\}\).
Observe that \(\{2n-1\}=R_1 \subset R_2 \subset \ldots \subset R_{\lfloor \frac{n}{2} \rfloor }\) and that \(|R_i| = 4i-3\), \(1 \le i \le \lfloor \frac{n}{2} \rfloor \). Indeed, notice that round \(2n-1 \in R_i\) for all \(i=1, \ldots , \lfloor \frac{n}{2} \rfloor \), and that with each unit increase of index i four rounds are added, two to the “left” of round \(2n-1\) and two to the “right” of round \(2n-1\).
Lemma 3.2
\(U_i\) is tight for each \(i=1, \ldots , \lfloor \frac{n}{2} \rfloor \).
Proof
Consider any fixed i with \(1 \le i \le \lfloor \frac{n}{2} \rfloor \). Observe that for any round \(r \notin R_i\) all patterns in \(U_i\) are identical, i.e., \(h^1_r = h^2_r\) for all \(h^1, h^2 \in U_i, r \notin R_i\). It follows that any match between a pair of teams within \(U_i\) takes place in a round from \(R_i\). Consider the first two rounds in some set \(R_i\), i.e., rounds \(2n-2i+1\) and \(2n-2i+2\). There is only one team in \(U_i\), which has a symbol in \(\{H,A\}\) that is different from the symbols of the other teams from \(U_i\) in these rounds, namely team \(P^A(2n-2i+1)\): the team that features a break in round \(2n-2i+1\). Thus, \(m^-_{2n-2i+1}(U_i) = m^-_{2n-2i+2}(U_i) = 1\). Next, for the third and fourth rounds in \(R_i\), i.e., rounds \(2n-2i+3\) and \(2n-2i+4\), there are two teams that have a symbol in \(\{H,A\}\) that is different from the symbols of the other teams from \(U_i\) in these rounds, namely team \(P^A(2n-2i+1)\) and \(P^A(2n-2i+3)\). This implies that \(m_{2n-2i+3}(U_i) = m_{2n-2i+4}(U_i) = 2\). In fact, continuing in this way, we see \(m^-_{2n-2i+j}=\lceil \frac{j}{2}\rceil \) and we arrive at \(m_{2n-1}(U_i) = \frac{|U_i|}{2}\). By symmetry, we claim that \(m^-_{2n-1-j} = m^-_{j}\) for \(j=1, 2, \ldots , 2i-2\). Thus, \(A(U_i) = \sum _{r=2n-2i+1}^{2i-2} m^-_r(U_i) = 1 + 1 + 2 + 2 + \ldots + \frac{|U_i|-2}{2}+\frac{|U_i|-2}{2}+ \frac{|U_i|}{2} + \frac{|U_i|-2}{2}+\frac{|U_i|-2}{2} + \ldots + 2 + 2 + 1 + 1 = \frac{|U_i|(|U_i|-1)}{2}\). It follows that \(U_i\) is tight. \(\square \)
We are now in a position to prove that, for schedules that are compatible with \(CPS_{2n}\), exactly n matches have precisely one round in which they can be played.
Theorem 3.2
For each \(2n \ge 4\): \(FP(CPS_{2n})=n\).
Proof
To prove this theorem, we (i) identify n matches, each of which, in any schedule compatible with \(CPS_{2n}\), can be played in one round only, and (ii) show that, for each other match, solutions exist where this match is played in different rounds.
Claim In any schedule compatible with \(CPS_{2n}\), all matches of the form \((P^A(2n-(2i-1)), P^H(2i-1))\) are played in round \(2n-1\), for \(i=1, \ldots , \lfloor \frac{n}{2} \rfloor \).
Proof
We prove this claim by induction. Clearly, the statement is true for \(i=1\) as round \(2n-1\) is the only round in which the match between the two teams \(P^A(2n-1)\) and \(P^A(1)\) can be played.
Suppose now the claim is true for \(i=1,2, \ldots , k-1\) (\(k-1 < \lfloor \frac{n}{2} \rfloor \)). As \(U_k\) is tight by Lemma 3.2, we know that \(t=P^A(2n-(2k-1))\) has to be scheduled against a team in \(U_k\) in every round where \(t\in M^-_r(U_k)\). This is true for the rounds \(2(k-1)-1,\dots ,2n-1\). Notice that in round \(2n-1\), by the induction hypothesis, all teams in \(U_{k-1}\) are already scheduled against teams from \(U_{k-1}\); thus, t has to be scheduled against a team in \(U_{k}\setminus U_{k-1} = \{t,P^H(2k-1)\}\). Therefore, the match \((P^A(2n-(2k-1)),P^H(2k-1))\) has to be scheduled in round \(2n-1\). \(\square \)
By symmetry, it follows that a similar analysis for the teams from the sets \(U^c_i\), \(1 \le i\le \lfloor \frac{n}{2} \rfloor \) implies that all teams from these sets play a match that can only be played in round \(2n-1\). Together with the claim, this means that we have shown that \(\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{2} \rfloor \) matches can only be played in round \(2n-1\). If n is odd, this leaves out two teams: \(P^A(n)\) and \(P^H(n)\). However, since these two teams have to play some match in round \(2n-1\), and as all other teams are already paired, they have to play each other. Thus, in any feasible schedule compatible with the CPS, the entire round \(2n-1\) consists of matches that can only be played in this round.
Finally, we point out that, due to Observation 2.3, in any feasible schedule compatible with \(CPS_{2n}\), the matches in round r can be interchanged with the matches in round \(r+1\) (\(r-1\)) if r is odd (even), for \(r=1, \ldots , 2n-2\). This proves the theorem. \(\square \)
Observe that the proof of Theorem 3.2 implies that all matches in the last round of a schedule compatible with a CPS are fixed, i.e., these matches cannot be played in any other round.
3.3 Measure 3: the spread
Given a HAP-set, we call the spread of a match \(\{i,j\}\) the number of distinct rounds in which it can be played, i.e., for which there is a schedule compatible with the given HAP-set that has this match in this round. Notice that this is not necessarily equal to the number of rounds r where \(h^i_r\) and \(h^j_r\) differ. Next, by simply summing the spread of a match over all matches, we arrive at the spread of a HAP-set. Formally:
Definition 3.7
The spread of match \(\{i,j\}\) with respect to feasible HAP-set \(F_{2n}\) is denoted by \(spr(i,j) = \)
$$\begin{aligned}&|\{r:~\exists \text{ a } \text{ schedule } S \text{ compatible } \text{ with } F_{2n} \text{ where } \text{ match } \{i,j\}\\ {}&\text{ is } \text{ in } \text{ round } r\}|. \end{aligned}$$
Definition 3.8
The spread of a HAP-set \(F_{2n}\) is the sum, over the matches, of the spread of a match, i.e., \(spread(F_{2n}) = \sum _{\{i,j\}} spr(i,j)\).
A higher value of the spread for a feasible HAP-set indicates more flexibility in scheduling individual matches. As an example, the spread of the HAP-set given in Table 1 is 84 (16 matches can be played in 4 rounds, 8 matches have 2 possible rounds, and the fixed part consists of 4 matches). We now state an upper bound on the spread of CPS\(_{2n}\).
Theorem 3.3
$$\begin{aligned} spread\left( CPS_{2n}\right)&\le \frac{n}{6}\left( 10n^2-9n+11\right) -\lceil \frac{n}{2}\rceil . \end{aligned}$$
Proof
First, we derive an upper bound for the spread of each individual match; then, we sum these upper bounds to obtain the result. As we identify each team with a pattern \(P^H(2i+1)\) or \(P^A(2i+1)\) \(0 \le i,j \le 2n-1\), a match is either of the form \((P^H(2i+1), P^H(2j+1))\) or \((P^A(2i+1), P^A(2j+1))\) (with \(i < j\)), or it is of the form \((P^H(2i+1), P^A(2j+1))\) (with \(i,j = 0,\dots ,n-1\)). We refer to the former set of matches as matches of Type 1 and to the latter set of matches as matches of Type 2. Obviously:Consider a match of Type 1. Given two teams \(P^H(2i+1)\), \(P^H(2j+1)\) with \(0 \le i < j \le n-1 \), their HAPs differ in the rounds \(R_{i,j}:=[2i+1,2j]\). As two teams can only be scheduled in rounds where they have a different HAPs, it follows immediately that, for each \(0 \le i < j \le n-1\):Using (2), we are able to bound the sum of the spreads of the corresponding matches; we find for \(2n \ge 4\):Notice that we also need to count the spreads of the matches \((P^A(2i+1),P^A(2j+1))\); by symmetry, their sum will also be upper bounded by \(Z_{1,2n}\), which leads to:Consider now a match of Type 2. Two teams \(P^H(2i+1),P^A(2j+1)\) have different HAPs in rounds \(R^c_{i,j}:=[1,2\min (i,j)]\cup [2\max (i,j)+1,2n-1]\). It follows that the spread of a match between two such teams obeys, for each \(i,j = 0,\ldots , n-1\):However, here we can prove better bounds. We distinguish three cases when looking at matches of Type 2. We assume \(i\le j\), as the analysis is similar if \(i\ge j\).
$$\begin{aligned} spread\left( CPS_{2n}\right)= & {} \sum \limits _{i < j} (spr(P^H(2i+1),P^H(2j+1)) \nonumber \\&+spr(P^A(2i+1),P^A(2j+1))) \nonumber \\&{+} \sum _{i{=}0}^{n{-}1} \sum _{j{=}0}^{n{-}1} spr(P^H(2i{+}1), P^A(2j+1)). \nonumber \\ \end{aligned}$$
(1)
$$\begin{aligned} spr(P^H(2i+1),P^H(2j+1)) \le |R_{i,j}| = 2(j-i). \end{aligned}$$
(2)
$$\begin{aligned}&\sum \limits _{i < j} spr(P^H(2i+1),P^H(2j+1)) \\&\quad \le \sum _{j=1}^{n}\sum _{i=0}^{j-1}2(j-i) \\&\quad = \sum _{j=1}^{n-1}j(j+1) = \\&\quad = \frac{1}{6}(n-1)n(2n-1)+\frac{n(n-1)}{2} \\&\quad = \frac{1}{6}((n-1)n(2n-1) + 3n(n-1)) =: Z_{1,2n}. \end{aligned}$$
$$\begin{aligned}&\sum \limits _{i < j} (spr(P^H(2i+1),P^H(2j+1)) \nonumber \\&\quad + spr(P^A(2i+1),P^A(2j+1))) \le 2Z_{1,2n}. \end{aligned}$$
(3)
$$\begin{aligned} spr(P^H(2i+1),P^A(2j+1)) \le |R^c_{i,j}|. \end{aligned}$$
(4)
Case 1
\(i=n-j-1.\)
From the proof of Theorem 3.2, we get immediately that the match \((P^H(2i+1),P^A(2j+1))\) can be scheduled in round \(2n-1\) if and only if \(i=n-j-1\); obviously, in this case, the spread of this match is equal to 1. Hence, for \(i,j = 0,\ldots , n-1\) with \(i=n-j-1\):
$$\begin{aligned} \qquad \quad spr(P^H(2i+1),P^A(2j+1)) = 1. \end{aligned}$$
(5)
Case 2
\(i < n-j-1.\)
From Definition 3.5, it follows that \(P^H(2i+1)\in U_i\), which is a tight set by Lemma 3.2. This means that in rounds [1, 2i], \(P^H(2i+1)\) has to be scheduled against 2i teams from \(U_i\). As \(P^A(2j'+1) \in U_i\) if and only if \(n-j'-1 \le i\), \(P^A(2j+1) \not \in U_i\). Therefore, \((P^H(2i+1),P^A(2j+1))\) cannot be scheduled in [1, 2i]. Since, in addition, round \(2n-1\) is not available, it follows that this match can only be played in one of the rounds in \([2j+1, 2n-2]\) . We conclude, for \(i,j = 0,\ldots , n-1\) with \(i<n-j-1\):
$$\begin{aligned}&\qquad spr(P^H(2i+1),P^A(2j+1)) \le 2(n-j-1). \nonumber \\ \end{aligned}$$
(6)
Case 3
\(i > n-j-1.\)
We apply a similar argument as in Case 2. In this case, we observe that \(U_{n-j-1}\) is tight, which means that \(P^A(2j+1)\) can only play teams from \(U_{n-j-1}\) in rounds \([2j+1,2n-2]\), and \(P^H(2i+1) \not \in U_{n-j-1}\) as \(i > n-j-1\). Therefore, \((P^H(2i+1),P^A(2j+1))\) cannot be scheduled in \([2j+1,2n-1]\), and must be scheduled in [1, 2i]. It follows that, for \(i,j = 0,\ldots , n-1\) with \(i>n-j-1\):
$$\begin{aligned} \qquad \quad spr(P^H(2i+1),P^A(2j+1)) \le 2i. \end{aligned}$$
(7)
We now derive an upper bound for the sum of the spreads of a subset of the matches of Type 2. Let \(\lfloor \frac{n}{2}\rfloor =k\), so \(n = 2k\) if n is even, and \(n = 2k+1\) if n is odd. We use the right-hand sides of expressions (5), (6), and (7), to obtain an upper bound for the sum of the spreads of the subset of the matches of Type 2, where we let i vary from 0 till \(k-1\); we find for each \(2n \ge 4\):In the above derivations, validity of the inequality follows from inequalities (5), (6), and (7). Notice that \(Z_{2,2n}\) is the result of the sum of the upper bounds of the spreads corresponding to the matches (\(P^H(2i+1),P^A(2j+1)\)), where \(i < k\). By symmetry, \(Z_{2,2n}\) is also equal to the sum of the spreads corresponding to matches (\(P^H(2i+1),P^A(2j+1)\)) where \(i \ge n-k\) (recall that \(k = \lfloor \frac{n}{2} \rfloor \)). If n is even, this would mean \(k = n-k\) and the sum over all upper bounds is equal to \(Z_{2,2n}\), leading to:If n is odd, we still need to bound the spread of the matches \((P^H(2k+1),P^A(2j+1)\) where \(j\ge k\), and \((P^A(2k+1),P^H(2j+1))\) where \(j>k\). It is not difficult to see that the sum of the spread of these matches is bounded from above by \(Z_{odd} = 2k\cdot k + 1 + 2k\cdot k = 4k^2 + 1\), leading to:Combining (1), (3) and (8), for even n we get an upper bound of:Combining (1), (3) and (9), for odd n we get an upper bound of:When n is even, \(3n = 6\lceil \frac{n}{2}\rceil \), and when n is odd, \(3n = 6\lceil \frac{n}{2}\rceil -3\). Therefore, we can write, for any n, that:This finishes the proof. \(\square \)
$$\begin{aligned}&\sum _{i=0}^{k-1} \sum _{j=0}^{n-1} spr(P^H(2i+1),P^A(2j+1)) = \\&\quad =\sum _{i=0}^{k-1} \sum _{j=i}^{n-1} spr(P^H(2i+1),P^A(2j+1))\\&\qquad + \sum _{i=0}^{k-1} \sum _{j=0}^{i-1} spr(P^H(2i+1),P^A(2j+1)) = \\&\quad = \sum _{i=0}^{k-1} \sum _{j:i=n-j-1}spr(P^H(2i+1),P^A(2j+1)) \\&\qquad + \sum _{i=0}^{k-1} \sum _{j:j<n-i-1}spr(P^H(2i+1),P^A(2j+1)) \\&\qquad +\sum _{i=0}^{k-1} \sum _{j:j>n-i-1}spr(P^H(2i+1),P^A(2j+1)) \\&\qquad + \sum _{i=0}^{k-1}\sum _{j=0}^{i-1}spr(P^H(2i+1),P^A(2j+1)) \le \\&\quad \le \sum _{i=0}^{k-1}[1+\sum _{j=i}^{n-i-2}2(n-j-1)\\&\qquad +\left( \sum _{j=n-i}^{n-1}2i\right) + \sum _{j=0}^{i-1}2(n-i-1)] = \\&\quad = \sum _{i=0}^{k-1} [1 + n(n-2i-1) +2i\cdot i+ 2i(n-i-1)] = \\&\quad =\sum _{i=0}^{k-1} [1 + n^2 - n - 2i] \\&\quad = k(n^2-n+1) - k(k-1) =: Z_{2,2n}. \end{aligned}$$
$$\begin{aligned} \sum _{i=0}^{n-1} \sum _{j=0}^{n-1} spr(P^H(2i+1),P^A(2j+1)) \le 2Z_{2,2n}. \end{aligned}$$
(8)
$$\begin{aligned} \sum _{i=0}^{n-1} \sum _{j=0}^{n-1} spr(P^H(2i+1),P^A(2j+1)) \le 2Z_{2,2n} + Z_{odd}.\nonumber \\ \end{aligned}$$
(9)
$$\begin{aligned}&spread\left( CPS_{2n}\right) \le 2Z_{1,2n} + 2Z_{2,2n} = \\&\quad = \frac{1}{6}(2(n-1)n(2n-1) \\&\qquad + 6n(n-1)) + 2k(n^2-n+1) - 2k(k-1) = \\&\quad = \frac{1}{6}(4n^3-6n^2+2n+6n^2-6n\\&\qquad +6n^3-6n^2+6n-6n(k-1)) = \\&\quad = \frac{1}{6}(10n^3-6n^2+8n - 6n k) = \\&\quad = \frac{1}{6}(10n^3 - 9n^2 + 8n). \end{aligned}$$
$$\begin{aligned}&spread\left( CPS_{2n}\right) \le 2Z_{1,2n} + 2Z_{2,2n} + 4k^2+1 =\\&\quad = \frac{1}{6}(2(n-1)n(2n-1) \\&\qquad + 6n(n-1)) + 2k(n^2-n+1) \\&\qquad - 2k(k-1) + 4k^2 + 1 = \\&\quad = \frac{1}{6}(2(n-1)n(2n-1) + 6n(n-1) \\&\qquad + 6(n-1)(n^2-n+1) + 12k(k+1) + 6) = \\&\quad = \frac{1}{6}(10n^3 - 12n^2 + 8n + 6(n-1)(k+1) + 6) = \\&\quad = \frac{1}{6}(10n^3 - 6n^2 + 8n -6(nk-k+n)) = \\&\quad = \frac{1}{6}(10n^3 - 9n^2 + 8n + 3). \end{aligned}$$
$$\begin{aligned} spread\left( CPS_{2n}\right)&\le \frac{1}{6}(10n^3 - 9n^2 + 11n)-\lceil \frac{n}{2}\rceil . \end{aligned}$$
We can calculate the actual value of the spread of CPS\(_{2n}\) using integer programming (see Sect. 4). In Table 4, we explicitly list the value of the spread of CPS\(_{2n}\) and its upper bound for values of 2n up to 30, and note that this bound is tight. In fact, we conjecture that this bound is tight for any even number of teams.
Table 4
Values for the spread and the upper bound for CPS with 2n teams
2n | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 | 22 | 24 | 26 | 28 | 30 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
upper bound | 10 | 35 | 88 | 177 | 314 | 507 | 768 | 1105 | 1530 | 2051 | 2680 | 3425 | 4298 | 5307 |
spread(CPS) | 10 | 35 | 88 | 177 | 314 | 507 | 768 | 1105 | 1530 | 2051 | 2680 | 3425 | 4298 | 5307 |
Conjecture 3.1
$$\begin{aligned} spread\left( CPS_{2n}\right)&= \frac{n}{6}\left( 10n^2-9n+11\right) -\lceil \frac{n}{2}\rceil . \end{aligned}$$
4 Computing the measures
In Sect. 4.1, we introduce two mathematical formulations that are instrumental in computing the flexibility measures proposed earlier. In Sect. 4.2, we present computational results for single-break HAP-sets.
4.1 Mathematical formulations
In order to check whether a given HAP-set \(F_{2n}\) has a width of at least W, we develop a feasibility integer programming (IP) formulation, such that if this formulation has a feasible solution, W pairwise match-distinct schedules can be constructed that are compatible with \(F_{2n}\). The given HAP-set consist of 2n HAPs \(h^i\), represented by the parameter \(h^i_r\) which equals 1 if \(h^i\) has a home game on round r and 0 otherwise. We refer to \(t_i\) as the team that plays according to HAP \(h^i\). The binary decision variable \(x^w_{i,j,r}\) equals 1 if in schedule w, \(t_i\) is playing a home game against team \(t_j\) on round r, and 0 otherwise. We use R to denote the set of rounds {\(1,2,...,2n-1\)}.Constraints (10) enforce that each match is played exactly once in each schedule, while constraints (11) make sure that each team plays exactly one match per round in each schedule. Constraints (12) and (13) accomplish that a home match for \(t_i\) against \(t_j\) can only be scheduled on round r if \(h^i\) features a home match and \(h^j\) specifies an away match on that round. The fact that all W schedules need to be pairwise match-distinct is enforced by constraints (14).
$$\begin{aligned}&\sum _{r \in R} (x^w_{i,j,r} + x^w_{j,i,r}) = 1&\forall i,j \in F_{2n}: i \ne j, w \in \{1,\ldots ,W\} \end{aligned}$$
(10)
$$\begin{aligned}&\sum _{j \in F_{2n}} (x^w_{i,j,r} + x^w_{j,i,r}) = 1&\forall i \in F_{2n}, r \in R, w \in \{1,\ldots ,W\} \end{aligned}$$
(11)
$$\begin{aligned}&x^w_{i,j,r} \le h^i_r&\forall i,j \in F_{2n}, r \in R, w \in \{1,\ldots ,W\} \end{aligned}$$
(12)
$$\begin{aligned}&x^w_{i,j,r} \le 1 - h^j_r&\forall i,j \in F_{2n}, r \in R, w \in \{1,\ldots ,W\} \end{aligned}$$
(13)
$$\begin{aligned}&\sum \limits _{w=1}^{W} x^w_{i,j,r} \le 1&\forall i,j \in F_{2n}, r \in R \end{aligned}$$
(14)
$$\begin{aligned}&x^w_{i,j,r} \in \{0,1\}&\forall i,j \in F_{2n}, r \in R, w \in \{1,\ldots ,W\} \end{aligned}$$
(15)
The width of a HAP-set \(F_{2n}\) can be determined by solving formulation (10)–(15) by a binary search on potential values for W. Moreover, it is possible to adapt this formulation to study properties of patterns that allow the existence of a feasible HAP-set with width at least W. This can be done by treating the \(h^i_r\) parameters as variables and then adding constraints on these to reflect the properties one wants the patterns to have. Furthermore, an objective function, e.g., minimizing the total number of breaks, could be added.
To compute the FP, we consider the model above for \(W=2\), where we, for a given match between \(t_{i'}\) and \(t_{j'}\), replace constraints (14) with
This yields a feasibility IP that allows to check whether or not the match between \(t_{i'}\) and \(t_{j'}\) is part of the fixed part of HAP-set \(F_{2n}\). FP\((F_{2n})\) is then obtained by summing the number of IPs that are infeasible over all matches {\(t_{i'}\), \(t_{j'}\)}.
(16)
Probably the most challenging measure, from a computational point of view, is the spread. When we consider formulation (10)–(15) for \(W=1\), formulation (17)–(21) arises. Note that we dropped the index w in the x variables and that constraint (14) is now redundant. Consider now a match between \(t_{i'}\) and \(t_{j'}\), to be played in a particular round \(\ell \) (regardless of the home advantage) as enforced by constraint (22).The idea is that by solving the resulting feasibility IP for each match between \(t_{i'}\) and \(t_{j'}\) and each round \(\ell \) which is compatible with the given HAP-set \(F_{2n}\), we can find the spread by solving at most \(n \times \frac{n}{2} \times (2n-1)\) IPs. Indeed, each round has \(n \times \frac{n}{2}\) H-A pairs, and for each of these, in each of the \(2n-1\) rounds, after solving formulation (17)–(22), we record yes/no whether this match can be played in this round. Next, enumerating gives us the spread of each match, from which we determine the spread of the HAP-set.
$$\begin{aligned}&\sum _{r \in R} (x_{i,j,r} + x_{j,i,r}) = 1&\quad \forall i,j \in F_{2n}: i \ne j \end{aligned}$$
(17)
$$\begin{aligned}&\sum _{j \in F_{2n}} (x_{i,j,r} + x_{j,i,r}) = 1&\quad \forall i \in F_{2n}, r \in R \end{aligned}$$
(18)
$$\begin{aligned}&x_{i,j,r} \le h^i_r&\quad \forall (\{i,j\},r) \ne (\{i',j'\}, \ell ) \end{aligned}$$
(19)
$$\begin{aligned}&x_{i,j,r} \le 1 - h^j_r&\quad \forall (\{i,j\},r) \ne (\{i',j'\}, \ell ) \end{aligned}$$
(20)
$$\begin{aligned}&x_{i,j,r} \in \{0,1\}&\forall i,j \in F_{2n}, r \in R \end{aligned}$$
(21)
$$\begin{aligned}&x_{i',j',\ell } + x_{j',i',\ell }= 1&\end{aligned}$$
(22)
Table 5
Flexibility measures for single-break HAP-sets for up to 16 teams
2n | D-notation | spread | FP |
|---|---|---|---|
4 | 21 (CPS) | 10 | 2 |
6 | 221 (CPS) | 35 | 3 |
8 | 2221 (CPS) | 88 | 4 |
3121 | 76 | 4 | |
10 | 22221 (CPS) | 177 | 5 |
31221 | 161 | 4 | |
12 | 222221 (CPS) | 314 | 6 |
312212 | 266 | 6 | |
312221 | 332 | 4 | |
321221 | 266 | 6 | |
313121 | 254 | 6 | |
14 | 2222221 (CPS) | 507 | 7 |
3122212 | 471 | 6 | |
3122221 | 557 | 4 | |
3212221 | 471 | 6 | |
3123121 | 423 | 7 | |
3131221 | 439 | 6 | |
3213121 | 423 | 7 | |
16 | 22222221 (CPS) | 768 | 8 |
31222122 | 686 | 8 | |
31222212 | 796 | 6 | |
31222221 | 864 | 4 | |
32122212 | 632 | 8 | |
32122221 | 796 | 6 | |
32212221 | 686 | 8 | |
31223121 | 672 | 8 | |
31231221 | 690 | 6 | |
31312212 | 614 | 8 | |
31312221 | 838 | 6 | |
32122131 | 614 | 8 | |
32123121 | 684 | 8 | |
32131221 | 690 | 6 | |
32213121 | 672 | 8 | |
31313121 | 640 | 8 | |
41213121 | 552 | 8 |
4.2 Results
We have used the formulations in Sect. 4.1 to compute the spread and the fixed part for all D-notations corresponding to feasible single-break HAP-sets of \(2n \le 16\). Recall that each such D-notation represents a family of HAP-sets with the same value for the flexibility measures (see Section 2.1). All computations were done using IBM Ilog Cplex 12.8 on a Dell Latitude 7490 with Intel Core i7-8650 @ 1.9 GHz and 16 GB RAM. IP models (10)–(16) and (17)–(22) were solved in less than one second; all flexibility measures were computed in less than 1 minute for up to 16 teams. Recall that we know that the width equals one for all single-break HAP-sets from Theorem 3.1.
The results are summarized in Table 5. While for 4 and 6 teams, all single-break HAP-sets are equivalent with respect to all flexibility measures, this is no longer the case for 8 teams and more. It turns out that for 8 teams, the popular canonical pattern set is the best choice with respect to the spread and as good as any other single-break HAP-set when we focus on the fixed part. For 10 to 16 teams, however, the canonical pattern set is clearly dominated by another type of schedule, indicated by the D-notation 312...21. Moreover, for all values of 2n that we considered, this single-break HAP-set shows the highest spread as well as the lowest fixed part.
We also point out the following: we claim that if some match (P(r), P(s)) is in the FP, then its complementary match, defined as \((P^c(r), P^c(s))\) is also in the FP. Thus, the set of matches in the FP can be seen as pairs. Interestingly, for \(2n \in \{10,14\}\), there exist feasible single-break HAP-sets with an odd number of matches in the FP. This can only happen when the complement of a match is the match itself, as in the match \((P^H(r), P^A(r))\). Thus, in these cases, although the match is between two teams that have complementary HAPs (and hence could, seemingly, play in each round), apparently, this match can only be played in one round only.
5 Conclusion
In a first-break-then-schedule approach, it is important to have freedom to schedule the individual matches after the home-away patterns have been chosen. We have proposed three measures that indicate the amount of freedom associated with a particular HAP-set. We have theoretically established how the most popular HAP-set, the canonical pattern set (CPS), fares on these measures. Also, we have computed, using integer programming, for all feasible single-break HAP-sets up to order 16, the numerical values of the proposed measures. It is interesting to see that, when the number of teams exceeds 10, the CPS is not the most flexible HAP-set.
More generally, while we have focused here on single break HAP-sets, we expect that, when allowing HAPs with break-numbers of value 2 and larger, one can construct HAP-sets that score better on our flexibility measures, i.e., achieve a better value for the width, fixed part, and spread, respectively. We leave this as an interesting direction to explore.
Acknowledgements
We thank Sigrid Knust for discussing D-sequences. The research of Frits C.R. Spieksma was partly funded by the NWO Gravitation Project NETWORKS, Grant Number 024.002.003.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.