How difficult is the frequency selection problem?

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)139-147
Number of pages9
JournalOperations Research Letters
Volume17
Issue number3
DOIs
StatePublished - Apr 1995
Externally publishedYes

Keywords

  • Computational complexity
  • Frequency domain methodology
  • Simulation

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Fingerprint Dive into the research topics of 'How difficult is the frequency selection problem?'. Together they form a unique fingerprint.

  • Cite this