A key part of the 600 MHz incentive auction will be determining whether sufficient spectrum remains in which to repack those stations that don't participate in the auction or have their bids accepted. This process involves creating “pairwise interference constraint” files that pre-calculate all the channels a station could be assigned to be consistent with preservation of coverage area and population served. During the auction, a “feasibility checker” can then be used to quickly determine whether a given channel assignment is feasible using the pairwise interference constraint files.
On Nov. 3, the Incentive Auction Task Force released a preliminary software that can be used to generate the pairwise constraint data and perform feasibility checking. The notice announcing the software cautions, “We emphasize that the software we are releasing today is the product of ongoing staff work implementing decisions adopted by the Commission and has not been finalized for use in the incentive auction. The full Commission will make all final decisions regarding the repacking process and other matters relating to the incentive auction at a later date.”
Interested parties may generate their own pairwise interference constraint files using the “Constraint Generator” and the TVStudy software. The “Feasibility Checker,” which is released as open-source software by an outside software development team, can be used with the constraint files created by the “Constraint Generator” to perform feasibility checks in a manner similar to what the FCC will use during the real-time reverse auction. The software is available for download from the Incentive Auction LEARN Repacking page.
The README file on the Constraint Generator GitHub site lists the requirements for the software and they are substantial. The Constraint Generator will run on Max OS X, Linux and Windows platforms and requires the Java Runtime Environment (JRE7), PostgreSQL 9.3.1 or higher, Git, and TVStudy 1.3.1. One terabyte of disk space, 4 GB of RAM and a modern multicore processor are recommended. Each run of TVStudy produces over 500 GB of data that must be loaded into a robust database. Indexing that data will require additional space.
Generating the pairwise constraint files requires running TVStudy eight times using specific sets of channel replications. This can take five to eight hours. Once the TVStudy output files are placed in the proper directories, SQL tables have to be created. After that is completed, two models are available for Constraint Generation. These can be edited as necessary. One of the parameters that can be modified is “nationwide_acceptable_interference_pct”, the acceptable threshold of interference in terms of the interference-free population of a TV station. It defaults to 0.5 percent.
The README on the Feasibility Checker GitHub site notes the SATFC (SAT-based Feasibility Checker) combines a formulation of feasibility checking based on propositional satisfiability with a heuristic pre-solver and a SAT solver tuned for the types of instances observed in auction simulations. SATFC was created by Auctionomics, notably Alexandre Fréchette, Guillaume Saulnier-Comte, Nick Arnosti, and Kevin Leyton-Brown. For more information on how it works see Kevin Leyton-Brown's presentation Investigating the Viability of Exact Feasibility Testing. The paper includes a comparison of different solver methods, including PicoSAT (see T-Mobile: 84 MHz of UHF Spectrum Can Be Reclaimed With Limited Impact on TV).
The Feasibility Checker is primarily intended to run on Unix-like platforms and requires Java 7 or Java 8 to run. A modified version of the SAT solver clasp v2.2.3 compiled for JNA library usage is required, which in turn requires having gcc v4.8.1 or higher as well as the standard Unix C libraries. Instructions are provided on how to compile clasp. The Feasibility Checker requires two sets of data to run. One is the domain file that lists every station to be studied and the channels on which it can broadcast. The other is the pairwise interference constraint files data created by the Constraint Generator.
I doubt many individuals will have the time or resources to generate their own constraint files and perform some feasibility checks to see how the system will function. I would expect groups like the National Association of Broadcasters to put the software to the test. It will be interesting to see what they find!
