Maximum Independent Set · Distributional MIPLIB

Problem Description

In a maximum independent set (MIS) problem, an undirected graph \(G=(V,E)\) is given. The goal is to select the largest subset of nodes such that no two selected nodes are connected by an edge in \(G\).

The easy and medium levels are generated with the generator of [Gasse19] on Barabási-Albert graphs with affinity \(m_{BA}=4\) (each new node attaches to 4 existing nodes, so \(|E|=4(|V|-4)\)). This generator does not write one constraint per edge: it first computes a greedy clique partition of \(V\) and replaces the edges inside each clique by a single clique inequality; all remaining edges keep an edge inequality. The very hard levels of [Huang23] are generated on Erdős-Rényi graphs \(G(|V|,p)\) with \(p=8/(|V|-1)\) (expected average degree 8, i.e. about \(4|V|\) edges) and use one edge inequality per edge. All instances are unweighted.

Notation.

\(G=(V,E)\): undirected graph; \(x_v\in\{0,1\}\): 1 if node \(v\in V\) is in the independent set.
\(\mathcal{Q}\): a collection of cliques of \(G\) (each with at least 2 nodes) such that every edge of \(E\) is contained in exactly one \(Q\in\mathcal{Q}\). For the easy and medium levels, \(\mathcal{Q}\) consists of the cliques of size at least 2 of the greedy clique partition plus every edge not inside one of these cliques; for the very hard levels, \(\mathcal{Q}=E\) (every edge is its own 2-clique).

Formulation.

\begin{align} \max\ & \sum_{v\in V} x_v \\ \textrm{s.t.}\ & \sum_{v\in Q} x_v \leq 1, && \forall Q\in\mathcal{Q}, \\ & x_v\in\{0,1\}, && \forall v\in V. \end{align}

With \(\mathcal{Q}=E\) this is the edge formulation \(x_u+x_v\le 1,\ \forall (u,v)\in E\). Since each edge lies in exactly one \(Q\in\mathcal{Q}\), both forms have the same feasible integer solutions; the clique form has slightly fewer rows (e.g. about 3,950 instead of 3,984 for 1,000 nodes) and a tighter LP relaxation.

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	# Constr	#Node	Graph Type	Graph Parameter	Avg. Degree	Related Literature
Easy	[Gasse19]	1000	3946.25	1,000	Barabasi-Albert	affinity m = 4	7.97	Branching [Gasse19,Gupta20]
Medium	[Gasse19]	1500	5941.14	1,500	Barabasi-Albert	affinity m = 4	7.98	Branching, LNS [Gasse19,Gupta20,Wu21]; Backdoor [Cai25]
Very hard	[Huang23]	6000	23996.57	6,000	Erdos-Renyi	p = 8/(n-1) (about 0.00133)	8 (expected)	LNS[Huang23]
Very hard 2	[Huang23]	12000	48009.62	12,000	Erdos-Renyi	p = 8/(n-1) (about 0.00067)	8 (expected)	LNS[Huang23]

Generator

Generators are available at Learn2Branch and Ecole.

License

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

Instances for MIS-Easy and MIS-Medium in Distributional MIPLIB were generated with code from [Gasse19] (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, IS has been used as a benchmark in [Gasse19, Gupta20]. Their generator could be found at Learn2Branch. For 1-hour runtime limit with SCIP, it is tested on IS instances on Barabasi-Albert random graphs with 500, 1,000 and 1,500 nodes and affinity set to 4. (Note that in [Gasse19, Gupta20, Wu21], the papers state the graphs are Erdos-Renyi random graphs. However, the source code indicates they are Barabasi-Albert graphs.)

Large Neighborhood Search

For large neighborhood search, IS has been used in [Wu21, Huang23, Huang23b]. Huang et al. [Huang23] use Erdos-Renyi graphs with 6,000 and 12,000 nodes and affinity set to 4. Huang et al. In addition to the distributions complied in Distributional MIPLIB shown in the table above, Wu et al. [Wu21] use Barabasi-Albert graphs with 1,500, 3,000 and 6,000 nodes and affinity set to 4. [Huang23b] use Barabasi-Albert graphs with 9,000 nodes and affinity set to 5 to test a heuristic.

Backdoor

For learning backdoors, IS has been used as a benchmark in [Cai25], which trains on Barabasi-Albert graphs with 1,250 nodes and affinity set to 4, and tests on graphs of the same size as well as on larger graphs with 1,500 nodes and affinity set to 4 (the Medium 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

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

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