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