Switch to German Switch to English

UflLib

The UflLib benchmark page was created in 2003 at MPI Informatik. A mirror site has been created here in 2024 to ensure continued access. It contains a collection of benchmark instances for the Uncapacitated Facility Location Problem, also known as Simple Plant Location Problem, or the (Uncapacitated) Warehouse Location Problem.

There are m cities/customers and n potential facility locations. With each location we associate a nonnegative opening cost fi. Between each facility i and each city j there is a nonnegative connection or service cost cij. The task is to connect each city to exactly one opened facility such that the sum of all (opening plus connection) costs is minimized.

This problem has been studied intensively, and here a collection of standard benchmark problems can be accessed. Source code of benchmark generators for some instances classes is also available.

If you find errors, have additional benchmarks, solutions, or code material, please contact us via email.

In some of the benchmark packages all instances have been solved to optimality, which is indicated with .



Benchmark Size Opt Instances
Bilde-Krarup 1.4 MB 220 description - data-format - download
Bilde-Krarup instance generator 2 KB description - data-format - download
Chessboard 78 KB 30 description - data-format - download
Euclidean 650 KB 30 description - data-format - download
Finite projective planes, k=11 98 KB 30 description - data-format - download
Finite projective planes, k=17 384 KB 30 description - data-format - download
Galvão-Raggi 850 KB 50 description - data-format - download
Galvão-Raggi instance generator 4 KB description - data-format - download
Koerkel-Ghosh symmetric 17 MB 45 description - data-format - download
Koerkel-Ghosh sym. instance generator 2 KB description - data-format - download
Koerkel-Ghosh asymmetric 17 MB 45 description - data-format - download
Koerkel-Ghosh asym. instance generator 2 KB description - data-format - download
K-median 38 MB 6, (18) description - data-format - download
K-median instance generator 2 KB description - data-format - download
Large duality gap, Class A 71 KB 30 description - data-format - download
Large duality gap, Class B 71 KB 30 description - data-format - download
Large duality gap, Class C 71 KB 30 description - data-format - download
M* 23 MB 22 description - data-format - download
ORLIB 2.3 MB 15 description - data-format - download
Perfect Codes 98 KB 32 description - data-format - download
Uniform 677 KB 30 description - data-format - download



Data Format

Instances are stored in two basic formats. Suppose n is the number of facilities and m the number of cities.

1. Simple Format

The first line consists of 'FILE: ' and the name of the file. The next line contains n, m and a 0. The subsequent n lines consist of the number of the facility, the opening cost, and the connetion cost to the cities.

Example: n = 4, m = 3
FILE: Exapmle.txt
4 3 0
1 300 130 120 80
2 400 140 100 50
3 150 130 90 140
4 200 100 120 150

2. ORLIB-Cap Format

The format allows to store instances for the uncapacitated and capacitated facility location problem. The first line of a file consists n and m. The next n lines are the opening cost and the capacity of each facility. The following numbers for the cities are the demand and the connections to all facilities. For each city there is one line with the demand, and one line with connection costs to all factilities.

Example: uncapacitated n = 4, m = 3
4 3
0 300
0 400
0 150
0 200
0
130 140 130 100
0
120 100 90 120
0
80 50 140 150

3. Solution Format

There are m numbers from {0,1,...,n-1}. The i-th number is the facility city i is connected to. The last number of the file is the cost of the solution. Facilities and cities are ordered by appearance in the instance file. If the number of a facility does not appear in the solution file, it remains closed in the solution. Note that the numbering starts with 0.

Example: n = 4, m = 3
2 2 2 510