Multi Stage Uncapacitated Facility Location Problem

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 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