一种基于匈牙利算法的二次分配问题求解方法

二次分配问题(Quadratic assignment problem,QAP)属于NP-hard组合优化难题.二次分配问题的线性化及下界计算方法,是求解二次分配问题的重要途径.以Frieze-Yadegar线性化模型和Gilmore-Lawler下界为基础,详细论述了二次分配问题线性化模型的结构特征,并分析了Gilmore-Lawler下界值往往远离目标函数最优值的原因.在此基础上,提出一种基于匈牙利算法的二次分配问题对偶上升下界求解法.通过求解QAPLIB中的部分实例,说明了方法的有效和可行性.

A Solution Method for the Quadratic Assignment Problem Based on the Hungarian Algorithm

Quadratic assignment problem (QAP) is a NP-hard combinatorial optimization problem. The linearization of the QAP,as well as the lower bounds for the QAP is the key way for solving it. In this paper,we exploited the linear program structure of the QAP based on Frieze-Yadegar formulation and Gilmore-Lawler bound,and analyzed the reason that the Gilmore-Lawler bound is usually far away from the optimal objective value. Furthermore,we proposed a dual ascent procedure for the lower bound of the quadratic assignment problem based on the Hungarian algorithm. Selected instances in the QAPLIB are tested,and the experimental results show that it is feasible and important in solving the quadratic assignment problem by using the new method.