автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Разработка и анализ алгоритмов для задачи выполнимости и ее обобщений на основе L-разбиения

На правах рукописи

ЯГОФАРОВА Дарья Ивановна

РАЗРАБОТКАМ АНАЛИЗ АЛГОРИТМОВ ДЛЯ ЗАДАЧИ ВЫПОЛНИМОСТИ И ЕЕ ОБОБЩЕНИЙ НА ОСНОВЕ ¿-РАЗБИЕНИЯ

13.01 - системный анализ, управление и обработка информации (б научных исследованиях)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук'

Омск - 2006

Работа выполнена в Омском филиале Института математики имени С.Л. Соболева СО РАН

Научный руководитель:

доктор физико-математических иаук, профессор Колоколов Александр Александрович

Официальные оппоненты:

доктор физико-математических наук Попов Леонид Денисович

кандидат физико-математических наук, доцент Симанчев Руслан Юрьевич

Ведущая организация:

Уральский государственный университет им. A.M. Горького

Защита состоится <21» декабря 2006 г. в 16 00 часов на заседании диссертационного совета ДМ 212.179.03 при ГОУ ВПО "Омский государственный университет им. Ф.М. Достоевского" по адресу: 644077, г. Омск, ул. Нефтезаводская, 11.

С диссертацией можно ознакомиться . в библиотеке Омского государственного университета им. Ф.М. Достоевского.

Автореферат разослан е- ноября 2006 г.

Ученый секретарь

диссертационного совета, пу

к.ф.-м.н., доцент А.М.Семенов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Задача выполнимости логической формулы играет важную роль в дискретной оптимизации и теории сложности. Это первая задача, для ' которой была доказана NP-полнота [13], к ней сводятся многие задачи теории графов, построения расписаний, криптографии. Ограничения логического типа необходимо учитывать в процессе принятия решений в планировании, управлении, проектировании и других областях [2,3,8,14,15]. В связи с этим широко применяются различные обобщения задачи выполнимости, например, задача максимальной выполнимости.

Ввиду сложности рассматриваемых задач для их исследования и решения требуется применение системного анализа, моделей и методов оптимизации. К основным направлениям исследования задачи выполнимости и ее обобщений относятся изучение их сложности, выявление полиномиально разрешимых случаев, разработка и анализ алгоритмов, построение семейств "трудных" задач для конкретных алгоритмов [1, 7, 12, 14].

Среди известных подходов к исследованию задач с логическими ограничениями можно выделить применение моделей и методов целочисленного программирования (ЦП) [1, 7].

Для анализа и решения задач ЦП Колоколовым A.A. предложен метод регулярных разбиений [б]. Значительное число результатов получено с помощью Z-разбиения. С использованием этого подхода описаны новые классы отсечений, найдены оценки числа итераций для алгоритмов отсечения, алгоритмов ветвей и границ и некоторых других, исследована ¿-структура ряда задач, предложены алгоритмы перебора ¿-классов для задачи целочисленного линейного программирования (ЦЛП), задачи о покрытии множества, простейшей задачи размещения. Для задачи выполнимости построены семейства задач с ¿-накрытиями большой мощности, предложен вариант алгоритма перебора ¿-классов [7]. Аделыниным A.B. разработан точный алгоритм решения задачи максимальной выполнимости [22].

Несмотря на значительное число работ по задаче выполнимости и ее обобщениям недостаточно исследований проведено с использованием моделей и методов целочисленного программирования, в частности, метода регулярных разбиений. Другим актуальным направлением является создание параллельных алгоритмов для различных задач

оптимизации [5, 10], в том числе для задач с логическими ограничениями.

Цель диссертации - разработка и анализ алгоритмов решения задачи выполнимости с использованием моделей целочисленного линейного программирования и ¿-разбиения, исследование некоторых смежных задач.

Методы исследования. В работе использованы теория и методы целочисленного линейного программировапия, комбинаторной оптимизации, современная методология экспериментальных исследований с применением вычислительной техники и пакетов прикладных программ для решения задач оптимизации.

Научная новизна. В диссертации получил дальнейшее развитие метод регулярных разбиений при исследовании задачи выполнимости. Разработаны новые алгоритмы решения задачи выполнимости, предложены алгоритмы приближенного решения задачи максимальной выполнимости, проведено исследование ¿-структуры задач 2-выполнимости и выполнимости некоторых специальных логических формул.

Основные результаты диссертации заключаются в следующем:

1. Разработаны алгоритмы перебора ¿-классов для задачи выполнимости логической формулы и на их основе предложены параллельные варианты алгоритмов.

2. Получены верхние оценки мощности ¿-накрытий задач 2-выполни-ыости и выполнимости для специального класса логических формул, из которых вытекает полиномиальная разрешимость указанных задач.

3. Построены алгоритмы локального поиска для задачи максимальной выполнимости, основанные на модели целочисленного линейного программирования и алгоритме перебора ¿-классов для задачи выполнимости.

4. Предложена модель целочисленного линейного программирования для задачи о минимальном комитете, предназначенная для ее исследования с использованием ¿-разбиения.

5. Создано программное обеспечение для разработанных алгоритмов, проведены экспериментальные исследования на известных сериях тестовых задач.

Практическая ценность. Разработанные алгоритмы решения задач выполнимости и максимальной выполнимости применимы дяя решения прикладных задач с логическими ограничениями,

возникающих в управлении, проектировании, принятии решений. Некоторые теоретические результаты включены в учебный процесс в Омском государственном университете при подготовке специалистов по прикладной математике.

Апробация работы. Результаты диссертации докладывались на Региональной студенческой конференции "Молодежь III тысячелетия" (Омск, 2002), международных конференциях по исследованию операций OR'2003 (Хайдельберг, Германия, 2003) и OR'2005 (Бремен, Германия, 2005), Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2004), Международной школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 2005), Mini Euro Conference on VNS (Тенерифе, Испания, 2005), XXXVII Региональной молодежной школе-конференции "Проблемы теоретической и прикладной математики" (Екатеринбург, 2006), III Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, 2006), а также на заседаниях научного семинара "Математическое моделирование и дискретная оптимизация" в Омском филиале Института математики им. C.JI. Соболева СО РАН.

Публикации. Основные результаты диссертации опубликованы в 15 научных работах, список которых приведен в конце автореферата.

Структура и объем работы. Диссертация изложена на 112 страницах и состоит из введения, четырех глав, заключения, списка литературы (115 наименований) и приложения,

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы диссертации, указываются направления теоретических и экспериментальных исследований задачи выполнимости и ее обобщений, излагается краткое содержание работы.

В первой главе содержатся постановки задач и обзор известных результатов, имеющих отношение к рассматриваемой проблематике.

В п. 1.1 приводятся постановки задач выполнимости, максимальной выполнимости и соответствующие им модели целочисленного программирования. Указываются два подхода к решению несовместных систем ограничений. В рамках одного из них дается понятие комитетного решения и рассматривается задача о минимальном комитете.

Пусть даны логические переменные хь... ,х„, которые могут принимать два значения: истина или ложь. Литералом называется

либо переменная Xj (позитивный литерал), либо ее отрицание Xj (негативный литерал). Рассмотрим логическую формулу F в конъюнктивной нормальной форме (КНФ)

F = С\ Л С2 Л... Л Ст,

где каждая формула (скобка) Q является дизъюнкцией литералов. Формула называется выполнимой, если существует набор значений переменных, при котором она принимает значение истина; такой набор называется выполняющим, В противном случае формула называется невыполнимой.

Задан а в ыполнимости (задача SAT) заключается в том, чтобы определить, выполнима ли данная формула F. Одним из вариантов этой задачи является задача к-выполнимости (к-SAT), где каждая скобка Ci содержит не более к литералов. Известно, что задача ¿-SAT является NP-псшной при А: > 3 [13].

Одним из актуальных направлений является выделение и исследование подклассов формул, для которых задача SAT решается за полиномиальное время (от длины входа). К наиболее известным нолииомиалыю разрешимым случаям относятся задача 2-SAT и задача выполнимости хорновских формул. Отметим, что формула в КНФ называется ¡сормовской, если каждая скобка в ней содержит не более одного позитивного литерала.

Рассмотрим модель ЦЛП для задачи выполнимости. С этой целью введем булевы переменные у\,...,уп такие, что yj соответствует переменной а (1 — yj) — ее отрицанию. Условие выполнимости формулы F эквивалентно существованию решения системы:

Z Vj~ £ ад>1-|СГ1. i=h-..,m, (1)

i*=C,+ 7'eCf

0<tfj£I, j = l,...,n, (2)

yj&Z, j = (3)

где Су и Ct — множества индексов переменных, входящих в скобку Ci с отрицанием и без пего соответственно.

Чтобы получить модель ЦЛП, падо добавить к (1)-(3) целевую функцию, например, f(y) = jfj —> шах или /(у) = £ yj —> max, где

в

Во многих случаях формула может оказаться невыполнимой. Тогда соответствующую модель ЦЛП можно рассматривать как несобственную задачу математического программирования [4],

В области принятия решений имеется несколько подходов к анализу несовместных систем ограничений. Один из них заключается в отыскании "решения", удовлетворяющего максимальному количеству ограничений. В случае логической формулы с этой точки зрения в литературе рассматривается иевзвешенная задача максимальной выполнимости. Если ограничения в системе имеют разную степень важности, то традиционно каждому из них приписывается вес и ищется "решение", для которого суммарный вес выполненных ограничений максимален.

Пусть скобки Ci,...,C„i имеют неотрицательные веса Ci,...,с™. Задача максимальной выполнимости (задача MAX-SAT) состоит в отыскании набора значений переменных, при котором суммарный вес выполненных скобок будет наибольшим. Известно, что эта задача является NP-трудноЙ, даже если каждая скобка в формуле содержит не более двух литералов.

Рассмотрим модель ЦЛП для задачи MAX-SAT:

т

Л*) = £ CiZi -» max, i-i

при условиях

И Уз ~ Y, Vj + Zi< ICfl, t = 1,..., m, (5)

0 < < 1, Vj £Z, j = l,(6) 0<£i<l, Zi&zy i = l,...,m. (7)

Если в допустимом решении задачи (4)-(7) для некоторого г имеет место Zi = 1, то формула С, принимает значение истина. Оптимальное значение целевой функции равно максимальному суммарному весу выполненных скобок.

Другим направлением решения задач с противоречивыми условиями является использование комитетных конструкций. Метод комитетов применяется для исследования задач принятия решений, диагностики, классификации. Исследованиям в атом направлении посвящепы работы Вл.Д. Мазурова, М.Ю. Хачая и других авторов [9, И, 16].

(4)

Пусть X - произвольное множество, и задана система непустых подм ножеств

А С X, г = 1,... ,т, (8)

для которой допускается случай П Д=0- -

1—1

Комитетным решением (комитетом) системы (8) называется конечная последовательность О = (ж1, х2,... ,хк) элементов множества X такая, что в каждом множестве А лежит более полов ни ы членов О, т.е. выполнены неравенства

к

|{г.хЧД}|>-, ¿ = 1.....т.

Задача о минималъном комитете: найти комитет системы (8) с наименьшим возможным числом элементов (или показать, что система не имеет комитетных решений).

В случае конечных множеств данная задача является НР-трудноЙ (16).

В н. 1.2 рассматриваются приложения задачи выполнимости и приводятся некоторые постановки задач, имеющих связь с выполнением логических условий. К таким задачам относятся, например, задача раскраски графа, задача факторизации, задачи проектирования различных изделий.

В п. 1.3 содержится обзор известных алгоритмов для задач выполнимости и максимальной выполнимости.

Вторая глава посвящена исследованию и решению задачи выполнимости на основе целочисленного программирования и ¿-разбиения.

В п. 2.1 приводятся необходимые определения и обозначения. Точки х, у 6 Я" (х >- у) называются [¿-эквивалентными, если не существует отделяющей их точки г £ ¿Г", т.е. такой, что выполняется х ^ г ^ у. Здесь >-, Ь - знаки лексикографического сравнения. Такое отношение порождает разбиение любого множества X на непересекающиеся классы эквивалентности, которые называются Ь-классами. Соответствующее фактор-множество называется Ь-разбиением множества X. Каждая точка ге2" образует отдельный ^класс, остальные классы состоят из не цело численных точек и называются дробными. Указанное разбиение обладает рядом полезных свойств [6], применяемых при разработке и исследовании алгоритмов целочисленного программирования, в частности, алгоритмов перебора ¿-классов.

Рассмотрим лексикографическую задачу ЦЛП следующего вида:

найти у* = lexmaw{M П Z"), (9)

где М -■ некоторый выпуклый * многогранник. Важную роль в исследовании задачи (9) и методов ее решения играет множество

Mf = {у € М : yi-г V л S (М П Z")},

которое называется верхним дробным накрытием задачи (9). Фактормножество Mf/L называется верхним L-накритием.

Для задачи

найти у* = lexmin(M П Z11) (10)

рассматривается нижнее дробное накрытие

М* = {уеМ: У •< г VZ 6 (М n Z")}

и нижнее L-накрытие. M^/L. Если М П Zn — 0, то Mf = М* = М.

Выделение этих частей релаксационного множества задачи связано с тем, что в некоторых методах ЦП (алгоритмах отсечения, перебора ¿-классов) происходит последовательное исключение точек из М^ или из М», т.е. эти методы можно рассматривать как определенные способы "сиятия" дробных накрытий.

Раздел 2.2 посвящен анализу ¿-структуры многогранников задач 2-выполнимости и выполнимости для одного специального класса логических формул.

Через М обозначим многогранник, определяемый системой ограничений (1), (2). Рассмотрим задачу SAT как задачу поиска лексикографически максимального элемента множества М П 2я.

Ранее были построены семейства задач 2-SAT и 3-SAT, у которых мощности верхних ¿-накрытий задачи (9) растут экспоненциально с увеличением числа переменных в формуле [7). Для задачи 3-SAT эти семейства содержат как выполнимые, так и невыполнимые формулы. Примеры задач 2-SAT с мощными ¿-накрытиями были найдены только для невыполнимых формул. Нами доказана следующая

Теорема 2.1 Пусть М - многогранник задачи 2-SAT, содержащий целочисленную точку. Тогда \M?/L\ < п — 1, где п - количество переменных в формуле.

Построен пример формулы, для которой данная оценка достигается.

Далее нам потребуется лексикографическое сравнение множеств из Rn: X >- У, если х ¡- у для всех х е X и у G У. Подмножество Q

дробных ¿-классов из Х/Ь называется ¿•комплексом, если для любых V, V' из <2 не существует отделяющей их точки г е Хпг". Через Ф(Л') обозначим мощность максимального ¿-комплекса.

Рассмотрим задачу выполнимости для одного специального класса логических формул. Обращая в хорновской формуле Р все литералы, получим формулу Р', изоморфную Р, каждая скобка которой содержит не более одного негативного литерала. Через М' обозначим многогранпик такой формулы.

Теорема 2.2 Для многогранника М' справедлива оценка Ф(М') < п.

Из приведенных теорем, в частности,. следует полиномиальная разрешимость задачи 2- выполни мости и задачи выполнимости хорновских формул.

В п. 2.3 описывается предложенный нами алгоритм перебора ¿-классов ЬСЕ для решения задачи выполнимости и рассматриваются некоторые его модификации.

За конечное число шагов алгоритм ЬСЕ либо находит лексикографически максимальное решение задачи (9) в случае выполнимой формулы, либо указывает на ее невыполнимость.

У

Ряс. 1: Лепта ¿-классов

Основной шаг метода перебора ¿-классов для задачи (9) заключается в переходе от одного класса из М?/Ь к другому в порядке лексикографического убывания, начиная с лексикографически максимального ¿-класса. Этот процесс удобно интерпретировать с помощью лепты, в которой каждая ячейка обозначает отдельный ¿-класс. Классы, соответствующие целочисленным точкам, показаны штриховкой (рис. 1). Алгоритм ЬСЕ порождает последовательность точек £ А/®, которые принадлежат различным ¿-классам. В отличие от метода перебора ¿-классов для общей задачи ЦЛП поиск представителей указанных классов удается осуществлять комбинаторно без решения задач линейного программирования. Это возможно благодаря следующему свойству: в каждом ¿-классе многогранника М содержится

полуцелочислениая точка, т.е. точка со значениями координат из множества {0,^,1}. Показано, что трудоемкость алгоритма перебора ¿-классов LCE не превышает 0(п?т - \M?/L\),

Для задачи 2-SAT предлагается следующая модификация алгоритма LCE: завершение работы осуществляется в результате нахождения решения или после просмотра (п ~ 1)-го ¿-класса (обозначим такой алгоритм LCEis)- Из теоремы 2.1 вытекает, что алгоритм LCE2з является полиномиальным.

В случае хорновских формул целесообразно использовать следующий двухэтапный алгоритм LCE//: сначала, обращая в хорновской формуле все литералы, строим изоморфную формулу, затем применяем к ней алгоритм LCE. Из теоремы 2.2 следует, что алгоритм LCE^ полиномиален для задачи выполнимости хорновских формул.

Нами разработан также алгоритм перебора ¿-классов для задачи (10), который ищет лексикографически минимальный набор, выполняющий формулу (алгоритм LCE-1).

П. 2.4 посвящен разработке параллельного алгоритма перебора ¿-классов PLCE, который заключается в следующем. Сначала выполняется определенное число итераций алгоритма LCE. Затем порождается несколько процессов, каждый из которых начинает просматривать ленту ¿-классов с различных ячеек при помощи LCE. Если некоторый процесс обработал "свою" часть ленты, то он переходит к другой ее части. Работа алгоритма завершается в результате нахождения некоторого решения или после просмотра всей ленты (в этом случае логическая формула невыполнима). Отметим, что для выполнимой формулы параллельный алгоритм может получить решение раньше, чем LCE, за счет нахождения другого решения, не являющегося лексикографически максимальным. В работе алгоритм PLCE реализован для любого количества процессов и ориентирован на использование многопроцессорных вычислительных устройств с общей памятью.

Предложенные алгоритмы перебора ¿-классов могут ' быть использованы при решении некоторых более общих задач. Например, алгоритм LCE применяется в точных алгоритмах для невзвешенной задачи MAX-SAT [22], а также в программном комплексе для эскизного проектирования одежды ¡8].

Результаты второй главы опубликованы в [19,20,22-24,27-29,32,33].

В третьей главе рассматриваются задача максимальной выполнимости и задача о минимальном комитете.

В п. 3.1 описываются разработанные нами алгоритмы локального поиска для задачи максимальной выполнимости.

Для приближенного решения задачи MAX-SAT имеется значительное число алгоритмов локального поиска. Особенностью этих алгоритмов является то, что поиск локального оптимума осуществляется в пространстве логических переменных xi,..., хп. Они отличаются друг от друга видом окрестностей и некоторыми процедурами. В работе [31] нами предложено перейти к использованию пространства вспомогательных переменных z\,.,,, zm из модели ЦЛП (4)-(7), соответствующих скобкам формулы. В этом случае поиск локального оптимума задачи MAXSAT сводится к решению конечной последовательности задач SAT, для каждой из которых применяется LCE.

Определим окрестность Qp(z) текущей точки z радиуса р\

2) z € Qp(z)t если расстояние Хэмминга d(z,z) < р и выполнено неравенство f(z) > /(г).

В алгоритмах используется подмножество Q(z) С QP(S), удовлетворяющее некоторым условиям (в зависимости от конкретного алгоритма).

Общая идея алгоритмов состоит в построении последовательности окрестностей, в которых осуществляется направленный перебор точек. Для каждой из этих точек решается специальная задача выполнимости алгоритмом LCE.

Нами исследовались два алгоритма, отличающиеся друг от друга видом окрестностей Q(z). В алгоритме LSI множество Q{z) включает лишь одну точку z,z ф z, для которой формула выполнима. В алгоритме LS2 указанное множество совпадает с Qp{z).

П. 3.2 посвящен задаче О минимальном комитете, построению и анализу соответствующих ей моделей ЦЛП.

В (11, 16] и других работах для исследования задачи о минимальном комитете используются модели целочисленного программирования. С целью применения Z^разбиения на основе модели из [11], которая не является линейной, нами построена следующая модель ЦЛП:

1) 5 е QP{z);

¿aytj >&, i = l,...,m; j-i

П

s min

(и) (12)

z h < 2s - 1,

(13)

(14)

(15)

« > 1, tj > 0, j = 1,...

€ Z, j = 1,... ,тг,

где A = (ay) - булева (тп x п)-матрица инциденций множеств Dj и максимально совместных подсистем системы (8).

Установлена следующая взаимосвязь данной модели с задачей о минимальном комитете.

Теорема 3.4 Комитет системы (S) существует тогда и только тогда, когда задача ЦЛП (11)-(15) имеет допустимое решение.

Теорема 3.5 Между множествам минимальных комитетов системы (8) и оптимальными решениями задачи (11)-(15) существует взаимно однозначное соответствие.

Следует отметить, что при фиксированном $ система неравенств (12) представляет собой обобщение системы линейных ограничений задачи о покрытии множества с целочисленными переменными.

В п. 3.3 проводится экспериментальное сравнение ¿-структуры модели (11)-(15) и известной ранее модели ЦЛП [16). Оказалось, что предложенная нами модель более удобна для применения метода перебора Is-классов.

Результаты третьей главы опубликованы в [21, 24-27, 30, 31].

В четвертой главе обсуждаются результаты экспериментальных исследований для разработанных нами алгоритмов. Расчеты выполнялись на сериях тестовых задач из электронной библиотеки SATLIB [17] и некоторых специальных семействах логических формул,

В п, 4.1 приводятся результаты решения задачи выполнимости алгоритмами перебора L-классов LCE и LCE-1, Предлагается и анализируется несколько вариантов предварительной сортировки переменных.

Проведено экспериментальное сравнение алгоритма LCE с известным точным гибридным алгоритмом, предложенным авторами работы [12] (обозначим его BF). Серии тестовых примеров брались из библиотеки SATLIB. Алгоритм перебора ¿-классов LCE оказался заметно лучше алгоритма BF на всех сериях класса "Flat" Graph Colouring, несмотря на достаточно большую размерность логических формул. Задачи данного класса были построены путем сведения к задаче SAT задачи о вершинной раскраске графа. На других задачах рассмотренные

алгоритмы дополняли друг друга по времени решения. В каждой серии как правило встречались примеры с ¿-накрытиями большой мощности, на которых алгоритм LCE уступал алгоритму BF. Отметим, что с такими ¿/-накрытиями можно бороться, используя разные упорядочения переменных.

Эксперимент показал, что предложенные нами алгоритмы перебора ¿-классов позволяют решать задачи выполнимости достаточно большой размерности и могут быть использованы в прикладных исследованиях.

В п. 4.2 описываются результаты вычислительного эксперимента для параллельного алгоритма перебора ¿-классов. Расчеты проводились на четырехпроцессорном компьютере Xeon (2 GHz). Исследовалась зависимость времени работы алгоритма PLCE от числа процессоров. Для выполнимых формул во многих случаях время решения на четырех процессорах оказалось в десятки раз меньше, чем на одном процессоре. В экспериментальных исследованиях использовался также пакет ILOG CPLEX 10.0 для решения задач целочисленного программирования. По времени решения он значительно уступал PLCE на всех рассмотренных задачах.

В целом проведенный вычислительный эксперимент подтверждает эффективность параллельного алгоритма.

В п. 4.3 содержатся результаты вычислительных экспериментов для алгоритмов локального поиска, предложенных в п 3.1.

Эксперимент проводился на невыполнимых формулах из библиотеки SATLIB, которые рассматривались как невзвешенные задачи максимальной выполнимости, и на тестовых примерах, взятых из (18]. Целью вычислительного эксперимента было сравнение алгоритмов LSI и LS2 по времени и точности получаемых решений, а также исследование их поведения в зависимости от радиуса окрестности. Начальные точки генерировались случайным образом или находились с помощью генетического алгоритма. Окрестности QP(z) рассматривались для Р< 2.

Проведенные исследования показали эффективность предложенных алгоритмов и целесообразность их применения для приближенного решения задачи максимальной выполнимости.

Содержание данной главы отражено в работах [22, 24, 27, 29].

В заключении приводятся основные результаты диссертации, а в приложении — некоторые таблицы с информацией о вычислительном эксперименте.

Список литературы

[1] Адельшин A.B. Исследование задач максимальной и минимальной выполнимости с использованием ¿-разбиения // Автоматика н телемеханика. - 2004. - № 3. - С. 35 - 42.

[2] Беспалов Д-В., Семенов A.A. О логических выражениях для задачи 2-ФАКТОРИЗАЦИЯ // Вычислительные технологии. - 2002. - Т. 7, Ч. 2.-С. 18-25.

[3] Дулькейт В.И., Файзуллин Р.Т. Алгоритм построения эквивалентных КНФ для задачи факторизации // Материалы III Всероссийской конференции "Проблемы оптимизации н экономические приложения". - Омск, 2006. - С. 90.

[4] Еремин И.И., Мазуров Вл.Д., Астафьев H.H. Несобственные задачи линейного и выпуклого программирования, - М: Наука, 1983. - 336 с.

[5} Еремин И.И., Попов Л.Д. ' Параллельные фейеровские методы для сильно структурированных систем линейных неравенств и уравнений // Алгоритмы и программные средства параллельных вычислений. - Екатеринбург: ИММ УрО РАН, 2002. - Вып. 6. -С. 61 - 65. !

[6] Колоколов A.A. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журнал исследования операций. - 1994. -№2.-G. 1S- 39.

[7] Колоколов АА., Адельшин A.B., Чередова Ю.Н. Применение ¿-разбиения к исследованию некоторых задач выполнимости // Байкальской международной школы-семинара "Методы оптимизации и их приложения". - Иркутск, 2001. - Т. 1. - С. 166 - 172.

[8] Колоколов A.A., Нагорная 3-Е., Гуселетова О.Н., Ярош A.B. Задачи дискретной оптимизации и программный комплекс для эскизного проектирования одежды // Труды XIII Байкальской международной школы-семинара "Методы оптимизации и их приложения". - Иркутск, 2005. - Т. 1. - С. 509 - 514.

[9] Мазуров Вл.Д. Метод комитетов в задачах оптимизации и классификации. - М.: Наука, 1990. - 248 с.

10] Сергиенко И.В., Шило В.П., Рощи» В.А. Распараллеливание процесса оптимизации для задач дискретного программирования // Кибернетика и системный анализ. - 2004. - № 2. - С. 45 - 52.

11] Хачай М.Ю. К задаче о минимальном комитете // Тезисы докладов Всероссийской конференции "Алгоритмический анализ неустойчивых задач". - Екатеринбург, 2004. - С. 309.

12] Borchers В., Fur man J. A Two-phase exact algorithm for MAXSAT and weighted MAX-SAT problems // Journal of Combinatorial Optimization. - 1998. - V. 2, № 4. - P. 299 - 306.

13] Cook S.A. The complexity of theorem-proving procedure // Proc. 3rd Annual ACM Symposium on the Theory of Computing. - 1971. -P. 151 - 159.

14] Gu J., Purdom P., Franco J., Wah B. Algorithms for the Satisfiability (SAT) Problem: A Survey // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. - 1996. - V. 35. - P. 19 - 130.

15] Kautz H., Selman B. Planning as Satisfiability // Proc. 10th European Conference on Artificial Intelligence (ECAI 92). - 1992. - P. 359 - 363.

16] Mazurov VI.D., Khachai M.Yu., Rybin A.I, Committee Constructions for Solving Problems of Selection, Diagnostics, and Prediction // Proceedings of the Steklov Institute of mathematics. - 2002. - Suppl. 1. -P. 67-101.

17] timnu. cs. ubc. ca/^hoos/SA TLIB/benchm. html

18] www.nmt. edu/^borchers/maxsat.html

Работы автора по теме диссертации

[19] Калльрат Ю.Н., Колоколов А.А., Ягофарова Д.И. Алгоритм перебора ¿-классов для задачи выполнимости // Материалы Всероссийской конференции "Проблемы оптимизации и экономические приложения". - Омск, 2003. - С. 94.

[20] Колоколов А.А., Адельшип А.В., Ягофарова Д.И. Алгоритмы лексикографического перебора для решения задачи выполнимости и некоторых ее обобщений / / Труды XIII Байкальской

между народной школы-семинара "Методы оптимизации и их приложения". - Иркутск, 2005. - Т. 1. - С. 503 - 508.

[21] Колоколов A.A., Адельшин A.B., Ягофарова Д.И. Алгоритмы точного и приближенного решения задачи максимальной выполнимости // Материалы III Всероссийской конференции "Проблемы оптимизации и экономические приложения". - Омск, 2006. - С. 42 - 46.

[22] Колоколов A.A., Адельшин A.B., Ягофарова Д.И. Решение задач выполнимости и некоторых ее обобщений с использованием метода перебора L-классов // Прикладная математика и информационные технологии: Сб. науч. и метод, трудов. - Омск: Изд-во ОмГТУ, 2005.

- С. 68 - 79.

[23] Колоколов A.A., Тюрюмов А.Н., Ягофарова Д.И. Параллельный алгоритм перебора ¿-классов для задачи выполнимости // Материалы III Всероссийской конференции "Проблемы оптимизации и экономические приложения". - Омск, 2006. - С. 102.

[24] Колоколов A.A., Тюрюмов А.Н., Ягофарова Д.И. Разработка и экспериментальное исследование алгоритмов решения задач выполнимости и максимальной выполнимости. Препринт. - Омск: Ом ГУ, 2006. - 19 с.

[25] Колоколов A.A., Ягофарова Д.И. Об одной модели целочисленного программирования для задачи о минимальном комитете // Материалы российской конференции "Дискретный анализ и исследование операций". - Новосибирск, 2004. - С. 163.

[26] Колоколов A.A., Ягофарова Д.И., Адельшин A.B., Тюрюмов А.Н. О некоторых алгоритмах локального поиска для решения задачи максимальной выполнимости // Труды 37-й Региональной молодежной конференции "Проблемы теоретической и прикладной математики". - Екатеринбург: УрО РАН, 2006. - С. 382 - 385.

[27] Колоколов A.A., Ягофарова 'Д.И., Тюрюмов А.Н. Разработка алгоритмов для задачи выполнимости и некоторых ее обобщений с использованием перебора ¿-классов // Омский научный вестник.

- 2006. - № 5 (39) - С. 57 - 61.

[28] Ягофарова Д.И. Анализ L-структуры задачи 2-выполнимости // Материалы ежегодного научного семинара "Под знаком - Омск: ООО "Издатель-Полиграфист", 2003. - С. 71 - 77.

[29] Ягофарова Д.И. Об алгоритмах перебора ¿-классов для решения задачи выполнимости // Актуальные проблемы экономических, социально-гуманитарных и естественных наук. Технологии профессионального образования: материалы межвузовской научно-методической конференции. - Омск: НОУ "Евразийский институт экономики, менеджмента, информатики", 2006. - С. 47 - 51.

[30} Kolokolov A., Adelsbin A,, Yagofarova D. Development of Local Search Algorithms for MAX-SAT Problem Using ¿-class Enumeration // Abstracts of Annual International Conference on Operations Research 2006. - Karlsruhe, 2006. - P. 78,

[31] Kolokolov A., Adelshin A., Yagofarova D. Local search algorithms for the MAX SAT problem based on ¿-class enumeration // Extended Abstracts of 18th Mini Euro Conference on VNS. - Tenerife, 2005, -P. 117 - 118.

[32] Kolokolov A., Kallrath J.,Yagofarova D. Analysis and Solving the Satisfiability Problem Using ¿-partition // Abstracts of Annual International Conference on Operations Research 2003. - Heidelberg, 2003. - P. 128.

[33] Kolokolov A., Yagofarova D., Tynryumov A. Development of ¿-class Enumeration Algorithms for Satisfiability Problem // Abstracts of Annual International Conference on Operations Research 2005. -Bremen, 2005. - P. 107 - 108.

Отпечатано с оригинал-макета, предоставленного автором

Подписано в печать 16.11.2006. Усл. печ. л. 1,25. Уч.-изд. л.

Формат 60x84/16. Бумага офсетная. 1,3. Тираж 120 экз. Заказ № 180.

Отпечатано в "Полиграфическом центре КАН" 644050, г. Омск, пр. Мира 11а, тел.: (3812) 65-47-31 Лицензия ПЛД № 58-47 от 21.04.1997.

Введение

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

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

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

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

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

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

2.2 Анализ L-структуры многогранника задачи выполнимости.

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

2.4 Параллельные алгоритмы.

3 Применение метода перебора L-классов к решению некоторых задач дискретной оптимизации

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

3.2 Модели целочисленного линейного программирования для задачи о минимальном комитете.

3.3 Экспериментальное сравнение L-структуры моделей . 7G

4 Экспериментальные исследования

4.1 Вычислительный эксперимент для алгоритмов перебора

L-классов.

4.2 Результаты эксперимента для параллельного алгоритма

4.3 Сравнение эвристических алгоритмов.

Задача выполнимости логической формулы играет важную роль в дискретной оптимизации и теории сложности [7, 42]. Она является первой задачей, для которой доказана NP-полнота [G7], к пей сводятся многие задачи теории графов, построения расписаний, криптографии. Ограничения логического типа необходимо учитывать в процессе принятия решений в планировании, управлении, проектировании и других областях [28, 36, 78, 87, 112]. В связи с этим широко применяются различные обобщения задачи выполнимости, например, задача максимальной выполнимости.

Ввиду сложности рассматриваемых задач для их исследования и решения требуется применение системного анализа, моделей и методов оптимизации. К основным направлениям исследования задачи выполнимости и ее обобщений относятся изучение сложности, выявление полиномиально разрешимых случаев, разработка и анализ алгоритмов, построение семейств "трудных" задач для конкретных алгоритмов [6, 64, 65, 68, 71, 74, 75, 78, 79, 85, 96, 100, 102, 107, 108, ИЗ].

Среди известных подходов к решению задач с логическими ограничениями можно выделить алгоритмы ветвей и границ, алгоритмы отсечения, а также комбинаций этих методов [6, 66, 69, 70, 78, 82, 103]. В последнее время большое внимание уделяется таким алгоритмам решения задач выполнимости и максимальной выполнимости как поиск с запретами [83, 98], имитация отжига [110], локальный поиск [77,106,109], генетические алгоритмы [61, 97].

В области принятия решений имеется несколько подходов к анализу несовместных систем ограничений. Можно, например, искать "решение", удовлетворяющее максимальному числу ограничений. Такой подход реализуется, в частности, в задаче максимальной выполнимости. Другим направлением решения задач с противоречивыми условиями является использование комитетных конструкций, обобщающих понятие решения. Данной проблематике посвящены работы Вл.Д. Мазурова, М.Ю. Хачая и других авторов [13, 39 - 41, 52, 99].

Для исследования и решения задач дискретной оптимизации, в том числе для рассматриваемых нами, широко используются модели и методы целочисленного программирования (ЦП) [1, 3, И, 38, 41, 49, 53, 54, 60, 78, 99].

Ранее А.А. Колоколовым предложен метод регулярных разбиений, который предназначен для анализа и решения задач ЦП [20]. Значительное число результатов получено с помощью L-разбиения [9,12, 1С -18, 21, 26, 27, 43, 47]. С использованием этого подхода описаны новые классы отсечений, найдены оценки числа итераций для алгоритмов отсечения, алгоритмов ветвей и границ и некоторых других, исследована L-структура ряда задач, предложены алгоритмы перебора L-классов для задачи целочисленного линейного программирования (ЦЛП), задачи о покрытии множества, простейшей задачи размещения, получены результаты по устойчивости задач и алгоритмов. Построены семейства задач с мощными 1/-иакрытиями, получены первые результаты по разработке алгоритмов перебора L-классов для задач выполнимости и максимальной выполнимости [1, 22, 25, 32, 89].

Несмотря на значительное число работ по задаче выполнимости и ее обобщениям недостаточно исследований проведено с использованием моделей и методов целочисленного программирования, в частности, метода регулярных разбиений. Другим актуальным направлением является создание параллельных алгоритмов для различных задач оптимизации [15, 4G, 48], в том числе для задач с логическими ограничениями.

Цель диссертации - разработка и анализ алгоритмов решения задачи выполнимости с использованием моделей целочисленного линейного программирования и L-разбиепия, исследование некоторых смежных задач.

В работе предложены алгоритмы перебора L-классов для задачи выполнимости логической формулы и на их основе разработаны параллельные варианты алгоритмов. Указанные алгоритмы применяются для точного решения невзвешенной задачи максимальной выполнимости [23, 25] и в программном комплексе для эскизного проектирования одежды [29]. Проведено исследование L-структуры задач 2-выполнимости и выполнимости некоторых специальных логических формул.

Для задачи максимальной выполнимости разработаны алгоритмы локального поиска, основанные на модели ЦЛП и алгоритме перебора L-классов для задачи выполнимости. Вычислительный эксперимент показал перспективность применения предложенных алгоритмов для решения задачи выполнимости и некоторых ее обобщений. Для задачи о минимальном комитете построена новая модель целочисленного линейного программирования, установлен ряд ее свойств, проведено экспериментальное сравнение двух моделей ЦЛП на основе L-разбиения.

Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения.

Основные результаты диссертации заключаются в следующем:

1. Разработаны алгоритмы перебора L-классов для задачи выполнимости логической формулы и на их основе предложены параллельные варианты алгоритмов.

2. Получены верхние оценки мощности L-накрытий задач 2-выполнимости и выполнимости для специального класса логических формул, из которых вытекает полиномиальная разрешимость указанных задач.

3. Построены алгоритмы локального поиска для задачи максимальной выполнимости, основанные на модели целочисленного линейного программирования и алгоритме перебора L-классов для решения задачи выполнимости.

4. Предложена модель целочисленного линейного программирования для задачи о минимальном комитете, предназначенная для ее анализа с использованием L-разбиения, проведено ее экспериментальное исследование.

5. Создано программное обеспечение для разработанных алгоритмов, проведены экспериментальные исследования на известных сериях тестовых задач.

Разработанные алгоритмы решения задач выполнимости и максимальной выполнимости применимы для решения прикладных задач с логическими ограничениями. Полученные теоретические результаты могут быть использованы в учебном процессе при подготовке специалистов по прикладной математике.

Заключение

В работе проведено исследование задач выполнимости и максимальной выполнимости логической формулы, а также задачи о минимальном комитете на основе моделей целочисленного линейного программирования и L-разбиения, предложены алгоритмы их решения. Указанные задачи имеют большое число приложений в управлении, проектировании и принятии решений.

1. Адельшин А.В. Исследование задач максимальной и минимальной выполнимости с использованием L-разбиения // Автоматика и телемеханика. - 2004. - № 3. - С. 35 - 42.

2. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ «Регулярная и хаотичная динамика», 2001. - 288 с.

3. Береснев B.JL, Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск, 1978. - 333 с.

4. Беспалов Д.В., Семенов А.А. О логических выражениях для задачи 2-ФАКТОРИЗАЦИЯ // Вычислительные технологии. 2002. -Т. 7, Ч. 2. - С. 18 - 25.

5. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. - 296 с.

6. Всемирнов М.А., Гирш Э.А., Данцин Е.Я., Иванов С.В. Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности // Зап. науч. семин. ПОМН. 2001. - Т. 277. - С. 14 - 46.

7. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. - 416 с.

8. Данцин Е.Я. Две системы доказательства тавтологииности, основанные на методе расщеплений. Зап. науч. семин. ЛОМИ. - 1981. - Т. 105.- С. 24 - 44.

9. Девятерикова М.В., Колоколов А.А. Анализ устойчивости по целевой функции некоторых алгоритмов дискретной оптимизации // Труды XIII Байкальской международной школы-семинара "Методы оптимизации и их приложения". Иркутск, 2005. - Т. 1. -С. 449 - 454.

10. Дулькейт В.И., Файзуллин Р.Т. Алгоритм построения эквивалентных КНФ для задачи факторизации // Материалы III Всероссийской конференции "Проблемы оптимизации и экономические приложения". Омск, 2006. - С. 90.

11. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, 1981. - 344 с.

12. Еремеев А.В., Заозерская Л.А., Колоколов А.А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискретный анализ и исследование операций. -2000. Сер. 2, Т. 7. - С. 22 - 46.

13. Еремин И.И., Мазуров Вл.Д. Нестационарные процессы математического программирования. М.: Наука, 1979. - 288 с.

14. Еремин И.И., Мазуров Вл.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. М: Наука, 1983. -336 с.

15. Еремин И.И., Попов Л.Д. Параллельные фейеровские методы для сильно структурированных систем линейных неравенств и уравнений // Алгоритмы и программные средства параллельныхвычислений. Екатеринбург: ИММ УрО РАН, 2002. - Вып. 6. -С. 61 - 65.

16. Заблоцкая О.А. Нижняя оценка числа итераций для одного алгоритма лексикографической оптимизации // Дискретная оптимизация и численные методы решения прикладных задач. -Новосибирск: ВЦ СО АН СССР, 1986. С. 21 - 27.

17. Забудский Г.Г. Некоторые свойства многогранника задачи о р-медиапе // Вестник Омского университета. Омск: ОмГУ, 1997. - № 4. - С. 11-13.

18. Заозерская J1.A. Об одном алгоритме перебора L-классов для решения задачи о покрытии множества // Труды XI Байкальской международной школы-семинара "Методы оптимизации и их приложения". Иркутск, 1998. - Т. 1. - С. 139 - 142.

19. Калльрат Ю.Н., Колоколов А.А., Ягофарова Д.И. Алгоритм перебора L-классов для задачи выполнимости // Материалы Всероссийской конференции "Проблемы оптимизации и экономические приложеиия". Омск, 2003. - С. 94.

20. Колоколов А.А. Регулярные разбиения в целочисленном программировании // Методы решения и анализа задач дискретной оптимизации. Омск: ОмГУ, 1992. - С. 67 - 93.

21. Колоколов А.А. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журнал исследования операций. 1994. - № 2. - С. 18 - 39.

22. Колоколов А.А., Адельшин А.В., Чередова Ю.Н. Применение L-разбиения к исследованию некоторых задач выполнимости // Труды XII Байкальской международной школы-семинара "Методыоптимизации и их приложения". Иркутск, 2001. - Т. 1. -С. 166 - 172.

23. Колоколов А.А., Адельшин А.В., Ягофарова Д.И. Алгоритмы точного и приближенного решения задачи максимальной выполнимости // Материалы III Всероссийской конференции "Проблемы оптимизации и экономические приложения". Омск, 2006. - С. 42 - 46.

24. Колоколов А.А., Заозерская JI.A. Регулярные разбиения и лексикография: Учебно-методическое пособие. Омск: ОмГУ, 1999. -31 с.

25. Колоколов А.А., Леванова Т.В. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения // Вестник Омского университета. Омск: ОмГУ, 1996. - № 1. -С. 21-23.

26. Колоколов А.А., Тюрюмов А.Н., Ягофарова Д.И. Параллельный алгоритм перебора L-классов для задачи выполнимости // Материалы III Всероссийской конференции "Проблемы оптимизации и экономические приложения". Омск, 2006.1. С. 102.

27. Колоколов А.А., Тюрюмов А.Н., Ягофарова Д.И. Разработка и экспериментальное исследование алгоритмов решения задач выполнимости и максимальной выполнимости. Препринт. Омск: Ом ГУ, 2006. - 19 с.

28. Колоколов А.А., Чередова Ю.Н. Исследование и решение задачи о выполнимости с использованием L-разбиения // Материалы международной конференции "Дискретный анализ и исследование операций". Новосибирск, 2000. - С. 150.

29. Колоколов А.А., Ягофарова Д.И. Об одной модели целочисленного программирования для задачи о минимальном комитете // Материалы российской конференции "Дискретный анализ и исследование операций". Новосибирск, 2004. - С. 163.

30. Колоколов А.А., Ягофарова Д.И., Тюрюмов А.Н. Разработка алгоритмов для задачи выполнимости и некоторых ее обобщений с использованием перебора L-классов // Омский научный вестник.- 2006. № 5 (39)-С. 57-61.

31. Колоколов А.А., Ярош А.В. Проектирование одежды с использованием некоторых моделей дискретной оптимизации // Омский научный вестник. 2002. - Вып. 20. - С. 91 - 94.

32. Коутинхо С. Введение в теорию чисел. Алгоритм RSA. -М.: Постмаркет, 2001. 328 с.

33. Кузнецова А.А., Стрекаловский А.С., Цевээндорж И. Об одном подходе к решению целочисленных задач оптимизации //ЖВМ и МФ. 1999. - Т. 39. - М. - С. 9 - 16.

34. Мазуров Вл.Д. Метод комитетов в задачах оптимизации и классификации. М.: Наука, 1990. - 248 с.

35. Мазуров Вл.Д., Хачай М.Ю. Комитетпые конструкции // Известия Уральского университета. 1999, серия "Математика - механика".- Вып. 2 (14). С. 77 - 109.

36. Мазуров Вл.Д., Хачай М.Ю. Комитеты систем линейных неравенств // Автоматика и телемеханика. 2004. - № 2. -С. 43 - 54.

37. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. - 512 с.

38. Сайко JI.A. Исследование мощности L-накрытий некоторых задач о покрытии // Дискретная оптимизация и анализ сложных систем.- Новосибирск: ВЦ СО АН СССР, 1989. С. 76 - 97.

39. Семенов А.А., Буранов Е.В. Погружение задачи криптоанализа симметричных шифров в пропозициональную логику // Вычислительные технологии. 2003. - Т. 8. (Совместный выпуск с журналом "Региональный вестник Востока") - С. 118 - 126.

40. Сергиенко И.В., Шило В.П. Вероятностная декомпозиция задач линейного целочисленного программирования с булевыми переменными и автоматический выбор алгоритмов для их решения // Кибернетика и системный анализ. 1994. - № 2. - С. 149 - 158.

41. Сергиенко И.В., Шило В.П., Рощин В.А. Распараллеливание процесса оптимизации для задач дискретного программирования // Кибернетика и системный анализ. 2004. - № 2. - С. 45 - 52.

42. Симанчев Р.Ю. Сравнение вполне регулярных отсечений и алгоритмов // Методы решения и анализа задач дискретной оптимизации. Омск: ОмГУ, 1992. - С. 107 - 123.

43. Соколинская И.М., Соколинский Л.Б. Параллельный алгоритм решения задачи линейного программирования с неформализованными ограничениями // Материалы III Всероссийской конференции "Проблемы оптимизации и экономические приложения". Омск, 2006. - С. 156.

44. Схрейвер А. Теория линейного и целочисленного программирования: в 2-х т. М.: Мир, 1991. - 702 с.

45. Файзуллин Р.Т., Салаев Е.В. Об одном итерационном алгоритме решения задачи "Выполнимость" // Материалы III Всероссийской конференции "Проблемы оптимизации и экономические приложения". Омск, 2006. - С. 129.

46. Файзуллин Р.Т., Салаев Е.В. Применение метода последовательных приближений с инерцией к решению задачи 3-SAT // Таврический вестник информатики и математики. 2006. - №1. - С. 44 - 49.

47. Хачай М.Ю. К задаче о минимальном комитете // Тезисы докладов Всероссийской конференции "Алгоритмический анализ неустойчивых задач". Екатеринбург, 2004. - С. 309.

48. Ху Т. Целочисленное программирование и потоки в сетях. -М.: Мир, 1974. 520 с.

49. Шевченко В.Н. Качественные вопросы целочисленного программирования. М.: Физматлит, 1995. - 190 с.

50. Ягофарова Д.И. Анализ L-структуры задачи 2-выполнимости // Материалы ежегодного научного семинара "Под знаком -Омск: ООО "Издатель-Полиграфист", 2003. С. 71 - 77.

51. Ablow С.М., Kaylor D.J. Inconsistent homogenous linear inequalities // Bull.Amer.Math.Soc. 1965. - V. 71 - № 5. - P. 724.

52. Ablow C.M., Kaylor D.J. A commitee solution of the pattern recognition problem // IEEE Trans. 1965. - V. IT-11. - № 3. -P. 453 - 455.

53. Aspvall В., Plass M.F., Tarjan R.E. A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas // Information Processing Letters 8(3). 1979. - P. 121 - 132.

54. Ayteiniz T. A probabilistic study of 3-Satisfiability. Dissertation for the degree of Doctor of Philosophy. 2001. - 119 p.

55. Back Т., Eiben A.E., Vink M.E. A superior evolutionary algorithm for 3-SAT //In Proc. of the 7th Annual Conference on Evolutionary Programming, LNCS 1744. 1998. - P. 125 - 136.

56. Blair C.E., Jeroslow R.G., Lowe J.K. Some results and experiments in programming techniques for propositional logic //Computers and Operations Research. 1986. - V. 13. - №5. - P. 633 - 645.

57. Borchers В., Furman J. A Two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems //Journal of Combinatorial Optimization. 1998. - V.2. - №4. - P. 299 - 306.

58. Boros E., Crama Y., Hammer P.L. Polynomial-time inference of all valid implications for Horn and related formulae // Annals of Mathematics and Artificial Intelligence. 1990. - V. 1. - P. 21 - 32.

59. Boros E., Hammer P.L., Sun X. Recognition of q-Horn formulae in linear time // Discrete Applied Mathematics. 1994. - V. 55. - P. 1 - 13.

60. Cheriyan J., Cunningham W.H., Tuncel L., and Wang Y. A linear programming and rounding approach to max 2-sat // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1996. -V. 26. - P. 395 - 414.

61. Cook S.A. The complexity of theorem-proving procedure // Proc. 3rd Annual ACM Symposium on the Theory of Computing. 1971. -P. 151 - 159.

62. Cook S.A., Mitchell D.G. Finding Hard Instances of the Satisfiability-Problem: A Survey // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1996. - V. 35. - P. 1 - 17.

63. Davis M., Logemann G., Loveland D. A machine program for theorem-proving // Communications of the ACM. 1962. - V. 5. - Ж 7. -P. 394 - 397.

64. Davis M., Putnam H. A computing procedure for quantification theory // Journal of the ACM. 1960. - V. 7. - Ж 3. - P. 201 - 215.

65. Dowling W.F., Gallier J.H. Linear-Time Algorithms for Testing the Satisfiability of Propositional Horn Formulae // Journal of Logic Programming 1, 1984, P. 267 284.

66. Eremeev A. Modeling and Analysis of Genetic Algorithm with Tournament Selection // Proc. of Artificial Evolution Conference. Lecture Notes in Computer Science, 2000. Vol. 1829. - P. 84 - 95.

67. Eremeev A.V., Kolokolov A.A. On some genetic and L-class enumeration algorithms in integer programming // Proc. of the First Intertational Conference on Evolutionary Computation and its Applications. Moscow, 1996. - P. 297 - 303.

68. Franco J., Van Gelder A. A perspective on certain polynomial time solvable classes of satisfiability // Discrete Applied Mathematics. -2003. V. 125. - P. 297 - 303.

69. Goemans M.X., Williamson D.A. New 3/4-approximation algorithms for MAX SAT // SIAM Journal on Discrete Mathematics. 1994. -№.7. - P. 656 - 666.

70. Goldberg D. Genetic Algorithms in Search, Optimization and Machine Learning. Reading: Addison Wesley, 1989. - 412 pp.

71. Gu J. Local Search for the Satisfiability (SAT) Problem // IEEE Transaction on Sistems, Man and Cibernetics. 1993. - № 23 (4) -P. 1108 - 1129.

72. Gu J., Purdom P., Franco J., Wah B. Algorithms for the Satisfiability (SAT) Problem: A Survey // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1996. - V. 35. - P. 19 - 130.

73. Hansen P., Jaumard B. Algorithms for the Maximum Satisfiability Problem. // Computing 44. 1990. - P. 279 - 303.

74. Hastad J. Some optimal inapproximability results //Proc. of the 29th Annual ACM Symposium on Theory of Computing, 1997. P. 1 - 10.

75. Hogg T. Refining the phase transition in combinatorial search // Artificial Intelligence. 1996. - V.81. - P. 127 - 154.

76. Hooker J.N. Generalized resolution and cutting planes //Annals of Operations Research. 1988. - V.12. - P. 217 - 239.

77. Jaumard В., Stan M., Desrosiers J. Tabu Search and a Quadratic Relaxation for the Satisfiability Problem // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1996. - Vol. 26. -P. 457 - 477.

78. Johnson D. Approximation algorithms for combinatorial problems //Journal of Comput. System Science. 1974. - V.9. - P. 256 - 278.

79. Joy S., Mitchell J., Borchers B. A branch and cut algorithm for MAX-SAT and weighted MAX-SAT // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1997. - V. 35. -P. 519 - 536.

80. Karloff H., Zwick U. A 7/8-approximation algorithm for MAX 3-SAT? //Proc. of the 38th Annual IEEE Symposium on Foundations of Computer Science, 1997. P. 406 - 415.

81. Kautz H., Selman В. Planning as Satisfiability // Proceedings of the 10th European Conference on Artificial Intelligence (ECAI 92). 1992.- P. 359 363.

82. Kohli R., Krishnamurti R. Average perfomance of heuristics for satisfiability //SIAM Journal on Discrete Mathematics. 1989. - V.2.- P. 508 523.

83. Kolokolov A.A., Adelshin A.V., Cheredova J.N. The L-partition approach to SAT and MAX SAT // Annual Conference of the GOR. Abstracts. Duisburg, 2001. - P. 118.

84. Kolokolov A., Adelshin A., Yagofarova D. Development of Local Search Algorithms for MAX-SAT Problem Using L-class Enumeration // International Conference on Operations Research 2006. Abstract Guide.- Karlsruhe, 2006. P. 78.

85. Kolokolov A., Adelshin A., Yagofarova D. Local search algorithms for the MAX SAT problem based on L-class enumeration //Extended Abstracts of 18th Mini Euro Conference on VNS. Tenerife (Spain), 2005.-P. 117-118.

86. Kolokolov A., Kallrath J.,Yagofarova D. Analysis and Solving the Satisfiability Problem Using L-partition. // Abstracts of Annual International Conference Operations Research 2003. Heidelberg, 2003.- P. 128.

87. Kolokolov A., Yagofarova D., Tyuryumov A. Development of L-class Enumeration Algorithms for Satisfiability Problem // Abstracts of Annual International Conference Operations Research 2005. Bremen, 2005. - P. 107 - 108.

88. Kullmann O. New methods for 3-SAT decision and worst-case analysis.- Theoretical Computer Science 223 (1-2), 1999. P. 1 - 72.

89. Laursen Per S. Parallel Heuristic search introductions and a new approach // Solving Combinatorial Optimiz. Problems in Parallel / ed. A. Ferreire and P. Pardalos. - Berlin: Springer-Verlag, 1996. -P. 248-274.

90. Marathe M.V., Ravi S.S. On approximation algorithms for the minimum satisfiability problem // Information Processing Letters. -1996. V. 58. - P. 23 - 29.

91. Marchiori E., Rossi C. A flipping genetic algorithm for hard 3-SAT problems //In Proc. of the Genetic and Evolutionary Computation Confeence (GECCO-99). 1999. - P. 393 - 400.

92. Mazure В., Sais L., Gregorie E. Tabu Search for SAT // Proceedings of CP'95 Workshop on Solving Really Hard Problems. 1995. -P. 127 - 130.

93. Mazurov VI.D., Khachai M.Yu., Rybin A.I. Committee Constructions for Solving Problems of Selection, Diagnostics, and Prediction // Proceedings of the Steklov Institute og mathematics Suppl. 1 2002. -P. 67-101.

94. Mitchell D., Selman В., Levesque H. Hard and Easy Distributions of SAT Problems // Proceedings of АААГ92. 1992 - P. 459 - 465.

95. Monien В., Speckenmeyer E. Solving Satisfiability in less then 2" steps. // Discrete Applied Mathematics. 1985. - JV* 10. - P. 287 - 295.

96. Papadimitriou C.H. On selecting a satisfying truth assignment // Proc. of FOCS'91. 1991. - P. 163 - 169.

97. Paturi R., Pudlak P., Saks M.E., Zane F. An improved exponential-time algorithm for k-SAT // Proc. of FOCS'98. 1998. - P. 628 - 637.

98. Paturi R., Pudlak P., Zane F. Satisfiability coding lemma // Proc. of FOCS'97. 1997. - P. 566 - 574.

99. Reeves С. Genetic Algorithms for the Operation Researcher // INFORMS Journal on Computing, 1997. V. 9. - № 3. - P. 231 - 250.

100. Resende M.G.C, Feo T.A. A GRASP for Satisfiability // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. -1996. V. 26. - P. 499 - 520.

101. Schoning U. A probabilistic algorithm for k-SAT and constraint satisfaction problems // Proc. of FOCS'99. 1999. - P. 410 - 414.

102. Scutella M.G. A note on Dowling and Gallier's top-down algorithm for propositional Horn satisfiability // Journal of Logic Programming. -1990. V. 8. - P. 265 - 273.

103. Selman В., Kautz H., Cohen B. Local Search Strategies for Satisfiability Testing // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1996. - V. 26 - P. 521 - 531.

104. Spears M.W. Simulated Annealing for Hard Satisfiability Problems // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1996. - V. 26. - P. 533 - 557.

105. Stiitzle Т., Hoos H., Roli A. A review of the literature on local search algorithms for MAX-SAT // Technical Report AIDA-01-02. Darmstadt University of Technology. Computer Science Department. Intellectics Group. 2001. - 21 pp.

106. Velev M.N., Bryant R.E. Effective use of boolean satisfiability procedures in thr formal verification of superscalar and VLIM microprocessors. // Proc. of 38th Design Automation Conference (DAC'01). 2001. - P. 226 - 231.

107. Yannakakis M. On the approximation of maximum satisfiability // Proc. of the 3rd ACM-SIAM Symposium on Discrete Algorithms. -1992. P. 1 - 9.114. www.cs.ubc.ca/~hoos/SATLIB/benchm.html115. www.nmt.edu/~borchers/maxsat.html