Симметрии многогранника системы независимости и их применение для решения задачи об упаковке множества

• Автор: Червяков, Олег Владимирович
• Шифр специальности: 05.13.16
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Омск
• Количество страниц: 126 с. : ил.

1.1. Основные понятия

1.2. Линейные симметрии и автоморфизмы.

1.3. Аффинные симметрии и Яотображения

1.4. Критерий существования Яотображения

1.5. Симметрии с единичным сдвигом.

1.6. Аффинные симметрии специальных систем независимости

Глава 2. Понижение размерности задачи

на системе независимости

2.1. Постановки задач

2.2. Задача об упаковке множества

2.3. Полиэдральная схема понижения размерности.

2.4. Комбинаторная схема.
2.5. Процедура ветвления и задача об упаковке .
Глава 3. Приближенные алгоритмы
решения задачи об упаковке
3.1. Приближенная схема понижения размерности.
3.2. Приближенный алгоритм решения задачи об упаковке .
3.3. Приближенный алгоритм для некоторых
специальных систем независимости
3.4. Задача о наибольшем независимом множестве
вершин и алгоритм ПР
3.5. Вычислительный эксперимент.
Заключение
Список литературы


Эксперименты проводились на задаче об упаковке множества первая и вторая серии экспериментов и задаче о наибольшем независимом множестве вершин третья и четвертая серии. В общей сложности было решено 5 задач об упаковке множества и 6 задач о наибольшем независимом множестве вершин графа. Из полученных результатов вытекает, что предложенные в работе приближенные алгоритмы имеют хорошую экспериментальную оценку точности как на случайных, так и на специально сгенерированных задачах и в среднем лучше известного жадного алгоритма, алгоритмов Хватала и Кларксона 1. Эксперименты показали, что использование в метоле ветвей и границ процедуры понижения размерности, основанной на симметриях многогранника, дает значительное ускорение процесса решения задач. Результаты работы докладывались на Втором Сибирском конгрессе по прикладной и индустриальной математике Новосибирск, , Хой Всероссийской конференции Математическое программирование и приложения Екатеринбург, , Международной конференции Проблемы оптимизации и экономические приложения Омск, . Международной Сибирской конференции по исследованию операций Новосибирск. Х1ой Всероссийской конференции Математическое программирование и приложения Екатеринбург, , а также на семинарах кафедры математического моделирования Омского государственного университета. Института информационных технологий и прикладной математики СО РАН и Института математики им. С.Л. Соболева СО РАН. Основные результаты диссертации опубликованы в работах . Автор выражает искреннюю признательность научному руководителю Р. Ю.Симанчву за постоянное внимание и всестороннюю поддержку при выполнении данной работы.