Hybrid approaches to sports league scheduling using constraint programming and simulated annealing

Abstract

Sports league scheduling deals with constructing solutions in form of tournaments for a set of teams following rules of a considered sports league and a corresponding shared view on what good solutions should look like. They constitute difficult combinatorial optimization problems due to their large number of constraints, which makes finding valid solutions alone a challenging task, paired with an optimization aspect, which aims at minimizing the deviation from desired positive tournament properties. In this thesis, we investigate hybrid approaches based on the constraint programming (CP) paradigm and the metaheuristic simulated annealing (SA) applied on two concrete problems of this class, namely the Traveling Tournament Problem (TTP) and the International Timetabling Competition 2021 problem (ITC2021). The TTP aims at capturing the essence of the complexity of sports league scheduling while the ITC2021 is motivated by real-world instances with their plethora of hard and soft constraints. More concretely for the TTP, we implement and evaluate the Traveling Tournament Simulated Annealing (TTSA) approach from Anagnostopoulos et al. in the Julia programming language and combine it with a CP model to quickly find random initial solutions. This allows us to successfully reproduce fast cooling experiments from the literature on benchmark instances. We adapt the TTSA further for the constraints and objective function of the ITC2021 problem, implement some algorithmic improvements, and perform final tuning experiments to obtain a portfolio of promising configurations. To find initial solutions, we design and implement a tool which transforms the ITC2021 XML instances into the language of the CP modeling software MiniZinc, which allows us to efficiently compare four different backend solvers with various configurations and restarting mechanisms. Given the highly constrained nature of the problem, we assumed CP to work better, however, with this pure CP approach we could only find feasible solutions for slightly more than half of the 45 instances. In a parallel hybridization, we finally combine CP with SA. For each instance, multiple threads are started in each of which we first search for a feasible solution via the Chuffed CP solver using randomization and a shorter time limit. The solution is subsequently provided to the SA to improve it, for which we sample a configuration from the aforementioned portfolio randomly. In case no feasible solution is found by CP, this then becomes the task of SA, which can handle infeasible solutions and reduce constraint violations. This allows us to find feasible solutions for two thirds of the instances, which is an improvement compared to pure CP runs. Moreover, we are able to frequently improve initial CP solutions while sometimes full CP runs are better. Still, the overall performance is below other ITC2021 competitors; we cannot reach the best known solutions by a substantial margin. In particular, it seems preferable to use integer programming instead of CP. In our setting, it turned out to be beneficial to have a hybrid approach since we dealt with instances where only CP found a solution and instances where only SA found a solution. We also had instances where the solution found by CP was improved substantially by the SA.

Ligenplanungsprobleme befassen sich mit der Erstellung von Spielplänen für Teams in jeweils einer bestimmten Sportliga mit ihren Regeln und einem geteilten Verständnis davon, was einem guten Plan entspricht. Sie gelten als schwierige kombinatorische Optimierungsprobleme, bedingt durch ihre hohe Anzahl von Constraints, welche es erschweren, schon allein gültige Lösungen zu finden, gepaart mit einer Optimierungskomponente, bei der Abweichungen von gewünschten positiven Eigenschaften minimiert werden sollen. In dieser Arbeit untersuchen wir hybride Ansätze basierend auf dem Constraint Programming (CP) Paradigma und der Metaheuristik Simulated Annealing (SA) angewandt auf zwei herausfordernde Probleme aus dieser Klasse, nämlich das Traveling Tournament Problem (TTP) und das International Timetabling Competition Problem 2021 (ITC2021). Das TTP versucht die grundsätzliche Schwierigkeit in einer möglichst einfachen Problemstellung zu erfassen, während das ITC2021 auf Echtwelt-Probleminstanzen mit ihrer Vielzahl an Constraints und Optimierungskriterien abstellt. Konkret implementieren wir den Traveling Tournament Simulated Annealing (TTSA) Ansatz für das TTP von Anagnostopoulos et al. in der Programmiersprache Julia und kombinieren diesen mit einem eigenen CP-Modell zum schnellen Finden von zufälligen Startlösungen. Wir können damit Experimente mit schneller Abkühlung für Benchmark- Instanzen aus der Literatur erfolgreich reproduzieren. Wir erweitern TTSA um die Constraints und Zielfunktion des ITC2021 Problems, nehmen einige algorithmische Verbesserungen vor und führen anschließend entsprechende Tuning-Experimente durch, um ein Portfolio von günstigen Parameter-Konfigurationen zu bestimmen. Zum Finden gültiger Lösungen entwerfen wir zuerst ein Transformationsprogramm, welches die per XML spezifizierten ITC2021 Instanzen in die Sprache der CP Modellierungssoftware MiniZinc übersetzt. Dies gestattet das effiziente Vergleichen von vier unterschiedlichen Backend-Solvern mit verschiedensten Konfigurationen und Restarting- Mechanismen. Die hohe Anzahl an Constraints hat eine Verwendung von CP nahegelegt, jedoch vermochten wir damit nur für etwas mehr als die Hälfte der 45 bereitgestellten Testinstanzen gültige Lösungen zu finden. In einer parallelen Hybridisierung verknüpfen wir nun CP mit SA. Dabei werden je Instanz mehrere Threads gestartet, wobei jeweils zuerst versucht wird, über den Chuffed CP-Solver mit eigener Randomisierung eine gültige Lösung innerhalb eines kürzeren ixZeitlimits zu finden. Diese wird anschließend dem SA zur Verbesserung übergeben, wobei eine Konfiguration aus dem Portfolio zufällig selektiert wird. Sollte über CP keine gültige Lösung gefunden werden, so wird dies dem SA überlassen, welcher auch mit ungültigen Lösungen umgehen und Constraint-Verletzungen reduzieren kann. Damit können wir zumindest für zwei Drittel der Instanzen gültige Lösungen finden, was eine Verbesserung gegenüber reinen CP-Optimierungsläufen darstellt. Außerdem können wir oft CP-Startlösungen verbessern. Gesamt betrachtet können unsere Lösungen mit denen der anderen ITC2021 Kompetitoren nicht mithalten. Insbesondere erscheint eine Verwendung von Integer Programming effektiver als CP zu sein. Allerdings stellte sich der hybride Lösungsansatz für uns als vorteilhaft dar, da wir teilweise Lösungen nur in der CP-Phase, teilweise nur in der SA-Phase fanden. Wir hatten aber auch Instanzen, bei denen SA die durch CP gefundene Lösung deutlich verbesserte.