Robust solutions to Euclidean facility location problems withuncertain data

Liping Zhang; Soon-Yi Wu

doi:10.3934/jimo.2010.6.751

Article Contents

2010, Volume 6, Issue 4: 751-760. Doi: 10.3934/jimo.2010.6.751

This issue Previous Article On information quality ranking and its managerial implications Next Article Optimal financing and dividend strategies in a dual model with proportional costs

Robust solutions to Euclidean facility location problems with uncertain data

Liping Zhang^1, and
Soon-Yi Wu^2,

1.
Department of Mathematical Sciences, Tsinghua University, Beijing 100084
2.
Department of Mathematics, National Cheng Kung University, Tainan

Received: June 30, 2009

Revised: March 31, 2010

Published: September 2010

Abstract Related Papers Cited by

Abstract

We consider uncertainty Euclidean facility location problems. Using the existing robust optimization methodology, we certainly obtain robust optimal solution of the Euclidean facility location problem with unknown-but-bounded uncertainty or with an ellipsoidal uncertainty by solving an SOCP or an SDP. In addition, we show that the robust counterpart of the Euclidean facility location problem with $\cap$-ellipsoidal uncertainty is NP-hard. We give an explicit SDP to approximate the NP-hard problem and estimate the quality of the approximation via the level of conservativeness.

Keywords:

Mathematics Subject Classification: Primary: 90C08; Secondary: 90C25.

Citation:

Related Papers

Cited by

References

[1]	F. Alizadeh and D. Goldfarb, Second-order cone programming, Math. Programming, Ser. B, 95 (2003), 3-51.
[2]	M. M. Ali and L. Masinga, A nonlinear optimization model for optimal order quantities with stochastic demand rate and price change, J. Ind. Manag. Optim., 3 (2007), 139-154.
[3]	K. D. Andersen, E. Christiansen, A. R. Conn and M. L. Overton, An efficient primal-dual interior-point method for minimizing a sum of Euclidean norms, SIAM J. Sci. Comput., 22 (2000), 243-262.doi: 10.1137/S1064827598343954.
[4]	A. Ben-Tal, A. Nemirovski and C. Roos, Robust solutions of uncertain quadratic and conic-quadratic problems, SIAM J. Optim., 13 (2002), 535-560.doi: 10.1137/S1052623401392354.
[5]	A. Ben-Tal and A. Nemirovski, Robust convex optimization, Math. Oper. Res., 23 (1998), 769-805.doi: 10.1287/moor.23.4.769.
[6]	L. El-Ghaoui and H. Lebret, Robust solutions to least-square problems with uncertain data matrices, SIAM J. Matrix Anal. Appl., 18 (1997), 1035-1064.doi: 10.1137/S0895479896298130.
[7]	M. L. Overton, A quadratically convergent method for minimizing a sum of Euclidean norms, Math. Programming, 27 (1983), 34-63.doi: 10.1007/BF02591963.
[8]	L. Qi and G. Zhou, A smoothing Newton method for minimizing a sum of Euclidean norms, SIAM J. Optim., 11 (2000), 389-410.doi: 10.1137/S105262349834895X.
[9]	M. Shunko and S. Gavirneni, Role of Transfer prices in global supply chains with random demands, J. Ind. Manag. Optim., 3 (2007), 99-117.
[10]	G. L. Xue and Y. Ye, An efficient algorithm for minimizing a sum of $p$-norms, SIAM J. Optim., 10 (2000), 551-579.doi: 10.1137/S1052623497327088.