Accessibility navigation

Pseudo-Boolean optimisation for RobinX sports timetabling

Lester, M. M. ORCID: (2022) Pseudo-Boolean optimisation for RobinX sports timetabling. Journal of Scheduling, 25. pp. 287-299. ISSN 1099-1425

Text (Open Access) - Published Version
· Available under License Creative Commons Attribution.
· Please see our End User Agreement before downloading.

[img] Text - Accepted Version
· Restricted to Repository staff only


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

To link to this item DOI: 10.1007/s10951-022-00737-7


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%.

Item Type:Article
Divisions:Science > School of Mathematical, Physical and Computational Sciences > Department of Computer Science
ID Code:105037
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.


Downloads per month over past year

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

Page navigation