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

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[2]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[3]

Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020136
[4]

Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184
[5]

Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023
[6]

Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027
[7]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028
[8]

Valery Y. Glizer. Novel Conditions of Euclidean space controllability for singularly perturbed systems with input delay. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 307-320. doi: 10.3934/naco.2020027
[9]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133
[10]

Alexandre B. Simas, Fábio J. Valentim. $W$-Sobolev spaces: Higher order and regularity. Communications on Pure & Applied Analysis, 2015, 14 (2) : 597-607. doi: 10.3934/cpaa.2015.14.597
[11]

Enkhbat Rentsen, Battur Gompil. Generalized nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022
[12]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[13]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[14]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463
[15]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[16]

Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021008
[17]

A. Aghajani, S. F. Mottaghi. Regularity of extremal solutions of semilinaer fourth-order elliptic problems with general nonlinearities. Communications on Pure & Applied Analysis, 2018, 17 (3) : 887-898. doi: 10.3934/cpaa.2018044
[18]

Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401
[19]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151
[20]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences