P-median Problem   Benchmarks

Home Benchmarks Library P-median Problem

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