Quantile-Based Simulation Optimization With Inequality Constraints: Methodology and Applications

• Published in: IEEE transactions on automation science and engineering 2016-04, Vol.13 (2), p.701-708
• Main Authors: Chang, Kuo-Hao, Lu, Hou-Kuen
• Format: Article
• Language: English
• Subjects: Analytical models; Automation; Convergence; Direct search method; Estimating techniques; Linear programming; Mathematical model; Noise; Optimization; Optimization techniques; quantile; Simplex method; Simulation; simulation optimization; Stochastic models; stochastic Nelder-Mead simplex method; Stochastic processes
• ISSN: 1545-5955; 1558-3783
• DOI: 10.1109/TASE.2015.2406736

Many automation or manufacturing systems are too complex to be modeled by analytical approaches and can only resort to fast-running simulation. Stochastic Nelder-Mead simplex method (SNM) is a newly developed methodology for simulation optimization with expected-value-based objective functions. Quantile, as an important alternative to the usual expected value, provides additional information about the distribution of system performance. In particular, it is useful in describing the tail behavior of the distribution. In this paper, we exploit the structure of SNM and extend it to solve simulation optimization problems with quantile-based objective functions and inequality constraints. The proposed method, called SNM-QC, utilizes the same search strategy as SNM but further incorporates effective quantile estimation techniques and penalty function approaches to solve the problem. We prove that SNM-QC has the desirable global convergence guarantee, i.e., the algorithm is guaranteed to converge to the true optima with probability one. One advantage of SNM-QC is that it is a direct search method that determines the moving direction simply by comparing a set of solutions rather than estimating gradient, thus it can handle many practical problems where gradient does not exist or is difficult to estimate. An extensive numerical study shows that the performance of SNM-QC is promising compared to the existing heuristics. Two illustrative applications are provided in the end to demonstrate the viability of SNM-QC in practical settings. This paper proposes a direct search method, called SNM-QC, for solving quantile-based simulation optimization problems with inequality constraints. Compared to traditional methods that are largely focused on expected-value-based objective functions, SNM-QC complements the existing literature in simulation optimization. In particular, by adjusting the value in the quantile-based simulation optimization formulation, SNM-QC allows for more flexibility when seeking the optimal solution associated with the problem. The advantages of SNM-QC are that it is easy to implement and moreover, it does not require gradient estimation in the search process. In practice, SNM-QC can be applied, for example, to determine the staffing level in an emergency room of a hospital so as to maximize the service quality of an out-of-hospital system measured by the 90th percentile of the times taken to respond to emergency requests, subject to budget constraints.