Deep Optimization for Spectrum Repacking
  Over 13 months in 2016-17 the FCC conducted an "incentive auction" to
repurpose radio spectrum from broadcast television to wireless internet. In the
end, the auction yielded $19.8 billion, $10.05 billion of which was paid to 175
broadcasters for voluntarily relinquishing their licenses across 14 UHF
channels. Stations that continued broadcasting were assigned potentially new
channels to fit as densely as possible into the channels that remained. The
government netted more than $7 billion (used to pay down the national debt)
after covering costs. A crucial element of the auction design was the
construction of a solver, dubbed SATFC, that determined whether sets of
stations could be "repacked" in this way; it needed to run every time a station
was given a price quote. This paper describes the process by which we built
SATFC. We adopted an approach we dub "deep optimization", taking a data-driven,
highly parametric, and computationally intensive approach to solver design.
More specifically, to build SATFC we designed software that could pair both
complete and local-search SAT-encoded feasibility checking with a wide range of
domain-specific techniques. We then used automatic algorithm configuration
techniques to construct a portfolio of eight complementary algorithms to be run
in parallel, aiming to achieve good performance on instances that arose in
proprietary auction simulations. To evaluate the impact of our solver in this
paper, we built an open-source reverse auction simulator. We found that within
the short time budget required in practice, SATFC solved more than 95% of the
problems it encountered. Furthermore, the incentive auction paired with SATFC
produced nearly optimal allocations in a restricted setting and substantially
outperformed other alternatives at national scale.
