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 , if22.jpg (892 bytes)I   and a matrix   gij , if22.jpg (892 bytes)I, jf22.jpg (892 bytes)J.

FIND:

 

 

Nonempty subset   S f44.jpg (953 bytes)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,  
  
gijf22.jpg (892 bytes)
{0,1,2,3,4}, if22.jpg (892 bytes)Ij ,  jf22.jpg (892 bytes)J, and  gij > 3000  for  i f33.jpg (917 bytes)Ij ,  jf22.jpg (892 bytes)J.  

   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

Results for k=17