Common issues in discrete optimization and discrete-event simulation

Sheldon H. Jacobson, Enver Yücesan

Research output: Contribution to journalArticlepeer-review


This note studies and exploits common issues between discrete-event simulation models and algorithms for discrete optimization problems to prove that two discrete-event simulation search problems are NP-hard. More specifically, NEIGHBORHOOD, seeks a sequence of events such that two distinct states can be accessed, one state after executing all but the last k events and another state after executing all the events, while INITIALIZE seeks a sequence of events such that executing the sequence with one particular initial event results in a particular state being reached, while for a second initial event, that particular state cannot be reached. Implications of these results for discrete-event simulation modeling and analysis (e.g., assessing when steady state, termination conditions have been reached, or optimal input parameters values for simulation optimization have been established) as well as for discrete optimization problems (e.g., assessing a priori the effectiveness of a neighborhood for simulated annealing or tabu search) are discussed.

Original languageEnglish (US)
Pages (from-to)341-345
Number of pages5
JournalIEEE Transactions on Automatic Control
Issue number2
StatePublished - Feb 2002


  • Computational complexity
  • Discrete optimization
  • Discrete-event simulation
  • NP-hard

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Common issues in discrete optimization and discrete-event simulation'. Together they form a unique fingerprint.

Cite this