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

• A Quadratic Assignment Problem (duh!)
• Linearizable with constraints
• Applyable to the Real World (more later)
• NP-hard
• Cannot be solved in Polynomial Time on a Deterministic Turing Machine
•  

How to solve it:

• Linearize with branch and bound

What's this!?

What we'll cover today:

• Why was Translation important?
• What a common mapping in the problem looks like?
• What made this project extremely difficult.

What's the QAP - Cont

How to solve it... really

• Combinatorics: Permutations and Permutations
• Minimize a set of costs with a goal of a integer solution:
  • n x n
  • Level 1 Linearization - n x n of n x n's
    (what we'll focus on)
  • Level 2 Linearization - n x n of n x n of n x n's
  • Level 3 Linearization - n x n of n x n of n x n of n x n's
    (what the program does)

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

• Memory Usage
• Mappings/Repeats
• Level 1 - 2 repeats
• Level 2 - 6 repeats
• Level 3 - 24 repeats
• Time Problems
• Problem size above 15 considered difficult
• Problem size above 22 or so cannot be solved in a reasonable time

Mapping row -> costs

000 000 000 000 000 000 1 2 3 4 000 5 6 7 8 000 9 10 11 12 000 13 14 15 16	000 000 000 000 000 17 000 18 19 20 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)

• black 17 is r1 = 1, c1 = 2; r2 = 2, c2 = 1
• to find red 17, swap r1/r2 and c1/c2
• red 17 is at r1 = 2, c1 = 1; r2 = 1, c2 = 2

126 (cyan highlight)

• black 126 is r1 = 2, c1 = 4; r2 = 5, c2 = 2
• to find red 126, swap r1/r2 and c1/c2
• red 126 is at r1 = 5, c1 = 2; r2 = 3, c2 = 4

How the Mapping Works

159 (magenta highlight)

• black 159 is r1 = 3, c1 = 3; r2 = 4, c2 = 4
• to find red 159, swap r1/r2 and c1/c2
• red 159 is at r1 = 4, c1 = 4; r2 = 3, c2 = 3

184 (blue highlight)

• black 184 is r1 = 4, c1 = 1; r2 = 5, c2 = 5
• to find red 184, swap r1/r2 and c1/c2
• red 184 is at r1 = 5, c1 = 5; r2 = 4, c2 = 1

Mapping row -> costs

000 000 000 000 000 000 1 2 3 4 000 5 6 7 8 000 9 10 11 12 000 13 14 15 16	000 000 000 000 000 17 000 18 19 20 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

• Learning Fortran
• Learning to read old code
• Debugging
• Converting Data
• Fortran on Itanium: Column Major and Big Endian
• C on x86: Row Major and Little Endian

Applications

• Economics
• Facility Locations for creating a Distribution Network
• Electronics
• Connecting a set of modules together on a breadboard minimzing wire use
• Other Proposed Applications
• Scheduling
• Parallel and Distributed Computing

Special Thanks to:

• Dr. Pete Hahn - Penn State University
• Dr. William Hightower - High Point University
• Zachary Jones and Glenn Ford
• Drs. Aaron and Kim Titus
• Mozilla Firefox's S5 project

Any Questions?