Optimization Online


Effective formulation reductions for the quadratic assignment problem

Huizhen Zhang(zhzzywz***at***gmail.com)
Cesar Beltran-Royo(cesar.beltran***at***urjc.es)
Miguel Constantino(miguel.constantino***at***fc.ul.pt)

Abstract: 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, which we call formulation IPQAP-I. 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 32 QAPLIB instances, which range from 12 to 32 locations, are presented. The proposed reductions turned out to be very effective: By applying the new constraint reduction or the new variable reduction to the IPQAP-I formulation, we solved 13 and 23 instances, respectively, compared to the 7 instances solved by formulation IPQAP-I.

Keywords: quadratic assignment problem, linear integer programming, linear programming relaxation, sparse matrix

Category 1: Combinatorial Optimization


Download: [PDF]

Entry Submitted: 12/17/2008
Entry Accepted: 12/17/2008
Entry Last Modified: 12/17/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society