More Like this

1. Posterior-Based Stopping Rules for Bayesian Ranking-and-Selection Procedures

   https://doi.org/10.1287/ijoc.2021.1132  

   Eckman, David J.; Henderson, Shane G. (May 2022, INFORMS Journal on Computing)

   Sequential ranking-and-selection procedures deliver Bayesian guarantees by repeatedly computing a posterior quantity of interest—for example, the posterior probability of good selection or the posterior expected opportunity cost—and terminating when this quantity crosses some threshold. Computing these posterior quantities entails nontrivial numerical computation. Thus, rather than exactly check such posterior-based stopping rules, it is common practice to use cheaply computable bounds on the posterior quantity of interest, for example, those based on Bonferroni’s or Slepian’s inequalities. The result is a conservative procedure that samples more simulation replications than are necessary. We explore how the time spent simulating these additional replications might be better spent computing the posterior quantity of interest via numerical integration, with the potential for terminating the procedure sooner. To this end, we develop several methods for improving the computational efficiency of exactly checking the stopping rules. Simulation experiments demonstrate that the proposed methods can, in some instances, significantly reduce a procedure’s total sample size. We further show these savings can be attained with little added computational effort by making effective use of a Monte Carlo estimate of the posterior quantity of interest. Summary of Contribution: The widespread use of commercial simulation software in industry has made ranking-and-selection (R&S) algorithms an accessible simulation-optimization tool for operations research practitioners. This paper addresses computational aspects of R&S procedures delivering finite-time Bayesian statistical guarantees, primarily the decision of when to terminate sampling. Checking stopping rules entails computing or approximating posterior quantities of interest perceived as being computationally intensive to evaluate. The main results of this paper show that these quantities can be efficiently computed via numerical integration and can yield substantial savings in sampling relative to the prevailing approach of using conservative bounds. In addition to enhancing the performance of Bayesian R&S procedures, the results have the potential to advance other research in this space, including the development of more efficient allocation rules. 

   more » « less
2. Let’s Do Ranking & Selection

   Nelson, Barry L. (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.)

   Many tutorials and survey papers have been written on ranking & selection because it is such a useful tool for simulation optimization when the number of feasible solutions or “systems” is small enough that all of them can be simulated. Cheap, ubiquitous, parallel computing has greatly increased the “all of them can be simulated” limit. Naturally these tutorials and surveys have focused on the underlying theory of R&S and have provided pseudocode procedures. This tutorial, by contrast, emphasizes applications, programming and interpretation of R&S, using the R programming language for illustration. Readers (and the audience) can download the code and follow along with the examples, but no experience with R is needed. 

   more » « less
3. Let's Do Ranking & Selection

   Nelson, Barry L (December 2022, Proceedings of the 2023 Winter Simulation Conference)

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

   Many tutorials and survey papers have been written on ranking & selection because it is such a useful tool for simulation optimization when the number of feasible solutions or “systems” is small enough that all of them can be simulated. Cheap, ubiquitous, parallel computing has greatly increased the “all of them can be simulated” limit. Naturally these tutorials and surveys have focused on the underlying theory of R&S and have provided pseudocode procedures. This tutorial, by contrast, emphasizes applications, programming and interpretation of R&S, using the R programming language for illustration. Readers (and the audience) can download the code and follow along with the examples, but no experience with R is needed. 

   more » « less
4. Covering a Few Submodular Constraints and Applications

   https://doi.org/10.4230/lipics.approx/random.2025.25  

   Bajpai, Tanvi; Chekuri, Chandra; Kulkarni, Pooja (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Ene, Alina; Chattopadhyay, Eshan (Ed.)

   We consider the problem of covering multiple submodular constraints. Given a finite ground set N, a cost function c: N → ℝ_+, r monotone submodular functions f_1,f_2,…,f_r over N and requirements b_1,b_2,…,b_r the goal is to find a minimum cost subset S ⊆ N such that f_i(S) ≥ b_i for 1 ≤ i ≤ r. When r = 1 this is the well-known Submodular Set Cover problem. Previous work [Chekuri et al., 2022] considered the setting when r is large and developed bi-criteria approximation algorithms, and approximation algorithms for the important special case when each f_i is a weighted coverage function. These are fairly general models and capture several concrete and interesting problems as special cases. The approximation ratios for these problem are at least Ω(log r) which is unavoidable when r is part of the input. In this paper, motivated by some recent applications, we consider the problem when r is a fixed constant and obtain two main results. When the f_i are weighted coverage functions from a deletion-closed set system we obtain a (1+ε)(e/(e-1))(1+β)-approximation where β is the approximation ratio for the underlying set cover instances via the natural LP. Second, for covering multiple submodular constraints we obtain a randomized bi-criteria approximation algorithm that for any given integer α ≥ 1 outputs a set S such that f_i(S) ≥ (1-1/e^α-ε)b_i for each i ∈ [r] and 𝔼[c(S)] ≤ (1+ε)α ⋅ OPT. These results show that one can obtain nearly as good an approximation for any fixed r as what one would achieve for r = 1. We also demonstrate applications of our results to implicit covering problems such as fair facility location. 

   more » « less
5. Counterexamples for multi-parameter weighted paraproducts

   https://doi.org/10.5802/crmath.52  

   Mozolyako, Pavel; Psaromiligkos, Georgios; Volberg, Alexander (February 2020, Comptes rendus mathematiques de lAcademie des sciences)

   We build the plethora of counterexamples to bi-parameter two weight embedding theorems. Two weight one parameter embedding results (which is the same as results of boundedness of two weight classical paraproducts, or two weight Carleson embedding theorems) are well known since the works of Sawyer in the 80’s. Bi-parameter case was considered by S. Y. A. Chang and R. Fefferman but only when underlying measure is Lebesgue measure. The embedding of holomorphic functions on bi-disc requires general input measure. In [9] we classified such embeddings if the output measure has tensor structure. In this note we give examples that without tensor structure requirement all results break down. 

   more » « less