max planck institut
informatik
informatik
These are large scale benchmarks, which were translated from benchmarks for the k-median problem.
They are similar to the instances in the Euclidian
package. In the Euclidian plane n points are generated. Each point is simultaneously
facility and customer (m = n). The connection costs are determined by the
Euclidian distance. All the opening costs are equal and calculated by one of the following
formulas:
| Type | Opening cost |
|
I |
sqrt(n) / 10 |
|
II |
sqrt(n) / 100 |
|
III |
sqrt(n) / 1000 |
We generated 6 problems of Type I with m = n = 500, 1000, 1500, 2000, 2500, 3000. We also included code for a little program that allows the user to adjust the opening costs. To prevent rounding errors, we rounded all data up to 4 significant digits and then made all the entries integer. The package can be downloaded here. An instance generator is also available.
| [1] |
S. Ahn, C. Cooper, G. Cornuejols and A.M. Frieze Probabilistic analysis of a relaxation for the k-median problem Mathematics of Operations Research, 13:1-31, 1988. |
| [2] |
F. Barahona and F.A. Chudak Near-optimal solutions to large scale facility location problems Technical Report, IBM Watson Research Center, 2000. |