Minimum Vertex Cover

Problem Description

In a minimum vertex cover (MVC) problem, an undirected graph \(G=(V,E)\) is given, with a nonnegative weight on each node. The goal is to select a subset of nodes of minimum total weight such that at least one end point of every edge in the graph is selected.

All levels are generated on Barabási-Albert random graphs with the generator of [Huang23] (based on the generator of [Song20]; the easy, medium and hard levels are new and use the same code with different parameters). A graph with \(|V|\) nodes and affinity \(m_{BA}\) (each new node attaches to \(m_{BA}\) existing nodes) has exactly \(m_{BA}(|V|-m_{BA})\) edges. Node weights are drawn independently and uniformly from \([0,1]\), so the instances are weighted vertex cover problems.

Notation.

Formulation.

\begin{align} \min\ & \sum_{v\in V} w_v x_v \\ \textrm{s.t.}\ & x_u+x_v\geq 1, && \forall (u,v)\in E, \\ & x_v\in\{0,1\}, && \forall v\in V. \end{align}

There is one constraint per edge, so the number of constraints is \(|E|=m_{BA}(|V|-m_{BA})\).

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#NodeGraph TypeGraph ParameterAvg. Degree Related Literature
Easy New 1200 0 0 59751,200Barabasi-Albertaffinity m = 59.96 N/A
Medium New 2000 0 0 99752,000Barabasi-Albertaffinity m = 59.98 Backdoor [Cai25]
Hard New 500 0 0 30100500Barabasi-Albertaffinity m = 70120.4 N/A
Very hard [Huang23] 1000 0 0 651001,000Barabasi-Albertaffinity m = 70130.2 LNS [Huang23]
Very hard 2 [Huang23] 2000 0 0 1351002,000Barabasi-Albertaffinity m = 70135.1 LNS [Huang23]
Very hard 3 [Huang24] 9000 0 0 449759,000Barabasi-Albertaffinity m = 59.99 PaS [Huang24, Cai25]; LNS [Huang23b]

Generator

We provide a generator for MVC at https://github.com/amf272/Distributional-MIPLIB-Generators/tree/main/MVC .

License

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

Related literature

Large Neighborhood Search

For large neighborhood search, Huang et al. [Huang23] use Barabasi-Albert graphs with 1,000 and 2,000 nodes and affinity set to 70. The set of instances with 1000 nodes was used for training. The set of instances with 2000 nodes was used as an out-of-distribution test set. MVC has been used in [Song20, Huang23, Huang23b].  In addition to the distributions complied in Distributional MIPLIB shown in the table above, Song et al. [Song20] use both Erdos-Renyi and Barabasi-Albert graphs with 1,000 nodes and affinity set to 4. Huang et al. [Huang23b] use the Very hard 3 distribution (Barabasi-Albert graphs with 9,000 nodes and affinity set to 5) to test a heuristic.

Backdoor

For learning backdoors, MVC has been used as a benchmark in [Cai25], which trains on Barabasi-Albert graphs with 1,500 nodes and affinity set to 5, and tests on graphs of the same size as well as on larger graphs with 2,000 nodes and affinity set to 5 (the Medium distribution in Distributional MIPLIB).

Predict-and-Search

For predict-and-search, MVC has been used as a benchmark in [Huang24] and [Cai25], which train on Barabasi-Albert graphs with 6,000 nodes and affinity set to 5, and test on graphs of the same size as well as on larger graphs with 9,000 nodes and affinity set to 5 (the Very hard 3 distribution in Distributional MIPLIB).

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

[Song20] Song, Jialin, Ravi Lanka, Yisong Yue, and Bistra Dilkina. "A general large neighborhood search framework for solving integer linear programs." In Advances in Neural Information Processing Systems, vol. 33, pp. 20012–20023, 2020. [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]

[Cai25] Cai, Junyang, Taoan Huang, and Bistra Dilkina. "Multi-task representation learning for mixed integer linear programming." In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR), pp. 134–151, 2025. [paper]

[Huang24] Huang, Taoan, et al. "Contrastive predict-and-search for mixed integer linear programs." In International Conference on Machine Learning (ICML), PMLR vol. 235, pp. 19757–19771, 2024. [paper]