ballred.gif (861 bytes) Simple Plant Location Problem  ballred.gif (861 bytes) Benchmarks
line.jpg (1129 bytes)

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

Instances on the Perfect Codes

Let Bk be a set of words (or vectors) of length k over an alphabet {0, 1}. A binary code of length  k is an arbitrary nonempty subset of Bk. Perfect binary code with distance 3 is a subset  CÍ Bk, |C|=2k/(k+1) such that Hamming distance d(c1,c2³3 for all c1, c2ÎC, c1¹c2. These codes exist for k = 2r –1, r>1, integer.
Put n = 2k, I J = {1,…, n}. Opening cost of each facility is equal 3000. Every element iÎI corresponds to a vertex x(i) of the binary hyper cube. Therefore, we may define a distance dij = d(x(i),x(j)) for any two elements i,jÎI. Now we define

   

where xij is a random number taken from the set {0, 1, 2, 3, 4} with uniform distribution.
Arbitrary perfect code C produces a partition of into 2k/(k+1) disjointed spheres of radius 1  and corresponds to a strong local minimum for the UFLP. Number of perfect codes grows  exponentially as k increases. The best lower bound is

The minimal distance between two perfect codes or strong local minima is at least .
The instances for   k = 7,  n = m = 128 are given in the table.  Allocation of  local optima  for the first instance one can see on the diagram

Code The optimal value Duality 
gap (%)
The optimal solution

 334

 48232.00

   0.01

  5   12   24   25   35   46   50   63   66   79   83   94  104  105  117  124

 434

 48217.00

   0.01

  2   11   23   30   40   45   49   60   69   80   84   89   99  106  118  127

 534

 48227.00

   0.00

  3   13   18   32   40   42   53   59   70   76   87   89   97  111  116  126

 634

 48219.00

   0.01

  1   12   23   30   38   47   52   57   72   77   82   91   99  106  117  128

 734

 48223.00

   0.01

  3   13   18   32   40   42   53   59   70   76   87   89   97  111  116  126

 834

 48215.00

   0.01

  3   16   22   25   37   42   52   63   66   77   87   92  104  107  113  126

 934

 48221.00

   0.01

  4   14   23   25   37   43   50   64   65   79   86   92  104  106  115  125

1034

 48217.00

   0.01

  2    7   27   30   44   45   49   56   73   80   84   85   99  102  122  127

1134

 48220.00

   0.01

  4    9   22   31   37   48   51   58   71   78   81   92   98  107  120  125

1234

 48223.00

   0.01

  4   13   23   26   38   43   49   64   65   80   86   91  103  106  116  125

1334

 48211.00

   0.00

  6   12   17   31   35   45   56   58   71   73   84   94   98  112  117  123

1434

 48226.00

   0.01

  3   13   24   26   34   48   53   59   70   76   81   95  103  105  116  126

1534

 48209.00

   0.00

  8   11   21   26   34   45   51   64   65   78   84   95  103  108  118  121

1634

 48226.00

   0.01

  7   10   22   27   36   45   49   64   65   80   84   93  102  107  119  122

1734

 48221.00

   0.01

 12   13   18   23   33   40   59   62   67   70   89   96  106  111  116 117

1834

 48225.00

   0.00

  1    8   27   30   42   47   52   53   76   77   82   87   99  102  121  128

1934

 48222.00

   0.01

  4   15   21   26   38   41   51   64   65   78   88   91  103  108  114  125

2034

 48205.00

   0.00

  8   11   21   26   33   46   52   63   66   77   83   96  103  108  118  121

2134

 48226.00

   0.00

  4   13   23   26   33   48   54   59   70   75   81   96  103  106  116  125

2234

 48229.00

   0.00

  6   11   17   32   39   42   52   61   68   77   87   90   97  112  118  123

2334

 48215.00

   0.01

  3   14   21   28   34   47   56   57   72   73   82   95  101  108  115  126

2434

 48212.00

   0.01

  2   11   21   32   40   45   51   58   71   78   84   89   97  108  118  127

2534

 48209.00

   0.01

  7    9   22   28   34   48   51   61   68   78   81   95  101  107  120  122

2634

 48207.00

   0.00

  7   14   18   27   33   44   56   61   68   73   85   96  102  111  115  122

2734

 48220.00

   0.01

  8   11   18   29   33   46   55   60   69   74   83   96  100  111  118  121

2834

 48220.00

   0.01

 12   13   19   22   33   40   58   63   66   71   89   96  107  110  116 117

2934

 48207.00

   0.00

  2   15   24   25   35   46   53   60   69   76   83   94  104  105  114  127

3034

 48222.00

   0.00

  2   13   23   28   35   48   54   57   72   75   81   94  101  106  116  127

3134

 48223.00

   0.01

  6   11   23   26   33   48   52   61   68   77   81   96  103  106  118  123

3234

 48204.00

   0.01

  8   13   17   28   34   43   55   62   67   74   86   95  101  112  116  121

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