How difficult is the Frequency Selection Problem?

Frequency domain methodology has been applied to discrete-event simulations to identify terms in a polynomial metamodel of the simulation output. This paper studies the problems associated with optimally selecting input frequencies to drive the frequency domain method. This Frequency Selection Problem (FSP) can be formulated as a large mixed integer linear program (MILP) or as a large set of small linear programs (LPs). The number of such LPs with nonzero optimal values is shown to be exponential in the number of input parameters to the model. Each such LP solution corresponds to a local optimum of the MILP formulation. The LP formulation is also used to show that this local search version of FSP is polynomially solvable. A new NP-complete problem, the Indicator Function Spacing Problem is presented. The problem is then used to show that FSP is NP-easy, hence no harder than NP-complete problems. These results suggest that FSP is difficult, and that researchers addressing this problem should focus their attention on the construction of heuristic procedures rather than polynomial time algorithms.