WSC 2006 Abstracts

On an Initial Transient Deletion Rule with Rigorous Theoretical Support
Hernan Awad (University of Miami) and Peter W. Glynn (Stanford University)

Abstract:
We study an initial transient deletion rule proposed by Glynn and Iglehart. We argue that it has desirable properties both from a theoretical and practical standpoint; we discuss its bias reducing properties, and its use both in the single replication setting and in the multiple replications / parallel processing context.

A New Approach for Parallel Steady-state Simulations
Ming-hua Hsieh (National Chengchi University, Taiwan)

Abstract:
We propose a new procedure for building confidence interval estimators of steady-state parameters in discrete event simulations. The procedure uses parallel processors to generate independent replications and constructs the confidence interval estimator by solving a generalized least square problem. The most appealing theoretical feature of the proposed procedure is that the precision of the resulted estimator can be improved by simply increasing the number of processors (or independent replications) while the simulated time length is fixed on an appropriate level on each processor. Experiments conducted on M/M/1 queue waiting time processes in heavy traffic confirm this theoretical property.

Performance Evaluation of Spectral Procedures for Simulation Analysis
Emily K. Lada (SAS Institute Inc.) and James R. Wilson (North Carolina State University)

Abstract:
We summarize an experimental performance evaluation of WASSP and the Heidelberger-Welch (HW) algorithm, two sequential spectral procedures for steady-state simulation analysis. Both procedures approximate the log-smoothed-periodogram of the batch means after suitable data-truncation to eliminate the effects of initialization bias, finally delivering a confidence-interval estimator for the mean response that satisfies user-specified half-length and coverage-probability requirements. HW uses a Cramer-von Mises test for initialization bias based on the method of standardized time series; and then HW fits a quadratic polynomial to the batch-means log-spectrum. In contrast WASSP uses the von Neumann randomness test and the Shapiro-Wilk normality test to obtain an approximately stationary Gaussian batch-means process whose log-spectrum is approximated via wavelets. Moreover, unlike HW, WASSP estimates the final sample size required to satisfy the user's confidence-interval requirements. Regarding closeness of conformance to both confidence-interval requirements, we found that WASSP outperformed HW in the given test problems.

On Choosing Parameters in Retrospective-Approximation Algorithms for Simulation-Optimization
Raghu Pasupathy (Virginia Tech)

Abstract:
The Simulation-Optimization (SO) problem is a constrained optimization problem where the objective function is observed with error, usually through an oracle such as a simulation. Retrospective Approximation (RA) is a general technique that can be used to solve SO problems. In RA, the solution to the SO problem is approached using solutions to a sequence of approximate problems, each of which is generated using a specified sample size and solved to a specified error tolerance. In this paper, our focus is parameter choice in RA algorithms, where the term parameter is broadly interpreted. Specifically, we present (i) conditions that guarantee convergence of estimated solutions to the true solution; (ii) convergence properties of the sample-size and error-tolerance sequences that ensure that the sequence of estimated solutions converge to the true solution in an optimal fashion; and (iii) a numerical procedure that efficiently solves the generated approximate problems for one-dimensional SO.

Optimal Resource Allocation in Two Stage Sampling of Input Distributions
Achal Bassamboo (Northwestern University) and Sandeep Juneja (Tata Institute of Fundamental Research)

Abstract:
Consider a performance measure that is evaluated via Monte Carlo simulation where input distributions to the underlying model may involve two stage sampling. The settings of interest include the case where in the first stage physical samples from the distribution are collected. In the second stage, Monte Carlo sampling is done from the observed empirical distribution. We also consider the sampling-importance resampling (SIR) algorithm. Here it is difficult to sample directly from the desired input distribution, and these samples are generated in two stages. In the first stage, a large number of samples are generated from a distribution convenient from the sampling viewpoint. In the second, a resampling is done from the samples generated in the first stage so that asymptotically the new samples have the desired distribution. We discuss how to allocate computational and other effort optimally among the two stages to minimize the estimator's resultant mean square error.

Ranking and Selection with Multiple “Targets”
Douglas Morrice (The University of Texas at Austin) and John Butler (The Ohio State University)

Abstract:
Managers of large industrial projects often measure performance by multiple attributes. In previous work, we developed a multiattribute ranking and selection procedure to allow tradeoffs between conflicting objectives. More recent developments in ranking and selection incorporate the notion of “constraints”, or “targets”, that must be satisfied. In this paper we demonstrate how some forms of single attribute utility functions can be used to create a target or constraint. We re-analyze our original problem under the assumption that there are unacceptable levels for some attributes.

Monitoring Variability of Autocorrelated Processes Using Standardized Time Series Variance Estimators
Seong-Hee Kim (Georgia Institute of Technology)

Abstract:
We consider the problem of monitoring variability of autocorrelated processes. This paper combines variance estimation techniques from the simulation literature with a statistical process control chart from statistical process control (SPC) literature. The proposed SPC method does not require any assumptions on the distribution of the underlying process and uses a variance estimate from each batch as a basic observation. The control limits of the chart are determined analytically. The proposed chart is tested using stationary processes with both normal and non-normal marginals.

A Comparison of Sample-Path-Based Simulation-Optimization and Stochastic Decomposition for Multi-Location Transshipment Problems
Lei Zhao (Tsinghua University) and Suvrajeet Sen (University of Arizona)

Abstract:
Because of its applicability, as well as its generality, research in the area of simulation-optimization continues to attract significant attention. These methods, most of which rely on the statistically motivated search techniques, are at their best when very little is known about the structure of the function (e.g., function evaluations are treated as "black-box" function-calls). In some applications such as the one discussed in this paper, objective function values may be obtained through linear/network flow optimization models. In such cases, the objective function may be convex, and in such circumstances, very large instances can be solved using stochastic programming techniques. This paper presents a computational case for using such techniques, whenever applicable.

Computing Worst-Case Tail Probabilities in Credit Risk
Soumyadip Ghosh (IBM TJ Watson Research Center) and Sandeep Juneja (Tata Institute of Fundamental Research)

Abstract:
Simulation is widely used to measure credit risk in portfolios of loans, bonds, and other instruments subject to possible default. This analysis requires performing the difficult modeling task of capturing the dependence between obligors adequately. Current methods assume a form for the joint distribution of the obligors and match its parameters to given dependence specifications, usually correlations. The value-at-risk risk measure (a function of its tail quantiles) is then evaluated. This procedure is naturally limited by the form assumed, and might not approximate well the "worst-case" possible over all joint distributions that match the given specification. We propose a procedure that approximates the joint distribution with chessboard distributions, and provides a sequence of improving estimates that asymptotically approach this "worst-case" value-at-risk. We use it to experimentally compare the quality of the estimates provided by the earlier procedures.

A Testbed of Simulation-Optimization Problems
Raghu Pasupathy (Virginia Tech) and Shane G Henderson (Cornell University)

Abstract:
We propose a testbed of simulation-optimization problems. The purpose of the testbed is to encourage development and constructive comparison of simulation-optimization techniques and algorithms. We are particularly interested in increasing attention to the finite-time performance of algorithms, rather than the asymptotic results that one often finds in the literature.

Simulation-based Response Surface Computation in the Presense of Monotonicity
Eunji Lim and Peter W Glynn (Stanford University)

Abstract:
In many stochastic models, it is known that the response surface corresponding to a particular performance measure is monotone in the underlying parameter. For example, the steady-state mean waiting time for customers in a single server queue is known to be monotone in the service rate. In other contexts, the simulator may believe, on the basis of intuition, that the response surface is monotone. This paper describes an appropriate methodology for incorporating such monotonicity constraints into one's response surface estimator.

Response Gradient Estimation Using Mathematical Programming Models of Discrete-Event System Sample Paths
Wai Kin (Victor) Chan (Rensselaer Polytechnic Institute) and Lee W. Schruben (University of California, Berkeley)

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.

Simulation Selection Problems: Overview of an Economic Analysis
Stephen E. Chick (INSEAD) and Noah Gans (OPIM Department - Wharton School)

Abstract:
This paper summarizes a new approach that we recently proposed for ranking and selection problems, one that maximizes the expected NPV of decisions made when using stochastic or discrete-event simulation. The expected NPV models not only the economic benefit from implementing a selected system, but also the marginal costs of simulation runs and discounting due to simulation analysis time. Our formulation assumes that facilities exist to simulate a fixed number of alternative systems, and we pose the problem as a "stoppable" Bayesian bandit problem. Under relatively general conditions, a Gittins index can be used to indicate which system to simulate or implement. We give an asymptotic approximation for the index that is appropriate when simulation outputs are normally distributed with known but potentially different variances for the different systems.

Selection and Multiple-Comparison Procedures for Regenerative Systems
Marvin K Nakayama (New Jersey Institute of Technology)

Abstract:
We propose two-stage methods for selection and multiple comparisons with the best (MCB) of steady-state performance measures of regenerative systems. We assume the systems being compared are simulated independently, and the methods presented are asymptotically valid as the confidence-interval width parameter shrinks and the first-stage run length grows at a rate that is at most the inverse of the square of the confidence-interval width parameter. When the first-stage run length is asymptotically negligible compared to the total run length, our procedures are asymptotically efficient. We provide an asymptotic comparison of our regenerative MCB procedures with those based on standardized time series (STS) methods in terms of mean and variance of total run length. We conclude that regenerative MCB methods are strictly better than STS MCB methods for any fixed number of batches, but the two become equivalent as the number of batches grows large.

Integration of Statistical Selection with Search Mechanism for Solving Multi-Objective Simulation-Optimization Problems
Loo Hay Lee, Ek Peng Chew, and Suyan Teng (National University of Singapore)

Abstract:
In this paper, we consider a multi-objective simulation optimization problem with three features: huge solution space, high uncertainty in performance measures, and multi-objective problem which requires a set of non-dominated solutions. Our main purpose is to study how to integrate statistical selection with search mechanism to address the above difficulties, and to present a general solution framework for solving such problems. Here due to the multi-objective nature, statistical selection is done by the multi-objective computing budget allocation (MOCBA) procedure. For illustration, MOCBA is integrated with two meta-heuristics: multi-objective evolutionary algorithm (MOEA) and nested partitions (NP) to identify the non-dominated solutions for two inventory management case study problems. Results show that, the integrated solution framework has improved both search efficiency and simulation efficiency. Moreover, it is capable of identifying a set of non-dominated solutions with high confidence.

On-Line Instrumentation for Simulation-Based Optimization
Anna Persson, Henrik Grimm, and Amos Ng (Centre for Intelligent Automation)

Abstract:
Traditionally, a simulation-based optimization (SO) system is designed as a black-box in which the internal details of the optimization process is hidden from the user and only the final optimization solutions are presented. As the complexity of the SO systems and the optimization problems to be solved increases, instrumentation – a technique for monitoring and controlling the SO processes – is becoming more important. This paper proposes a white-box approach by advocating the use of instrumentation components in SO systems, based on a component-based architecture. This paper argues that a number of advantages, including efficiency enhancement, gaining insight from the optimization trajectories and higher controllability of the SO processes, can be brought out by an on-line instrumentation approach. This argument is supported by the illustration of an instrumentation component developed for a SO system designed for solving real-world multi-objective operation scheduling problems.

Adaptation of the UOBYQA Algorithm for Noisy Functions
Geng Deng and Michael C. Ferris (University of Wisconsin-Madison)

Abstract:
In many real-world optimization problems, the objective function may come from a simulation evaluation so that it is (a) subject to various levels of noise, (b) not differentiable, and (c) computationally hard to evaluate. In this paper, we modify Powell's UOBYQA algorithm to handle those real-world simulation problems. Our modifications apply Bayesian techniques to guide appropriate sampling strategies to estimate the objective function. We aim to make the underlying UOBYQA algorithm proceed efficiently while simultaneously controlling the amount of computational effort.

SPSA Algorithms with Measurement Reuse
Mohammed Shahid Abdulla (Indian Institute of Science) and Shalabh Bhatnagar (Indian Insitute of Science)

Abstract:
Four algorithms, all variants of Simultaneous Perturbation Stochastic Approximation (SPSA), are proposed. The original one-measurement SPSA uses an estimate of the gradient of objective function L containing an additional bias term not seen in two-measurement SPSA. As a result, the asymptotic covariance matrix of the iterate convergence process has a bias term. We propose a one-measurement algorithm that eliminates this bias, and has asymptotic convergence properties making for easier comparison with the two-measurement SPSA. The algorithm, under certain conditions, outperforms both forms of SPSA with the only overhead being the storage of a single measurement. We also propose a similar algorithm that uses perturbations obtained from normalized Hadamard matrices. The convergence w.p. 1 of both algorithms is established. We extend measurement reuse to design two second-order SPSA algorithms and sketch the convergence analysis. Finally, we present simulation results on an illustrative minimization problem.

Experimental Evaluation of Integrated Path Estimators
James Michael Calvin (New Jersey Institute of Technology)

Abstract:
We describe the results of numerical experiments evaluating the efficiency of variance estimators based on integrated sample paths. The idea behind the estimators is to compute a vector of integrated paths and combine them to form an estimator of the time-average variance constant that is used, for example, in the construction of confidence intervals. When used in conjunction with batching, the approach generalizes the method of non-overlapping batch means. Compared with non-overlapping batch means, the estimators require longer to compute, have smaller variance and larger bias. We show that for long enough simulation run lengths, the efficiency (the reciprocal of running time multiplied by mean-squared error) of integrated path estimators can be much greater than that of non-overlapping batch means; the numerical experiments show an efficiency improvement by up to a factor of ten.

Empirical Evaluation of Data-based Density Estimation
E Jack Chen (BASF Corporation) and W David Kelton (University of Cincinnati)

Abstract:
This paper discusses implementation of a sequential procedure to estimate the steady-state density of a stochastic process. The procedure computes sample densities at certain points and uses Lagrange interpolation to estimate the density f(x). Even though the proposed sequential procedure is a heuristic, it does have strong basis. Our empirical results show that the procedure gives density estimates that satisfy a pre-specified precision requirement. An experimental performance evaluation demonstrates the validity of using the procedure to estimate densities.

Generating Multivariate Mixture of Normal Distributions Using A Modified Cholesky Decomposition
Jin Wang and Chunlei Liu (Valdosta State University)

Abstract:
Mixture of normals is a more general and flexible distribution for modeling of daily changes in market variables with fat tails and skewness. An efficient analytical Monte Carlo method was proposed by Wang and Taaffe for generating daily changes using a multivariate mixture of normal distributions with arbitrary covariance matrix. However the usual Cholesky Decomposition will fail if the covariance matrix is not positive definite. In practice, the covariance matrix is unknown and has to be estimated. The estimated covariance may be not positive definite. We propose a modified Cholesky decomposition for semi-definite matrices and also suggest an optimal semi-definite approximation for indefinite matrices.

Combined Ranking and Selection with Control Variates
Shing Chih Tsai and Barry L Nelson (Northwestern University)

Abstract:
Nelson and Staum derived R&S procedures that employ control-variate estimators (CVs) instead of sample means to obtain more statistical efficiency. However, control-variate estimators require more computational effort than sample means, and effective controls must be identified. We present a new CV screening procedure to avoid much of the computation cost. We also present a two-stage CV combined procedure which captures the ability to eliminate inferior systems in the first stage and the statistical efficiency of control variates for selection in the second stage. An empirical evaluation is provided.

Comparison of Limit Standards Using a Sequential Probability Ratio Test
Roy R Creasey Jr (Longwood University) and K. Preston White (University of Virginia)

Abstract:
We continue our research into the comparison, via simulation experiments, of a stochastic system to a limit standard. A limit standard is defined as a maximum and/or minimum standard. We have found that evaluation methods using proportions provide a statistically valid comparison of this family of standards. In this paper, we present the use of Wald's sequential probability ratio test (SPRT) as a comparison method. We define a fully sequential analysis procedure, as well as initial test results.

Performance Evaluations of Comparison-with-a-standard Procedures
E Jack Chen (BASF Corporation)

Abstract:
We investigate the performance of a heuristic sequential procedure to compare a finite number of designs with respect to a single standard. The goal is to identify the best design, and if the chosen best design is not the standard, to determine whether the chosen best design is better than the standard. We give preferential status to the standard because there are costs and time involved in replacing the standard. We accomplish this goal by extending indifference-zone selection procedures. An experimental performance evaluation demonstrates the validity and efficiency of our sequential procedures.

A Polytope Method for Estimating Factor Main Effects
Bruce Ankenman (Northwestern University) and Russell Cheng and Susan Lewis (University of Southampton)

Abstract:
Consider the problem of identifying important factors influencing a response in a simulation experiment where the number of factors is large. When the direction of the effect of factors is known, the method of sequential bifurcation is effective for quickly removing noninfluential factors. Though good, the method is not fully efficient in that not all the information available is fully utilized. We present a method based on a polytope construction that makes use of all available information and which is therefore more efficient. In this paper we focus on the deterministic case to highlight its theoretical foundation. The method can however be extended to the stochastic case. Numerical examples are given comparing the new method with sequential bifurcation showing its improved performance.

A Two-Phase Maxi-Min Algorithm for Forward-Inverse Experiment Design
Russell R. Barton (The Pennsylvania State University)

Abstract:
In customer-driven design of systems or products, one has performance targets in mind and would like to identify system design parameters that yield the target performance vector. Since most simulation models predict performance given design parameter values, this identification must be done iteratively through an optimization search procedure. In some cases it would be preferable to find design parameter values directly via an explicit inverse model. Regression and other forms of approximation 'metamodels' provide estimates of simulation model outputs as a function of design parameters. It is possible to design fitting experiments (DOE’s) that allow simultaneous fitting of both forward and inverse metamodels. This paper discusses the potential for this strategy and shows a simple two-phase DOE strategy using a maxi-min measure of DOE quality.

A Hybrid Method for Simulation Factor Screening
Hua Shen and Hong Wan (Purdue University)

Abstract:
Factor screening is performed to eliminate unimportant factors so that the remaining important factors can be more thoroughly studied in later experiments. Controlled Sequential Bifurcation (CSB) and Controlled Sequential Factorial Design (CSFD) are two new screening methods for discrete-event simulations. Both methods use hypothesis testing procedures to control the Type I Error and power of the screening results. The scenarios at which each method is most efficient are complementary. This paper proposes a two-stage hybrid approach to combine CSB and CSFD. The new method usually has the same error control as CSB and CSFD. The efficiency, on the other hand, is usually much better than either component method.