Dynamic rating of European football teams

^** Formerly Knorr-Held. Email: held{at}stat.uni-muenchen.de In this paper we apply and extend recently proposed methodsfor the dynamic analysis of pairwise comparison data to Europeanfootball teams. Our statistical model is based on the cumulativelogistic link model with time-changing parameters for the strengthof each team. We jointly analyse the results from the five topEuropean leagues from 1996 to 2001 and all international matchesbetween teams from these leagues. We introduce weights for internationalmatches and also allow for a different size of the home teamadvantage in the different leagues. We suggest that the resultsfrom such an analysis may be taken as an alternative to theUEFA coefficient, which is currently used to determine the numberof teams from each league to take part in the European footballcontests.     

Maximizing breaks and bounding solutions to the mirrored traveling tournament problem

We investigate the relation between two aspects of round robin tournament scheduling problems: breaks and distances. The distance minimization problem and the breaks maximization problem are equivalent when the distance between every pair of teams is equal to 1. We show how to construct schedules with a maximum number of breaks for some tournament types. The connection between breaks maximization and distance minimization is used to derive lower bounds to the mirrored traveling tournament problem and to prove the optimality of solutions found by a heuristic for the latter.     

Determining matchdays in sports league schedules to minimize rest differences

Many sports leagues first announce the games to be played in each round and then determine their matchdays as the season progresses. This study focuses on the fairness criterion of minimizing the total rest difference among opposing teams to find the matchdays for an announced schedule. We show that the problem is decomposable into optimizing the rounds separately. We also provide a polynomial-time exact algorithm for canonical schedules.     

The multi-league sports scheduling problem,or how to schedule thousands of matches

We consider the simultaneous scheduling of multiple sport leagues, with interdependencies arising from teams in different leagues belonging to the same club. Teams from the same club share the same venue with limited capacity. We minimize the total capacity violation in polynomial time when each league has the same, even number of teams. We introduce two generalizations: one where teams from a club have to play according to the same pattern, and one where club capacities differ throughout the season.     

A branching scheme for finding cost-minimal round robin tournaments

Single round robin tournaments are a well known class of sports leagues schedules. We consider leagues with a set T of n teams where n is even. Costs are associated to each possible match. The goal is to find the minimum cost tournament among those having the minimum number of breaks. We pick up structural properties of home–away-pattern sets having the minimum number of breaks. A branching idea using these properties is developed in order to guide branching steps on the first levels of a branch-and-bound tree in order to avoid nodes corresponding to infeasible subproblems.     

Multidimensional scaling analysis of soccer dynamics

This paper studies the behavior of teams competing within soccer national leagues. The dissimilarities between teams are measured using the match results at each round and that information feeds a multidimensional scaling (MDS) algorithm for visualizing teams’ performance. Data characterizing four European leagues during season 2014–2015 is adopted and processed using three distinct approaches. In the first, one dissimilarity matrix and one MDS map per round are generated. After, Procrustes analysis is applied to linearly transform the MDS charts for maximum superposition and to build one global MDS representation for the whole season. In the second approach, all data is combined into one dissimilarity matrix leading to a single global MDS chart. In the third approach, the results per round are used to generate time series for all teams. Then, the time series are compared, generating a dissimilarity matrix and the corresponding MDS map. In all cases, the points on the maps represent teams state up to a given round. The set of points corresponding to each team forms a locus representative of its performance versus time.     

A branching scheme for minimum cost tournaments with regard to real-world constraints

Single round robin tournaments are a well-known class of sports leagues schedules. We consider leagues with a set T of n teams where n is even. Costs are associated with each possible match. Moreover, stadium availability, fixed matches, and regions’ capacities are taken into account. The goal is to find the minimum cost tournament among those having the minimum number of breaks and being feasible with regard to these additional constraints. A branching scheme is developed where branching is done by fixing a break for a team. Thus, the focus is on identifying breaks leading to an infeasible home away pattern set in order to avoid the resulting infeasible subtrees of a branch and bound tree.     

Construction of sports schedules with multiple venues

A graph theoretical model is presented for constructing calendars for sports leagues where balancing requirement have to be considered with respect to the different venues where competitions are to be located. An inductive construction is given for leagues having a number of teams 2n which is of the form 2^p in particular.     

Rankings and values for team games

In this article we attack several problems that arise when a group of individuals is organized in several teams with equal number of players in each one (e.g., for company work, in sports leagues, etc). We define a team game as a cooperative game v that can have non-zero values only on coalitions of a given cardinality; it is further shown that, for such games, there is essentially a unique ranking among the players. We also study the way the ranking changes after one or more players retire. Also, we characterize axiomatically different ways of ranking the players that intervene in a cooperative game.     

On the existence of sports schedules with multiple venues

We give theoretical methods of creating sports schedules where there are multiple venues for the games, and the number of times each team uses each venue should be balanced. A construction for leagues having 2^p?8 teams was given by de Werra, Ekim and Raess. Here we show that feasible schedules exist when the league has an arbitrary even number of teams greater than or equal to 8.     

Iterative algorithms for the curfew planning problem

The curfew planning problem is to design an annual timetable for railway track maintenance teams. Each team is capable of handling certain types of repairs and replacement jobs. The jobs are combined into a set of projects according to their locations and types. The timetable shows which project should be worked on by each team on a weekly basis throughout an entire year. Our objective is to design a schedule with minimum network disruption due to ongoing maintenance projects that require absolute curfew. Absolute curfew projects are those that cause complete closure of the rail traffic. For tackling this problem, we develop four optimization-based iterative algorithms. We also present very promising computational results obtained within a few minutes using data provided by a major North American railroad.     

A multi-round generalization of the traveling tournament problem and its application to Japanese baseball

In a double round-robin tournament involving n teams, every team plays 2(n − 1) games, with one home game and one away game against each of the other n − 1 teams. Given a symmetric n by n matrix representing the distances between each pair of home cities, the traveling tournament problem (TTP) seeks to construct an optimal schedule that minimizes the sum total of distances traveled by the n teams as they move from city to city, subject to several natural constraints to ensure balance and fairness. In the TTP, the number of rounds is set at r = 2. In this paper, we generalize the TTP to multiple rounds (r = 2k, for any k ? 1) and present an algorithm that converts the problem to finding the shortest path in a directed graph, enabling us to apply Dijkstra’s Algorithm to generate the optimal multi-round schedule. We apply our shortest-path algorithm to optimize the league schedules for Nippon Professional Baseball (NPB) in Japan, where two leagues of n = 6 teams play 40 sets of three intra-league games over r = 8 rounds. Our optimal schedules for the Pacific and Central Leagues achieve a 25% reduction in total traveling distance compared to the 2010 NPB schedule, implying the potential for considerable savings in terms of time, money, and greenhouse gas emissions.     

Flow does not Model Flows up to Weak Dihomotopy

We prove that the category of flows cannot be the underlying category of a model category whose corresponding homotopy types are the flows up to weak dihomotopy. Some hints are given to overcome this problem. In particular, a new approach of dihomotopy involving simplicial presheaves over an appropriate small category is proposed. This small category is obtained by taking a full subcategory of a locally presentable version of the category of flows. Mathematics Subject Classifications (2000) 55P99, 68Q85, 18A32, 55U35.     

Scheduling programs with repetitive projects: A comparison of a simulated annealing,a genetic and a pair-wise swap algorithm

We address the problem of scheduling in programs involving the production of multiple units of the same product. Our study was motivated by a construction program for fast naval patrol boats. Other applications of this problem include procurement of multiple copies of aircraft, spacecraft, and weapon systems. In this problem we must decide how many units of the product to assign to each of a number of available crews (individuals, teams, subcontractors, etc.). These types of problems are characterized by two potentially conflicting considerations: 1) the need to complete each unit by its contractual due date, and 2) learning effects. Because of the first consideration, there is a tendency to use multiple crews for simultaneous production, so that meeting due dates is assured. However, the second consideration encourages assigning many units to a single crew so that learning effects are maximized. We study this scheduling problem with two different penalty cost structures and develop models for both versions. The models trade-off the penalty associated with late deliveries and the savings due to learning (and possibly incentive payments for early completion). We discuss different heuristic algorithms — simulated annealing, a genetic algorithm, and a pair-wise swap heuristic — as well as an exhaustive search to determine a baseline for comparisons. Our computational results show that the pair-wise swap algorithm is the most efficient solution procedure for these models.     

Minimization of Linear Functionals Defined on Solutions of Large-Scale Discrete Ill-Posed Problems

The minimization of linear functionals defined on the solutions of discrete ill-posed problems arises, e.g., in the computation of confidence intervals for these solutions. In 1990, Eldén proposed an algorithm for this minimization problem based on a parametric programming reformulation involving the solution of a sequence of trust-region problems, and using matrix factorizations. In this paper, we describe MLFIP, a large-scale version of this algorithm where a limited-memory trust-region solver is used on the subproblems. We illustrate the use of our algorithm in connection with an inverse heat conduction problem. AMS subject classification (2000) 65F22     

Solving a manpower scheduling problem for airline catering using metaheuristics

We study a manpower scheduling problem with job time windows and job-skills compatibility constraints. This problem is motivated by airline catering operations, whereby airline meals and other supplies are delivered to aircrafts on the tarmac just before the flights take-off. Jobs (flights) must be serviced within a given time-window by a team consisting of a driver and loader. Each driver/loader has the skills to service some, but not all, of the airline/aircraft/configuration of the jobs. Given the jobs to be serviced and the roster of workers for each shift, the problem is to form teams and assign teams and start-times for the jobs, so as to service as many flights as possible. Only teams with the appropriate skills can be assigned to a flight. Workload balance among the teams is also a consideration. We present model formulations and investigate a tabu search heuristic and a simulated annealing heuristic approach to solve the problem. Computational experiments show that the tabu search approach outperforms the simulated annealing approach, and is capable of finding good solutions.     

Scatter search for project scheduling with resource availability cost

This paper considers a project scheduling problem with the objective of minimizing resource availability costs, taking into account a deadline for the project and precedence relations among the activities. Exact methods have been proposed for solving this problem, but we are not aware of existing heuristic methods. Scatter search is used to tackle this problem, and our implementation incorporates advanced strategies such as dynamic updating of the reference set, the use of frequency-based memory within the diversification generator, and a combination method based on path relinking. We also analyze the merit of employing a subset of different types when combining solutions. Extensive computational experiments involving more than 2400 instances are performed. For small instances, the performance of the proposed procedure is compared to optimal solutions generated by an exact cutting plane algorithm and upper and lower bounds from the literature. For medium and larger size instances, we developed simple multi-start heuristics and comparative results are reported.     

Scheduling non-professional table-tennis leagues

In this paper we consider a sports league scheduling problem which occurs in planning non-professional table-tennis leagues. The problem consists in finding a schedule for a time-relaxed double round robin tournament where different hard and soft constraints have to be taken into account. We model the problem as an integer linear program and a multi-mode resource-constrained project scheduling problem, respectively. Based on the second model a heuristic solution algorithm is proposed, which proceeds in two stages using local search and genetic algorithms. Computational results show the efficiency of the approaches.     

Polynomial Algorithms for a Class of Discrete Minmax Linear Programming Problems

We consider the problem of obtaining integer solutions to a minmax linear programming problem. Although this general problem is NP-complete, it is shown that a restricted version of this problem can be solved in polynomial time. For this restricted class of problems two polynomial time algorithms are suggested, one of which is strongly polynomial whenever its continuous analogue and an associated linear programming problem can be solved by a strongly polynomial algorithm. Our algorithms can also be used to obtain integer solutions for the minmax transportation problem with an inequality budget constraint. The equality constrained version of this problem is shown to be NP-complete. We also provide some new insights into the solution procedures for the continuous minmax linear programming problem.     

A GRASP-based approach for technicians and interventions scheduling for telecommunications

The Technicians and Interventions Scheduling Problem for Telecommunications embeds the scheduling of interventions, the assignment of teams to interventions and the assignment of technicians to teams. Every intervention is characterized, among other attributes, by a priority. The objective of this problem is to schedule interventions such that the interventions with the highest priority are scheduled at the earliest time possible while satisfying a set of constraints like the precedence between some interventions and the minimum number of technicians needed with the required skill levels for the intervention. We present a Greedy Randomized Adaptive Search Procedure (GRASP) for solving this problem. In the proposed implementation, we integrate learning to the GRASP framework in order to generate good-quality solutions using information brought by previous ones. We also compute lower bounds and present experimental results that validate the effectiveness of this approach.