Federal Communications Commission Appendix A Reconfiguration Technical Guide 1 Introduction This document details the procedures the Commission will employ to determine the Commission’s proposed reconfiguration (Option 1 in the Initial Commitment System) and the constraints an incumbent must satisfy for an acceptable alternative reconfiguration (Option 2 in the Initial Commitment System) and supplements the descriptions of those processes in the Initial 39 GHz Reconfiguration Public Notice. See generally, Notice of Initial 39 GHz Reconfiguration Procedures et al., GN Docket No. 14-177, AU Docket No. 19-59, Public Notice, DA 19-196 (WTB/OEA Mar. 20, 2019) (Initial 39 GHz Reconfiguration Procedures Public Notice). If an incumbent selects either Option 1 or Option 2 in the Initial Commitment System, it ultimately will receive modified licenses that reflect these reconfiguration processes. There are three main steps to the process: 1. For each incumbent with 39 GHz licenses, identify the PEA or PEAs where it currently has holdings and determine the total holdings within each PEA. (Section 2) 2. For each incumbent, determine the reconfiguration whereby the FCC combines an incumbent’s partial block holdings into full 100 megahertz PEA spectrum blocks and at most one partial PEA block. (Section 3) 3. For each incumbent that chooses to retain a single partial PEA block, determine the geographic area within the PEA that will constitute the geographic boundaries of the partial PEA block that will result in a modified license. (Section 4) 2 Determining Existing Holdings for Each Licensee in Each PEA We will determine an incumbent’s holdings by identifying how many two-kilometer by two-kilometer (2x2 km) grid cells are contained within an existing license. In particular, we describe below the process we will use for creating the 2x2 km uniform grid, for calculating each grid cell’s associated population-weighted internal point, and for associating a grid cell with a license. This process is based upon the methodology used by the Commission’s TVStudy software to measure station-to-station and Inter-service Interference (ISIX) during the broadcast incentive auction See Use of Spectrum Bands Above 24 GHz for Mobile Radio Services, Fourth Report and Order, FCC 18-180, at 9, para. 21 (Dec. 12, 2018). with certain adjustments. While the TVStudy software calculated a global 2x2 km grid, in order to minimize areal distortion as the algorithm moves away from the equator, the TVStudy algorithm varied the width of each cell across bands of latitude. TVStudy FAQ, Federal Communications Commission, www.fcc.gov/electromagnetic-compatibility-division/tvstudy-interference-analysis-software/tvstudy-faq#Q12 (last updated Mar. 28, 2017). As a result, that software does not necessarily result in consistently sized and shaped grid cells. In contrast, the process detailed below first generates a uniform grid with 2x2 km cells for each contiguous part of the United States using locally-appropriate equal area map projections. Since the reconfiguration methodology analyzes the MHz-pops of each license on a per-PEA basis, the appropriate 2x2 km uniform grid is then overlaid on the GIS boundary data of each PEA. For each grid cell in the PEA, a single population-weighted “internal point” (i.e., a point that falls within the grid cell geometry) is calculated from the U.S. Census Bureau’s 2010 data using the same methodology employed by the TVStudy software. GIS boundary data including the 2x2 km uniform grids, and the population-weighted internal points for all grid cells, are available in ESRI-standard Shapefile format on the Auction 103 website, available at www.fcc.gov/auction/103. Creating the 2x2 km Uniform Grid For each contiguous area of the United States (comprised of one or more PEAs), a uniform grid with cells of equal area (2x2 km) is generated, resulting in separate grids for the continental United States, Alaska, Hawaii, American Samoa, and Guam and the Northern Mariana Islands. Each grid is defined using an “equal area” map projection so that the area contained within a single grid cell remains consistent regardless of the location of the grid cell. Each grid has been created by overlaying a 2 km x 2 km “fishnet” across the extent of the respective PEA boundary or set of boundaries, with an origin starting in the bottom-left corner of each overlay. This methodology generates each separate grid using an appropriate Albers equal area conic map projection. With equal area projections, cells may appear to have a non-uniform shape when viewed using a different map projection, depending on the grid cell’s location on the earth. All map projections introduce distortions in area, shape, scale, or direction that are inherent when transforming a three-dimensional spherical object to a two-dimensional cartesian representation. An equal area projection is one that minimizes distortion to area across a given geography at the expense of greater distortion in shape, scale, or direction. See John P. Snyder, Map Projections—A Working Manual, U.S. Geological Survey 3-7 (1987), available at https://pubs.usgs.gov/pp/1395/report.pdf. The boundaries of each PEA are then overlaid with the appropriate uniform grid to establish the set of 2x2 km grid cells contained within the PEA. In the case where a 2x2 km grid cell is intersected with the boundary of more than one PEA, this process results in a partial grid cell associated with each intersecting PEA. Calculating the Internal Point for each 2x2 km Grid Cell Using population data for each census block from the 2010 U.S. Census dataset, See Staff Block Estimates, Federal Communications Commission, www.fcc.gov/reports-research/data/staff-block-estimates (last updated Dec. 18, 2018). the “internal point” for each census block (a “census point”) is overlaid with the uniform grid intersected with the PEA boundaries calculated above. The U.S. Census Bureau defines an internal point (i.e., latitude and longitude coordinates) for each geographic entity that is generally at or near the geographic center of the entity. For certain irregularly shaped entities where the geographic center would be outside the boundaries of the entity, the internal point is calculated as the point inside of the entity nearest to the geographic center and on land, where possible. See 2010 Geographic Terms and Concepts - Geographic Area Attributes, U.S. Census Bureau, www.census.gov/geo/reference/gtc/gtc_area_attr.html (last updated Dec. 6, 2012). The algorithm calculates from these points a single “population-weighted” internal point for each grid cell within a PEA, which is considered to represent the entire population associated with that grid cell. For grid cells in which no census points fall, an internal point with zero population is calculated at the grid cell’s geometric center (“centroid”), or, if the centroid falls outside of the grid cell, the nearest point to the centroid that falls within the geometry. For grid cells in which a single census point falls, that point becomes the “population-weighted” internal point for the grid cell. For grid cells in which more than one census point falls, a population-weighted average internal point is calculated. Specifically, for each census point, the algorithm multiplies the population associated with that point by its latitude and separately by its longitude. Next, the algorithm sums the population-weighted latitude (and population-weighted longitude) values across all census points that fall within the grid cell. The summed population-weighted latitude (and population-weighted longitude) is then divided by the sum of the population of all census points within the grid cell. The point located at the resulting latitude and longitude (or, if the calculated point falls outside of the grid cell’s geometry, the nearest point that falls within the geometry) is thus considered to represent the population-weighted internal point for that grid cell. Determining an incumbent’s existing holdings We determine holdings based on existing licenses as follows. We first create GIS boundary data for each license, using the PEA license data and the four corners of the RSA license data found in the Universal Licensing System. A specific grid cell is associated with a license if the boundary for the license contains the internal point of that grid cell. For each of the incumbent’s licenses, we sum the population of all grid cells associated with the license within a given PEA to determine the incumbent’s population coverage for that license in that PEA. To obtain an incumbent’s total covered MHz-pops within a PEA, we sum over the incumbent’s licenses in the PEA, the population coverage of each license multiplied by 50 MHz, the bandwidth allocated to each existing license. To obtain the number of spectrum blocks corresponding to the new band plan, we divide the MHz-pops of the incumbent by the population of that PEA*100. If this results in a fractional component that is at least 0.99, i.e. coverage of full blocks plus at least 99% of the fractional block, then the number of blocks is rounded up to whole blocks. 3 Determining a Reconfiguration for Each Incumbent by Combining Its Partial Holdings into Full Peas and at Most One Partial PEA The licenses of each incumbent are reconfigured through mathematical optimization so that, after the licenses are modified based on the reconfiguration, the incumbent will have full 100 megahertz PEA licenses and at most one partial license. The total weighted MHz-pops for this configuration will be at least as great as that of the original holdings. This optimization is performed for each incumbent separately. As input to the optimization, we first determine the PEAs for which an incumbent has partial holdings. This is calculated by summing the total weighted MHz-pops in the PEA that an incumbent holds. Each incumbent’s MHz-pops will be weighted as described in the Initial 39 GHz Reconfiguration Procedures Public Notice and Appendix C: Imputing Auction 101 Prices for Weights. If this amount divided by the total weighted MHz-pops in the PEA is fractional, we put this license into the set of “partial license holdings” for this incumbent. We label the set of PEAs for which the incumbent has partial holdings as S. The goal of the reconfiguration process is to minimize the value of the remaining white space in the partial PEA block. If the reconfiguration process creates only whole blocks, the value of the remaining white space will be zero. Thus, the primary optimization is to choose a reconfiguration that results in the incumbent having only full licenses. It does this by first determining if there is a reconfiguration where the only partial holding has at least 90% of the total weighted MHz-pops, so that after rounding up, the partial holding would become a full license. Initial 39 GHz Reconfiguration Procedures Public Notice at paras. 41-42 If this is possible, the next optimization chooses among all such configurations, the partial PEA where the rounding affects the fewest unassigned weighted MHz-pops. If there are ties among such configurations, the optimization chooses the PEA where the rounding affects the least population. Thereafter, tie-breaking will choose the PEA randomly among all tied PEA solutions. If there is no configuration which results in the incumbent having all full licenses, then the optimization chooses a reconfiguration such that the PEA in which the incumbent has its one partial holding will have minimum weighted MHz-pops of whitespace. If there is a tie, one chooses the partial holding where the population of the whitespace is minimal. Tie-breaking after these two optimizations will choose the PEA randomly among all tied PEA solutions. Allocation optimization model for incumbent that owns partial licenses DATA: Mi is a scalar, the weighted MHz-pops of PEA i. S is the set of all partial holdings for the incumbent. T is a scalar the total weighted MHz-pops of all partial licenses of the incumbent VARIABLES: xi is a non-negative variable which is the weighted MHz-pops the licensee is assigned in PEA area i. fi is a binary variable, it has value 1 if PEA area i is chosen as the only allowable partial license assignment, and zero otherwise. yi is a non-negative variable which is the resulting white space in PEA i in weighted MHz- pops when the PEA is not completely cleared for sale. When fi is zero, then yi is set to zero. gi is a binary variable, it has value 1 if PEA area i is chosen as the only allowable partial license assignment and the partial license results in over 90% holdings for the PEA, and zero otherwise. zi is a binary variable, equal to 1 if PEA area i is assigned completely (i.e. 100 MHz license) to licensee, and zero otherwise. wi is a non-negative variable that measures the white space in the only PEA where there are partial holdings. WS is the resulting white space (in terms of weighted MHz-pops) of the PEA in which the incumbent has a partial holding Mixed Integer Programing Formulation Minimize the white space in the one partial holding (NOTE: white space will be zero in this optimization if the PEA chosen will have a partial holding of at least 90%): WS= mini∈Swi Subject to: At most one PEA can have a partial holding: i∈Sfi≤1 (1) Assignment plus white space equals weighted MHz-pops of the PEA: xi+yi=Mi, ∀i∈S (2) When zi=0, then xi≤Mifi, that is, this PEA area is either assigned partially or not at all. (Looking at it another way: when zi=0, fi≥xiMi implying that either xi=0 in which case fi is allowed to be zero, or xi>0, in which case fi=1): xi≤Mi zi+fi, ∀i∈S (3) If zi=1, then yi=0 (there is no white space): yi≤Mi 1-zi, ∀i∈S (4) If zi=1, then xi must equal Mi: xi≥Mizi, ∀i∈S (5) Total holdings of the licensee must equal T in any assignment: i∈Sxi=T (6) If the partial holdings are greater than 90% of the PEA, the licensee is assigned the whole license (gi=1); If not, gi=0, and the optimization chooses the PEA with smallest white-space wi: xi≥0.9Migi ∀i∈S (7a) xi≤Mi-0.1Mi(1-gi) ∀i∈S (7b) If fi=0, set wi=0 because the licensee is not assigned a partial license in the PEA and therefore there is no white space. If fi=1, then wi≥yi. If gi=1, wi is allowed to be zero and a second optimization will need to determine which PEA is chosen among all reconfigurations where the partial holding is at least 90%: wi≤Mifi ∀i∈S (8a) wi≥yi-Mi1-fi+gi ∀i∈S (8b) Variables zi and fi are binary and variables xi, yi, and wi are continuous variables: zi∈0,1, ∀i∈S (9) fi∈0,1, ∀i∈S (10) gi∈0,1, ∀i∈S (11) xi≥0, ∀i∈S (12) yi≥0, ∀i∈S (13) wi≥0, ∀i∈S (14) Tie-Breaking Optimization when the first optimization finds a reconfiguration that provides the incumbent with all full (no partial) licenses: DATA and VARIABLES are the same as specified above. The objective function remains the same; All constraints remain the same except that (7b) is removed, as is the g vector, and constraints (7a) and (8a) and (8b) are changed as follows: Only consider reconfigurations that have at least 90% holding in the partial license xi≥0.9fi ∀i∈S (7a) Measure the white space of this partial holding. wi≤Mifi ∀i∈S (8a) wi≥yi-Mi1-fi ∀i∈S (8b) Tie-Breaking Optimization once the minimum white space has been determined: DATA and VARIABLES are same as specified above with the following additional data: Let wghti equal the weight factor used to determine Mi Then, we determine the population Pi within the white-space of a PEA whose total white space is equal to the solution obtained in the first optimization, by dividing WS by both 100 and the PEA’s weight factor wghti. Thus: Pi=WSwghti*100 The new objective is: Find the PEA that has the smallest population over all tied solutions: Min i∈SPifi All constraints remain the same as the previous optimization with the addition of the following constraint to limit the white space in the PEA with the partial license to be the value found in the previous optimization: i∈Swi=WS 4 Determining the Geography of Retained Partial PEA Licenses The geographic boundaries of a partial PEA block will be determined by adjusting the incumbent’s currently licensed area in the PEA. Although an incumbent may provide an acceptable alternative reconfiguration, the incumbent cannot specify the geographic boundaries of the partial PEA block. In all cases, the Commission will determine the geographic boundaries of the partial PEA block. When the Geographic Footprint of an Incumbent’s Current Holdings Needs to be Increased Define each grid cell of the PEA in terms of an i and a j coordinate (where i represents the grid cell’s position in the row numbered from left to right and the j represents the grid cell’s position in the column numbered from top to bottom). Let T be the total weighted MHz-pops that the incumbent must have after the reconfiguration Let C be the partial holding of the incumbent in this PEA in terms of weighted MHz-pops before increasing its footprint. The process of increasing the incumbent’s geographic area begins by creating a list of the grid cells that surround the boundary of the incumbent’s current holdings in the partial PEA, i.e. all grid cells that share a side border with the grid cells in the partial holdings C but are not contained in C. Denote this new set of cells, B. If including all cells in B as part of the incumbent’s holdings results in holdings that are less than or equal to T, then each of these cells is added to C, i.e. C = C È B. We again look at the grid cells that are adjacent to this augmented set C, and put them in set B and again check if including all of these cells will result in holdings that are less than or equal to T. The process continues until when examining the grid cells adjacent to C and adding their holdings to C, the total holdings of the incumbent become strictly greater than T. (Note: If the holdings exactly equal T, we add the cells of B to the cells of C, and the resulting set is the partial holdings after reconfiguration.) In this case, we do not add these cells but rather solve an optimization that only adds a subset of these boundary cells such that the total weighted MHz-pops is greater than or equal to T. All cells in B containing zero population will be included in the new partial geography. We present the optimization problem that determines this new set of holdings: DATA: T is the total weighted MHz-pops that the incumbent is to have after the reconfiguration. C is the set of cells allocated for this incumbent after the iteration of the process described above in which the total weighted MHz-pops is below T. B is the set of cells in the PEA on the external border of C, where adding B into C will increase the allocated holding above T. V(C) is the weighted MHz-pops of cells in C. wij is a scalar representing the weighted MHz-pops associated with cell (i,j) for each (i,j)∈B. VARIABLES: xij is a binary variable which represents the (i,j)th cell in B. It has value 1 if this cell is included in the final reconfiguration, and 0 otherwise. OBJECTIVE FUNCTION: Minimize the total weighted MHz-pops of the cells in the new geographic footprint. mini,j∈Bwijxij CONSTRAINTS: Assuring that the total weighted MHz-pops of selected cells in B to join C together with C is at least T. VC+i,j∈Bwijxij≥T When the Geographic Footprint of an Incumbent’s Current Holdings Needs to be Decreased Define each grid cell of the PEA in terms of an i and a j coordinate (where i represents the grid cell’s position in the row numbered from left to right and the j represents the grid cell’s position in the column numbered from top to bottom). Let T be the total weighted MHz-pops that the incumbent must have after the reconfiguration. Let C be the partial holding of the incumbent in this PEA in terms of weighted MHz-pops before decreasing its footprint. The process of decreasing the geographic begins by considering the grid cells that make up the boundary of the incumbent’s current holdings in the partial PEA. That is all cells that are within the partial holding C and share a side border with cells that are not in C. Denote this new set of grid cells, B. If removing all of these cells results in holdings that are still greater than or equal to T, then each of these cells is removed and now C= C \ B. The process continues until when examining the grid cells on the boundary of C and removing them from C, the total weighted MHz-pops of the incumbent is strictly less than T. (Note: If the holdings exactly equal T: we remove the boundary cells of C, and the resulting set is the partial holdings after reconfiguration.) In this case, we do not remove these grid cells but rather solve an optimization that only removes a subset of these boundary cells such that the total weighted MHz-pops is greater than or equal to T. All cells in B containing zero population will be included in the new partial geography. We present the optimization problem that determines this new set of holdings. DATA: T is the total weighted MHz-pops that the incumbent is to have after the reconfiguration. C is the set of cells allocated for this incumbent after the iteration of the process described above in which the total weighted MHz-pops is above T. B is the set of cells in C and on the internal border of C, where removing B from C will reduce the allocated holding below T. V(C) is the weighted MHz-pops of cells in C. wij is a scalar representing the weighted MHz-pops associated with cell (i,j) for each (i,j)∈B. VARIABLES: xij is a binary variable represents the (i,j)th cell in B. It has value 1 if this cell is not included in the final reconfiguration, and 0 otherwise. OBJECTIVE FUNCTION: Maximize the total weighted MHz-pops of the cells removed from the border of C in the new geographic footprint. maxi,j∈Bwijxij CONSTRAINTS: The total weighted MHz-pops after removing the cells (i,j) in B that will not be included in the final configuration is at least T. VC-i,j∈Bwijxij≥T March 20, 2019