Sampling-Based Approximation Schemes for Capacitated Stochastic Inventory Control Models
We study the classical multi-period capacitated stochastic inventory control problems in a data-driven setting. Instead of assuming full knowledge of the demand distributions, we assume that the demand distributions can only be accessed through drawing random samples. Such data-driven models are ubi...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/129792 |
| _version_ | 1826202250687545344 |
|---|---|
| author | Cheung, Wang Chi Simchi-Levi, David |
| author2 | Massachusetts Institute of Technology. Department of Civil and Environmental Engineering |
| author_facet | Massachusetts Institute of Technology. Department of Civil and Environmental Engineering Cheung, Wang Chi Simchi-Levi, David |
| author_sort | Cheung, Wang Chi |
| collection | MIT |
| description | We study the classical multi-period capacitated stochastic inventory control problems in a data-driven setting. Instead of assuming full knowledge of the demand distributions, we assume that the demand distributions can only be accessed through drawing random samples. Such data-driven models are ubiquitous in practice, where the cumulative distribution functions of the underlying random demand are either unavailable or too complex to work with. We consider the sample average approximation (SAA) method for the problem and establish an upper bound on the number of samples needed for the SAA method to achieve a near-optimal expected cost, under any level of required accuracy and prespecified confidence probability. The sample bound is polynomial in the number of time periods as well as the confidence and accuracy parameters. Moreover, the bound is independent of the underlying demand distributions. However, the SAA requires solving the SAA problem, which is #P-hard. Thus, motivated by the SAA analysis, we propose a polynomial time approximation scheme that also uses polynomially many samples. Finally, we establish a lower bound on the number of samples required to solve this data-driven newsvendor problem to near-optimality. |
| first_indexed | 2024-09-23T12:04:33Z |
| format | Article |
| id | mit-1721.1/129792 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:04:33Z |
| publishDate | 2021 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | dspace |
| spelling | mit-1721.1/1297922022-10-01T08:00:39Z Sampling-Based Approximation Schemes for Capacitated Stochastic Inventory Control Models Cheung, Wang Chi Simchi-Levi, David Massachusetts Institute of Technology. Department of Civil and Environmental Engineering Massachusetts Institute of Technology. Institute for Data, Systems, and Society We study the classical multi-period capacitated stochastic inventory control problems in a data-driven setting. Instead of assuming full knowledge of the demand distributions, we assume that the demand distributions can only be accessed through drawing random samples. Such data-driven models are ubiquitous in practice, where the cumulative distribution functions of the underlying random demand are either unavailable or too complex to work with. We consider the sample average approximation (SAA) method for the problem and establish an upper bound on the number of samples needed for the SAA method to achieve a near-optimal expected cost, under any level of required accuracy and prespecified confidence probability. The sample bound is polynomial in the number of time periods as well as the confidence and accuracy parameters. Moreover, the bound is independent of the underlying demand distributions. However, the SAA requires solving the SAA problem, which is #P-hard. Thus, motivated by the SAA analysis, we propose a polynomial time approximation scheme that also uses polynomially many samples. Finally, we establish a lower bound on the number of samples required to solve this data-driven newsvendor problem to near-optimality. 2021-02-17T18:48:20Z 2021-02-17T18:48:20Z 2019-05 2020-06-02T16:43:01Z Article http://purl.org/eprint/type/JournalArticle 0364-765X 1526-5471 https://hdl.handle.net/1721.1/129792 Cheung, Wang Chi and David Simchi-Levi. "Sampling-Based Approximation Schemes for Capacitated Stochastic Inventory Control Models." Mathematics of Operations Research 44, 2 (May 2019): 668-692. en 10.1287/MOOR.2018.0940 Mathematics of Operations Research Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute for Operations Research and the Management Sciences (INFORMS) SSRN |
| spellingShingle | Cheung, Wang Chi Simchi-Levi, David Sampling-Based Approximation Schemes for Capacitated Stochastic Inventory Control Models |
| title | Sampling-Based Approximation Schemes for Capacitated Stochastic Inventory Control Models |
| title_full | Sampling-Based Approximation Schemes for Capacitated Stochastic Inventory Control Models |
| title_fullStr | Sampling-Based Approximation Schemes for Capacitated Stochastic Inventory Control Models |
| title_full_unstemmed | Sampling-Based Approximation Schemes for Capacitated Stochastic Inventory Control Models |
| title_short | Sampling-Based Approximation Schemes for Capacitated Stochastic Inventory Control Models |
| title_sort | sampling based approximation schemes for capacitated stochastic inventory control models |
| url | https://hdl.handle.net/1721.1/129792 |
| work_keys_str_mv | AT cheungwangchi samplingbasedapproximationschemesforcapacitatedstochasticinventorycontrolmodels AT simchilevidavid samplingbasedapproximationschemesforcapacitatedstochasticinventorycontrolmodels |