max planck institut
informatik
informatik
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^2+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.
| [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. |