РОЗВ’ЯЗУВАННЯ КВАДРАТИЧНОЇ ЗАДАЧІ ПРО ПРИЗНАЧЕННЯ
DOI:
https://doi.org/10.31319/2519-8106.2(39)2018.154222Ключові слова:
квадратична задача про призначення, QAP, метод Франка-Вулфа, квадратична регуляризаціяАнотація
Стаття присвячена проблемі розв’язання квадратичної задачі про призначення (QAP) з використанням сучасних методів оптимізації. В статті розглянуто декілька різних методів дослідження QAP, але вони не знаходять найкращі розв’язки та потребують багато часу.
В роботі використано метод Франка-Вулфа, який потребує досить мало часу, навіть при розв’язуванні задач великої розмірності. Далі для розв’язування задачі QAP використано точну квадратичну регуляризацію. Це дозволяє отримувати найкращі розв’язки в задачі QAP навіть для задач великої розмірності.
Проведені порівняльні числові експерименти підтверджують ефективність методу точної квадратичної регуляризації при розв’язуванні задач QAP.Посилання
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.
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:
a. Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
b. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
c. Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
