ballred.gif (861 bytes) P-median Problem  ballred.gif (861 bytes) Benchmarks
line.jpg (1129 bytes)

ballred.gif (861 bytes) Home Benchmarks Library ballred.gif (861 bytes) P-median Problem ballred.gif (861 bytes)

Instances on Chess-Board

Let us glue boundaries of the 3k ×3k chess board so that we get a torus. Put r=3k. Each cell of the  torus has 8 neighboring cells. For example, the cell (1,1) has the following neighbors: (1,2), (1,r), (2,1), (2,2), (2,r), (r,1), (r,2), (r,r). Define  n=9k2, p=k2, I=J={1,…, n} and

where xij are random numbers taken in the set {0,1,2,3,4} with uniform distribution. The torus is divided into k2 squares by 9 cells in each of them. Every cover of the torus by k2 squares corresponds to a feasible solution for the p-median problem. Total number of  feasible solutions is 2·3k+1–9. The minimal distance between them is 2k. We denote this class of benchmarks by CBk. The instances for   k=4,  p=16,  n=m=144 are given in the table.

All instances on Chess-Board pm_chess.zip 129 Kb

Code The optimal value Duality 
gap (%)		 The optimal solution

334

 258

7.17 3, 6, 21, 36, 39, 42, 57, 72, 75, 78, 93, 108, 111, 114, 129, 144

 434

 247

4.82 2, 5, 8, 11, 38, 41, 44, 47, 73, 76, 79, 82, 109, 112, 115, 118

 534

 246

1.89 1, 4, 7, 10, 38, 41, 44, 47, 75, 78, 81, 84, 111, 114, 117, 120

 634

 235

26.38 26, 29, 32, 35, 63, 66, 69, 72, 99, 102, 105, 108, 134, 137, 140, 143

 734

 257

9.96 15, 18, 21, 24, 51, 54, 57, 60, 85, 88, 91, 94, 121, 124, 127, 130

 834

 236

3.76 2, 5, 8, 11, 38, 41, 44, 47, 74, 77, 80, 83, 110, 113, 116, 119

 934

 249

6.21 2, 5, 11, 32, 38, 41, 47, 68, 74, 77, 83, 104, 110, 113, 119, 140

1034

 239

23.01 3, 6, 9, 12, 39, 42, 45, 48, 74, 77, 80, 83, 109, 112, 115, 118

1134

 232

28.88 10, 13, 16, 19, 46, 49, 52, 55, 82, 85, 88, 91, 118, 121, 124, 127

1234

 244

6.23 26, 29, 32, 35, 63, 66, 69, 72, 97, 100, 103, 106, 135, 138, 141, 144

1334

 249

6.44 16, 25, 31, 34, 52, 61, 67, 70, 88, 97, 103, 106, 124, 133, 139, 142

1434

 247

6.43 25, 28, 31, 34, 62, 65, 68, 71, 97, 100, 103, 106, 133, 136, 139, 142

1534

 247

3.01 6, 9, 27, 36, 42, 45, 63, 72, 78, 81, 99, 108, 114, 117, 135, 144

1634

 250

23.20 13, 16, 19, 22, 51, 54, 57, 60, 85, 88, 91, 94, 121, 124, 127, 130

1734

 247

8.79 25, 28, 31, 34, 62, 65, 68, 71, 97, 100, 103, 106, 135, 138, 141, 144

1834

 253

27.67 8, 17, 26, 35, 44, 53, 62, 71, 80, 89, 98, 107, 116, 125, 134, 143

1934

 251

34.66 26, 29, 32, 35, 61, 64, 67, 70, 97, 100, 103, 106, 134, 137, 140, 143

2034

 243

29.22 8, 17, 26, 35, 44, 53, 62, 71, 80, 89, 98, 107, 116, 125, 134, 143

2134

 242

8.48 25, 28, 31, 34, 62, 65, 68, 71, 98, 101, 104, 107, 134, 137, 140, 143

2234

 249

8.01 1, 4, 7, 10, 38, 41, 44, 47, 75, 78, 81, 84, 111, 114, 117, 120

2334

 250

28.00 9, 12, 18, 27, 45, 48, 54, 63, 81, 84, 90, 99, 117, 120, 126, 135

2434

 249

30.12 27, 30, 33, 36, 63, 66, 69, 72, 97, 100, 103, 106, 134, 137, 140, 143

2534

 256

9.58 3, 6, 9, 12, 38, 41, 44, 47, 75, 78, 81, 84, 110, 113, 116, 119

2634

 239

7.74 7, 10, 16, 25, 43, 46, 52, 61, 79, 82, 88, 97, 115, 118, 124, 133

2734

 248

5.07 7, 13, 28, 34, 43, 49, 64, 70, 79, 85, 100, 106, 115, 121, 136, 142

2834

 232

26.72 27, 30, 33, 36, 61, 64, 67, 70, 99, 102, 105, 108, 134, 137, 140, 143

2934

 239

28.45 13, 16, 19, 34, 49, 52, 55, 70, 85, 88, 91, 106, 121, 124, 127, 142

3034

 247

31.17 3, 6, 9, 12, 38, 41, 44, 47, 74, 77, 80, 83, 110, 113, 116, 119

3134

 239

2.73 26, 29, 32, 35, 61, 64, 67, 70, 97, 100, 103, 106, 133, 136, 139, 142

3234

 226

3.32 5, 11, 14, 20, 41, 47, 50, 56, 77, 83, 86, 92, 113, 119, 122, 128

ballred.gif (861 bytes) Home Benchmarks Library ballred.gif (861 bytes) P-median Problem ballred.gif (861 bytes)