Publication Date

2013-04-20

Availability

Embargoed

Embargo Period

2015-04-20

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PHD)

Department

Industrial Engineering (Engineering)

Date of Defense

2013-04-03

First Committee Member

Eunji Lim

Second Committee Member

Shihab S. Asfour

Third Committee Member

Murat Erkoc

Fourth Committee Member

Nurcin Celik

Fifth Committee Member

Edward Baker

Abstract

The first part of this dissertation studies a constrained simulation-based optimization problem over a discrete set where noise-corrupted observations of the objective and constraints are available. The problem is challenging because the feasibility of a solution cannot be known for certain. The uncertainty, in turn, arises from the noisy measurements of the constraints. To tackle this issue, we propose an innovative method that converts constrained optimization into the unconstrained optimization problem of finding a saddle point of the Lagrangian. The method applies stochastic approximation to the Lagrangian in search of the saddle point. We prove that the proposed method converges to the optimal solution almost surely (a.s.) under suitable conditions as the number of iterations grows. We present the effectiveness of the proposed method numerically in four examples, with applications in inventory control, call center staffing and emergency room management. The second part of this dissertation discusses the problem of fitting a convex function based on noisy data from simulation output. The traditional way of fitting a convex function to data, which is done by computing a convex function minimizing the sum of least squares, takes too long to compute the fit. It also runs into an “out of memory” issue when the number of data points exceeds a few hundred. In this dissertation, we propose a computationally efficient way by minimizing the sum of least absolute deviations rather than the sum of squares. The least absolute deviations estimator we introduce in this dissertation is posed via a solution to a linear program (LP) while the traditional least squares estimator is posed via a solution to a quadratic program (QP). Furthermore, our LP formulation has a dual problem that exhibits a block-angular form in its constraints. This enables one to apply decomposition techniques such as Dantzig-Wolfe decomposition to solve the dual problem. Thus the proposed estimator can be computed faster and for larger datasets than the least squares estimator. We present numerical examples to illustrate the relative performance of the proposed estimator compared to that of the least squares estimator. We also establish the consistency of the proposed estimator and its derivative by proving that, under modest assumptions, the estimator and its derivative converge almost surely (a.s.) to the true values as the number of data points increases to infinity. The third part of this dissertation concerns the initial transient problems when running discrete-event simulation in our simulation-based optimization framework. When using a discrete event simulation to estimate some steady-state variables we are aiming to optimize, we deduce that it is desirable to initialize the simulation according to steady-state distribution because the initial transient phase will be induced otherwise. However, due to the lack of information on steady-state distribution, practitioners usually start the simulation in some arbitrary fashion, which results in an initial transient phase prior to steady-state. In this paper, we provide a methodology to determine the length of the initial transient phase of (possibly multi-dimensional) simulation output. Such an elaborated method can be further used to devise an algorithm to compute better estimators for steady-state performance measures by utilizing simulation output after the initial transient phase. The proposed methodology is based on a simple idea of dividing simulation output into several batches, observing the way the observations are distributed in each batch, and trying to find a change in these distributions. The efficiency of the proposed methodology is illustrated through numerical experiments.

Keywords

simulation-based optimization; discrete optimization; Lagrangian duality; convex regression; least absolute deviation

Download

Share

COinS