{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,28]],"date-time":"2026-09-28T22:51:55Z","timestamp":1790635915741,"version":"4.1.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,12,27]],"date-time":"2017-12-27T00:00:00Z","timestamp":1514332800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["Discovery Grant"],"award-info":[{"award-number":["Discovery Grant"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Auctionomics, Inc."}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2017,12,27]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/3107548","type":"journal-article","created":{"date-parts":[[2017,12,27]],"date-time":"2017-12-27T18:50:34Z","timestamp":1514400634000},"page":"97-104","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Deep optimization for spectrum repacking"],"prefix":"10.1145","volume":"61","author":[{"given":"Neil","family":"Newman","sequence":"first","affiliation":[{"name":"University of British Columbia, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexandre","family":"Fr\u00e9chette","sequence":"additional","affiliation":[{"name":"University of British Columbia, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kevin","family":"Leyton-Brown","sequence":"additional","affiliation":[{"name":"University of British Columbia, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,12,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-007-0178-0"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1788994.1789011"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.02.001"},{"key":"e_1_2_1_4_1","unstructured":"Cramton P. Lopez H. Malec D. Sujarittanonta P. Design of the reverse auction in the broadcast incentive auction. Working Paper (2015) http:\/\/www.cramton.umd.edu\/papers2015-2019\/cramton-reverse-auction-design-fcc-comment-pn.pdf 2015.  Cramton P. Lopez H. Malec D. Sujarittanonta P. Design of the reverse auction in the broadcast incentive auction. Working Paper (2015) http:\/\/www.cramton.umd.edu\/papers2015-2019\/cramton-reverse-auction-design-fcc-comment-pn.pdf 2015."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1770849.1770864"},{"key":"e_1_2_1_6_1","volume-title":"National Bureau of Economic Research","author":"Doraszelski U.","year":"2017"},{"key":"e_1_2_1_7_1","unstructured":"FCC. Office of engineering and technology releases and seeks comment on updated OET-69 software. FCC Public Notice DA 13--138 February 2013.  FCC. Office of engineering and technology releases and seeks comment on updated OET-69 software. FCC Public Notice DA 13--138 February 2013."},{"key":"e_1_2_1_8_1","first-page":"1","article-title":"related to incentive auction repacking feasibility checker. FCC Public Notice","author":"Information","year":"2014","journal-title":"DA 14--3"},{"key":"e_1_2_1_9_1","unstructured":"FCC. Repacking constraint files (2015). http:\/\/data.fcc.gov\/download\/incentive-auctions\/Constraint_Files\/ 2015. Accessed 2015--11--20.  FCC. Repacking constraint files (2015). http:\/\/data.fcc.gov\/download\/incentive-auctions\/Constraint_Files\/ 2015. Accessed 2015--11--20."},{"key":"e_1_2_1_10_1","unstructured":"FCC. Reverse auction opening prices (2015). http:\/\/wireless.fcc.gov\/auctions\/incentive-auctions\/Reverse_Auction_Opening_Prices_111215.xlsx 2015. Accessed 2015--11--15.  FCC. Reverse auction opening prices (2015). http:\/\/wireless.fcc.gov\/auctions\/incentive-auctions\/Reverse_Auction_Opening_Prices_111215.xlsx 2015. Accessed 2015--11--15."},{"key":"e_1_2_1_11_1","volume-title":"AAAI Conference on Artificial Intelligence 8 (2016","author":"Fr\u00e9chette A.","year":"2016"},{"key":"e_1_2_1_12_1","volume-title":"Logic Programming and Nonmonotonic Reasoning","author":"Gebser M.","year":"2007"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00081-3"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2076450.2076469"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25566-3_40"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1734953.1734959"},{"key":"e_1_2_1_17_1","volume-title":"Department of Computer Science","author":"Hutter F.","year":"2014"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09584-4_4"},{"key":"e_1_2_1_19_1","first-page":"1","article-title":"The international SAT solver competitions","volume":"33","author":"J\u00e4rvisalo M.","year":"2012","journal-title":"Artificial Intelligence Magazine"},{"key":"e_1_2_1_20_1","volume-title":"European Conference on Artificial Intelligence (ECAI)","author":"Kadioglu S.","year":"2010"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Kearns M. Dworkin L. A computational study of feasible repackings in the FCC incentive auctions. CoRR abs\/1406.4837 2014.  Kearns M. Dworkin L. A computational study of feasible repackings in the FCC incentive auctions. CoRR abs\/1406.4837 2014.","DOI":"10.2139\/ssrn.2456395"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2015.11.002"},{"key":"e_1_2_1_23_1","unstructured":"Knutson R. Gryta T. Verizon AT&T may face bidding limits in spectrum auction. Wall Street Journal (Apr. 2014). http:\/\/www.wsj.com\/articles\/SB10001424052702304626304579510154106120342. Accessed 2016--12--12.  Knutson R. Gryta T. Verizon AT&T may face bidding limits in spectrum auction. Wall Street Journal (Apr. 2014). http:\/\/www.wsj.com\/articles\/SB10001424052702304626304579510154106120342. Accessed 2016--12--12."},{"key":"e_1_2_1_24_1","unstructured":"Leyton-Brown K. The viability of exact feasibility checking. Talk at the Stanford Institute for Economic Policy Research Conference on the design of the U.S. Incentive Auction for reallocating spectrum between wireless telecommunications and television broadcasting February 2013.  Leyton-Brown K. The viability of exact feasibility checking. Talk at the Stanford Institute for Economic Policy Research Conference on the design of the U.S. Incentive Auction for reallocating spectrum between wireless telecommunications and television broadcasting February 2013."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Li S. Obviously strategy-proof mechanisms. Available at SSRN 2560028 2015.  Li S. Obviously strategy-proof mechanisms. Available at SSRN 2560028 2015.","DOI":"10.2139\/ssrn.2560028"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orp.2016.09.002"},{"key":"e_1_2_1_27_1","volume-title":"Churchill Lectures in Economics","author":"Milgrom P.","year":"2004"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602834"},{"key":"e_1_2_1_29_1","first-page":"43","article-title":"Synthesizing Scheduling Algorithms from High-Level Models, 47 (Springer","author":"Monette J.-N.","year":"2009","journal-title":"Boston"},{"key":"e_1_2_1_30_1","unstructured":"Newman N. Leyton-Brown K. Milgrom P. Segal I. Assessing economic outcomes in simulated reverse clock auctions for radio spectrum. Technical report abs\/1706.04324 (2017). http:\/\/arxiv.org\/abs\/1706.04324.  Newman N. Leyton-Brown K. Milgrom P. Segal I. Assessing economic outcomes in simulated reverse clock auctions for radio spectrum. Technical report abs\/1706.04324 (2017). http:\/\/arxiv.org\/abs\/1706.04324."},{"key":"e_1_2_1_31_1","volume-title":"International SAT Competition","author":"Nudelman E.","year":"2003"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0269888901000029"},{"key":"e_1_2_1_33_1","volume-title":"AAAI Conference on Artificial Intelligence","author":"Xu L.","year":"2010"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622673.1622687"},{"key":"e_1_2_1_35_1","unstructured":"Zhang C. Bengio S. Hardt M. Recht B. Vinyals O. Understanding deep learning requires rethinking generalization. CoRR abs\/1611.03530 2016.  Zhang C. Bengio S. Hardt M. Recht B. Vinyals O. Understanding deep learning requires rethinking generalization. CoRR abs\/1611.03530 2016."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3107548","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3107548","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:25Z","timestamp":1750217425000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3107548"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,27]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,12,27]]}},"alternative-id":["10.1145\/3107548"],"URL":"https:\/\/doi.org\/10.1145\/3107548","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,27]]},"assertion":[{"value":"2017-12-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}