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 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, c2C, c1 c2. These codes exist for k = 2r 1, r>1, integer.
Put n = 2k, n/(k+1), I J = {1,, n}. Every element iI 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

 334

 232

 5.98

 5, 12, 24, 25, 35, 46, 50, 63, 66, 79, 83, 94, 104, 105, 117, 124

 434

 217

 2.72

 2, 11, 23, 30, 40, 45, 49, 60, 69, 80, 84, 89, 99, 106, 118, 127

 534

 227

 1.25

 3, 13, 18, 32, 40, 42, 53, 59, 70, 76, 87, 89, 97, 111, 116, 126

 634

 219

 1.96

 1, 12, 23, 30, 38, 47, 52, 57, 72, 77, 82, 91, 99, 106, 117, 128

 734

 223

 4.14

 3, 13, 18, 32, 40, 42, 53, 59, 70, 76, 87, 89, 97, 111, 116, 126

 834

 215

 1.46

 3, 16, 22, 25, 37, 42, 52, 63, 66, 77, 87, 92, 104, 107, 113, 126

 934

 221

 1.92  4, 14, 23, 25, 37, 43, 50, 64, 65, 79, 86, 92, 104, 106, 115, 125

1034

 217

 2.48

 2, 7, 27, 30, 44, 45, 49, 56, 73, 80, 84, 85, 99, 102, 122, 127

1134

 220

 4.40

 4, 9, 22, 31, 37, 48, 51, 58, 71, 78, 81, 92, 98, 107, 120, 125

1234

 223

 1.51

 4, 13, 23, 26, 38, 43, 49, 64, 65, 80, 86, 91, 103, 106, 116, 125

1334

 211

 1.51

 6, 12, 17, 31, 35, 45, 56, 58, 71, 73, 84, 94, 98, 112, 117, 123

1434

 226

 2.77

3, 13, 24, 26, 34, 48, 53, 59, 70, 76, 81, 95, 103, 105, 116, 126

1534

 209

 0.17

 8, 11, 21, 26, 34, 45, 51, 64, 65, 78, 84, 95, 103, 108, 118, 121

1634

 226

 0.17

 7, 10, 22, 27, 36, 45, 49, 64, 65, 80, 84, 93, 102, 107, 119, 122

1734

 221

 0.17

 12, 13, 18, 23, 33, 40, 59, 62, 67, 70, 89, 96, 106, 111, 116 117

1834

 225

 1.95

 1, 8, 27, 30, 42, 47, 52, 53, 76, 77, 82, 87, 99, 102, 121, 128

1934

 222

 1.74

 4, 15, 21, 26, 38, 41, 51, 64, 65, 78, 88, 91, 103, 108, 114, 125

2034

 205

 0.00 

 8, 11, 21, 26, 33, 46, 52, 63, 66, 77, 83, 96, 103, 108, 118, 121

2134

 226

 0.77

 4, 13, 23, 26, 33, 48, 54, 59, 70, 75, 81, 96, 103, 106, 116, 125

2234

 229

 2.79

 6, 11, 17, 32, 39, 42, 52, 61, 68, 77, 87, 90, 97, 112, 118, 123

2334

 215

 0.74

 3, 14, 21, 28, 34, 47, 56, 57, 72, 73, 82, 95, 101, 108, 115, 126

2434

 212

 2.83

2, 11, 21, 32, 40, 45, 51, 58, 71, 78, 84, 89, 97, 108, 118, 127

2534

 209

 0.80

 7, 9, 22, 28, 34, 48, 51, 61, 68, 78, 81, 95, 101, 107, 120, 122

2634

 207

 1.31

 7, 14, 18, 27, 33, 44, 56, 61, 68, 73, 85, 96, 102, 111, 115, 122

2734

 220

 0.48

 8, 11, 18, 29, 33, 46, 55, 60, 69, 74, 83, 96, 100, 111, 118, 121

2834

 220

 2.06

 12, 13, 19, 22, 33, 40, 58, 63, 66, 71, 89, 96, 107, 110, 116, 117

2934

 207

 0.00

 2, 15, 24, 25, 35, 46, 53, 60, 69, 76, 83, 94, 104, 105, 114, 127

3034

 222

 0.00

 2, 13, 23, 28, 35, 48, 54, 57, 72, 75, 81, 94, 101, 106, 116, 127

3134

 223

 2.37

 6, 11, 23, 26, 33, 48, 52, 61, 68, 77, 81, 96, 103, 106, 118, 123

3234

 204

 3.44

 8, 13, 17, 28, 34, 43, 55, 62, 67, 74, 86, 95, 101, 112, 116, 121

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