International Timetabling Competition 2019 – ITC2019.org
We are the winners! The final score is available here. [Paper][Presentation][Video]
The ITC 2019 has described a general formulation of the tactical level university timetabling problem. The competition provides real data from universities worldwide. We have implemented a high-performance algorithm to solve any university timetabling problem formulated in the ITC2019 format.
Our algorithm is based on a Mixed Integer Programming model which provides us with information about a lower bound and when an instance is solved to optimality.
5 of our solutions to the ITC 2019 instances are proven optimal.
We have improved 21 of our competition solutions since the competition deadline (November 18, 2019).
Most recent improvement: March 27, 2023.
Instance | Best solution | Lower bound | Gap | Competition solution | |
---|---|---|---|---|---|
1 Early | agh-fis-spr17 | 2,985 | 1,429 | 52.13% | 3,081 |
1 Early | agh-ggis-spr17 | 34,285 | 23,164 | 32.44% | 35,808 |
1 Early | bet-fal17 | 289,452 | 89,278 | 69.16% | 290,086 |
1 Early | iku-fal17 | 18,968 | 18,109 | 4.53% | 18,968 |
1 Early | mary-spr17 | 14,910 | 14,486 | 2.84% | 14,910 |
1 Early | muni-fi-spr16 | 3,752 | 3,621 | 3.49% | 3,756 |
1 Early | muni-fsps-spr17 | 868 | 868 | 0.00% | 868 |
1 Early | muni-pdf-spr16c | 32,762 | 16,255 | 50.38% | 36,487 |
1 Early | pu-llr-spr17 | 10,038 | 10,038 | 0.00% | 10,038 |
1 Early | tg-fal17 | 4,215 | 4,215 | 0.00% | 4,215 |
2 Middle | agh-ggos-spr17 | 2,855 | 1,982 | 30.58% | 3,055 |
2 Middle | agh-h-spr17 | 21,161 | 8,945 | 57.73% | 23,502 |
2 Middle | lums-spr18 | 95 | 24 | 74.74% | 95 |
2 Middle | muni-fi-spr17 | 3,738 | 2,549 | 31.81% | 3,825 |
2 Middle | muni-fsps-spr17c | 2,594 | 1,361 | 47.53% | 2,596 |
2 Middle | muni-pdf-spr16 | 17,159 | 13,719 | 20.05% | 18,151 |
2 Middle | nbi-spr18 | 18,014 | 18,014 | 0.00% | 18,014 |
2 Middle | pu-d5-spr17 | 15,377 | 6,981 | 54.60% | 15,910 |
2 Middle | pu-proj-fal19 | 147,712 | 67,549 | 54.27% | 148,016 |
2 Middle | yach-fal17 | 1,135 | 526 | 57.13% | 1,239 |
3 Late | agh-fal17 | 140,194 | 6,522 | 95.35% | 186,200 |
3 Late | bet-spr18 | 348,524 | 76,489 | 78.05% | 348,589 |
3 Late | iku-spr18 | 25,863 | 25,855 | 0.03% | 25,878 |
3 Late | lums-fal17 | 349 | 254 | 27.22% | 349 |
3 Late | mary-fal18 | 4,331 | 3,546 | 18.13% | 4,422 |
3 Late | muni-fi-fal17 | 2,837 | 1,890 | 33,38% | 2,999 |
3 Late | muni-fspsx-fal17 | 10,645 | 7,869 | 26.08% | 17,074 |
3 Late | muni-pdfx-fal17 | 82,258 | 29,333 | 64.34% | 117,412 |
3 Late | pu-d9-fal19 | 38,834 | 32,321 | 16.77% | 43,006 |
3 Late | tg-spr18 | 12,704 | 12,704 | 0.00% | 12,704 |
Holm et al. (2022) describe a reduction procedure of the ITC 2019 datasets. These reduced datasets were used during the competition and are available for download here.
Holm (2022) describe additional methods to further reduce the datasets. We implemented these methods after the competition deadline and the datasets are available here.
Contact dsho@dtu.dk regarding problems with the datasets.
DTU: https://www.dtu.dk/nyheder/nyhed?id=%7B3EF69D8B-ABBB-4710-B0AA-F7ED3AABB8B4%7D (Danish)
https://www.dtu.dk/english/news/nyhed?id=%7BD1BAE83B-A366-4703-BC81-42FC2610ABD9%7D (English)
Videnskab.dk: https://videnskab.dk/teknologi-innovation/danskere-vinder-guld-til-vm-i-skemalaegning (Danish)
Ingeniøren/DataTech: https://pro.ing.dk/datatech/artikel/dtu-phder-vandt-verdensmesterskabet-i-skemalaegning-vi-har-brugt-sindssygt-lang (Danish)
Jyllands-Posten: https://jyllands-posten.dk/nyviden/ECE12396156/vmguld-til-danskere-i-disciplinen-skemalaegning/ (Danish)