几种基于匈牙利算法求解二次分配问题的方法及其分析比较

Empirical Comparative Analysis of the Solution Methods for the Quadratic Assignment Problem Based on the Hungarian Algorithm

二次分配问题(Quadratic assignment problem,QAP)属于NP-hard组合优化难题。二次分配问题的线性化模型和下界计算方法,是求解二次分配问题的重要途径。本文以二次分配问题的线性化模型为基础,根据现有QAP对偶上升下界计算方法中的具体操作,提出几种可行的QAP对偶上升计算新方法。最后,通过求解QA-PLIB中的部分实例,深入分析其运行结果,详细讨论了基于匈牙利算法求解二次分配问题的对偶方法中哪些操作可较大程度地提高目标函数最优解的下界增长速度,这为基于匈牙利算法求解二次分配问题的方法的改进奠定了基础。

Quadratic assignment problem （QAP） is a NP-hard combinatorial optimization problem. The linearization of the QAP, and the lower bounds for the QAP are the key ways for solving it. In this paper, several achievable dual ascent solution methods for the QAP are proposed based on the linearization of the QAP and the specified implementation of the current dual ascent approach for the QAP. Then, a few of selected instances in the QAPLIB are tested, and the corresponding tested results are further studied. Furthermore, the processes which are included in the dual ascent approaches and can significantly accelerate the lower bounds of the QAP are discussed in detail. What is studied in this paper lays a foundation for the improvement of the solution methods for the QAP based on the Hungarian algorithm.