simplex-glpk with modified glpk for fpgaHEADmaster

1 files changed, 200 insertions, 0 deletions

diff --git a/glpk-5.0/examples/tsp/moscow.tsp b/glpk-5.0/examples/tsp/moscow.tsp
new file mode 100644
index 0000000..a2d4ea2
--- /dev/null
+++ b/glpk-5.0/examples/tsp/moscow.tsp
@@ -0,0 +1,200 @@
+NAME: MOSCOW
+TYPE: TSP
+COMMENT: 68 cities in Moscow region (Andrew Makhorin <mao@gnu.org>)
+DIMENSION: 68
+EDGE_WEIGHT_TYPE: EXPLICIT
+EDGE_WEIGHT_FORMAT: LOWER_DIAG_ROW
+EDGE_WEIGHT_SECTION
+0
+80 0
+99 66 0
+73 153 156 0
+118 156 205 116 0
+136 103 37 190 242 0
+134 128 180 141 90 217 0
+72 75 127 126 81 164 86 0
+131 94 146 184 133 183 67 91 0
+75 38 90 136 126 127 94 45 56 0
+67 52 46 124 169 83 165 88 132 76 0
+134 66 69 207 219 68 189 138 136 101 106 0
+179 142 194 204 153 231 87 139 52 104 180 188 0
+145 98 63 216 240 26 212 159 178 122 109 53 226 0
+83 7 69 156 159 106 131 78 97 41 55 60 145 95 0
+85 38 68 158 180 105 152 99 118 62 57 74 166 100 41 0
+188 163 97 222 294 77 277 223 243 187 135 145 291 93 166 165 0
+38 101 125 92 80 162 96 34 101 71 93 164 149 176 104 116 214 0
+88 66 118 142 97 155 62 40 67 36 103 129 115 150 69 90 215 50 0
+113 50 102 174 164 139 136 83 92 46 88 94 140 134 53 74 199 109 74 0
+67 94 146 113 62 183 81 19 86 64 107 157 134 178 97 118 242 29 35 102 0
+133 132 96 167 239 91 245 168 212 156 80 159 260 117 135 137 55 159 183
+ 168 187 0
+51 64 54 108 157 91 159 82 139 83 25 118 187 117 67 69 143 77 97 100 101
+ 88 0
+122 116 168 129 78 205 12 74 55 82 153 177 75 200 119 140 265 84 50 124
+ 69 233 147 0
+148 115 49 202 254 29 229 176 195 139 95 97 243 45 118 117 48 174 167
+ 151 195 83 103 217 0
+95 32 84 156 146 121 118 65 84 28 70 95 132 116 35 56 181 91 56 18 84
+ 150 82 106 133 0
+133 70 122 194 184 159 156 103 112 66 108 99 160 148 73 94 219 129 94 25
+ 122 188 120 144 171 38 0
+57 58 110 118 98 147 103 17 84 28 71 121 132 142 61 82 206 43 42 66 36
+ 151 65 91 159 48 86 0
+164 101 142 225 188 167 122 134 55 97 139 109 107 152 104 125 239 150
+ 116 67 135 219 151 110 191 69 87 117 0
+145 93 78 218 240 41 212 159 153 122 117 27 205 26 87 100 118 176 150
+ 121 178 132 129 200 70 116 126 142 126 0
+142 74 77 215 227 60 197 146 134 109 114 8 186 45 68 82 137 172 137 102
+ 165 151 126 185 89 103 107 129 107 19 0
+85 48 100 146 119 137 84 55 63 10 86 111 111 132 51 72 197 72 38 56 57
+ 166 93 72 149 38 76 38 107 132 119 0
+106 26 73 179 182 110 154 101 120 64 78 48 168 97 30 62 170 127 92 76
+ 120 158 90 142 122 58 84 84 102 75 56 74 0
+171 138 72 225 277 52 252 199 218 162 118 120 266 68 141 140 25 197 190
+ 174 218 80 126 240 23 156 194 182 214 93 112 172 145 0
+65 18 48 138 160 85 132 79 98 42 37 69 146 80 21 20 145 96 70 54 98 117
+ 49 120 97 36 74 62 105 80 77 52 44 120 0
+90 163 173 17 99 207 124 111 167 138 141 217 187 228 166 168 239 77 127
+ 176 96 184 125 112 219 158 196 120 222 228 225 148 189 242 148 0
+47 22 67 116 121 104 106 40 80 24 44 85 128 99 25 39 164 66 44 46 59 124
+ 46 94 116 28 66 23 97 99 93 34 48 139 19 118 0
+89 26 78 150 140 115 112 59 78 22 64 89 126 110 29 50 175 85 50 24 78
+ 144 76 100 127 6 44 42 75 110 97 32 52 150 30 152 22 0
+31 111 118 42 134 155 153 91 157 101 86 165 205 176 114 116 207 57 107
+ 139 86 152 70 141 167 121 159 83 190 176 173 111 137 190 96 59 78 115 0
+115 35 56 188 191 93 158 110 111 73 87 31 159 80 42 45 153 136 101 63
+ 129 152 99 146 105 65 68 93 86 58 39 83 17 128 53 198 57 61 146 0
+37 70 103 91 121 140 121 44 101 45 62 124 149 135 73 75 197 41 59 83 63
+ 142 56 109 152 65 103 27 134 135 132 55 96 175 55 93 25 59 56 105 0
+143 142 106 177 249 101 255 178 222 166 90 169 270 127 145 147 65 169
+ 193 178 197 10 98 243 93 160 198 161 229 142 161 176 168 90 127 194 134
+ 154 162 162 152 0
+152 151 115 186 258 110 264 187 231 175 99 178 279 136 154 156 100 178
+ 202 187 206 45 107 252 98 169 207 170 238 151 170 185 177 121 136 203
+ 143 163 171 171 161 55 0
+146 74 81 219 230 70 191 149 124 112 118 12 176 55 72 84 147 175 140 102
+ 168 161 130 179 99 104 107 132 97 29 10 122 56 122 81 229 96 100 177 39
+ 136 171 180 0
+118 50 53 191 203 84 173 122 126 85 90 16 174 69 44 58 150 148 113 78
+ 141 149 102 161 102 79 83 105 101 43 24 95 32 125 53 201 69 73 149 15
+ 108 159 168 28 0
+50 56 62 107 155 99 151 74 131 75 17 110 179 121 59 61 151 76 89 92 93
+ 96 8 139 111 74 112 57 143 121 118 85 82 134 41 124 38 68 69 91 48 106
+ 115 122 94 0
+107 126 110 113 209 117 221 144 201 145 87 179 249 143 129 131 149 133
+ 159 162 162 94 62 209 129 144 182 127 213 158 177 155 152 152 111 130
+ 108 138 98 161 118 104 113 187 163 70 0
+105 42 94 166 156 131 128 75 84 38 80 86 132 126 45 66 191 101 66 8 94
+ 160 92 116 143 10 28 58 59 113 94 48 68 166 46 168 38 16 131 55 75 170
+ 179 94 70 84 154 0
+114 133 117 120 216 124 228 151 208 152 94 186 256 150 136 138 156 140
+ 166 169 169 101 69 216 136 151 189 134 220 165 184 162 159 159 118 137
+ 115 145 105 168 125 111 120 194 170 77 35 161 0
+89 42 72 162 184 109 156 103 122 66 61 70 170 104 45 4 169 120 94 78 122
+ 141 73 144 121 60 98 86 127 97 78 76 58 144 24 172 43 54 120 41 79 151
+ 160 80 54 65 135 70 142 0
+218 166 151 291 313 114 285 232 226 195 190 100 278 99 160 173 191 249
+ 223 194 251 205 202 273 143 189 199 215 199 73 92 205 148 166 153 301
+ 172 183 249 131 208 215 224 102 116 194 231 186 238 170 0
+81 147 168 48 68 205 93 80 136 117 136 208 156 219 150 159 250 46 96 155
+ 65 195 120 81 217 137 175 89 191 219 216 118 173 240 139 31 109 131 66
+ 182 84 205 214 220 192 119 141 147 148 163 292 0
+147 84 125 208 180 160 115 117 48 80 122 100 100 145 87 108 222 133 99
+ 50 118 202 134 103 174 52 70 100 17 119 100 90 85 197 88 210 80 58 173
+ 69 117 212 221 90 84 126 196 42 203 110 192 179 0
+93 112 96 99 195 103 207 130 187 131 73 165 235 129 115 117 135 119 145
+ 148 148 80 48 195 115 130 168 113 199 144 163 141 138 138 97 116 94 124
+ 84 147 104 90 99 173 149 56 14 140 21 121 217 127 182 0
+97 91 143 151 103 180 37 49 76 57 128 152 100 175 94 115 240 59 25 99 44
+ 208 122 25 192 81 119 66 125 175 160 47 117 215 95 136 69 75 116 121 84
+ 218 227 160 136 114 184 91 191 119 248 105 108 170 0
+122 121 85 156 228 80 234 157 201 145 69 148 249 106 124 126 70 148 172
+ 157 176 15 77 222 68 139 177 140 208 121 140 155 147 91 106 173 113 133
+ 141 141 131 25 30 150 138 85 83 149 90 130 194 184 191 69 197 0
+179 142 194 232 181 222 115 139 48 104 180 164 38 207 145 166 291 149
+ 115 126 134 260 187 103 243 128 146 132 83 181 162 111 161 266 146 215
+ 128 126 205 145 149 270 279 152 160 179 249 118 256 170 254 184 76 235
+ 124 249 0
+38 67 82 99 144 119 146 69 126 70 50 121 174 132 70 72 171 64 84 103 88
+ 116 34 134 131 85 123 52 154 132 129 80 93 154 52 116 40 79 57 102 43
+ 126 135 133 105 33 90 95 97 76 205 107 137 76 109 105 174 0
+100 34 86 173 168 123 140 87 100 50 72 70 148 118 37 58 183 113 78 52
+ 106 152 84 128 135 44 57 70 75 97 78 60 27 158 38 180 39 38 131 39 87
+ 162 171 78 54 76 146 44 153 62 170 159 58 132 103 141 134 87 0
+69 46 98 130 117 135 82 39 72 16 83 109 120 130 49 70 195 65 20 54 55
+ 163 77 70 147 36 74 22 105 130 117 26 72 170 50 132 24 30 95 81 39 173
+ 182 120 93 69 139 46 146 74 203 111 88 125 45 152 120 64 58 0
+160 97 138 219 168 173 102 126 35 91 135 113 87 158 100 121 235 136 102
+ 63 121 215 147 90 187 65 83 113 30 132 113 98 98 210 101 202 93 71 186
+ 82 130 225 234 103 97 139 209 55 216 123 205 171 13 195 111 204 83 150
+ 71 101 0
+70 89 73 110 176 104 184 107 164 108 50 142 212 130 92 94 136 96 122 125
+ 125 81 25 172 116 107 145 90 176 145 150 118 115 139 74 127 71 101 89
+ 124 81 91 100 154 126 33 37 117 44 98 218 138 159 23 147 70 212 53 109
+ 102 172 0
+188 136 121 261 283 84 255 202 196 165 160 70 248 69 130 143 161 219 193
+ 164 221 175 172 243 113 159 169 185 169 43 62 175 118 136 123 271 142
+ 153 219 101 178 185 194 72 86 164 201 156 208 140 30 262 162 187 218
+ 164 224 175 140 173 175 188 0
+94 28 80 167 162 117 134 81 100 44 66 69 148 112 31 52 177 107 72 56 100
+ 146 78 122 129 38 63 64 81 96 77 54 21 152 32 174 33 32 125 38 81 156
+ 165 77 53 70 140 48 147 56 169 153 64 126 97 135 140 81 6 52 77 103 139
+ 0
+45 43 75 118 142 112 138 61 118 62 30 97 166 108 46 48 164 76 76 79 80
+ 109 21 126 124 61 99 44 130 108 105 72 69 147 28 128 25 55 76 78 35 119
+ 128 109 81 13 83 71 90 52 181 119 113 69 101 98 166 32 63 56 126 46 151
+ 57 0
+113 35 48 186 191 85 163 110 119 73 85 37 167 72 39 37 145 136 101 71
+ 129 144 97 151 97 67 76 93 94 64 45 83 25 120 48 196 57 61 144 8 103
+ 154 163 47 21 89 158 63 165 33 137 182 77 144 126 133 153 100 47 81 90
+ 121 107 46 76 0
+97 21 57 170 173 94 145 92 111 55 69 46 159 81 14 55 154 118 83 67 111
+ 149 81 133 106 49 87 75 118 73 54 65 18 129 35 180 39 43 128 33 87 159
+ 168 58 30 73 143 59 150 58 146 164 101 129 108 138 159 84 45 63 114 106
+ 116 39 60 25 0
+116 79 131 177 133 168 98 76 51 41 117 127 63 163 82 103 228 86 52 77 71
+ 197 124 86 180 69 97 69 100 154 135 48 105 203 83 163 65 63 142 96 86
+ 207 216 135 111 116 186 69 193 107 227 132 83 172 61 186 63 111 85 57
+ 86 149 197 85 103 104 96 0
+EOF
+
+Vertices of the graph:
+ 1 Aprelevka                  35 Lyubertsy
+ 2 Balashikha                 36 Mozhaysk
+ 3 Bronnitsy                  37 Moskva
+ 4 Vereya                     38 Mytischi
+ 5 Volokolamsk                39 Naro-Fominsk
+ 6 Voskresensk                40 Noginsk
+ 7 Vysokovsk                  41 Odintsovo
+ 8 Dedovsk                    42 Ozherel'ye
+ 9 Dmitrov                    43 Ozyory
+10 Dolgoprudny                44 Orekhovo-Zuevo
+11 Domodedovo                 45 Pavlovsky Posad
+12 Drezna                     46 Podol'sk
+13 Dubna                      47 Protvino
+14 Egor'yevsk                 48 Pushkino
+15 Zheleznodorozhny           49 Puschino
+16 Zhukovsky                  50 Ramenskoye
+17 Zaraysk                    51 Roshal
+18 Zvenigorod                 52 Ruza
+19 Zelenograd                 53 Sergiyev Posad
+20 Ivanteyevka                54 Serpukhov
+21 Istra                      55 Solnechnogorsk
+22 Kashira                    56 Stupino
+23 Klimovsk                   57 Taldom
+24 Klin                       58 Troitsk
+25 Kolomna                    59 Fryazino
+26 Korolyov (Podlipki)        60 Khimki
+27 Krasnoarmeysk              61 Khot'kovo
+28 Krasnogorsk                62 Chekhov
+29 Krasnozavodsk              63 Shatura
+30 Kurovskoye                 64 Schyolkovo
+31 Likino-Dulyovo             65 Scherbinka
+32 Lobnya                     66 Elektrostal
+33 Losino-Petrovsky           67 Elektrougli
+34 Lukhovitsy                 68 Yakhroma
+
+Optimal tour length is 1994 kilometers (obtained by glpk tspsol):
+1 39 4 36 52 5 7 24 55 19 60 10 32 68 13 57 9 61 53 29 27 20 48 26 38
+59 64 33 67 15 2 35 16 50 66 40 45 12 44 31 63 51 30 14 6 3 25 34 17 22
+42 56 43 47 49 54 62 23 46 11 65 58 41 37 28 8 21 18 1