American Institute of Mathematical Sciences

Advanced
April  2007, 3(2): 173-191. doi: 10.3934/jimo.2007.3.173

Solving the quadratic assignment problem using F-MSG algorithm

R. N. Gasimov 1, and  O. Ustun 1,

1. 

Eskişehir Osmangazi University, Department of Industrial Engineering, Bademlik 26030, Eskişehir, Turkey, Turkey

Received  August 2006 Revised  November 2006 Published  April 2007

Quadratic assignment problems are one of the famous strongly NP-hard combinatorial optimization problems. Because of the wide area of applications and the difficulties existing in finding optimal solutions, these problems are one of the most common objects for application of optimization methods. This paper examines the use of a generalized version of the modified subgradient algorithm for solving quadratic assignment problems. Promising computational results are reported for benchmark problem instances taken from the quadratic assignment problem library - QAPLIB.
Keywords: Global optimization., Modified subgradient algorithm, Nonconvex optimization, Sharp augmented Lagrangian, Quadratic assignment problem, F-MSG algorithm.
Mathematics Subject Classification: Primary: 90B80, 90C20; secondary: 90C26, 90C5.
Citation: R. N. Gasimov, O. Ustun. Solving the quadratic assignment problem using F-MSG algorithm. Journal of Industrial and Management Optimization, 2007, 3 (2) : 173-191. doi: 10.3934/jimo.2007.3.173
[1]

Chunrong Chen, T. C. Edwin Cheng, Shengji Li, Xiaoqi Yang. Nonlinear augmented Lagrangian for nonconvex multiobjective optimization. Journal of Industrial and Management Optimization, 2011, 7 (1) : 157-174. doi: 10.3934/jimo.2011.7.157
[2]

Chunrong Chen. A unified nonlinear augmented Lagrangian approach for nonconvex vector optimization. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 495-508. doi: 10.3934/naco.2011.1.495
[3]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial and Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177
[4]

Xueyong Wang, Yiju Wang, Gang Wang. An accelerated augmented Lagrangian method for multi-criteria optimization problem. Journal of Industrial and Management Optimization, 2020, 16 (1) : 1-9. doi: 10.3934/jimo.2018136
[5]

Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial and Management Optimization, 2019, 15 (1) : 235-259. doi: 10.3934/jimo.2018041
[6]

Lipu Zhang, Yinghong Xu, Zhengjing Jin. An efficient algorithm for convex quadratic semi-definite optimization. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 129-144. doi: 10.3934/naco.2012.2.129
[7]

Zhong Wan, Chaoming Hu, Zhanlu Yang. A spectral PRP conjugate gradient methods for nonconvex optimization problem based on modified line search. Discrete and Continuous Dynamical Systems - B, 2011, 16 (4) : 1157-1169. doi: 10.3934/dcdsb.2011.16.1157
[8]

Chunlin Hao, Xinwei Liu. Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 19-29. doi: 10.3934/naco.2012.2.19
[9]

Liangliang Sun, Fangjun Luan, Yu Ying, Kun Mao. Rescheduling optimization of steelmaking-continuous casting process based on the Lagrangian heuristic algorithm. Journal of Industrial and Management Optimization, 2017, 13 (3) : 1431-1448. doi: 10.3934/jimo.2016081
[10]

Fengqiu Liu, Xiaoping Xue. Subgradient-based neural network for nonconvex optimization problems in support vector machines with indefinite kernels. Journal of Industrial and Management Optimization, 2016, 12 (1) : 285-301. doi: 10.3934/jimo.2016.12.285
[11]

Yigui Ou, Xin Zhou. A modified scaled memoryless BFGS preconditioned conjugate gradient algorithm for nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2018, 14 (2) : 785-801. doi: 10.3934/jimo.2017075
[12]

Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial and Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103
[13]

Weijun Zhou, Youhua Zhou. On the strong convergence of a modified Hestenes-Stiefel method for nonconvex optimization. Journal of Industrial and Management Optimization, 2013, 9 (4) : 893-899. doi: 10.3934/jimo.2013.9.893
[14]

Jean-Paul Arnaout, Georges Arnaout, John El Khoury. Simulation and optimization of ant colony optimization algorithm for the stochastic uncapacitated location-allocation problem. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215
[15]

Alireza Goli, Hasan Khademi Zare, Reza Tavakkoli-Moghaddam, Ahmad Sadeghieh. Application of robust optimization for a product portfolio problem using an invasive weed optimization algorithm. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 187-209. doi: 10.3934/naco.2019014
[16]

Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial and Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891
[17]

Arezu Zare, Mohammad Keyanpour, Maziar Salahi. On fractional quadratic optimization problem with two quadratic constraints. Numerical Algebra, Control and Optimization, 2020, 10 (3) : 301-315. doi: 10.3934/naco.2020003
[18]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005
[19]

Xiangyu Gao, Yong Sun. A new heuristic algorithm for laser antimissile strategy optimization. Journal of Industrial and Management Optimization, 2012, 8 (2) : 457-468. doi: 10.3934/jimo.2012.8.457
[20]

Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial and Management Optimization, 2019, 15 (2) : 909-932. doi: 10.3934/jimo.2018077

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (284)
  • HTML views (0)
  • Cited by (9)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy