P-median Problem   Benchmarks

Home Benchmarks Library P-median Problem

Instances with large duality gap

Instances with large duality gap are difficult for exact methods based on the linear programming relaxation. Below we present three classes of instances Gap-A, Gap-B, Gap-C for the p-median problem where duality gap ranges from 30%  to 60%. For all instances n = m = 100 and the transportation matrices (gij) are the same as the matrices for Gap-A, Gap-B, Gap-C in the Uncapacitated Facility Location Problem (UFLP). The upper bounds p on the number of open facilities equal to the cardinality of optimal solutions in the corresponding UFPL instances.

The transportation matrix (gij) has 10 non-infinite elements  in each column. These elements are taken at random from the set {0, 1, 2, 3, 4} with uniform distribution. Input data in txt-format are aviable in the first column of the table.

All instances  Class Gap-A   pm_gap-a.zip  107 Kb

 Code The optimal value Duality Gap (%) The optimal solution 332 154 34.30 10, 14, 17, 33, 34, 40, 44, 50, 59, 63, 64, 78 432 155 46.02 12, 21, 35, 44, 47, 57, 58, 61, 65, 75, 80, 91 532 150 35.53 2, 4, 31, 32, 40, 42, 52, 56, 73, 77, 80, 89 632 162 39.40 10, 13, 38, 52, 63, 64, 67, 75, 82, 85, 87, 93 732 157 33.14 3, 5, 11, 17, 25, 31, 37, 51, 53, 59, 95 832 136 32.02 13, 19, 21, 22, 32, 34, 40, 56, 60, 62, 87, 98 932 133 36.73 16, 30, 37, 41, 46, 55, 56, 58, 63, 67, 72, 87 1032 127 28.82 12, 20, 21, 23, 33, 36, 38, 41, 48, 64, 67, 75 1132 163 44.14 10, 16, 23, 58, 68, 69, 74, 75, 82, 88, 94, 100 1232 123 25.85 3, 10, 18, 21, 22, 31, 35, 57, 69, 71, 87, 92, 99 1332 164 40.01 4, 9, 17, 28, 59, 66, 71, 76, 79, 82, 91, 97 1432 150 30.98 5, 11, 22, 25, 41, 55, 61, 62, 65, 75, 84, 89 1532 158 40.34 7, 10, 22, 23, 31, 32, 40, 45, 52, 54, 55, 59 1632 141 36.36 9, 10, 21, 35, 37, 39, 41, 45, 48, 67, 80, 86 1732 157 42.21 4, 13, 33, 38, 41, 65, 73, 75, 85, 90, 91, 96 1832 135 38.86 7, 11, 13, 27, 28, 30, 34, 46, 47, 48, 77, 78 1932 146 34.64 9, 32, 39, 40, 45, 56, 61, 62, 70, 72, 90, 98 2032 150 38.46 22, 26, 28, 41, 49, 61, 64, 67, 80, 84, 93, 97 2132 140 34.38 2, 13, 23, 36, 43, 48, 50, 64, 76, 77, 85, 91 2232 145 29.26 4, 5, 10, 31, 34, 42, 47, 70, 81, 92, 94, 100 2332 172 49.40 12, 13, 32, 36, 38, 44, 51, 57, 67, 71, 87, 88 2432 137 28.94 3, 7, 11, 14, 21, 23, 28, 31, 68, 74, 87, 90 2532 153 44.32 11, 25, 28, 33, 43, 47, 52, 64, 79, 95, 98, 99 2632 164 47.28 5, 9, 16, 25, 26, 28, 44, 66, 79, 91, 95, 99 2732 123 30.45 2, 6, 11, 12, 13, 21, 41, 48, 49, 63, 64, 90, 91 2832 145 30.20 9, 11, 21, 26, 33, 34, 65, 67, 76, 83, 84, 90 2932 155 41.18 2, 16, 19, 52, 55, 62, 71, 76, 77, 81, 84, 91 3032 113 32.46 9, 27, 35, 39, 43, 53, 66, 67, 72, 73, 89, 93 3132 130 30.12 1, 24, 26, 30, 31, 54, 60, 62, 63, 83, 85, 96, 99 3232 157 43.96 5, 17, 30, 33, 38, 41, 50, 55, 64, 71, 89, 95

Class Gap-B

The transportation matrix (gij) has 10 non-infinite elements in each row. These elements are taken at random from the set {0, 1, 2, 3, 4} with uniform distribution. Input data in txt-format are aviable in the first column of the table.

All instances  Class Gap-B pm_gap-b.zip  106 Kb

 Code The optimal value Duality Gap (%) The optimal solution 123 35.33 4, 16, 21, 23, 24, 25, 28, 29, 51, 58, 69, 79, 85, 91, 92 132 34.07 20, 22, 32, 37, 49, 55, 60, 62, 69, 74, 80, 84, 87, 88, 92 135 32.55 11, 13, 19, 23, 30, 32, 33, 34, 35, 42, 59, 73, 74, 79, 90 140 42.43 1, 7, 17, 20, 24, 33, 77, 80, 83, 84, 85, 92, 95, 99, 100 130 33.18 6, 12, 33, 34, 37, 38, 45, 50, 60, 69, 71, 74, 76, 77, 91 138 32.34 4, 17, 25, 27, 46, 47, 54, 56, 63, 82, 84, 89, 91, 95, 100 172 61.06 6, 12, 18, 19, 24, 28, 35, 37, 51, 53, 55, 61, 94, 100 165 55.18 4, 16, 17, 19, 21, 30, 36, 70, 74, 82, 84, 85, 86, 100 162 44.11 3, 7, 9, 22, 33, 35, 44, 72, 84, 86, 91, 96, 97, 99 136 34.09 1, 2, 4, 10, 11, 26, 31, 37, 41, 59, 61, 73, 75, 86, 87 169 45.77 5, 6, 7, 11, 13, 17, 26, 47, 64, 67, 79, 83, 86, 92 157 47.51 10, 20, 32, 34, 41, 42, 54, 64, 65, 72, 73, 81, 91, 100 160 47.61 7, 14, 19, 26, 44, 45, 48, 63, 65, 72, 78, 95, 96, 97 140 24.53 4, 5, 11, 12, 15, 29, 37, 41, 60, 63, 73, 77, 79, 98, 99 174 52.42 12, 16, 19, 24, 28, 42, 45, 50, 57, 59, 87, 94, 96, 98 134 35.97 5, 9, 13, 17, 23, 26, 32, 42, 54, 58, 89, 90, 94, 95, 97 136 33.44 17, 20, 30, 32, 34, 38, 39, 59, 63, 65, 78, 81, 84, 92, 98 131 37.92 7, 8, 9, 22, 32, 42, 58, 62, 67, 69, 71, 77, 83, 84, 100 126 40.35 4, 5, 10, 11, 12, 14, 17, 25, 54, 55, 60, 74, 92, 94, 97 179 51.60 7, 8, 15, 28, 49, 55, 58, 62, 67, 71, 72, 89, 90, 92 134 29.93 4, 7, 8, 15, 21, 23, 50, 52, 64, 73, 74, 84, 85, 90, 93 137 38.67 18, 25, 29, 30, 42, 48, 52, 54, 55, 68, 71, 72, 73, 78, 97 124 35.48 2, 3, 9, 10, 23, 44, 48, 60, 69, 74, 76, 85, 91, 93, 98 131 31.26 10, 17, 20, 35, 40, 44, 48, 59, 63, 77, 82, 83, 93, 95, 96 159 47.60 3, 10, 12, 20, 23, 25, 35, 38, 43, 45, 56, 57, 69, 94 151 47.37 7, 10, 17, 19, 26, 28, 29, 31, 34, 36, 48, 51, 67, 72 132 33.53 13, 27, 33, 36, 39, 43, 45, 50, 51, 52, 56, 64, 71, 79, 96 144 36.73 1, 15, 24, 25, 26, 27, 33, 39, 44, 49, 54, 65, 72, 76, 89 158 40.71 1, 12, 15, 18, 25, 34, 36, 39, 78, 82, 95, 96, 98, 100 125 37.67 5, 10, 18, 20, 28, 42, 52, 64, 67, 76, 79, 89, 91, 92, 96

Class Gap-C

The transportation matrix (gij) has 10 non-infinite elements in each row and each column. These elements are taken at random from the set {0, 1, 2, 3, 4} with uniform distribution. Input data in txt-format are aviable in the first column of the table.

All instances  Class Gap-C pm_gap-c.zip  106 Kb

 Code The optimal value Duality Gap (%) The optimal solution 147 39.73 7, 18, 24, 26, 28, 29, 34, 50, 53, 57, 66, 75, 80, 92 145 58.77 29, 34, 40, 42, 47, 50, 51, 58, 59, 68, 74, 76, 88, 90 142 59.56 5, 17, 21, 33, 45, 48, 52, 55, 60, 63, 81, 90, 97, 99 144 41.91 6, 15, 21, 29, 32, 33, 38, 42, 54, 65, 70, 71, 73, 88 137 41.52 3, 33, 36, 38, 42, 49, 54, 55, 56, 65, 76, 91, 94, 96 144 34.83 11, 17, 25, 39, 45, 46, 51, 55, 60, 74, 83, 85, 86, 96 130 37.65 5, 12, 20, 22, 25, 33, 47, 57, 67, 80, 84, 93, 97, 98 138 43.06 1, 7, 8, 12, 14, 17, 28, 32, 44, 49, 52, 63, 74, 100 147 43.36 3, 13, 14, 18, 23, 28, 34, 37, 38, 59, 72, 83, 89, 91 142 41.17 1, 3, 9, 14, 25, 45, 48, 52, 72, 73, 82, 88, 90, 94 140 44.39 1, 2, 4, 23, 26, 42, 49, 55, 66, 70, 71, 86, 91, 97 152 44.20 17, 22, 25, 39, 49, 53, 55, 65, 69, 72, 74, 79, 80, 83 133 41.94 2, 5, 19, 22, 33, 35, 38, 51, 52, 65, 66, 67, 73, 91 141 45.24 23, 24, 35, 37, 42, 51, 52, 71, 82, 88, 90, 96, 97, 100 134 43.98 8, 32, 44, 52, 53, 55, 57, 65, 71, 79, 82, 89, 95, 99 139 45.56 5, 8, 12, 18, 31, 34, 41, 51, 54, 57, 74, 76, 83, 90 137 38.16 6, 13, 16, 22, 28, 58, 64, 65, 69, 76, 77, 87, 91, 92 140 41.56 5, 11, 24, 27, 28, 33, 57, 61, 68, 73, 75, 84, 94, 98 138 36.30 3, 10, 12, 15, 26, 28, 52, 57, 81, 91, 95, 97, 98, 100 121 40.94 6, 8, 14, 17, 25, 31, 32, 33, 55, 63, 67, 75, 85, 89 133 42.29 7, 8, 13, 21, 22, 25, 27, 42, 61, 69, 80, 88, 92, 95 139 43.92 3, 12, 21, 29, 38, 62, 67, 74, 75, 77, 78, 85, 88, 90 131 42.17 5, 8, 11, 27, 32, 45, 56, 62, 66, 68, 69, 71, 82, 85 132 40.18 9, 10, 24, 27, 28, 39, 51, 55, 66, 67, 69, 71, 95, 99 139 37.31 2, 4, 19, 31, 32, 35, 38, 39, 40, 50, 57, 71, 91, 92 137 41.92 18, 21, 31, 42, 50, 54, 56, 57, 58, 59, 62, 73, 81, 99 124 37.73 5, 6, 13, 23, 24, 31, 45, 53, 56, 57, 59, 61, 70, 85 137 39.29 17, 18, 20, 35, 41, 58, 64, 65, 68, 75, 79, 90, 92, 96 141 47.59 9, 22, 39, 45, 66, 70, 73, 75, 77, 84, 85, 90, 91, 97 129 40.96 3, 6, 22, 25, 33, 60, 62, 68, 72, 80, 84, 86, 93, 95

Home Benchmarks Library P-median Problem