Decoration
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

Benchmarks:
UflLib

   UflLib


Large duality gap

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.

For more detailed information see the benchmark page at Sobolev Institute of Mathematics. On this page 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.

References

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