WSC 2005 Final Abstracts

Importance Sampling Simulation in the Presence of Heavy Tails
Achal Bassamboo (Kellogg School of Management), Sandeep Juneja (Tata Institute of Fundamental Research) and Assaf Zeevi (Columbia Business School)

Abstract:
We consider importance sampling simulation for estimating rare event probabilities in the presence of heavy-tailed distributions that have polynomial-like tails. In particular, we prove the following negative result: there does not exist an asymptotically optimal state-independent change-of-measure for estimating the probability that a random walk (respectively, queue length for a single server queue) exceeds a ``high'' threshold before going below zero (respectively, becoming empty). Furthermore, we derive explicit bounds on the best asymptotic variance reduction achieved by importance sampling relative to naive simulation. We illustrate through a simple numerical example that a ``good" state-dependent change-of-measure may be developed based on an approximation of the zero-variance measure.

Some Large Deviations Results for Latin Hypercube Sampling
Shane S. Drew and Tito Homem-de-Mello (Northwestern University)

Abstract:
Large deviations theory is a well-studied area which has shown to have numerous applications. The typical results, however, assume that the underlying random variables are either i.i.d. or exhibit some form of Markovian dependence. Our interest in this paper is to study the validity of large deviations results in the context of estimators built with \emph{Latin Hypercube sampling}, a well-known sampling technique for variance reduction. We show that a large deviation principle holds for Latin Hypercube sampling for functions in one dimension and for separable multi-dimensional functions. Moreover, the upper bound of the probability of a large deviation in these cases is no higher under Latin Hypercube sampling than it is under Monte Carlo sampling. We extend the latter property to functions that preserve negative dependence (such as functions that are monotone in each argument). Numerical experiments illustrate the theoretical results presented in the paper.

Limit Theorems for the Multilevel Splitting Algorithm in the Simulation of Rare Events
Frédéric Cérou and Francois Le Gland (IRISA / INRIA Rennes), Pierre Del Moral (Université de Nice-Sophia Antipolis) and Pascal Lezaud (CENA / ENAC)

Abstract:
In this article, a genetic-type algorithm based on interacting particle systems is presented, together with a genealogical model, for estimating a class of rare events arising for instance in telecommunication networks, nuclear engineering, etc. The distribution of a Markov process hitting a rare but critical set is represented in terms of a Feynman-Kac model in path space. Approximation results obtained previously for these models are applied here to estimate the probability of the rare events as well as the probability distribution of the critical trajectories.

Procedures for Feasibility Detection in the Presence of Multiple Constraints
Demet Batur and Seong-Hee Kim (Georgia Institute of Technology)

Abstract:
In this paper, we address the problem of finding a set of feasible or near-feasible systems among a finite number of simulated systems in the presence of stochastic constraints. Andradottir, Goldsman, and Kim (2005) present a procedure that detects feasibility of systems in the presence of one constraint with a pre-specified probability of correctness. We extend their procedure to the case of multiple constraints by the use of the Bonferroni inequality. Unfortunately, the resulting procedure tends to be very conservative when the number of systems or constraints is large. As a remedy, we present a screening procedure that uses an aggregated observation, which is a linear combination of the collected observations across stochastic constraints. Then, we present an accelerated procedure that combine the extension of Andradottir, Goldsman, and Kim (2005) with the procedure that uses aggregated observations. Some experimental results that compare the performance of the proposed procedures are presented.

A Moving Mesh Approach for Simulation Budget Allocation on Continuous Domains
Mark W. Brantley and Chun-Hung Chen (George Mason University)

Abstract:
We introduce a moving mesh algorithm for simulation optimization across a continuous domain. During each iteration, the mesh movement is determined by allocating simulation runs to partitions of the domain that are critical in the process of identifying good solutions. The partition boundaries are then adjusted to equally distribute the allocation runs between each partition. To test the moving mesh algorithm, we implemented it using the OCBA method to allocate simulation runs to each partition. But, the simplicity of the procedure should provide flexibility for it to be used with other simulation optimization techniques. Results are presented for several numerical experiments and suggest that the technique has potential given further development.

New Developments in Ranking and Selection: An Empirical Comparison of the Three Main Approaches
Jürgen Branke and Christian Schmidt (Universität Karlsruhe (TH)) and Stephen E. Chick (INSEAD)

Abstract:
Selection procedures are used in many applications to select the best of a finite set of alternatives, as in discrete optimization with simulation. There are a wide variety of procedures, which begs the question of which selection procedure to select. This paper (a) summarizes the main structural approaches to deriving selection procedures, (b) describes an innovative empirical testbed, and (c) summarizes esults from work in progress that provides the most exhaustive assessment of selection procedures to date. The most efficient and easiest to control procedures allocate samples with a Bayesian model for uncertainty about the means, and use a new expected opportunity cost-based stopping rule.

Determination of the 'Best' That Meets a Limit Standard
Roy R. Creasey Jr., Melanie B. Marks, and Bennie D. Waller (Longwood University) and K. Preston White, Jr. (University of Virginia)

Abstract:
This paper describes on-going research, where we compare, via simulation experiments, a stochastic system to a standard. We are particularly interested in a subset of standards we call limit standards. A limit standard is a maximum or minimum benchmark derived from requirements, another model, or the actual system. The problem is to determine if a system meets the limit standard at customer-defined probabilities. Then, for those systems that meet the limit standard, identify which system is the “best,” or results in the lowest probability of reaching the standard. Current comparison methods are based on expected value and cannot solve this type of problem. We outline a two-step approach, using methods from acceptance sampling and ordered statistics, to solve this problem.

Using Parallel and Distributed Computing to Increase the Capability of Selection Procedures
E. Jack Chen (BASF Corporation)

Abstract:
We present a framework for deploying selection procedures in a parallel and distributed environment to identify the stochastic systems with optimal expected response when the number of alternatives is large. The goal is to speed up the process of identifying a good design with a specified probability. We present a sequential selection procedure and discuss the validity of dividing the entire set of alternative designs into several groups that can be processed in a parallel and distributed fashion. The surviving designs from each group are then processed subsequently. An experimental evaluation demonstrates the validity and efficiency of the procedure.

Finding the Best in the Presence of a Stochastic Constraint
Sigrún Andradóttir, David Goldsman, and Seong-Hee Kim (Georgia Institute of Technology)

Abstract:
Our problem is that of finding the best system - i.e., the system with the largest or smallest primary performance measure - among a finite number of simulated systems in the presence of a stochastic constraint on a secondary performance measure. In order to solve this problem, we first find a set that contains only feasible or near-feasible systems (Phase I) and then choose the best among those systems in the set (Phase II). We present a statistically valid procedure for Phase I and then propose another procedure that performs Phases I and II sequentially to find the best feasible system. Finally, we provide some experimental results for the second procedure.

Initial Transient Problem for Steady-state Output Analysis
Peter W. Glynn (Stanford University)

Abstract:
This tutorial is concerned with providing an overview of the key issues that arise in consideration of the initial transient problem for steady-state simulations. In addition, we will discuss the related problem of construction of low-bias estimators.

A Test of Randomness Based on the Distance Between Consecutive Random Number Pairs
Matthew J. Duggan, John H. Drew, and Lawrence M. Leemis (The College of William & Mary)

Abstract:
One of the most popular methods of generating "random" numbers for use in a computer program employs a Lehmer random number generator. If constructed properly, these generators will yield streams of numbers that will appear random but can also be easily replicated. However, Marsaglia (1968) discovered a potential flaw in these random number generators, namely, if consecutive n-tuples of the generated numbers are plotted in n-dimensional space, the points may fall into a small number of hyperplanes. In this paper, we compare the theoretical distribution of the distances to the actual distances produced by a specific random number generator in order to devise a statistical test of randomness for the validity of the random number generator.

Cycle-Time Quantile Estimation in Manufacturing Systems Employing Dispatching Rules
Jennifer E. McNeill, John W. Fowler, and Gerald T. Mackulak (Arizona State University) and Barry L. Nelson (Northwestern University)

Abstract:
The cycle-time distribution of manufacturing systems employing dispatching rules other than FIFO can be both highly skewed and have heavy tails. Previous cycle-time quantile estimation work has suggested that the Cornish-Fisher expansion can be used in conjunction with discrete-event simulation to provide cycle-time quantile estimates for a variety of systems operating under FIFO dispatching without requiring excess data storage. However, when the cycle-time distribution exhibits heavy skewness and kurtosis, the accuracy of quantile estimates obtained using the Cornish-Fisher expansion may degrade, sometimes severely. This paper demonstrates the degradation and motivates the need for a modification to the Cornish-Fisher expansion for estimating quantiles under non-FIFO dispatching rules. A solution approach combining a data transformation, the maximum (minimum)-transformation, with the Cornish-Fisher expansion is presented. Results show that this provides significant improvements in accuracy over using the Cornish-Fisher expansion alone while still retaining the advantage of requiring minimal data storage.

Linear Combinations of Overlapping Variance Estimators for Simulations
Tûba Aktaran-Kalayci and David Goldsman (Georgia Institute of Technology)

Abstract:
We examine properties of linear combinations of overlapping standardized time series area estimators for the variance parameter of a stationary stochastic process. We find that the linear combination estimators have lower bias and variance than their overlapping constituents and nonoverlapping counterparts; in fact, the new estimators also perform particularly well against the benchmark batch means estimator. We illustrate our findings with analytical and Monte Carlo examples.

Automated Analysis of Simulation Output Data
Stewart Robinson (University of Warwick)

Abstract:
Appropriate analysis of simulation output is important to the success of a simulation study. Many users, however, do not have the skills required to perform such analyses. One way of overcoming this problem is to provide automated tools for analyzing simulation output. An Excel based automated “Analyser” is described that performs an analysis of a single scenario. The Analyser links to a commercial simulation software package, SIMUL8, and provides recommendations on warm-up, number of replications and run-length. Various standard procedures are used in the Analyser with some adaptations to make them suitable for automation. This research demonstrates the potential of the approach. A requirement for further development is more thorough testing of the analysis procedures, particularly for their robustness and generality in use. Further adaptation of the procedures for automation may also be required.

Exploring Exponentially Weighted Moving Average Control Charts to Determine the Warm-up Period
Manuel D. Rossetti and Zhe Li (University of Arkansas) and Peng Qu (Advanced Micro Devices)

Abstract:
In this paper, we examine the use of exponentially weighted moving average (EWMA) control charts for the detection of initialization bias in steady state simulation experiments. EWMA charts have the interesting property of being more sensitive to shifts in the data as compared to other control charting techniques. We exploit this sensitivity by developing a criteria for searching for the deletion point when the EWMA is applied to the reversed data sequence. This allows us to more easily detect and count the number of times the smoothed sequence remains in control. Our results indicate that the procedure can quickly find and recommend a deletion point. In addition, the properties of the resulting estimators are good if the dataset that is being analyzed does not have an overtly large amount of biased data points. We use experimental test cases to illustrate the properties of the procedure.

Performance Evaluation of ASAP3 for Steady-state Output Analysis
Natalie M. Steiger (University of Maine), Emily K. Lada (SAS Institute Inc.) and James R. Wilson (NC State University)

Abstract:
An experimental performance evaluation of ASAP3 is presented, including several queueing systems with characteristics typically encountered in practical applications of steady-state simulation analysis procedures. Based on the method of nonoverlapping batch means, ASAP3 is a sequential procedure designed to produce a confidence-interval estimator of a steady-state mean response that satisfies user-specified precision and coverage-probability requirements. ASAP3 is compared with its predecessor ASAP and the batch means procedure of Law and Carson (LC) in the following test problems: (a) queue waiting times in the M/M/1/LIFO, M/H_2/1, and M/M/1 queues with 80% server utilization; and (b) response (sojourn) times in a central server model of a computer system. Regarding conformance to the given precision and coverage-probability requirements, ASAP3 compared favorably with the ASAP and LC procedures. Regarding the average sample sizes needed to satisfy progressively more stringent precision requirements, ASAP3's efficiency was reasonable for the given test problems.

Analysis Methodology: Are We Done?
Enver Yücesan (INSEAD), Sigrún Andradóttir and David Goldsman (Georgia Institute of Technology), Bruce W. Schmeiser (Purdue University) and Lee W. Schruben (University of California, Berkeley)

Abstract:
Since 1967, the Winter Simulation Conference has been a forum for the introduction of innovative approaches to effectively analyze discrete-event simulation experiments. The goal of this panel is to bring together key contributors to analysis methodology research in order to clarify areas that they think are essentially complete, and identify areas that need more work. In doing so, we hope to help provide direction to younger researchers looking for the "right" problems to work on.

Two Simulated Annealing Algorithms for Noisy Objective Functions
Andrei A. Prudius and Sigrún Andradóttir (Georgia Institute of Technology)

Abstract:
We present two new variants of the simulated annealing algorithm (with a decreasing cooling schedule) that are designed for solving discrete simulation optimization problems. We also provide conditions under which our methods converge almost surely to the set of global optimal solutions, discuss the implications of our results for both transient and steady-state simulations, and provide some numerical results.

Discrete Optimization via Simulation Using Coordinate Search
L. Jeff Hong (The Hong Kong University of Science and Technology)

Abstract:
In this paper we propose a coordinate search algorithm to solve the optimization-via-simulation problems with integer-ordered decision variables. We show that the sequence of solutions generated by the algorithm converges to the set of local optimal solutions with probability 1 and the estimated optimal values satisfy a central limit theorem. We compare the coordinate search algorithm to the COMPASS algorithm proposed in Hong and Nelson (2004) through a set of numerical experiments. We see that the coordinate search has a better performance.

Stochastic Optimization Using Model Reference Adaptive Search
Jiaqiao Hu, Michael C. Fu, and Steven I. Marcus (University of Maryland)

Abstract:
We apply the recently introduced approach of model reference adaptive search to the setting of stochastic optimization and report on simulation results.

Subcontracting in a Make-to-stock Production System, IPA Gradients for a SFM
Sameh Al-Shihabi (University of Jordan)

Abstract:
This work extends the single product, single facility and single warehouse Make-to-Stock (MTS) model (Zhao and Melamed 2004), by allowing subcontracting. In addition to the inventory triggering level employed in their model, a new subcontracting triggering level is used to manage the subcontracted amount. A stochastic fluid model (SFM) is used to model the MTS system with subcontracting. In the current model, the subcontractor is assumed capable of satisfying any difference between the demand and the in-house production to keep the inventory at the subcontracting triggering level. The sensitivity of the inventory on-hand, backorders and amounts subcontracted with respect to the two employed triggering levels are found using infinitesimal perturbation analysis (IPA).

Performance of Variance Updating Ranking and Selection Procedures
Gwendolyn J. Malone (DRS Technologies) and Seong-Hee Kim, David Goldsman, and Demet Batur (Georgia Institute of Technology)

Abstract:
Kim and Nelson (2005) developed two indifference-zone procedures for steady-state simulation where the goal is to find the system with the largest or smallest expected steady-state performance measure. One of the procedures, called KN++, updates a variance estimate as more observations become available and is proven to be asymptotically valid when there is no dependence across systems (for example, there is no use of common random numbers). Their procedure exhibits significant improvement over other existing procedures for use in steady-state simulation. In this paper, we first present a modification of KN++ that is asymptotically valid with the use of common random numbers. Then, we study how well KN++ works when data within a system are independent and identically distributed, but data between systems may be positively correlated. Specific applications include the finding-the-best problem when (i) the data are normal, and (ii) the data are Bernoulli.

Multiobjective Simulation Optimization Using an Enhanced Genetic Algorithm
Hamidreza Eskandari, Luis Rabelo, and Mansooreh Mollaghasemi (University of Central Florida)

Abstract:
This paper presents an improved genetic algorithm approach, based on new ranking strategy, to conduct multi-objective optimization of simulation modeling problems. This approach integrates a simulation model with stochastic nondomination-based multiobjective optimization technique and genetic algorithms. New genetic operators are introduced to enhance the algorithm performance of finding Pareto optimal solutions and its efficiency in terms of computational effort. An elitism operator is employed to ensure the propagation of the Pareto optimal set, and a dynamic expansion operator to increase the population size. An importation operator is adapted to explore some new regions of the search space. Moreover, new concepts of stochastic and significant dominance are introduced to improve the definition of dominance in stochastic environments.