Benchmark library ballred.gif (861 bytes) Simple Plant Location Problem

ballred.gif (861 bytes) Home ballred.gif (861 bytes) Simple Plant Location Problem ballred.gif (861 bytes)


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. 
Class Number of iterations Number of the best 
Number of record change  Colculation time (hh:mm:ss)

           374 264

371 646 11 00:00:15
Chess            138 674 136 236 17 00:00:06
FPP         6 656 713 6 652 295 27 00:05:20
Gap-A       10 105 775 3 280 342 10 00:04:52
Gap-B       30 202 621 14 656 960 22 00:12:24
Gap-C 541 320 830 323 594 521 30 01:42:51
Uniform                 9 834 2748 8 00:00:00
Eucl                 1 084 552 5 00:00:00

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.

Class PCodes Chess FPP Gap-A Gap-B Gap-C Uniform Eucl
Local optima 928



827 909 915 411 101

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.



ballred.gif (861 bytes) Home ballred.gif (861 bytes) Simple Plant Location Problem ballred.gif (861 bytes)