×

zbMATH — the first resource for mathematics

A distributionally robust optimization approach for two-stage facility location problems. (English) Zbl 1445.90051
Summary: In this paper, we consider a facility location problem where customer demand constitutes considerable uncertainty, and where complete information on the distribution of the uncertainty is unavailable. We formulate the optimal decision problem as a two-stage stochastic mixed integer programming problem: an optimal selection of facility locations in the first stage and an optimal decision on the operation of each facility in the second stage. A distributionally robust optimization framework is proposed to hedge risks arising from incomplete information on the distribution of the uncertainty. Specifically, by exploiting the moment information, we construct a set of distributions which contains the true distribution and where the optimal decision is based on the worst distribution from the set. We then develop two numerical schemes for solving the distributionally robust facility location problem: a semi-infinite programming approach which exploits moments of certain reference random variables and a semi-definite programming approach which utilizes the mean and correlation of the underlying random variables describing the demand uncertainty. In the semi-infinite programming approach, we apply the well-known linear decision rule approach to the robust dual problem and then approximate the semi-infinite constraints through the conditional value at risk measure. We provide numerical tests to demonstrate the computation and properties of the robust solutions.
MSC:
90B80 Discrete location and assignment
90C17 Robustness in mathematical programming
90C22 Semidefinite programming
90C34 Semi-infinite programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anderson E, Xu H, Zhang D (2014) Confidence levels for cvar risk measures and minimax limits. Business Analytics Working Paper Series, University of Sydney, Australia · Zbl 1436.90092
[2] Averbakh, I.; Berman, O., Minimax regret p-center location on a network with demand uncertainty, Locat Sci, 5, 4, 247-254 (1997) · Zbl 0928.90042
[3] Averbakh, I.; Berman, O., Minmax regret median location on a network under uncertainty, INFORMS J Comput, 12, 2, 104-110 (2000) · Zbl 1034.90007
[4] Balinski, ML; Rispoli, FJ, Signature classes of transportation polytopes, Math Program, 60, 1-3, 127-144 (1993) · Zbl 0783.90078
[5] Balinski, M. L.; Russakoff, Andrew, Faces of dual transportation polyhedra, Mathematical Programming Studies, 1-8 (1984), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 0553.90066
[6] Ben-Tal, A.; Goryashko, A.; Guslitzer, E.; Nemirovski, A., Adjustable robust solutions of uncertain linear programs, Math Program, 99, 2, 351-376 (2004) · Zbl 1089.90037
[7] Bertsimas, Dimitris; Sethuraman, Jay, Moment Problems and Semidefinite Optimization, International Series in Operations Research & Management Science, 469-509 (2000), Boston, MA: Springer US, Boston, MA · Zbl 0957.90522
[8] Bonami, P.; Günlük, O.; Linderoth, J., Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods, Math Program Comput, 10, 3, 333-382 (2018) · Zbl 1400.90239
[9] Calafiore, G.; Campi, MC, Uncertain convex programs: randomized solutions and confidence levels, Math Program, 102, 1, 25-46 (2005) · Zbl 1177.90317
[10] Calafiore, GC; Campi, MC, The scenario approach to robust control design, IEEE Trans Autom Control, 51, 5, 742-753 (2006) · Zbl 1366.93457
[11] Campi, MC; Garatti, S., A sampling-and-discarding approach to chance-constrained optimization: feasibility and optimality, J Optim Theory Appl, 148, 2, 257-280 (2011) · Zbl 1211.90146
[12] Chen, J.; Burer, S., Globally solving nonconvex quadratic programming problems via completely positive programming, Math Program Comput, 4, 1, 33-52 (2012) · Zbl 1257.90065
[13] Conde, E., Minmax regret location-allocation problem on a network under uncertainty, Eur J Oper Res, 179, 3, 1025-1039 (2007) · Zbl 1163.90384
[14] Daskin, MS, What you should know about location modeling, Naval Res Logist, 55, 4, 283-294 (2008) · Zbl 1153.90482
[15] Daskin, MS, Network and discrete location: models, algorithms, and applications (2011), London: Wiley, London
[16] Davis L (1991) Handbook of genetic algorithms. Van Nostrand Reinhold Company. ISBN-10: 0442001738
[17] Delage, E.; Ye, Y., Distributionally robust optimization under moment uncertainty with application to data-driven problems, Oper Res, 58, 3, 595-612 (2010) · Zbl 1228.90064
[18] Derinkuyu, K.; Pınar, M., On the s-procedure and some variants, Math Methods Oper Res, 64, 1, 55-77 (2006) · Zbl 1115.93025
[19] Díaz, JA; Fernández, E., A branch-and-price algorithm for the single source capacitated plant location problem, J Oper Res Soc, 53, 7, 728-740 (2002) · Zbl 1130.90354
[20] Esfahani, PM; Kuhn, D., Data-driven distributionally robust optimization using the wasserstein metric: performance guarantees and tractable reformulations, Math Program, 171, 1-2, 115-166 (2018) · Zbl 1433.90095
[21] Gondzio J, Yildirim EA (2018) Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulations. arXiv preprintarXiv:1810.02307
[22] Goyal, SK, Improving vam for unbalanced transportation problems, J Oper Res Soc, 35, 12, 1113-1114 (1984)
[23] Hong, LJ; Yang, Y.; Zhang, L., Sequential convex approximations to joint chance constrained programs: a monte carlo approach, Oper Res, 59, 3, 617-630 (2011) · Zbl 1231.90303
[24] Kuhn, D.; Wiesemann, W.; Georghiou, A., Primal and dual linear decision rules in stochastic and robust optimization, Math Program, 130, 1, 177-209 (2011) · Zbl 1236.90087
[25] Landau, HJ, Moments in mathematics (1987), Providence: American Mathematical Society, Providence
[26] Lim, M.; Daskin, MS; Bassamboo, A.; Chopra, S., A facility reliability problem: formulation, properties, and algorithm, Naval Res Logist, 57, 1, 58-70 (2010) · Zbl 1180.90090
[27] Louveaux, FV, Discrete stochastic location models, Ann Oper Res, 6, 2, 21-34 (1986)
[28] Love D, Bayraksan G (2015) Phi-divergence constrained ambiguous stochastic programs for data-driven optimization. Technical report, Department of Integrated Systems Engineering, The Ohio State University, Columbus, Ohio · Zbl 1369.90113
[29] Lu, M.; Ran, L.; Shen, JM, Reliable facility location design under uncertain correlated disruptions, Manuf Serv Oper Manag, 17, 4, 445-455 (2015)
[30] Owen, SH; Daskin, MS, Strategic facility location: a review, Eur J Oper Res, 111, 3, 423-447 (1998) · Zbl 0938.90048
[31] ReVelle, CS; Eiselt, HA, Location analysis: a synthesis and survey, Eur J Oper Res, 165, 1, 1-19 (2005) · Zbl 1112.90362
[32] Santiváñez, J.; Carlo, HJ, Reliable capacitated facility location problem with service levels, EURO J Transp Logist, 7, 4, 315-341 (2018)
[33] Scarf, H.; Arrow, KJ; Karlin, S., A min-max solution of an inventory problem, Stud Math Theory Inventory Prod, 10, 201-209 (1958)
[34] Shapiro, Alexander, On Duality Theory of Conic Linear Problems, Nonconvex Optimization and Its Applications, 135-165 (2001), Boston, MA: Springer US, Boston, MA · Zbl 1055.90088
[35] Shapiro, A., Monte carlo sampling methods, Handb Oper Res Manag Sci, 10, 353-425 (2003)
[36] Shapiro A, Nemirovski A (2005) On complexity of stochastic programming problems. In: Continuous optimization. Springer, Berlin, pp 111-146 · Zbl 1115.90041
[37] Shapiro, A.; Dentcheva, D.; Ruszczyński, AP, Lectures on stochastic programming: modeling and theory (2009), Philadelphia: SIAM, Philadelphia · Zbl 1183.90005
[38] Snyder, LV, Facility location under uncertainty: a review, IIE Trans, 38, 7, 547-564 (2006)
[39] Snyder, LV; Daskin, MS, Stochastic p-robust location problems, IIE Trans, 38, 11, 971-985 (2006)
[40] Sun, H.; Xu, H., Convergence analysis for distributionally robust optimization and equilibrium problems, Math Oper Res, 41, 2, 377-401 (2015) · Zbl 1338.90288
[41] Sun, H.; Xu, H.; Wang, Y., Asymptotic analysis of sample average approximation for stochastic optimization problems with joint chance constraints via conditional value at risk and difference of convex functions, J Optim Theory Appl, 161, 1, 257-284 (2014) · Zbl 1314.90059
[42] Wiesemann, W.; Kuhn, D.; Sim, M., Distributionally robust convex optimization, Oper Res, 62, 6, 1358-1376 (2014) · Zbl 1327.90158
[43] Wu, Chenchen; Du, Donglei; Xu, Dachuan, An Approximation Algorithm for the Two-Stage Distributionally Robust Facility Location Problem, Springer Proceedings in Mathematics & Statistics, 99-107 (2014), Cham: Springer International Publishing, Cham · Zbl 1327.90098
[44] Xia, W.; Vera, JC; Zuluaga, LF, Globally solving nonconvex quadratic programs via linear integer programming techniques, INFORMS J Comput (2019)
[45] Xu, H.; Liu, Y.; Sun, H., Distributionally robust optimization with matrix moment constraints: Lagrange duality and cutting plane methods, Math Program, 169, 2, 489-529 (2018) · Zbl 1391.90449
[46] Zhang, J.; Xu, H.; Zhang, L., Quantitative stability analysis for distributionally robust optimization with moment constraints, SIAM J Optim, 26, 3, 1855-1882 (2016) · Zbl 1346.90650
[47] Zymler, S.; Kuhn, D.; Rustem, B., Distributionally robust joint chance constraints with second-order moment information, Math Program, 137, 1-2, 167-198 (2013) · Zbl 1286.90103
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.