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

摘要

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