Towards a universal test suite for combinatorial auction algorithms

By Kevin Leyton-Brown, Mark Pearson, Yoav Shoham. ACM Conference on Economics and Computation, 2000

468 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Management Science and Operations Research, Marketing

View Paper: https://www.semanticscholar.org/paper/102edd6b6ec078daa064ec8bda142aa7bc60431d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Management Science and Operations Research

In Marketing

Citations in the corpus

Sequential Model-Based Optimization for General Algorithm Configuration (2011, background): “These instances come from the following domains: quasigroup completion, QCP [37]; small world graph colouring, SWGCP [38]; winner determination in combinatorial auctions, REGIONS100 [41]; mixed integer knapsack, MIK [42].”
Efficient Benchmarking of Algorithm Configuration Procedures via Model-Based Surrogates (2017, methodology): “CPLEX-Regions is a MIP benchmark based on the well-known IBM ILOG CPLEX solver, applied to MIP-encoded instances of the combinatorial auction winner determination problem (Leyton-Brown et al 2000).”
Instance-Specific Algorithm Configuration (2014, background): “Network flow instances, capacitated facility location instances, bounded and unbounded mixed knapsack instances and capacitated lot sizing problems, all taken from [82], as well as combinatorial auction instances from [59].”
Automated configuration of algorithms for solving hard computational problems (2009, methodology): “Scenario Type of benchmark instances & citation # training # test CPLEX-REGIONS200 Combinatorial Auctions (CATS) (Leyton-Brown et al., 2000) 1 000 1 000 CPLEX-MJA Machine-Job Assignment (BCOL) (Aktürk et al.”
ParamILS: An Automatic Algorithm Configuration Framework (2014, methodology): “We used the regions generator from the Combinatorial Auction Test Suite (Leyton-Brown et al., 2000), with the goods parameter set to 100 and the bids parameter set to 500.”
Parallel Algorithm Configuration (2012, unknown): “273% REGIONS200 Combinatorial winner determination [21] 1000 1000 0% 1.”
Automatically improving the anytime behaviour of optimisation algorithms (2014, background): “The benchmark set is composed of 2 000 MIP-encoded instances (200 goods, 1000 bids) of the NP-hard winner determination problem for combinatorial auctions [31, 37].”
Exact Combinatorial Optimization with Graph Convolutional Neural Networks (2019, methodology): “Our second benchmark is comprised of combinatorial auction instances, generated following the arbitrary relationships procedure of Leyton-Brown et al. [37, Section 4.3].”
Automated Configuration of Mixed Integer Programming Solvers (2010, methodology): “We generated them using the regions generator from the Combinatorial Auction Test Suite [22], with parameters goods=100 and bids=500.”
Algorithm runtime prediction: Methods & evaluation (2012, methodology): “We generated 2000 instances using the regions generator from the Combinatorial Auction Test Suite [77], with the number of bids selected uniformly at random from between 750 and 1250, and a fixed bids/goods ratio of 3.”
Boosting as a Metaphor for Algorithm Design (2003, methodology): “Our instance distribution involved making a uniform choice between nine of the distributions from the Combinatorial Auction Test Suite (CATS) [11], and randomly choosing parameters for each instance.”
Learning the Empirical Hardness of Optimization Problems: The Case of Combinatorial Auctions (2002, methodology): “Subsequent research has exposed a variety of problems with t hese legacy distributions: see, for example, [2, 4, 15].”
ISAC - Instance-Specific Algorithm Configuration (2010, background): “and unbounded mixed knapsack instances and capacitated lot sizing problems, all taken from [25], as well as combinatorial auction instances from [21].”
Learning to Search in Branch and Bound Algorithms (2014, background): “We have demonstrated on multiple datasets that compared to a commercial solver, our approach finds solutions with a better objective and establishes a smaller gap, using less time.”
Hydra-MIP : Automated Algorithm Configuration and Selection for Mixed Integer Programming (2011, methodology): “We generated 500 training and 500 test instances using the regions generator from the Combinatorial Auction Test Suite [22], with the number of bids selected uniformly at random from between 750 and 1250, and a fixed bids/goods ratio of 3.91 (following [21]).”