Abstract
We approach a class of discrete event simulation-based optimization problems using optimality in probability, an approach which yields what is termed a "champion solution". Compared to the traditional optimality in expectation, this approach favors the solution whose actual performance is more likely better than that of any other solution; this is an effective alternative to the traditional optimality sense, especially when facing a dynamic and nonstationary environment. Moreover, using optimality in probability is computationally promising for a class of discrete event simulation-based optimization problems, since it can reduce computational complexity by orders of magnitude compared to general simulation-based optimization methods using optimality in expectation. Accordingly, we have developed an "Omega Median Algorithm" in order to effectively obtain the champion solution and to fully utilize the efficiency of well-developed off-line algorithms to further facilitate timely decision making. An inventory control problem with nonstationary demand is included to illustrate and interpret the use of the Omega Median Algorithm, whose performance is tested using simulations.
Introduction: The Limits of Expectation
In Discrete Event Systems (DES), such as supply chains or manufacturing lines, decision-makers often face stochastic optimization problems. The goal is to find a decision $u$ that minimizes a cost function $J(u, \omega)$, where $\omega$ represents random noise or sample paths.
The traditional approach relies on Optimality in Expectation, seeking to minimize the average cost over many scenarios. While standard, this approach suffers from two significant drawbacks:
- Computational Complexity: Finding a near-optimal average requires simulating numerous scenarios ($M$) across a large set of candidate solutions ($I$), resulting in a complexity of $O(M \cdot I \cdot C)$. This often precludes real-time decision-making.
- The "Average" Trap: In nonstationary environments where conditions change rapidly, the long-term average may not reflect the best immediate action. A solution that is optimal on average might actually perform worse than an alternative in the majority of individual cases.
A New Paradigm: Optimality in Probability
To address these issues, this paper proposes Optimality in Probability. Instead of the average, we seek the Champion Solution ($u^c$)—the decision that has at least a 50% chance of outperforming any other feasible solution.
Consider a sports analogy: In a championship series, the "Champion" is the team that wins the most games (Optimality in Probability). As shown in the table above, Team A wins 4 out of 6 games despite Team B having a higher total (and thus average) score across the series. In many real-world scenarios, winning the "game" at hand is more critical than maintaining a high average over hypothetical infinite trials.
The Omega Median Algorithm (OMA)
The authors introduce the Omega Median Algorithm (OMA) as an efficient method to identify the Champion Solution. The algorithm transforms a complex stochastic problem into a series of simpler deterministic ones.
The OMA follows three elegant steps:
- Sample: Generate $M$ random sample paths (scenarios).
- Solve Deterministically: For each path, find the absolute best solution (the $\omega$-solution). This allows the use of highly optimized off-line deterministic algorithms.
- Find the Median: The estimate of the Champion Solution is the median of these individual $\omega$-solutions.
The theoretical foundation of OMA rests on the property of unimodality. If the cost function has a single clear minimum, the median of the optimal solutions for individual paths is mathematically guaranteed to be the Champion Solution. Furthermore, the OMA estimate converges to the true champion solution exponentially fast as the number of samples ($M$) increases.
Evaluation and Results
The OMA was tested using a simulated Inventory Control Problem involving setup costs, holding costs, and backlogging penalties. The study compared performance in both stationary (constant demand) and nonstationary (fluctuating demand) environments.
Key findings include:
- Computational Speedup: OMA reduces complexity from $O(M \cdot I \cdot N \log N)$ to $O(M \cdot N \log N)$ by eliminating the iterative search over the solution space.
- Superior Nonstationary Performance: In environments with shifting demand, the Champion Solution achieved a 14.52% lower average cost than standard heuristics.
- Robustness: Even in stationary environments where optimality in expectation is the standard, OMA remained highly competitive, coming within 1.03% of the theoretical optimum.
Conclusion and Limitations
Optimality in Probability offers a robust, computationally efficient alternative for stochastic optimization in dynamic environments. However, its application requires the objective function to be unimodal. Additionally, as suggested by Arrow’s Paradox, a clear "Champion" may not always exist if preferences are cyclical (e.g., A beats B, B beats C, but C beats A). Future work will focus on generalizing existence conditions and extending this logic to broader classes of stochastic problems.
Summary updated