Efficient simulation budget allocation for subset selection using regression metamodels☆

Abstract

This research considers the ranking and selection (R&S) problem of selecting the optimal subset from a finite set of alternative designs. Given the total simulation budget constraint, we aim to maximize the probability of correctly selecting the top- m designs. In order to improve the selection efficiency, we incorporate the information from across the domain into regression metamodels. In this research, we assume that the mean performance of each design is approximately quadratic. To achieve a better fit of this model, we divide the solution space into adjacent partitions such that the quadratic assumption can be satisfied within each partition. Using the large deviation theory, we propose an approximately optimal simulation budget allocation rule in the presence of partitioned domains. Numerical experiments demonstrate that our approach can enhance the simulation efficiency significantly.

Introduction

Discrete-event systems (DES) simulation has played an important role in analyzing modern complex systems and evaluating decision problems, since these systems are usually too difficult to be described using analytical models. DES simulation has been a common analysis method of choice and widely used in many practical applications, such as the queueing systems, electric power grids, air and land traffic control systems, manufacturing plants and supply chains (Gao and Chen, 2016, Xu et al., 2015, Xu et al., 2016). However, running the simulation model is usually time consuming, and a large number of simulation replications are typically required to achieve an accurate estimate of a design decision (Lee et al., 2010). In addition, it could be computationally quite expensive to select the best design(s) when the number of alternatives is relatively large.

In this paper, we consider the problem of selecting the optimal subset of the top- m designs out of t alternatives, where the performance of each design is estimated based on simulation. In order to improve the selection efficiency, we aim to intelligently allocate the simulation replications to each design to maximize the probability of correctly selecting all the top- m designs. This problem setting falls in the well-established statistics branch known as ranking and selection (R&S) (Xu et al., 2015).

In the literature, several types of efficient R&S procedures have been developed. The indifference-zone (IZ) approach allocates the simulation budget to provide a guaranteed lower bound for the probability of correct selection ( P C S ) (Kim & Nelson, 2001). Chen, Lin, Yücesan, and Chick (2000) proposed an optimal computing budget allocation (OCBA) approach for R&S problems. The OCBA approach allocates the simulation replications sequentially in order to maximize P C S under a simulation budget constraint. Gao, Chen, and Shi (2017a), Gao and Shi (2015) and He, Chick, and Chen (2007) further developed the OCBA method with the expected opportunity cost ( E O C ) measure, which focuses more on the consequence of a wrong selection compared to P C S . Brantley, Lee, Chen, and Chen (2013) proposed another approach called optimal simulation design (OSD) to select the best design with regression metamodels. It assumes that all designs fit a single quadratic line and the variance of each design is identically distributed. The OSD approach was further extended in Brantley, Lee, Chen, and Xu (2014), Gao, Gao, Xiao, and Shi (2018) and Xiao, Lee, and Chen (2015) to consider more general problems by dividing the solution space into adjacent partitions. Although these studies are also based on partitioning or metamodeling, they do not aim to select the top m designs, and are therefore different in objectives from this research. Other variants of OCBA include selecting the best design considering resource sharing and allocation (Peng, Chen, Fu, & Hu, 2013) and input uncertainty (Gao, Xiao, Zhou, & Chen, 2017b).

Most of the existing R&S procedures focus on identifying the best design and return a single choice as the estimated optimum. However, decision makers may prefer to have several good alternatives instead of one and make the final selection by considering some qualitative criteria, such as political feasibility and environmental consideration, which might be neglected by computer models (Gao and Chen, 2016, Zhang et al., 2016). The selection procedure providing the top- m designs can help the decision makers make their final decision in a more flexible way.

The literature on the optimal subset selection is sparse. Chen, He, Fu, and Lee (2008) and Zhang et al. (2016) considered the optimal subset selection problem using the OCBA framework, which maximizes P C S under a simulation budget constraint. In Gao and Chen (2015), an optimal subset selection procedure was proposed to minimize the measure of E O C . The optimal subset selection problem was further extended in Gao and Chen (2016) for general underlying distributions using the large deviations theory.

The aforementioned R&S procedures could smartly allocate the computing budget given the simulation results. They estimate the performance of each design only by considering the sample information of the considered design itself. However, the designs nearby could also provide useful information since neighboring designs usually have similar performance. Based on this idea, we aim to improve the selection efficiency by incorporating the information from across the domain into some response surfaces. Unlike traditional R&S methods, the regression based approaches require simulation experiments on only a subset of all the designs under consideration. The performances of the other designs can be inferred based on the sample information of the simulated designs. This provides us an effective way to further improve the efficiency for solving the subset selection problem, which is the motivation of this paper.

In this research, we assume the underlying function isquadratic or approximately quadratic. This assumption could help utilize the structure information of the design space and led to significant improvement of the computational efficiency. It is commonly used in the literature, such as Brantley et al., 2013, Brantley et al., 2014, McConnell and Servaes (1990) and Xiao et al. (2015). Based on this assumption we built a quadratic regression metamodel to incorporate the information from across the domain. The first contribution of this work is that we propose an asymptotically optimal allocation rule that determines which designs need to be simulated and the number of simulation budget allocated to them, such that the P C S of the optimal subset could be maximized. We call this procedure the optimal computing budget allocation for selecting the top- m designs with regression (OCBA-mr). In order to further extend the OCBA-mr procedure to more general cases where the underlying function is partially quadratic or non-quadratic, we divide the solution space into adjacent partitions and build a quadratic regression metamodel within each partition. The underlying function in each partition could be well approximated by a quadratic function if the solution space is properly partitioned or each partition is small enough. According to the results in Brantley et al. (2014), Gao et al. (2018) and Xiao et al. (2015), the use of partitioned domains along with regression metamodels could significantly improve the simulation efficiency. That means interpolating the solution space can be an effective way for us to have further improvement. For different problems, the solution space could be divided into discrete partitions using different criteria, such as the size of corporations, the type of industries and the temperature of chemical process (Xiao et al., 2015). Based on the idea mentioned above, we develop an asymptotically optimal computing budget allocation procedure for selecting the top- m designs with regression in partitioned domains (OCBA-mrp), which is an extension of the OCBA-mr procedure for more general cases. In order to maximize the P C S of the optimal subset, the OCBA-mrp procedure not only determines the optimal simulation budget allocation within each partition but also determines the optimal budget allocation between partitions.

The rest of the paper is organized as follows. In Section 2, we formulate the optimal subset selection problem with regression metamodel and derive an asymptotically optimal simulation budget allocation rule, called OCBA-mr. Section 3 extends the OCBA-mr method for more general cases with partitioned domains and derives another asymptotically optimal simulation budget allocation rule, called OCBA-mrp. The performance of the proposed methods is illustrated with numerical examples in Section 4. Section 5 concludes the paper. The proof of the theorems in this paper can be found in the online supplement (available at https://arxiv.org/abs/1904.10639).

Section snippets

Optimal subset selection strategy

In this section, we provide an optimal computing budget allocation rule for the subset selection problem based on the regression metamodel.

Optimal subset selection strategy for partitioned domains

The regression based method mentioned above can greatly improve the subset selection efficiency compared to the traditional methods. However, it is constrained with the typical assumptions such as the assumption of quadratic underlying function for the means. It is possible that the underlying function is neither quadratic nor approximately quadratic, so that we will fail to find the top- m designs. In order to extend our method to more general cases, we divide the solution space into adjacent

Sequential budget allocation algorithm

Based on the discussion above, we propose two sequential budget allocation algorithm to implement the optimality conditions. They are Optimal Computing Budget Allocation for selecting the top- m designs with regression (OCBA-mr) based on Theorem 1, Theorem 2 and Optimal Computing Budget Allocation for selecting the top- m designs with regression in partitioned domains (OCBA-mrp) based on Theorem 4, Theorem 5.

(1) OCBA-mr Algorithm

INITIALIZE: κ ← 0 ; Perform n 0 simulation replications for three design

Numerical experiments

In this section, we test our proposed simulation budget allocation rules, OCBA-mr and OCBA-mrp, with some existing methods on several typical optimal subset selection problems. We use the following three budget allocation approaches for comparison. The top- m designs are selected based on their mean values.

•

Equal Allocation (EA): The EA is the most commonly used and simplest method, which allocates the simulation budget equally to each of the design.

•

OCBAm + Allocation: The OCBAm + is an efficient

Conclusions

In this study, we further enhanced the simulation efficiency of finding the top- m designs by incorporating quadratic regression equation(s). Using the large deviations theory, we formulate the problem of selecting the top- m designs as that of maximizing the minimum convergence rate of the false selection probability. We derived two asymptotically optimal budget allocation rules, OCBA-mr and OCBA-mrp, for one partition and multi-partition problem setting, respectively. Numerical results suggest

Fei Gao received the B.S. and M.S. degrees from Tianjin University, Tianjin, China, in 2012 and 2015, and the Ph.D. degree in systems engineering and engineering management from City University of Hong Kong, Hong Kong, China, in 2018. He is currently an Operations Research Engineer with Network Planning Department, SF Technology, Shenzhen, China. His research is devoted to simulation optimization, large-scale optimization, and their applications in healthcare management.

Cited by (3)

Fei Gao received the B.S. and M.S. degrees from Tianjin University, Tianjin, China, in 2012 and 2015, and the Ph.D. degree in systems engineering and engineering management from City University of Hong Kong, Hong Kong, China, in 2018. He is currently an Operations Research Engineer with Network Planning Department, SF Technology, Shenzhen, China. His research is devoted to simulation optimization, large-scale optimization, and their applications in healthcare management.

Zhongshun Shi is an Assistant Professor in the Department of Industrial and Systems Engineering at the University of Tennessee-Knoxville. Prior to joining UTK in 2019, he was a research associate in the Department of Industrial and Systems Engineering at the University of Wisconsin-Madison from 2017 to 2019. He received the B.S. degree in Applied Mathematics from China University of Geosciences, Beijing, in 2011, and the Ph.D. degree in Management Science and Engineering from Peking University, China, in 2016. His research interests include smart manufacturing, complex system optimization, large-scale optimization, approximation algorithm design and supply chain management.

Siyang Gao received the B.S. degree in Mathematics from Peking University, Beijing, China, in 2009, and the Ph.D. degree in Industrial Engineering from University of Wisconsin-Madison, Madison, WI, in 2014. Dr. Gao is an Assistant Professor with the Department of Systems Engineering and Engineering Management, City University of Hong Kong. His research is devoted to simulation optimization, large-scale optimization and their applications in healthcare management. His work has appeared in Operations Research, IEEE Transactions on Automatic Control, Automatica, etc. Dr. Gao is a member of the Institute for Operations Research and the Management Sciences (INFORMS) and Institute of Electrical and Electronics Engineers (IEEE).

Hui Xiao received the Ph.D. degree from National University of Singapore. He is currently an Associate Professor with the Department of Management Science and Engineering, Southwestern university of Finance and Economics, Chengdu, China. His research is devoted to simulation optimization, large-scale optimization and reliability modeling and optimization. His work has appeared in IEEE Transactions on Systems, Man, and Cybernetics: Systems, IEEE Transactions on Automation Science and Engineering, Reliability Engineering & System Safety, etc. He is a member of Institute of Electrical and Electronics Engineers (IEEE).

View full text

© 2019 Elsevier Ltd. All rights reserved.