American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Portfolio procurement policies for budget-constrained supply chains with option contracts and external financing
  • JIMO Home
  • This Issue
  • Next Article
    Optimal risk control and dividend strategies in the presence of two reinsurers: Variance premium principle
July  2018, 14(3): 1085-1104. doi: 10.3934/jimo.2017091

A variational inequality approach for constrained multifacility Weber problem under gauge

Jianlin Jiang 1, , Shun Zhang 1, , Su Zhang 2,, and  Jie Wen 1,

1. 

Department of Mathematics, College of Science, Nanjing University of Aeronautics and Astronautics, 29 Yudao Street, Qinhuai District, Nanjing 210016, China
2. 

Department of Financial Management, Business School, Nankai University, 94 Weijin Road, Nankai District, Tianjin 300071, China

* Corresponding author: Su Zhang

Received  February 2016 Revised  May 2017 Published  September 2017

Fund Project: The first author is supported by National Natural Science Foundation of China No. 11571169, the Qing Lan Project and the Fundamental Research Funds for the Central Universities No. NQ2016002. The third author is supported by National Natural Science Foundation of China No. 11401322

The classical multifacility Weber problem (MFWP) is one of the most important models in facility location. This paper considers more general and practical case of MFWP called constrained multifacility Weber problem (CMFWP), in which the gauge is used to measure distances and locational constraints are imposed to facilities. In particular, we develop a variational inequality approach for solving it. The CMFWP is reformulated into a linear variational inequality, whose special structures lead to new projection-type methods. Global convergence of the projection-type methods is proved under mild assumptions. Some preliminary numerical results are reported which verify the effectiveness of proposed methods.

Keywords: Facility location, multifacility Weber problem, gauge, locational constraints, variational inequality approach.
Mathematics Subject Classification: Primary: 90B85; Secondary: 90C33.
Citation: Jianlin Jiang, Shun Zhang, Su Zhang, Jie Wen. A variational inequality approach for constrained multifacility Weber problem under gauge. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1085-1104. doi: 10.3934/jimo.2017091
References:
[1]

R. S. Burachik and A. N. Iusem, A generalized proximal point algorithm for the variational inequality problem in a Hilbert space, SIAM J. Optim., 8 (1998), 197-216. doi: 10.1137/S1052623495286302. Google Scholar

[2]

E. Carrizosa, E. Conde, M. Munõz and J. Puerto, Simpson points in planar problems with locational constraints -the polyhedral gauge case, Math. Oper. Res., 22 (1997), 297-300. doi: 10.1287/moor.22.2.291. Google Scholar

[3]

M. Cera, J. A. Mesa, F. A. Ortega and F. Plastria, Locating a central hunter on the plane, J. Optim. Theory Appl., 136 (2008), 155-166. doi: 10.1007/s10957-007-9293-y. Google Scholar

[4]

F. Daneshzand and R. Shoeleh, Multifacility location problem, in Facility Location: Concepts, Models, Algorithms and Case Studies, R.Z. Farahani and M. Hekmatfar (eds.), Springer, Berlin, (2009), 69-92. Google Scholar

[5]

Z. Drezner, Facility Location: A Survey of Applications and Methods, Springer, New York, 1995. doi: 10.1007/978-1-4612-5355-6. Google Scholar

[6]

Z. Drezner and H. W. Hamacher, Facility Location: Applications and Theory, Springer-Verlag, Berlin, 2002. doi: 10.1007/978-3-642-56082-8. Google Scholar

[7]

R. Durier, On Pareto optima, the Fermat-Weber problem and polyhedral gauges, Math. Program., 47 (1990), 65-79. doi: 10.1007/BF01580853. Google Scholar

[8]

B. C. Eaves, On the basic theorem of complememtarity, Math. Program., 1 (1971), 68-75. doi: 10.1007/BF01584073. Google Scholar

[9]

J. W. Eyster, J. A. White and W. W. Wierwille, On solving multifacility location problems using a hyperboloid approximation procedure, AIIE Trans., 5 (1973), 275-280. doi: 10.1080/05695557308974912. Google Scholar

[10]

F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003. Google Scholar

[11]

M. C. Ferris and C. Kanzow, Engineering and economic applications of complementarity problems, SIAM Review, 39 (1997), 669-713. doi: 10.1137/S0036144595285963. Google Scholar

[12]

B. S. He, A new method for a class of linear variational inequalities, Math. Program., 66 (1994), 137-144. doi: 10.1007/BF01581141. Google Scholar

[13]

B. S. He, A modified projection and contraction method for a class of linear complementarity problems, J. Comput. Math., 14 (1996), 54-63. Google Scholar

[14]

B. S. He, X. M. Yuan and W. X. Zhang, A customized proximal point algorithm for convex minimization with linear constraints, Comput. Optim. Appl., 56 (2013), 559-572. doi: 10.1007/s10589-013-9564-5. Google Scholar

[15]

I. N. Katz and S. R. Vogl, A Weiszfeld algorithm for the solution of an asymmetric extension of the generalized Fermat location problem, Comput. Math. Appl., 59 (2010), 399-410. doi: 10.1016/j.camwa.2009.07.007. Google Scholar

[16]

R. F. Love and J. G. Morris, Mathematical models of road travel distances, Manag. Sci., 25 (1979), 130-139. doi: 10.1287/mnsc.25.2.130. Google Scholar

[17]

R. F. Love and J. G. Morris, On estimating road distances by mathematical functions, Euro. J. Oper. Res., 36 (1988), 251-253. doi: 10.1016/0377-2217(88)90431-6. Google Scholar

[18]

R. F. Love, J. G. Morris and G. O. Wesolowsky, Facilities Location: Models and Methods, North-Holland, Amsterdam, 1988. Google Scholar

[19]

B. Martinet, Regularision d'inéquations variationnelles par approximations successive, Revue Francaise d'Automatique et Informatique Recherche Opérationnelle, 4 (1970), 154-158. Google Scholar

[20]

W. Miehle, Link length minimization in networks, Oper. Res., 6 (1958), 232-243. doi: 10.1287/opre.6.2.232. Google Scholar

[21]

H. Minkowski, Theorie der konvexen Körper, Gesammelte Abhandlungen, Teubner, Berlin, 1911.Google Scholar

[22]

S. Nickel, Restricted center problems under polyhedral gauges, Euro. J. Oper. Res., 104 (1998), 343-357. doi: 10.1016/S0377-2217(97)00189-6. Google Scholar

[23]

L. M. Ostresh, The multifacility location problem: Applications and descent theorems, J. Regional Sci., 17 (1977), 409-419. doi: 10.1111/j.1467-9787.1977.tb00511.x. Google Scholar

[24]

F. Plastria, Asymmetric distances, semidirected networks and majority in Fermat-Weber problems, Ann. Oper. Res., 167 (2009), 121-155. doi: 10.1007/s10479-008-0351-0. Google Scholar

[25]

F. Plastria, The Weiszfeld algorithm: proof, amendments, and extensions, in Foundations of Location Analysis, H.A. Eiselt and V. Marianov (eds.), Springer, US, 155 (2011), 357-389. doi: 10.1007/978-1-4419-7572-0_16. Google Scholar

[26]

J. B. Rosen and G. L. Xue, On the convergence of Miehle's algorithm for the Euclidean multifacility location problem, Oper. Res., 40 (1992), 188-191. doi: 10.1287/opre.40.1.188. Google Scholar

[27]

J. B. Rosen and G. L. Xue, On the convergence of a hyperboloid approximation procedure for the perturbed Euclidean multifacility location problem, Oper. Res., 41 (1993), 1164-1171. doi: 10.1287/opre.41.6.1164. Google Scholar

[28]

M. V. Solodov and P. Tseng, Modified projection-type methods for monotone variational inequalities, SIAM J. Control Optim., 34 (1996), 1814-1830. doi: 10.1137/S0363012994268655. Google Scholar

[29]

H. Uzawa, Iterative methods for concave programming, in Studies in Linear and Nonlinear Programming, K.J. Arrow, L. Hurwicz and H. Uzawa (eds.), Stanford University Press, Stanford, (1958), 154-165. Google Scholar

[30]

J. E. Ward and R. E. Wendell, A new norm for measuring distance which yields linear location problems, Oper. Res., 28 (1980), 836-844. Google Scholar

[31]

J. E. Ward and R. E. Wendell, Using block norms for location modelling, Oper. Res., 33 (1985), 1074-1090. doi: 10.1287/opre.33.5.1074. Google Scholar

[32]

E. Weiszfeld, Sur le point pour lequel la somme des distances de n points donnés est minimum, Tohoku Math. J., 43 (1937), 355-386. Google Scholar

[33]

C. Witzgall, Optimal location of a central facility, mathematical models and concepts, Report 8388, National Bureau of Standards, Washington DC, US, 1964.Google Scholar

show all references

References:
[1]

R. S. Burachik and A. N. Iusem, A generalized proximal point algorithm for the variational inequality problem in a Hilbert space, SIAM J. Optim., 8 (1998), 197-216. doi: 10.1137/S1052623495286302. Google Scholar

[2]

E. Carrizosa, E. Conde, M. Munõz and J. Puerto, Simpson points in planar problems with locational constraints -the polyhedral gauge case, Math. Oper. Res., 22 (1997), 297-300. doi: 10.1287/moor.22.2.291. Google Scholar

[3]

M. Cera, J. A. Mesa, F. A. Ortega and F. Plastria, Locating a central hunter on the plane, J. Optim. Theory Appl., 136 (2008), 155-166. doi: 10.1007/s10957-007-9293-y. Google Scholar

[4]

F. Daneshzand and R. Shoeleh, Multifacility location problem, in Facility Location: Concepts, Models, Algorithms and Case Studies, R.Z. Farahani and M. Hekmatfar (eds.), Springer, Berlin, (2009), 69-92. Google Scholar

[5]

Z. Drezner, Facility Location: A Survey of Applications and Methods, Springer, New York, 1995. doi: 10.1007/978-1-4612-5355-6. Google Scholar

[6]

Z. Drezner and H. W. Hamacher, Facility Location: Applications and Theory, Springer-Verlag, Berlin, 2002. doi: 10.1007/978-3-642-56082-8. Google Scholar

[7]

R. Durier, On Pareto optima, the Fermat-Weber problem and polyhedral gauges, Math. Program., 47 (1990), 65-79. doi: 10.1007/BF01580853. Google Scholar

[8]

B. C. Eaves, On the basic theorem of complememtarity, Math. Program., 1 (1971), 68-75. doi: 10.1007/BF01584073. Google Scholar

[9]

J. W. Eyster, J. A. White and W. W. Wierwille, On solving multifacility location problems using a hyperboloid approximation procedure, AIIE Trans., 5 (1973), 275-280. doi: 10.1080/05695557308974912. Google Scholar

[10]

F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003. Google Scholar

[11]

M. C. Ferris and C. Kanzow, Engineering and economic applications of complementarity problems, SIAM Review, 39 (1997), 669-713. doi: 10.1137/S0036144595285963. Google Scholar

[12]

B. S. He, A new method for a class of linear variational inequalities, Math. Program., 66 (1994), 137-144. doi: 10.1007/BF01581141. Google Scholar

[13]

B. S. He, A modified projection and contraction method for a class of linear complementarity problems, J. Comput. Math., 14 (1996), 54-63. Google Scholar

[14]

B. S. He, X. M. Yuan and W. X. Zhang, A customized proximal point algorithm for convex minimization with linear constraints, Comput. Optim. Appl., 56 (2013), 559-572. doi: 10.1007/s10589-013-9564-5. Google Scholar

[15]

I. N. Katz and S. R. Vogl, A Weiszfeld algorithm for the solution of an asymmetric extension of the generalized Fermat location problem, Comput. Math. Appl., 59 (2010), 399-410. doi: 10.1016/j.camwa.2009.07.007. Google Scholar

[16]

R. F. Love and J. G. Morris, Mathematical models of road travel distances, Manag. Sci., 25 (1979), 130-139. doi: 10.1287/mnsc.25.2.130. Google Scholar

[17]

R. F. Love and J. G. Morris, On estimating road distances by mathematical functions, Euro. J. Oper. Res., 36 (1988), 251-253. doi: 10.1016/0377-2217(88)90431-6. Google Scholar

[18]

R. F. Love, J. G. Morris and G. O. Wesolowsky, Facilities Location: Models and Methods, North-Holland, Amsterdam, 1988. Google Scholar

[19]

B. Martinet, Regularision d'inéquations variationnelles par approximations successive, Revue Francaise d'Automatique et Informatique Recherche Opérationnelle, 4 (1970), 154-158. Google Scholar

[20]

W. Miehle, Link length minimization in networks, Oper. Res., 6 (1958), 232-243. doi: 10.1287/opre.6.2.232. Google Scholar

[21]

H. Minkowski, Theorie der konvexen Körper, Gesammelte Abhandlungen, Teubner, Berlin, 1911.Google Scholar

[22]

S. Nickel, Restricted center problems under polyhedral gauges, Euro. J. Oper. Res., 104 (1998), 343-357. doi: 10.1016/S0377-2217(97)00189-6. Google Scholar

[23]

L. M. Ostresh, The multifacility location problem: Applications and descent theorems, J. Regional Sci., 17 (1977), 409-419. doi: 10.1111/j.1467-9787.1977.tb00511.x. Google Scholar

[24]

F. Plastria, Asymmetric distances, semidirected networks and majority in Fermat-Weber problems, Ann. Oper. Res., 167 (2009), 121-155. doi: 10.1007/s10479-008-0351-0. Google Scholar

[25]

F. Plastria, The Weiszfeld algorithm: proof, amendments, and extensions, in Foundations of Location Analysis, H.A. Eiselt and V. Marianov (eds.), Springer, US, 155 (2011), 357-389. doi: 10.1007/978-1-4419-7572-0_16. Google Scholar

[26]

J. B. Rosen and G. L. Xue, On the convergence of Miehle's algorithm for the Euclidean multifacility location problem, Oper. Res., 40 (1992), 188-191. doi: 10.1287/opre.40.1.188. Google Scholar

[27]

J. B. Rosen and G. L. Xue, On the convergence of a hyperboloid approximation procedure for the perturbed Euclidean multifacility location problem, Oper. Res., 41 (1993), 1164-1171. doi: 10.1287/opre.41.6.1164. Google Scholar

[28]

M. V. Solodov and P. Tseng, Modified projection-type methods for monotone variational inequalities, SIAM J. Control Optim., 34 (1996), 1814-1830. doi: 10.1137/S0363012994268655. Google Scholar

[29]

H. Uzawa, Iterative methods for concave programming, in Studies in Linear and Nonlinear Programming, K.J. Arrow, L. Hurwicz and H. Uzawa (eds.), Stanford University Press, Stanford, (1958), 154-165. Google Scholar

[30]

J. E. Ward and R. E. Wendell, A new norm for measuring distance which yields linear location problems, Oper. Res., 28 (1980), 836-844. Google Scholar

[31]

J. E. Ward and R. E. Wendell, Using block norms for location modelling, Oper. Res., 33 (1985), 1074-1090. doi: 10.1287/opre.33.5.1074. Google Scholar

[32]

E. Weiszfeld, Sur le point pour lequel la somme des distances de n points donnés est minimum, Tohoku Math. J., 43 (1937), 355-386. Google Scholar

[33]

C. Witzgall, Optimal location of a central facility, mathematical models and concepts, Report 8388, National Bureau of Standards, Washington DC, US, 1964.Google Scholar

Table 1.  MA, GMA, Algorithm 1 and Algorithm 2 for MFWP
Problem MA GMA Algorithm 1 Algorithm 2
E1 CPU 0.0003 0.0004 0.0147 0.0143
Iter. 2 9 152.44 157.52
Obj. 182.23 182.43 181.42 181.42
E2 CPU 0.0109 0.0006 0.0149 0.0144
Iter. 206 5 158.58 159.96
Obj. 182.19 182.68 181.42 181.42
E1' CPU / / 0.0145 0.0138
Iter. / / 154.32 156.04
Obj. / / 181.42 181.42
E2' CPU / / 0.0147 0.0141
Iter. / / 158.84 161.82
Obj. / / 181.42 181.42
E3 CPU 0.1949 0.0050 0.0206 0.0207
Iter. 3733.40 85.86 195.76 197.14
Obj. 63737.39 65188.08 63515.97 63515.97
Table Options

Download as excel

Problem MA GMA Algorithm 1 Algorithm 2
E1 CPU 0.0003 0.0004 0.0147 0.0143
Iter. 2 9 152.44 157.52
Obj. 182.23 182.43 181.42 181.42
E2 CPU 0.0109 0.0006 0.0149 0.0144
Iter. 206 5 158.58 159.96
Obj. 182.19 182.68 181.42 181.42
E1' CPU / / 0.0145 0.0138
Iter. / / 154.32 156.04
Obj. / / 181.42 181.42
E2' CPU / / 0.0147 0.0141
Iter. / / 158.84 161.82
Obj. / / 181.42 181.42
E3 CPU 0.1949 0.0050 0.0206 0.0207
Iter. 3733.40 85.86 195.76 197.14
Obj. 63737.39 65188.08 63515.97 63515.97
Table 2.  HAP, GHAP, SHAP, SGHAP, Algorithm 1 and Algorithm 2 for MFWP
m HAP GHAP SHAP SGHAP Algo. 1 Algo. 2
ε=50 ε=5 ε=0.5 ε=0.05 ε=50 s=5 ε=0.5 ε=0.05
2 CPU 0.21 0.44 1.08 2.75 0.15 0.27 0.60 1.53 0.87 0.80 1.38 1.32
Iter. 48.52 101.78 247.60 630.34 33.88 61.28 138.00 348.72 262.84 243.48 272.78 272.84
Dobj. 82.2151 28.6441 9.0927 2.6080 82.2156 28.6446 9.0932 2.6083 2.6082 2.6052 0.0000 0.0002
4 CPU 0.98 2.48 6.60 17.89 0.58 1.33 3.45 9.26 2.61 2.33 2.15 2.08
Iter. 107.70 270.20 720.00 1936.20 63.50 145.90 376.10 1003.40 378.30 337.80 168.90 168.90
Dobj. 283.4897 94.6138 30.0266 9.0773 283.4903 94.6144 30.0271 9.0767 9.0713 9.0701 0.0000 0.0005
6 CPU 2.26 5.95 16.08 43.94 1.28 3.17 8.52 23.22 5.71 4.00 2.82 2.73
Iter. 164.36 431.30 1167.66 3145.08 92.64 230.90 616.96 1664.60 541.94 382.48 126.82 126.84
Dobj. 475.4137 155.9050 49.3255 15.0577 475.4124 155.9035 49.3238 15.0528 15.0468 15.0480 0.0000 -0.0003
8 CPU 3.80 10.14 27.60 74.81 2.11 5.44 14.72 39.90 8.44 5.98 3.20 3.12
Iter. 216.50 578.56 1573.84 4245.06 119.98 309.62 836.70 2262.78 638.06 453.98 101.70 101.74
Dobj. 698.8811 227.5549 72.0128 22.1839 698.8829 227.5570 72.0143 22.1790 22.1858 22.1714 0.0000 0.0021
10 CPU 6.08 16.40 44.55 120.77 3.34 8.77 23.73 64.28 14.02 9.34 4.27 4.14
Iter. 274.60 740.54 2012.20 5414.64 150.90 396.42 1072.20 2899.56 840.34 563.34 97.68 97.80
Dobj. 925.6176 299.2628 94.3543 28.8958 925.6183 299.2637 94.3537 28.8839 28.8930 28.8793 0.0000 -0.0123
Table Options

Download as excel

m HAP GHAP SHAP SGHAP Algo. 1 Algo. 2
ε=50 ε=5 ε=0.5 ε=0.05 ε=50 s=5 ε=0.5 ε=0.05
2 CPU 0.21 0.44 1.08 2.75 0.15 0.27 0.60 1.53 0.87 0.80 1.38 1.32
Iter. 48.52 101.78 247.60 630.34 33.88 61.28 138.00 348.72 262.84 243.48 272.78 272.84
Dobj. 82.2151 28.6441 9.0927 2.6080 82.2156 28.6446 9.0932 2.6083 2.6082 2.6052 0.0000 0.0002
4 CPU 0.98 2.48 6.60 17.89 0.58 1.33 3.45 9.26 2.61 2.33 2.15 2.08
Iter. 107.70 270.20 720.00 1936.20 63.50 145.90 376.10 1003.40 378.30 337.80 168.90 168.90
Dobj. 283.4897 94.6138 30.0266 9.0773 283.4903 94.6144 30.0271 9.0767 9.0713 9.0701 0.0000 0.0005
6 CPU 2.26 5.95 16.08 43.94 1.28 3.17 8.52 23.22 5.71 4.00 2.82 2.73
Iter. 164.36 431.30 1167.66 3145.08 92.64 230.90 616.96 1664.60 541.94 382.48 126.82 126.84
Dobj. 475.4137 155.9050 49.3255 15.0577 475.4124 155.9035 49.3238 15.0528 15.0468 15.0480 0.0000 -0.0003
8 CPU 3.80 10.14 27.60 74.81 2.11 5.44 14.72 39.90 8.44 5.98 3.20 3.12
Iter. 216.50 578.56 1573.84 4245.06 119.98 309.62 836.70 2262.78 638.06 453.98 101.70 101.74
Dobj. 698.8811 227.5549 72.0128 22.1839 698.8829 227.5570 72.0143 22.1790 22.1858 22.1714 0.0000 0.0021
10 CPU 6.08 16.40 44.55 120.77 3.34 8.77 23.73 64.28 14.02 9.34 4.27 4.14
Iter. 274.60 740.54 2012.20 5414.64 150.90 396.42 1072.20 2899.56 840.34 563.34 97.68 97.80
Dobj. 925.6176 299.2628 94.3543 28.8958 925.6183 299.2637 94.3537 28.8839 28.8930 28.8793 0.0000 -0.0123
Table 3.  Numerical results for CMFWP under Euclidean distances
n m PC method PPA1 PPA2 Algorithm 1 Algorithm 2
CPU Iter. CPU Iter. CPU Iter. CPU Iter. CPU Iter.
50 2 0.034 34.45 0.018 31.32 0.018 32.93 0.018 29.84 0.015 30.34
4 0.093 40.32 0.044 36.60 0.046 37.78 0.044 36.39 0.043 37.11
6 0.197 45.92 0.071 39.23 0.072 40.92 0.068 37.82 0.063 38.08
8 0.314 49.93 0.096 41.63 0.100 43.87 0.093 41.91 0.090 41.76
10 0.499 53.08 0.141 47.04 0.151 49.52 0.141 45.92 0.137 45.72
100 2 0.036 17.27 0.027 25.87 0.028 27.21 0.024 22.44 0.022 22.65
4 0.135 24.74 0.063 31.24 0.065 32.14 0.057 27.51 0.054 28.48
6 0.277 26.42 0.099 33.51 0.113 35.02 0.097 31.42 0.098 31.99
8 0.570 29.63 0.154 35.44 0.169 38.68 0.147 34.51 0.147 34.82
10 0.830 30.46 0.221 38.73 0.238 40.56 0.221 37.22 0.219 37.81
200 2 0.098 19.98 0.054 26.81 0.059 29.40 0.051 26.68 0.052 27.49
4 0.370 22.05 0.121 28.88 0.126 30.43 0.116 28.23 0.111 28.13
6 0.825 23.80 0.216 33.26 0.243 37.04 0.208 31.44 0.202 31.59
8 1.574 24.02 0.333 35.37 0.344 36.59 0.299 31.36 0.293 32.24
10 2.391 25.59 0.523 40.48 0.557 42.38 0.500 37.77 0.489 38.27
500 2 0.241 9.62 0.150 25.82 0.156 27.45 0.121 21.26 0.118 21.82
4 1.131 11.73 0.490 37.29 0.505 38.14 0.388 29.03 0.371 28.75
6 3.335 16.14 0.884 38.74 0.993 42.53 0.770 32.16 0.727 32.02
8 6.072 17.01 1.281 39.89 1.358 41.56 1.057 33.45 1.006 33.16
10 9.968 18.62 2.138 48.18 2.266 50.49 1.653 36.62 1.646 37.34
1000 2 0.716 7.78 0.386 28.34 0.414 29.86 0.321 22.47 0.320 23.51
4 3.306 9.75 1.443 45.45 1.484 45.77 1.214 37.59 1.231 38.65
6 8.109 10.88 2.879 49.66 3.036 51.44 2.108 35.86 2.132 36.42
8 20.743 13.95 4.956 55.43 5.132 56.06 3.942 42.44 3.642 40.38
10 37.590 17.52 7.712 59.15 7.941 59.95 5.819 43.43 5.893 45.85
Table Options

Download as excel

n m PC method PPA1 PPA2 Algorithm 1 Algorithm 2
CPU Iter. CPU Iter. CPU Iter. CPU Iter. CPU Iter.
50 2 0.034 34.45 0.018 31.32 0.018 32.93 0.018 29.84 0.015 30.34
4 0.093 40.32 0.044 36.60 0.046 37.78 0.044 36.39 0.043 37.11
6 0.197 45.92 0.071 39.23 0.072 40.92 0.068 37.82 0.063 38.08
8 0.314 49.93 0.096 41.63 0.100 43.87 0.093 41.91 0.090 41.76
10 0.499 53.08 0.141 47.04 0.151 49.52 0.141 45.92 0.137 45.72
100 2 0.036 17.27 0.027 25.87 0.028 27.21 0.024 22.44 0.022 22.65
4 0.135 24.74 0.063 31.24 0.065 32.14 0.057 27.51 0.054 28.48
6 0.277 26.42 0.099 33.51 0.113 35.02 0.097 31.42 0.098 31.99
8 0.570 29.63 0.154 35.44 0.169 38.68 0.147 34.51 0.147 34.82
10 0.830 30.46 0.221 38.73 0.238 40.56 0.221 37.22 0.219 37.81
200 2 0.098 19.98 0.054 26.81 0.059 29.40 0.051 26.68 0.052 27.49
4 0.370 22.05 0.121 28.88 0.126 30.43 0.116 28.23 0.111 28.13
6 0.825 23.80 0.216 33.26 0.243 37.04 0.208 31.44 0.202 31.59
8 1.574 24.02 0.333 35.37 0.344 36.59 0.299 31.36 0.293 32.24
10 2.391 25.59 0.523 40.48 0.557 42.38 0.500 37.77 0.489 38.27
500 2 0.241 9.62 0.150 25.82 0.156 27.45 0.121 21.26 0.118 21.82
4 1.131 11.73 0.490 37.29 0.505 38.14 0.388 29.03 0.371 28.75
6 3.335 16.14 0.884 38.74 0.993 42.53 0.770 32.16 0.727 32.02
8 6.072 17.01 1.281 39.89 1.358 41.56 1.057 33.45 1.006 33.16
10 9.968 18.62 2.138 48.18 2.266 50.49 1.653 36.62 1.646 37.34
1000 2 0.716 7.78 0.386 28.34 0.414 29.86 0.321 22.47 0.320 23.51
4 3.306 9.75 1.443 45.45 1.484 45.77 1.214 37.59 1.231 38.65
6 8.109 10.88 2.879 49.66 3.036 51.44 2.108 35.86 2.132 36.42
8 20.743 13.95 4.956 55.43 5.132 56.06 3.942 42.44 3.642 40.38
10 37.590 17.52 7.712 59.15 7.941 59.95 5.819 43.43 5.893 45.85
Table 4.  Numerical results for CMFWP under gauge
n m PC method PPA1 PPA2 Algorithm 1 Algorithm 2
CPU Iter. CPU Iter. CPU Iter. CPU Iter. CPU Iter.
50 2 0.077 58.93 0.038 52.66 0.037 53.87 0.028 39.33 0.028 40.22
4 0.219 77.85 0.084 60.53 0.086 61.71 0.066 49.14 0.063 46.94
6 0.471 86.40 0.141 65.16 0.145 68.42 0.116 54.87 0.111 54.47
8 0.859 101.61 0.231 76.47 0.222 76.93 0.183 62.82 0.183 64.13
10 1.238 103.24 0.300 77.12 0.306 78.26 0.264 65.93 0.254 65.08
100 2 0.130 47.82 0.053 38.50 0.055 39.37 0.038 28.84 0.039 29.39
4 0.416 56.39 0.133 48.53 0.131 48.98 0.101 37.98 0.101 39.32
6 0.778 58.80 0.239 57.14 0.235 57.93 0.175 43.07 0.174 44.15
8 1.922 86.76 0.351 62.63 0.369 66.90 0.294 52.46 0.279 51.38
10 2.986 90.21 0.507 67.44 0.514 67.12 0.436 56.77 0.426 56.10
200 2 0.146 21.38 0.077 29.11 0.081 30.09 0.056 21.32 0.058 23.21
4 0.634 31.07 0.201 37.14 0.204 37.92 0.148 27.76 0.156 30.00
6 1.363 33.58 0.384 45.09 0.390 45.95 0.297 34.45 0.293 35.05
8 2.796 37.18 0.622 50.46 0.651 53.04 0.473 38.48 0.510 42.54
10 8.218 79.37 1.112 69.73 1.128 69.27 0.941 57.59 0.934 58.11
500 2 0.280 9.53 0.166 23.66 0.198 29.26 0.139 20.84 0.153 23.46
4 1.686 16.28 0.579 37.75 0.624 40.80 0.420 27.21 0.470 31.33
6 5.626 22.22 1.072 41.50 1.048 40.41 0.815 31.00 0.854 33.42
8 9.956 27.75 1.826 43.97 2.061 48.70 1.529 35.96 1.601 38.73
10 23.448 43.14 2.762 53.52 2.831 53.89 2.067 39.27 2.228 43.10
1000 2 0.700 7.49 0.379 23.81 0.391 24.30 0.314 19.23 0.266 16.97
4 3.450 8.06 1.385 32.74 1.451 33.15 0.982 22.62 1.060 24.86
6 7.448 9.23 2.457 37.53 2.721 40.88 1.880 28.29 2.050 31.22
8 14.150 10.25 4.177 41.70 4.380 42.95 2.981 29.10 3.212 32.05
10 39.917 13.78 8.838 51.66 9.151 51.74 6.629 38.16 6.997 41.41
Table Options

Download as excel

n m PC method PPA1 PPA2 Algorithm 1 Algorithm 2
CPU Iter. CPU Iter. CPU Iter. CPU Iter. CPU Iter.
50 2 0.077 58.93 0.038 52.66 0.037 53.87 0.028 39.33 0.028 40.22
4 0.219 77.85 0.084 60.53 0.086 61.71 0.066 49.14 0.063 46.94
6 0.471 86.40 0.141 65.16 0.145 68.42 0.116 54.87 0.111 54.47
8 0.859 101.61 0.231 76.47 0.222 76.93 0.183 62.82 0.183 64.13
10 1.238 103.24 0.300 77.12 0.306 78.26 0.264 65.93 0.254 65.08
100 2 0.130 47.82 0.053 38.50 0.055 39.37 0.038 28.84 0.039 29.39
4 0.416 56.39 0.133 48.53 0.131 48.98 0.101 37.98 0.101 39.32
6 0.778 58.80 0.239 57.14 0.235 57.93 0.175 43.07 0.174 44.15
8 1.922 86.76 0.351 62.63 0.369 66.90 0.294 52.46 0.279 51.38
10 2.986 90.21 0.507 67.44 0.514 67.12 0.436 56.77 0.426 56.10
200 2 0.146 21.38 0.077 29.11 0.081 30.09 0.056 21.32 0.058 23.21
4 0.634 31.07 0.201 37.14 0.204 37.92 0.148 27.76 0.156 30.00
6 1.363 33.58 0.384 45.09 0.390 45.95 0.297 34.45 0.293 35.05
8 2.796 37.18 0.622 50.46 0.651 53.04 0.473 38.48 0.510 42.54
10 8.218 79.37 1.112 69.73 1.128 69.27 0.941 57.59 0.934 58.11
500 2 0.280 9.53 0.166 23.66 0.198 29.26 0.139 20.84 0.153 23.46
4 1.686 16.28 0.579 37.75 0.624 40.80 0.420 27.21 0.470 31.33
6 5.626 22.22 1.072 41.50 1.048 40.41 0.815 31.00 0.854 33.42
8 9.956 27.75 1.826 43.97 2.061 48.70 1.529 35.96 1.601 38.73
10 23.448 43.14 2.762 53.52 2.831 53.89 2.067 39.27 2.228 43.10
1000 2 0.700 7.49 0.379 23.81 0.391 24.30 0.314 19.23 0.266 16.97
4 3.450 8.06 1.385 32.74 1.451 33.15 0.982 22.62 1.060 24.86
6 7.448 9.23 2.457 37.53 2.721 40.88 1.880 28.29 2.050 31.22
8 14.150 10.25 4.177 41.70 4.380 42.95 2.981 29.10 3.212 32.05
10 39.917 13.78 8.838 51.66 9.151 51.74 6.629 38.16 6.997 41.41
[1]

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

T. A. Shaposhnikova, M. N. Zubova. Homogenization problem for a parabolic variational inequality with constraints on subsets situated on the boundary of the domain. Networks & Heterogeneous Media, 2008, 3 (3) : 675-689. doi: 10.3934/nhm.2008.3.675
[3]

Junfeng Yang. Dynamic power price problem: An inverse variational inequality approach. Journal of Industrial & Management Optimization, 2008, 4 (4) : 673-684. doi: 10.3934/jimo.2008.4.673
[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]

Junkee Jeon, Jehan Oh. Valuation of American strangle option: Variational inequality approach. Discrete & Continuous Dynamical Systems - B, 2019, 24 (2) : 755-781. doi: 10.3934/dcdsb.2018206
[6]

Wenyan Zhang, Shu Xu, Shengji Li, Xuexiang Huang. Generalized weak sharp minima of variational inequality problems with functional constraints. Journal of Industrial & Management Optimization, 2013, 9 (3) : 621-630. doi: 10.3934/jimo.2013.9.621
[7]

Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733
[8]

S. J. Li, Z. M. Fang. On the stability of a dual weak vector variational inequality problem. Journal of Industrial & Management Optimization, 2008, 4 (1) : 155-165. doi: 10.3934/jimo.2008.4.155
[9]

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

Rong Hu, Ya-Ping Fang, Nan-Jing Huang. Levitin-Polyak well-posedness for variational inequalities and for optimization problems with variational inequality constraints. Journal of Industrial & Management Optimization, 2010, 6 (3) : 465-481. doi: 10.3934/jimo.2010.6.465
[11]

Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1795-1807. doi: 10.3934/jimo.2018123
[12]

Constantine M. Dafermos. A variational approach to the Riemann problem for hyperbolic conservation laws. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 185-195. doi: 10.3934/dcds.2009.23.185
[13]

Yekini Shehu, Olaniyi Iyiola. On a modified extragradient method for variational inequality problem with application to industrial electricity production. Journal of Industrial & Management Optimization, 2019, 15 (1) : 319-342. doi: 10.3934/jimo.2018045
[14]

X. X. Huang, Xiaoqi Yang. Levitin-Polyak well-posedness in generalized variational inequality problems with functional constraints. Journal of Industrial & Management Optimization, 2007, 3 (4) : 671-684. doi: 10.3934/jimo.2007.3.671
[15]

Jorge A. Becerril, Javier F. Rosenblueth. Necessity for isoperimetric inequality constraints. Discrete & Continuous Dynamical Systems - A, 2017, 37 (3) : 1129-1158. doi: 10.3934/dcds.2017047
[16]

Takeshi Fukao, Nobuyuki Kenmochi. Quasi-variational inequality approach to heat convection problems with temperature dependent velocity constraint. Discrete & Continuous Dynamical Systems - A, 2015, 35 (6) : 2523-2538. doi: 10.3934/dcds.2015.35.2523
[17]

Liping Pang, Fanyun Meng, Jinhe Wang. Asymptotic convergence of stationary points of stochastic multiobjective programs with parametric variational inequality constraint via SAA approach. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1653-1675. doi: 10.3934/jimo.2018116
[18]

Fioralba Cakoni, Houssem Haddar. A variational approach for the solution of the electromagnetic interior transmission problem for anisotropic media. Inverse Problems & Imaging, 2007, 1 (3) : 443-456. doi: 10.3934/ipi.2007.1.443
[19]

Sergey V. Bolotin, Piero Negrini. Variational approach to second species periodic solutions of Poincaré of the 3 body problem. Discrete & Continuous Dynamical Systems - A, 2013, 33 (3) : 1009-1032. doi: 10.3934/dcds.2013.33.1009
[20]

Takeshi Fukao. Variational inequality for the Stokes equations with constraint. Conference Publications, 2011, 2011 (Special) : 437-446. doi: 10.3934/proc.2011.2011.437

2018 Impact Factor: 1.025

Tools

Metrics

  • PDF downloads (51)
  • HTML views (951)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences