Pseudo-Boolean optimisation for RobinX sports timetabling
Open Access
- 18 June 2022
- journal article
- research article
- Published by Springer Nature in Journal of Scheduling
- Vol. 25 (3) , 287-299
Abstract
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 pseudo-Boolean (PB) optimisation problem; this instance can be solved using existing pseudo-Boolean 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%.Keywords
This publication has 21 references indexed in Scilit:
- PBLib – A Library for Encoding Pseudo-Boolean Constraints into CNF2015
- Expressively Modeling the Social Golfer Problem in SATProcedia Computer Science, 2015
- Conflict-driven answer set solving: From theory to practiceArtificial Intelligence, 2012
- An effective greedy heuristic for the Social Golfer ProblemAnnals of Operations Research, 2011
- Using a SAT-solver to schedule sports leaguesJournal of Scheduling, 2010
- An improved SAT formulation for the social golfer problemAnnals of Operations Research, 2010
- Round robin scheduling – a surveyEuropean Journal of Operational Research, 2008
- A Schedule-Then-Break Approach to Sports TimetablingLecture Notes in Computer Science, 2001
- Scheduling a Major College Basketball Conference—RevisitedOperations Research, 2001
- Optimal Scheduling for Even-Numbered Team Athletic ConferencesA I I E Transactions, 1977