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

Benchmarks:
UflLib

   UflLib

Galvão-Raggi Benchmarks

The Galvão-Raggi benchmarks have a unique structure. There is always m = n. The underlying bipartite graph of the problem is randomly filled with edges to some respect. This arc density d is given upfront. Then the present arcs are assigned a cost sampled from a uniform distribution in the range [1, n] (except for n=150 we chose the range [1, 500]). The connection cost between a facility and a customer is the shortest path in this graph. The opening costs are sampled from a Normal distribution. Parameters for the different problem classes are provided in the following table.

Problem size Density Fixed costs' parameters
(m = n) d mean standard deviation
10 0.300 4.3 2.3
20 0.150 9.4 4.8
30 0.100 13.9 7.4
50 0.061 25.1 14.1
70 0.043 42.3 20.7
100 0.025 51.7 28.9
150 0.018 186.1 101.5
200 0.015 149.5 94.4


From these 8 classes we only generated 10 instances for each of the classes with m = n = 50, 70, 100, 150 and 200. We believe the other classes to be too small for today's computers. Nevertheless, one can still download the code for a generator to produce some instances of these classes. A package with benchmarks and code for the generator can be downloaded here.

References

[1] R.D. Galvão and L.A. Raggi
A method for solving to optimality uncapacitated location problems
Annals of Operations Research, 18:225-244, 1989.