Stochastic Optimization and Learning for Two-Stage Supplier Problems

Fuente: arXiv
Saved in:
Bibliographic Details
Main Authors: Brubach, Brian, Grammel, Nathaniel, Harris, David G., Srinivasan, Aravind, Tsepenekas, Leonidas, Vullikanti, Anil
Format: Preprint
Published: 2020
Subjects:
Online Access:
Tags: Add Tag
No Tags, Be the first to tag this record!
_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