A Dual Framework for Lower Bounds of the Quadratic Assignment Problem Based on Linearization

摘要

A dual framework allowing the comparison of various bounds for the quadratic assignment problem(QAP) based on linearization, e.g.the bounds of Adams and Johnoson, Ccrraresi and Malucelli, and Hahn and Grant, is presented, We discuss the differences of these bounds and propose a new and more general bounding procedure based on the dual of the linearization of Adams and Johnson. The new procedure has been applieed to problems of dimension up to n=72, and the computational resuits indicate that the new bound competes well with existing linearization bounds and yiields a good trade off between computation time and bound quality.