Метод плетей и границ в квадратичной задаче о назначениях
Hooker J. Logic-based methods for optimization: combining optimization and constraint satisfaction. A Wiley-Interscience Publication, John Wiley Sz Sons, Inc. 2000. Hadley S. W., Rendi F., Wolkowicz H. A New Lower Bound via Projection for the Quadratic Assignment Problem. Mathematics of Operations Research 17, 1993, 727−739. Кнут Д. Искусство программирования для ЭВМ. т.З. Сортировка и поиск… Читать ещё >
Содержание
Основные результаты диссертационной работы были доложены на Всероссийской конференции «Дискретный анализ и исследование операций», проходившей в Новосибирске летом 2004 года, и опубликованы в [44, 56].
Заключение.
Диссертационная работа посвящена развитию методов поиска оптимума в ИР-трудных задачах дискретной оптимизации. Этот поиск, как правило, осуществляется посредством методов неявного перебора. В традиционном методе ветвей и границ разбиение множества ф всех решений исследуемой задачи определяется деревом частичных решений — поддеревом полного дерева, и к одному множеству такого разбиения относятся все элементы множества ф, являющиеся ветвями полного дерева решений и продолжениями ровно одной ветви в дереве частичных решений. *
Предложенная в работе технология (метод плетей и границ) является обобщением метода ветвей и границ. Она позволяет, во-первых, строить так называемые недревовидные покрытия: для того, чтобы представить каждый элемент этого покрытия в виде объединения множеств, соответствующих ветвям в дереве частичных решений, требуется построить дерево, в котором ветвей больше, чем элементов в недревовидном покрытии.
Во-вторых, строится такое покрытие, в котором удается оценить сразу не одно частичное решение, как в методе ветвей и границ, а целый специально сконструированный набор частичных решений — плеть.
Основой для формализации метода плетей и границ служат следующие результаты.
1. В работе сформулировано и обосновано правило подстановки, которое позволяет получать наборы плетей, используя замкнутые диаграммы, являющиеся интерпретациями невыполнимых логических формул.
2. Сформулирована и доказана теорема о полноте набора плетей в задаче дискретной оптимизации, которая гарантирует, что набор плетей, построенный по правилу подстановки, покрывает все множество решений задачи.
3. Описан метод плетей и границ в общем виде.
Метод плетей и границ применен для квадратичной задачи о назначениях, одной из основных сложностей которой является многоэкстремальность, т. е. наличие большого числа решений, на которых целевая функция достигает значений, близких к оптимальному, но не оптимальных. Причем часто эти решения рассредоточены по разным ветвям дерева частичных решений. Если, же все такие ветви попадают в одну плеть, то за одно оценивание мы можем отсечь большой класс неперспективных решений.
В отличие от метода ветвей и границ параметрами в методе плетей и границ являются не только выбор способа оценивания и тактики ветвления, но и способ формирования недревовидных покрытий. Для квадратичной задачи о назначениях найдены реализации соответствующих параметров, а именно:
1. Предложены способы формирования полного набора плетей на основе специальных невыполнимых логических формул (Цейтина, Хорна, пт-циклов). Получены и обоснованы методы построения плетей с известным локальным оптимумом.
2. Разработан способ оценивания плети для задачи, базирующийся на решении линейной задачи о назначениях. Проведены исследования структуры плетей с целыо улучшения этой нижней оценки, результатом которых явилась улучшенная нижняя оценка плети.
Представлена алгоритмическая реализация метода плетей и границ для квадратичной задачи о назначениях. Проведены численные эксперименты с целью проверки корректности и выявления наилучших значений параметров алгоритма. Результаты экспериментов позволяют сделать следующие
выводы:
Ключевую роль в представленной реализации играет построение нижней оценки.
Существуют замкнутые шаблоны, применение которых значительно сокращает перебор.
Алгоритм позволяет решать квадратичные задачи о назначениях размера до 20. *
Предложенный метод плетей и границ может быть использован для любых задач дискретной оптимизации. При этом достаточно, используя семантику задачи, определить способ оценивания.
Алгоритмическая реализация метода может быть использована при составлении компьютерных программ для нахождения оптимального решения в конкретных задачах о назначениях, например, проектировании клиник и бизнес-центров, расположении клавиш на панели управления некоторого устройства и других.
Метод плетей и границ в квадратичной задаче о назначениях (реферат, курсовая, диплом, контрольная)
1. Романовский И. В. Дискретный анализ. СПб.: Невский ДиалектБХВПетербург, 2003. 320 с.:ил.
2. Давыдов Г. В., Давыдова И. М. Метод плетей и границ. Исследование операций и статистическое моделирование. Издательство Санкт-Петербургского Университета. 1994. Вып. 6. с.14−30.
3. Давыдов Г. В. Синтез метода резолюций с обратным методом. Записки научных семинаров ЛОМИ 20(1971), с. 24−35.
4. Давыдов Г. В., Давыдова И. М. Двойственные алгоритмы в дискретной оптимизации. Вопросы кибернетики. 1987. Вып. 131. с.90−117.
5. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Москва: Мир, 1982.
6. Sahni S., Gonzalez Т. P-complete Approximation Problems. Journal of the ACM 23, 1976, 555−565.
7. Koopmans Т. C., Beckmann M. Assignment Problems and the Location of Economic Activities. Econometrica, vol.25, No. 1, 1957, pp.53−768| Clay Mathematics Institute. Millennium Problems. http://www.claymath.org/millennium/PvsNP/.
8. Burkard R., Pardalos P., Pitsoulis L., Cela E. The Quadratic Assignment Problem. Optimirung und Kontrolle, Nr. 126, 1998.
9. Cela E. The quadratic assignment problem: special cases and relatives. PhD thesis, Graz University of Technology, Graz, Austria, 1995.
10. Burkard R., Cela E. Linear Assignment Problems and Extensions. Optimirung und Kontrolle, Nr.127, 1998.
11. Elshafei A. N. Hospital Layout as a Quadratic Assignment Problem. Operations Research Quarterly 28, 1977, 167−179.
12. Maniezzo V., Colorni A. The Ant System Applied to the Quadratic Assignment Problem. Tech. Rep. IRIDIA/94−28, Universite Libre de Bruxelles, Belgium, 1994.
13. Burkard R. E., Offerman J. Entwurf von Schreibmaschinentastaturen mittels quadratischer Zuordnungsprobleme. Z. Operations Research 21, 1977, B121-B123.
14. Eiselt H. A., Laporte G. A Combinatorial Optimization Problem Arising in Dartboard Design. The Journal of the Operational Research Society 42,1991, 113−118.
15. Commander C. W., Pardalos P. M. A Survey of the Quadratic Assignment Problem, with Applications. Submitted to The Morehead Electronic Journal of Applicable Mathematics, 2003.
16. Carlson R. C., Nemhauser G. L. Scheduling to minimize cost. Operations Research 14, 1966, 52−58.
17. Brixius N. W., Anstreicher K. M. The Steinberg wiring problem. Working Paper, The University of Iowa, October 2001.
18. Geoffrion A. M., Graves G. W. Scheduling Parallel Production Lines with Changeover Costs: Practical Applications of a Quadratic Assignment/LP Approach. Operations Research 24, 1976, 595−610.
19. Edwards C. S. The derivation of a greedy approximator for the Koopmans-Beckmann quadratic assignment problem. Proceedings of the 77 -th Combinatorial Programming Conference (CP77), 1977, 55−86.
20. Edwards C. S. A branch and bound algorithm for the Koopmans-Beckmann quadratic assignment problem. Mathematical Programming Study 13, 1980, 35−52.
21. Lawler E. L. The Quadratic Assignment Problem. Management Science 9, 1963, 586−599.
22. Gilmore P. C. Optimal and Suboptimalf Algorithms for the Quadratic Assignment Problem. SIAM Journal on Applied Mathematics 10, 1962, SOS-SIS.
23. Hadley S. W., Rendi F., Wolkowicz H. A New Lower Bound via Projection for the Quadratic Assignment Problem. Mathematics of Operations Research 17, 1993, 727−739.
24. Anstreicher K. M., Brixius N. W., Linderoth J., Goux J. -P. Solving Large Quadratic Assignment Problems on Computational Grids. Mathematical Programing, Series B 91, 2002, 563−588.
25. Nugent, Vollman T. E., Ruml J. An experimental comparison of techniques for the assignment of facilities to locations. Operations Research, 1968: 150−173.
26. Armour G. C., Buffa E. S. Heuristic Algorithm and Simulation Approach to Relative Location of Facilities. Management Science 9, 1963, 294−309.
27. Aarts E., Lenstra J. K. Local Search in Combinatorial OptimizationJohn Wiley & Sons, 1997.
28. Glover F. Tabu Search Part 2. ORSA Journal on Computing2, no. 1, 1989, 4−32.
29. Glover F. Tabu Search Part 1. ORSA Journal on Computing 1, 1989 no. 3, 190−206.
30. Burkard R. E., Rendl F. A. Thermodynamically Motivated Simulation Procedure for Combinatorial Optimization Problems. European Journal of Operational Research 17, 1983, 169−174.
31. Cerny V. Thermodynamical Approach to the Traveling Salesman Problem: An Effcient Simulation Algorithm. Journal of Optimization Theory and Applications 45, 1985, 41−51.
32. Tate D., Smith A. A genetic approach to the quadratic assignment problem. Computers and Operations Reseach, vol. 22, no. l, 1995, 73−83.
33. Gambardella L. M., Taillard E., Dorigo M. Ant Colonies for the Quadratic Assignment Problem. Journal of the Operational Research Society, 50, 1999, 167−176.
34. Pitsoulis L. A Sparse GRASP for Solving the Quadratic Assignment Problem. M.Eng. thesis, The University of Florida, 1994.
35. Solving QAPLIB, a selected DPLP dataset, and other difficult instances with GATS, http://acrl.cs.unb.ca/research/gats/.
36. QAPLIB Home Page, http://www.seas.upenn.edu/qaplib/ (Last update: 10 March 2005).
37. Haken A. Intractability of resolution. Theoretical Computer Science, 39, 1985, 297−308.
38. Цейтин F. С. О сложности вывода в исчислении высказываний. Записки научных семинаров ЛОМИ, 8, «Наука», Л., 1968, 234−259.
39. Kowalski R. A. Logic for Problem Solving. Elsevier-North Holland, 1979, 287 p.
40. Мартюшев А. В. Алгоритм решения квадратичной задачи о назначениях методом плетей и границ. Вестник молодых ученых, серия «Прикладная математика и механика», № 1, 2004.
41. Robinson J. A. A machine-oriented logic based on resolution priciple. Journal of the ACM, pages 23−41, 1965.
42. Jonker R., Volgenant A. A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems. Computing 38, 1987, 325−340.
43. Дистель R Теория графов. Пер. с англ. Новосибирск: Изд-во Ин-та математики, 2002. — 336 с.
44. Берж К. Теория графов и ее применения. Издательство Иностранной Литературы, Москва, 1962.
45. Berge С. Graphes et hypergraphes. Dunod (Paris, 1970).
46. Hooker J. Logic-based methods for optimization: combining optimization and constraint satisfaction. A Wiley-Interscience Publication, John Wiley Sz Sons, Inc. 2000.
47. Hopcroft J., Karp R. M. An n5/2 algorithm for maximum Matchings in bipartite graphs. SIAM J. Comput., 1973, 2, s. 225−231.
48. Кнут Д. Искусство программирования для ЭВМ. т.З. Сортировка и поиск. Пер. с англ. М.: Мир, 1978.
49. Maus A. Sorting by generating the sorting permutation, and the effect of caching on sorting. Norsk informatikkonferanse, Oslo, 20−22 Nov, 2000.
50. Липский В. Комбинаторика для программистов. Пер. с польск.- М.: Мир, 1988. 213 с. ил.
51. Hall Ph. On representatives of subsets. J. London Math. Soc., 1935, 10, s. 26−30.
52. Eric Taillard home page. Quadratic assignment instances. http://ina.eivd.ch/collaborateurs/etd/problemes.dir/qap.dir/qap.html.