More Like this

1. Revisiting Subset Selection

   Eckman, David J.; Plumlee, Matthew; Nelson, Barry L. (December 2021, Proceedings of the 2020 Winter Simulation Conference)

   Bae, K.-H.; Feng, B.; Kim, S.; Lazarova-Molnar, S.; Zheng, Z.; Roeder, T.; Thiesing, R. (Ed.)

   In the subset-selection approach to ranking and selection, a decision-maker seeks a subset of simulated systems that contains the best with high probability. We present a new, generalized framework for constructing these subsets and demonstrate that some existing subset-selection procedures are situated within this framework. The subsets are built by calculating, for each system, a minimum standardized discrepancy between the observed performances and the space of problem instances for which that system is the best. A system’s minimum standardized discrepancy is then compared to a cutoff to determine whether the system is included in the subset. We examine the problem of finding the tightest statistically valid cutoff for each system and draw connections between our approach and other subset-selection methodologies. Simulation experiments demonstrate how the screening power and subset size are affected by the choice of standardized discrepancy. 

   more » « less
2. Online Learning in Weakly Coupled Markov Decision Processes: A Convergence Time Study

   Wei, Xiaohan; Yu, Hao; Neely, Michael J. (January 2018, Proc. ACM Meas. Anal. Comput. Syst.)

   We consider multiple parallel Markov decision processes (MDPs) coupled by global constraints, where the time varying objective and constraint functions can only be observed after the decision is made. Special attention is given to how well the decision maker can perform in T slots, starting from any state, compared to the best feasible randomized stationary policy in hindsight. We develop a new distributed online algorithm where each MDP makes its own decision each slot after observing a multiplier computed from past information. While the scenario is significantly more challenging than the classical online learning context, the algorithm is shown to have a tight O( T ) regret and constraint viola- tions simultaneously. To obtain such a bound, we combine several new ingredients including ergodicity and mixing time bound in weakly coupled MDPs, a new regret analysis for online constrained optimization, a drift analysis for queue processes, and a perturbation analysis based on Farkas’ Lemma. 

   more » « less
3. A Classification Method for Ranking and Selection with Covariates

   https://doi.org/10.1109/WSC57314.2022.10015235  

   Keslin, Gregory; Nelson, Barry L.; Plumlee, Matthew; Pagnoncelli, Bernardo K.; Rahimian, Hamed (December 2022, Proceedings of the 2022 Winter Simulation Conference)

   Feng, B.; Pedrielli, G; Peng, Y.; Shashaani, S.; Song, E.; Corlu, C.; Lee, L.; Chew, E.; Roeder, T.; Lendermann, P. (Ed.)

   Ranking & selection (R&S) procedures are simulation-optimization algorithms for making one-time decisions among a finite set of alternative system designs or feasible solutions with a statistical assurance of a good selection. R&S with covariates (R&S+C) extends the paradigm to allow the optimal selection to depend on contextual information that is obtained just prior to the need for a decision. The dominant approach for solving such problems is to employ offline simulation to create metamodels that predict the performance of each system or feasible solution as a function of the covariate. This paper introduces a fundamentally different approach that solves individual R&S problems offline for various values of the covariate, and then treats the real-time decision as a classification problem: given the covariate information, which system is a good solution? Our approach exploits the availability of efficient R&S procedures, requires milder assumptions than the metamodeling paradigm to provide strong guarantees, and can be more efficient. 

   more » « less
4. Analysis of Evolved Response Thresholds for Decentralized Dynamic Task Allocation

   https://doi.org/10.1145/3530821  

   Mathias, H. David; Wu, Annie S.; Dang, Daniel (June 2022, ACM Transactions on Evolutionary Learning and Optimization)

   In this work, we investigate the application of a multi-objective genetic algorithm to the problem of task allocation in a self-organizing, decentralized, threshold-based swarm. We use a multi-objective genetic algorithm to evolve response thresholds for a simulated swarm engaged in dynamic task allocation problems: two-dimensional and three-dimensional collective tracking. We show that evolved thresholds not only outperform uniformly distributed thresholds and dynamic thresholds but achieve nearly optimal performance on a variety of tracking problem instances (target paths). More importantly, we demonstrate that thresholds evolved for some problem instances generalize to all other problem instances, eliminating the need to evolve new thresholds for each problem instance to be solved. We analyze the properties that allow these paths to serve as universal training instances and show that they are quite natural. After a priori evolution, the response thresholds in our system are static. The problem instances solved by the swarms are highly dynamic, with schedules of task demands that change over time with significant differences in rate and magnitude of change. That the swarm is able to achieve nearly optimal results refutes the common assumption that a swarm must be dynamic to perform well in a dynamic environment. 

   more » « less
5. Stochastic Constraints: How feasible is feasible?

   Eckman, David J; Henderson, Shane G; Shashaani, S (December 2023, ACM)

   Corlu, C G; Hunter, S R; Lam, H; Onggo, B S; Shortle, J; Biller, B (Ed.)

   Stochastic constraints, which constrain an expectation in the context of simulation optimization, can be hard to conceptualize and harder still to assess. As with a deterministic constraint, a solution is considered either feasible or infeasible with respect to a stochastic constraint. This perspective belies the subjective nature of stochastic constraints, which often arise when attempting to avoid alternative optimization formulations with multiple objectives or an aggregate objective with weights. Moreover, a solution’s feasibility with respect to a stochastic constraint cannot, in general, be ascertained based on only a finite number of simulation replications. We introduce different means of estimating how “close” the expected performance of a given solution is to being feasible with respect to one or more stochastic constraints. We explore how these metrics and their bootstrapped error estimates can be incorporated into plots showing a solver’s progress over time when solving a stochastically constrained problem. 

   more » « less