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 Finite Projective Planes

Let us consider a finite projective plane of order k. It is a collection of  n = k2 + k + 1 points x1,..., xn and lines L1,..., Ln. An incidence matrix A is an n matrix defining the following: aij = 1 if xj Î Li and aij = 0 otherwise. The incidence matrix A satisfying the following properties:

1.      A has constant row sum k + 1;

2.      A has constant column sum k + 1;

3.      the inner product of any two district rows of A is 1;

4.      the inner product of any two district columns of A is 1.

These matrices exist if k is a power of prime. A set of lines Bj = {Li | xj Î Li}is called a bundle for  the point xj. We define a class of instances for the p-median problem. Put I = J = {1,, n} and 
                 

          

where x ij  are random numbers taken in the set {0,1,2,3,4} with uniform distribution. We denote this class of instances by FPPk. Optimal solution for FPPk corresponds to a bundle of the plane and can be found in polynomial time. Every bundle corresponds to a strong local optimum of the p-median problem with neighborhood Flip + Swap. Hamming distance for arbitrary pair of the strong local optima equals 2k. Hence, the diameter of area where local optima are located is quite big. Moreover, there are no other local  optima with distance  less or equal k to the bundle. The class FPPk is hard enough for the local search methods when k is sufficiently large. The instances for k = 11,  p = 12,  n = m = 133 are given in the table.

(All instances on the Finite Projective Planes for k = 11 mp_fp_11.zip 172 Kb)

Code The optimal value Duality gap (%) The optimal solution
1 230  12.20 9, 25, 38, 40, 68, 74, 75, 78, 86, 95, 100, 119
2 220  11.59 16, 39, 55, 68, 70, 98, 104, 105, 108, 116, 125, 130
3 233  11.33 13, 15, 43, 49, 50, 53, 61, 70, 75, 94, 117, 133
4 221  14.62 2, 3, 6, 14, 23, 28, 47, 70, 86, 99, 101, 129
5 226  10.68 3, 26, 42, 55, 57, 85, 91, 92, 95, 103, 112, 117
6 236  11.42 6, 15, 20, 39, 62, 78, 91, 93, 121, 127, 128, 131
7 211  7.02 4, 9, 28, 51, 67, 80, 82, 110, 116, 117, 120, 128
8 220  10.47 14, 27, 29, 57, 63, 64, 67, 75, 84, 89, 108, 131
9 225  10.00 4, 5, 8, 16, 25, 30, 49, 72, 88, 101, 103, 131
10 228  5.40 2, 15, 17, 45, 51, 52, 55, 63, 72, 77, 96, 119
11 219  12.86 2, 10, 19, 24, 43, 66, 82, 95, 97, 125, 131, 132
12 239  10.66 17, 33, 46, 48, 76, 82, 83, 86, 94, 103, 108, 127
13 226  11.90 12, 25, 27, 55, 61, 62, 65, 73, 82, 87, 106, 129
14 224  6.24 9, 25, 38, 40, 68, 74, 75, 78, 86, 95, 100, 119
15 236  12.23 4, 10, 11, 14, 22, 31, 36, 55, 78, 94, 107, 109
16 219  7.69 2, 30, 36, 37, 40, 48, 57, 62, 81, 104, 120, 133
17 234  7.76 1, 7, 8, 11, 19, 28, 33, 52, 75, 91, 104, 106
18 224  11.02 20, 36, 49, 51, 79, 85, 86, 89, 97, 106, 111, 130
19 234  5.16 2, 4, 32, 38, 39, 42, 50, 59, 64, 83, 106, 122
20 228  9.12 5, 24, 47, 63, 76, 78, 106, 112, 113, 116, 124, 133
21 221  9.48 9, 25, 38, 40, 68, 74, 75, 78, 86, 95, 100, 119
22 223  14.47 10, 26, 39, 41, 69, 75, 76, 79, 87, 96, 101, 120
23 223  6.79 6, 19, 21, 49, 55, 56, 59, 67, 76, 81, 100, 123
24 216  13.04 20, 26, 27, 30, 38, 47, 52, 71, 94, 110, 123, 125
25 216  10.48 17, 33, 46, 48, 76, 82, 83, 86, 94, 103, 108, 127
26 232  9.30 11, 17, 18, 21, 29, 38, 43, 62, 85, 101, 114, 116
27 222  6.76 15, 31, 44, 46, 74, 80, 81, 84, 92, 101, 106, 125
28 227  10.42 13, 36, 52, 65, 67, 95, 101, 102, 105, 113, 122, 127
29 213  6.59 10, 33, 49, 62, 64, 92, 98, 99, 102, 110, 119, 124
30 231  8.50 16, 22, 23, 26, 34, 43, 48, 67, 90, 106, 119, 121


The instances for k=17,  p=18,  n=m=307.

(All instances on the Finite Projective Planes for k = 17 mp_fp_17.zip  588 Kb)

Code The optimal value Duality gap (%) The optimal solution
1 548   29, 45, 49, 58, 109, 111, 130, 135, 158, 170, 176, 203, 206, 213, 214, 228, 245, 302
2 531   1, 24, 36, 42, 69, 72, 79, 80, 94, 111, 168, 202, 218, 222, 231, 282, 284, 303
3 554   7, 12, 35, 47, 53, 80, 83, 90, 91, 105, 122, 179, 213, 229, 233, 242, 293, 295
4 544   11, 27, 31, 40, 91, 93, 112, 117, 140, 152, 158, 185, 188 195, 196, 210, 227, 284
5 541   24, 27, 34, 35, 49, 66, 123, 157, 173, 177, 186, 237, 239, 258, 263, 286, 298, 304
6 552   1, 13, 19, 46, 49, 56, 57, 71, 88, 145, 179, 195, 199, 208, 259, 261, 280, 285
7 526   7, 24, 81, 115, 131, 135, 144, 195, 197, 216, 221, 244, 256, 262, 289, 292, 299, 300
8 546   5, 21, 25, 34, 85, 87, 106, 111, 134, 146, 152, 179, 182, 189, 190, 204, 221, 278
9 541   15, 17, 36, 41, 64, 76, 82, 109, 112, 119, 120, 134, 151, 208, 242, 258, 262, 271
10 549   46, 48, 67, 72, 95, 107, 113, 140, 143, 150, 151, 165, 182, 239, 273, 289, 293, 302
11 528   33, 67, 83, 87, 96, 147, 149, 168, 173, 196, 208, 214, 241, 244, 251, 252, 266, 283
12 551   6, 11, 34, 46, 52, 79, 82, 89, 90, 104, 121, 178, 212, 228, 232, 241, 292, 294
13 548   4, 27, 39, 45, 72, 75, 82, 83, 97, 114, 171, 205, 221, 225, 234, 285, 287, 306
14 548   42, 76, 92, 96, 105, 156, 158, 177, 182, 205, 217, 223, 250 253, 260, 261, 275, 292
15 555   5, 10, 33, 45, 51, 78, 81, 88, 89, 103, 120, 177, 211, 227, 231, 240, 291, 293
16 549   51, 85, 101, 105, 114, 165, 167, 186, 191, 214, 226, 232, 259, 262, 269, 270, 284, 301
17 556   40, 74, 90, 94, 103, 154, 156, 175, 180, 203, 215, 221, 248, 251, 258, 259, 273, 290
18 540   9, 14 37, 49 55, 82, 85, 92, 93 107, 124, 181, 215, 231, 235, 244, 295, 297
19 544   10, 12, 31, 36, 59, 71, 77, 104, 107, 114, 115, 129, 146, 203, 237, 253, 257, 266
20 538   14, 71, 105, 121, 125, 134, 185, 187, 206, 211, 234, 246, 252, 279, 282, 289, 290, 304
21 557   25, 28, 35, 36, 50, 67, 124, 158, 174, 178, 187, 238, 240, 259, 264, 287, 299, 305
22 551   4, 9, 32, 44, 50, 77, 80, 87, 88, 102, 119, 176, 210, 226, 230, 239, 290, 292
23 557   7, 9, 28, 33, 56, 68, 74, 101, 104, 111, 112, 126, 143, 200, 234, 250, 254, 263
24 531   9, 13, 22, 73, 75, 94, 99, 122, 134, 140, 167, 170, 177, 178, 192, 209, 266, 300
25 536   13, 18, 41, 53, 59, 86, 89, 96, 97, 111, 128, 185, 219, 235, 239, 248, 299, 301
26 552   28, 44, 48, 57, 108, 110, 129, 134, 157, 169, 175, 202, 205, 212, 213, 227, 244, 301
27 543   39, 41, 60, 65, 88, 100, 106, 133, 136, 143, 144, 158, 175, 232, 266, 282, 286, 295
28 552   32, 34, 53, 58, 81, 93, 99, 126, 129, 136, 137, 151, 168, 225, 259, 275, 279, 288
29 547   4, 5, 19, 36, 93, 127, 143, 147, 156, 207, 209, 228, 233, 256, 268, 274, 301, 304
30 541   36, 70, 86, 90, 99, 150, 152, 171, 176, 199, 211, 217, 244, 247, 254, 255, 269, 286

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