P-median Problem   Benchmarks

Home Benchmarks Library P-median Problem

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 258 7.17 3, 6, 21, 36, 39, 42, 57, 72, 75, 78, 93, 108, 111, 114, 129, 144 247 4.82 2, 5, 8, 11, 38, 41, 44, 47, 73, 76, 79, 82, 109, 112, 115, 118 246 1.89 1, 4, 7, 10, 38, 41, 44, 47, 75, 78, 81, 84, 111, 114, 117, 120 235 26.38 26, 29, 32, 35, 63, 66, 69, 72, 99, 102, 105, 108, 134, 137, 140, 143 257 9.96 15, 18, 21, 24, 51, 54, 57, 60, 85, 88, 91, 94, 121, 124, 127, 130 236 3.76 2, 5, 8, 11, 38, 41, 44, 47, 74, 77, 80, 83, 110, 113, 116, 119 249 6.21 2, 5, 11, 32, 38, 41, 47, 68, 74, 77, 83, 104, 110, 113, 119, 140 239 23.01 3, 6, 9, 12, 39, 42, 45, 48, 74, 77, 80, 83, 109, 112, 115, 118 232 28.88 10, 13, 16, 19, 46, 49, 52, 55, 82, 85, 88, 91, 118, 121, 124, 127 244 6.23 26, 29, 32, 35, 63, 66, 69, 72, 97, 100, 103, 106, 135, 138, 141, 144 249 6.44 16, 25, 31, 34, 52, 61, 67, 70, 88, 97, 103, 106, 124, 133, 139, 142 247 6.43 25, 28, 31, 34, 62, 65, 68, 71, 97, 100, 103, 106, 133, 136, 139, 142 247 3.01 6, 9, 27, 36, 42, 45, 63, 72, 78, 81, 99, 108, 114, 117, 135, 144 250 23.20 13, 16, 19, 22, 51, 54, 57, 60, 85, 88, 91, 94, 121, 124, 127, 130 247 8.79 25, 28, 31, 34, 62, 65, 68, 71, 97, 100, 103, 106, 135, 138, 141, 144 253 27.67 8, 17, 26, 35, 44, 53, 62, 71, 80, 89, 98, 107, 116, 125, 134, 143 251 34.66 26, 29, 32, 35, 61, 64, 67, 70, 97, 100, 103, 106, 134, 137, 140, 143 243 29.22 8, 17, 26, 35, 44, 53, 62, 71, 80, 89, 98, 107, 116, 125, 134, 143 242 8.48 25, 28, 31, 34, 62, 65, 68, 71, 98, 101, 104, 107, 134, 137, 140, 143 249 8.01 1, 4, 7, 10, 38, 41, 44, 47, 75, 78, 81, 84, 111, 114, 117, 120 250 28.00 9, 12, 18, 27, 45, 48, 54, 63, 81, 84, 90, 99, 117, 120, 126, 135 249 30.12 27, 30, 33, 36, 63, 66, 69, 72, 97, 100, 103, 106, 134, 137, 140, 143 256 9.58 3, 6, 9, 12, 38, 41, 44, 47, 75, 78, 81, 84, 110, 113, 116, 119 239 7.74 7, 10, 16, 25, 43, 46, 52, 61, 79, 82, 88, 97, 115, 118, 124, 133 248 5.07 7, 13, 28, 34, 43, 49, 64, 70, 79, 85, 100, 106, 115, 121, 136, 142 232 26.72 27, 30, 33, 36, 61, 64, 67, 70, 99, 102, 105, 108, 134, 137, 140, 143 239 28.45 13, 16, 19, 34, 49, 52, 55, 70, 85, 88, 91, 106, 121, 124, 127, 142 247 31.17 3, 6, 9, 12, 38, 41, 44, 47, 74, 77, 80, 83, 110, 113, 116, 119 239 2.73 26, 29, 32, 35, 61, 64, 67, 70, 97, 100, 103, 106, 133, 136, 139, 142 226 3.32 5, 11, 14, 20, 41, 47, 50, 56, 77, 83, 86, 92, 113, 119, 122, 128

Home Benchmarks Library P-median Problem