一种求解二次分配问题的新方法

A New Solution Method for Quadratic Assignment Problem

二次分配问题(QAP)是一种易于表述却难于求解的组合优化难题。将二次分配问题目标函数中的二次项线性化得到与原问题等价的(混合)整数线性化模型,是求解二次分配问题的重要途径,但二次分配问题线性化模型中庞大的变量和约束数,致使利用其求解较大规模的实例仍具有很大困难。通过松弛原有二次分配问题线性化模型中的约束,得到3个求解规模较小且较松弛的模型,提出了一种求解二次分配问题的新方法,并不仅从理论上证明了该方法的正确性,也从实验的角度说明了该方法较以往方法的优越性。

Quadratic assignment problem（QAP） can be described easily,but it is one of the most difficult combinatorial optimization problems.Linearization of the QAP,getting rid of the quadratic terms in the QAP objective function by transforming them into equivalent linear ones,is an important solution method for the QAP.The very large number of variables and constraints existing in the linearization of the QAP,however,usually pose an obstacle for efficiently solving the moderate QAP instances.In this paper,we proposed a new solution method for the QAP as a result of relaxing the constraints of the previous linearization of the QAP, and got three new improved linearizations of the QAP.Not only the theoretical results show that it is feasible in solving the QAP by using the new solution method,but also the experimental results show the superiorities of the new linearizations.