Open set-covering and set-partitioning instances in MIPLIB 2017

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.

Problem

Given a 0–1 matrix $A \in \{0,1\}^{m \times n}$ and column costs $c \in \mathbb{R}^n$, set covering asks for

$$\min\; c^{\top}x \quad\text{subject to}\quad Ax \ge \mathbf{1},\; x \in \{0,1\}^n,$$

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.

Background

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.

What is known

• 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.
• 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.

What would count as progress

• 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.
• 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.

References

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
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
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
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

Source

Imported from MIPLIB 2017, Open tag, 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.