运筹学学报 ›› 2013, Vol. 17 ›› Issue (4): 87-95.

• 运筹学 • 上一篇    下一篇

一类特殊二次分配问题的线性化求解新方法

张惠珍1,2,*, 魏欣1, 马良1   

  1. 1. 上海理工大学管理学院, 上海 200093; 2. 上海理工大学超网络(中国)研究中心, 上海 200093
  • 出版日期:2013-12-15 发布日期:2013-12-15
  • 通讯作者: 张惠珍 E-mail:zhzzywz@gmail.com
  • 基金资助:

    上海市一流学科建设 (No. S1201YLXK),高等学校博士学科点专项科研基金联合资助课题 (No. 20123120120005),上海高校青年教师培养资助计划 (No. slg12010),上海市教育委员会科研创新 (No. 14YZ090),上海理工大学博士科研启动项目 (No. 1D-10-303-002)

A new solution method by linearization for a special kind of quadratic assignment problem

ZHANG Huizhen1,2,*, WEI Xin1, MA Liang1   

  1. 1. School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China; 2. Center for Supernetworks Research, University of Shanghai for Science and Technology, Shanghai 200093, China
  • Online:2013-12-15 Published:2013-12-15

摘要: 许多抽象于实际的二次分配问题, 其流矩阵与距离矩阵中有很多零元素, 求解该类二次分 配问题时, 可通过先行利用零元素的信息减小问题规模, 缩短计算时间. 以二次分配问题的线 性化模型为基础, 提出了一种求解流矩阵与距离矩阵中同时存在大量零元素的二次分配问题新方法, 不仅从理论上证明了方法的可行性, 而且从实验的角度说明了该方法比以往方法更加优越.

关键词: 二次分配问题, 线性化, 稀疏二次分配问题, 模型

Abstract: Usually, there are many zero elements in the flow matrix and distance matrix of the quadratic assignment problem (QAP) instances abstracted from the practical problems, and the computation time of solving this kind of QAP can be dramatically decreased by using its zero elements to reduce the size of the problem. Based on the linearization of the QAP, we proposed a new solution method for the QAP with many zero elements in both flow matrix and distance matrix in this paper. Moreover, the feasibilities and advantages of solving this special kind of QAP by using the new linearization are approved from the theoretical and experimental point of view, respectively.

Key words: quadratic assignment problem (QAP), linearization, sparse quadratic assignment problem (SQAD), model

中图分类号: