一类特殊二次分配问题及其求解

Solving a Special Kind of Quadratic Assignment Problem

二次分配问题(quadratic assignment problem,QAP)是应用于诸多领域的组合优化NP-难题,许多从实际问题中抽象出来的二次分配问题,其流矩阵与距离矩阵中存在大量零元素,如果在该类二次分配问题的求解中,能够充分利用这些零元素的信息,将大大缩减问题的规模,节省大量运算时间。本文以二次分配问题的线性松弛模型为基础,分别从理论和实验的角度对这类二次分配问题的求解进行了研究,说明了二次分配问题求解中,先行利用零元素信息减小问题规模的可行性和重要性。

Quadratic assignment problem （QAP） is a NP-hard combinatorial optimization problem and has been applied in various fields. There are always many zero elements in the flow matrix or distance matrix of the quadratic assignment problem instances which are abstracted from the practical problems. Much computation time can be saved if we can first reduce the size of the problem by using its zero elements. In this paper, we study the solution to this kind of quadratic assignment problem both in theory and experiments based on its linearization. The theoretical and experimental results show that it is feasible and important to solve these quadratic assignment problems by reducing the size of the problem via zero elements.