ballred.gif (861 bytes) P-median Problem  ballred.gif (861 bytes) Benchmarks
line.jpg (1129 bytes)

ballred.gif (861 bytes) Home Benchmarks Library ballred.gif (861 bytes) P-median Problem ballred.gif (861 bytes)

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.

Class Gap-A 

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

331

123

 35.33

 4, 16, 21, 23, 24, 25, 28, 29, 51, 58, 69, 79, 85, 91, 92

431

132

 34.07

 20, 22, 32, 37, 49, 55, 60, 62, 69, 74, 80, 84, 87, 88, 92

531

135

 32.55

 11, 13, 19, 23, 30, 32, 33, 34, 35, 42, 59, 73, 74, 79, 90

631

140

 42.43

 1, 7, 17, 20, 24, 33, 77, 80, 83, 84, 85, 92, 95, 99, 100

731

130

 33.18

 6, 12, 33, 34, 37, 38, 45, 50, 60, 69, 71, 74, 76, 77, 91

831

138

 32.34

 4, 17, 25, 27, 46, 47, 54, 56, 63, 82, 84, 89, 91, 95, 100

931

172

 61.06

 6, 12, 18, 19, 24, 28, 35, 37, 51, 53, 55, 61, 94, 100

1031

165

 55.18

 4, 16, 17, 19, 21, 30, 36, 70, 74, 82, 84, 85, 86, 100

1131

162

 44.11

 3, 7, 9, 22, 33, 35, 44, 72, 84, 86, 91, 96, 97, 99

1231

136

 34.09

 1, 2, 4, 10, 11, 26, 31, 37, 41, 59, 61, 73, 75, 86, 87

1331

169

 45.77

 5, 6, 7, 11, 13, 17, 26, 47, 64, 67, 79, 83, 86, 92

1431

157

 47.51

 10, 20, 32, 34, 41, 42, 54, 64, 65, 72, 73, 81, 91, 100

1531

160

 47.61

 7, 14, 19, 26, 44, 45, 48, 63, 65, 72, 78, 95, 96, 97

1631

140

 24.53

 4, 5, 11, 12, 15, 29, 37, 41, 60, 63, 73, 77, 79, 98, 99

1731

174

 52.42

 12, 16, 19, 24, 28, 42, 45, 50, 57, 59, 87, 94, 96, 98

1831

134

 35.97

 5, 9, 13, 17, 23, 26, 32, 42, 54, 58, 89, 90, 94, 95, 97

1931

136

 33.44

 17, 20, 30, 32, 34, 38, 39, 59, 63, 65, 78, 81, 84, 92, 98

2031

131

 37.92

 7, 8, 9, 22, 32, 42, 58, 62, 67, 69, 71, 77, 83, 84, 100

2131

126

 40.35

 4, 5, 10, 11, 12, 14, 17, 25, 54, 55, 60, 74, 92, 94, 97

2231

179

 51.60

 7, 8, 15, 28, 49, 55, 58, 62, 67, 71, 72, 89, 90, 92

2331

134

 29.93

 4, 7, 8, 15, 21, 23, 50, 52, 64, 73, 74, 84, 85, 90, 93

2431

137

 38.67

 18, 25, 29, 30, 42, 48, 52, 54, 55, 68, 71, 72, 73, 78, 97

2531

124

 35.48

 2, 3, 9, 10, 23, 44, 48, 60, 69, 74, 76, 85, 91, 93, 98

2631

131

 31.26

 10, 17, 20, 35, 40, 44, 48, 59, 63, 77, 82, 83, 93, 95, 96

2731

159

 47.60

 3, 10, 12, 20, 23, 25, 35, 38, 43, 45, 56, 57, 69, 94

2831

151

 47.37

 7, 10, 17, 19, 26, 28, 29, 31, 34, 36, 48, 51, 67, 72

2931

132

 33.53

 13, 27, 33, 36, 39, 43, 45, 50, 51, 52, 56, 64, 71, 79, 96

3031

144

 36.73

 1, 15, 24, 25, 26, 27, 33, 39, 44, 49, 54, 65, 72, 76, 89

3131

158

 40.71

 1, 12, 15, 18, 25, 34, 36, 39, 78, 82, 95, 96, 98, 100

3231

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

333

147

 39.73

 7, 18, 24, 26, 28, 29, 34, 50, 53, 57, 66, 75, 80, 92

433

145

 58.77

 29, 34, 40, 42, 47, 50, 51, 58, 59, 68, 74, 76, 88, 90

533

142

 59.56

 5, 17, 21, 33, 45, 48, 52, 55, 60, 63, 81, 90, 97, 99

633

144

 41.91

 6, 15, 21, 29, 32, 33, 38, 42, 54, 65, 70, 71, 73, 88

733

137

 41.52

 3, 33, 36, 38, 42, 49, 54, 55, 56, 65, 76, 91, 94, 96

833

144

 34.83

 11, 17, 25, 39, 45, 46, 51, 55, 60, 74, 83, 85, 86, 96

933

130

 37.65

 5, 12, 20, 22, 25, 33, 47, 57, 67, 80, 84, 93, 97, 98

1033

138

 43.06

 1, 7, 8, 12, 14, 17, 28, 32, 44, 49, 52, 63, 74, 100

1133

147

 43.36

 3, 13, 14, 18, 23, 28, 34, 37, 38, 59, 72, 83, 89, 91

1233

142

 41.17

 1, 3, 9, 14, 25, 45, 48, 52, 72, 73, 82, 88, 90, 94

1333

140

 44.39

 1, 2, 4, 23, 26, 42, 49, 55, 66, 70, 71, 86, 91, 97

1433

152

 44.20

 17, 22, 25, 39, 49, 53, 55, 65, 69, 72, 74, 79, 80, 83

1533

133

 41.94

 2, 5, 19, 22, 33, 35, 38, 51, 52, 65, 66, 67, 73, 91

1633

141

 45.24

 23, 24, 35, 37, 42, 51, 52, 71, 82, 88, 90, 96, 97, 100

1733

134

 43.98

 8, 32, 44, 52, 53, 55, 57, 65, 71, 79, 82, 89, 95, 99

1833

139

 45.56

 5, 8, 12, 18, 31, 34, 41, 51, 54, 57, 74, 76, 83, 90

1933

137

 38.16

 6, 13, 16, 22, 28, 58, 64, 65, 69, 76, 77, 87, 91, 92

2033

140

 41.56

 5, 11, 24, 27, 28, 33, 57, 61, 68, 73, 75, 84, 94, 98

2133

138

 36.30

 3, 10, 12, 15, 26, 28, 52, 57, 81, 91, 95, 97, 98, 100

2233

121

 40.94

 6, 8, 14, 17, 25, 31, 32, 33, 55, 63, 67, 75, 85, 89

2333

133

 42.29

 7, 8, 13, 21, 22, 25, 27, 42, 61, 69, 80, 88, 92, 95

2433

139

 43.92

 3, 12, 21, 29, 38, 62, 67, 74, 75, 77, 78, 85, 88, 90

2533

131

 42.17

 5, 8, 11, 27, 32, 45, 56, 62, 66, 68, 69, 71, 82, 85

2633

132

 40.18

 9, 10, 24, 27, 28, 39, 51, 55, 66, 67, 69, 71, 95, 99

2733

139

 37.31

 2, 4, 19, 31, 32, 35, 38, 39, 40, 50, 57, 71, 91, 92

2833

137

 41.92

 18, 21, 31, 42, 50, 54, 56, 57, 58, 59, 62, 73, 81, 99

2933

124

 37.73

 5, 6, 13, 23, 24, 31, 45, 53, 56, 57, 59, 61, 70, 85

3033

137

 39.29

 17, 18, 20, 35, 41, 58, 64, 65, 68, 75, 79, 90, 92, 96

3133

141

 47.59

 9, 22, 39, 45, 66, 70, 73, 75, 77, 84, 85, 90, 91, 97

3233

129

 40.96

 3, 6, 22, 25, 33, 60, 62, 68, 72, 80, 84, 86, 93, 95

ballred.gif (861 bytes) Home Benchmarks Library ballred.gif (861 bytes) P-median Problem ballred.gif (861 bytes)