- Код статьи
- S3034533S0044466925070043-1
- DOI
- 10.7868/S303453325070043
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том 65 / Номер выпуска 7
- Страницы
- 1110-1117
- Аннотация
- Матрицы перестановки, возникающие в процессе треугольного разложения сдвинутых симметричных матриц с выбором максимального по модулю ведущего элемента на диагонали, используются как начальные приближения для серии элементарных перестановок, улучшающих целевое значение квадратичной задачи о назначениях. Приведены результаты тестирования предлагаемого метода на 128 тестовых задачах из QAPLIB.
- Ключевые слова
- квадратичная задача о назначениях симметричное треугольное разложение полный выбор ведущего элемента на диагонали
- Дата публикации
- 23.04.2025
- Год выхода
- 2025
- Всего подписок
- 0
- Всего просмотров
- 18
Библиография
- 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.
