UflLib


Perfect Codes

These benchmarks were proposed by Kochetov and Ivanenko [1]. We have n = m, where n is the kth power of 2. For calculating the costs, every facility and customer number is represented in binary notation. If the Hamming distance between the two binary numbers (codes) is less or equal than 1, the connection cost is a random number taken from {0, 1, 2, 3, 4} and infinity otherwise. A perfect binary code with Hamming distance r is a nonempty subset of the possible binary words with length k (or the possible binary facility and customer numbers, or the corners of a k-dimensional unit-length hypercube), where the Hamming distance is at least r for each pair of different code-words. An arbitrary perfect code with distance 3 produces a partition of the k-dimensional hypercube in disjoint spheres of radius 1 and corresponds to a strong local minimum. The number of codes and the minimum distance between two strong local minima grows exponentially as k increases.

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.