Algorithms & Complexity

Computer Science 1

Group

Research

Teaching

Misc

UflLib

Finite Projective Planes Instances

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 = 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.

More details are available at Sobolev Institute of Mathematics, where the instances are available for download in a different data format. The UflLib package contains the same instances in the simple data format.

References

[1]	Yu. Kochetov and D. Ivanenko. Computationally Difficult Instances for the Uncapacitated Facility Location Problem. In: T. Iberaki, K. Nonobe, Y. Musunori (eds.), Metaheuristics: Progress as Real Problem Solvers, Chapter 16, pp. 351-367, 2005.