加入
Open timetabling instances in MIPLIB 2017
Find better course, school or public-transport timetables, or prove optimality, on seven open MIPLIB 2017 timetabling instances.
shoal 2周前提交
0 个父提交
提交 af27d94cbd148e69ff171f85a2295f8aba529ba1
+45 −0 README.md 新增 查看文件
| @@ -0,0 +1,45 @@ | ||
| 1 | +# Open timetabling instances in MIPLIB 2017 | |
| 2 | + | |
| 3 | +Seven open MIPLIB 2017 instances come from timetabling: course and school timetables at real universities and schools, and periodic or energy-aware timetables for public transport. Four of their best solutions improved during 2026, yet none has been proved optimal. | |
| 4 | + | |
| 5 | +## Problem | |
| 6 | + | |
| 7 | +Each instance is a mixed-integer linear program, given as an MPS file, that minimises a weighted penalty or cost over timetables satisfying hard constraints such as room capacities, clashes between courses or students, and timing windows. For each instance below, find a feasible solution with a lower objective value than the best known, or prove that the best known value is optimal. | |
| 8 | + | |
| 9 | +| Instance | Application | Variables | Best known | Last improved | | |
| 10 | +|---|---|---|---|---| | |
| 11 | +| `comp12-2idx` | curriculum-based course timetabling (ITC2007 instance comp12, time assignment stage) | 11,863 | 277 | July 2024 | | |
| 12 | +| `kottenpark09` | educational timetabling in the XHSTT format | 2,893,026 | 1,715 | July 2020 | | |
| 13 | +| `rwth-timetable` | university course timetabling, RWTH Aachen | 923,564 | 772,347 | July 2026 | | |
| 14 | +| `tpl-tub-ws1617` | post-enrolment course timetabling, TU Berlin | 747,601 | 121,065 | July 2026 | | |
| 15 | +| `splan1` | university course timetabling | 1,317,382 | −194,385.04 | June 2026 | | |
| 16 | +| `r4l4-02-tree-bounds-50` | periodic timetabling in public transport (PESP) | 11,468 | 499,061,405 | September 2026 | | |
| 17 | +| `zeil` | shifting train departures to minimise peak power use | 70,116 | 1,081.3585 | October 2024 | | |
| 18 | + | |
| 19 | +## Background | |
| 20 | + | |
| 21 | +Timetabling is a classic application of integer programming in which real instances are large and heavily constrained. `comp12-2idx` is the first stage of a decomposition of an instance from the 2007 International Timetabling Competition (Lach and Lübbecke, 2012; Bonutti et al., 2012). `kottenpark09` comes from the XHSTT format for real educational timetabling problems, for which Fonseca, Santos, Carrano and Stidsen (2017) studied integer programming techniques. `r4l4-02-tree-bounds-50` is a Periodic Event Scheduling Problem built from data of the LinTim project and the PESPlib collection (Goerigk, Schachtebeck and Schöbel, 2013), and `zeil` adapts a draft railway timetable for a small part of the German network so that the peak power consumption, averaged over 15-minute intervals, is as small as possible. | |
| 22 | + | |
| 23 | +## What is known | |
| 24 | + | |
| 25 | +- The values above are MIPLIB's best known objectives (solution file version 37, 24 September 2026); MIPLIB publishes no dual bounds for them. | |
| 26 | +- `rwth-timetable` and `tpl-tub-ws1617` were improved on 21 July 2026 by Michael Winkler and Ed Klotz with Gurobi 13.0 at default settings apart from a zero MIP gap, and `splan1` on 9 June 2026 by Yuji Shinano and Stefan Vigerske. | |
| 27 | +- The current best for `r4l4-02-tree-bounds-50` was found on 22 September 2026 by Yicheng Huang, Wenzhi Gao, Dongdong Ge, Madeleine Udell and Yinyu Ye. | |
| 28 | +- For `kottenpark09`, Ed Klotz reports that CPLEX needed about 10 hours on 12 threads to reach solutions in the 4,000 to 5,000 range; the best value has stood since 2020. | |
| 29 | + | |
| 30 | +## What would count as progress | |
| 31 | + | |
| 32 | +- A solution file in MIPLIB's SOL format with a lower objective than the table. MIPLIB's solution checker verifies integrality, bounds and every constraint in exact arithmetic and recomputes the objective within seconds. | |
| 33 | +- A proof that a listed value is optimal, for example a matching dual bound with a certificate that can be checked independently. This is a separate and much harder kind of progress than a better solution. | |
| 34 | + | |
| 35 | +## References | |
| 36 | + | |
| 37 | +1. A. Gleixner et al. (2021). MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library. *Mathematical Programming Computation* 13, 443–490. https://doi.org/10.1007/s12532-020-00194-3 | |
| 38 | +2. G. Lach and M. E. Lübbecke (2012). Curriculum based course timetabling: new solutions to Udine benchmark instances. *Annals of Operations Research* 194, 255–272. https://doi.org/10.1007/s10479-010-0700-7 | |
| 39 | +3. A. Bonutti, F. De Cesco, L. Di Gaspero and A. Schaerf (2012). Benchmarking curriculum-based course timetabling: formulations, data formats, instances, validation, visualization, and results. *Annals of Operations Research* 194, 59–70. https://doi.org/10.1007/s10479-010-0707-0 | |
| 40 | +4. G. H. G. Fonseca, H. G. Santos, E. G. Carrano and T. J. R. Stidsen (2017). Integer programming techniques for educational timetabling. *European Journal of Operational Research* 262, 28–39. https://doi.org/10.1016/j.ejor.2017.03.020 | |
| 41 | +5. M. Goerigk, M. Schachtebeck and A. Schöbel (2013). Evaluating line concepts using travel times and robustness. *Public Transport* 5, 267–284. https://doi.org/10.1007/s12469-013-0072-x | |
| 42 | + | |
| 43 | +## Source | |
| 44 | + | |
| 45 | +Imported from [MIPLIB 2017, Open tag](https://miplib.zib.de/tag_open.html), curated by Zuse Institute Berlin. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion. | |