The Capacitated  Facility  Location Problem

  Home   The Capacitated Facility Location Problem

Benchmarks

We consider 5 benchmarks classes. All of them have the same matrices {p_ij} and {g_ij} and differ only by facilities capacity.  For the first class facilities capacity are equal 10. For another classes the facilities capacity are equally 20, 30, 40 и 50 standard units of produce correspondingly.

In the following Tables we dive the computational results. In the first column there are codes of instamces as text file.  
Optimal  values of objective function are obtained by Igor Vasiliev (Irkutsk).
                     

Class 1.   20 tasks.  Facilities capacity is 10	All benchmarks of class 1 сap-10.zip  836 Kb
LP Column  contains  lower bounds obtained by linear program; MLP Column  contains lower bounds obtained by relaxation of integrality of  xij. OPT Column  contains  optimal  values of objective function. UB Column  contains upper bounds

Code	LP	MLP	OPT	UB	Feasible solution  (Set of selected  facilities)	Destination
1	2769,04	2796,0	2842,8	2894,7	1, 5, 11, 13, 17, 20, 23, 25, 26, 29, 30, 31, 33, 42, 51, 53, 58, 72, 78, 79, 86, 94	show
2	2893,92	2916,4	2969,6	3016,6	1, 5, 8, 13, 19, 21, 22, 23, 29, 40, 54, 58, 60, 61, 64, 72, 80, 81, 82, 91, 98	show
3	2960,90	2995,8	3053,3	3147,7	3, 11, 17, 28, 34, 36, 43, 46, 52, 53, 55, 56, 57, 64, 66, 68, 73, 76, 81, 82, 85, 86, 90	show
4	2841,61	2866,4	2943,1	3004,2	8, 9, 10, 22, 25, 27, 28, 30, 33, 34, 36, 52, 60, 63, 68, 74, 75, 76, 79, 80, 81, 100	show
5	2897,74	2911,4	2974,5	3077,1	2, 4, 5, 6, 7, 18, 19, 22, 25, 27, 34, 36, 39, 57, 58, 71, 82, 85, 87, 92, 96, 98	show
6	2967,66	2982,2	3040,1	3100,2	12, 14, 15, 19, 24, 29, 36, 39, 54, 56, 61, 62, 63, 64, 66, 67, 68, 74, 75, 78, 79, 80, 86, 91	show
7	2922,90	2960,6	3013,7	3114,9	1, 4, 6, 7, 9, 10, 18, 21, 23, 25, 33, 54, 55, 62, 66, 82, 86, 87, 88, 91, 99, 100	show
8	2825,37	2849,9	2891,4	2966,5	7, 9, 22, 29, 40, 44, 47, 50, 51, 55, 57, 58, 63, 64, 66, 67, 76, 78, 80, 86, 88, 94	show
9	2888,47	2924,4	2984,9	3035,1	2, 4, 8, 17, 20, 22, 27, 33, 34, 37, 39, 40, 46, 52, 55, 65, 67, 76, 84, 88, 93, 94, 97	show
10	2926,47	2967,9	3029,3	3112,0	10, 15, 16, 17, 25, 29, 32, 35, 41, 47, 50, 55, 61, 69, 72, 75, 76, 78, 79, 86, 94, 95, 99	show
11	2924,95	2944,9	3016,4	3085,1	3, 4, 5, 11, 16, 18, 21, 29, 49, 56, 65, 67, 68, 71, 74, 76, 77, 78, 80, 81, 84, 90, 91	show
12	2906,06	2938,6	3003,5	3090,0	3, 8, 19, 24, 30, 35, 39, 43, 49, 62, 69, 72, 75, 76, 77, 78, 82, 85, 86, 88, 91, 93, 96	show
13	2866,65	2895,6	2954,6	3032,0	3, 4, 6, 10, 19, 28, 30, 34, 35, 36, 39, 42, 43, 51, 66, 68, 80, 85, 87, 89, 90, 93, 97, 98	show
14	2859,76	2884,3	2936,4	3016,8	1, 5, 9, 11, 15, 17, 19, 40, 42, 46, 48, 56, 62, 66, 69, 74, 75, 77, 78, 83, 85	show
15	2796,68	2827,9	2886,1	2939,6	2, 16, 19, 32, 35, 37, 42, 45, 46, 47, 57, 61, 62, , 64, 67, 77, 78, 81, 87, 92, 93	show
16	2862,12	2869,0	2926,4	2986,7	3, 6, 13, 16, 19, 23, 24, 43, 49, 50, 51, 56, 61, 64, 65, 67, 73, 75, 86, 89, 91	show
17	2910,78	2939,8	2992,6	3045,2	5, 7, 9, 10, 13, 16, 23, 28, 35, 36, 45, 47, 58, 60, 69, 74, 78, 79, 80, 90, 96, 99	show
18	2812,08	2830,4	2897,3	2945,7	2, 6, 8, 9, 15, 17, 24, 28, 33, 41, 48, 52, 56, 61, 63, 77, 81, 82, 84, 89, 92	show
19	2856,11	2879,7	2938,3	2969,3	2, 8, 11, 21, 23, 25, 27, 33, 34, 42, 44, 46, 47, 50, 59, 75, 76, 84, 86, 88, 95, 98, 100	show
20	2855,65	2882,3	2940,0	3023,2	3, 4, 6, 7, 12, 15, 19, 21, 24, 26, 32, 39, 42, 48, 52, 58, 61, 63, 66, 80, 87, 93, 99	show

 

Class 2.   20 tasks.  Facilities capacity is 20

All benchmarks of class 2 cap-20.zip 836 Kb

LP Column  contains  lower bounds obtained by linear program;
MLP Column  contains lower bounds obtained by relaxation of integrality of  x_ij.
OPT Column  contains  optimal  values of objective function.
UB Column  contains upper bounds 

Code	LP	OPT	UB	Feasible solution  (Set of selected  facilities)	Destination
1	2049,18	2110,839	2130,4	1, 5, 11, 16, 17, 23, 25, 29, 44, 53, 73, 75, 85, 86, 94	show
2	2151,964	2196,111	2224,2	5, 6, 21, 22, 24, 29, 40, 43, 51, 58, 61, 66, 80, 88, 97	show
3	2186,485	2250,047	2279,9	10, 18, 26, 31, 52, 53, 55, 66, 68, 69, 73, 84, 85, 86, 90	show
4	2095,343	2164,932	2183,0	3, 8, 9, 10, 19, 22, 25, 27, 28, 33, 38, 56, 60, 75, 93	show
5	2089,726	2145,423	2176,2	2, 4, 7, 12, 18, 19, 21, 22, 40, 80, 81, 82, 85, 87, 92, 94	show
6	2204,322	2273,843	2303,1	12, 19, 23, 29, 39, 56, 57, 60, 61, 62, 68, 76, 78, 80, 84, 91	show
7	2170,993	2224,963	2265,1	1, 2, 7, 10, 18, 21, 25, 28, 33, 37, 49, 59, 73, 87, 91, 98	show
8	2098,142	2140,044	2156,4	7, 20, 29, 40, 47, 50, 51, 55, 57, 63, 71, 76, 86, 88	show
9	2157,882	2216,528	2246,4	22, 24, 26, 29, 33, 34, 39, 40, 44, 46, 55, 60, 63, 77, 90, 97	show
10	2142,529	2216,789	2240,4	2, 6, 10, 12, 29, 35, 50, 53, 55, 60, 61, 69, 70, 76, 79, 94	show
11	2168,987	2230,958	2261,5	3, 5, 7, 8, 11, 16, 18, 44, 49, 67, 68, 77, 78, 81, 84, 88	show
12	2160,239	2225,163	2254,0	13, 14, 19, 21, 40, 52, 69, 72, 74, 75, 77, 78, 82, 85, 86, 93	show
13	2090,554	2160,767	2175,0	3, 4, 19, 30, 39, 43, 68, 70, 80, 85, 87, 89, 90, 93, 95, 98	show
14	2160,221	2226,947	2254,1	1, 9, 15, 19, 20, 42, 43, 45, 46, 54, 59, 62, 69, 74, 79, 96	show
15	2092,174	2156,231	2184,9	2, 6, 10, 12, 16, 24, 26, 35, 39, 42, 47, 51, 57, 61, 93, 99	show
16	2154,244	2210,485	2235,6	6, 13, 19, 20, 33, 38, 43, 61, 67, 68, 71, 73, 88, 91, 98	show
17	2172,755	2239,593	2263,2	2, 5, 8, 9, 16, 30, 35, 36, 47, 64, 66, 69, 79, 82, 85, 90	show
18	2105,997	2175,144	2198,9	1, 6, 8, 12, 15, 24, 33, 41, 49, 59, 77, 82, 84, 91, 96	show
19	2096,486	2153,092	2183,4	3, 16, 23, 33, 34, 42, 44, 47, 50, 68, 73, 76, 86, 92 100	show
20	2119,986	2178,856	2218,2	4, 6, 7, 15, 22, 24, 32, 39, 52, 57, 58, 66, 80, 84, 99	show

Class 3.   20 tasks.  Facilities capacity is 30

All benchmarks of class 3 cap-30.zip 836 Kb

LP Column  contains  lower bounds obtained by linear program;
MLP Column  contains lower bounds obtained by relaxation of integrality of  x_ij.
OPT Column  contains  optimal  values of objective function.
UB Column  contains upper bounds  

Code	LP	OPT	UB	Feasible solution  (Set of selected  facilities)	Destination
1	1822.6	1923.9	1924.2	5, 11, 16, 25, 29, 40, 44, 50, 73, 86, 94 100	show
2	1914.9	2015.7	2032.1	5, 6, 8, 19, 22, 40, 44, 54, 58, 61, 88, 91	show
3	1939.3	2053.4	2084.1	21, 31, 35, 36, 42, 46, 57, 66, 68, 69, 72, 76, 90	show
4	1876.7	2000.8	2015.9	12, 25, 26, 28, 38, 52, 59, 60, 68, 75, 76, 81	show
5	1833.0	1942.8	1968.8	2, 8, 18, 21, 34, 39, 40, 72, 80, 85, 94	show
6	1976.9	2102.1	2123.5	9, 12, 23, 24, 29, 36, 54, 61, 76, 78, 84, 91, 94	show
7	1928.2	2041.0	2088.1	5, 17, 21, 27, 28, 33, 38, 39, 42, 43, 67, 76	show
8	1870.4	1978.4	1990.8	4, 7, 40, 43, 50, 51, 55, 57, 63, 75, 76, 88	show
9	1890.1	1992.5	2005.5	17, 18, 24, 27, 33, 34, 43, 46, 60, 76, 77, 87	show
10	1918.2	2062.5	2066.6	2, 12, 29, 35, 50, 61, 68, 69, 76, 79, 80, 89, 94	show
11	1927.8	2024.8	2036.8	3, 5, 8, 11, 18, 29, 44, 67, 78, 81, 84, 91	show
12	1934.1	2050.9	2084.5	3, 6, 8, 14, 19, 35, 46, 53, 59, 72, 77, 91	show
13	1853.1	1979.0	1996.9	3, 4, 23, 25, 34, 42, 58, 61, 68, 85, 87, 90, 98	show
14	1941.9	2053.7	2075.2	4, 15, 20, 26, 36, 50, 55, 56, 62, 66, 69, 74, 77	show
15	1855.8	1944.9	1944.9	2, 8, 24, 26, 29, 39, 42, 47, 61, 72, 93, 99	show
16	1927.6	2032.1	2042.2	19, 22, 28, 38, 48, 61, 67, 68, 71, 73, 88, 91	show
17	1954.2	2059.7	2063.7	1, 6, 7, 9, 10, 16, 28, 35, 45, 47, 60, 66, 69	show
18	1883.5	2015.0	2021.6	1, 6, 15, 17, 24, 41, 74, 75, 77, 82, 91, 93	show
19	1856.6	1962.1	1962.1	2, 16, 33, 34, 44, 47, 60, 69, 73, 86, 92 100	show
20	1886.9	1961.3	1973.3	4, 7, 10, 15, 24, 27, 32, 39, 44, 52, 57, 58, 84	show

 

LP Column  contains  lower bounds obtained by linear program;
MLP Column  contains lower bounds obtained by relaxation of integrality of  x_ij.
OPT Column  contains  optimal  values of objective function.
UB Column  contains upper bounds 

Code	LP	OPT	UB	Feasible solution  (Set of selected  facilities)	Destination
1	1760.5	1879.9	1879.9	11, 25, 29, 40, 44, 50, 73, 86, 94, 100	show
2	1851.1	1959.9	1959.9	6, 8, 19, 22, 40, 54, 61, 66, 68, 88, 91	show
3	1874.1	1990.3	2002.7	3, 11, 21, 36, 42, 57, 69, 72, 80, 82, 90	show
4	1829.6	1977.2	1978.0	3, 7, 12, 20, 25, 28, 33, 38, 59, 60, 93	show
5	1757.4	1869.4	1881.8	2, 18, 34, 39, 40, 48, 80, 85, 91, 92	show
6	1919.0	2045.8	2053.8	9, 12, 19, 29, 36, 61, 75, 76, 78, 84, 94	show
7	1844.6	1976.3	1993.7	1, 7, 8, 17, 21, 28, 30, 33, 38, 39, 42, 91	show
8	1794.2	1905.3	1942.0	4, 7, 22, 40, 43, 50, 55, 57, 62, 63, 76	show
9	1810.5	1931.1	1931.1	17, 18, 33, 39, 45, 49, 60, 67, 74, 76, 84	show
10	1878.0	1989.9	2019.5	10, 12, 31, 61, 66, 67, 68, 69, 76, 79, 80	show
11	1852.0	1956.2	1978.5	3, 5, 8, 18, 29, 44, 67, 78, 81, 84, 91	show
12	1867.0	1983.9	2007.6	6, 10, 14, 19, 32, 53, 59, 72, 78, 82, 91	show
13	1802.0	1919.9	1919.9	3, 4, 25, 42, 58, 61, 62, 68, 85, 87, 98	show
14	1880.0	1998.2	2002.7	4, 9, 15, 20, 42, 43, 50, 59, 74, 77, 100	show
15	1795.1	1890.4	1890.4	2, 8, 24, 29, 39, 42, 72, 74, 79, 93, 99	show
16	1850.6	1966.6	1966.6	4, 8, 20, 28, 33, 38, 43, 48, 61, 68, 71, 73	show
17	1887.1	2015.8	2037.0	1, 2, 8, 9, 10, 16, 17, 35, 66, 69, 79	show
18	1836.5	1976.9	1987.6	1, 15, 17, 46, 74, 75, 77, 82, 91, 92, 93	show
19	1801.3	1923.1	1923.1	16, 33, 34, 44, 47, 53, 70, 73, 76, 92, 100	show
20	1824.0	1939.2	1939.2	4, 7, 10, 15, 24, 27, 32, 39, 44, 57, 58, 84	show

LP Column  contains  lower bounds obtained by linear program;
MLP Column  contains lower bounds obtained by relaxation of integrality of  x_ij.
OPT Column  contains  optimal  values of objective function.
UB Column  contains upper bounds 

Code	LP	OPT	UB	Feasible solution  (Set of selected  facilities)	Destination
1	1748.0	1879.9	1879.9	11, 25, 29, 40, 44, 50, 73, 86, 94, 100	show
2	1740.2	1950.5	1950.5	5, 6, 8, 21, 22, 32, 54, 61, 91, 97	show
3	1863.8	1989.9	1989.9	3, 4, 21, 36, 38, 69, 72, 73, 82, 90, 99	show
4	1821.3	1974.0	1974.0	3, 7, 12, 20, 25, 28, 33, 38, 59, 60, 93	show
5	1742.1	1860.2	1860.2	2, 8, 20, 34, 39, 40, 48, 72, 80, 85	show
6	1904.3	2037.8	2044.1	9, 12, 23, 24, 29, 36, 54, 61, 76, 78, 84	show
7	1821.6	1975.6	1975.6	1, 7, 8, 21, 28, 30, 33, 38, 39, 42, 91	show
8	1773.2	1897.7	1897.7	4, 7, 22, 40, 43, 50, 55, 57, 62, 63	show
9	1796.5	1915.7	1915.7	17, 18, 33, 39, 45, 49, 60, 67, 74, 84	show
10	1875.0	1989.9	1998.4	10, 12, 31, 61, 66, 67, 68, 69, 76, 79, 80	show
11	1839.2	1938.5	1938.5	2, 8, 18, 38, 45, 67, 78, 84, 88, 91	show
12	1852.1	1965.3	1967.3	1, 3, 14, 15, 21, 35, 37, 46, 53, 82	show
13	1791.8	1918.5	1918.5	3, 4, 30, 39, 42, 58, 61, 63, 68, 87, 95	show
14	1866.1	1995.8	1995.8	4, 9, 15, 20, 42, 43, 50, 59, 74, 77, 100	show
15	1786.3	1879.7	1879.7	2, 8, 24, 29, 39, 42, 74, 79, 93, 99	show
16	1836.1	1953.7	1957.6	4, 20, 38, 43, 48, 50, 54, 61, 71, 73	show
17	1874.7	2013.9	2028.5	8, 10, 35, 36, 37, 47, 60, 64, 69, 79, 85	show
18	1829.3	1974.2	1975.2	8, 12, 29, 33, 38, 41, 60, 75, 77, 93, 96	show
19	1793.1	1915.3	1915.3	16, 33, 34, 44, 47, 53, 70, 73, 76, 92, 100	show
20	1815.3	1939.2	1939.2	4, 7, 10, 15, 24, 27, 32, 39, 44, 57, 58, 84	show

Home   The Capacitated  Facility  Location Problem