Effective formulation reductions for the quadratic assignment problem

In this paper we study two formulation reductions for the quadratic assignment problem (QAP). In particular we apply these reductions to the well known Adams and Johnson [2] integer linear programming formulation of the QAP. We analyze two cases: In the first case, we study the effect of constraint reduction. In the second case, we study the effect of variable reduction in the case of a sparse cost matrix. Computational experiments with a set of 30 QAPLIB instances, which range from 12 to 32 locations, are presented. The proposed reductions turned out to be very effective.