Stochastic Optimization and Learning for Two-Stage Supplier Problems
Open Access
- 9 December 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Probabilistic Machine Learning
- Vol. 1 (1) , 1-20
Abstract
The main focus of this article is radius-based (supplier) clustering in the two-stage stochastic setting with recourse, where the inherent stochasticity of the model comes in the form of a budget constraint. In addition to the standard (homogeneous) setting where all clients must be within a distance \(R\) of the nearest facility, we provide results for the more general problem where the radius demands may be inhomogeneous (i.e., different for each client). We also explore a number of variants where additional constraints are imposed on the first-stage decisions, specifically matroid and multi-knapsack constraints, and provide results for these settings. We derive results for the most general distributional setting, where there is only black-box access to the underlying distribution. To accomplish this, we first develop algorithms for the polynomial scenarios setting; we then employ a novel scenario-discarding variant of the standard Sample Average Approximation method, which crucially exploits properties of the restricted-case algorithms. We note that the scenario-discarding modification to the SAA method is necessary to optimize over the radius.
Keywords
All Related Versions
Funding Information
- National Science Foundation (CCF-1422569, CCF-1749864 and CCF-1918749)
- Amazon
- Adobe
This publication has 20 references indexed in Scilit:
- Where to locate COVID‐19 mass vaccination facilities?Naval Research Logistics (NRL), 2021
- The Roadside Healthcare Facility Location Problem A Managerial Network Design ChallengeProduction and Operations Management, 2020
- Generalized Center Problems with OutliersACM Transactions on Algorithms, 2019
- Approximation algorithms for distributionally-robust stochastic optimization with black-box distributions2019
- On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a GraphSIAM Journal on Computing, 2006
- Sampling Bounds for Stochastic Optimization2005
- Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization ProblemsLecture Notes in Computer Science, 2004
- The Sample Average Approximation Method for Stochastic Discrete OptimizationSIAM Journal on Optimization, 2002
- On Minimizing a Convex Function Subject to Linear InequalitiesJournal of the Royal Statistical Society Series B: Statistical Methodology, 1955
- Linear Programming under UncertaintyManagement Science, 1955