Article

Response gradient estimation using mathematical programming models of discrete-event system sample paths

Authors:

Wai Kin (Victor) Chan,

Lee W. SchrubenAuthors Info & Claims

WSC '06: Proceedings of the 38th conference on Winter simulation

Pages 272 - 278

Published: 03 December 2006 Publication History

Abstract

This paper illustrates the use of mathematical programming in computing gradient estimators. Consistency property of these estimators is established under the usual assumptions for IPA gradient estimator consistency. A finite difference tolerance limit is introduced. For complex discrete-event systems, more concise linear programming representations are developed. These new representations provide a direct way of calculating gradient estimates.

References

[1]

Cao, X. R. (1985). Convergence of parameter sensitivity estimates in a stochastic experiment. IEEE Transactions on Automatic Control 30(9): 845--853.

[2]

Cao, X. R. and H.-F. Chen (1997). Perturbation realization, potentials, and sensitivity analysis of Markov processes. Automatic Control, IEEE Transactions on 42(10): 1382--1393.

[3]

Chan, W. K. V. (2005). Mathematical Representations of Discrete-Event System Dynamics. Ph.D. dissertation, University of California, Berkeley.

[4]

Chan, W. K. V. and L. W. Schruben (2003). Properties of discrete event systems from their mathematical programming representations. Proceedings of the 2003 Winter Simulation Conference (IEEE Cat. No. 03CH7499), ed. Chick, S. E., Sanchez, P. J., Ferrin, D., and Morrice, D. J., IEEE. Part Vol.1, 2003, pp. 496--502 Vol.1. Piscataway, NJ, USA.

Digital Library

[5]

Freimer, M. and L. Schruben (2001). Graphical representation of IPA estimation. Proceeding of the 2001 Winter Simulation Conference (Cat. No.01CH37304), ed. Peters, B. A., Smith, J. S., Medeiros, D. J., Rohrer, M. W., IEEE. Part Vol.1, 2001, pp.422--7 vol.1. Piscataway, NJ, USA.

Digital Library

[6]

Fu, M. and J.-Q. Hu (1997). Conditional Monte Carlo: gradient estimation and optimization applications, Kluwer Academic Publishers, Boston.

[7]

Fu, M. C. and J. Q. Hu (1991). Consistency of infinitesimal perturbation analysis for the GI/G/m queue. European Journal of Operational Research 54(1): 121--39.

[8]

Gal, T. (1979). Postoptimal Analyses, Parametric Programming and Related Topics, McGraw-Hill, London.

[9]

Glasserman, P. (1991a). Gradient Estimation via Perturbation Analysis, Kluwer Academic Publishers, Boston.

[10]

Glasserman, P. (1991b). Structural conditions for perturbation analysis of queuing-systems. Journal of the Association for Computing Machinery 38(4): 1005--1025.

Digital Library

[11]

Gong, W. B. and Y. C. Ho (1987). Smoothed (conditional) perturbation analysis of discrete event dynamic-systems. Ieee Transactions on Automatic Control 32(10): 858--866.

[12]

Ho, Y. C. and X. Cao (1991). Perturbation Analysis of Discrete Event Dynamic Systems, Kluwer Academic Publishers, Boston.

[13]

Ho, Y. C., M. A. Eyler and T. T. Chien (1979). A gradient technique for general buffer storage design in a production line. International Journal of Production Research 17(6): 557--580.

[14]

Homem-de-Mello, T., A. Shapiro and M. L. Spearman (1999). Finding optimal material release times using simulation-based optimization. Management Science 45(1): 86--102.

Digital Library

[15]

Lindley, D. V. (1952). The theory of queues with a single server. Proceedings of the Cambridge Philosophical Society 48(2): 277--289.

[16]

Schruben, L. W. (2000). Mathematical programming models of discrete event system dynamics. 2000 Winter Simulation Conference Proceedings (Cat. No. 00CH37165), ed. Joines, J. A., Barton, R. R., Kang, K., and Fishwick, P. A., IEEE. Part vol.1, 2000, pp.381--5 vol.1. Piscataway, NJ, USA.

Digital Library

[17]

Suri, R. (1987). Infinitesimal perturbation analysis for general discrete event systems. Journal of the ACM 34(3): 686--717.

Digital Library

[18]

Suri, R. (1989). Perturbation analysis - the state of the art and research issues explained Via the GI/G/1 Queue. Proceedings of the IEEE 77(1): 114--137.

[19]

Suri, R. and M. A. Zazanis (1988). Perturbation analysis gives strongly consistent sensitivity estimates for the M/G/1 queue. Management Science 34(1): 39--64.

Digital Library

Cited By

Fu MHenderson S(2017)History of seeking better solutions, aka simulation optimizationProceedings of the 2017 Winter Simulation Conference10.5555/3242181.3242192(1-27)Online publication date: 3-Dec-2017
https://dl.acm.org/doi/10.5555/3242181.3242192
Chan WClosser NHill RKuhl M(2013)Sensitivity analysis of linear programming formulations for G/G/m queueProceedings of the 2013 Winter Simulation Conference: Simulation: Making Decisions in a Complex World10.5555/2675983.2676070(667-677)Online publication date: 8-Dec-2013
https://dl.acm.org/doi/10.5555/2675983.2676070
Barton RDunkin AIngalls R(2009)Simulation optimization using metamodelsWinter Simulation Conference10.5555/1995456.1995494(230-238)Online publication date: 13-Dec-2009
https://dl.acm.org/doi/10.5555/1995456.1995494
Show More Cited By

Response gradient estimation using mathematical programming models of discrete-event system sample paths
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Adaptive perturbation-based gradient estimation for discrete latent variable models
AAAI'23/IAAI'23/EAAI'23: Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence

The integration of discrete algorithmic components in deep learning architectures has numerous applications. Recently, Implicit Maximum Likelihood Estimation, a class of gradient estimators for discrete exponential family distributions, was proposed by ...
Outlier detection and robust covariance estimation using mathematical programming

The outlier detection problem and the robust covariance estimation problem are often interchangeable. Without outliers, the classical method of maximum likelihood estimation (MLE) can be used to estimate parameters of a known distribution from ...
Gradient estimation with discrete stein operators
NIPS '22: Proceedings of the 36th International Conference on Neural Information Processing Systems

Gradient estimation—approximating the gradient of an expectation with respect to the parameters of a distribution—is central to the solution of many machine learning problems. However, when the distribution is discrete, most common gradient estimators ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

WSC '06: Proceedings of the 38th conference on Winter simulation

December 2006

2429 pages

ISBN:1424405017

Editors:
L. Felipe Perrone
Bucknell University
,
Barry G. Lawson
University of Richmond
,
Jason Liu
Colorado School of Mines
,
Frederick P. Wieland
Sensis Corporation
,
General Chair:
David Nicol
University of Illinois, Urbana-Champaign
,
Program Chair:
Richard Fujimoto
College of Computing, Georgia Tech

Sponsors

IIE: Institute of Industrial Engineers
ASA: American Statistical Association
IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
IEEE-CS\DATC: The IEEE Computer Society
SIGSIM: ACM Special Interest Group on Simulation and Modeling
NIST: National Institute of Standards and Technology
(SCS): The Society for Modeling and Simulation International
INFORMS-CS: Institute for Operations Research and the Management Sciences-College on Simulation

Publisher

Winter Simulation Conference

Publication History

Published: 03 December 2006

Check for updates

Qualifiers

Article

Conference

WSC06

Sponsor:

IIE
ASA
IEICE ESS
IEEE-CS\DATC
SIGSIM
NIST
(SCS)
INFORMS-CS

WSC06: Winter Simulation Conference 2006

December 3 - 6, 2006

California, Monterey

Acceptance Rates

WSC '06 Paper Acceptance Rate 177 of 252 submissions, 70%;

Overall Acceptance Rate 3,413 of 5,075 submissions, 67%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
142
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Fu MHenderson S(2017)History of seeking better solutions, aka simulation optimizationProceedings of the 2017 Winter Simulation Conference10.5555/3242181.3242192(1-27)Online publication date: 3-Dec-2017
https://dl.acm.org/doi/10.5555/3242181.3242192
Chan WClosser NHill RKuhl M(2013)Sensitivity analysis of linear programming formulations for G/G/m queueProceedings of the 2013 Winter Simulation Conference: Simulation: Making Decisions in a Complex World10.5555/2675983.2676070(667-677)Online publication date: 8-Dec-2013
https://dl.acm.org/doi/10.5555/2675983.2676070
Barton RDunkin AIngalls R(2009)Simulation optimization using metamodelsWinter Simulation Conference10.5555/1995456.1995494(230-238)Online publication date: 13-Dec-2009
https://dl.acm.org/doi/10.5555/1995456.1995494
Matta AJefferson TFowler JIngalls R(2008)Simulation optimization with mathematical programming representation of discrete event systemsProceedings of the 40th Conference on Winter Simulation10.5555/1516744.1516987(1393-1400)Online publication date: 7-Dec-2008
https://dl.acm.org/doi/10.5555/1516744.1516987
Chan WSchruben LJefferson TFowler JIngalls R(2008)Mathematical programming representations for state-dependent queuesProceedings of the 40th Conference on Winter Simulation10.5555/1516744.1516839(495-501)Online publication date: 7-Dec-2008
https://dl.acm.org/doi/10.5555/1516744.1516839

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten