max planck institut
informatik
informatik
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 = 9k^2. 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 k^2 kings covering the
boards, however, grows exponentially as k increases.
More details are available at Sobolev Institute of Mathematics. Here experimental results are reported, and 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. |