UflLib
Chessboard Instances
The benchmarks based on a chessboard were proposed by Kochetov and Ivanenko [1]. The board is quadratic and has length 3k. The boundaries are connected that the board yields a torus. At each field there is a customer and a facility location, so n = m = 9k2. For the instances in the package k = 4 and therefore n = m = 144. A facility can serve a customer with a cost in {0,1,2,3,4}, if a chess king can reach the field of the customer from the field of the facility. All other connection costs are set to infinity, the opening costs are equal to 3000 for each facility. In the optimal solution the k^2 kings cover the whole board. The number of sets of k2 kings covering the boards, however, 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. |