A Mixed Integer Quadratic Reformulation of the Quadratic Assignment Problem with Rank-1 Matrix

摘要

This paper focuses on the formulation and solution of certain quadratic assignment problem (QAP). A new mixed integer quadratic programming (MIQP) formulation of the QAP is presented that is especially well suited for solving instances where the flow or distance matrix is of rank-1. Computational experiments are conducted on some special generated instances as well as on some instances from the QAPLIB (Burkard et al., 1997; QAPLIB, 2012). The QAP is solved using a two-stage procedure. The objective is first simplified as a result of the rank-1 assumption and thereafter the quadratic objective is convexified. The resulting convex MIQP is then solved with a suitable solver.