A variational inequality approach for constrained multifacility Weber problem under gauge

Jianlin Jiang; Shun Zhang; Su Zhang; Jie Wen

doi:10.3934/jimo.2017091

Article Contents

2018, Volume 14, Issue 3: 1085-1104. Doi: 10.3934/jimo.2017091

This issue Previous Article Optimal risk control and dividend strategies in the presence of two reinsurers: Variance premium principle Next Article Portfolio procurement policies for budget-constrained supply chains with option contracts and external financing

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

* Corresponding author: Su Zhang
* Corresponding author: Su Zhang

Received: January 31, 2016

Revised: April 30, 2017

Early access: August 2017

Published: June 2018

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.

Abstract Full Text(HTML) Figure(0) / Table(4) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 90B85; Secondary: 90C33.

Citation:

Full Text(HTML)

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

| Show Table

DownLoad: CSV

Table 2. HAP, GHAP, SHAP, SGHAP, Algorithm 1 and Algorithm 2 for MFWP

m		HAP				GHAP				SHAP	SGHAP	Algo. 1	Algo. 2
m		ε=50	ε=5	ε=0.5	ε=0.05	ε=50	s=5	ε=0.5	ε=0.05	SHAP	SGHAP	Algo. 1	Algo. 2
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

| Show Table

DownLoad: CSV

Table 3. Numerical results for CMFWP under Euclidean distances

n	m	PC method		PPA1		PPA2		Algorithm 1		Algorithm 2
n	m	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

| Show Table

DownLoad: CSV

Table 4. Numerical results for CMFWP under gauge

n	m	PC method		PPA1		PPA2		Algorithm 1		Algorithm 2
n	m	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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.