Solving the Station Repacking Problem
Abstract
We investigate the problem of repacking stations in the FCC's upcoming, multi-billion-dollar "incentive auction". Early efforts to solve this problem considered mixed-integer programming formulations, which we show are unable to reliably solve realistic, national-scale problem instances. We describe the result of a multi-year investigation of alternatives: a solver, SATFC, that has been adopted by the FCC for use in the incentive auction. SATFC is based on a SAT encoding paired with a wide range of techniques: constraint graph decomposition; novel caching mechanisms that allow for reuse of partial solutions from related, solved problems; algorithm configuration; algorithm portfolios; and the marriage of local-search and complete solver strategies. We show that our approach solves virtually all of a set of problems derived from auction simulations within the short time budget required in practice.
Cite
Text
Fréchette et al. "Solving the Station Repacking Problem." AAAI Conference on Artificial Intelligence, 2016. doi:10.1609/AAAI.V30I1.10077Markdown
[Fréchette et al. "Solving the Station Repacking Problem." AAAI Conference on Artificial Intelligence, 2016.](https://mlanthology.org/aaai/2016/frechette2016aaai-solving/) doi:10.1609/AAAI.V30I1.10077BibTeX
@inproceedings{frechette2016aaai-solving,
title = {{Solving the Station Repacking Problem}},
author = {Fréchette, Alexandre and Newman, Neil and Leyton-Brown, Kevin},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2016},
pages = {702-709},
doi = {10.1609/AAAI.V30I1.10077},
url = {https://mlanthology.org/aaai/2016/frechette2016aaai-solving/}
}