American Institute of Mathematical Sciences

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

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  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.
Keywords: Robust Optimization, NP-Hard., Semidefinite Programming, Euclidean Facility Location Problem, Second-Order Cone Programming.
Mathematics Subject Classification: Primary: 90C08; Secondary: 90C2.
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, Ser. B, 95 (2003), 3-51.  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-154.  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-262. 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-560. doi: 10.1137/S1052623401392354.  Google Scholar

[5]

A. Ben-Tal and A. Nemirovski, Robust convex optimization, Math. Oper. Res., 23 (1998), 769-805. 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-1064. 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-63. 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-410. 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-117.  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-579. doi: 10.1137/S1052623497327088.  Google Scholar

show all references

References:
[1]

F. Alizadeh and D. Goldfarb, Second-order cone programming, Math. Programming, Ser. B, 95 (2003), 3-51.  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-154.  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-262. 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-560. doi: 10.1137/S1052623401392354.  Google Scholar

[5]

A. Ben-Tal and A. Nemirovski, Robust convex optimization, Math. Oper. Res., 23 (1998), 769-805. 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-1064. 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-63. 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-410. 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-117.  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-579. 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]

Lin Zhu, Xinzhen Zhang. Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021030
[4]

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
[5]

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
[6]

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
[7]

Qingsong Duan, Mengwei Xu, Liwei Zhang, Sainan Zhang. Hadamard directional differentiability of the optimal value of a linear second-order conic programming problem. Journal of Industrial & Management Optimization, 2021, 17 (6) : 3085-3098. doi: 10.3934/jimo.2020108
[8]

Narges Torabi Golsefid, Maziar Salahi. Second order cone programming formulation of the fixed cost allocation in DEA based on Nash bargaining game. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021032
[9]

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
[10]

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
[11]

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
[12]

Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1873-1884. doi: 10.3934/jimo.2019033
[13]

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
[14]

Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1527-1538. doi: 10.3934/jimo.2019015
[15]

Daniel Heinlein, Ferdinand Ihringer. New and updated semidefinite programming bounds for subspace codes. Advances in Mathematics of Communications, 2020, 14 (4) : 613-630. doi: 10.3934/amc.2020034
[16]

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
[17]

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
[18]

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
[19]

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
[20]

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

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy