A Column Generation Scheme for Distributionally Robust Multi-Item Newsvendor Problems

References

• Ardestani-Jaafari A, Delage E (2016) Robust optimization of sums of piecewise linear functions with application to inventory problems. Oper. Res. 64(2):474–494.Link, Google Scholar
• Ban GY, Rudin C (2019) The big data newsvendor: Practical insights from machine learning. Oper. Res. 67(1):90–108.Link, Google Scholar
• Bansal M, Huang KL, Mehrotra S (2018) Decomposition algorithms for two-stage distributionally robust mixed binary programs. SIAM J. Optim. 28(3):2360–2383.Crossref, Google Scholar
• Ben-Tal A, den Hertog D, De Waegenaere A, Melenberg B, Rennen G (2013) Robust solutions of optimization problems affected by uncertain probabilities. Management. Sci. 59(2):341–357.Link, Google Scholar
• Bertsimas D, Van Parys B (2022) Bootstrap robust prescriptive analytics. Math. Programming 195(1):39–78.Crossref, Google Scholar
• Bertsimas D, Gupta V, Kallus N (2018) Robust sample average approximation. Math. Programming 171(1):217–282.Crossref, Google Scholar
• Bertsimas D, McCord C, Sturt B (2023) Dynamic optimization with side information. European J. Oper. Res. 304(2):634–651.Crossref, Google Scholar
• Bertsimas D, Shtern S, Sturt B (2022) Two-stage sample robust optimization. Oper. Res. 70(1):624–640.Link, Google Scholar
• Bertsimas D, Sim M, Zhang M (2019) Adaptive distributionally robust optimization. Management Sci. 65(2):604–618.Link, Google Scholar
• Bixby RE, Gregory JW, Lustig IJ, Marsten RE, Shanno DF (1992) Very large-scale linear programming: A case study in combining interior point and simplex methods. Oper. Res. 40(5):885–897.Link, Google Scholar
• Chen Z, Xiong P (2022) RSOME in Python: An open-source package for robust stochastic optimization made easy. Optimization Online, https://optimization-online.org/wp-content/uploads/2021/06/8443-1.pdf.Google Scholar
• Chen Z, Sim M, Xiong P (2020) Robust stochastic optimization made easy with RSOME. Management Sci. 66(8):3329–3339.Link, Google Scholar
• Chen Y, Sun H, Xu H (2021) Decomposition and discrete approximation methods for solving two-stage distributionally robust optimization problems. Comput. Optim. Appl. 78(1):205–238.Crossref, Google Scholar
• Cheramin M, Cheng J, Jiang R, Pan K (2022) Computationally efficient approximations for distributionally robust optimization. INFORMS J. Comput. 34(3):1768–1794.Link, Google Scholar
• Costa L, Contardo C, Desaulniers G (2019) Exact branch-price-and-cut algorithms for vehicle routing. Transportation Sci. 53(4):946–985.Link, Google Scholar
• Delage E, Saif A (2022) The value of randomized solutions in mixed-integer distributionally robust optimization problems. INFORMS J. Comput. 34(1):333–353.Link, Google Scholar
• Delage E, Ye Y (2010) Distributionally robust optimization under moment uncertainty with application to data-driven problems. Oper. Res. 58(3):595–612.Link, Google Scholar
• Desaulniers G, Desrosiers J, Solomon MM (2002) Accelerating strategies in column generation methods for vehicle routing and crew scheduling problems. Essays and Surveys in Metaheuristics, Operations Research/Computer Science Interfaces Series, vol. 15 (Springer, Boston), 309–324.Google Scholar
• Desrochers M, Soumis F (1989) A column generation approach to the urban transit crew scheduling problem. Transportation Sci. 23(1):1–13.Link, Google Scholar
• Donohue KL (2000) Efficient supply contracts for fashion goods with forecast updating and two production modes. Management Sci. 46(11):1397–1411.Link, Google Scholar
• Du Merle O, Villeneuve D, Desrosiers J, Hansen P (1999) Stabilized column generation. Discrete Math. 194(1–3):229–237.Crossref, Google Scholar
• Gallego G, Moon I (1993) The distribution free newsboy problem: Review and extensions. J. Oper. Res. Soc. 44(8):825–834.Crossref, Google Scholar
• Gamboa CA, Valladão DM, Street A, Homem-de Mello T (2021) Decomposition methods for Wasserstein-based data-driven distributionally robust problems. Oper. Res. Lett. 49(5):696–702.Crossref, Google Scholar
• Goh J, Sim M (2010) Distributionally robust optimization and its tractable approximations. Oper. Res. 58(4-part-1):902–917.Link, Google Scholar
• Hanasusanto GA, Kuhn D, Wallace SW, Zymler S (2015) Distributionally robust multi-item newsvendor problems with multimodal demand distributions. Math. Programming 152(1):1–32.Crossref, Google Scholar
• Hao Z, He L, Hu Z, Jiang J (2020) Robust vehicle pre-allocation with uncertain covariates. Production Oper. Management 29(4):955–972.Crossref, Google Scholar
• Ho CP, Hanasusanto GA (2019) On data-driven prescriptive analytics with side information: A regularized Nadaraya-Watson approach. Optimization Online (January 23), http://www.optimization-online.org/DB_FILE/2019/01/7043.pdf.Google Scholar
• Kallus N, Mao X (2022) Stochastic optimization forests. Management Sci. 69(4):1975–1994.Google Scholar
• Kamburowski J (2015) On the distribution-free newsboy problem with some non-skewed demands. Oper. Res. Lett. 43(2):165–171.Crossref, Google Scholar
• Kannan R, Bayraksan G, Luedtke JR (2023) Residuals-based distributionally robust optimization with covariate information. Math. Program., ePub ahead of print September 26, https://doi.org/10.1007/s10107-023-02014-7.Google Scholar
• Karmarkar N (1984) A new polynomial-time algorithm for linear programming. Combinatorica 4:373–395.Crossref, Google Scholar
• Kuhn D, Wiesemann W, Georghiou A (2011) Primal and dual linear decision rules in stochastic and robust optimization. Math. Programming 130(1):177–209.Crossref, Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Luo F, Mehrotra S (2019) Decomposition algorithm for distributionally robust optimization using Wasserstein metric with an application to a class of regression models. European J. Oper. Res. 278(1):20–35.Crossref, Google Scholar
• Mehrotra S, Papp D (2014) A cutting surface algorithm for semi-infinite convex programming with an application to moment robust optimization. SIAM J. Optim. 24(4):1670–1697.Crossref, Google Scholar
• Mohajerin Esfahani P, Kuhn D (2018) Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations. Math. Programming 171(1):115–166.Crossref, Google Scholar
• Namkoong H, Duchi JC (2016) Stochastic gradient methods for distributionally robust optimization with f-divergences. NIPS. 29:2208–2216.Google Scholar
• Natarajan K, Sim M, Uichanco J (2018) Asymmetry and ambiguity in newsvendor models. Management Sci. 64(7):3146–3167.Link, Google Scholar
• Nguyen VA, Zhang F, Blanchet J, Delage E, Ye Y (2021) Robustifying conditional portfolio decisions via optimal transport. Preprint, submitted March 30, https://arxiv.org/abs/2103.16451.Google Scholar
• Perakis G, Sim M, Tang Q, Xiong P (2022) Robust pricing and production with information partitioning and adaptation. Management Sci. 69(3):1398–1419.Link, Google Scholar
• Qin Y, Wang R, Vakharia AJ, Chen Y, Seref MM (2011) The newsvendor problem: Review and directions for future research. European J. Oper. Res. 213(2):361–374.Crossref, Google Scholar
• Rahimian H, Mehrotra S (2019) Distributionally robust optimization: A review. Preprint, submitted August 13, https://arxiv.org/abs/1908.05659.Google Scholar
• Rahimian H, Bayraksan G, Homem-de Mello T (2019) Controlling risk and demand ambiguity in newsvendor models. European J. Oper. Res. 279(3):854–868.Crossref, Google Scholar
• Rousseau LM, Gendreau M, Feillet D (2007) Interior point stabilization for column generation. Oper. Res. Lett. 35(5):660–668.Crossref, Google Scholar
• Saif A, Delage E (2021) Data-driven distributionally robust capacitated facility location problem. European J. Oper. Res. 291(3):995–1007.Crossref, Google Scholar
• Scarf H (1957) A Min-Max Solution of an Inventory Problem. Arrow K, Karlin S, Scarf H, eds. Studies in the Mathematical Theory of Inventory and Production (Stanford University Press, Stanford, CA).Google Scholar
• Shapiro A, Dentcheva D, Ruszczyński A (2014) Lectures on Stochastic Programming: Modeling and Theory (SIAM, Philadelphia).Crossref, Google Scholar
• Vanderbeck F (2000) On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Oper. Res. 48(1):111–128.Link, Google Scholar
• Wang S, Delage E (2023) A column generation scheme for distributionally robust multi-item newsvendor problems. http://dx.doi.org/10.1287/ijoc.2022.0010.cd, https://github.com/INFORMSJoC/2022.0010.Google Scholar
• Wang S, Li J, Mehrotra S (2022) A solution approach to distributionally robust chance-constrained assignment problems. INFORMS J. Optim. 4(2):125–147.Link, Google Scholar
• Wiesemann W, Kuhn D, Sim M (2014) Distributionally robust convex optimization. Oper. Res. 62(6):1358–1376.Link, Google Scholar
• Zverovich V, Fábián CI, Ellison EF, Mitra G (2012) A computational study of a solver system for processing two-stage stochastic lps with enhanced benders decomposition. Math. Program. Comput. 4(3):211–238.Crossref, Google Scholar