P-median Problem   Benchmarks

Home Benchmarks Library P-median Problem

Instances on the Perfect Codes

Let Bk be a set of words (or vectors) of length k over an alphabet {0, 1}. A binary code of length  k is an arbitrary nonempty subset of Bk. Perfect binary code with distance 3 is a subset  C Ì Bk, |C| = 2k/(k + 1) such that Hamming distance d(c1, c2) ³ 3 for all c1, c2ÎC, c1¹ c2. These codes exist for k = 2r –1, r>1, integer.
Put n = 2k, n/(k+1), I J = {1,…, n}. Every element iÎI corresponds to a vertex x(i) of the binary hyper cube Z2k. Therefore, we may define a distance dij = d(x(i), x(j)) for any two elements i, j Î I. Now we define

where xij is a random number taken from the set {0, 1, 2, 3, 4} with uniform distribution.

Arbitrary perfect code C produces a partition of Z2k into p disjointed spheres of radius 1  and corresponds to a feasible solution of the p-median problem. Number of perfect codes grows  exponentially as k increases. The best lower bound is

The minimal distance between two perfect codes or feasible solutions is at least .

The instances for   k = 7,  p = 16, n = m = 128 are given in the table

(All instances on the Perfect Codes mp-pc.zip 109 Kb)

 Code The optimal value Duality  gap (%) The optimal solution 232 5.98 5, 12, 24, 25, 35, 46, 50, 63, 66, 79, 83, 94, 104, 105, 117, 124 217 2.72 2, 11, 23, 30, 40, 45, 49, 60, 69, 80, 84, 89, 99, 106, 118, 127 227 1.25 3, 13, 18, 32, 40, 42, 53, 59, 70, 76, 87, 89, 97, 111, 116, 126 219 1.96 1, 12, 23, 30, 38, 47, 52, 57, 72, 77, 82, 91, 99, 106, 117, 128 223 4.14 3, 13, 18, 32, 40, 42, 53, 59, 70, 76, 87, 89, 97, 111, 116, 126 215 1.46 3, 16, 22, 25, 37, 42, 52, 63, 66, 77, 87, 92, 104, 107, 113, 126 221 1.92 4, 14, 23, 25, 37, 43, 50, 64, 65, 79, 86, 92, 104, 106, 115, 125 217 2.48 2, 7, 27, 30, 44, 45, 49, 56, 73, 80, 84, 85, 99, 102, 122, 127 220 4.40 4, 9, 22, 31, 37, 48, 51, 58, 71, 78, 81, 92, 98, 107, 120, 125 223 1.51 4, 13, 23, 26, 38, 43, 49, 64, 65, 80, 86, 91, 103, 106, 116, 125 211 1.51 6, 12, 17, 31, 35, 45, 56, 58, 71, 73, 84, 94, 98, 112, 117, 123 226 2.77 3, 13, 24, 26, 34, 48, 53, 59, 70, 76, 81, 95, 103, 105, 116, 126 209 0.17 8, 11, 21, 26, 34, 45, 51, 64, 65, 78, 84, 95, 103, 108, 118, 121 226 0.17 7, 10, 22, 27, 36, 45, 49, 64, 65, 80, 84, 93, 102, 107, 119, 122 221 0.17 12, 13, 18, 23, 33, 40, 59, 62, 67, 70, 89, 96, 106, 111, 116 117 225 1.95 1, 8, 27, 30, 42, 47, 52, 53, 76, 77, 82, 87, 99, 102, 121, 128 222 1.74 4, 15, 21, 26, 38, 41, 51, 64, 65, 78, 88, 91, 103, 108, 114, 125 205 0.00 8, 11, 21, 26, 33, 46, 52, 63, 66, 77, 83, 96, 103, 108, 118, 121 226 0.77 4, 13, 23, 26, 33, 48, 54, 59, 70, 75, 81, 96, 103, 106, 116, 125 229 2.79 6, 11, 17, 32, 39, 42, 52, 61, 68, 77, 87, 90, 97, 112, 118, 123 215 0.74 3, 14, 21, 28, 34, 47, 56, 57, 72, 73, 82, 95, 101, 108, 115, 126 212 2.83 2, 11, 21, 32, 40, 45, 51, 58, 71, 78, 84, 89, 97, 108, 118, 127 209 0.80 7, 9, 22, 28, 34, 48, 51, 61, 68, 78, 81, 95, 101, 107, 120, 122 207 1.31 7, 14, 18, 27, 33, 44, 56, 61, 68, 73, 85, 96, 102, 111, 115, 122 220 0.48 8, 11, 18, 29, 33, 46, 55, 60, 69, 74, 83, 96, 100, 111, 118, 121 220 2.06 12, 13, 19, 22, 33, 40, 58, 63, 66, 71, 89, 96, 107, 110, 116, 117 207 0.00 2, 15, 24, 25, 35, 46, 53, 60, 69, 76, 83, 94, 104, 105, 114, 127 222 0.00 2, 13, 23, 28, 35, 48, 54, 57, 72, 75, 81, 94, 101, 106, 116, 127 223 2.37 6, 11, 23, 26, 33, 48, 52, 61, 68, 77, 81, 96, 103, 106, 118, 123 204 3.44 8, 13, 17, 28, 34, 43, 55, 62, 67, 74, 86, 95, 101, 112, 116, 121

Home Benchmarks Library P-median Problem