Deep optimization for spectrum repacking
Deep optimization for spectrum repacking
复制标题
频谱重新打包的深度优化
DOI：
10.1145/3107548
复制
发表时间：
2017
影响因子：
22.7
通讯作者：
Kevin Leyton
中科院分区：
文献类型：
--
作者：
N. Newman;A. Fréchette;Kevin Leyton
在2016- 17年的13个月里，美国联邦通信委员会进行了一次“激励拍卖”，将无线电频谱从广播电视重新用于无线互联网。最终，拍卖产生了198亿美元，其中100.5亿美元支付给了175家广播公司，以自愿放弃14个超高频（UHF）频道的许可证。继续广播的电台被分配了潜在的新频道，以尽可能密集地适应剩余的频道。在支付成本（包括调整）后，政府净收入超过70亿美元（用于偿还国债）。拍卖设计的一个关键要素是构造一个求解器，称为基于SAT的可行性分析（SATFC），它确定是否可以以这种方式“重新包装”一组站;每次给一个站报价时，它都需要运行。本文介绍了我们建立SATFC的过程。我们采用了一种我们称之为“深度优化”的方法，采用数据驱动、高度参数化和计算密集型的方法来设计求解器。更具体地说，为了构建SATFC，我们设计了一种软件，可以将完整的和本地搜索SAT编码的可行性检查与广泛的领域特定技术配对，例如约束图分解和新颖的缓存机制，这些机制允许重用相关的部分解决方案，解决问题。然后，我们使用自动算法配置技术来构建并行运行的8个互补算法的组合，旨在在专有拍卖模拟中出现的实例上实现良好的性能。为了评估本文中我们的求解器的影响，我们构建了一个开源的反向拍卖模拟器。我们发现，在实践所需的短时间内，SATFC解决了95%以上的问题。此外，激励拍卖与SATFC配对产生了几乎最优的配置在一个限制的设置，并大大优于其他替代品在全国范围内。
Over 13 months in 2016--17 the U.S. Federal Communications Commission conducted an "incentive auction" to repurpose radio spectrum from broadcast television to wireless internet. In the end, the auction yielded $19.8 bn, $10.05 bn of which was paid to 175 broadcasters for voluntarily relinquishing their licenses across 14 Ultra High Frequency (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 bn (used to pay down the national debt) after covering costs (including retuning). A crucial element of the auction design was the construction of a solver, dubbed SAT-based Feasibility Checker (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, such as constraint graph decomposition and novel caching mechanisms that allow for reuse of partial solutions from related, solved problems. We then used automatic algorithm configuration techniques to construct a portfolio of 8 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.