October  2010, 6(4): 751-760. doi: 10.3934/jimo.2010.6.751

Robust solutions to Euclidean facility location problems with uncertain data

1. 

Department of Mathematical Sciences, Tsinghua University, Beijing 100084

2. 

Department of Mathematics, National Cheng Kung University, Tainan

Received  July 2009 Revised  April 2010 Published  September 2010

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.
Citation: Liping Zhang, Soon-Yi Wu. Robust solutions to Euclidean facility location problems with uncertain data. Journal of Industrial & Management Optimization, 2010, 6 (4) : 751-760. doi: 10.3934/jimo.2010.6.751
References:
[1]

F. Alizadeh and D. Goldfarb, Second-order cone programming,, Math. Programming, 95 (2003), 3. Google Scholar

[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. Google Scholar

[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. doi: 10.1137/S1064827598343954. Google Scholar

[4]

A. Ben-Tal, A. Nemirovski and C. Roos, Robust solutions of uncertain quadratic and conic-quadratic problems,, SIAM J. Optim., 13 (2002), 535. doi: 10.1137/S1052623401392354. Google Scholar

[5]

A. Ben-Tal and A. Nemirovski, Robust convex optimization,, Math. Oper. Res., 23 (1998), 769. doi: 10.1287/moor.23.4.769. Google Scholar

[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. doi: 10.1137/S0895479896298130. Google Scholar

[7]

M. L. Overton, A quadratically convergent method for minimizing a sum of Euclidean norms,, Math. Programming, 27 (1983), 34. doi: 10.1007/BF02591963. Google Scholar

[8]

L. Qi and G. Zhou, A smoothing Newton method for minimizing a sum of Euclidean norms,, SIAM J. Optim., 11 (2000), 389. doi: 10.1137/S105262349834895X. Google Scholar

[9]

M. Shunko and S. Gavirneni, Role of Transfer prices in global supply chains with random demands,, J. Ind. Manag. Optim., 3 (2007), 99. Google Scholar

[10]

G. L. Xue and Y. Ye, An efficient algorithm for minimizing a sum of $p$-norms,, SIAM J. Optim., 10 (2000), 551. doi: 10.1137/S1052623497327088. Google Scholar

show all references

References:
[1]

F. Alizadeh and D. Goldfarb, Second-order cone programming,, Math. Programming, 95 (2003), 3. Google Scholar

[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. Google Scholar

[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. doi: 10.1137/S1064827598343954. Google Scholar

[4]

A. Ben-Tal, A. Nemirovski and C. Roos, Robust solutions of uncertain quadratic and conic-quadratic problems,, SIAM J. Optim., 13 (2002), 535. doi: 10.1137/S1052623401392354. Google Scholar

[5]

A. Ben-Tal and A. Nemirovski, Robust convex optimization,, Math. Oper. Res., 23 (1998), 769. doi: 10.1287/moor.23.4.769. Google Scholar

[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. doi: 10.1137/S0895479896298130. Google Scholar

[7]

M. L. Overton, A quadratically convergent method for minimizing a sum of Euclidean norms,, Math. Programming, 27 (1983), 34. doi: 10.1007/BF02591963. Google Scholar

[8]

L. Qi and G. Zhou, A smoothing Newton method for minimizing a sum of Euclidean norms,, SIAM J. Optim., 11 (2000), 389. doi: 10.1137/S105262349834895X. Google Scholar

[9]

M. Shunko and S. Gavirneni, Role of Transfer prices in global supply chains with random demands,, J. Ind. Manag. Optim., 3 (2007), 99. Google Scholar

[10]

G. L. Xue and Y. Ye, An efficient algorithm for minimizing a sum of $p$-norms,, SIAM J. Optim., 10 (2000), 551. doi: 10.1137/S1052623497327088. Google Scholar

[1]

Xiaoni Chi, Zhongping Wan, Zijun Hao. Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111

[2]

Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171

[3]

Ye Tian, Shu-Cherng Fang, Zhibin Deng, Wenxun Xing. Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming. Journal of Industrial & Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703

[4]

Guowei Hua, Shouyang Wang, Chi Kin Chan, S. H. Hou. A fractional programming model for international facility location. Journal of Industrial & Management Optimization, 2009, 5 (3) : 629-649. doi: 10.3934/jimo.2009.5.629

[5]

Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965

[6]

Liwei Zhang, Jihong Zhang, Yule Zhang. Second-order optimality conditions for cone constrained multi-objective optimization. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1041-1054. doi: 10.3934/jimo.2017089

[7]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881

[8]

Xinmin Yang. On second order symmetric duality in nondifferentiable multiobjective programming. Journal of Industrial & Management Optimization, 2009, 5 (4) : 697-703. doi: 10.3934/jimo.2009.5.697

[9]

Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2019033

[10]

Xi-De Zhu, Li-Ping Pang, Gui-Hua Lin. Two approaches for solving mathematical programs with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 951-968. doi: 10.3934/jimo.2015.11.951

[11]

Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1

[12]

Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193

[13]

Shouhong Yang. Semidefinite programming via image space analysis. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1187-1197. doi: 10.3934/jimo.2016.12.1187

[14]

Christine Bachoc, Alberto Passuello, Frank Vallentin. Bounds for projective codes from semidefinite programming. Advances in Mathematics of Communications, 2013, 7 (2) : 127-145. doi: 10.3934/amc.2013.7.127

[15]

Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2019015

[16]

Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial & Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117

[17]

Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial & Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521

[18]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019102

[19]

Anurag Jayswala, Tadeusz Antczakb, Shalini Jha. Second order modified objective function method for twice differentiable vector optimization problems over cone constraints. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 133-145. doi: 10.3934/naco.2019010

[20]

Ruotian Gao, Wenxun Xing. Robust sensitivity analysis for linear programming with ellipsoidal perturbation. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2019041

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (10)
  • HTML views (0)
  • Cited by (5)

Other articles
by authors

[Back to Top]