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

Abstract

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

CLC Number:

O221.7

ZHANG Huizhen, WEI Xin, MA Liang. A new solution method by linearization for a special kind of quadratic assignment problem[J]. Operations Research Transactions, 2013, 17(4): 87-95.

References

Misevicius A. An improved hybrid genetic algorithm: new result for the quadratic assignment Problem [J]. Knowledge-Based Systems, 2004, 17(2-4): 65-73.

张惠珍, 马良. 一类特殊二次分配问题及其求解 [J]. 系统工程, 2008, 26(8): 113-117.

Zhang H Z, Beltran-Royo C, Constantino M. Effective formulation reductions for the quadratic assignment problem [J]. Computers & Operations Research, 2010, 37(11): 2007-2016.

Kaufman L, Broeckx F. An algorithm for the quadratic assignment problem using Bender's decomposition [J]. European Journal of Operational Research, 1978, 2(3): 204-211.

Xia Y, Yuan Y X. A new linearization method for quadratic assignment problems [J]. Optimization Methods and Software, 2006, 21(5): 805-818.

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(1): 261-278.

Lawler E L. The quadratic assignment problem [J]. Management Science, 1963, 9(4): 586-599.

Frieze A M, Yadegar J. On the quadratic assignment problem [J]. Discrete Applied Mathematics, 1983, 5(1): 89-98.

Adams W P, Johnson T A. Improved linear programming-based lower bounds for the quadratic assignment problem [C]//Quadratic Assignment and Related Problems. New York: American Mathematical Society, 1994, 16: 43-75.

Erdogan G, Tansel B. A branch and cut algorithm for quadratic assignment problems based on linearizations [J]. Computers and Operations Research, 2007, 34(4): 1085-1106.

Ramachandran B, Pekny J F. Higher order lifting techniques in the solution of the quadratic assignment problem [C]//State of the Art in Global Optimization: Computational Methods and Applications. Netherlands: Kluwer Academic Publishers, 1996: 75-92.

Ramakrishnan K G, Resende M G C, Ramachandran B, et al. Tight QAP bounds via linear programming [C]//Combinatorial and Global Optimization. Singapore: World Scientific Publishing Co. 2002, 297-303.

张惠珍, 马良. 一种求解二次分配问题的新方法 [J]. 系统管理学报, 2010, 19(6): 645-650.

[1]	JIAN Jinbao, YANG Linfeng, ZHANG Chen. The models and optimization method for power system unit commitment problems [J]. Operations Research Transactions, 2020, 24(2): 87-102.
[2]	A Chunxiang, SHAO Yi. Optimal investment and reinsurance problem with delay under the CEV model [J]. Operations Research Transactions, 2020, 24(1): 73-87.
[3]	WEI Qian, WANG Yongmao. Pricing of power european options based on Tsallis entropy under stochastic interest rate [J]. Operations Research Transactions, 2019, 23(4): 124-130.
[4]	WANG Huining, XU Xiuli. Fluid models driven by a working vacation-queue with PH-service time distribution [J]. Operations Research Transactions, 2019, 23(2): 57-66.
[5]	REN Jiamin, FENG Wei, ZHAO Lingqi, WANG Shiying, JIRIMUTU. The 1-good-neighbor diagnosability of the Cayley graphs UG_n generated by unicyclic graphs under the PMC model and the MM^* model [J]. Operations Research Transactions, 2019, 23(1): 97-103.
[6]	GUO Wenjing, LI Xiaojun. Optimal consumption-investment-insurance purchase strategy under the condition of stochastic interest rate [J]. Operations Research Transactions, 2018, 22(4): 31-44.
[7]	YU Ke, ZHANG Xiaoqing, ZHAO Kequan. Multi-objective optimization approach of the optimal performance allocation [J]. Operations Research Transactions, 2018, 22(4): 89-98.
[8]	YU Shanen, XU Wenyang, LIU Guangyu. Researching of the scattered layout problem in circular zone [J]. Operations Research Transactions, 2018, 22(3): 132-138.
[9]	LI Weidong, LI Li, XU Yan. The concentration research of PM2.5 in Beijing with time series analysis [J]. Operations Research Transactions, 2018, 22(2): 115-126.
[10]	ZHANG Xiaoming, WANG Yingming, SHI Hailiu. A merger and acquisition decision of innovative enterprises based on the undesirable return to scale [J]. Operations Research Transactions, 2018, 22(1): 42-54.
[11]	GUO Tiande, HAN Congying, ZHAO Tong,. Optimization models and algorithms for large capacity fingerprint automatic identification system [J]. Operations Research Transactions, 2017, 21(4): 19-33.
[12]	HUANG Yakui, LI Bo, KANG Yang, DAI Yuhong, LIU Jianjun. A mixed integer model and an algorithm for steady-state gas network optimization [J]. Operations Research Transactions, 2017, 21(2): 13-23.
[13]	CHEN Zhongwen, ZHAO Qi, BIAN Kai. A successive linearization method with flexible penalty for nonlinear semidefinite programming [J]. Operations Research Transactions, 2017, 21(2): 84-100.
[14]	HU Yifan. An augmented proximity stress model for edge label overlap removal [J]. Operations Research Transactions, 2015, 19(3): 85-95.
[15]	WANG Xiaomin. The production possibility set and frontier for the two-stage additive DEA model [J]. Operations Research Transactions, 2015, 19(3): 131-139.

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments