Table 1.
MA, GMA, Algorithm 1 and Algorithm 2 for MFWP
-
Previous Article
Optimal risk control and dividend strategies in the presence of two reinsurers: Variance premium principle
- JIMO Home
- This Issue
-
Next Article
Portfolio procurement policies for budget-constrained supply chains with option contracts and external financing
July
2018, 14(3): 1085-1104.
doi: 10.3934/jimo.2017091
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.
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. |
| [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 |
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 | |
| 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 | |
| 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 | |
| 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] |
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 |
| [2] |
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 |
| [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, 2017, 13 (5) : 1-13. 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, 2017, 13 (5) : 1-23. 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
Other articles
by authors
[Back to Top]