Accessibility navigation


Reprobate at ITC 2021: pseudoboolean optimisation for RobinX sports timetabling

Lester, M. ORCID: https://orcid.org/0000-0002-2323-1771 (2021) Reprobate at ITC 2021: pseudoboolean optimisation for RobinX sports timetabling. In: 13th International Conference on the Practice and Theory of Automated Timetabling - PATAT 2021, 23 Aug 2022 - 26 Aug 2022, Bruges, Belgium. (In Press)

[img] Text - Accepted Version
· Restricted to Repository staff only
· The Copyright of this document has not been checked yet. This may affect its availability.

328kB

It is advisable to refer to the publisher's version if you intend to cite from this work. See Guidance on citing.

Abstract/Summary

We report on the development of Reprobate, a tool for solving sports timetabling problems in 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 tune 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 tuning process yielded an average reduction in solution cost of 23%.

Item Type:Conference or Workshop Item (Paper)
Refereed:Yes
Divisions:Science > School of Mathematical, Physical and Computational Sciences > Department of Computer Science
ID Code:99149

University Staff: Request a correction | Centaur Editors: Update this record

Page navigation