Sobolev Institute of Mathematics
Laboratory "Mathematical Methods of Decision Making"

 Dr. Yuri Kochetov Yuri Kochetov Curriculum Vitae  Publications Conference presentations Industrial experience Benchmarks library

Benchmarks library

UNCAPACITATED  FACILITY  LOCATION  PROBLEM

 GIVEN: Finite sets  of  facilities  I = { 1, ..., n } and clients  J = { 1, ..., m }, a nonnegative vector ci , iI   and a matrix   gij , iI, jJ. FIND: Nonempty subset   S I   which minimize the objective function:

Software for the Local Search Algorithms for Windows-95   (zip-file 227 Kb)

1. INSTANCES  WITH  LARGE  DUALITY  GAP

The instances are generated at random with the following parameters:

n = m = 100,  ci = 3000,  Ij I | Ij |=10,

gij
{0,1,2,3,4}, iIj ,  jJ, and  gij > 3000  for  i Ij ,  jJ.

Three types of matrices gij are considered: classes A, B, C.

Class A

The matrix gij has exactly 10 noninfinity elements for each column j.
The branch and bound algorithm runs approximately 10 million nodes to find an optimal solution.

Benchmarks generator for Windows-95 (zip-file 173 Kb)           Results

Class B

The matrix  gij has exactly 10 noninfinity elements for each row  i.
The branch and bound algorithm runs approximately 30 million nodes to find an optimal solution.

Benchmarks generator for Windows-95 (zip-file 174 Kb)           Results

Class C

The matrix gij has exactly 10 noninfinity elements for each row i and each column  j. The branch and bound algorithm runs more than 500 million nodes to find an optimal solution.

Benchmarks generator for Windows-95 (zip-file 174 Kb)            Results

2.   INSTANCES  ON  FINITE  PROJECTIVE  PLANES

The instances are based on the incidence matrices for the finite projective planes. If the plane has dimension k  we generate UFLP instances for n=k2+k+1 facilities and m=n clients. The fixed costs ci equal 3000. The matrix gij has exactly n+1 noninfinity elements from the set {0,1,2,3,4} for each row i and column j. Optimal solutions have (n+1) opening facilities and can be found in polynomial time.

Results for k=11