Benchmark library Simple Plant Location Problem

Home Simple Plant Location Problem 

Benchmarks

Construction of hard benchmarks is the important deal for researching combinatorial optimization problems. May be that the instance difficult for some method is simple for another one. And vice versa.  Particularly, the instances where are lot of local optima and they have mutual distance for each pair of them, are very hard for local search algorithms. But for all that this instances are quite simple for branch-and-bound algorithm.  

There are some benchmarks for Simple Plant Location Problem. The difference one of them is construction of matrix of transportation cost. They divided into several groups (classes):

1. Instances on perfect codes   (PCodes)

2. Instances on chess-board  (Chess)

3. Instances on finite projective planes (FPP)

4. Instances with large duality gap (Gap-A, Gap-B, Gap-C)

5. Instances with uniform distribution (Uniform)

6. Instances on Euclidean plane (Eucl)

For all classes | I | = | J |, facility opening cost is equal to 3000. Transportation matrices are designed thus that number of opening facilities in the optimal solution not is strongly differ on different classes. 

It is typical of the PCodes and Chess classes that number of strong local optima  for neighborhood 
add-drop-swap  increase exponentially along with increasing problem dimension. The FPP class is polynomial solvable one. The classes Gap-A, Gap-B, Gap-C have a big duality gap. The classes Uniform and Eucl are most famous for construction approximate algorithms with guaranteed accuracy rating. In the Table we dive the averaged characteristics for behavior exact  branch-and-bound method on this classes. 

The running time is given for PC Pentium-IV, 1800 MHz. 

For each class, we took the following computational experiment. We generate 9000 initial solutions in the feasible domain at random with uniform distribution. Standard local search algorithm was applied to each of them by the neighborhood add-drop-swap:

  .  

So, we get set of  local optima.

For each of them number of another local optima with distance at the most r = 1, 2, 3, ... was calculated. This number was  average out all local optima. There are results of the computational experiment in the picture. They demonstrate that the classes differ from each other not only by the number of local optima but also by an average density and, therefore, it may be that Euclidean class is more easy for local search algorithms The PCodes, FPP and Gap-C classes are more hard.

 

Home Simple Plant Location Problem