二次分配问题及其求解方法的研究进展(Ⅱ)

Surveys on the Studies of Solution Methods to the Quadratic Assignment Problem

二次分配问题(Quadratic assignment problem,QAP)属于NP-hard组合优化难题。过去几十年,线性化技术和下界计算方法是利用经典算法求解二次分配问题的关键所在。本文简要回顾了目前QAP问题的线性化技术和下界计算方法的研究进展,最后讨论了利用线性化技术求解二次分配问题及其下界的发展趋势。

Quadratic assignment problem（QAP） is a NP-hard combinatorial optimization problem.In the past years,linearizations of the QAP,as well as low bounds for QAP are very important in solving QAP to optimality by exact algorithms.In this paper,the developments and recent work on linearizations of the QAP and its low bounds are reviewed.Furthermore,the research tendency of solving QAP by linearizations is also discussed.