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

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.

Citation

IBM Research Report, RC22530, July 2002.

Article

Download

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