JANUARY 2018 | VOL. 61 | NO. 1 | COMMUNICATIONS OF THE ACM 101
this space to building a customized solver. Identifying a set of
parameters that optimize a given algorithm’s performance
on a given dataset is called algorithm configuration. There
exist a wide variety of algorithm configuration tools. 2, 15, 16, 26 We
used Sequential Model-based Algorithm Configuration
(SMAC), 15 the publicly available method that arguably
achieves the best performance (see e.g., Hutter et al. 17). SMAC
uses the “Bayesian optimization” approach of interleaving
random sampling and the exploration of algorithm designs
that appear promising based on a learned model.
Unfortunately, even after performing algorithm configuration, it is rare to find a single algorithm that outperforms all
others on instances of an NP-complete problem such as SAT.
This inherent variability across solvers can be exploited by
algorithm portfolios. 13, 31, 34 Most straightforwardly, one selects
a small set of algorithms with complementary performance
on problems of interest and, when asked to solve a new
instance, executes them in parallel. Of course, we wanted to
construct such algorithm portfolios automatically as part of
our deep optimization approach. We did this by using a
method called Hydra33 which runs iteratively, at each step
directing the algorithm configurator to optimize marginal
gains over the given portfolio. This allows Hydra to find
algorithms that may perform poorly overall but that complement the existing portfolio. Overall, we ran Hydra for eight
steps, thereby producing a portfolio of novel solvers (dubbed
SATFC) that could run on a standard 8-core workstation. The
Incentive Auction used SATFC 2. 3. 1, which is available online
at https://github.com/FCC/SATFC.
4. DATA FROM AUCTION SIMULATIONS
During the development of SATFC the FCC shared with us a
wide range of anonymized problem instances that arose in
auction simulations they performed in order to validate the
auction design. These formed the “training set” we used in
the deep optimization process when constructing SATFC
2. 3. 1. These simulations explored a very narrow set of
answers to the questions of which stations would participate
and how bidders would interact with the auction mechanism; they do not represent a statement either by us or by the
FCC about how these questions were resolved in the real auction (indeed, by law the answers will not be revealed to us or
to the public for two years). It is of course impossible to guarantee that variations in the assumptions would not have
yielded computationally different problems.
While SATFC 2. 3. 1 is itself open-source software, it is
unfortunately impossible for us to share the data that was
used to build it. In this paper, we have opted for what we
hope is the next best thing: evaluating SATFC 2. 3. 1 and various alternatives using a publicly available test set. We thus
wrote our own reverse auction simulator and released it as
open source software (see http://cs.ubc.ca/labs/beta/Projects/
SATFC). We used this simulator to simulate 20 auctions, in
each case randomly sampling bidder valuations from a publicly available model6 using parameters obtained directly
from its authors. This model specifies stations’ values for
broadcasting in UHF, vs,uhf. Of course, a station has no value
for going off air: vs,off = 0. In some cases the reverse auction can
reassign a UHF station to a channel in 1 of 2 less valuable VHF
simplify the interference graph by removing edges and nodes
respectively. This can shrink the size of the component containing s+ and make this technique even more effective.
Containment caching. Finally, we know that every repacking
problem will be derived from a restriction of the interference
graph to some subset of S. We know this graph in advance of
the auction; this suggests the possibility of doing offline work
to precompute solutions. However, our graph has 2 990
nodes, and the number of restricted graphs is thus 22990 ≈
10900. Thus, it is not possible to consider all of them offline.
Not every restricted problem is equally likely to arise in
practice. To target likely problems, we could simply run a
large number of simulations and cache the solution to every
repacking problem encountered. Unfortunately, we found
that it was extremely rare for problems to repeat across sufficiently different simulator inputs, even after running hundreds of simulations (generating millions of instances and
costing years of CPU time). However, we can do better than
simply looking for previous solutions to a given repacking
problem. If we know that S is repackable then we know the
same is true for every S′ ⊆ S (and indeed, we know the packing itself—the packing for S restricted to the stations in S′).
Similarly, if we know that S was not packable then we know
the same for every S′ ⊇ S. This observation dramatically magnifies the usefulness of each cached entry S, because each S
can be used to answer queries about an exponential number
of subsets or supersets. This is especially useful because
sometimes it can be harder to find a repacking for subsets of
S than it can be to find a repacking for S.
We call a cache meant to be used in this way a containment
cache, because it is queried to determine whether one set
contains another (i.e., whether the query contains the cache
item or vice versa). To the best of our knowledge, containment caching is a novel idea. A likely reason why this scheme
is not already common is that querying a containment cache
is nontrivial: one cannot simply index entries with a hash
function; instead, an exponential number of keys can match
a given query. We were nevertheless able to construct an algorithm that solved this problem quickly in our setting. We
observe that containment caching is applicable to any family
of feasibility testing problems generated as subsets of a master set of constraints, not just to spectrum repacking.
In more detail, we maintain two caches, a feasible cache
and an infeasible cache, and store each problem we solve in
the appropriate cache. We leverage the methods from
Section 3. 1 to enhance the efficiency of our cache, storing
full instances for SAT problems and the smallest simplified component for UNSAT problems. When asked
whether it is possible to repack station set S, we first check
whether a subset of S belongs to the infeasible cache (in
which case the original problem is infeasible); if we find
no matches, we decompose the problem into its smallest
simplified component and check if the feasible cache contains a superset of those stations, in which case the original problem is feasible.
3. 2. Searching the design space
Overall, our design space had 191 parameters, nested as
much as four levels deep. We now describe how we searched