A New Flow Model for Solving the Quadratic Assignment Problem

doi:10.12005/orms.2018.0088

Operations Research and Management Science ›› 2018, Vol. 27 ›› Issue (4): 83-87.DOI: 10.12005/orms.2018.0088

• Theory Analysis and Methodology Study • Previous Articles Next Articles

A New Flow Model for Solving the Quadratic Assignment Problem

ZOU Hui-min¹, XIA Yong²

1.Beijing Polytechnic, Beijing 100176, China;
2.School of Mathematics and Systems Sciences, Beihang University, Beijing 100191, China

Received:2015-07-24 Online:2018-04-25

求解二次分配问题的新的流量模型

邹慧敏¹, 夏勇²

1.北京电子科技职业学院,北京 100176;
2.北京航空航天大学数学与系统科学学院,北京 100191

作者简介:邹慧敏(1989-),女,辽宁大连人,助讲,硕士。研究方向:最优化理论与算法;夏勇(1980-),男,江苏海安人,副教授,博士,博士生导师。研究方向:最优化理论与算法。
基金资助:
国家自然科学基金(11571029,11471325,11771056)

Abstract

Abstract: The quadratic assignment problem(QAP)is one of the classical combinatorial optimization problems with many applications in various fields. In this paper, a new flow model for QAP is proposed based on combining the recent studies on various QAP linearizations. The limited numerical results show that the new flow model outperforms a few linearizations for QAP.

Key words: quadratic assignment problem, linearization, flow model, mixed integer linear program

摘要： 二次分配问题是具有广泛应用背景的经典组合优化难题之一。本文在二次分配问题已有线性化模型的基础上,提出了一种新的基于流量的线性化模型。数值试验结果表明,新模型无论从时间上还是计算节点数都更具有优势。

关键词: 二次分配问题, 线性化, 流量模型, 混合整数线性规划

CLC Number:

O224

ZOU Hui-min, XIA Yong. A New Flow Model for Solving the Quadratic Assignment Problem[J]. Operations Research and Management Science, 2018, 27(4): 83-87.

邹慧敏, 夏勇. 求解二次分配问题的新的流量模型[J]. 运筹与管理, 2018, 27(4): 83-87.

References

[1]Koopmans T C, Beckmann M J. Assignment problems and the location of economic activities[J]. Econometrica, 1957, 25: 53-76.
[2]Loiola E M, Abreu N M M, Boaventura-Netto P O, et al. A survey for the quadratic assignment problem[J]. Europeam Journal of Operational Research, 2007, 176: 657-690.
[3]Steinberg L. The backboard wiring problem: a placement algorithm[J]. SIAM Review, 1961, 3: 37-50.
[4]Brixius N W, Anstreicher K M. The Steingberg wiring problem[J]. Gro tschelM, ed. the Sharpest Cut, The Impact of Manfred Padberg and His Work. MPS-SIAM Series on Optimization. SIAM Publisher, 2004, 4: 293-307.
[5]ElshafeiA N. Hospital layout as a quadratic assignment problem[J]. Operations Research Quarterly, 1977, 28: 167-179.
[6]Carlson R C, Nemhauser G L. Scheduling to minimize interaction cost[J]. Operations Research, 1966, 14: 52-58.
[7]魏欣, 马良, 张惠珍.二次分配问题的大洪水算法求解[J].运筹与管理,2011,20(1):1007-3221.
[8]张惠珍, 马良.几种基于匈牙利算法求解二次分配问题的方法及其分析比较[J].运筹与管理,2010,19(1):92-99.
[9]夏勇.二次指派问题的Gilmore-Lawler界的改进[J].工程数学学报,2007,03:401-413.
[10]Akkeles A, Acan A, Unveren A. A fresh view: quadratic assignment problem[J]. Proceedings of the 5th International Congress on Computational Mechanics-GRACM 2005.Limassol, July 2005. 737-744.
[11]Drezner Z, Hahn P M, Taillard E D. Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods[J]. Annals of Operations Research, 2005, 139: 65-94.
[12]Kaufman L, Broeckx F, An algorithm for the quadratic assignment problem using bender’s decomposition[J]. Europen Journal of Operational Research, 1978, 2: 204-211.
[13]Xia Y, Yuan Y. A new linearization method for quadratic assignment prob-lems[J]. Optimization Methods and Software, 2006, 21: 805-818.
[14]Lawler E L. The quadratic assignment problem[J]. Management Science, 1963, 9: 586-599.
[15]Frieze A M, Yadegar J. On the quadratic assignment problem[J]. Discrete Applied Mathematics, 1983, 5: 89-98.
[16]Ramachandran B, Pekny J F. Higher order lifting techniques in the solution of the quadratic assignment problem[J]. Floudas C A, Pardalos P M, eds. State of the art in global optimization: computational methods and applications. Netherlands: Kluwer Academic Publishers, 1996. 75-92.
[17]Ramakrishnan K G, Resende M G C, Ramachandran B, et al. Tight QAP bounds via linear programming. Pardalos P M, Migdalas A, Burkard R, eds. Combinatorial and Global Optimization. Singapore[J]. World Scientific Publishing Co. 2002. 297-303.
[18]Zhang H Z, Beltran-Royo C, Ma L. Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers[J]. Annals of Operations Research, 2013, 207: 261-278.
[19]AL-Khayyal F A, Falk J E. Jointly constrained biconvex programming[J]. Mathematics of Operations Research, 1983, 8: 273-286.
[20]AL-Khayyal F A, Larsen C. Global optimization of a quadratic function subject to a bounded mixed integer constraint set[J]. Annals of Operations Research, 1990, 25: 169-180.
[21]Sherali H D, Tuncbilek C H. A global optimization algorithm for polynomial programming programs using a reformulation-linearization technique[J]. Journal of Global Optimization, 1992, 2: 101-112.
[22]Erdogˇan G, Tansel B. A branch-and-cut algorithm for quadratic assignment problems based on linearizations[J]. Computers and Operations Research, 2007, 34: 1085-1106.
[23]McCormick P, Computability of global solution to factorable nonconvex problems: Part I-Convex underestimating problems[J]. Mathematical Programming, 1976, 10: 147-175.

A New Flow Model for Solving the Quadratic Assignment Problem

求解二次分配问题的新的流量模型

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Recommended Articles

Metrics

[1]	CHEN Yu-ting, ZHANG Hui-zhen. Two-level Medical Facility Location Problem and Tabu Search Algorithm [J]. Operations Research and Management Science, 2021, 30(9): 56-63.
[2]	JI Shou-feng, LUO Rong-juan, SUN Qi, ZHU Bao-lin. A Hybrid Estimation of Distribution Algorithm for Quadratic Assignment Problem [J]. Operations Research and Management Science, 2018, 27(1): 74-83.
[3]	HU Shao-Long, HU Zhi-hua, CAO Yang. Optimization for Storage or Retrieval Routing Problem Based on Mutil-candidates Storages Location [J]. Operations Research and Management Science, 2013, 22(5): 111-116.