Combinatorial Auctions

Problem Description

In the Combinatorial Auction (CA) problem, \(n\) bids \((B_i, p_i)\) for subsets of \(m\) items are given, where \(B_i\) is the subset (bundle) of items requested by bid \(i\) and \(p_i\) is its bidding price. The objective is to accept a set of pairwise compatible bids (no item is sold twice) that maximizes the total revenue.

All instances in this library are generated with the arbitrary relationships scheme of [Leyton-Brown00] (Section 4.3), using the generator of [Gasse19] (very easy, easy and medium levels; the very hard levels of [Huang23] use the same generator with 2,000/4,000 items and 4,000/8,000 bids). Each bidder submits an initial bundle (built by adding items one by one with probability 0.7, guided by the bidder's private interests and pairwise item compatibilities) together with up to 5 substitutable bundles that share at least one item with the initial one, i.e. at most 6 bids per bidder. A bundle's price is the sum of the bidder's private item values (common resale value drawn uniformly from \([1,100]\), perturbed by up to \(\pm 50\)) plus a super-additive term \(|B_i|^{1.2}\); prices are real-valued. A bidder's bids are mutually exclusive (XOR bids). When a bidder places 3 or more bids, the generator encodes this exclusivity with a dummy item that is added to all of that bidder's bundles; bidders with exactly 2 bids need no dummy item because a substitutable bundle always shares an item with the initial bundle. The regions distribution of [Leyton-Brown00] is not used here.

Notation.

Formulation.

\begin{align} \max\ & \sum_{i\in N} p_i x_i \\ \textrm{s.t.}\ & \sum_{i\in N:\, j\in B_i} x_i \leq 1, && \forall j\in M^+, \\ & \sum_{i\in N_k} x_i \leq 1, && \forall k\in K, \\ & x_i\in\{0,1\}, && \forall i\in N. \end{align}

The second family is the item constraint of the dummy items, so in the files every constraint has the same form \(\sum_{i: j\in B_i} x_i\le 1\) over the extended item set \(M^+\cup K\), and the number of constraints is \(|M^+|+|K|\). This is why the constraint count exceeds the number of items (e.g. about 192 constraints for 100 items: roughly 100 item rows plus about 90 dummy-item rows).

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#Item#BidBid Distribution Related Literature
Very easy [Gasse19] 500 0 0 192.2100500Arbitrary [Leyton-Brown00] Branching [Gasse19,Gupta20]
Easy [Gasse19] 1000 0 0 385.042001,000Arbitrary [Leyton-Brown00] Branching [Gasse19, Gupta20]; Backdoor [Cai24, Cai25]
Medium [Gasse19] 1500 0 0 578.073001,500Arbitrary [Leyton-Brown00] Branching [Gasse19, Gupta20]
Very hard [Huang23] 4000 0 0 2676.322,0004,000Arbitrary [Leyton-Brown00] LNS [Song20, Wu21, Huang23]; PaS [Huang24, Cai25]; Configuration [Cai25]
Very hard 2 [Huang23] 8000 0 0 5351.954,0008,000Arbitrary [Leyton-Brown00] LNS [Song20, Wu21, Huang23]

Generator

Generators are available at Learn2Branch.

License

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

Instances for CA 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, CA has been used as a benchmark in [Gasse19, Gupta20] where their generator could be found here. In addition, Ecole has a generator for CA instances that allows customized problem parameters.  For 1-hour runtime limit with SCIP, the typical problem sizes that have been used range from 100 items with 500 bids to 500 items with 1500 bids.

Large Neighborhood Search (LNS)

For large neighborhood search, CA has been used in [Song20, Wu21, Huang23]. For 1-hour runtime limit,  the typical problem sizes that have been used range from 2,000 items and 4,000 bids to 8,000 items and 16,000 bids. In addition to the distributions complied in Distributional MIPLIB shown in the table above, [Wu21] used CA instances with 8000 items and 16000 bids.

The table above summarizes the distributions that have been used in previous works and availability in Distributional MIPLIB. All these instances follow the arbitrary distribution.

Backdoor

For learning backdoors, CA has been used as a benchmark in [Cai25], which trains on instances with 175 items and 850 bids, and tests on instances of the same size as well as on larger instances with 200 items and 1,000 bids (the Easy distribution in Distributional MIPLIB). [Cai24] trains on instances with 150 items and 750 bids, and tests on instances of the same size as well as on larger instances with 200 items and 1,000 bids (the Easy distribution).

Predict-and-Search (PaS)

For predict-and-search, CA has been used as a benchmark in [Huang24] and [Cai25], which train on instances with 2,000 items and 4,000 bids (the Very hard distribution in Distributional MIPLIB), and test on instances of the same size as well as on larger instances with 3,000 items and 6,000 bids.

Solver Configuration

For solver configuration, CA has been used as a benchmark in [Cai25], which trains on instances with 2,000 items and 4,000 bids (the Very hard distribution in Distributional MIPLIB), and tests on instances of the same size as well as on larger instances with 3,000 items and 6,000 bids.

Citation

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

Original Formulation

@inproceedings{leyton2000towards,
  title={Towards a universal test suite for combinatorial auction algorithms},
  author={Leyton-Brown, Kevin and Pearson, Mark and Shoham, Yoav},
  booktitle={Proceedings of the 2nd ACM conference on Electronic commerce},
  pages={66--76},
  year={2000}
}

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

[Leyton-Brown00] Leyton-Brown, Kevin, Mark Pearson, and Yoav Shoham. "Towards a universal test suite for combinatorial auction algorithms." In Proceedings of the 2nd ACM Conference on Electronic Commerce, pp. 66–76, 2000. [paper]

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

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

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

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

[Cai24] Cai, Junyang, Taoan Huang, and Bistra Dilkina. "Learning backdoors for mixed integer linear programs with contrastive learning." In European Conference on Artificial Intelligence (ECAI), 2024. [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]