A fix-and-optimize heuristic for the ITC2021 sports timetabling problem.
No Thumbnail Available
Date
2022
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This paper addresses the general and challenging Sports Timetabling Problem proposed during the International Timetabling
Competition of 2021 (ITC2021). The problem is expressed in a flexible format which enables modeling a number of real-world
constraints that often occur in Sports Timetabling. An integer programming (IP) formulation and a fix-and-optimize heuristic
are proposed to address the problem. The fix-and-optimize approach uses the IP formulation to heuristically decompose the
problem into sub-problems and efficiently search on very large neighborhoods. The diverse ITC2021 benchmark instances
were used to evaluate the proposed methods. The formulation resulted in proven optimal solutions for two instances. However,
it failed to produce feasible solutions for most instances. The proposed fix-and-optimize, which uses an automatic sub-problem
size calibration strategy, resulted in feasible solutions for 37 out of the 45 ITC2021 instances. Among these solutions, four
are the best known in the literature. The proposed approach participated in the ITC2021 and was one of the finalists.
Description
Keywords
Sports timetabling, Round robin tournament, Fix-and-optimize
Citation
FONSECA, G. H. G. da; TOFFOLO, T. A. M. A fix-and-optimize heuristic for the ITC2021 sports timetabling problem. Journal of Scheduling, v. 25, p. 273-286, jun. 2022. Disponível em: <https://link.springer.com/article/10.1007/s10951-022-00738-6>. Acesso em: 03 maio 2023.