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