The Capacitated  Facility  Location Problem
line.jpg (1129 bytes)

ballred.gif (861 bytes)  Home ballred.gif (861 bytes)  The Capacitated Facility Location Problem ballred.gif (861 bytes)

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

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  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

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  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

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

 


        
Class 4.
 
  20 tasks.  Facilities capacity is 40

   
All benchmarks of class 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

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

 


       
Class 5.
 
  20 tasks.  Facilities capacity is 50


All benchmarks of class 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

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

ballred.gif (861 bytes) Home ballred.gif (861 bytes)  The Capacitated  Facility  Location Problem