基于线性化技术的二次分配问题求解新方法

A new solution method for the quadratic assignment problem based on the linearization technique

文章在对已有二次分配问题(QAP)线性化模型深入研究的基础上,提出一种二次分配问题线性化新方法,进而给出了对称二次分配问题的线性化模型.最后,通过求解二次分配基准问题库(QAPLIB)中的部分实例说明了该线性化新方法的有效性和重要性.

In this paper,a new linearization of the quadratic assignment problem（QAP） is proposed based on the study on the current various QAP linearizations.Furthermore,the linearization of the symmetric quadratic assignment problem（SQAP） is discussed.Finally,a few of selected instances in the QAPLIB are tested,and the experimental results show that it is feasible and important in solving QAP by using the new linearization technique.