IP models for round robin tournaments

Generally speaking in sports competition a number of teams play against each other over a period of time according to a certain scheme. The round robin scheme is very popular in many team sports like soccer and basketball. In this paper we study several basic variants of round robin tournaments. Additionally, we examine real world issues that have to be considered when constructing a sports league schedule. We consider constraints imposed by third parties such as security aspects and legal requirements. Moreover, we analyze constraints aiming at attractive and fair sports league schedules. Throughout this paper integer programming models are the means to formally define what the particular problem under consideration is all about. Moreover, the standard solver Cplex is used in order to compute optimal solutions for small- to medium-size instances. Computational results indicate which particular constraint to relax in order to come up with acceptable schedules in reasonable time.     

Minimizing costs in round robin tournaments with place constraints

In this paper we consider a general sports league scheduling problem and propose solution algorithms for it. The objective is to find a feasible schedule for a round robin tournament with minimum number of breaks and minimum total costs where additionally place constraints are taken into account. We present a “first-break, then-schedule” approach which uses an enumerative procedure to generate home-away patterns and integer programming for finding corresponding schedules. Computational results are presented for leagues with up to 14 teams.     

An application of integer programming to playoff elimination in football championships

Football is the most followed and practiced sport in Brazil, with a major economic importance. Thousands of jobs depend directly on the activity of the football teams. The Brazilian national football championship is followed by millions of people, who attend the games in the stadiums, follow radio and TV transmissions, and check newspapers, radio, TV, and, more recently, the Internet in search of information about the performance and chances of their favorite teams. Teams which do not qualify for the playoffs lose a lot of money and are even forced to dismantle their structure. We comment and compare the complexity of playoff elimination in football and baseball championships. We present two integer‐programming models which are able to detect in advance when a team has already qualified for or been eliminated from the playoffs. Results from these models can be used not only to guide teams and fans, but are also very useful to identify and correct wrong statements made by the press and team administrators. The application and the use of both models in the context of the 2002 edition of the Brazilian national football championship are discussed.     

Sports scheduling: Problems and applications

Sports scheduling problems mainly consist in determining the date and the venue in which each game of a tournament will be played. Integer programming, constraint programming, metaheuristics, and hybrid methods have been successfully applied to the solution of different variants of this problem. This paper provides an introductory review of fundamental problems in sports scheduling and their formulations, followed by a survey of applications of optimization methods to scheduling problems in professional leagues of different sport disciplines such as football, baseball, basketball, cricket, and hockey. A case study illustrates a real‐life application of integer programming to the schedule of the yearly Brazilian football tournament.     

An efficient algorithm for constrained global optimization and application to mechanical engineering design: League championship algorithm (LCA)

The league championship algorithm (LCA) is a new algorithm originally proposed for unconstrained optimization which tries to metaphorically model a League championship environment wherein artificial teams play in an artificial league for several weeks (iterations). Given the league schedule, a number of individuals, as sport teams, play in pairs and their game outcome is determined given known the playing strength (fitness value) along with the team formation (solution). Modelling an artificial match analysis, each team devises the required changes in its formation (a new solution) for the next week contest and the championship goes for a number of seasons. In this paper, we adapt LCA for constrained optimization. In particular: (1) a feasibility criterion to bias the search toward feasible regions is included besides the objective value criterion; (2) generation of multiple offspring is allowed to increase the probability of an individual to generate a better solution; (3) a diversity mechanism is adopted, which allows infeasible solutions with a promising objective value precede the feasible solutions. Performance of LCA is compared with comparator algorithms on benchmark problems where the experimental results indicate that LCA is a very competitive algorithm. Performance of LCA is also evaluated on well-studied mechanical design problems and results are compared with the results of 21 constrained optimization algorithms. Computational results signify that with a smaller number of evaluations, LCA ensures finding the true optimum of these problems. These results encourage that further developments and applications of LCA would be worth investigating in the future studies.     

An improved league championship algorithm with free search and its application on production scheduling

An improved league championship algorithm with free search (LCAFS) is proposed to avoid the drawbacks of basic LCA, such as premature convergence, slow convergence speed. The parameters of the algorithm vary linearly along with iteration. A novel match schedule is designed to improve the competition capability for the sport teams. Furthermore, the free search operation is introduced to promote the diversity of the league. Inspired by the real league degradation, degradation mechanism is used to preserve the team elites. It is convinced by using benchmark functions that LCAFS is superior to other compared algorithms in the global searching performance and convergence speed. The proposed algorithm is finally employed as learning method of parameters in neural network to establish the shop floor production scheduling model and achieves good results.     

Scheduling the professional soccer leagues of Austria and Germany

Generating a regular season schedule is a demanding task for any sports league. In Europe, the creation of a suitable schedule for every national top soccer league not only has to address numerous conflicting inner-league requirements and preferences. Additionally, the games of the European Cup matches (Champions League, UEFA Cup, National Cup Winners) have to be taken into account. In this paper we consider the case of Austria and Germany, that is the planning problem the “Deutsche Fußball-Bund” (DFB) and the “Österreichische Fußball-Bund” (ÖFB) are confronted with. For both leagues we develop models and algorithms which yield reasonable schedules quickly. The models borrow their expressive power from so-called partially renewable resources. Our approach generates schedules which have been accepted for play once by the DFB and six times by the ÖFB.     

Scheduling the Italian Football League: an ILP-based approach

Scheduling the Italian Major Football League (the so-called “Serie A”) consists in finding for that league a double round robin tournament schedule that takes into account both typical requirements such as conditions on home-away matches and specific requests of the Italian Football Association such as twin-schedules for teams belonging to the same home-town. In this paper, we present a solution procedure able to derive feasible schedules that are also balanced with respect to additional cable televisions requirements. This procedure adapts the recent approach by Nemhauser and Trick to schedule a College Basketball Conference that considers however only half of the teams involved here. The proposed procedure is divided into three phases: phase 1 generates a pattern set respecting the cable televisions requirements and several other constraints; phase 2 produces a feasible round robin schedule compatible with the above pattern set; finally, phase 3 generates the actual calendar assigning the teams to the patterns. The procedure allows to generate within short time several different reasonable calendars satisfying the cable television companies requirements and satisfying various other operational constraints while minimizing the total number of violations on the home-away matches conditions.     

Simultaneous scheduling of football games and referees using Turkish league data

Assignment decisions of referees to football (soccer) games are highly debated in sports media. Referee assignments are typically done on a weekly basis as the league progresses. However, this practice ignores important workload constraints on referees. Moreover, referees' skill levels should also be considered in determining their assignments. In this article, we first give a mixed integer linear program formulation for the problem of simultaneously generating a game schedule and assigning main referees to games by incorporating specific rules in the Turkish league. We also approach this problem using a genetic algorithm (GA) because of the computational difficulties in solving the problem. In the GA solution pool, we suggest using templates for referee assignments that follow several referee‐related workload constraints. We explain how these templates can be obtained by solving a mixed integer linear model prior to running the GA. The usage of these templates for referee assignments is conceptually similar to using a basic match schedule for game scheduling such as the one used in the Turkish Football League. We use the Turkish Football League fixtures for 2010–2013 as a case study. Experiments with the GA using real‐world data show a rather modest performance in terms of computation time and objective function value. Our numerical results indicate that the problem is extremely hard to solve.     

A constraint programming approach to the multiple-venue,sport-scheduling problem

In this paper, we consider the problem of scheduling sports competitions over several venues which are not associated with any of the competitors. A two-phase, constraint programming approach is developed, first identifying a solution that designates the participants and schedules each of the competitions, then assigning each competitor as the “home” or the “away” team. Computational experiments are conducted and the results are compared with an integer goal programming approach. The constraint programming approach achieves optimal solutions for problems with up to sixteen teams, and near-optimal solutions for problems with up to thirty teams.     

The Structure and Complexity of Sports Elimination Numbers

Abstract. Identifying the teams that are already eliminated from contention for first place of a sports league, is a classic problem that has been widely used to illustrate the application of linear programming and network flow. In the classic setting each game is played between two teams and the first place goes to the team with the greatest total wins. Recently, two papers [W], [AEHO] detailed a surprising structural fact in the classic setting: At any point in the season, there is a computable threshold W such that for any team i , i is eliminated (has no chance to win or tie for first place) if and only if i cannot win W or more games. They used this threshold to speed up the identification of eliminated teams. In both papers the proofs of the existence of a threshold are tied to the computational methods used to find it. In this paper we show that thresholds exist for a wide range of elimination problems (including European football), thus greatly generalizing the classic setting; we use a simpler proof which is not connected to any particular computational method; we resolve the more refined issue (in the classic setting) of which teams have a chance to be the strict winner of the most games; examine these issues in the context of multidivision leagues with playoffs and wildcards; and establish NP-hardness results for certain elimination questions.     

The Structure and Complexity of Sports Elimination Numbers

Identifying the teams that are already eliminated from contention for first place of a sports league, is a classic problem that has been widely used to illustrate the application of linear programming and network flow. In the classic setting each game is played between two teams and the first place goes to the team with the greatest total wins. Recently, two papers [W], [AEHO] detailed a surprising structural fact in the classic setting: At any point in the season, there is a computable threshold W such that for any team i , i is eliminated (has no chance to win or tie for first place) if and only if i cannot win W or more games. They used this threshold to speed up the identification of eliminated teams. In both papers the proofs of the existence of a threshold are tied to the computational methods used to find it. In this paper we show that thresholds exist for a wide range of elimination problems (including European football), thus greatly generalizing the classic setting; we use a simpler proof which is not connected to any particular computational method; we resolve the more refined issue (in the classic setting) of which teams have a chance to be the strict winner of the most games; examine these issues in the context of multidivision leagues with playoffs and wildcards; and establish NP-hardness results for certain elimination questions.     

Referee assignment in the Chilean football league using integer programming and patterns

This article uses integer linear programming to address the referee assignment problem in the First Division of the Chilean professional football league. The proposed approach considers balance in the number of matches each referee must officiate, the frequency of each referee being assigned to a given team, the distance each referee must travel over the course of a season, and the appropriate pairings of referee experience or skill category with the importance of the matches. Two methodologies are studied, one traditional and the other a pattern‐based formulation inspired by the home‐away patterns for scheduling season match calendars. Both methodologies are tested in real‐world and experimental instances, reporting results that improve significantly on the manual assignments. The pattern‐based formulation attains major reductions in execution times, solving real instances to optimality in just a few seconds, while the traditional one takes anywhere from several minutes to more than an hour.     

Exploring polynomial classifier to predict match results in football championships

Football is the team sport that mostly attracts great mass audience. Because of the detailed information about all football matches of championships over almost a century, matches build a huge and valuable database to test prediction of matches results. The problem of modeling football data has become increasingly popular in the last years and learning machine have been used to predict football matches results in many studies. Our present work brings a new approach to predict matches results of championships. This approach investigates data of matches in order to predict the results, which are win, draw and defeat. The investigated groups were different type of combinations of two by two pairs, win-draw, win-defeat and draw-defeat, of the possible matches results of each championship. In this study we employed the features obtained by scouts during a football match. The proposed system applies a polynomial algorithm to analyse and define matches results. Some machine-learning algorithms were compared with our approach, which includes experiments with information obtained from the football championships. The association between polynomial algorithm and machine learning techniques allowed a significant increase of the accuracy values. Our polynomial algorithm provided an accuracy superior to 96%, selecting the relevant features from the training and testing set.     

Visualization Techniques for Schedule Comparison

Project schedules are effectively represented by Gantt charts, but comparing multiple versions of a schedule is difficult. To compare versions with current methods, users must search and navigate through multiple large documents, making it difficult to identify differences. We present two novel visualization techniques to support the comparison of Gantt charts. First, we encode two Gantt charts in one view by overlapping them to show differences. Second, we designed an interactive visual technique, the 'TbarView', that allows users to compare multiple schedules within one single view. We evaluated the overlap and TbarView techniques via a user study. The study results showed that our design provided a quick overview of the variances among two or more schedules, and the techniques also improved efficiency by minimizing view switching. Our visual techniques for schedule comparison could be combined with other resource analysis tools to help project teams identify and resolve errors and problems in project schedules.     

Risk identification and scoring in early-lifecycle concurrent engineering teams

Due to the highly constrained schedules and budgets that NASA missions must contend with, the identification and management of cost, schedule and risks in the earliest stages of the lifecycle is critical. At the Jet Propulsion Laboratory, it is the concurrent engineering teams that first address these items in a systematic manner. Foremost of these concurrent engineering teams is Team X. Started in 1995, Team X has carried out over 1,000 studies, dramatically reducing the time and cost involved, and has been the model for other concurrent engineering teams both within NASA and throughout the larger aerospace community. The ability to do integrated risk identification and assessment was first introduced into Team X in 2001. In this paper, we describe how the Team X risk process is evolving, highlighting the strengths and weaknesses of the different approaches.     

A mixed integer programming formulation and effective cuts for minimising schedule durations of Australian truck drivers

Transport companies seek to maximise vehicle utilisation and minimise labour costs. Both goals can be achieved if the time required to fulfil a sequence of transportation tasks is minimised. However, if schedule durations are too short drivers may not have enough time for recuperation and road safety is impaired. In Australia transport companies must ensure that truck drivers can comply with Australian Heavy Vehicle Driver Fatigue Law and schedules must give enough time for drivers to take the amount of rest required by the regulation. This paper shows how transport companies can minimise the duration of truck driver schedules complying with Australian Heavy Vehicle Driver Fatigue Law. A mixed integer programming formulation is presented and valid inequalities are given. Computational experiments show that these inequalities provide significant reduction in computational effort when using one of the most advanced commercial mixed integer programming solver.     

Biomimetic control architecture for robotic cooperative tasks

This article proposes some control algorithms to be applied to the MIROSOT robot league architecture. The MIROSOT league soccer game concept is fairly simple: two teams of robots, with 3–5 robots per side, play football autonomously. The ball that the teams play with is an orange golf ball. Above the pitch is a machine vision camera running at 60 frames per second. This camera is linked to a server, which calculates the positions and velocities of each of the robots and the ball, and then determines what each robot should be doing. These instructions are then communicated to the robots over wireless links. In order to develop an efficient control strategy and architecture, the robots have to use strategies from the real human soccer game. Using the software Simi Scout, a suitable analysis of tactics can be extracted from the games. After analyzing the soccer game, a number of attributes are specified and then embedded at different levels. The specified attributes are interconnected, and the analysis of the game is processed for optimization. Using this information, the robot program is adapted and experimental tests/games are played. We comment on the results, and propose an improved control architecture based on practical results.     

Soccer schedules in Europe: an overview

In this paper, we give an overview of the competition formats and the schedules used in 25 European soccer competitions for the season 2008?C2009. We discuss how competitions decide the league champion, qualification for European tournaments, and relegation. Following Griggs and Rosa (Bull. ICA 18:65?C68, 1996), we examine the popularity of the so-called canonical schedule. We investigate the presence of a number of properties related to successive home or successive away matches (breaks) and of symmetry between the various parts of the competition. We introduce the concept of ranking-balancedness, which is particularly useful to decide whether a fair ranking can be made. We also determine how the schedules manage the carry-over effect. We conclude by observing that there is quite some diversity in European soccer schedules, and that current schedules leave room for further optimizing.     

On the application of graph colouring techniques in round-robin sports scheduling

The purpose of this paper is twofold. First, it explores the issue of producing valid, compact round-robin sports schedules by considering the problem as one of graph colouring. Using this model, which can also be extended to incorporate additional constraints, the difficulty of such problems is then gauged by considering the performance of a number of different graph colouring algorithms. Second, neighbourhood operators are then proposed that can be derived from the underlying graph colouring model and, in an example application, we show how these operators can be used in conjunction with multi-objective optimisation techniques to produce high-quality solutions to a real-world sports league scheduling problem encountered at the Welsh Rugby Union in Cardiff, Wales.