Pseudo-Boolean optimisation for RobinX sports timetabling

Lester, M. M. ORCID: https://orcid.org/0000-0002-2323-1771 (2022) Pseudo-Boolean optimisation for RobinX sports timetabling. Journal of Scheduling, 25. pp. 287-299. ISSN 1099-1425 doi: 10.1007/s10951-022-00737-7

Abstract/Summary

We report on the development of Reprobate, a tool for solving sports timetabling problems in a subset of the RobinX format. Our tool is based around a monolithic translation of a sports timetabling instance into a pseudoboolean (PB) optimisation problem; this instance can be solved using existing pseudoboolean solvers. Once the tool has found a feasible solution, it can improve it using a second encoding that alters only the home/away pattern of games. We entered our tool into the International Timetabling Competition 2021. While it was effective on many instances, it struggled to cope with schedules involving large break constraints. However, among instances for which it could initially find a feasible solution, the combination of use of a portfolio of solvers, a range of variations on the encoding and the aforementioned local improvement process yielded an average reduction in solution cost of 23%.

Additional Information	Extended version of a paper published at Practice and Theory of Automated Timetabling (PATAT) 2021 about an entry to the International Timetabling Competition (ITC) 2021.
Item Type	Article
URI	https://reading-clone.eprints-hosting.org/id/eprint/105037
Item Type	Article
Refereed	Yes
Divisions	Science > School of Mathematical, Physical and Computational Sciences > Department of Computer Science
Uncontrolled Keywords	pseudoboolean constraints sports timetabling International Timetabling Competition RobinX
Additional Information	Extended version of a paper published at Practice and Theory of Automated Timetabling (PATAT) 2021 about an entry to the International Timetabling Competition (ITC) 2021.
Publisher	Springer
Download/View statistics	View download statistics for this item