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 = k² + k + 1 points x₁,..., x_n and lines L₁,..., L_n. An incidence matrix A is an n× n matrix defining the following: a_ij = 1 if x_j Î L_i and a_ij = 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 B_j = {L_i | x_j Î L_i}is called a bundle for  the point x_j. 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 FPP_k. Optimal solution for FPP_k 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 FPP_k 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)

---

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)

Home Benchmarks Library P-median Problem