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.