Stochastic Optimization and Learning for Two-Stage Supplier Problems
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917631825543168 |
|---|---|
| author | Brubach, Brian Grammel, Nathaniel Harris, David G. Srinivasan, Aravind Tsepenekas, Leonidas Vullikanti, Anil |
| author_facet | Brubach, Brian Grammel, Nathaniel Harris, David G. Srinivasan, Aravind Tsepenekas, Leonidas Vullikanti, Anil |
| contents | The main focus of this paper 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 (SAA) method, which crucially exploits properties of the restricted-case algorithms. We note that the scenario-discarding modification to the SAA method is necessary in order to optimize over the radius. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2008_03325 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Stochastic Optimization and Learning for Two-Stage Supplier Problems Brubach, Brian Grammel, Nathaniel Harris, David G. Srinivasan, Aravind Tsepenekas, Leonidas Vullikanti, Anil Data Structures and Algorithms The main focus of this paper 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 (SAA) method, which crucially exploits properties of the restricted-case algorithms. We note that the scenario-discarding modification to the SAA method is necessary in order to optimize over the radius. |
| title | Stochastic Optimization and Learning for Two-Stage Supplier Problems |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2008.03325 |