Written by Kelly Easton, George Nemhauser, Michael Trick

Matthew Lai

CS 537 Scheduling

Sports Scheduling

Paper Summary

Introduction

Sports scheduling is the process of scheduling games between multiple teams into what the paper calls a tournament. The paper focuses on Round robin tournaments, specifically the single round robin and double round robin tournaments. The single round robin tournament consists of games scheduled such that each team plays each other team exactly once. Double round robin tournaments consists of games in which each team plays each other team twice, usually once at each team’s home venue. Other tournament types mentioned and expanded on in the paper is the balanced tournament design problem consisting of games that are hosted within neutral grounds with common facilities to host all games, the bipartite tournament problem which states the problem of scheduling games between the members of two groups such that each member of one group plays all the members in the other group, and the traveling tournament problem which states a problem in which the home stands and road trips are considered as well as the total distance by each team.

There are some useful terms that should be introduced prior to the paper proper, some of which has cropped up in the previous paragraph. A break is the number of times that a team has consecutive home or away games. A tournament is a series of games in which teams play each other team. A schedule is a mapping of games into slots such that each team plays at most once in each slot. A mirrored or partially mirrored schedule occurs in double round robin games in which a team’s schedule can simply be mirrored so that each team plays the other teams twice without having to recalculate the schedule; the teams will play each team once at each venue. A compact schedule is a schedule that includes the minimum possible number of slots. A pattern is a vector of home, away, or bye designations for a single team over the slots of a schedule. A complementary pattern is such that one pattern consists of slots that are exactly complimentary to the respective slots in the other pattern. A pattern set is a collection of patters, one for each team. A tour is the schedule for a single team. A trip or road trip is a series of consecutive away games. A home stand is the opposite, it is a series of consecutive home games.

In the first part of this paper we will look at defining the problems that were introduced in the chapter. We will discuss the specific solutions for each problem and the specific details of each. We will then discuss some of the more general solutions to sports scheduling including graph algorithms, integer programming, constraints programming, and some metaheuristic algorithms.

Round Robin Tournaments

Single Round Robin Tournament

The single round robin tournament is a tournament in which each team plays each other team exactly once. It can be formally described with the following definition:

Input: A set of n teams T = { 1, 2, …, n }

Output: A mapping of the games in the set G = {gij :i, j T, i < j}

To slots in the set S = {sk, k = 1, …, n-1 if n is even and k = 1, …, n if n is odd}

This SSRT problem can be described as a block design problem which is described as (v, k,). The block design algorithm attempts to create subsets of size k using the v elements of the set where each element can only appear in subsets. The SSRT problem, therefore, can be described as (n, 2, 1) where n is the number of teams participating in the tournament, 2 is the size of each subset, and 1 is the number of subsets that a team can appear simultaneously in. In other words, each of the nteamsis placed into a subset of size 2 and in at most 1 subset. That subset is then a scheduled game for that slot. This block design problem can be solved with what is known as the circle method. This method is described as follows: Each teams is labeled in order as , 1, 2, …, n-1. On day i, play team i vs. , (i-1) vs (i+1) …, () vs (). Each integer is reduced by (modn – 1)to keep the team number within the interval [1, n -1]. Thelabel is then replaced with team n. Figure 1 is an example with n = 8. Team n or 8 is paired against team i, team 1 on day 1 and team 2 on day 2. This continues for every team in the set. This ensures that each team plays each other team only once within the tournament.

Another solution that can be applied to many round robin tournaments, including the SSRTP, is the Latin Squares problem. A Latin square is an n x n array that is filled with n different symbols each of which occur only once in each row, and only once in each column. By creating a Latin square where each row and column of the array is a representation of a team, one can create a schedule for a tournament. In each cell is the slot in which the two teams would play each other. Figure 2 is such an example of scheduling teams into a Latin square. For day one, the game schedules is simply the teams that correspond to the cells with a value of one, in this case the upward diagonal from the bottom left of the square. There has been a lot of research done in the field of Latin squares and their construction and much of that research can be adopted and applied into the sports scheduling field.

Pattern Set Problems

An alternative way to look at scheduling problems is with pattern sets. In our previous problem statement and solutions, schedules were constructed by assigning team matchups to schedule slots. The reverse process has also been suggested to be an effective alternative to this train of thought. In this case, a pattern set is generated for each team in which they have available slots in which they can play games. This might be a pattern of once every few days or once every week. Then compatible teams are paired with these pattern sets to form schedules. It is then imperative to find a good algorithm to generate pattern sets that will match among different teams. Pattern sets that are generated in this matter will be either feasible patterns, patterns where the set of teams will successfully generate a round robin tournament, or infeasible patterns, where the various teams’ patterns cannot be matched to form a tournament. The whole set of constraints that must be met in order to generate feasible patterns is not currently known, however some basic constraints is useful as baseline constraints. For example, each pair of patterns must differ by at least one slot. This means that any pattern can only appear at most once in a pattern set. For double round robin tournaments, the conditions are stronger. For each pattern pairs generated for any two teams, there must be at least one slot in which one team is at home and the other team is away, and another slot where the team’s play venue is reversed. This is to ensure that teams will eventually match back up with the other team to play each team twice, once in each venue. Another condition for round robin, is that every slot in the pattern set must include an equal number of home and away games. This is obvious because there must be one team at home and one team playing away

Balanced Tournament Designs

A balanced tournament is, as mentioned previously in this paper, a tournament where all the games are played entirely within a neutral set of venues. This means that each game in the tournament has an additional constraint, the slot availability of the venues themselves. The formal definition of the balanced tournament design problem is as follows. The input is a set of n teams T = { 1, …, n } and a number of facilities F. The problem then is to map the games in order to get an output ofgames in set G={gij:i,j∈T, i < j } to the slots available at each facility described by the set S = {sfk, f = 1, …, F, k = 1, …, n – 1 if n is even and k = 1, …, n if n is odd } such that no more than one game involving team i is assigned to a particular slot and the difference between the number of appearances of team i at two separate facilities is no more than 1.In other words, a set of games, each with a pair of teams, must be mapped to the available time slots at a set of facilities. No team can play in more than one game in any one slot and the number of appearances for each team must be spread across all facilities.

One proposed solution to this problem is the BTDP-NO algorithm. This “bracelet” algorithm works for 2m+1 odd number of teams. To perform the BTDP-NO algorithm, each team is arranged from 1 through 2m + 1 into an elongated pentagon or “bracelet”. Each facility is associated with each row containing two teams.For each slot k= 1, …, 2m+1 give the team at the top of the pentagon the bye. For each row with two teams, i, j associated with facility f, assign gij to skf. Each team is then shifted one position in clockwise direction for the next day. Figure 3 is an example of m=2 with 5 different teams. In this tournament, the first set of games will be between teams 2 and 5, 3 and 4, each playing within each the m facilities, facility 1 and facility 2 respectively for this first set. Team 1 will receive the bye game in which they do not play. On the next day each team is rotated clockwise such that team 2 receives the bye and team 1 plays team 3, team 4 plays team 5, each playing in facility 1 and facility 2 respectively.

Bipartite Tournament

The bipartite tournament is a tournament in which there are two sets of teams or players. Each individual in each set must play every individual in the other set. The formal definition of the bipartite tournament is as follows. The input for this tournament is two teams with n players (or teams) T1={x1,...,xn} and T2 = { y1, …, yn }. The output for this tournament type is a mappingof games in the set G = { gij : i∈ T1, j ∈ T2 }, to the slots in the set S = {sk, k = 1, …, n } such that exactly one game including t is mapped to any given slot for all t ∈ T1  T2. As was stated, this problem is not necessarily limited to players, but also to teams, encompassing the concept of leagues or conferences of teams.

General Solution Methods for Sports Scheduling

Graph Algorithms

The sports scheduling problem can be solved as a graph problem. The sports schedule would be represented on a graph, with 2m teams, as a graph K2m with 2m colors. The edge [i, j] would represent a game between team i and team j. The SRRT problem can be presented as a 1-factorization of K2m such that each vertex (or team) is not connected by any two edges of the same value (or color). In this way, by taking the 1-factor of a certain value (or color), you receive a perfect matching of pairs such that no vertex (or team) is connected to more than one other vertex. This 1-factorized graph should be oriented (made directed) such that the direction indicates the home/away orientation of the game. In figure 4, we have a 1-factorization graph with 5 colors. Each node has, at most, one edge of each color.In this graph, a team might be represented as a number, with six teams present within this graph. To find the schedule of a slot is the simple matter of taking the 1-factor of ‘red’ to get a pairing between the teams. Because the graph is a 1-factorization graph, no node will be scheduled to more than one game in any time slot. Figure 5 gives an example of the 1-factor of red for the graph given in figure 4. To schedule venues in addition to tournament game scheduling, the graph simply becomes an oriented graph where each edge becomes a directed edge, as shown in figure5. For double round robin tournament, an extra edge with a symmetric orientation to the existing edge is added between any two nodes. In this way, the teams will play each other twice, once in each venue.

In general, sports scheduling algorithms, such as the aforementioned graph solution, will be adapted to attempt to solve several different sports scheduling problems. One of these problems is the Minimum Breaks problem, an attempt to minimize the total number of breaks the team within a tournament receives. In SRRTP, with an even number of teams, it is possible, albeit with only two feasible patterns, to have a tournament with no breaks. That is no team will have a home stand or trip greater than 1. Therefore with an even number of teams in SRRTP, the tournament will most likely be scheduled with multiple breaks for each team in order to satisfy other conditions. With an odd number of teams, there is the introduce of a bye for a single team in every slot, thus increasing the number of feasible patterns available, allowing for many more patterns with no breaks. Another problem that many general algorithms attempt to solve is the Geographical Location problem. An important constraint concerning geographical location is not necessarily ensuring that teams minimize travel, but to ensure that the scheduling patterns generated do no result in consecutive games in which the two teams with similar geographical locale play each other consecutively in each venue. This is to increase attendance by introducing different matchups in a shorter period of time, as attendees are more likely to attend to see another team play rather than the same matchup. A third sports scheduling problem that will be described in this section is the Divisions problem. Sports leagues often organize themselves into divisions. Teams within a division are often organized by geography in which division teams are relatively close to one another when compared to intra-division matchups. Thus many leagues, such as the MLB, add the scheduling constraint that teams play inter-division games on the weekday and intra-division games on the weekend. De Werra, who wrote many papers on the subject of sports scheduling, goes more into detail with oriented factorizations of complete graphs to solve this problem.

Integer Programming

Integer programming is a mathematical optimization or feasibility program where some or all variables are restricted to be integers. Integer programming is an NP-hard problem that was adapted and developed by Nemhauser and Trick - authors of the paper on which this paper is summarizing - for sports scheduling. An integer programming solution for SRRTP is easy to formulate. Let binary variables xijk = 1 if i plays j in slot k and xijk = 0 otherwise for i < j ∈ {1, …, n } and k ∈ { 1,… n – 1} for even n. In Basic SRRTP the IP problem should satisfy the two following constraints.

The first constraint guarantees that every team plays exactly once in each slot. The second ensures that each team plays every opponent exactly once.

Constraint Programming

Constraints Programming is a programming paradigm with a combinatorial approach for solving hard optimization problems. CP for sports scheduling, as implemented by Martin Henz, performed the steps differently from IP. It first assigned teams to patterns before matching teams in games. This constraints programming solution for sports programming reported ran on the order of minutes as compared to the 24 hour run time from the Integer Programming.

Traveling Tournament Problem

The traveling tournament problem is a unique tournament problem proposed by Nemhauserand Trick that can be solved with their unique hybrid integer programming and constraints programming solution. Its input is a set of teams T = { 1, …, n }; D: an n x n integer distance matrix with elements dij; l, u integer parameters. The output is a double round robin tournament in which the teams in set T follow certain constraints. The length of each home stand and road trip is between l and u inclusive. The total distance traveled by any team is also minimized. With the maximum value of u = (n – 1) , this problem becomes a traveling salesman problem. For a small u the team must return home often, increasing travel distance. For u = 1, the problem becomes on of finding a feasible solution.

To solve this problem, a hybrid method using both Integer Programming and Constraints Programming was used. These two different models are used in a parallel algorithm known as the parallel branch and price algorithm. Each individual team tour is represented as the columns of this column generating algorithm. The Constraints Programming is used to solve the pricing problem to determine the solution to the minimum price, in this case, travel distance. The Integer Processor will attempt to determine the tours for each team in the tournament that will best solve the home stand/road trip constraint of the problem. Additionally a CP model is also used as part of a primal heuristic that is run on a separate processor on the side that will attempt to look for a good, but not necessarily best solution by using the solutions generated so far by the other parts of the algorithm.

Metaheuristics: Simulated Annealing

Simulated Annealing is a generic probabilistic metaheuristic for global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. The algorithm starts from a current state S. It probabilistically decides between moving from the current state to some neighboring S’ state. In this TTSA algorithm, the regions containing infeasible schedules penalize the algorithm to discourage it from remaining in the area. The figure 6 gives an example of a stage of simulated annealing. At this stage with a higher temperature, the marker that is searching for the global maximum will move at a fast rate. As the temperature drops, the marker will decrease its rate of jump and its location will be increasingly narrowed to the points that the algorithm has determined is the most statistically likely location of the global maximum.