WSC 2001 Final Abstracts

Modeling and Generating Multivariate Time Series with Arbitrary Marginals and Autocorrelation Structures
Bahar Deler 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. In this paper, we present a general-purpose input-modeling tool for representing, fitting, and generating random variates from multivariate input processes to drive computer simulations. We explain the theory underlying the suggested data fitting and data generation techniques, and demonstrate that our framework fits models accurately to both univariate and multivariate input processes.

Generating Daily Changes in Market Variables Using a Multivariate Mixture of Normal Distributions
Jin Wang (Valdosta State University)

Abstract:
The mixture of normal distributions provides a useful extension of the normal distribution for modeling of daily changes in market variables with fatter-than-normal tails and skewness. An efficient analytical Monte Carlo method is proposed for generating daily changes using a multivariate mixture of normal distributions with arbitrary covariance matrix. The main purpose of this method is to transform (linearly) a multivariate normal with an input covariance matrix into the desired multivariate mixture of normal distributions. This input covariance matrix can be derived analytically. Any linear combination of mixtures of normal distributions can be shown to be a mixture of normal distributions.

Accounting for Input Model and Parameter Uncertainty in Simulation
Faker Zouaoui (Sabre, Inc.) and James R. Wilson (NC State University)

Abstract:
Taking into account input-model, input-parameter, and stochastic uncertainties inherent in many simulations, our Bayesian approach to input modeling yields valid point and confidence-interval estimators for a selected posterior mean response. Exploiting prior information to specify the prior plausibility of each candidate input model and to construct prior distributions on the model's parameters, we combine this information with the likelihood function of sample data to compute posterior model probabilities and parameter distributions. Our Bayesian Simulation Replication Algorithm involves: (a) estimating parameter uncertainty by sampling from the posterior parameter distributions on selected runs; (b) estimating stochastic uncertainty by multiple independent replications of those runs; and (c) estimating model uncertainty by weighting the results of (a) and (b) using the corresponding posterior model probabilities. We allocate runs in (a) and (b) to minimize final estimator variance subject to a computing-budget constraint. An experimental performance evaluation demonstrates the advantages of this approach.

Towards a Framework for Black-Box Simulation Optimization
Sigurdur Ólafsson and Jumi Kim (Iowa State University)

Abstract:
Optimization using simulation has increased in popularity in recent years as more and more simulation packages now offer optimization features. At the same time, academic research in this area has grown, but more work is needed to bring results from the academic community to solve practical problems. This paper describes an effort in this direction. We present a framework that can be used to effectively solve large combinatorial-type simulation optimization problems in an automated or semi-automated manner.

Global Random Optimization by Simultaneous Perturbation Stochastic Approximation
John L. Maryak (Johns Hopkins University, Applies Physics Lab) and Daniel C. Chin (Johns Hopkins University, Applied Physics Lab)

Abstract:
A desire with iterative optimization techniques is that the algorithm reach the global optimum rather than get stranded at a local optimum value. Here, we examine the global convergence properties of a "gradient free" stochastic approximation algorithm called "SPSA," that has performed well in complex optimization problems. We establish two theorems on the global convergence of SPSA. The first provides conditions under which SPSA will converge in probability to a global optimum using the well-known method of injected noise. In the second theorem, we show that, under different conditions, "basic" SPSA without injected noise can achieve convergence in probability to a global optimum. This latter result can have important benefits in the setup (tuning) and performance of the algorithm. The discussion is supported by numerical studies showing favorable comparisons of SPSA to simulated annealing and genetic algorithms.

Constrained Optimization Over Discrete Sets Via SPSA with Application to Non-Separable Resource Allocation
James E. Whitney, II and Latasha I. Solomon (Morgan State University) and Stacy D. Hill (Johns Hopkins University-Applied Physics Laboratory)

Abstract:
This paper presents a version of the Simultaneous Perturbation Stochastic Approximation (SPSA) algorithm for optimizing non-separable functions over discrete sets under given constraints. The primary motivation for discrete SPSA is to solve a class of resource allocation problems wherein the goal is to distribute a finite number of discrete resources to finitely many users in such a way as to optimize a specified objective function. The basic algorithm and the application of the algorithm to the optimal resource allocation problem is discussed and simulation results are presented which illustrate its performance.

Stopping Simulated Paths Early
Paul Glasserman (Columbia Business School) and Jeremy Staum (Cornell University)

Abstract:
We provide results about stopping simulation paths early as a variance reduction technique, adding to our earlier work on this topic. The problem of pricing a financial instrument with cashflows at multiple times, such as a mortgage-backed security, motivates this approach, which is more broadly applicable to problems in which early steps are more informative than later steps of a path. We prove a limit theorem that demonstrates that this relative informativeness of simulation steps, not the number of steps, determines the effectiveness of the method. Next we consider an extension of the idea of stopping simulation paths early, showing how early stopping can be random and depend on the state a path has reached, yet still produce an unbiased estimator. We illustrate the potential effectiveness of such estimators, and describe directions for future research into their design.

Efficient Simulation for Discrete Path-Dependent Option Pricing
James M. Calvin (New Jersey Institute of Technology)

Abstract:
In this paper we present an algorithm for simulating functions of the minimum and terminal value for a random walk with Gaussian increments. These expectations arise in connection with estimating the value of path-dependent options when prices are monitored at a discrete set of times. The expected running time of the algorithm is bounded above by a constant as the number of steps increases.

A New Approach to Pricing American-Style Derivatives
Scott B. Laprise, Michael C. Fu, and Steven I. Marcus (University of Maryland) and Andrew E. B. Lim (Columbia University)

Abstract:
This paper presents a new approach to pricing American-style derivatives. By approximating the value function with a piecewise linear interpolation function, the option holder's continuation value can be expressed as a summation of European call option values. Thus the pricing of an American option written on a single underlying asset can be converted to the pricing of a series of European call options. We provide two examples of American-style options where this approximation technique yields both upper and lower bounds on the true option price.

Variance Estimation Using Replicated Batch Means
Sigrún Andradóttir and Nilay Tanik Argon (Georgia Institute of Technology)

Abstract:
We present a new method for obtaining confidence intervals in steady-state simulation. In our replicated batch means method, we do a small number of independent replications to estimate the steady-state mean of the underlying stochastic process. In order to obtain a variance estimator, we further group the observations from these replications into non-overlapping batches. We show that for large sample sizes, the new variance estimator is less biased than the batch means variance estimator, the variances of the two variance estimators are approximately equal, and the new steady-state mean estimator has a smaller variance than the batch means estimator when there is positive serial correlation between the observations. For small sample sizes, we compare our replicated batch means method with the (standard) batch means and multiple replications methods empirically, and show that the best overall coverage of confidence intervals is obtained by the replicated batch means method with a small number of replications.

On the MSE Robustness of Batching Estimators
Yingchieh Yeh and Bruce W. Schmeiser (Purdue University)

Abstract:
Variance is a classical measure of a point estimator's sampling error. In steady-state simulation experiments, many estimators of this variance---or its square root, the standard error---depend upon batching the output data. In practice, the optimal batch size is unknown because it depends upon unknown statistical properties of the simulation output data. When optimal batch size is estimated, the batch size used is random. Therefore, robustness to estimated batch size is a desirable property for a standard-error estimation method. We argue that a previous measure---the second derivative of mse with respect to estimated batch size---is conceptually flawed. We propose a new measure, the second derivative of the mse with respect to the estimated center of gravity of the non-negative autocorrelations of the output process. A property of the new robustness measure is that both mse and robustness yield identical rankings.

Improving Standardized Time Series Methods by Permuting Path Segments
James M. Calvin and Marvin K. Nakayama (New Jersey Institute of Technology)

Abstract:
We describe an extension procedure for constructing new standardized time series procedures from existing ones. The approach is based on averaging over sample paths obtained by permuting path segments. Analytical and empirical results indicate that permuting improves standardized time series methods. We also propose a new standardized time series method based on maximums.

Accounting for Parameter Uncertainty in Simulation Input Modeling
Faker Zouaoui (Sabre, Inc.) and James R. Wilson (NC State Univ)

Abstract:
We formulate and evaluate a Bayesian approach to probabilistic input modeling. Taking into account the parameter and stochastic uncertainties inherent in most simulations, this approach yields valid predictive inferences about the output quantities of interest. We use prior information to construct prior distributions on the input-model parameters. Combining this prior information with the likelihood function of sample data observed on the input processes, we compute the posterior parameter distributions using Bayes' rule. This leads to a Bayesian Simulation Replication Algorithm in which: (a) we estimate the parameter uncertainty by sampling from the posterior distribution of the input model's parameters on selected simulation runs; and (b) we estimate the stochastic uncertainty by multiple independent replications of those selected runs. We also formulate some performance evaluation criteria that are reasonable within both the Bayesian and frequentist paradigms. An experimental performance evaluation demonstrates the advantages of the Bayesian approach versus conventional frequentist techniques.

Reducing Input Parameter Uncertainty for Simulations
Szu Hui Ng and Stephen E. Chick (Department of Industrial and Operations Engineering)

Abstract:
Parameters of statistical distributions that are input to simulations are typically not known with certainty. For existing systems, or variations on existing systems, they are often estimated from field data. Even if the mean of simulation output were estimable exactly as a function of input parameters, there may still be uncertainty about the output mean because inputs are not known precisely. This paper considers the problem of deciding how to allocate resources for additional data collection so that input uncertainty is reduced in a way that effectively reduces uncertainty about the output mean. The optimal solution to the problem in full generality appears to be quite challenging. Here, we simplify the problem with asymptotic approximations in order provide closed-form sampling plans for additional data collection activities. The ideas are illustrated with a simulation of a critical care facility.

Resampling Methods for Input Modeling
Russell R. Barton (The Pennsylvania State University) and Lee W. Schruben (University of California, Berkeley)

Abstract:
Stochastic simulation models are used to predict the behavior of real systems whose components have random variation. The simulation model generates artificial random quantities based on the nature of the random variation in the real system. Very often, the probability distributions occurring in the real system are unknown, and must be estimated using finite samples. This paper shows three methods for incorporating the error due to input distributions that are based on finite samples, when calculating confidence intervals for output parameters.

A Markov Chain Perspective on Adaptive Monte Carlo Algorithms
Paritosh Y. Desai and Peter W. Glynn (Stanford University)

Abstract:
This paper discusses some connections between adaptive Monte Carlo algorithms and general state space Markov chains. Adaptive algorithms are iterative methods in which previously generated samples are used to construct a more efficient sampling distribution at the current iteration. In this paper, we describe two such adaptive algorithms, one arising in a finite-horizon computation of expected reward and the other arising in the context of solving eigenvalue problems. We then discuss the connection between these adaptive algorithms and general state space Markov chain theory, and offer some insights into some of the technical difficulties that arise in trying to apply the known theory for general state space chains to such adaptive algorithms.

Chessboard Distributions
Soumyadip Ghosh and Shane G. Henderson (Cornell University)

Abstract:
We review chessboard distributions for modeling partially specified finite-dimensional random vectors. Chessboard distributions can match a given set of marginals, a given covariance structure, and various other constraints on the distribution of a random vector. It is necessary to solve a potentially large linear program to set up a chessboard distribution, but random vectors can then be rapidly generated.

Constrained Monte Carlo and the Method of Control Variates
Roberto Szechtman and Peter W. Glynn (Stanford University)

Abstract:
A constrained Monte Carlo problem arises when one computes an expectation in the presence of a priori computable constraints on the expectations of quantities that are correlated with the estimand. This paper discusses different applications settings in which such constrained Monte Carlo computations arise, and establishes a close connection with the method of control variates when the constraints are of equality form.

Selection-of-the-Best Procedures for Optimization Via Simulation
Juta Pichitlamken and Barry L. Nelson (Northwestern University)

Abstract:
We propose fully sequential indifference-zone selection procedures that are specifically for use within an optimization-via-simulation algorithm when simulation is costly and partial or complete information on solutions previously visited is maintained. {\it Sequential Selection with Memory} guarantees to select the best or near-best alternative with a user-specified probability when some solutions have already been sampled and their previous samples are retained. For the case when only summary information is retained, we derive a modified procedure. We illustrate how our procedure can be applied to optimization-via-simulation problems and compare its performance with other methods by numerical examples.

Using Common Random Numbers for Indifference-Zone Selection
E. Jack Chen (BASF Corporation)

Abstract:
This paper discusses the validty of using common random numbers (CRNs) with two-stage selection procedures to improve the possibility of correct selection and discusses the intrinsic subset pre-selection of the Enhanced Two-Stage Selection (ETSS) procedure. We propose using CRNs with Rinott's two-stage selection and ETSS procedures when the underlying processes satisfy certain conditions. An experimental performance evaluation demonstrates the improvement in the possibility of correct selection of using CRNs with two-stage selection procedures and the intrinsic subset pre-selection of the ETSS procedure.

A Genetic Algorithm and an Indifference-Zone Ranking and Selection Framework for Simulation Optimization
Henrik E. Hedlund and Mansooreh Mollaghasemi (University of Central Florida)

Abstract:
A methodology for optimization of simulation models is presented. The methodology is based on a genetic algorithm in conjunction with an indifference-zone ranking and selection procedure under common random numbers. An application of this optimization algorithm to a stochastic mathematical model is provided in this paper.

Graphical Representation of IPA Estimation
Michael Freimer (School of ORIE, Cornell University) and Lee Schruben (Department of IEOR, University of California at Berkeley)

Abstract:
Infinitesimal Perturbation Analysis (IPA) estimators of the response gradient for a discrete event stochastic simulation are typically developed within the framework of Generalized semi-Markov processes (GSMPs). Unfortunately, while mathematically rigourous, GSMPs are not particularly useful for modeling real systems. In this paper we describe a procedure that allows IPA gradient estimation to be easily and automatically implemented in the more general and intuitive modeling context of Event Graphs. The intent is to make IPA gradient estimation more easily understood and more widely accessible. The pictorial nature of Event Graphs also provides insights into the basic IPA calculations and alternative descriptions of conditions under which the IPA estimator is known to be unbiased.

Monte Carlo Simulation Approach to Stochastic Programming
Alexander Shapiro (Georgia Institute of Technology )

Abstract:
Various stochastic programming problems can be formulated as problems of optimization of an expected value function. Quite often the corresponding expectation function cannot be computed exactly and should be approximated, say by Monte Carlo sampling methods. In fact, in many practical applications, Monte Carlo simulation is the only reasonable way of estimating the expectation function. In this talk we discuss converges properties of the sample average approximation (SAA) approach to stochastic programming. We argue that the SAA method is easily implementable and can be surprisingly efficient for some classes of stochastic programming problems.

Stochastic Modeling of Airlift Operations
Julien Granger, Ananth Krishnamurthy, and Stephen M. Robinson (University of Wisconsin-Madison)

Abstract:
Large-scale military deployments require transporting equipment and personnel over long distances in a short time. Planning an efficient airlift system is complicated and several models exist in the literature. Particularly, a study conducted on a deterministic optimization model developed by the Naval Postgraduate School and the RAND Corporation has shown that incorporating stochastic events leads to a degradation of performance. In this paper we investigate the applicability of network approximation methods to take into account randomness in an airlift network. Specifically, we show that approximation methods can model key performance features with sufficient accuracy to permit their use for network improvement, while requiring only a small fraction of the computational work that would have been needed had simulation been used for all of the performance evaluations. Also, we predict that combining simulation and approximation may work substantially better than either one of these alone.

Importance Sampling Using the Semi-Regenerative Method
James M. Calvin (New Jersey Institute of Technology), Peter W. Glynn (Stanford University) and Marvin K. Nakayama (New Jersey Institute of Technology)

Abstract:
We discuss using the semi-regenerative method, importance sampling, and stratification to estimate the expected cumulative reward until hitting a fixed set of states for a discrete-time Markov chain on a countable state space. We develop a general theory for this problem and present several central limit theorems for our estimators. We also present some empirical results from applying these techniques to simulate a reliability model.

Quantile and Histogram Estimation
E. Jack Chen (BASF Corporation) and W. David Kelton (The Pennsylvania State University)

Abstract:
This paper discusses implementation of a sequential procedure to construct proportional half-width confidence intervals for a simulation estimator of the steady-state quantiles and histograms of a stochastic process. Our quasi-independent (QI) procedure increases the simulation run length progressively until a certain number of essentially independent and identically distributed samples are obtained. We compute sample quantiles at certain grid points and use Lagrange interpolation to estimate the p quantile. It is known that order statistics quantile estimator is asymptotically unbiased when the output sequences satisfy certain conditions. Even though the proposed sequential procedure is a heuristic procedure, it does have strong basis. Our empirical results show that the procedure gives quantile estimates and histograms that satisfy a pre-specified precision requirement. An experimental performance evaluation demonstrates the validity of using the QI procedure to estimate the quantiles and histograms.

On-Line Error Bounds for Steady-State Approximations: A Potential Solution to the Initialization Bias Problem
Enver Yücesan, Luk N. Van Wassenhove, and Klenthis Papanikas (INSEAD) and Nico M. van Dijk (University of Amsterdam)

Abstract:
By studying performance measures via reward structures, on-line error bounds are obtained by successive approximation. These bounds indicate when to terminate computation with guaranteed accuracy; hence, they provide insight into steady-state convergence. The method therefore presents a viable alternative to steady-state computer simulation where the output series is typically contaminated with initialization bias whose impact on the output cannot be easily quantified. The method is illustrated on a number of capacitated queueing networks. The results indicate that the method offers a practical tool for numerically approximating performance measures of queueing networks. Results on steady-state convergence further quantify the error involved in analyzing an inherently transient system using a steady-state model.

Simulating Ruin Probabilities in Insurance Risk Processes with Subexponential Claims
Nam Kyoo Boots (Vrije University) and Perwez Shahabuddin (Columbia University)

Abstract:
We describe a fast simulation framework for simulating small ruin probabilities in insurance risk processes with subexponential claims. Naive simulation is inefficient for estimating small probabilities since the event of interest is rare, and special simulation techniques like importance sampling need to be used. An importance sampling change of measure known as subexponential twisting has been found useful for some rare event simulations in the subexponential context. We describe a set of conditions on the process that are sufficient to ensure that the infinite horizon probability can be estimated in a (work-normalized) large set asymptotically optimal manner, using this change of measure. These conditions are satisfied for some large classes of insurance risk processes -- e.g., processes with Markov-modulated claim-arrivals and claim-sizes -- where the heavy tails are of the `Weibull type'. We also give similar conditions, that are much weaker, for the estimation of the finite horizon ruin probability. Finally, we present experiments supporting our results.

Using Quantile Estimates in Simulating Internet Queues with Pareto Service Times
Martin J. Fischer and Denise M. Bevilacqua Masi (Mitretek Systems), Donald Gross and John Shortle (George Mason University) and Percy H. Brill (University of Windsor)

Abstract:
It is readily apparent how important the Internet is to modern life. The exponential growth in its use requires good tools for analyzing congestion. Much has been written recently asserting that classical queueing models assuming Poisson arrivals or exponential service cannot be used for the accurate study of congestion in major portions of the Internet. Internet traffic data indicate that heavy-tailed distributions (e.g., Pareto) serve as better models in many situations for packet service lengths. But these distributions may not possess closed-form analytic Laplace transforms; hence, much of standard queueing theory cannot be used. Simulating such queues becomes essential; however, previous research pointed out difficulties in obtaining the usual moment performance measures such as mean wait in queue. In this paper, we investigate using quantile estimates of waiting times (e.g., median instead of mean), which appear to be considerably more efficient when service times are Pareto.

Sensitivity Analysis of Censored Output through Polynomial, Logistic, and Tobit Regression Meta-Models: Theory and Case Study
Jack P. C. Kleijnen (Tilburg University) and Antonie Vonk Noordegraaf and Mirjam Nielen (Wageningen University)

Abstract:
This paper focuses on simulation output that may be censored; that is, the output has a limited range (examples are simulations that have as output the time to occurrence of a specific event - such as a ‘rare' event - within a fixed time horizon). For sensitivity analysis of such simulations we discuss three alternatives: (i) traditional polynomial regression models, (ii) logistic or logit regression, and (iii) tobit analysis. The case study concerns the control of a specific animal disease (namely, IBR) in The Netherlands. The simulation experiment has 31 environmental factors or inputs, combined into 64 scenarios - each replicated twice. Traditional polynomial regression gives some estimated main effects with wrong signs. Logit regression correctly predicts whether simulation output is censored or not, for 92% of the scenarios. Tobit analysis does not give effects with wrong signs; it correctly predicts censoring, for 89% of the scenarios.