Содержание к диссертации
Введение 4
1 Задача выполнимости и методы ее решения ... 10
Постановки задач и модели целочисленного программирования 10
Связь с другими задачами и приложения 18
Алгоритмы для задач выполнимости и максимальной выполнимости 25
2 Исследование и решение задачи выполнимости с
использованием L-разбиения 35
Предварительные сведения 36
Анализ L-структуры многогранника задачи выполнимости 40
Алгоритмы перебора L-классов для задачи выполнимости 50
Параллельные алгоритмы 58
3 Применение метода перебора L-классов к решению
некоторых задач дискретной оптимизации .... 65
3.1 Разработка алгоритмов локального поиска для задачи
максимальной выполнимости с использованием перебора
Zr классов 60
Модели целочисленного линейного программирования для задачи о минимальном комитете 68
Экспериментальное сравнение L-структуры моделей . 76
4 Экспериментальные исследования 80
Вычислительный эксперимент для алгоритмов перебора L-классов 80
Результаты эксперимента для параллельного алгоритма 89
Сравнение эвристических алгоритмов 91
Заключение 96
Список литературы 98
Приложение 113
Введение к работе
Задача выполнимости логической формулы играет важную роль в дискретіюіі оптимизации и теории сложности [7, 42]. Она является первой задачей, для которой доказана NP-полнота [G7], к ней сводятся многие задачи теории графов, построения расписаний, криптографии. Ограничения логического типа необходимо учитывать в процессе принятия решений в планировании, управлении, проектировании и других областях [28, 36, 78, 87, 112]. В связи с этим широко применяются различные обобщения задачи выполнимости, например, задача максимальной выполнимости.
Ввиду сложности рассматриваемых задач дли их исследования и решении требуется применение системного анализа, моделей и методов оптимизации. К основным направлениям исследования задачи выполнимости и ее обобщений относятся изучение сложности, выявление полиномиально разрешимых случаев, разработка и анализ алгоритмов, построение семейств "трудных" задач для конкретных алгоритмов [6, 64, 65, 68, 71, 74, 75, 78, 79, 85, 96, 100, 102, 107, 108, ИЗ].
Среди известных подходов к решению задач с логическими ограничениями можно выделить алгоритмы ветвей и границ, алгоритмы отсечения, а также комбинаций этих методов [G, G6, 69, 70, 78, 82, 103]. В последнее время большое внимание уделяется таким алгоритмам решения задач выполнимости и максимальной выполнимости как поиске запретами [83, 98], имитация отжига [ПО], локальный поиск [77,106,109], генетические алгоритмы [61, 97].
В области принятия решений имеется несколько подходов к анализу несовместных систем ограничении. Можно, например, искать "решение", удовлетворяющее максимальному числу ограничений. Такой подход реализуется, в частности, в задаче максимальной выполнимости. Другим направлением решения задач с противоречивыми условиями является использование комитетных конструкций, обобщающих понятие решения. Дайной проблематике посвящены работы Вл.Д. Мазурова, М.Ю. Хачая и других авторов [13, 39 - 41, 52, 99].
Для исследования и решения задач дискретной оптимизации, в том числе для рассматриваемых нами, широко используются модели и методы целочисленного программирования (ЦП) [1, 3, 11, 38, 41, 49, 53, 54, GO, 78, 99].
Ранее А.А. Колоколовым предложен метод регулярных разбиений, который предназначен для анализа и решения задач ЦП {20]. Значительное число результатов получено с помощью L-разбиения [9,12, 1G-18, 21, 26, 27, 43, 47]. С использованием этого подхода описаны новые классы отсечений, найдены оценки числа итераций для алгоритмов отсечения, алгоритмов ветвей и границ и некоторых других, исследована L-структура ряда задач, предложены алгоритмы перебора ^-классов для задачи целочисленного линейного программирования (ЦЛП), задачи о покрытии множества, простейшей задачи размещения, получены результаты по устойчивости задач и алгоритмов. Построены семейства задач с мощными L-накрытиями, получены первые результаты по разработке алгоритмов перебора L-классов для задач выполнимости и максимальной выполнимости [1, 22, 25, 32, 89].
Несмотря на значительное число работ но задаче выполнимости и ее обобщениям недостаточно исследований проведено с использованием моделей и методов целочисленного программирования, в частности, метода регулярных разбиений. Другим актуальным направлением
является создание параллельных алгоритмов для различных задач оптимизации [15, 4G, 48], в том числе для задач с логическими ограничениями.
Цель диссертации - разработка и анализ алгоритмов решения задачи выполнимости с использованием моделей целочисленного линейного программирования и L-разбиепия, исследование некоторых смежных задач.
В работе предложены алгоритмы перебора L-классов для задачи выполнимости логической формулы и на их основе разработаны параллельные варианты алгоритмов. Указанные алгоритмы применяются для точного решения невзвешенпой задачи максимальной выполнимости [23, 25] и в программном комплексе для эскизного проектирования одежды [29]. Проведено исследование L-структуры задач 2-выполнимости и выполнимости некоторых специальных логических формул.
Для задачи максимальной выполнимости разработаны алгоритмы локального поиска, основанные на модели ЦЛП и алгоритме перебора L-классов для задачи выполнимости. Вычислительный эксперимент показал перспективность применения предложенных алгоритмов для решения задачи выполнимости и некоторых ее обобщений. Для задачи о минимальном комитете построена новая модель ]целочисленного линейного программирования, установлен ряд ее свойств, проведено экспериментальное сравнение двух моделей ЦЛП на основе L-разбиения.
Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения.
В первой главе приводятся постановки задач выполнимости, максимальной выполнимости и соответствующие им модели целочисленного программирования. Указываются два подхода к решению несовместных систем ограничений. Один из них заключается
в отыскании "решения", удовлетворяющего максимальному количеству ограничений. В рамках другого подхода вводится понятие комитетного решения и формулируется задача о минимальном комитете. Рассматриваются некоторые задачи, которые можно связать с выполнимостью логических формул: задача раскраски графа, задача 2-факторизации, задача проектирования изделий сложной структуры. Приводится обзор известных алгоритмов для задач выполнимости и максимальной выполнимости.
Вторая глава посвящена исследованию и решению задачи выполнимости на основе целочисленного программирования и L-разбиения. Сначала дается определение L-разбиения и указываются его свойства, приводятся некоторые известные семейства задач выполнимости, мощности L-пакрытий которых растут экспоненциально с увеличением числа переменных в формуле. Затем исследуется L-структура задачи 2-выполиимости. Показывается, что в случае выполнимой формулы мощность L-накрытия не превосходит п — 1, где п - число переменных в формуле. Изучается также L-структура некоторых специальных логических формул. Из полученных результатов, в частности, следует полиномиальная разрешимость задачи 2-выполнимости и задачи выполнимости хорновских формул. Ранее полиномиальная разрешимость этих задач была установлена другими методами [59, 71J.
Далее описывается предложенный в работе алгоритм перебора L-классов LCE для решения задачи выполнимости и рассматриваются некоторые его модификации. В отличие от метода перебора L-классов для общей задачи ЦЛП поиск представителей L-классов удается осуществлять комбинаторным путем, без решения задач линейного программирования. Последний раздел данной главы посвящен разработке параллельного алгоритма перебора L-классов для задачи
выполнимости.
В третьей главе рассматриваются задача максимальной выполнимости и задача о минимальном комитете. В первом разделе излагаются разработанные нами алгоритмы локального поиска для задачи максимальной выполнимости. Общая идея этих алгоритмов состоит в построении последовательности окрестностей, в которых осуществляется направленный перебор точек. Для каждой из этих точек решается специальная задача выполнимости алгоритмом LCE. Следующие разделы посвящены задаче о минимальном комитете, построению и анализу соответствующих ей моделей целочисленного линейного программирования. Кроме того, проводится экспериментальное сравнение двух моделей ЦЛП на основе і-разбиения.
В четвертой главе обсуждаются результаты экспериментальных исследований для разработанных нами алгоритмов. Расчеты выполнялись на сериях тестовых задач из электронной библиотеки SATLIB [114] и некоторых специальных семействах логических формул.
Первый раздел посвящен применению для решения задачи выполнимости алгоритмов перебора L-классов. Предлагается и анализируется несколько вариантов предварительной сортировки переменных. Проводится сравнение алгоритма LCE с известным точным гибридным алгоритмом, предложенным авторами статьи [63]. Выделены семейства задач из электронной библиотеки, на которых LCE заметно превосходит известный алгоритм. В следующем разделе исследуется зависимость времени работы параллельного алгоритма перебора L-классов от числа процессоров. В целом результаты экспериментов указывают па эффективность применения предложенных алгоритмов для решения задач выполнимости достаточно большой размерности и возможность их использования в прикладных исследованиях.
Последний раздел посвящен решению задачи максимальной
выполнимости алгоритмами локального поиска. Выполнено сравнение двух алгоритмов по времени работы и точности получаемых решений. Для нахождения "хороших" начальных приближений предлагается использовать генетический алгоритм. Проведенные исследования показали целесообразность применения алгоритмов локального поиска для приближенного решения задачи максимальной выполнимости.
Результаты диссертации докладывались на Региональной студенческой конференции "Молодежь III тысячелетия" (Омск, 2002), международных конференциях по исследованию операций OR'2003 (Хайдельберг, Германия, 2003) и OR'2005 (Бремен, Германия, 2005), Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2004), Международной школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 2005), Mini Euro Conference on VNS (Тенерифе, Испания, 2005), XXXVII Региональной молодежной школе-конференции "Проблемы теоретической и прикладной математики" (Екатеринбург, 2006), III Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, 200G), а также на заседаниях научного семинара "Математическое моделирование и дискретная оптимизация" в Омском филиале Института математики им. С.Л. Соболева СО РАН. Основные результаты работы опубликованы в [19, 23-25, 30, 31, 33-35, 55, 56, 90-93].
Автор благодарит научного руководителя д.ф.-м.п., профессора А.А. Колоколова за постоянное внимание к работе, а также выражает признательность к.ф.-м.н. А.В. Адсльшину и А.Н. Тюргомову за полезные советы и плодотворные обсуждения.
