The benchmarks based on finite projective planes were presented by Kochetov
and Ivanenko
[1]. They can easily be solved to optimality in polynomial time, however they
are a great challenge for local search algorithms.
Based on incidence matrices for the finite projective planes they have
n = m, where n is calculated by n=kČ+k+1. For the given instances k was chosen to be k=11 and k=17.
Opening costs are set to 3000 for all facilities. The matrix of connection costs has
exactly n+1 noninfinity elements from the set {0,1,2,3,4} for each row and each
column.
Slightly more details are accessible at the page at the Sobolev
Institute of Mathematics. Here the instances are available
for download in a different data format. The UflLib-package contains the
same instances in the simple data format. They can be downloaded here.
References
[1]
Yu.Kochetov and D. Ivanenko
Computationally Difficult Instances for the Uncapacitated Facility Location
Problem
Proceedings of the 5th Metaheuristic Conference (MIC 2003), Kyoto, 2003.
[an error occurred while processing this directive]