UflLib
Large Duality Gap Instances
These benchmarks are due to Kochetov and Ivanenko [1]. They were generated at random with the following parameters. The number of facilities is equal to the number of cities with n = m = 100. All opening costs are set to 3000. In class A each city has 10 cheap connections with values from the set {0,1,2,3,4}. All other connection costs are set to a value greater 3000 representing infinity. In class B every facility has 10 cheap connections, and in class C there are 10 cheap connections for each facility and each city. The classes increase in difficulty for mathematical programming and branch-and-bound algorithms from class A to class C.
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. |