The Capacitated  Facility  Location Problem

Home   The Capacitated Facility Location Problem

Benchmarks

We consider 5 benchmarks classes. All of them have the same matrices {pij} and {gij} 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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  xij.
OPT
Column  contains  optimal  values of objective function.
UB
Column  contains upper bounds

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

 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  xij.
OPT
Column  contains  optimal  values of objective function.
UB
Column  contains upper bounds

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

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

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