## Information Related to Incentive Auction Repacking Feasibility Checker

**PUBLIC NOTICE**

**Federal Communications Commission445 12th St., S.W.**

**News Media Information 202 / 418-0500**

**Internet: http://www.fcc.gov**

**Washington, D.C. 20554**

**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**

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 chan nels.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 if 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**

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**

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**

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.

Note: We are currently transitioning our documents into web compatible formats for easier reading. We have done our best to supply this content to you in a presentable form, but there may be some formatting issues while we improve the technology. The original version of the document is available as a PDF, Word Document, or as plain text.