Join
Open set-covering and set-partitioning instances in MIPLIB 2017
Beat the best known costs, or prove them optimal, on 16 open MIPLIB set-covering and set-partitioning instances from crew and vehicle scheduling.
State the problem, from MIPLIB 2017
Browse files shoal committed 2 weeks ago
0 parents
commit a76d4a859dc205ee8cc40fb1c03d654d4c589967
+55 −0 README.md added View file
| @@ -0,0 +1,55 @@ | ||
| 1 | +# Open set-covering and set-partitioning instances in MIPLIB 2017 | |
| 2 | + | |
| 3 | +Set covering and set partitioning are the combinatorial core of crew and vehicle scheduling for railways and buses. MIPLIB 2017 still lists sixteen instances of these two problems as open: some of their best solutions improved as recently as 2026, yet none has been proved optimal. | |
| 4 | + | |
| 5 | +## Problem | |
| 6 | + | |
| 7 | +Given a 0–1 matrix $A \in \{0,1\}^{m \times n}$ and column costs $c \in \mathbb{R}^n$, set covering asks for | |
| 8 | + | |
| 9 | +$$\min\; c^{\top}x \quad\text{subject to}\quad Ax \ge \mathbf{1},\; x \in \{0,1\}^n,$$ | |
| 10 | + | |
| 11 | +and set partitioning asks for the same with $Ax = \mathbf{1}$. In the scheduling instances a column is a candidate duty or vehicle rotation, and a row is a task that must be covered at least once, or exactly once. For each instance below, find a cheaper feasible solution or prove that the listed value is optimal. All are pure 0–1 programs except the three `core` instances, which add a few side constraints and continuous variables. | |
| 12 | + | |
| 13 | +| Instance | Rows | Columns | Type | Origin | Best known | | |
| 14 | +|---|---|---|---|---|---| | |
| 15 | +| `scpj4scip` | 1,000 | 99,947 | covering | random | 128 | | |
| 16 | +| `scpk4` | 2,000 | 100,000 | covering | random | 318 | | |
| 17 | +| `scpl4` | 2,000 | 200,000 | covering | random | 259 | | |
| 18 | +| `scpm1` | 5,000 | 500,000 | covering | random | 537 | | |
| 19 | +| `scpn2` | 5,000 | 1,000,000 | covering | random | 485 | | |
| 20 | +| `core2586-950` | 2,589 | 13,226 | covering | Italian railways | 944 | | |
| 21 | +| `core4284-1064` | 4,287 | 21,714 | covering | Italian railways | 1062 | | |
| 22 | +| `core4872-1529` | 4,875 | 24,656 | covering | Italian railways | 1530 | | |
| 23 | +| `ramos3` | 2,187 | 2,187 | covering | product manufacturing | 186 | | |
| 24 | +| `ex1010-pi` | 1,468 | 25,200 | covering | logic synthesis | 233 | | |
| 25 | +| `ivu06` | 1,177 | 787,239 | partitioning | transit duty scheduling | 142.86 | | |
| 26 | +| `ivu06-big` | 1,177 | 2,277,736 | partitioning | transit duty scheduling | 140.74 | | |
| 27 | +| `ivu59` | 3,436 | 2,569,996 | partitioning | transit duty scheduling | 912.70 | | |
| 28 | +| `ds-big` | 1,042 | 174,997 | partitioning | bus driver duties | 194.498 | | |
| 29 | +| `t1717` | 551 | 73,885 | partitioning | Telebus, Berlin | 158,260 | | |
| 30 | +| `t1722` | 338 | 36,630 | partitioning | Telebus, Berlin | 108,953 | | |
| 31 | + | |
| 32 | +## Background | |
| 33 | + | |
| 34 | +The `core` instances come from the Italian railways crew-scheduling models used by Caprara, Fischetti and Toth (1999). The five `scp` instances were produced by Shunji Umetani's generator, which follows the scheme of Balas and Ho (1980): integer costs between 1 and 100, every column covers at least one row and every row is covered by at least two columns. The `ivu` instances arise from column generation for duty scheduling in public transport (Borndörfer, Löbel and Weider, 2008), and `t1717` and `t1722` are vehicle-scheduling problems from Telebus, Berlin's transport service for people with disabilities. The largest, `ivu59`, has about 2.6 million columns. | |
| 35 | + | |
| 36 | +## What is known | |
| 37 | + | |
| 38 | +- The values in the table are MIPLIB's best known objectives (solution file version 37, 24 September 2026), except for `scpm1`: its instance page lists a solution of value 537 with no violations (Yuya Hattori and Masaaki Hirose, 16 October 2024), while its summary line and the solution file still give 540. MIPLIB publishes no dual bounds, so the remaining gap is not recorded by the source. | |
| 39 | +- The records are still moving: `ds-big` and `ivu59` were last improved in June and July 2026 by Yuji Shinano and Stefan Vigerske, and `scpk4`, `scpm1` and `scpn2` in 2024. | |
| 40 | + | |
| 41 | +## What would count as progress | |
| 42 | + | |
| 43 | +- A solution file in MIPLIB's SOL format with a lower objective than the table. MIPLIB's solution checker verifies feasibility and recomputes the objective in exact arithmetic within seconds. | |
| 44 | +- A proof that a listed value is optimal, for example a lower bound that matches it, backed by a certificate an independent checker can replay. This is a separate and much harder kind of progress. | |
| 45 | + | |
| 46 | +## References | |
| 47 | + | |
| 48 | +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 | |
| 49 | +2. A. Caprara, M. Fischetti and P. Toth (1999). A heuristic method for the set covering problem. *Operations Research* 47, 730–743. https://doi.org/10.1287/opre.47.5.730 | |
| 50 | +3. E. Balas and A. Ho (1980). Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study. *Mathematical Programming Studies* 12, 37–60. https://doi.org/10.1007/BFb0120886 | |
| 51 | +4. R. Borndörfer, A. Löbel and S. Weider (2008). A bundle method for integrated multi-depot vehicle and duty scheduling in public transit. In *Computer-aided Systems in Public Transport*, LNEMS 600, 3–24. https://doi.org/10.1007/978-3-540-73312-6_1 | |
| 52 | + | |
| 53 | +## Source | |
| 54 | + | |
| 55 | +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. | |