TY - JOUR

T1 - How difficult is the frequency selection problem?

AU - Jacobson, Sheldon H.

N1 - Funding Information:
The author would like to thank David Goldsman, and three anonymous referees for their recommendations and suggestions that have resulted in significant improvements in the paper's content and presentation. I would also like to thank Steve Gilbert for comments on the paper, Charles Reilly for his comments on the proofs of Theorems 2 and 3, and Douglas J. Morrice for his helpful discussions on this line of research. This research was supported in part by NSF grant DMI-9409266.
Copyright:
Copyright 2015 Elsevier B.V., All rights reserved.

PY - 1995/4

Y1 - 1995/4

N2 - 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 (IFSP), is presented. This 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.

AB - 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 (IFSP), is presented. This 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.

KW - Computational complexity

KW - Frequency domain methodology

KW - Simulation

UR - http://www.scopus.com/inward/record.url?scp=0029288144&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029288144&partnerID=8YFLogxK

U2 - 10.1016/0167-6377(95)00004-4

DO - 10.1016/0167-6377(95)00004-4

M3 - Article

AN - SCOPUS:0029288144

VL - 17

SP - 139

EP - 147

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 3

ER -