WSC 2002 Final Abstracts |
Monday 10:30:00 AM 12:00:00 PM
Advanced Input Modeling
Chair:
Shane G. Henderson (Cornell University)
Parameter Estimation for ARTA
Processes
Bahar Biller (Carnegie Mellon University) and Barry L.
Nelson (Northwestern University)
Abstract:
Providing accurate and automated input-modeling support
is one of the challenging problems in the application of computer simulation.
The models incorporated in current input-modeling software packages often fall
short of what is needed because they emphasize independent and identically
distributed processes, while dependent time-series processes occur naturally
in the simulation of many real-life systems. This paper introduces a
statistical methodology for fitting stochastic models to dependent time-series
input processes. Specifically, an automated and statistically valid algorithm
is presented to fit ARTA (Autoregressive-to-Anything) processes with marginal
distributions from the Johnson translation system to stationary univariate
time-series data. The use of this algorithm is illustrated via a real-life
example.
Properties of the NORTA Method in Higher
Dimensions
Soumyadip Ghosh and Shane G. Henderson (Cornell
University)
Abstract:
The NORTA method for multivariate generation is a fast
general purpose method for generating samples of a random vector with given
marginal distributions and given product-moment or rank correlation matrix.
However, this method has been shown to fail to work for some feasible
correlation matrices. (A matrix is feasible if there exists a random vector
with the given marginal distributions and the matrix as the correlation
matrix.) We investigate how this feasibility problem behaves as the dimension
of the random vector is increased and find the problem to become acute
rapidly. We also find that a modified NORTA procedure, augmented by a
semidefinite program (SDP) that aims to generate a correlation matrix "close"
to the desired one, performs well with increasing dimension.
The Vine Copula Method for Representing High
Dimensional Dependent Distributions: Application to Continuous Belief
Nets
Dorota Kurowicka and Roger M. Cooke (Delft University of
Technology)
Abstract:
High dimensional probabilistic models are often
formulated as belief nets (BN’s), that is, as directed acyclic graphs with
nodes representing random variables and arcs representing “influence”. BN’s
are conditionalized on incoming information to support probabilistic inference
in expert system applications. For continuous random variables, an adequate
theory of BN’s exists only for the joint normal distribution. In general, an
arbitrary correlation matrix is not compatible with arbitrary marginals, and
conditionalization is quite intractable. Transforming to normals is unable to
reproduce exactly a specified rank correlation matrix. We show that a
continuous belief net can be represented as a regular vine, where an arc from
node i to j is associated with a (conditional) rank correlation between i and
j. Using the elliptical copula and the partial correlation transformation
properties, it is very easy to conditionalize the distribution on the value of
any node, and hence update the BN.
Monday 1:30:00 PM 3:00:00 PM
Optimization via Simulation
Chair: Barry L. Nelson (Northwestern University)
Two-Stage NP Method with
Inheritance
Jumi Kim and Sigurdur Ólafsson (Iowa State University)
Abstract:
The nested partitions method is a flexible and
effective framework of optimizing large-scale problems with combinatorial
structure. In this paper we consider the nested partitions method for
simulation optimization and propose a new variant that uses inheritance to
speed convergence. The new nested partitions method with inheritance algorithm
performs well for when applied to test problems but it also calls for new
analysis of convergence.
Randomized-Direction Stochastic Approximation Algorithms
Using Deterministic Sequences
Xiaoping Xiong (University of
Maryland), I-Jeng Wang (Johns Hopkins University) and Michael C. Fu
(University of Maryland)
Abstract:
We study the convergence and asymptotic normality of a
generalized form of stochastic approximation algorithm with deterministic
perturbation sequences. Both one-simulation and two-simulation methods are
considered. Assuming a special structure of deterministic sequence, we
establish sufficient condition on the noise sequence for a.s. convergence of
the algorithm. Construction of such a special structure of deterministic
sequence follows the discussion of asymptotic normality. Finally we discuss
ideas on further research in analysis and design of the deterministic
perturbation sequences.
A Combined Procedure for Optimization via
Simulation
Juta Pichitlamken (Kasetsart University) and Barry L.
Nelson (Northwestern University)
Abstract:
We propose an optimization-via-simulation algorithm for
use when the performance measure is estimated via a stochastic, discrete-event
simulation, and the decision variables may be subject to deterministic linear
integer constraints. Our approach - which consists of a global guidance
system, a selection-of-the-best procedure, and local improvement - is globally
convergent under very mild conditions.
Monday 3:30:00 PM 5:00:00 PM
Rare Event Simulation and Combinatorial
Optimization Using Cross Entropy
Chair: Perwez Shahabuddin (Columbia
University)
Estimating Buffer Overflows in Three Stages Using
Cross-Entropy
P. T. de Boer (University of Twente), D. P. Kroese
(The University of Queensland) and R. Y. Rubinstein (Technion)
Abstract:
In this paper we propose a fast adaptive Importance
Sampling method for the efficient simulation of buffer overflow probabilities
in queueing networks. The method comprises three stages. First we estimate the
minimum Cross-Entropy tilting parameter for a small buffer level; next, we use
this as a starting value for the estimation of the optimal tilting parameter
for the actual (large) buffer level; finally, the tilting parameter just found
is used to estimate the overflow probability of interest. We recognize three
distinct properties of the method which together explain why the method works
well; we conjecture that they hold for quite general queueing networks.
Numerical results support this conjecture and demonstrate the high efficiency
of the proposed algorithm.
Estimation of Rare Event Probabilities Using
Cross-Entropy
Tito Homem-de-Mello (Ohio State University) and
Reuven Y. Rubinstein (Technion, Israel Institute of Technology)
Abstract:
This paper deals with estimation of probabilities of
rare events in static simulation models using a fast adaptive two-stage
procedure based on importance sampling and Kullback-Liebler's cross-entropy
(CE). More specifically, at the first stage we estimate the optimal parameter
vector in the importance sampling distribution using CE, and at the second
stage we estimate the desired rare event probability using importance sampling
(likelihood ratios). Some theoretical aspects of the proposed method,
including its convergence, are established. The numerical results presented
suggest that the method effectively estimates rare event probabilities.
Sequence Alignment by Rare Event
Simulation
Jonathan Keith and Dirk P. Kroese (The University of
Queensland)
Abstract:
We present a new stochastic method for finding the
optimal alignment of DNA sequences. The method works by generating random
paths through a graph (the edit graph) according to a Markov chain. Each path
is assigned a score, and these scores are used to modify the transition
probabilities of the Markov chain. This procedure converges to a fixed path
through the graph, corresponding to the optimal (or near-optimal) sequence
alignment. The rules with which to update the transition probabilities are
based on Rubinstein's Cross-Entropy Method, a new technique for stochastic
optimization. This leads to very simple and natural updating formulas. Due to
its versatility, mathematical tractability, and simplicity, the method has
great potential for a large class of combinatorial optimization problems, in
particular in biological sciences.
Tuesday 8:30:00 AM 10:00:00 AM
Output Analysis
Chair: Bruce
Schmeiser (Purdue University)
A Comparison of Output-Analysis Methods for
Simulations of Processes with Multiple Regeneration Sequences
James
M. Calvin and Marvin K. Nakayama (New Jersey Institute of Technology)
Abstract:
We compare several simulation estimators for a
performance measure of a process having multiple regeneration sequences. We
examine the setting of two regeneration sequences. We compare two existing
estimators, the permuted estimator and the semi-regenerative estimator, and
two new estimators, a type of U-statistic estimator and a type of V-statistic
estimator. The last two estimators are obtained by resampling trajectories
without and with replacement, respectively. The permuted estimator and the
U-statistic estimator turn out to be equivalent, but the others are in general
different. We show that when estimating the second moment of a cumulative
cycle reward, the semi-regenerative and V-statistic estimators have
non-negative bias, with the semi-regenerative bias being larger. The permuted
estimator was previously shown to be unbiased. Although some of the estimators
have different small-sample properties, they all satisfy central limit
theorems with the same asymptotic variance constant.
ASAP2: An Improved Batch Means Procedure for
Simulation Output Analysis
Natalie M. Steiger (University of
Maine), Emily K. Lada and James R. Wilson (North Carolina State University),
Christos Alexopoulos (Georgia Tech ), David Goldsman (Georgia Tech) and Faker
Zouaoui (Sabre, Inc.)
Abstract:
We introduce ASAP2, an improved variant of the
batch-means algorithm ASAP for steady-state simulation output analysis. ASAP2
operates as follows: the batch size is progressively increased until the batch
means pass the Shapiro-Wilk test for multivariate normality; and then ASAP2
delivers a correlation-adjusted confidence interval. The latter adjustment is
based on an inverted Cornish-Fisher expansion for the classical batch means
t-ratio, where the terms of the expansion are estimated via a first-order
autoregressive time series model of the batch means. ASAP2 is a sequential
procedure designed to deliver a confidence interval that satisfies a
prespecified absolute or relative precision requirement. When used in this
way, ASAP2 compares favorably to ASAP and the well-known procedures ABATCH and
LBATCH with respect to close conformance to the precision requirement as well
as coverage probability and mean and variance of the half-length of the final
confidence interval.
On Choosing a Single Criterion for
Confidence-Interval Procedures
Bruce Schmeiser (Purdue University)
and Yingchieh Yeh (Yuan Ze University)
Abstract:
Stating a confidence interval is a traditional method
of indicating the sampling error of a point estimator of a model's performance
measure. We propose a single dimensionless criterion, inspired by Schruben's
coverage function, for evaluating and comparing the statistical quality of
confidence-interval procedures. Procedure quality is usually thought to be
multidimensional, composed of the mean (and maybe the variance) of the
interval-width distribution and the probability of covering the performance
measure (and maybe other values). Our criterion, which we argue lies at the
heart of what makes a confidence-interval procedure good or bad, compares a
given procedure's intervals to those of an "ideal" procedure. For a given
point estimator (such as the sample mean) and given experimental data process
(such as a first-order autoregressive process with specified parameters), our
single criterion is a function of only the sample size (or other rule that
ends sampling).
Tuesday 10:30:00 AM 12:00:00 PM
Panel Discussion on Current Issues in
Input Modeling
Chair: James R. Wilson (North Carolina State
University)
Panel on Current Issues in Simulation Input
Modeling
Russell R. Barton (The Pennsylvania State University),
Russell C. H. Cheng (University of Southampton), Stephen E. Chick (INSEAD),
Shane G. Henderson (Cornell University), Averill M. Law (Averill Law &
Associates ), Lawrence M. Leemis (The College of William & Mary), Bruce W.
Schmeiser (Purdue University), Lee W. Schruben (University of California,
Berkeley) and James R. Wilson (North Carolina State University)
Abstract:
In recent years, substantial progress has been made in
the development of powerful new approaches to modeling and generation of the
stochastic input processes driving simulation models. In this panel
discussion, we examine some of the central issues and unresolved problems
associated with each of these approaches to simulation input modeling.
Tuesday 1:30:00 PM 3:00:00 PM
Recent Advances in Simulation
Optimization
Chair: Seong-Hee Kim (Georgia Institute of Technology)
Confidence Regions for Stochastic Approximation
Algorithms
Ming-hua Hsieh (National Chengchi University) and Peter
W. Glynn (Stanford University)
Abstract:
In principle, known central limit theorems for
stochastic approximation schemes permit the simulationist to provide
confidence regions for both the optimum and optimizer of a stochastic
optimization problem that is solved by means of such algorithms.
Unfortunately, the covariance structure of the limiting normal distribution
depends in a complex way on the problem data. In particular, the covariance
matrix depends not only on variance constants but also on even more
statistically challenging parameters (e.g. the Hessian of the objective
function at the optimizer). In this paper, we describe an approach to
producing such confidence regions that avoids the necessity of having to
explicitly estimate the covariance structure of the limiting normal
distribution. This procedure offers an easy way for the simulationist to
provide confidence regions in the stochastic optimization setting.
Response Surface Methodology
Revisited
Ebru Angün, Jack P.C. Kleijnen, Dick Den Hertog, and Gül
Gürkan (Tilburg University)
Abstract:
Response Surface Methodology (RSM) searches for the
input combination that optimizes the simulation output. RSM treats the
simulation model as a black box. Moreover, this paper assumes that simulation
requires much computer time. In the first stages of its search, RSM locally
fits first-order polynomials. Next, classic RSM uses steepest descent (SD);
unfortunately, SD is scale dependent. Therefore, Part 1 of this paper derives
scale independent ‘adapted’ SD (ASD) accounting for covariances between
components of the local gradient. Monte Carlo experiments show that ASD indeed
gives a better search direction than SD. Part 2 considers multiple outputs,
optimizing a stochastic objective function under stochastic and deterministic
constraints. This part uses interior point methods and binary search, to
derive a scale independent search direction and several step sizes in that
direction. Monte Carlo examples demonstrate that a neighborhood of the true
optimum can indeed be reached, in a few simulation runs.
A Conservative Adjustment to the ETSS
Procedure
E. Jack Chen (BASF Corporation)
Abstract:
Two-stage selection procedures have been widely studied
and applied in determining the required sample size (i.e., the number of
replications or batches) for selecting the best of k designs. The Enhanced
Two-Stage Selection (ETSS) procedure is a heuristic two-stage selection
procedure that takes into account not only the variance of samples, but also
the difference of sample means when determining the sample sizes. This paper
discusses the use of a conservative adjustment with the ETSS procedure to
increase the probability of correct selection. We show how the adjustment
allocates more simulation replications or batches to more promising designs at
the second stage. An experimental performance evaluation demonstrates the
efficiency of the adjustment.
Tuesday 3:30:00 PM 5:00:00 PM
Simulation Input Analysis
Chair:
Bahar Biller (Carnegie Mellon University)
Collecting Data and Estimating Parameters for Input
Distributions
Michael Freimer (Cornell University) and Lee Schruben
(University of California, Berkeley)
Abstract:
An early stage of a simulation study often consists of
collecting data in order to parameterize the model. This paper addresses the
question of how much data to collect, and from what sources. We use designed
experiments to identify important unknown parameters, taking into account the
current level of information about them. We develop approaches based on two
common forms of analysis of variance: a fixed effects model, and a random
effects model.
Joint Criterion for Factor Identification and Parameter
Estimation
Stephen E. Chick (INSEAD) and Szu Hui Ng (Singapore
Institute of Manufacturing Technology)
Abstract:
One goal in simulation experimentation is to identify
which input parameters most significantly influence the mean of simulation
output. Another goal is to obtain good parameter estimates for a response
model that quantifies how the mean output depends on influential input
parameters. The majority of experimental design techniques focus on either one
goal or the other. This paper uses a design criterion for follow-up
experiments that jointly identifies the important parameters and reduces the
variance of parameter estimates. The criterion is entropy-based, and is
applied to a critical care facility simulation.
Difficulties in Simulating Queues with Pareto
Service
Donald Gross and John F. Shortle (George Mason University)
and Martin J. Fischer and Denise M. B. Masi (Mitretek Systems)
Abstract:
M/G/1 queues, where G is a heavy-tailed distribution,
have applications in Internet modeling and modeling for insurance claim risk.
The Pareto distribution is a special heavy-tailed distribution called a
power-tailed distribution, and has been found to serve as adequate models for
many of these situations. However, to get the waiting time distribution, one
must resort to numerical methods, e.g., simulation. Many difficulties arise in
simulating queues with Pareto service and we investigate why this may be so.
Even if we are willing to consider truncated Pareto service, there still can
be problems in simulating if the truncation point (maximum service time
possible) is too large.
Wednesday 8:30:00 AM 10:00:00 AM
Difficult Queuing Simulation
Problems
Chair: Donald Gross (George Mason
University)
Rare-Event Simulation for Infinite Server
Queues
Roberto Szechtman and Peter W. Glynn (Stanford University)
Abstract:
We discuss rare-event simulation methodology for
computing tail probabilities for infinite-server queues. Our theoretical
discussion also offers some new simulation insights into the change-of-measure
associated with the Gartner-Ellis theorem of large deviations.
A Balanced Likelihood Ratio approach for Analyzing
Rare Events in a Tandem Jackson Network
Bruce C. Shultes
(University of Cincinnati)
Abstract:
Balanced likelihood ratio importance sampling methods
were originally developed for the analysis of fault-tolerant systems. This
paper provides a basis for adapting this approach to analyze the rare event
probability that total system size reaches a bound before returning to zero in
tandem Jackson networks. An optimal importance sampling distribution for the
single server case is derived through direct application of the balanced
likelihood ratio approach. The generalization of this approach to larger
systems is explored via a two-node tandem Jackson network. A general heuristic
approach is outlined along with certain open questions whose answers could
lead to a more robust solution. Asymptotic characteristics of the proposed
importance sampling approach for the two-node network are discussed. Bounded
relative error is only possible under certain conditions. Numerical results
illustrate the benefits of the approach.
Simulating M/G/1 Queues with Heavy-Tailed
Service
John C. Sees, Jr. (Center for Army Analysis) and John F.
Shortle (George Mason University)
Abstract:
We examine the performance and accuracy of simulating
M/G/1 queues when the service time is Pareto distributed with shape parameter,
alpha, between one and three. Two applications of this problem are in
insurance risk and telecommunications. When 2 < alpha ≤ 3, the theoretical
distribution of the sample averages of the queue waiting times is a stable
distribution. When alpha ≤ 2, the mean waiting time does not exist. We provide
a modified quantile simulation method, which is able to solve harder problems
than existing methods; in addition, it requires less memory, and allows the
user to emphasize accuracy or execution time. We also give numerical examples
for other heavy-tailed distributions, such as the lognormal.
Wednesday 10:30:00 AM 12:00:00 PM
New Simulation Output Analysis
Techniques
Chair: Christos Alexopoulos (Georgia Institute of
Technology)
A Statistical Process Control Approach for
Estimating the Warm-Up Period
Stewart Robinson (University of
Warwick)
Abstract:
One means for dealing with initialization bias in
simulation experiments is to implement a warm-up period. This requires the
correct estimation of the initial transient. A new method for determining the
warm-up period, based upon the principles of statistical process control
(SPC), is described. The method is tested on empirical data from a simulation
model that has been used in a real-life study. In comparing the results to
those from two commonly used warm-up methods, it appears that the SPC method
performs well. The strengths and weaknesses of the approach are discussed.
Two-Phase Quantile Estimation
E. Jack Chen
(BASF Corporation)
Abstract:
This paper discusses the implementation of a two-phase
procedure to construct confidence intervals for a simulation estimator of the
steady-state quantiles of stochastic processes. We compute sample quantiles at
certain grid points and use Lagrange interpolation to estimate the p quantile.
The algorithm dynamically increases the sample size so that quantile estimates
satisfy the proportional precision at the first phase and the relative or
absolute precision at the second phase. We show that the procedure gives
asymptotically unbiased quantile estimates. An experimental performance
evaluation demonstrates the validity of using grid points and the
quasi-independent procedure to estimate quantiles.
A Batch Means Procedure for Mean Value
Estimation of Processes Exhibiting Long Range Dependence
Andrés
Suárez-González, José C. López-Ardao, Cándido López-García, Miguel
Rodríguez-Pérez, Manuel Fernández-Veiga, and María Estrella Estrella
Sousa-Vieira (Universidade de Vigo)
Abstract:
Mean value estimation of processes exhibiting Long
Range Dependence (LRD) requires a different approach than the techniques
applied to those exhibiting Short Range Dependence (SRD), except for the
independent replication method. We describe a nonoverlapping batch means
method able to deal with LRD processes, the LRD Batch Means method. This
method exploits the behavior of Asymptotically Second-order Self-Similar
processes: their aggregated processes become well approximated by Fractional
Gaussian Noise (FGN) processes for large aggregation levels. Once tested
positively this similarity, the method produces a correlation-adjusted
confidence interval from an empirical approximation of the distribution of the
standardized average for the particular case of FGN processes. Afterwards, we
measure its performance over both LRD and SRD
processes.