i

Optimizing the QAP:

A Problem of Mapping

Jason Straw - jstraw@ibiblio.org

High Point University: Department of Mathematics and Computer Science

http://www.misato.us/presentations/seniorsem/

What's the QAP

How to solve it:

What's this!?

What we'll cover today:

What's the QAP - Cont

How to solve it... really

Translation

The Fortran

      IL = 3
      IR = 0
      DO 109 IRCT = N9,N63
        IVAL = IRCT 
        IF (MOD(IVAL,N8).EQ.0) GO TO 109
        IROW = IROW + 1
      CALL NATCH(N935,NUMCOL,LABEL,IVAL,
     1 IR,IL,N8,N64,N512,IROW,
     1 N45,N157,ROW,COST,COLUMN)
109   CONTINUE
      ITER = 0

            sub natch() 74 lines that ends in:

      ROWS(1,IROW) = ROWS(1,IROW) + 1
      K = ROWS(1,IROW) + 1
      ROWS(K,IROW) = ICOL
      COST(ICOL) = COST(ICOL) + 1
            

C

25 Lines consisting of 2 simple loops

Problems...

A few Initial Problems

Mapping row -> costs

000 000 000 000 000
000 1234
000 5678
000 9101112
000 13141516
000 000 000 000 000
17000 181920
21 000 22 23 24
25 000 26 27 28
29 000 30 31 32
000 000 000 000 000
33 34 000 35 36
37 38 000 39 40
41 42 000 43 44
45 46 000 47 48
000 000 000 000 000
49 50 51 000 52
53 54 55 000 56
57 58 59 000 60
61 62 63 000 64
000 000 000 000 000
65 66 67 68 000
69 70 71 72 000
73 74 75 76 000
77 78 79 80 000
000 17 33 49 65
000 000 000 000 000
000 81 82 83 84
000 85 86 87 88
000 89 90 91 92
1 000 34 50 66
000 000 000 000 000
93 000 94 95 96
97 000 98 99 100
101 000 102 103 104
2 18 000 51 67
000 000 000 000 000
105 106 000 107 108
109 110 000 111 112
113 114 000 115 116
3 19 35 000 68
000 000 000 000 000
117 118 119 000 120
121 122 123 000 124
125 126 127 000 128
4 20 36 52 000
000 000 000 000 000
129 130 131 132 000
133 134 135 136 000
137 138 139 140 000
000 21 37 53 69
000 93 105 117 129
000 000 000 000 000
000 141 142 143 144
000 145 146 147 148
5 000 38 54 70
81 000 106 118 130
000 000 000 000 000
149 000 150 151 152
153 000 154 155 156
6 22 000 55 71
82 94 000 119 131
000 000 000 000 000
157 158 000 159 160
161 162 000 163 164
7 23 39 000 72
83 95 107 000 132
000 000 000 000 000
165 166 167 000 168
169 170 171 000 172
8 24 40 56 000
84 96 108 120 000
000 000 000 000 000
173 174 175 176 000
177 178 179 180 000
000 25 41 57 73
000 97 109 121 133
000 149 157 165 173
000 000 000 000 000
000 181 182 183 184
9 000 42 68 74
85 000 110 122 134
141 000 158 166 174
000 000 000 000 000
185 000 186 187 188
10 26 000 59 75
86 98 000 123 135
142 150 000 167 175
000 000 000 000 000
189 190 000 191 192
11 27 43 000 76
87 99 111 000 136
143 151 159 000 176
000 000 000 000 000
193 194 195 000 196
12 28 44 60 000
88 100 112 124 000
144 152 160 168 000
000 000 000 000 000
197 198 199 200 000
000 29 45 61 77
000 101 113 125 137
000 153 161 169 177
000 185 189 193 197
000 000 000 000 000
13 000 46 62 78
89 000 114 126 138
145 000 162 170 178
181 000 190 194 198
000 000 000 000 000
14 30 000 63 79
90 102 000 127 139
146 154 000 171 179
182 186 000 195 199
000 000 000 000 000
15 31 47 000 80
91 103 115 000 140
147 155 163 000 180
183 187 191 000 200
000 000 000 000 000
16 32 48 64 000
92 104 116 128 000
148 156 164 172 000
184 188 192 196 000
000 000 000 000 000

How the Mapping Works

17 (yellow highlight)

126 (cyan highlight)

How the Mapping Works

159 (magenta highlight)

184 (blue highlight)

Mapping row -> costs

000 000 000 000 000
000 1234
000 5678
000 9101112
000 13141516
000 000 000 000 000
17000 181920
21 000 22 23 24
25 000 26 27 28
29 000 30 31 32
000 000 000 000 000
33 34 000 35 36
37 38 000 39 40
41 42 000 43 44
45 46 000 47 48
000 000 000 000 000
49 50 51 000 52
53 54 55 000 56
57 58 59 000 60
61 62 63 000 64
000 000 000 000 000
65 66 67 68 000
69 70 71 72 000
73 74 75 76 000
77 78 79 80 000
000 17 33 49 65
000 000 000 000 000
000 81 82 83 84
000 85 86 87 88
000 89 90 91 92
1 000 34 50 66
000 000 000 000 000
93 000 94 95 96
97 000 98 99 100
101 000 102 103 104
2 18 000 51 67
000 000 000 000 000
105 106 000 107 108
109 110 000 111 112
113 114 000 115 116
3 19 35 000 68
000 000 000 000 000
117 118 119 000 120
121 122 123 000 124
125 126 127 000 128
4 20 36 52 000
000 000 000 000 000
129 130 131 132 000
133 134 135 136 000
137 138 139 140 000
000 21 37 53 69
000 93 105 117 129
000 000 000 000 000
000 141 142 143 144
000 145 146 147 148
5 000 38 54 70
81 000 106 118 130
000 000 000 000 000
149 000 150 151 152
153 000 154 155 156
6 22 000 55 71
82 94 000 119 131
000 000 000 000 000
157 158 000 159 160
161 162 000 163 164
7 23 39 000 72
83 95 107 000 132
000 000 000 000 000
165 166 167 000 168
169 170 171 000 172
8 24 40 56 000
84 96 108 120 000
000 000 000 000 000
173 174 175 176 000
177 178 179 180 000
000 25 41 57 73
000 97 109 121 133
000 149 157 165 173
000 000 000 000 000
000 181 182 183 184
9 000 42 68 74
85 000 110 122 134
141 000 158 166 174
000 000 000 000 000
185 000 186 187 188
10 26 000 59 75
86 98 000 123 135
142 150 000 167 175
000 000 000 000 000
189 190 000 191 192
11 27 43 000 76
87 99 111 000 136
143 151 159 000 176
000 000 000 000 000
193 194 195 000 196
12 28 44 60 000
88 100 112 124 000
144 152 160 168 000
000 000 000 000 000
197 198 199 200 000
000 29 45 61 77
000 101 113 125 137
000 153 161 169 177
000 185 189 193 197
000 000 000 000 000
13 000 46 62 78
89 000 114 126 138
145 000 162 170 178
181 000 190 194 198
000 000 000 000 000
14 30 000 63 79
90 102 000 127 139
146 154 000 171 179
182 186 000 195 199
000 000 000 000 000
15 31 47 000 80
91 103 115 000 140
147 155 163 000 180
183 187 191 000 200
000 000 000 000 000
16 32 48 64 000
92 104 116 128 000
148 156 164 172 000
184 188 192 196 000
000 000 000 000 000

Project Difficulties

Applications

Special Thanks to:

Any Questions?