Optimization Online


Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers

Huizhen Zhang(zhzzywz***at***gmail.com)
Cesar Beltran-Royo(cesar.beltran***at***urjc.es)
Liang Ma(maliang***at***usst.edu.cn)

Abstract: The Quadratic Assignment Problem (QAP) can be solved by linearization, where one formulates the QAP as a mixed integer linear programming (MILP) problem. On the one hand, most of these linearization are tight, but hardly exploited within a reasonable computing time because of their size. On the other hand, Kaufman and Broeckx formulation [1] is the smallest of these linearizations, but very weak. In this paper, we analyze how Kaufman and Broeckx formulation can be tightened to obtain better QAP-MILP formulations. As we show in our numerical experiments, these tightened formulations remain small but computationally effective in order to solve the QAP by means of general purpose MILP solvers.

Keywords: quadratic assignment problem, mixed integer linear programming

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Statistics and Operations Research,Rey Juan Carlos University (URJC),C/ Tulipán s/n, 28933,Móstoles (Madrid),Spain 04/2010

Download: [PDF]

Entry Submitted: 05/20/2010
Entry Accepted: 05/20/2010
Entry Last Modified: 05/20/2010

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