This is an archived website. The group moved to RWTH Aachen University.

UflLib


Bilde-Krarup Instances

Similar instances: Koerkel-Ghosh, Uniform

The Bilde-Krarup benchmarks are quite old small scale instances. They were proposed in 1977 in [1]. The structure of the problems is based on the observation that smaller or greater opening costs make it economical to open more or less facilities. For most problems the opening costs are fixed to one value for all facilities, while the connection costs are drawn uniformly at random from some interval.
There are twenty-two classes of problems. The parameters for the classes are provided in the table below.

Class Size Opening Costs Connection Costs
B 30/80 Discrete Uniform (1000, 10000) Discrete Uniform (0, 1000)
C 50/100 Discrete Uniform (1000, 2000) Discrete Uniform (0, 1000)
Dq* 30/80 Identical, q*1000 Discrete Uniform (0, 1000)
Eq* 50/100 Identical, q*1000 Discrete Uniform (0, 1000)
(*) q = 1,...,10


The exact instances are not known. Therefore we generated 10 problems of each class, 220 problems in total.


References

[1] O. Bilde and J. Krarup.
Sharp lower bounds and efficient algorithms for the simple plant location problem.
Annals of Discrete Mathematics 1:79-97, 1977.