Optimization Online


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

Oktay Gunluk (oktay***at***watson.ibm.com)
Laci Ladanyi (ladanyi***at***watson.ibm.com)
Sven de Vries (devries***at***ma.tum.de)

Abstract: When combinatorial bidding is permitted in Spectrum Auctions, such as the upcoming FCC auction #31, the resulting 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). 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 test problems which involve 99 items and are substantially larger and more difficult than most of the previously used benchmark problems. Since there are no real-life test problems for combinatorial spectrum auctions, we used these test problems to observe the computational behavior of our algorithm. Our algorithm can solve all 2639 test problems, is very robust and compares favorably to the natural formulation solved using a commercial optimization package.

Keywords: integer programming, computation, auctions, FCC

Category 1: Applications -- OR and Management Sciences

Category 2: Integer Programming

Citation: IBM Research Report, RC22530, July 2002.

Download: [Postscript][PDF]

Entry Submitted: 08/30/2002
Entry Accepted: 08/30/2002
Entry Last Modified: 04/26/2004

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society