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
In engineering and management, decision-makers often rely on Discrete-Event Systems (DES) simulations to compare various design alternatives, such as different factory layouts or inventory strategies. However, these simulations are frequently computationally expensive and time-consuming, creating a bottleneck in the decision-making process. The classic "Ranking and Selection" (R&S) problem addresses how to distribute a limited simulation budget to identify the best design.
Traditional R&S methods often treat each design as an isolated entity, ignoring the potential for information sharing between similar designs. Furthermore, many real-world scenarios require identifying a high-quality subset (the top-$m$ designs) rather than just a single winner, allowing for flexibility based on qualitative factors like environmental impact or political feasibility. This paper introduces a framework that exploits the underlying structure of the design space to efficiently identify this top-$m$ subset.
Methodology
The researchers propose two primary algorithms based on the Optimal Computing Budget Allocation (OCBA) framework, enhanced by regression metamodels:
1. OCBA-mr (Regression)
This algorithm assumes that the performance across the design space can be approximated by a quadratic curve. By simulating only a small number of "support designs," the model uses regression to estimate the performance of all other designs in the space. This significantly reduces the number of designs that must be directly simulated.
2. OCBA-mrp (Partitioned Regression)
Recognizing that global quadratic assumptions rarely hold in complex real-world landscapes, the authors introduced a partitioning strategy. The solution space is divided into adjacent partitions where a quadratic model can more accurately fit the local data. This allows the algorithm to handle highly non-linear or oscillatory functions by treating them as a series of simpler local problems.
Theoretical Framework: Large Deviation Theory
To determine the optimal allocation of simulation runs, the authors utilize Large Deviation Theory. This mathematical framework is used to calculate the convergence rate of the probability of making a selection error. By maximizing this rate, the authors derive an approximately optimal allocation rule that directs simulation efforts toward the designs most likely to impact the accuracy of the top-$m$ selection.
Experimental Evaluation
The effectiveness of OCBA-mr and OCBA-mrp was tested across six experimental setups, ranging from synthetic functions to practical applications:
- Synthetic Benchmarks: These included 1D quadratic functions, complex non-quadratic 1D functions (such as the oscillatory Griewank function), and 2D continuous functions.
- Real-World Application: An (s, S) Inventory Problem from the Simulation Optimization Library was used to represent a typical supply chain decision scenario.
Key Insights
- Information Sharing: The core innovation lies in the realization that simulating a design is not always necessary to understand its performance. If the performance of neighboring designs is known, regression can provide a reliable estimate, acting as a massive efficiency booster.
- The "Key Design" Focus: The probability of error in subset selection is typically dominated by the "key design"—the one most likely to be incorrectly swapped into or out of the top-$m$ set. The proposed allocation rule mathematically identifies and focuses budget on resolving this specific ambiguity.
- Minimal Support Requirements: For a quadratic model, only three support designs per partition are required to build a functional model, allowing the algorithm to bypass the majority of designs during the simulation phase.
Results and Discussion
The proposed algorithms were compared against standard benchmarks, including Equal Allocation (EA) and the original OCBAm+ algorithm.
In all experiments, OCBA-mr and OCBA-mrp achieved a high Probability of Correct Selection (PCS) significantly faster than traditional methods. In the inventory problem, the proposed method reached near-perfect accuracy while baseline methods struggled at 40-60% accuracy under the same budget constraints. While the global OCBA-mr model struggled with highly non-quadratic functions, the partitioned OCBA-mrp remained the top performer across all scenarios, demonstrating its robustness for complex landscapes.
Conclusion and Future Work
This research demonstrates that incorporating regression metamodels and spatial partitioning into the OCBA framework can drastically improve simulation efficiency for subset selection. Future research directions include the development of adaptive partitioning—where the algorithm determines how to split the space dynamically—and extending the framework to handle non-normal noise distributions or high-dimensional design spaces where simple quadratic models may no longer suffice.
Summary updated