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 theFCC. 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 99items and are substantially larger and more diÆcult 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. For auction #31, the FCC isgoingto use a code thatis based on the presented work, but extended and adapted to the details of the FCC-rules for this auction.