$TITLE QUADRATIC ASSIGNMENT PROBLEM 1 $OFFUPPER * This problem is the quadratic assignment problem, i.e. the * problem of locating facilities in sites given * distance and flow matrices, as well as location costs * * References: * Burkard and Derigs book * SETS I sites / S1 * S20 / J facilities / F1 * F20 / ; TABLE A(I,I) distance matrix between sites S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 S13 S14 S15 S16 S17 S18 S19 S20 S1 0 1 2 3 4 1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 S2 1 0 1 2 3 2 1 2 3 4 3 2 3 4 5 4 3 4 5 6 S3 2 1 0 1 2 3 2 1 2 3 4 3 2 3 4 5 4 3 4 5 S4 3 2 1 0 1 4 3 2 1 2 5 4 3 2 3 6 5 4 3 4 S5 4 3 2 1 0 5 4 3 2 1 6 5 4 3 2 7 6 5 4 3 S6 1 2 3 4 5 0 1 2 3 4 1 2 3 4 5 2 3 4 5 6 S7 2 1 2 3 4 1 0 1 2 3 2 1 2 3 4 3 2 3 4 5 S8 3 2 1 2 3 2 1 0 1 2 3 2 1 2 3 4 3 2 3 4 S9 4 3 2 1 2 3 2 1 0 1 4 3 2 1 2 5 4 3 2 3 S10 5 4 3 2 1 4 3 2 1 0 5 4 3 2 1 6 5 4 3 2 S11 2 3 4 5 6 1 2 3 4 5 0 1 2 3 4 1 2 3 4 5 S12 3 2 3 4 5 2 1 2 3 4 1 0 1 2 3 2 1 2 3 4 S13 4 3 2 3 4 3 2 1 2 3 2 1 0 1 2 3 2 1 2 3 S14 5 4 3 2 3 4 3 2 1 2 3 2 1 0 1 4 3 2 1 2 S15 6 5 4 3 2 5 4 3 2 1 4 3 2 1 0 5 4 3 2 1 S16 3 4 5 6 7 2 3 4 5 6 1 2 3 4 5 0 1 2 3 4 S17 4 3 4 5 6 3 2 3 4 5 2 1 2 3 4 1 0 1 2 3 S18 5 4 3 4 5 4 3 2 3 4 3 2 1 2 3 2 1 0 1 2 S19 6 5 4 3 4 5 4 3 2 3 4 3 2 1 2 3 2 1 0 1 S20 7 6 5 4 3 6 5 4 3 2 5 4 3 2 1 4 3 2 1 0 ; TABLE B(J,J) flows between facilities 0 0 5 0 5 2 10 3 1 5 5 5 0 0 5 4 4 0 0 1 0 0 3 10 5 1 5 1 2 4 2 5 0 10 10 3 0 5 10 5 5 3 0 2 0 5 2 4 4 5 0 0 0 5 1 0 0 5 0 0 0 10 2 0 1 0 5 2 1 0 10 2 2 0 2 1 5 2 5 5 5 5 0 1 0 5 6 5 2 5 2 0 5 1 1 1 5 2 5 1 2 1 5 0 5 0 5 2 1 6 0 0 10 0 2 0 1 0 1 5 10 5 2 5 6 5 0 0 0 0 5 10 2 2 5 1 2 1 0 10 3 1 4 2 5 2 0 0 1 1 10 10 2 0 10 2 5 2 2 10 1 2 4 1 2 1 0 1 0 2 0 3 5 5 0 5 0 0 0 2 5 4 5 0 5 6 0 1 2 0 5 5 0 5 1 0 0 5 5 2 5 2 0 10 2 0 5 10 0 5 0 5 2 5 1 10 0 2 2 5 5 5 0 2 0 0 10 10 3 5 5 0 2 10 5 0 1 1 2 5 0 0 0 2 5 10 2 2 5 0 2 2 0 2 2 1 0 0 0 5 0 10 5 0 1 0 2 0 5 5 5 10 2 0 5 5 1 5 5 0 5 10 1 2 1 2 5 10 0 1 1 5 2 5 0 3 0 5 10 10 4 3 0 1 1 0 1 2 5 0 10 0 1 5 3 0 0 0 2 0 4 0 0 5 5 1 2 5 0 0 0 1 0 1 0 0 0 5 2 0 0 5 5 2 2 0 1 2 0 5 2 1 0 5 5 0 5 0 1 1 0 10 0 5 5 1 0 2 0 5 2 2 0 5 10 2 2 1 0 6 1 5 0 5 1 5 10 10 2 2 5 5 5 0 10 0 0 1 6 0 ; TABLE C(I,J) location costs of plant j in location i ; VARIABLES X(I,J) 0 or 1 indicating facility j in location i Z total cost ; BINARY VARIABLE X ; EQUATIONS COST define objective function ROW(I) row assignment constraints * COLUMN(J) column assignment constraints ; COST .. Z =E= SUM((I,J), C(I,J)*X(I,J) + SUM((K,L), A(I,K)*B(J,L)*X(I,J)*X(K,L))) ; ROW(I) .. SUM(J, X(I,J)) =E= 1 ; COLUMN(J) .. SUM(I, X(I,J)) =E= 1; MODEL QAP1 /ALL/ ; SOLVE QAP1 USING NLP MINIMIZING Z ; DISPLAY X.L, X.M ;