-
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
A variational inequality approach for constrained multifacility Weber problem under gauge
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 |
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.
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. |
[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. |
[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. |
[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.
|
[5] |
Z. Drezner,
Facility Location: A Survey of Applications and Methods, Springer, New York, 1995.
doi: 10.1007/978-1-4612-5355-6. |
[6] |
Z. Drezner and H. W. Hamacher,
Facility Location: Applications and Theory, Springer-Verlag, Berlin, 2002.
doi: 10.1007/978-3-642-56082-8. |
[7] |
R. Durier,
On Pareto optima, the Fermat-Weber problem and polyhedral gauges, Math. Program., 47 (1990), 65-79.
doi: 10.1007/BF01580853. |
[8] |
B. C. Eaves,
On the basic theorem of complememtarity, Math. Program., 1 (1971), 68-75.
doi: 10.1007/BF01584073. |
[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. |
[10] |
F. Facchinei and J. S. Pang,
Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003. |
[11] |
M. C. Ferris and C. Kanzow,
Engineering and economic applications of complementarity problems, SIAM Review, 39 (1997), 669-713.
doi: 10.1137/S0036144595285963. |
[12] |
B. S. He,
A new method for a class of linear variational inequalities, Math. Program., 66 (1994), 137-144.
doi: 10.1007/BF01581141. |
[13] |
B. S. He,
A modified projection and contraction method for a class of linear complementarity problems, J. Comput. Math., 14 (1996), 54-63.
|
[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. |
[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. |
[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. |
[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. |
[18] |
R. F. Love, J. G. Morris and G. O. Wesolowsky,
Facilities Location: Models and Methods, North-Holland, Amsterdam, 1988. |
[19] |
B. Martinet,
Regularision d'inéquations variationnelles par approximations successive, Revue Francaise d'Automatique et Informatique Recherche Opérationnelle, 4 (1970), 154-158.
|
[20] |
W. Miehle,
Link length minimization in networks, Oper. Res., 6 (1958), 232-243.
doi: 10.1287/opre.6.2.232. |
[21] |
H. Minkowski,
Theorie der konvexen Körper, Gesammelte Abhandlungen, Teubner, Berlin, 1911. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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.
|
[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.
|
[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. |
[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.
|
[33] |
C. Witzgall, Optimal location of a central facility, mathematical models and concepts, Report 8388, National Bureau of Standards, Washington DC, US, 1964. |
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. |
[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. |
[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. |
[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.
|
[5] |
Z. Drezner,
Facility Location: A Survey of Applications and Methods, Springer, New York, 1995.
doi: 10.1007/978-1-4612-5355-6. |
[6] |
Z. Drezner and H. W. Hamacher,
Facility Location: Applications and Theory, Springer-Verlag, Berlin, 2002.
doi: 10.1007/978-3-642-56082-8. |
[7] |
R. Durier,
On Pareto optima, the Fermat-Weber problem and polyhedral gauges, Math. Program., 47 (1990), 65-79.
doi: 10.1007/BF01580853. |
[8] |
B. C. Eaves,
On the basic theorem of complememtarity, Math. Program., 1 (1971), 68-75.
doi: 10.1007/BF01584073. |
[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. |
[10] |
F. Facchinei and J. S. Pang,
Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003. |
[11] |
M. C. Ferris and C. Kanzow,
Engineering and economic applications of complementarity problems, SIAM Review, 39 (1997), 669-713.
doi: 10.1137/S0036144595285963. |
[12] |
B. S. He,
A new method for a class of linear variational inequalities, Math. Program., 66 (1994), 137-144.
doi: 10.1007/BF01581141. |
[13] |
B. S. He,
A modified projection and contraction method for a class of linear complementarity problems, J. Comput. Math., 14 (1996), 54-63.
|
[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. |
[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. |
[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. |
[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. |
[18] |
R. F. Love, J. G. Morris and G. O. Wesolowsky,
Facilities Location: Models and Methods, North-Holland, Amsterdam, 1988. |
[19] |
B. Martinet,
Regularision d'inéquations variationnelles par approximations successive, Revue Francaise d'Automatique et Informatique Recherche Opérationnelle, 4 (1970), 154-158.
|
[20] |
W. Miehle,
Link length minimization in networks, Oper. Res., 6 (1958), 232-243.
doi: 10.1287/opre.6.2.232. |
[21] |
H. Minkowski,
Theorie der konvexen Körper, Gesammelte Abhandlungen, Teubner, Berlin, 1911. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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.
|
[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.
|
[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. |
[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.
|
[33] |
C. Witzgall, Optimal location of a central facility, mathematical models and concepts, Report 8388, National Bureau of Standards, Washington DC, US, 1964. |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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] |
Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial and Management Optimization, 2022, 18 (1) : 613-634. doi: 10.3934/jimo.2020171 |
[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 and Heterogeneous Media, 2008, 3 (3) : 675-689. doi: 10.3934/nhm.2008.3.675 |
[3] |
Gbeminiyi John Oyewole, Olufemi Adetunji. Solving the facility location and fixed charge solid transportation problem. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1557-1575. doi: 10.3934/jimo.2020034 |
[4] |
Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial and Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521 |
[5] |
Shahede Omidi, Jafar Fathali. Inverse single facility location problem on a tree with balancing on the distance of server to clients. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1247-1259. doi: 10.3934/jimo.2021017 |
[6] |
Junfeng Yang. Dynamic power price problem: An inverse variational inequality approach. Journal of Industrial and Management Optimization, 2008, 4 (4) : 673-684. doi: 10.3934/jimo.2008.4.673 |
[7] |
Francis Akutsah, Akindele Adebayo Mebawondu, Hammed Anuoluwapo Abass, Ojen Kumar Narain. A self adaptive method for solving a class of bilevel variational inequalities with split variational inequality and composed fixed point problem constraints in Hilbert spaces. Numerical Algebra, Control and Optimization, 2021 doi: 10.3934/naco.2021046 |
[8] |
Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $ k $-facility location problem with linear penalties. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056 |
[9] |
Junkee Jeon, Jehan Oh. Valuation of American strangle option: Variational inequality approach. Discrete and Continuous Dynamical Systems - B, 2019, 24 (2) : 755-781. doi: 10.3934/dcdsb.2018206 |
[10] |
Wenyan Zhang, Shu Xu, Shengji Li, Xuexiang Huang. Generalized weak sharp minima of variational inequality problems with functional constraints. Journal of Industrial and Management Optimization, 2013, 9 (3) : 621-630. doi: 10.3934/jimo.2013.9.621 |
[11] |
Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial and Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733 |
[12] |
Guowei Hua, Shouyang Wang, Chi Kin Chan, S. H. Hou. A fractional programming model for international facility location. Journal of Industrial and Management Optimization, 2009, 5 (3) : 629-649. doi: 10.3934/jimo.2009.5.629 |
[13] |
S. J. Li, Z. M. Fang. On the stability of a dual weak vector variational inequality problem. Journal of Industrial and Management Optimization, 2008, 4 (1) : 155-165. doi: 10.3934/jimo.2008.4.155 |
[14] |
Wenhui Shi. An epiperimetric inequality approach to the parabolic Signorini problem. Discrete and Continuous Dynamical Systems, 2020, 40 (3) : 1813-1846. doi: 10.3934/dcds.2020095 |
[15] |
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 and Management Optimization, 2010, 6 (3) : 465-481. doi: 10.3934/jimo.2010.6.465 |
[16] |
Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1795-1807. doi: 10.3934/jimo.2018123 |
[17] |
Liping Zhang, Soon-Yi Wu. Robust solutions to Euclidean facility location problems with uncertain data. Journal of Industrial and Management Optimization, 2010, 6 (4) : 751-760. doi: 10.3934/jimo.2010.6.751 |
[18] |
Yekini Shehu, Olaniyi Iyiola. On a modified extragradient method for variational inequality problem with application to industrial electricity production. Journal of Industrial and Management Optimization, 2019, 15 (1) : 319-342. doi: 10.3934/jimo.2018045 |
[19] |
Yarui Duan, Pengcheng Wu, Yuying Zhou. Penalty approximation method for a double obstacle quasilinear parabolic variational inequality problem. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022017 |
[20] |
Ouafa Belguidoum, Hassina Grar. An improved projection algorithm for variational inequality problem with multivalued mapping. Numerical Algebra, Control and Optimization, 2022 doi: 10.3934/naco.2022002 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]