Разработка и анализ алгоритмов для задачи выполнимости и ее обобщений на основе L-разбиения

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

Оглавление
Введение

1 Задача выполнимости и методы ее решения .

1.1 Постановки задач и модели целочисленного

программирования

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

1.3 Алгоритмы для задач выполнимости и максимальной

выполнимости

2 Исследование и решение задачи выполнимости с использованием разбиения

2.1 Предварительные сведения

2.2 Анализ структуры многогранника задачи

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


Сначала дается определение //-разбиения и указываются его свойства, приводятся некоторые известные семейства задач выполнимости, мощности //-накрытий которых растут* экспоненциально с увеличением числа переменных в формуле. Затем исследуется //-структура задачи 2-выполнимости. Показывается, что в случае выполнимой формулы мощность //-накрытия не превосходит п — 1, где п - число переменных в формуле. Изучается также Ь-структура некоторых специальных логических формул. Из полученных результатов, в частности, следует полиномиальная разрешимость задачи 2-выполнимости и задачи выполнимости хорновских формул. Ранее полиномиальная разрешимость этих задач была установлена другими методами (, ]. Далее описывается предложенный в работе алгоритм перебора />-классов ЬСЕ для решения задачи выполнимости и рассматриваются некоторые его модификации. В отличие от метода перебора //-классов для общей задачи ЦЛП поиск представителей Ь-классов удается осуществлять комбинаторным путем, без решения задач линейного программирования. В третьей главе рассматриваются задача максимальной выполнимости и задача о минимальном комитете. В первом разделе излагаются разработанные нами алгоритмы локального поиска для задачи максимальной выполнимости. Общая идея этих алгоритмов состоит в построении последовательности окрестностей, в которых осуществляется направленный перебор точек. Для каждой из этих точек решается специальная задача выполнимости алгоритмом ЬСЕ. Следующие разделы посвящены задаче о минимальном комитете, построению и анализу соответствующих ей моделей целочисленного линейного программирования. Кроме того, проводится экспериментальное сравнение двух моделей ЦЛП на основе //-разбиения. В четвертой главе обсуждаются результаты экспериментальных исследований для разработанных нами алгоритмов. Расчеты выполнялись на сериях тестовых задач из электронной библиотеки ЭАТЫВ [4] и некоторых специальных семействах логических формул. Первый раздел посвящен применению для решения задачи выполнимости алгоритмов перебора //-классов. Предлагается и анализируется несколько вариантов предварительной сортировки переменных. Проводится сравнение алгоритма ЬСЕ с известным точным гибридным алгоритмом, предложенным авторами статьи []. Выделены семейства задач из электронной библиотеки, па которых ЬСЕ заметно превосходит известный алгоритм. В следующем разделе исследуется зависимость времени работы параллельного алгоритма перебора . В целом результаты экспериментов указывают на эффективность применения предложенных алгоритмов для решения задач выполнимости достаточно большой размерности и возможность их использования в прикладных исследованиях. Выполнено сравнение двух алгоритмов но времени работы и точности получаемых решений. Для нахождения “хороших” начальных приближений предлагается использовать генетический алгоритм. Проведенные исследования показали целесообразность применения алгоритмов локального поиска для приближенного решения задачи максимальной выполнимости. Mini Euro Conference on VNS (Тенерифе, Испания, ), XXXVII Региональной молодежной школе-конференции “Проблемы теоретической и прикладной математики” (Екатеринбург, ), III Всероссийской конференции “Проблемы оптимизации и экономические приложения” (Омск, 0G), а также на заседаниях научного семинара “Математическое моделирование и дискретная оптимизация” в Омском филиале Института математики им. С.Л. Соболева СО РАН. Основные результаты работы опубликованы в [, -, , , -, , 5G, -]. Автор благодарит научного руководителя д. A.A. Колоколова за постоянное внимание к работе, а также выражает признательность к. A.B. Адельшииу и А. Н. Тюрюмову за полезные советы и плодотворные обсуждения. Глава посвящена постановкам задачи выполнимости логической формулы и некоторых близких задач, обзору методов их решения. В п. Рассматриваются два подхода к решению несовместных систем ограничений. Один из них реализуется, в частности, в задаче максимальной выполнимости. Для другого вводится понятие комитетного решения и формулируется задача о минимальном комитете. В и. Раздел 1. Для постановки задачи выполнимости введем необходимые определения. Логическая переменная - это переменная, которая может принимать только два значения: истина или лооюь.