PUBLIC NOTICE
Federal Communications Commission
445 12
th
St., S.W.
Washington, D.C. 20554
News Media Information 202 / 418-0500
Internet: http://www.fcc.gov
TTY: 1-888-835-5322
DA 14-3
Released: January 9, 2014
INCENTIVE AUCTION TASK FORCE RELEASES INFORMATION RELATED TO REPACKING;
ANNOUNCES WORKSHOP/WEBINAR TO PROVIDE ADDITIONAL DETAIL
GN Docket No. 12-268
1. As stated in the Notice of Proposed Rulemaking, the incentive auction will have three major
pieces: a reverse auction, a forward auction, and a reorganization or “repacking” of the broadcast television bands,
which is likely to include the reassignment of some television stations to new channels.
1
This Public Notice is
relevant to the repacking component of the incentive auction. We are releasing the information described here
and in the attached Technical Appendix in the interest of transparency and to give interested parties the
opportunity to provide input regarding aspects of the repacking process. We believe our action today is another
important step in the process of designing a successful incentive auction.
2
2. In July, we released updated TVStudy software and data representing the results of a staff analysis
of whether a television station could be assigned to particular channels in the repacking process, consistent with
statutory and other requirements, based on certain preliminary assumptions.
3
That information represented the
results of a staff analysis of whether a television station could be assigned to particular channels in the incentive
auction repacking process. Specifically, the information could be used in a reverse auction “to check the
feasibility of assigning channels to a given set of stations without violating any statutory or other constraints.
That is, the data could be used to determine whether channels could be assigned to all broadcasters remaining on
the air in a manner consistent with the applicable constraints i f a given set of reverse auction bids from
broadcasters were to be accepted. Such a ‘feasibility check’ could be conducted rapidly during the course of
bidding in the reverse auction because it would only require determining whether a channel assignment is feasible
for a set of stations, not that it represents the optimal channel assignment.”
4
In this Public Notice and the attached
Technical Appendix, we describe how a feasibility check could be performed.
1
Expanding the Economic and Innovation Opportunities of Spectrum Through Incentive Auctions, GN Docket No. 12-268,
Notice of Proposed Rulemaking, 27 FCC Rcd 12357, 12359, para. 5 (2012) (NPRM).
2
See Incentive Auction Task Force Releases Information Related to Incentive Auction Repacking, GN Docket No. 12-268,
ET Docket No. 13-26, Public Notice, 28 FCC Rcd 10370 (WTB 2013) (First Repacking PN).
3
See id.
4
Id. at 10371.
3. Optimization analysis is time-consuming; conducting it during the course of bidding in the
reverse auction would restrict the Commission’s auction design options.
5
The same data also could be used to
optimize channel assignments after the bidding is completed, however, without slowing down the bidding
process. Such optimization analysis could consider, in addition to the applicable constraints, additional factors
such as minimizing the number of channel changes and minimizing the estimated costs of repacking. Also, if the
Commission chooses to use a sealed-bid auction design, then optimization could be used to determine which bids
to accept in order to obtain a given amount of spectrum at minimum cost.
4. The full Commission will make final decisions regarding the repacking process and other
elements of the incentive auction; the Commission has made no final decision on the matters we address here.
This Public Notice and the attached Technical Appendix relate to the technical aspects of repacking and auction
design, and are responsive to those commenters who have requested the opportunity for comment on such details.
We emphasize that to participate in the reverse or forward auctions, bidders need not know or master the technical
details discussed herein or in the attached Technical Appendix. The Commission has announced the principle that
incentive auction participation, particularly for broadcasters, should be as simple as possible.
6
5. While at this time the Incentive Auction Task Force is not releasing any computer code, we are
releasing methodological information about multiple ways in which feasibility checks could be performed.
Interested parties can use the information contained in this Public Notice and the attached Technical Appendix,
together with the information and analysis we released with the First Repacking PN, to develop and conduct their
own repacking feasibility checks and to evaluate the approaches described in the technical appendix.
7
We invite
interested parties to provide input and comment on the information contained herein.
6. The repacking and reverse auction components of the incentive auction are interdependent. The
selection of winning reverse auction bids will depend on the Commission’s ability to determine whether, if a
given set of reverse auction bids from broadcasters were to be accepted, channels could be assigned to all
broadcasters remaining on the air in a manner consistent with the applicable constraints. If the Commission
ultimately decides to use a descending clock auction, it would be necessary to perform numerous feasibility
checks prior to each round of bidding. Speed, therefore, would be important: the analysis would have to be fast
enough to not unduly slow down the bidding process. In addition to speed, certainty also would be vital because
the Commission would need to pack all the stations that choose to remain on the air at the close of the auction.
7. For purposes of the incentive auction, a feasibility checker is a computer program that checks for
the existence of a feasible assignment of a set of television stations, consistent with applicable constraints. The
inputs required for a feasibility checker include:
1. A list of channels available for assignment in a TV band (e.g. channels 14 through 30 in the UHF band
in order to clear channels 31 through 51);
2. A set of stations to be assigned a channel;
3. A set of allowable channels for each station; and
5
Given that the Commission has not yet decided on an auction design, it is possible that the Commission will pick a design
that would allow for the use of optimization analysis during the auction.
6
See NPRM, 27 FCC Rcd at 12361-62, para. 10.
7
Many approaches to feasibility checking use open source software commonly used for complex problem solving. Interested
parties will be able to examine these software packages and use them to build their own feasibility checking tools.
4. A list of stations that cannot be simultaneously assigned to the same channel or adjacent channels for
each station.
8. The third and fourth required data inputs were provided in the First Repacking PN. Specifically,
the domain.csv file identifies the channel numbers that a given station could be assigned taking into account fixed
constraints.
8
The interference_paired.csv file identifies station pairs that cannot be simultaneously assigned to the
same channel or adjacent channels.
9
A feasible assignment is one that assures that each station is assigned a
channel within its domain possibilities that satisfies co- and adjacent-channel interference constraints and any
other requirements that may be established by the Commission.
9. The repacking feasibility checking process results in two possible outcomes: (i) a feasible channel
assignment for a set of stations, or (ii) a determination that no such feasible assignment exists. A number of
software packages are designed to either find such an assignment or determine that no such assignment is
possible. Because these algorithms are not guaranteed to terminate in a relatively short amount of time with a
definitive conclusion, a feasibility checker could be designed to result in a third possible outcome: a “time-out.”
A time-out instructs a feasibility checker to stop if the checker is unable to find a feasible assignment or to prove
infeasibility within a user-defined time limit. A time-out could be treated the same as a finding that no feasible
assignment exists.
10. We have been investigating various classes of mathematical software (“solvers”) capable of
determining whether or not a feasible assignment exists given the applicable constraints. We have focused our
investigation on two different types of solvers in particular: satisfiability solvers and integer optimization
solvers.
10
Each solver encodes the problem in a different manner, and uses alternative methods to solve the
problem. Preliminary investigations indicate that representative repacking problems can be solved efficiently
using one or both of these two approaches, such that either a feasible assignment or a declaration that no
assignment exists can be determined in less than two minutes of computation time, and often in considerably less
time. Thus, it appears that the use of feasibility checking would be compatible with a multiple round auction
format because it can compute answers quickly enough to allow multiple rounds of an auction to take place in a
reasonable amount of time.
11. The Incentive Auction Task Force intends to host a Workshop/Webinar in February to discuss the
approaches for feasibility checking using both satisfiability and integer optimization solvers, and the results of
initial testing. At that time, Task Force staff and its outside auction experts will also respond to questions and
comments about the various approaches detailed in this Public Notice and the attached Technical Appendix.
More information on the exact date and how to participate will be released prior to the Workshop/Webinar.
Details about the Workshop/Webinar will be released by Public Notice and on the LEARN website at:
http://www.fcc.gov/learn.
***
8
See First Repacking PN, 28 FCC Rcd at 10373.
9
Id. at 10374.
10
Although we have focused on these two types of solvers, we are continuing to investigate other approaches as well.
12. This Public Notice is being issued pursuant to sections 0.31, 0.51, 0.61, and 0.131 of the
Commission’s rules by the Office of Engineering and Technology and the International, Media, and Wireless
Telecommunications Bureaus, members of the Incentive Auction Task Force.
11
Comments may be filed using the
procedures for ex parte submissions in permit-but-disclose proceedings set forth in section 1.1206 of the
Commission’s rules.
12
When filing comments, please reference GN Docket No. 12-268. Information about
feasibility checking and other repacking data will be accessible via a link on the FCC’s LEARN website under the
Repacking Section, which can be found at http://fcc.gov/learn.
13. For further information, contact Jonathan McCormack at 202-418-1065, or via e-mail at
Jonathan.McCormack@fcc.gov.
11
47 CFR §§ 0.31, 0.51, 0.61, 0.131.
12
See 47 CFR § 1.1206(b)(2).
TECHNICAL APPENDIX
Solving Approaches for the Feasibility Checking Problem
I. INTRODUCTION
1. The Commission staff has been investigating the performance of two television station repacking
feasibility checking approaches, each using a different solving engine. The two types of solving engines we have
tested are satisfiability solvers and integer optimization solvers. Both solvers determine whether a channel
assignment for a list of stations is feasible given a set of restrictions on the assignment. They differ in the way the
problem is encoded and solved. In this Technical Appendix we present a brief discussion about these two solving
approaches, including for each type of solver the mathematical formulation of the feasibility problem used in our
testing.
II. SATISFIABILITY SOLVERS
2. Satisfiability solvers ask whether there exists a truth assignment to a set of Boolean variables
(variables evaluating to either true or false) that satisfies a given formula in propositional logic. (Satisfying a
formula means causing the whole formula to evaluate to true.) Without loss of generality, formulas in
propositional logic can be expressed in conjunctive normal form as follows:
? A (Boolean) variable is denoted xi,,j, and can take the value true or false.
? A literal is a possibly negated variable, denoted xi,,j or ¬xi,,j. The literal ¬xi,,j evaluates to true if xi,,j is false,
and to false otherwise.
? A clause is a disjunction of literals—that is, a list of literals connected by the OR operator, which is
denoted by the symbol ?. The clause (xi,,j ? xk,,l) evaluates to false if xi,,j and xk,,l are both false, and to true
otherwise.
? A formula is a conjunction of the whole set of clauses—that is, a list of all of the clauses, connected by
the AND operator, which is denoted by the symbol ?. If the set of clauses is {C1, C2, C3}, then the
formula is C1 ? C2 ? C3. Given a truth assignment to the variables, this formula evaluates to true if each
of C1, C2 and C3 evaluate to true, and to false otherwise.
3. The satisfiability problem asks whether there exists any truth assignment to the variables that
causes a formula to evaluate to true. This question can be difficult to answer because different clauses can contain
the same variables, in some cases negated and in some cases not. Values for these variables must be chosen
carefully so that each clause evaluates to true—e.g., a clause that contains only negated literals must contain at
least one that evaluates to false, and a clause that contains only positive literals must contain at least one that
evaluates to true.
4. The television station repacking feasibility checker can be encoded as a satisfiability problem as
follows: first, use the variable xs,c to represent the proposition that station s is assigned to channel c—that is, xs,c
will be true if station s is assigned to channel c and false otherwise—and hence create one such variable for every
station s and every channel c in the repacking band that is allowed in the domain.csv file. Then create the
following set of clauses:
? For every pair of channels c1 and c2 allowed for station s, create a clause (¬xs,c1 ? ¬xs,c2), expressing
the constraint that station s is allowed to broadcast on at most one of these channels.
? For every station s and set of allowable channels {c1, …, cn}, create a clause (xs,c1 ? … ? xs,cn)
expressing the constraint that station s must broadcast on (at least) one of its allowable channels.
? For every interference rule specified in the interference_paired.csv file, specifying that station s1
cannot broadcast on channel c1 while station s2 broadcasts on channel c2, create a clause to express
this constraint: (¬xs1,c1 ? ¬xs2,c2).
5. The conjunction of all of the clauses defined above defines a formula. A satisfiability solver can
then identify whether there exists a way of assigning truth values to the variables x that satisfies the formula.
III. INTEGER OPTIMIZATION SOLVERS
6. Integer optimization problems are concerned with the optimal allocation of limited resources
(assignment of values to decision variables) to meet a desired objective when some of these assignments are
restricted to discrete values. The objective function (goal) of the optimization problem must be a linear function.
A set of linear constraints that restrict the allowable assignment of values to each variable and bounds on each of
the variables further define the problem.
7. The following formulation can be used in examining whether channels can be assigned to
television stations within a specific band. Similar to the formulation used in the satisfiability solvers, define
binary variables xs,c to represent if station s is assigned to channel c, that is, xs,c will be equal to one (true) if station
s is assigned to channel c and zero (false) otherwise. For every station s to be repacked, create a variable for each
channel c listed in the domain.csv file for that station in the band.
Definition of indices:
S = the set of all stations to be assigned
= the domain set for station s?S, i.e. the set of allowable channels in the repacking band
Definition of variables:
, =
1 if station ? is assigned to channel ?
0 otherwise
The constraints:
? A constraint for each station that forces one of its allowable channels to be assigned to the station:
? ,? = 1,? ?
? For every pairwise restriction that precludes two stations from residing on the same channel, a
constraint is created that indicates at most one of the two stations (labeled here l ,m) can be
assigned to the that channel:
, + , ? 1
? Similarly, for every pairwise restriction that ensures that if station l is on channel c then station m
cannot be on channel c+1,
1
a constraint is added of the form:
, + , ? 1
8. In addition to a set of constraints that restrict the possible assignments, an optimization solver
also expects a linear objective function. Since the feasibility-checking problem only needs to know if an
assignment exists, the problem can use any linear cost vector, including the zero-vector as an objective function.
9. We note that the feasibility checker problem has a very special structure that allows us to further
strengthen the formulation and thereby solve such problems more efficiently. Specifically, it is possible to
combine many of the pairwise constraints into much stronger constraints known as “clique constraints.” A clique
is a set of variables that has the property that only one variable in this set can be set to 1 (or true). We find cliques
by creating a graph called the interference or constraint graph. This graph is formed by creating a node for each
possible station-channel assignment (i.e., each variable) and an edge for each of the pairwise interference
constraints, i.e. an edge is drawn between two nodes if the two assignments cannot occur simultaneously.
10. To find large cliques in the full graph we restrict our search to the subgraphs with fixed channel,
c. In essence, we identify stations such that only one of the stations in the set can be assigned to that channel. In
areas dense with channels, the resulting cliques tend to be relatively large and greatly aid in finding feasible
solutions. We therefore concentrate on the series of graphs where the c subscript is fixed. In such graphs, we find
cliques that specify for a given channel c, all of the stations that cannot simultaneously be on that channel in a
given region. The general form is:
,
?
? 1
where Sk is the set of stations which cannot share channel c. The number of unique clique constraints that can be
generated for this problem is extremely large. Only a subset of these constraints is added to the problem at the
onset.
11. Additionally, we add another set of clique constraints that consider both co-channel and adjacent
channel interferences. All such constraints are of the form:
,
?
+ ,
?
? 1,
where Sk+ and Sk- are two co-channel cliques in which every station in Sk+ cannot have any station in Sk- assigned
to its adjacent channel below.
12. The use of these clique constraints significantly reduces the number of constraints on the problem
because we remove any of the pairwise constraints that are subsumed in any of the generated cliques. These
constraints are used to strengthen the formulation and thereby improve the speed at which the linear programming
solver finds a feasible solution or proves that none exist.
1
Explicit constraints for adjacent channels below (i.e. c-1) are redundant, as they will be covered when generating all the
constraints for adjacent channels above. For example if station A is on channel 3 and station B cannot simultaneously be on
channel 2, that constraint would be covered when considering that if station B is on channel 2, station A cannot be on channel
3.