Chilean soccer league scheduling
Faced with a long list of constraints, O.R. group scores with efficient schedules that reduce travel costs, enhance key matches and boost attendance.
By Guillermo Durán and Mario Guajardo
In 2004, a Chilean newspaper interviewed prominent Georgia Tech professor George Nemhauser, who was in Chile to attend an academic seminar. Under the headline “Scientist Creates Successful Sports Schedules using Mathematical Modelling,” the article recounted how Nemhauser had successfully applied operations research (O.R.) models to baseball and basketball leagues in the United States (see, e.g., Nemhauser and Trick 1998). No one at that time could have imagined that this brief item would trigger what has become a lasting and fruitful alliance of Chilean academics and local organized soccer officials that for the last 10 years has implemented O.R. techniques in football (soccer) season scheduling.
The report caught the attention of the Chilean National Professional Football Association (ANFP), which until then had always defined the different leagues’ fixtures randomly, as did many other sports leagues around the world. The basic technique involved a so-called canonical schedule, a sort of pre-defined season format for a given number of generic clubs that specifies which team pairs play each other in each season round. Every year the ANFP would randomly assign the teams according to this format. The resulting schedules fulfilled certain basic conditions such as one meeting per tournament per pair of teams and exactly one scheduled match per team per round. Other conditions, however, such as “good” road trip sequences and the scheduling of important matches on attractive dates, were beyond the ability of the canonical schedule technique.
Proof of this is that in the 2004 season the country’s two most popular teams, Colo Colo and Universidad de Chile, were scheduled to play in the opening round. Setting such an important game so early in the season is inadvisable, particularly since at that point the summer is not yet over and many residents of Santiago, Chile’s main population center and home to numerous teams, are still away on holiday. As a result, only 25,000 fans attended the Colo Colo-Universidad de Chile match-up, which almost certainly would have attracted more than 40,000 had it been scheduled further into the season.
Inspired by the article on Nemhauser, ANFP officials approached the O.R. group (including the present authors) at the University of Chile’s Department of Industrial Engineering with a proposal for a joint project to use mathematical modeling in scheduling the First Division’s Opening and Closing tournaments that together constitute a full season in Chilean football. Our working relationship began with the definition of a series of conditions the 2005 Opening fixtures would have to meet. At that time, the tournaments involved 20 teams divided into four groups of five each, and were played in two phases. The first phase was a single round-robin, meaning each team played each other team once, while the second phase was an eight-team playoff featuring the two teams from each group that topped the tables in the first phase. One set of first-phase conditions had to do with the teams’ home-away match sequences. For example, no team could be scheduled to play more than two consecutive games both at home or both away. Furthermore, any such pair of consecutive home or away rounds could not be scheduled within the first or last two rounds of the tournament.
Geographically, the conditions incorporated the idea that “good” road trip sequences were desirable, or at least that “bad” ones should be avoided. This criterion is especially significant in a long and narrow country such as Chile’s that stretches some 2,600 miles from north to south. An example of a “good” sequence for a northern team would be to play two consecutive away matches in southern Chile, the first in a mid-week round and the second the following weekend. A “bad” sequence would be a central region team playing mid-week at a southern team’s venue and the following weekend at a northern club’s home ground.
Other schedule conditions capture the availability of stadiums, which are sometimes booked for concerts or closed for maintenance. On such dates the teams must be assigned away games. Also, since some venues are shared by two teams, one of them must necessarily be scheduled away on a date when the other is at home, and vice versa.
Yet other conditions aim at making the schedules more attractive. Matches between clubs in the same group are particularly exciting for fans when scheduled in the decisive final rounds of a tournament. Another way of increasing interest and boosting attendance is to set summer fixtures for matches between the most popular teams and those that play at home in or near tourist areas, thus taking advantage of the influx of holidaymakers. Also, classic matchups and derbies (games between nearby rivals) are scheduled in the latter half of the season as the fight for playoff spots heats up.
Finally, the television broadcaster carrying Chilean football matches (80 percent owned by the ANFP) also has requirements driven by the transport and operating costs of its mobile broadcast units. To hold down the expense of moving sophisticated equipment from one stadium to another, “good” match sequences for the broadcaster are also considered in the scheduling criteria.
All of the above conditions were included in the scheduling models we designed in the form of constraints. Although satisfying these constraints is the main goal of the process, in some cases certain conditions were incorporated into an objective function. One of our principal optimization criteria has been the maximization of the number of attractive matches toward the end of a tournament. Another is the maximization of “good” travel sequences for TV broadcasters. In the latest tournament, played in the first half of 2015, the objective function minimized the number of winter month games in the colder southern regions of the country to reduce cancellations due to bad weather.
The problem solved by the models is highly complex, containing 8,000 variables and 3,000 constraints. Generally speaking, the dimension and combinatorial structure of sports scheduling problems make merely finding a feasible solution a major challenge. For an eight-team, single round-robin, there are already 31 million possible fixture combinations; for the 18-team First Division of the Chilean football league the number is simply unimaginable. During the 10 years of the scheduling project, various O.R. tools have been employed such as constraint programming, exact integer programming formulations, heuristics and decomposition into subproblems.
Currently, the solution process for the Chilean league problem consists of three phases. In the first phase, an integer-programming model generates home-away patterns for the teams based on certain constraints. In the second phase, with these patterns already fixed, the remaining constraints are incorporated into a second integer programming model that generates a schedule specifying the matches to be played in each tournament round. Finally, in the third phase, yet another model assigns the exact dates and times of each match. This approach has produced very good solutions in a matter of minutes. Also, during the scheduling process the academic modeling team and league officials interact frequently to clarify details and add conditions not included in the original design. The models are run some 60 times, and the results are evaluated by the joint team until the definitive fixture schedule is arrived at.
In 2005 and 2006, the first two years of the project, the O.R. techniques were applied to the First Division tournaments with excellent results. Although certain factors unrelated to their application are difficult to isolate, some measurements comparing the last tournaments before 2005 with those immediately following clearly indicate a significant impact. Attendance at classic matches grew by 74 percent, while at summer games scheduled in tourist areas between popular teams and local clubs attendance increased between 46 percent and 156 percent.
The impact of the scheduling has also been very positive on the television broadcaster and therefore also on the teams, which derive a considerable part of their income from transmission rights. Each “good” scheduled trip means a savings for the broadcaster of $20,000 to $30,000. The models attempt to schedule five “good” trips per tournament. Thus, on one occasion in the project’s early years, matches involving local powerhouses Universidad de Chile and Universidad Católica were scheduled on a Saturday and a Sunday of the same weekend in two northern cities relatively close to each other. This allowed a single mobile television unit to be used for both games. The major transport cost savings that were achieved led one company executive to comment on the “lucky” schedule coincidence, not realizing it was the result of a deliberate O.R. model design criterion. Since then the company has increased the number of matches it broadcasts per round from four to nine and quadrupled its number of subscribers, due in part to more efficient resource allocation made possible by the improved schedules.
In light of these good results for the First Division, the ANFP asked the O.R. group in 2007 to develop models for the Second Division tournaments. Though the best Chilean teams are, of course, in the more popular First Division, the Second Division is still important given that every season its teams compete for promotion to the First. Most of them are located in smaller towns where football is one of the main forms of local entertainment, and the geographical constraints are particularly strong. A detailed description of the project’s application of O.R. methods to the Second Division is documented in Durán et al. (2012). The first season they were applied, stadium attendance grew by about 10 percent.
The impact of the methods on qualitative aspects has also been very significant; indeed, bigger in some cases than on the quantitative measures. This is reflected in: (i) greater transparency (all stakeholders notified of scheduling criteria); (ii) greater scheduling fairness (all teams’ concerns taken into account); (iii) greater match attractiveness (more exciting schedules for fans and the media); (iv) improved public order (better allocation of police resources and avoidance of street clashes between fans of intracity rivals playing separate matches at nearby stadiums); (v) greater credibility (in the eyes of players, team administrators, fans and the press); (vi) better performance of Chilean teams in international tournaments (due to deliberate scheduling of “better,” i.e., less tiring, road trips in rounds close to international match dates); (vii) more rational stadium operations (by barring home games during maintenance work or on concert dates).
Above all, the O.R. methods have enabled the ANFP to deal with issues that would be impossible to address manually or randomly with the previously used canonical schedule. The conditions taken into account change from year to year due to a range of factors. Over the 10 years of the project, the O.R. approach has showed itself to be adaptable to various different tournament formats. In 2008, for example, the division of First Division teams into groups was dropped and the top eight in regular season play advanced automatically to the playoffs. In 2013, the playoffs were eliminated and each tournament consisted simply of a single round-robin. Currently, the Closing tournament is a mirror of the Opening, so the matches are played in the same order but with their home-away status reversed. The Second Division has also experimented with different formats, including a quadruple round-robin and a two-phase tournament with zonal and national phases. In some cases a division schedule must take into account certain aspects of the schedule of some other division, such as when teams in different divisions share a home stadium.
Since its first Chilean league scheduling efforts in 2005, the project has modeled 22 First Division tournament schedules and, starting in 2007, 13 schedules for the Second Division. Scheduling of the Third Division, the lowest tier in Chilean professional football, has been handled by the project since 2013. O.R. solutions have also been developed by the group for other problems involving Chilean soccer. These include schedules generated by mathematical programming techniques for juvenile leagues and a fixture proposal for the South American qualification phase of the 2010 World Cup (Durán and Guajardo, 2014). In addition, a model was designed for assigning referees that has been utilized by some juvenile leagues and one First Division tournament (Alarcón et al. 2014).
When the project began there was already an extensive literature on sports scheduling and applications for various sports, but little documentation existed on the practical use of O.R. in football leagues beyond a few European cases. Since we wrote up our first experience in Chile, other Latin American countries have reported the use of similar techniques, including Honduras (Fiallos et al. 2010), Brazil (Ribeiro and Urrutia 2010, 2012) and Ecuador (Recalde et al. 2013). To our knowledge, the application of O.R. methods in Chilean football is the most lasting example in the literature for this sport.
In this regard, it is notable that there have been three major changes in ANFP leadership over the life of the O.R. scheduling project, yet the use of the techniques has been maintained. For the Association’s management, returning to the canonical schedule would now be practically unthinkable.
In addition to our ongoing work with Chilean football leagues, the group is now studying a series of other problems at the intersection of O.R., analytics and football, including efforts to improve the Copa Libertadores de América schedule and the FIFA rankings.
The 10 years of football scheduling have been an important formative experience for our researchers. Various student theses have grown out of the project, and in 2009 it was a finalist for the Excellence in Practice Award granted by the Association of European Operational Research Societies. Building on this experience, members of the group have also developed O.R. applications for Argentina’s professional basketball and volleyball leagues.
In conclusion, the authors would like to thank all of those who have participated actively alongside us in the O.R. group since 2005: F. Alarcón, A. Carmash, S. Cea, F. Chaigneau, J. Fuentes, J. Miranda, G. Poblete, R. Rosas, D. Sauré, M. Siebert, S. Souyris, A. Weintraub, R. Wolf-Yadlin and G. Zamorano.
Guillermo Durán ( firstname.lastname@example.org) is a professor and head of the Calculus Institute at the University of Buenos Aires in Argentina and a professor at the University of Chile. An O.R. consultant in projects with private and public sectors, Professor Duran’s research interests include operations research, combinatorial optimization and graph theory.
Mario Guajardo (email@example.com) is an assistant professor in the Department of Business and Management Science, NHH Norwegian School of Economics in Bergen, Norway. His research interests include operations research, collaborative logistics and sports scheduling.
- Alarcón F, Durán G, Guajardo M., 2014, “Referee Assignment in the Chilean Football League using Integer Programming and Patterns,” International Transactions in Operational Research, Vol. 21, pp. 415-438.
- Durán G, Guajardo M, Miranda J, Sauré D, Souyris S, Weintraub A, Wolf R., 2007, “Scheduling the Chilean soccer league by integer programming,” Interfaces, Vol. 37, pp. 539-552.
- Durán G, Guajardo M, Weintraub A, Wolf R., 2009, “O.R. in Soccer: Scheduling the Chilean League using Mathematical Programming,” OR/MS Today, Vol. 36, pp. 42-47.
- Durán G, Guajardo M, Wolf-Yadlin R., 2012, “Operations research techniques for scheduling Chile’s second division soccer league,” Interfaces, Vol. 42, pp. 273-285.
- Durán G, Guajardo M., 2014, “Scheduling the South American Qualifiers for the Football World Cup,” CLAIO XVII, Monterrey, Mexico, Book of Abstracts, p.31.
- Fiallos J, Pérez J, Sabillón F, Licona M., 2010, “Scheduling soccer league of Honduras using integer programming,” in Johnson A, Miller J (eds), Proceedings of the 2010 Industrial Engineering Research Conference, Cancún, Mexico.
- Nemhauser G, Trick M., 1998, “Scheduling a major college basketball conference,” Operations Research, Vol. 46, pp. 1-8.
- Recalde D, Torres R, Vaca P., 2013, “Scheduling the professional Ecuadorian football league by integer programming,” Computers & Operations Research, Vol. 40, pp. 2478–2484.
- Ribeiro CC, Urrutia S., 2010, “Soccer scheduling goaaaaal!” OR/MS Today, Vol. 37, pp. 52–57.
- Ribeiro CC, Urrutia S., 2012, “Scheduling the Brazilian soccer tournament: solution approach and practice,” Interfaces, Vol. 42, pp. 260–272.