Performance evaluation for distributionally robust optimization with uncertain binary entries

Shunichi Ohmori; Kazuho Yoshimoto

doi:10.11121/ijocta.01.2021.00911

Authors

Shunichi Ohmori Waseda University http://orcid.org/0000-0002-2635-0450
Kazuho Yoshimoto Waseda University http://orcid.org/0000-0003-2870-9612

DOI:

https://doi.org/10.11121/ijocta.01.2021.00911

Keywords:

Distributionally Robust Optimization, Robust Optimization, Stochastic Programming, Convex Optimization

Abstract

We consider the data-driven stochastic programming problem with binary entries where the probability of existence of each entry is not known, instead realization of data is provided. We applied the distributionally robust optimization technique to minimize the worst-case expected cost taken over the ambiguity set based on the Kullback-Leibler divergence. We investigate the out-of-sample performance of the resulting optimal decision and analyze its dependence on the sparsity of the problem.

Downloads

Download data is not yet available.

Author Biographies

Shunichi Ohmori, Waseda University

Shunichi Ohmori (PhD) is an associate professor at department of industrial and system engineering, Waseda
University in Japan, and a researcher at institute of globalproduction and logistics at Waseda University, and a
researcher at data science institute at Waseda University. He received the master and Ph.D degree in engineering at
Waseda University. His research interest lies in operations research and supply chain management.

Kazuho Yoshimoto, Waseda University

Kazuho Yoshimoto (Dr. Engg.) is a professor at department
of industrial and system engineering at Waseda University in
Japan, and a head of Institute of Global Production and
Logistics at Waseda University. He received the master and
Ph.D degree in engineering at Waseda University. His
research interest lies in facility and logistics design.

References

Bertsimas, D., & Kallus, N. (2020). From predictive to prescriptive analytics. Management Science, 66(3), 1025-1044.

Smith, J. E., & Winkler, R. L. (2006). The optimizer’s curse: Skepticism and postdecision surprise in decision analysis. Management Science, 52(3), 311-322.

Esfahani, P. M., & Kuhn, D. (2018). Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations. Mathematical Programming, 171(1-2), 115-166.

Charnes, A., & Cooper, W. W. (1959). Chance-constrained programming. Management science, 6(1), 73-79.

Soyster, A. L. (1973). Convex programming with set-inclusive constraints and applications to inexact linear programming. Operations research, 21(5), 1154-1157.

Ben-Tal, A., & Nemirovski, A. (1998). Robust convex optimization. Mathematics of operations research, 23(4), 769-805.

Ben-Tal, A., & Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations research letters, 25(1), 1-13.

Ben-Tal, A., & Nemirovski, A. (2000). Robust solutions of linear programming problems contaminated with uncertain data. Mathematical programming, 88(3), 411-424.

El Ghaoui, L., & Lebret, H. (1997). Robust solutions to least-squares problems with uncertain data. SIAM Journal on matrix analysis and applications, 18(4), 1035-1064.

El Ghaoui, L., Oustry, F., & Lebret, H. (1998). Robust solutions to uncertain semidefinite programs. SIAM Journal on Optimization, 9(1), 33-52.

Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations research, 52(1), 35-53.

Ben-Tal, A., Den Hertog, D., & Vial, J.P. (2015). Deriving robust counterparts of nonlinear uncertain inequalities. Mathematical programming, 149(1-2), 265-299.

Ben-Tal, A., & Nemirovski, A. (2008). Selected topics in robust convex optimization. Mathematical Programming, 112(1), 125-158.

Ben-Tal, A., El Ghaoui, L., & Nemirovski, A. (2009). Robust optimization (Vol. 28). Princeton University Press.

Gorissen, B. L., Yanıkoglu, ˙I., & den Hertog, D. (2015). A practical guide to robust optimization. Omega, 53, 124-137.

Gabrel, V., Murat, C., & Thiele, A. (2014). Recent advances in robust optimization: An overview. European journal of operational research, 235(3), 471-483.

Sozuer, S., & Thiele, A. C. (2016). The state of robust optimization. In Robustness Analysis in Decision Aiding, Optimization, and Analytics (pp. 89-112). Springer, Cham.

Delage, E., & Iancu, D. A. (2015). Robust multistage decision making. In The Operations Research Revolution (pp. 20-46). INFORMS.

Bandi, C., & Bertsimas, D. (2012). Tractable stochastic analysis in high dimensions via robust optimization. Mathematical programming, 134(1), 23-70.

Nemirovski, A. (2012). On safe tractable approximations of chance constraints. European Journal of Operational Research, 219(3), 707-718.

Ozmen, A., Weber, G.W., & Karimov, A. (2013). A new robust optimization tool applied on financial data.

Savku, E., & Weber, G. W. (2018). A stochastic maximum principle for a markov regime-switching jump-diffusion model with delay and an application to finance. Journal of Optimization Theory and Applications, 179(2), 696-721.

Kara, G., Ozmen, A., & Weber, G. W. (2019). Stability advances in robust portfolio optimization under parallelepiped uncertainty. Central European Journal of Operations Research, 27(1), 241-261.

Baltas, I., Xepapadeas, A., & Yannacopoulos, A. N. (2019). Robust control of parabolic stochastic partial differential equations under model uncertainty. European Journal of Control, 46, 1-13.

Sangaiah, A. K., Tirkolaee, E. B., Goli, A., & Dehnavi-Arani, S. (2019). Robust optimization and mixed-integer linear programming model for LNG supply chain planning problem. Soft Computing, 1-21.

Bertsimas, D., Gupta, V., & Kallus, N. (2018). Data-driven robust optimization. Mathematical Programming, 167(2), 235-292.

Delage, E., & Ye, Y. (2010). Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations research, 58(3), 595-612.

Ben-Tal, A., Bhadra, S., Bhattacharyya, C., & Nath, J. S. (2011). Chance constrained uncertain classification via robust optimization. Mathematical programming, 127(1), 145-173.

Dupacova, J., & Kopa, M. (2012). Robustness in stochastic programs with risk constraints. Annals of Operations Research, 200(1), 55-74.

Xu, H., Caramanis, C., & Mannor, S. (2012). A distributional interpretation of robust optimization. Mathematics of Operations Research, 37(1), 95-110.

Zymler, S., Kuhn, D., & Rustem, B. (2013). Distributionally robust joint chance constraints with second-order moment information. Mathematical Programming, 137(1-2), 167-198.

Sun, H., Gao, Z., Szeto, W. Y., Long, J., & Zhao, F. (2014). A distributionally robust joint chance constrained optimization model for the dynamic network design problem under demand uncertainty. Networks and Spatial Economics, 14(3-4), 409-433.

Wiesemann, W., Kuhn, D., & Sim, M. (2014). Distributionally robust convex optimization. Operations Research, 62(6), 1358-1376.

Ben-Tal, A., Den Hertog, D., DeWaegenaere, A., Melenberg, B., & Rennen, G. (2013). Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 59(2), 341-357.

Bayraksan, G., & Love, D. K. (2015). Data-driven stochastic programming using phi-divergences. In The Operations Research Revolution (pp. 1-19). INFORMS.

Bertsimas, D., & Van Parys, B. (2017). Bootstrap robust prescriptive analytics. arXiv preprint arXiv:1711.09974.