$TITLE  QUADRATIC ASSIGNMENT PROBLEM 2
$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 * S5 /
       J   facilities   / F1 * F5 / ;

ALIAS (I,K);

ALIAS (J,L);


  TABLE A(I,I)  distance matrix between sites
    S1  S2  S3  S4  S5  
S1  0   1   2   3   4
S2  1   0   1   2   3
S3  2   1   0   1   2
S4  3   2   1   0   1
S5  4   3   2   1   0   ;

  TABLE B(J,J)  flows between facilities
   F1  F2  F3  F4  F5
F1 0   0   5   0   5
F2 0   0   3  10   5
F3 5   3   0   2   0
F4 0  10   2   0   1
F5 5   5   0   1   0 ;



  TABLE C(I,J)  location costs of plant j in location i 
     F1  F2  F3  F4  F5
S1   23  34  12  12  23
S2   34  23  12  56  23
S3   45  12  23  78  54
S4   16  63  32  53  76
S5   41  26  85  63  53 ;


  VARIABLES
       X(I,J)  0 or 1 indicating facility j in location i
       PENTY   penalty parameter in objective function
       Z1      objective
       Z2      penalty from quadratic constraint
       Z       total cost for objective function ;

POSITIVE VARIABLE X ;

PENTY.L = 100 ;

*  X.L('S1','F1') = 1 ; 
*  X.L('S2','F2') = 1 ; 
*  X.L('S3','F3') = 1 ; 
*  X.L('S4','F4') = 1 ; 
*  X.L('S5','F5') = 1 ; 
 
* DISPLAY X.L ;

  EQUATIONS
       COST        define total objective function
       ROW(I)   row assignment constraints
       COLUMN(J)   column assignment constraints;
*      QUADR       single quadratic constraint ;

  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))) 
               - PENTY*SUM((I,J), SQR(X(I,J)) ) ;

  ROW(I) ..   SUM(J, X(I,J))  =E=  1 ;


 COLUMN(J) ..  SUM(I, X(I,J)) =E= 1;

*QUADR ..    SUM((I,J), SQR(X(I,J)) ) =G= 2.9 ;

  MODEL  QAP1 /ALL/ ;

  SOLVE QAP1 USING NLP MINIMIZING Z ;

  DISPLAY X.L, X.M ;