A low-rank bilinear programming approach for sub-optimal solution of the quadratic assignment problem

Abstract This paper is concerned with a new approach for solving quadratic assignment problems (QAP). We first reformulate QAP as a concave quadratic programming problem and apply an outer approximation algorithm. In addition, an improvement routine is incorporated in the final stage of the algorithm. Computational experiments on a set of standard data demonstrate that this algorithm can yield favorable results with a relatively low computational effort.