Combinatorial Auctions and Knapsack Problems - Online Resources (publications, test data, implemented algorithms)


Publications (see also the home pages of the People listed below)

  • Bibtex file for papers on combinatorial auctions and multidimensional knapsack problems (please send additions or corrections to holte@cs.ualberta.ca)

  • A summary of the complexity results for Maximum Set packing, the weighted version of which is equivalent to a single-unit combinatorial auction. Most noteworthy is that if k is the maximum number of items in a bid, you can get a solution guaranteed to be within a multiplicative factor of (k-1)+epsilon, or within 2(k+1)/3 for any epsilon ; moreover if no item has more than B bids bidding for it, you can get within a multiplicative factor of B of optimal. The web page gives full references for the papers proving the results quoted.
  • Papers in EC-00, the ACM 2000 conference on Electronic Commerce - quite a few on combinatorial auctions.
  • citeseer's entry for "Approximations of Weighted Independent Set and Hereditary Subset Problems" by Magnús M. Halldórsson
  • citeseer's entry for "A note on greedy algorithms for maximum weighted independent set problem" by Shuichi Sakai, Mitsunori Togasaki, and Koichi Yamazaki
  • "Independent sets with domination constraints" by Magnús M. Halldórsson, Jan Kratochvíl, and Jan Arne Telle
  • "Greedy local improvement and weighted set packing approximation" by Barun Chandra and Magnús M. Halldórsson
  • Fascinating account of the evolution of auctions to seel spectrum
  • citeseer's entry for "An Auction-Theoretic Modeling of Production Scheduling to Achieve Distributed Decision Making" by Erhan Kutanoglu
  • citeseer's entry for Noam Nisan's "Bidding and Allocation in Combinatorial Auctions Preliminary version"
  • "Combinatorial Auctions: A Survey" by Sven de Vries and Rakesh Vohra
  • recent papers by R. Battiti (reactive tabu search - RTS) near the bottom of this page, the paper "Local search with memory: Benchmarking RTS" has extensive tests of several algorithms on the multidimensional knapsack problem (also called the multiknapsack problem, but not to be confused with the multiple knapsack problem).
  • A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem. Martin Dyer, Alan Frieze, Ravi Kannan, Ajai Kapoor, Ljubomir Perkovic, and Umesh Vazirani. Combinatorics, Probability and Computing, 2, 1993.
  • "Probabilistic analysis of random m-dimensional knapsack problems", Mathematics of Operations Research 14 , 162-176, M. E. Dyer and A. M. Frieze
  • "Approximation Algorithms for the m-dimensional 0-1 knapsack problem: worst-case and probabilistic analyses", European Journal of Operational Research, 15(1):100-9, 1984, A. M. Frieze and M. R. B. Clarke.
  • A new exact algorithm for general orthogonal d-dimensional knapsack problems Algorithms - ESA '97, Springer Lecture Notes in Computer Science, vol. 1284, 1997, pp. 144-156, . P. Fekete and J. Schepers.
  • An Algorithm for the Multidimensional Multiple-Choice Knapsack Problem, Martin MOSER, Dusan P. JOKANOVIC and Norio SHIRATORI, IEICE Trans. Fundamentals, Vol.E80-A No.3 pp.582-589 1997/3.
    IJCAI'99

    p.520 - William Walsh and Michael Wellman
    p.527 - Craig Boutilier, Moises Goldszmidt, and Bikash Sabata
    p.542 - Tuomas Sandholm (the citeseer link for this, or a closely related paper)
    p.548 - Yuzo Fujishima, Kevin Leyton-Brown, and Yoav Shoham


    AAAI'2000

    p.2 - Holger Hoos and Craig Boutilier (local search)
    p.56 - Kevin Leyton-Brown, Yoav Shoham, and Moshe Tennenholtz (multi-unit)
    p.74 - David Parkes and Lyle Unger
    p.82 - David Parkes and Lyle Unger
    p.90 - Tuomas Sandholm (improved systematic search)
    p.98 - Moshe Tennenholtz
    p.110 - Makoto Yokoo, Yuko Sakurai, and Shiego Matsubara


    Test Data

  • Stanford's combinatorial auction test suite (artificial data generators) ( and here is the README file for CATS)
  • my version, formulated as a combinatorial auction, of the SPOT resource-allocation data (see the link below to get the original SPOT data).
  • Large set of combinatorial auction test problems: (a) based on Sandholm's models, (b) based on their more realistic "quadratic model", and (c) based on actual data from the FCC aubction
  • David Pisinger's code for generating knapsack and bin-packing problems
  • J. E. Beasley's OR-Library home page (test data for many OR problems including the Multidimensional knapsack problem)
  • the Martelli and Toth code (below) has a small test problem in it (as comments at the beginning of the program)
  • these are the test problems used by Joachim Paul Walser - not exactly multi-constraint knapsack problems, but somewhat related (see his monograph "Integer Optiization by Local Search" (1999) Lecture Notes in AI #1637)
  • contains price and nutrition information about McDonald's products, which is used to set up a kind of multidimensional knapsack problem (something like maximize nutritional value while keeping price and daily intake of certain substances (e.g. cholestrol, sodium) below a specified limit).
  • test problems for multiple knapsack problem -- but I suspect they have misnamed this and it is really for the multi-dimensional knapsack problem. This is the test data used by Dammeyer & Voss, by A. Drexel, and by Khuri, Baeck, & Heitkoetter
  • test problems for multiple knapsack problem -- but I suspect they have misnamed this and it is really for the multi-dimensional knapsack problem.
  • test problems for multi-objective knapsack and set-covering problems
  • SPOT weighted CSP data

    Implemented Algorithms

  • David Pisinger's code for solving various knapsack problems (but none for the multidimensional knapsack problem)
  • Martelli and Toth's algorithm for the 0/1 multiple knapsack problem (ACM TOMS (1985) pp.135-140) - algorithm 632 in ACM's "collected algorithms"
  • Joachim Paul Walser's WSAT(OIP) code. (see his monograph "Integer Optiization by Local Search" (1999) Lecture Notes in AI #1637)

    People

  • Esther Arkin (she does research on local search for combinatorial problems such as weighted set packing)
  • Craig Boutilier
  • Yuzo Fujishima (this is not his home page, just his email and postal address)
  • Holger Hoos
  • Daniel Lehmann
  • Kevin Leyton-Brown
  • Dave Pisinger -- includes a link to his PhD thesis (1995), an excellent source of information about various knapsack problems, but unfortunately not for the multidimensional knapsack problem.
  • Tuomas Sandholm
  • Yoav Shoham

    Related pages

  • Michael Trick's Operations Research Page: Resources

    Other pages potentially of interest

  • Guided Local Search
  • Bibliography on local search algorithms
  • Compendium of results on NP-complete problems