Multi Stage Uncapacitated Facility Location Problemline.jpg (1129 bytes)

ballred.gif (861 bytes) Home ballred.gif (861 bytes) Multi Stage Uncapacitated Facility Location Problem ballred.gif (861 bytes)  

Instances with «three galaxies» local optima

(3-Galax)  

The 3-Galax class is difficult for local search methods and easy for branch-and-bound method. Local optima are clustering into the three sets (galaxies) located quite far from each other. Local optima have high values of objective function for one galaxy and low values for two others. The global optimum belongs to a galaxy. In order to rich the global optimum from another galaxy with low values we have to visit the galaxy with high values of objective function. It is easy to generalize this class of instances for arbitrary number of galaxies.

The dimension of the instances is 50 facilities, 100 admissible facility paths, 100 customers.  The set of 50 facilities is divided on two parts: 48 low expensive facilities and 2 high expensive facilities. Fixed cost of low expensive facilities is 300. Fixed cost of high expensive facilities is 20000. 
The set of 100 admissible facility paths is divided on two parts as well: 50 paths contain the first high expensive facility and the last 50 paths contain the second high expensive facility. Each admissible facility path consists of  5 facilities. Four of them are low expensive and selected at random. The last facility in each path is high expensive.
Transportation matrix presents distances between points on Euclidean plane. The points are selected in square 7000x7000 at random with uniform distribution and independently from each other.
Allocation of  local optima for an instance one can see on the diagram. 

All instances type Galax.zip 1 320 Kb

Code

The optimal value

 Duality Gap (%)

The optimal set of open facilities

471

35789

34,1

1, 2, 3, 5, 6, 7, 12, 14, 15, 17, 18, 19, 21, 23, 24, 25, 26, 29, 30, 33, 34, 36, 37, 39, 40, 41, 42, 43, 44, 46, 47, 49

472

35282

 33,1

2, 3, 4, 5, 7, 9, 10, 12, 13, 14, 17, 18, 19, 20, 25, 27, 28, 29, 32, 39, 40, 41, 45, 46, 49

473

35880

 34,4

2, 6, 7, 9, 10, 11, 12, 14, 15, 18, 19, 20, 21, 22, 24, 26, 27, 28, 29, 31, 33, 36, 38, 40, 42, 43, 45, 46, 49

474

35916

 34,5

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 17, 18, 19, 20, 23, 24, 25, 26, 29, 32, 34, 37, 38, 40, 42, 43, 44, 45, 47, 48, 49

475

35277

 33,2

1, 3, 4, 9, 11, 12, 14, 15, 16, 19, 20, 22, 23, 24, 26, 28, 29, 30, 31, 32, 35, 36, 37, 38, 39, 40, 41, 42, 45, 50

476

34999

 32,6

2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 18, 19, 22, 25, 30, 31, 32, 33, 36, 40, 41, 43, 44, 45, 46, 47, 48, 49

477

35329

 33,8

1, 2, 4, 5, 6, 11, 13, 14, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 29, 30, 31, 33, 35, 36, 37, 38, 39, 41, 42, 43, 44, 50

478

35051

 33,6

1, 3, 4, 5, 6, 7, 8, 10, 12, 13, 15, 16, 17, 18, 19, 21, 23, 24, 29, 32, 33, 37, 39, 40, 44, 46, 50

479

35208

 32,9

1, 2, 8, 10, 12, 13, 15, 17, 18, 20, 21, 23, 25, 26, 27, 29, 30, 31, 32, 33, 35, 37, 38, 39, 43, 44, 46, 47, 48, 49

480

35114

 32,7

2, 4, 5, 7, 8, 9, 12, 13, 14, 15, 17, 18, 19, 23, 24, 25, 26, 30, 33, 34, 35, 37, 38, 41, 43, 44, 45, 50

481

35457

 33,9

1, 3, 8, 9, 13, 16, 17, 18, 19, 20, 22, 28, 29, 33, 37, 38, 40, 41, 44, 45, 48, 50

482

35248

 32,8

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 15, 16, 17, 18, 19, 21, 23, 24, 25, 26, 28, 31, 32, 34, 36, 37, 38, 39, 40, 42, 44, 46, 48, 49

483

35524

 33,7

2, 4, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 17, 19, 20, 21, 23, 24, 25, 26, 28, 29, 33, 34, 36, 37, 38, 39, 41, 44, 45, 47, 48, 49

484

35891

 34,4

2, 3, 5, 6, 7, 9, 10, 12, 13, 17, 18, 19, 23, 28, 29, 30, 33, 36, 37, 38, 40, 41, 42, 48, 50

485

35403

 33,9

3, 4, 5, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19, 23, 26, 27, 29, 33, 34, 38, 39, 40, 41, 43, 44, 45, 49

486

35222

 33,4

1, 2, 3, 4, 6, 9, 10, 11, 12, 13, 14, 15, 18, 22, 23, 24, 26, 28, 29, 34, 36, 37, 38, 43, 44, 46, 47, 50

487

35635

 34,3

1, 2, 3, 6, 9, 11, 12, 16, 17, 18, 20, 22, 23, 24, 28, 29, 30, 31, 33, 34, 35, 37, 39, 40, 41, 42, 43, 45, 46, 49

488

34982

 33,0

1, 2, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 20, 22, 23, 28, 30, 32, 34, 37, 40, 42, 44, 45, 46, 47, 50

489

35903

 34,6

2, 4, 5, 7, 9, 10, 11, 13, 14, 17, 18, 20, 21, 22, 23, 27, 29, 30, 33, 34, 36, 38, 39, 41, 42, 44, 45, 46, 47, 50

490

34504

 30,9

2, 3, 4, 5, 6, 8, 10, 11, 12, 13, 14, 15, 20, 23, 25, 26, 27, 28, 29, 30, 31, 32, 35, 39, 40, 41, 44, 48, 49

491

35258

 33,5

1, 3, 4, 8, 10, 11, 12, 13, 14, 16, 17, 19, 21, 22, 24, 25, 28, 31, 32, 33, 34, 35, 37, 38, 42, 43, 46, 47, 50

492

35602

 34,1

1, 2, 3, 6, 7, 8, 9, 11, 14, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 28, 30, 32, 36, 37, 38, 40, 43, 44, 45, 46, 47, 49

493

35067

 32,6

1, 2, 3, 5, 7, 8, 9, 10, 12, 15, 18, 19, 20, 21, 22, 24, 27, 28, 30, 36, 37, 38, 39, 40, 42, 43, 48, 50

494

35304

 32,7

2, 3, 4, 5, 6, 9, 12, 13, 14, 15, 16, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 32, 34, 38, 39, 43, 45, 46, 47, 48, 50

495

35417

 33,6

1, 2, 3, 4, 5, 6, 10, 12, 13, 16, 17, 20, 22, 23, 25, 26, 27, 29, 31, 32, 34, 36, 37, 38, 40, 41, 44, 47, 50

496

35643

 34,3

4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 19, 20, 21, 23, 25, 29, 32, 36, 38, 39, 40, 41, 45, 46, 47, 48, 49

497

35259

 33,7

2, 3, 4, 5, 6, 9, 10, 11, 12, 14, 15, 18, 19, 20, 21, 24, 27, 30, 31, 32, 35, 37, 38, 40, 41, 42, 44, 46, 50

498

35393

 33,6

1, 2, 3, 4, 5, 6, 9, 10, 12, 13, 17, 20, 24, 25, 26, 27, 29, 30, 32, 35, 36, 38, 39, 42, 45, 46, 48, 50

499

35425

 33,4

2, 4, 5, 7, 8, 10, 12, 14, 15, 16, 19, 22, 25, 27, 30, 31, 33, 34, 35, 36, 37, 38, 40, 42, 43, 46, 47, 48, 50

500

35168

 32,8

4, 5, 6, 7, 9, 12, 13, 14, 15, 18, 20, 21, 23, 24, 25, 26, 27, 29, 30, 31, 32, 35, 36, 37, 40, 42, 44, 46, 48, 49