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 with large duality gap

Instances with large duality gap are difficult for exact methods based on the linear relaxation. We present three classes  Gap-A, Gap-B, Gap-C with large duality gap.  The local search and branch-and-bound algorithms on the classes require considerable efforts. 

Class Gap-A 

The instances from Gap-A are easer than the instances from  Gap-B, Gap-C. Their duality gap in average equals 26%. The instances have dimension   n = m = 100. Opening cost of each facility is equal 3000. The transportation matrix gij has 10 non-forbidden (non-infinited) elements from the set {0, 1, 2, 3, 4} in each column j. In other words, each customer has 10 potential facilities choosen at random with uniform distribution from all facilities. The optimal solution has 12 or 13 opening facilities. Input data as text files are in the first column of the table.   Allocation of  local optima for the first instance one can see on the diagram.

All instances of Class Gap – A  gap-a.zip 107 Kb

Code

The optimal value

Duality Gap (%)

The optimal solution
332 36154 25.43   10  14  17  33  34  40  44  50  59  63 64 78
432 36155 24.71   12  21  35  44  47  57  58  61  65  75  80  91
532 36150 27.68   2  4  31  32  40  42  52  56  73  77  80  89
632 36162 24.40   10  13  38  52  63  64  67  75  82  85  87  93
732 33157 21.73   3  5  11  17  25  31  37  51  53  59  95
832 36136 26.22   13  19  21  22  32  34  40  56  60  62  87  98
932 36133 26.55   16  30  37  41  46  55  56  58  63  67  72  87
1032 36127 26.16   12  20  21  23  33  36  38  41  48  64  67  75
1132 36163 25.66   10  16  23  58  68  69  74  75  82  88  94  100
1232 39123 29.69   3  10  18  21  22  31  35  57  69  71  87  92  99
1332 36164 24.50   4  9  17  28  59  66  71  76  79  82  91  97
1432 36150 27.19   5  11  22  25  41  55  61  62  65  75  84  89
1532 36158 23.56   7  10  22  23  31  32  40  45  52  54  55  59
1632 36141 26.33   9  10  21  35  37  39  41  45  48  67  80  86
1732 36157 24.27   4  13  33  38  41  65  73  75  85  90  91  96
1832 36135 25.79   7  11  13  27  28  30  34  46  47  48  77  78
1932 36146 24.34   9  32  39  40  45  56  61  62  70  72  90  98
2032 36150 25.62   22  26  28  41  49  61  64  67  80  84  93  97
2132 36140 23.70   2  13  23  36  43  48  50  64  76  77  85  91
2232 36145 23.51   4  5 10 31 34 42 47 70 81 92 94  100
2332 36172 24.37   12 13 32 36 38 44 51 57 67 71 87 88
2432 36137 27.37   3 7 11 14 21 23 28 31 68 74 87 90
2532 36153 25.09   11 25 28 33 43 47 52 64 79 95 98 99
2632 36164 23.48   5 9 16 25 26 28 44 66 79 91 95 99
2732 39123 28.58   2 6 11 12 13 21 41 48 49 63 64 90 91
2832 36145 25.21   9 11 21 26 33 34 65 67 76 83 84 90
2932 36155 24.50   2 16 19 52 55 62 71 76 77 81 84 91
3032 36113 27.02   9 27 35 39 43 53 66 67 72 73 89 93
3132 39130 30.48   1 24 26 30 31 54 60 62 63 83 85 96 99
3232 36157 25.82   5 17 30 33 38 41 50 55 64 71 89 95

 

Class Gap-B

The instances from Gap-B are more difficult  than the instances from  Gap-A but easer than the instances from Gap-C. Their duality gap in average equals 21%. The instances have dimension   n = m = 100. Opening cost of each facility is equal 3000. The transportation matrix gij has 10 non-forbidden (non-infinited) elements from the set {0, 1, 2, 3, 4} in each row i. In other words, each facility  has 10 potential customers choosen at random with uniform distribution from all customers. The optimal solution has 14 or 15 opening facilities. Input data as text files are in the first column of the table.   Allocation of  local optima for the first instance one can see on the diagram. 

All instances of Class Gap – B  gap-b.zip 107 Kb

Code

The optimal value

Duality Gap (%)

The optimal solution
331 45123 24.26   4 16 21 23 24 25 28 29 51 58 69 79 85 91 92
431 45132 22.52   20 22 32 37 49 55 60 62 69 74 80 84 87 88 92
531 45135 19.25   11 13 19 23 30 32 33 34 35 42 59 73 74 79 90
631 45140 19.22   1  7  17 20 24 33 77 80 83 84 85 92 95 99 100
731 45130 24.01   6 12 33 34 37 38 45 50 60 69 71 74 76  77  91
831 45138 22.86   4 17 25 27 46 47 54 56 63 82 84 89 91 95 100
931 42172 20.69   6 12 18 19 24 28 35 37 51 53 55 61 94 100
1031 42165 16.91   4 16 17 19 21 30 36 70 74 82 84 85 86 100
1131 42162 17.74   3  7  9  22 33 35 44 72 84 86 91 96 97 99
1231 45136 19.72   1  2  4  10 11 26 31 37 41 59 61 73 75  86  87
1331 42169 18.05   5  6  7  11 13 17 26 47 64 67 79 83 86 92
1431 42157 18.65   10 20 32 34 41 42 54 64 65 72 73 81 91 100
1531 42160 17.72   7  14 19 26 44 45 48 63 65 72 78 95 96 97
1631 45140 21.89   4  5  11 12 15 29 37 41 60 63 73 77 79 98 99
1731 42174 19.22   12 16 19 24 28 42 45 50 57 59 87 94 96 98
1831 45134 22.72   5  9  13 17 23 26 32 42 54 58 89 90 94 95 97
1931 45136 22.80   17 20 30 32 34 38 39 59 63 65 78 81 84 92 98
2031 45131 22.55   7  8  9  22 32 42 58 62 67 69 71 77 83 84 100
2131 45126 24.14   4  5  10 11 12 14 17 25 54 55 60 74 92 94 97
2231 42179 19.75   7  8  15 28 49 55 58 62 67 71 72 89 90 92
2331 45134 21.82   4  7  8  15 21 23 50 52 64 73 74 84 85 90 93
2431 45137 24.28   18 25 29 30 42 48 52 54 55 68 71 72 73 78 97
2531 45124 26.26   2 3 9 10 23 44 48 60 69 74 76 85 91 93 98
2631 45131 23.83   10 17  20 35 40 44 48 59 63 77 82 83 93 95 96
2731 42159 16.96   3 10 12 20 23 25 35 38 43 45 56 57 69 94
2831 42151 17.56   7  10 17 19 26 28 29 31 34 36 48 51 67 72
2931 45132 24.55   13 27 33 36 39 43 45 50 51 52 56 64 71 79 96
3031 45144 20.88   1  15 24 25 26 27 33 39 44 49 54 65 72 76  89
3131 42158 21.68   1  12 15 18 25 34 36 39 78 82 95 96 98 100
3231 45125 23.58   5 10 18 20 28 42 52 64 67 76 79 89 91 92 96

 

Class Gap-C 

The instances from Gap-C are the most difficult. Their duality gap in average equals 28%. The instances have dimension   n = m = 100. Opening cost of each facility is equal 3000. The transportation matrix gij has 10 non-forbidden (non-infinited) elements from the set {0, 1, 2, 3, 4} in each row i and each column j. In other words, each facility  has 10 potential customers and each customer  has 10 potential facilities. They are choosen at random with uniform distribution. The optimal solution has 14 opening facilities. Input data as text files are in the first column of the table.   Allocation of  local optima for the first instance one can see on the diagram. 

All instances of Class  Gap – C  gap-c.zip 106 Kb

Code The optimal value

Duality Gap (%)

 The optimal solution
333 42147 28.39   7  18 24 26 28 29 34 50 53 57 66 75 80 92
433 42145 28.42   29 34 40 42 47 50 51 58 59 68 74 76 88 90
533 39177 22.99  9  30 33 35 40 54 60 68 71 72 84 91 92
633 42144 28.42   6  15 21 29 32 33 38 42 54 65 70 71 73 88
733 42137 28.42   3  33 36 38 42 49 54 55 56 65 76 91 94 96
833 42144 28.41   11  17 25 39 45 46 51 55 60 74 83 85 86 96
933 42130 28.39   5 12 20 22 25 33 47 57 67 80 84 93 97 98
1033 42138 28.41   1  7  8  12 14 17 28 32 44 49 52 63 74 100
1133 42147 28.41   3  13 14 18 23 28 34 37 38 59 72 83 89 91
1233 42142 28.41   1  3  9  14 25 45 48 52 72 73 82 88 90 94
1333 42140 28.41   1  2  4  23 26 42 49 55 66 70 71 86 91 97
1433 42152 28.42   17  22  25 39 49 53 55 65 69 72 74 79 80 83
1533 42133 28.40   2  5  19 22 33 35 38 51 52 65 66 67 73 91
1633 42141 28.42   23 24 35 37 42 51 52 71 82 88 90 96 97 100
1733 42134 28.41   8  32 44 52 53 55 57 65 71 79 82 89 95 99
1833 42139 28.42   5  8  12 18 31 34 41 51 54 57 74 76 83 90
1933 42137 28.41   6  13 16 22 28 58 64 65 69 76 77 87 91 92
2033 42140 28.40   5  11 24 27 28 33 57 61 68 73 75 84 94 98
2133 42138 28.38   3  10 12 15 26 28 52 57 81 91 95 97 98  100

2233

 42121 28.39   6  8  14 17 25 31 32 33 55 63 67 75 85 89
2333 42133 28.40   7  8  13 21 22 25 27 42 61 69 80 88 92 95
2433 42139 28.41   3  12  21 29 38 62 67 74 75 77 78 85 88 90
2533 42131 28.41   5  8  11 27 32 45 56 62 66 68 69 71 82 85
2633 42132 28.40   9  10  24 27 28 39 51 55 66 67 69 71 95 99
2733 42139 28.39   2  4  19 31 32 35 38 39 40 50 57 71 91 92
2833 42137 28.42   18  21  31 42 50 54 56 57 58 59 62 73 81 99
2933 42124 28.40   5  6  13 23 24 31 45 53 56 57 59 61 70 85
3033 42137 28.42   17  18  20 35 41 58 64 65 68 75 79 90 92 96
3133 42141 28.42   9  22  39 45 66 70 73 75 77 84 85 90 91 97
3233 42129 28.42   3 6 22 25 33 60 62 68 72 80 84 86 93 95

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