DOI: https://doi.org/10.31319/2519-8106.2(39)2018.154222

РОЗВ’ЯЗУВАННЯ КВАДРАТИЧНОЇ ЗАДАЧІ ПРО ПРИЗНАЧЕННЯ

Анатолій Іванович Косолап, Дмитро Олександрович Дубовик

Анотація


Стаття присвячена проблемі розв’язання квадратичної задачі про призначення (QAP) з використанням сучасних методів оптимізації. В статті розглянуто декілька різних методів дослідження QAP, але вони не знаходять найкращі розв’язки та потребують багато часу.

В роботі використано метод Франка-Вулфа, який потребує досить мало часу, навіть при розв’язуванні задач великої розмірності. Далі для розв’язування задачі QAP використано точну квадратичну регуляризацію. Це дозволяє отримувати найкращі розв’язки в задачі QAP навіть для задач великої розмірності.

Проведені порівняльні числові експерименти підтверджують ефективність методу точної квадратичної регуляризації при розв’язуванні задач QAP. 

Ключові слова


квадратична задача про призначення; QAP; метод Франка-Вулфа; квадратична регуляризація

Повний текст:

PDF

Посилання


Commander C.W. A Survey of the Quadratic Assignment Problem with Applications / C.W. Commander. – The University of Florida, 2003. – 18 p.

Cook W. Fifty-Plus Years of Combinatorial Integer Programming / W. Cook. – Georgia Institute of Technology, 2009. – 39 p.

Kenneth V.P. Differential Evolution. A Practical Approach to Global Optimization / V.P. Kenneth, R.M. Storn, J.A. Lampinen. – Berlin, Heidelberg: Springer-Verlag, 2005. –542 p.

Lawler E. L. The quadratic assignment problem / E. L. Lawler // Management Science. – 1963. – № 9. – P. 586 – 599.

Kaufmann L. An algorithm for the quadratic assignment problem using Bender’s decomposition / L. Kaufmann, F. Broeckx // European Journal of Operational Research. – 1978. – № 2. – P. 204 – 211.

Frieze A. M. On the quadratic assignment problem / A. M. Frieze, J. Yadegar // Discrete Applied Mathematics. – 1983. – № 5. – P. 89 – 98.

Adams W. P. Improved linear programming-based lower bounds for the quadratic assignment problem, in Quadratic Assignment and Related Problems / W. P. Adams, T. A. Johnson ; P. M. Pardalos and H. Wolkowicz eds. // DIMACS Series on Discrete Mathematics and Theoretical Computer Science. – 1994. – № 16. – P. 43 – 75.

Burkard R. E. Locations with spatial interactions: the quadratic assignment problem / R. E. Burkard, P. B. Mirchandani, R. L. Francis eds. // Discrete Location Theory, John Wiley and Sons, 1991. – P. 387–437.

Burkard R. E. A heuristic for quadratic boolean programs with applications to quadratic assignment problems / R. E. Burkard, T. Bonniger // European Journal of Operational Research. – 1983. –

№ 13. – P. 374 – 386.

Burkard R. E. Assignment and matching problems: Solution methods with Fortran programs / R. E. Burkard, U. Derigs // Lecture Notes in Economics and Mathematical Systems. – Springer-Verlag, Berlin. – 1980. – 148 p.

Glover F. Improved linear integer programming formulations of nonlinear integer problems / F. Glover // Management Science. – 1975. – № 22. – P. 455 – 460.

Geoffrion A. M. Lagrangean relaxation and its uses in integer programming / A. M. Geoffrion // Mathematical Programming Study. – 1974. – № 2. – P. 82 – 114.

Gilmore P. C. Optimal and suboptimal algorithms for the quadratic assignment problem / P. C. Gilmore // SIAM Journal on Applied Mathematics. – 1962. – № 10. – P. 305 – 313.

Gavett J. W. The optimal assignment of facilities to locations by branch and bound / J. W. Gavett, N. V. Plyter // Operations Research. – 1966. – № 14. – P. 210 – 232.

Land A. M. A problem of assignment with interrelated costs / A. M. Land // Operations Research Quarterly. – 1963. – № 14. – P. 185 – 198.

Nugent C. E. An experimental comparison of techniques for the assignment of facilities to locations / C. E. Nugent, T. E. Vollmann, J. Ruml // Journal of Operations Research. – 1969. – № 16. – P. 150 – 173.

Burkard R.E. Assignment problems / R.E. Burkard. – University of Bolona, 2009. - 392 p.

Dorigo M. Positive feedback as a search strategy / M. Dorigo, V. Maniezzo, A. Colorni. – Department of Electronics and Information, Milan : Polytechnic of Milan, 1991. – 20 p. (Technical Report 91-016).

Dorigo M. The ant system: Optimization by a colony of cooperating agents / M. Dorigo, V. Maniezzo, A. Colorni // IEEE Transactions on Systems, 1996. – vol. 26(1). – P. 29 – 41.

Rutkovskaya D. Neural networks, genetic algorithms and fuzzy systems / D. Rutkovskaya, M. Pilinsky, L. Rutkovsky ; trans. from polish I.D. Rudinsky. – M .: Hotline – Telecom, 2006. – 452 p.

Моров В.А. Применение генетического алгоритма к задачам оптимизации. Реализация генетического алгоритма для проблемы коммивояжера / В. А. Моров // Вестник Амурского Государственного Университета. Естественные и экономические науки. – 2012. – № 57. – С. 18 – 22.

Taillard E. Robust taboo search for the quadratic assignment problem / E. Taillard // Parallel Computing. – 1991. – № 17. – P. 443 – 455.

Battiti R. The reactive tabu search / R. Battiti, G. Tecchiolli // ORSA Journal on Computing. – 1994. – № 6(2). – P. 126 – 140.

Drezner Z. The extended concentric tabu for the quadratic assignment problem / Z. Drezner // European Journal of Operational Research. – 2005. – № 160. – P. 416 – 422.

Mину M. Математическое программирование / M. Mину ; перев. с фран. А.И. Штерна. – М.: Наука, 1990. – 487 p.

Косолап A. И. Глобальная оптимизация. Метод точной квадратичной регуляризации / А.И. Косолап. – Днепропетровск: ПГАСА, 2015. –164 p.

Nocedal, J. Numerical optimization / J. Nocedal, S.J. Wright. – Springer, 2006. – 685 p.