SYMMETRIC TRIANGULAR DECOMPOSITION FOR CONSTRUCTING APPROXIMATIONS TO SOLVING THE QUADRATIC ASSIGNMENT PROBLEM

Мұқаба

Дәйексөз келтіру

Толық мәтін

Ашық рұқсат Ашық рұқсат
Рұқсат жабық Рұқсат берілді
Рұқсат жабық Рұқсат ақылы немесе тек жазылушылар үшін

Аннотация

The permutation matrices that arise in the process of triangular decomposition of shifted symmetric matrices with the choice of the maximum modulo leading element on the diagonal are used as initial approximations for a series of elementary permutations that improve the target value of the quadratic assignment problem. The results of testing the proposed method on 128 test tasks from QAPLIB are presented.

Авторлар туралы

I. Kaporin

Federal Research Center "Computer Science and Control", RAS

Email: igorkaporin@mail.ru
Moscow, Russia

Әдебиет тізімі

  1. Koopmans T.C., Beckmann M. Assignment problems and the location of economic activities // Econometrica. 1957. V. 25. № 1. P. 53–76.
  2. Hurtado O.G., Poveda R.Ch, Moncada J. Exact and approximate sequential methods in solving the quadratic assignment problem // J. Language and Linguistic Studies. 2022. V. 18. № 3. P. 237–244.
  3. Burkard R., Dell’Amico M., Martello S. Assignment problems: revised reprint. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 2012.
  4. Zaied A.N.H., Shawky L.A.E.-F. A survey of quadratic assignment problems // Inter. J. Comput. Appl. 2014. V. 101. № 6. P. 28–36.
  5. Loiola E.M., De Abreu N.M.M., Boaventura-Netto P.O., Hahn P., Querido T. A survey for the quadratic assignment problem //Europ. J. Operat. Res. 2007. V. 176. № 2. P. 657–690.
  6. Sahni S., Gonzalez T. P-complete approximation problems // J. ACM (JACM). 1976. V. 23. № 3. P. 555–565.
  7. Fischetti M., Monaci M., Salvagnin D. Three ideas for the quadratic assignment problem // Operat. Res. 2012. V. 60. № 3. P. 954–964.
  8. Burkard R.E., Cela E., Karisch S.E., Rendl F., Anjos M., Hahn P. QAPLIB – A Quadratic Assignment Problem Library – Problem instances and solutions, [dataset]. University of Edinburgh; Computational Optimization Research At Lehigh (2022). https://doi.org/10.7488/ds/3428 https://datashare.ed.ac.uk/handle/10283/4390 https://coral.ise.lehigh.edu/data-sets/qaplib/qaplib-problem-instances-and-solutions/
  9. Hadley S.W., Rendl F., Wolkowicz H. Symmetrization of nonsymmetric quadratic assignment problems and the Hoffman-Wielandt inequality // Linear Algebra and its Applications. 1992. V. 167. P. 53–64.
  10. Silva A., Coelho L.C., Darvish M. Quadratic assignment problem variants: A survey and an effective parallel memetic iterated tabu search // Europ. J. Operat. Res. 2021. V. 292. № 3. P. 1066–1084.

Қосымша файлдар

Қосымша файлдар
Әрекет
1. JATS XML
Жүктеу

© Russian Academy of Sciences, 2025