A Branch-and-Price Algorithm and New Test Problems for Spectrum Auctions

Oktay Günlük (), Lászlo Ladányi () and Sven de Vries ()
Additional contact information
Oktay Günlük: IBM Research Division, T. J. Watson Research Center, Yorktown Heights, New York 10598
Lászlo Ladányi: IBM Research Division, T. J. Watson Research Center, Yorktown Heights, New York 10598
Sven de Vries: Zentrum Mathematik, Technische Universität München, Boltzmannstr. 3, D-85747 Garching bei München, Germany

Management Science, 2005, vol. 51, issue 3, 391-406

Abstract: When combinatorial bidding is permitted in auctions, such as the proposed FCC Auction #31, the resulting full valuations and winner-determination problem can be computationally challenging. We present a branch-and-price algorithm based on a set-packing formulation originally proposed by Dietrich and Forrest (2002, "A column generation approach for combinatorial auctions," in Mathematics of the Internet: E-Auction and Markets. The IMA Volumes in Mathematics and Its Applications, Vol. 127, Springer-Verlag, New York, 15--26). This formulation has a variable for every possible combination of winning bids for each bidder. Our algorithm exploits the structure of the XOR-of-OR bidding language used by the FCC. We also present a new methodology to produce realistic test problems based on the round-by-round results of FCC Auction #4. We generate 2,639 test problems, which involve 99 items and are substantially larger than most of the previously used benchmark problems. Because there are no real-life test problems for combinatorial spectrum auctions with the XOR-of-OR language, we used these test problems to observe the computational behavior of our algorithm. Our algorithm can solve all but one test problem within 10 minutes, appears to be very robust, and for difficult instances compares favorably to the natural formulation solved using a commercial optimization package with default settings. Although spectrum auctions are used as the guiding example to describe the merits of branch and price for combinatorial auctions, our approach applies to auctions of multiple goods in other scenarios similarly.

Keywords: combinatorial auctions; branch-and-price; spectrum auctions; test problems (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.1040.0332 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:51:y:2005:i:3:p:391-406

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().