Set Covering

Problem Description

In a set covering (SC) instance, we are given \(m\) elements and a collection \(S\) of \(n\) sets whose union is the set of all elements, each set having a cost. The goal is to select a minimum-cost subcollection of \(S\) whose union is still the set of all elements.

All levels are generated with the generator of [Gasse19] (the very hard levels of [Huang23], which follow [Wu21], use the same generator), which follows Balas and Ho (1980): the element-set incidence matrix has a fixed density of 0.05 (exactly \(\lfloor 0.05\,mn\rfloor\) nonzeros), every element belongs to at least one set, every set contains at least 2 elements, and the set costs are integers drawn uniformly from \(\{1,\dots,100\}\).

Notation.

Formulation.

\begin{align} \min\ & \sum_{s\in S} c_s x_s \\ \textrm{s.t.}\ & \sum_{s\in S:\, i\in s} x_s \geq 1, && \forall i\in U, \\ & x_s\in\{0,1\}, && \forall s\in S. \end{align}

There is one covering constraint per element (\(m\) constraints) and one binary variable per set (\(n\) variables).

Instance distributions

The table below summarizes the distributions that have been used in previous works and availability in Distributional MIPLIB, along with download links.

Hardness Level Dist Source
(ML4MILPs)		 # Var B # Var I # Var C # Constr#Element#SetDensitySet Cost Related Literature
Easy [Gasse19] 1000 0 0 5005001,0000.05U{1,...,100} Branching [Gasse19, Gupta20]
Medium [Gasse19] 1000 0 0 10001,0001,0000.05U{1,...,100} Branching [Gasse19,Gupta20]
Hard [Gasse19] 1000 0 0 20002,0001,0000.05U{1,...,100} Branching [Gasse19, Gupta20]
Very hard [Huang23] 4000 0 0 50005,0004,0000.05U{1,...,100} LNS [Wu21,Huang23,Huang23b]
Very hard 2 [Huang23] 8000 0 0 50005,0008,0000.05U{1,...,100} LNS [Huang23]

Generator

Generators are available at Learn2Branch.

License

The SC instances data in Distributional MIPLIB is licensed under a CC BY 4.0 license .

Instances for SC in Distributional MIPLIB were generated with code from [Gupta20] (code publicly available at https://github.com/ds4dm/learn2branch/tree/master; under the MIT License Learn2Branch License ).

Related Literature

Learning to Branch

For learning to branch, SC has been used as a benchmark in [Gasse19, Gupta20] where their generator could be found here. In addition, Ecole has a generator for SC instances that allows customized problem parameters. For 1-hour runtime limit with SCIP, the typical problem sizes that have been used range from 500 to 2,000 sets with 1,000 elements.

Large Neighborhood Search (LNS)

For large neighborhood search, CA has been used in [Wu21, Huang23, Huang23b]. For 1-hour runtime limit,  the typical problem sizes that have been used range from 1,000 to 8,000 sets with 5,000 elements.

Citation

Any work that uses any of the above instances should cite the papers below:

Distributional MIPLIB

@misc{huang2024distributional,
      title={Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methods}, 
      author={Weimin Huang and Taoan Huang and Aaron M Ferber and Bistra Dilkina},
      year={2024},
      eprint={2406.06954},
      archivePrefix={arXiv},
      primaryClass={cs.LG}
}

References

[Gasse19] Gasse, Maxime, et al. "Exact combinatorial optimization with graph convolutional neural networks." In Advances in Neural Information Processing Systems, vol. 32, 2019. [paper]

[Gupta20] Gupta, Prateek, et al. "Hybrid models for learning to branch." In Advances in Neural Information Processing Systems, vol. 33, pp. 18087–18097, 2020. [paper]

[Wu21] Wu, Yaoxin, Wen Song, Zhiguang Cao, and Jie Zhang. "Learning large neighborhood search policy for integer programming." In Advances in Neural Information Processing Systems, vol. 34, pp. 30075–30087, 2021. [paper]

[Huang23] Huang, Taoan, et al. "Searching large neighborhoods for integer linear programs with contrastive learning." In International Conference on Machine Learning (ICML), PMLR vol. 202, pp. 13869–13890, 2023. [paper]

[Huang23b] Huang, Taoan, et al. "Local branching relaxation heuristics for integer linear programs." In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR), pp. 96–113, 2023. [paper]