Анализ и решение задач максимальной и минимальной выполнимости с использованием L-разбиения

• Автор: Адельшин, Александр Владимирович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Омск
• Количество страниц: 102 с. : ил.

Содержание
Введение

Глава 1. Задачи дискретной оптимизации и выполнимость логических формул

1.1 Постановки задач и их сложность.

1.2 Связь с другими задачами и некоторые приложения . .

1.3 Гструктура задач целочисленного программирования . .

1.4 Методы решения.

Глава 2. Исследование задач с использованием Гразбиения

2.1 Гструктура многогранников задач максимальной и минимальной выполнимости.

2.2 Построение специальных семейств логических формул . .

2.3 Анализ Гнакрытий задач

Глава 3. Разработка и анализ алгоритмов для задач максимальной и минимальной выполнимости
3.1 Анализ некоторых алгоритмов целочисленного программирования на основе Гразбиения.
3.2 Алгоритмы точного решения для задачи максимальной выполнимости
3.3 Алгоритмы локального поиска для задачи максимальной выполнимости.
Глава 4. Результаты вычислительного эксперимента
4.1 Исследование и сравнение алгоритмов точного решения . .
4.2 Исследование алгоритмов локального поиска
Заключение
Список литературы


Разработаны алгоритмы точного и приближенного решения невзвешенной задачи максимальной выполнимости, основанные на использовании метода перебора . Проведены экспериментальные исследования эффективности этих алгоритмов. Диссертация состоит из введения, четырех глав и заключения. В первой главе приводятся постановки задач выполнимости, максимальной и минимальной выполнимости, рассмотрен ряд связанных с ними задач дискретной оптимизации. Указаны некоторые полиномиально разрешимые подклассы задач выполнимости. Приведен краткий обзор существующих алгоритмов решения данных задач, включая точные, эвристические и приближенные алгоритмы с гарантированной оценкой точности. Изложен метод регулярных разбиений, который является достаточно продуктивным при исследовании задач ЦП и анализе алгоритмов их решения. Во второй главе проводится анализ задач выполнимости, максимальной и минимальной выполнимости на основе целочисленного программирования и Ь-разбиения. Показано, что многогранник задачи максимальной выполнимости имеет альтернирующую //-структуру, а мощность любого дробного комплекса многогранника задачи минимальной выполнимости не превосходит величины т + 1, где га - число скобок данной логической формулы, причем полученная оценка является достижимой. Построены семейства логических формул, для которых исследована //-структура задач выполнимости, максимальной и минимальной выполнимости. В частности, выделены семейства, для которых все указанные задачи имеют мощности //-накрытий, растущие экспоненциально с увеличением числа переменных в формуле. Задачи из построенных семейств могут быть использованы в качестве тестовых примеров для различных алгоритмов. Третья глава посвящена разработке алгоритмов точного и приближенного решения задачи максимальной выполнимости, анализу ряда алгоритмов ЦП, основанных на использовании релаксационных множеств, при решении предложенных нами семейств задач максимальной и минимальной выполнимости. L-классов и ветвей и границ (метод Лэнд и Дойг) растут экспоненциально с увеличением числа переменных. Показано, что при решении некоторых задач из этих семейств первым алгоритмом Гомори используется линейное число отсечений. Предложены схемы точного решения невзвешенной задачи максимальной выполнимости и алгоритмы локального поиска, основанные на сведении задачи к конечной последовательности задач выполнимости и переборе L-классов. В четвертой главе содержатся результаты вычислительного эксперимента для разработанных нами алгоритмов. Проведено сравнение точного алгоритма с пакетом OPL Studio и с точным алгоритмом, предложенным B. Borchers и J. Furman [), на сериях случайных задач, семействах из электронных библиотек DIMACS и SATLIB, а также на семействах задач, построенных во второй главе. Кроме того, исследованы алгоритмы локального поиска при решении некоторых задач из библиотеки DIMACS. Выполнено сравнение этих алгоритмов относительно времени работы и точности получаемых решений. В целом полученные результаты экспериментального исследования указывают на эффективность использования предложенных алгоритмов при точном или приближенном решении задач максимальной выполнимости. Основные результаты диссертации опубликованы в работах [1 - 5, 7, , , , , ) и докладывались на следующих конференциях и семинарах: Международной школе-семинаре "Методы оптимизации и их приложения" (Иркутск, и ), Международной конференции по исследованию операций OIV (Дуйсбург, Германия, ), Международном семинаре "Алгебра и линейная оптимизация", посвященном -летию со дня рождения С. Екатеринбург, ), Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, ), Mini Euro Conference on VNS (Тенерифе, Испания, ), XXXVII Региональной молодежной школе-конференции "Проблемы теоретической и прикладной математики"(Екатеринбург, ), а также на научном семинаре "Математическое моделирование и дискретная оптимизация"в Омском филиале Института математики им. C.JI. Соболева СО РАН (-). Автор благодарит научного руководителя Колоколова A. A. за внимание и поддержку при выполнении данной работы, а также Ягофарову Д. И. и Тюрюмова А. Н. за сотрудничество.