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

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

¿И

АДЕЛЫПИН Александр Владимирович

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

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

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

Омск - 2006

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

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

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

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

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

кандидат физико-математических наук, доцент Заблоцкая Ольга Александровна

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

Институт динамики систем и теории управления СО РАН

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

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

Автореферат разослан " & " Си1/?е^ 2006 г.

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

диссертационного совета, [Н/ У

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

looCft

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

Актуальность темы. Во многих задачах управления, планирования, проектирования и других областях возникают логические ограничения, которые необходимо учитывать в процессе принятия решений. В связи со сложностью этих задач для их решения применяются модели и методы системного анализа, исследования операций и оптимизации. Указанные ограничения часто описываются с помощью логических формул и приводят к задачам максимальной или минимальной выполнимости, представляющих собой обобщения известной задачи выполнимости, одной из центральных в теории сложности. Задача выполнимости является первой, для которой была доказана iVP-полнота [13]. f Задачам, связанным с выполнимостью логических формул, посвяще-

но значительное число работ в области дискретной оптимизации. Основными направлениями исследований являются разработка и анализ алгоритмов их решения, изучение структуры и сложности задач, выделение полиномиально разрешимых подклассов и построение семейств "трудных" задач для определенных классов алгоритмов [1, 7, 11, 12, 14, 16, 18 - 20].

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

В настоящее время проблематика ЦП является достаточно широкой и включает исследование структуры и сложности решения задач, полиэдральный подход, методы отсечения, ветвей и границ, декомпозиции, приближенные и гибридные алгоритмы, метаэвристики, устойчивость задач и алгоритмов, многокритериальные постановки и ряд других [2, 5, 6, 8 -10]. Во многих алгоритмах используется аппарат непрерывной оптимизации [3, 5, 8].

Для исследования задач ЦП, разработки и анализа алгоритмов, основанных на релаксации условия целочисленности, A.A. Колоколовым был предложен метод регулярных разбиений [5]. Ранее с использованием этого подхода в [2, 4 - 6] и других работах исследована сложность решения ряда задач ЦП, изучена структура релаксационных множеств, введены

РОС. национальна!

3 БИБЛИОТЕКА

L.

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

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

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

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

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

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

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

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

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

4. На предложенных семействах задач проведен анализ алгоритмов перебора ¿-классов, ветвей и границ (метод Лэнд и Дойг) и двойственных дробных алгоритмов отсечения. Показано, что число итераций алгоритмов перебора L-классов и ветвей и границ на некоторых семействах экспоненциально зависит от размерности задач, а число итераций первого алгоритма Гомори растет линейно.

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

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

РАН (2000-2006).

Публикации. Основные результаты диссертации опубликованы в работах [21 - 32].

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

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

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

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

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

Пусть даны логические переменные ..., хп, которые могут принимать только два значения: истина или ложь. Литералом называется либо переменная хг либо ее отрицание хг Литерал х3 принимает значение истина в том и только в том случае, если переменная х} принимает значение ложь. Рассмотрим логическую формулу F в конъюнктивной нормальной форме (КНФ), т. е. представляющую собой конъюнкцию скобок (формул) Ст, каждая из которых является дизъюнкцией

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

Обобщениями задачи выполнимости являются задачи максимальной и минимальной выполнимости в следующих постановках. Пусть скобки Си. ■., Ст имеют неотрицательные веса с\,..., Ст. Задача максимальной (минимальной) выполнимости состоит в том, чтобы найти такой набор значений переменных, при котором суммарный вес всех выполненных скобок будет наибольшим (наименьшим).

Известно, что задачи максимальной и минимальной выполнимости являются Л^Р-трудными даже, если каждая скобка содержит не более двух литералов, в то время как аналогичная задача выполнимости полиномиально разрешима [13].

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

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

Точки х, у е Ып (х У у) называются Ь-эквивалентными, если не существует отделяющей их точки 2 € Я", т. е. такой, что выполняется х У 2 У у. Здесь >-, У - символы лексикографического сравнения векторов. Такое отношение эквивалентности порождает разбиение любого множества X С Я™ на непересекающиеся Ь-классы. Соответствующее фактор-множество Х/Ь называется Ь-разбиением множества X. Очевидно, что каждая точка множества X П 7>п образует отдельный ¿-класс. Остальные элементы множества Х/Ь являются дробными Ь- классами.

Подмножество К дробных ¿-классов из Х/Ь называется комплексом (.Ь-комплексом), если V V. V' € К не найдется точки г е X П отделяющей V и V'. Будем говорить, что выпуклое множество X имеет альтернирующую Ь-структуру, если выполняются условия:

1) мощность любого комплекса из Х/Ь не превосходит 1;

2) лексикографически максимальный и минимальный элементы множества Х/Ь являются целочисленными (если они существуют).

Альтернирующей ¿-структурой обладают релаксационные множества ряда известных задач ЦП, в частности, задач об упаковке и покрытии множеств, задачи стандартизации и других. Такого типа структура используется для построения оценок мощности ¿-накрытий и числа итераций алгоритмов отсечения, а также при разработке алгоритмов [5].

Пусть О - непустое замкнутое множество в Я". Рассмотрим задачу ЦП в лексикографической постановке:

найти г* = 1ехтпах(£1 П 2п). Определим множество

П. = {хеП: х>г Уг е (ПП £")},

называемое дробным накрытием задачи, а - ее Ь-накрытием.

Для задачи на минимум

найти г* = 1ехтт(П П дробное накрытие задачи определяется следующим образом: П. = х<г

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

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

Достаточно широкий класс алгоритмов решения задачи выполнимости основан на использовании процедуры расщепления. Под расщепляющим алгоритмом понимается алгоритм, который сводит задачу для исходной формулы Р к задаче для полиномиального числа формул ^х,..., Рр. В зависимости от типа сведения (детерминированное или вероятностное) существующие расщепляющие алгоритмы можно разделить на два семейства: ОРЬЬ-подобные и РР82-подобные алгоритмы.

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

В некоторых работах, например в [12, 18, 21, 24, 27], задачи с логическими условиями формулируются как задачи целочисленного линейного

программирования (ЦЛП), где каждой скобке исходной формулы ставится в соответствие линейное неравенство. Таким образом, для анализа и решения данных задач применяется аппарат ЦП. Разработаны методы ветвей и границ, отсечений и комбинации ветвей и границ с отсечениями [11, 12, 15, 17]. Кроме того, в последние годы развивается подход, в котором используются регулярные разбиения релаксационных многогранников задач. В данном разделе приводятся также оценки точности известных приближенных алгоритмов для решения задач максимальной и минимальной выполнимости.

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

В п. 2.1 приводятся модели ЦЛП задач выполнимости и максимальной выполнимости, предлагается модель для задачи минимальной выполнимости, на основе которых исследуется L-структура многогранников указанных задач.

Вместе с данными логическими переменными х\,...,хп введем булевы переменные yi,-.-,yn такие, что у} соответствует переменной х-,, а (1 — у3) - ее отрицанию, j = 1,... ,п. Условие истинности формулы F эквивалентно существованию решения системы

\С;\,г = 1,... ,то; (1)

j6C+ jeer

0<%<1, j = l,...,n; (2)

у/ € Z, j = 1,...,п, -(з)

где С; и Сг+ - множества индексов переменных, входящих в скобку С, с отрицанием и без него соответственно, i — 1,..., т. Через М обозначим многогранник, задаваемый системой ограничений (1)-(2).

Таким образом, задача выполнимости сводится к отысканию некоторой целочисленной точки многогранника М или доказательству того, что ее не существует. При этом можно сформулировать задачу выполнимости как задачу поиска лексикографически максимального допустимого решения множества (1)-(3):

найти 1ехтпах(М П Zn).

Рассмотрим модель ЦЛП для задачи максимальной выполнимости:

т

Уо = £ -> max (4)

i=l

£ Vi- £ Vi + Zi<\Crl i = l,...,m-, (5)

jeCf jeCt

0<Vj<l, j = l,...,n; (6)

0 < Zj < 1, i = 1,... ,m; (7)

€ Z, j = 1 ,...,n, i = l,...,m. (8)

В такой постановке в любом допустимом целочисленном решении z, = 1 только в том случае, когда формула Ci выполнена, г = 1,..., т. Таким образом, оптимальное значение целевой функции равно наибольшему суммарному весу выполненных скобок. Через Р обозначим многогранник, определяемый системой ограничений (5)-(7).

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

Далее рассматривается задача минимальной выполнимости и предложенный нами вариант модели ЦЛП:

т

Уо-Т, dzi min (9)

i=l

£ Vj - Е У} + hzx > m г-1,...,т; (10)

jeC,~ jeC?

0<»j<1, j = l,...,n; (11)

0 < ц < 1, t = l,...,m; (12)

j = l,...,n, i' = l,...,m. (13)

Здесь ki - длина скобки Ci, т. е. число входящих в нее литералов. Легко показать, что Zj = 0 только в том случае, когда формула Ci не выполнена. Таким образом, оптимальное значение целевой функции равно наименьшему суммарному весу выполненных скобок. Через Q обозначим многогранник, задаваемый системой (10)—(12).

Пусть в задачах (4)-(8) и (9)-(13) переменные упорядочены следующим образом: у\,..., уп, z\,..., zm. При этом предположении нами доказаны следующие утверждения.

Теорема 2.1 Многогранник Р задачи максимальной выполнимости (4)-(8) имеет альтернирующую Ь-структуру.

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

Теорема 2.2 Мощность любого Ь-комплекса многогранника <2 задачи минимальной выполнимости (9)-(13) не превосходит т+ 1.

Данная оценка является достижимой. Можно показать, что многогранник задачи минимальной выполнимости с формулой вида

^ = (XI V х2)(х3 V х4)... (х„_! V хп)

содержит ¿-комплекс мощности т + 1.

Таким образом, ¿-структура многогранника <3 задачи минимальной выполнимости "хуже", чем у многогранника Р задачи максимальной выполнимости, т.к. С? содержит более мощные ¿-комплексы, которые могут оказывать влияние на работу алгоритмов.

В п. 2.2 построены семейства логических формул, для которых исследована ¿-структура задач выполнимости, максимальной и минимальной выполнимости. Для некоторых из построенных семейств установлено, что данные задачи имеют ¿-накрытия, мощность которых растет экспоненциально с увеличением числа переменных в формуле. Пусть г = г(п) - полином степени не меньше 1 от п, г(п) —* +оо при п —> +оо, тогда верна следующая

Теорема 2.4 Пусть дана логическая формула вида ^ = С1Л... Л СГ) где формула С* не выполнима для каждого г = 1,... ,г и оптимальное решение любой задачи максимальной выполнимости для формулы С\ достигается более, чем на одном наборе значений переменных. Тогда мощность Ь-накрытия задачи максимальной выполнимости формулы F растет экспоненциально с увеличением числа переменных.

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

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

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

Семейство Б5. = С\ А ... А Сг, где С, = (х4,_з V з^Х^г-з V Хь-2){ХЬ-2УХь) для г = 1,... ,Г.

Семейство Э6. ¿6 = Сг Л ... Л СГ, где С, = (£51-4 V Х5»Х%-4 V Ух5г_з)(х5!_з V х51)(х51-2 V хы){хь^г V ®и-1)(®5<-1 V х5г) для г = 1,..., г.

Отметим, что матрицы соответствующих задач ЦЛП имеют блочно-диагональную структуру. Кроме того, в работе приводится семейство задач с матрицей другой структуры, в котором логические формулы имеют следующий вид:

Р = Сг А ... А Сп_2 А С', где Сг — (хг V хп-\ V х„), г = 1,..., п — 2, п- целое число, большее 2, и С = (х„_1 V хп)(хп-х V ¿„)(х П—1 » -Ьп ){Х п— IV!»).

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

Результаты второй главы приводятся в [22, 24, 26, 27, 30, 31].

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

В п. 3.1 выделяются семейства задач, для которых строятся оценки числа итераций алгоритмов перебора ¿-классов, ветвей и границ (метод Лэнд и Дойг) и двойственных дробных алгоритмов отсечения. Приведем один из полученных результатов для алгоритма ветвей и границ ЬВ.

Теорема 3.2 Если семейство логических формул удовлетворяет условиям теоремы 2.4, то число итераций алгоритма ЬО при решении задачи максимальной выполнимости для данного семейства растет экспоненциально с увеличением числа переменных в формуле.

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

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

нечной последовательности задач выполнимости, которые можно решать любым точным алгоритмом, в частности, алгоритмом перебора ¿-классов ЬСЕ, предложенным в работе [28].

Каждой скобке С4 поставим в соответствие булеву переменную 5,, г = 1,...,7тг. Тогда логической формуле Р будет отвечать множество булевых ш-векторов гк = (гк,..., г*), где к = 1,..., 2т. Разобьем множество всех векторов гк на подмножества следующим образом: гкг и гЬ принадлежат одному подмножеству, если число их нулевых компонент одинаково. При этом будем говорить, что все векторы с числом нулевых компонент, равным т, образуют т-слой (т = 0,..., т).

Идея алгоритмов состоит в частичном переборе т-слоев по некоторым правилам, например, с учетом текущего рекордного значения целевой функции р или в порядке возрастания т. На каждом т-слое осуществляется направленный перебор векторов гк в соответствии с лексикографическим порядком. В процессе решения для гк формулируется следующая задача: найти такой набор значений логических переменных, при котором скобка Сг выполнена тогда и только тогда, когда гк = 1, г = 1 ,...,ш. Если решение задачи найдено, то текущее рекордное значение р обновляется. После рассмотрения т-слоя ищем новый слой, содержащий векторы с числом нулей, меньшим т. Если такой слой существует, то переходим к перебору векторов на нем. В противном случае алгоритм завершает работу, текущее значение р является оптимальным значением целевой функции.

В работе исследуется вариант алгоритма, в котором перебор т-слоев осуществляется последовательно для значений т = 0,1,2,.... Каждая задача выполнимости решается алгоритмом ЬСЕ. Алгоритм завершает работу, если формула в текущей задачи выполнимости является выполнимой. Указанный алгоритм обозначим А1.

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

Определим окрестность £}Г(г) текущей точки г радиуса г:

1) г 6 Qr(z);

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

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

Результаты третьей главы опубликованы в [21, 23, 25, 28, 29, 32].

В четвертой главе приводятся результаты вычислительного эксперимента на сериях случайных задач, семействах из электронных библиотек DIMACS и SATLIB и семействах задач S5 и S6 с экспоненциальными * L-накрытиями, построенных в главе 2. С целью апробации и сравнения предложенных алгоритмов в данной работе реализованы алгоритмы AI и LS. В п. 4.1 исследуются алгоритмы точного решения задачи максимальной выполнимости. Для большинства серий задач время работы алгоритма AI сравнивалось со временем работы пакета OPL Studio (для задач с числом переменных и числом ограничений не более 300 использовалась версия 3.7, для остальных 2.1). Во многих случаях алгоритм AI заметно опережал OPL Studio. На рассматриваемых семействах также было проведено сравнение предложенного нами алгоритма с известным точным гибридным алгоритмом B.Borchers и J.Furman [11] (алгоритм BF). Кроме того, при решении задач алгоритмом AI использовалась специальная процедура переупорядочения переменных, которая в ряде случаев существенно ускоряла процесс решения.

Представленные результаты эксперимента показывают эффективность алгоритма j41. Выделены семейства задач из электронной библио- « теки, на которых этот алгоритм заметно превосходит алгоритм BF. На некоторых сериях задач время работы исследуемых алгоритмов не сильно отличается. Указаны также семейства задач, при решении которых алгоритм AI уступает алгоритму BF.

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

лиотеки DIMACS. Отметим следующие особенности алгоритма LS. Начальная точка генерируется случайно, точки текущей окрестности перебираются в лексикографическом порядке. Кроме того, время решения каждой задачи выполнимости было ограничено величиной tsAT■ В данном разделе приводится сравнение вариантов алгоритма LS при различных значениях îsat-

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

В заключении приводятся основные результаты диссертации. Список литературы

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

[2] Девятерикова М.В., Колоколов A.A. Анализ устойчивости некоторых алгоритмов дискретной оптимизации //Автоматика и телемеханика. - 2004. - №3. - С. 48 - 54.

[3] Еремин И.И. Теория линейной оптимизации. - Екатеринбург: Изд-во ИММ, 1998. - 247 с.

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

[5] Колоколов A.A. Регулярные разбиения и отсечения в целочисленном программировании //Сиб. журнал исследования операций. - 1994. -Ш - С. 18 - 39.

[6] Колоколов A.A., Девятерикова М.В. Анализ устойчивости L-разбиения множеств в конечномерном пространстве //Дис-

кретный анализ и исследование операций, 2000. Серия 2. - Т.7. -№2. - С. 47 - 53.

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

[8] Кузнецова А.А., Стрекаловский А.С., Цевээндорж И. Об одном подходе к решению целочисленных задач оптимизации //ЖВМ и МФ.

- 1999. - Т.39. - №1. - С. 9 - 16.

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

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

[11] 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.

[12] 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.

[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] Hansen P., Jaumard B. Algorithms for the maximum satisfiability problem //Computing. - 1990. - V.44. - P. 279 - 303.

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

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

[17] 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.

[18] 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. - P. 19 - 130.

[19] Kohli E., Krishnamurti R., Mirchandani P. The minimum satisfiability problem //SIAM Journal on Discrete Mathematics. - 1994. - J№9. -P. 275 - 283.

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

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

[21] Адельшин А.В. Задача максимальной выполнимости и некоторые алгоритмы целочисленного программирования. В кн.. Алгебра и линейная оптимизация. Труды международного семинара, посвященного 90-летию со дня рождения С. Н. Черникова, Екатеринбург. - Екатеринбург: УрО РАН, 2002. - С. 235 - 239.

[22] Адельшин А.В. Исследование задачи минимальной выполнимости с использованием L-разбиения //Информационный бюллетень Ассоциации мат. программирования. - Вып. 10. - Екатеринбург: УрО РАН, 2003. - С. 19 - 20.

[23] Адельшин А.В. Задача минимальной выполнимости и некоторые алгоритмы дискретной оптимизации //Материалы конференции "Проблемы оптимизации и экономические приложения". - Омск, 2003. -С. 72.

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

[25] Адельшин А.В. О сравнении некоторых алгоритмов целочисленного программирования //Материалы конференции "Дискретный анализ и исследование операций". - Новосибирск, 2004. - С. 149.

[26] Адельшин А.В., Колоколов А.А. Исследование задачи максимальной выполнимости с использованием L-разбиения //Материалы конференции "Дискретный анализ и исследование операций". - Новосибирск, 2002. - С. 201.

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

1

[28] Колоколов А.А., Адельшин А.В., Ягофарова Д.И. Решение задач выполнимости и некоторых ее обобщений с использованием метода перебора L-классов //Прикладная математика и информационные технологии. - Омск, 2005. - С. 68 - 79.

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

[30] Adelshin A.V., Kolokolov А.А. The L-partition approach to the MAX SAT problem //XXXIII International Conference on Operations Research AIR02002: Book of Abstracts. - Italy, 2002. - P. 44.

[31] 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.

[32] 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.

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

Подписано в печать 03.04.2006. Формат 60x84/16. Печ. л. 1,25. Уч.-изд. л. 1,3. Тираж 120 экз. Заказ №100.

Отпечатано в издательско-полиграфическом отделе ОмГУ 644077, г. Омск, пр. Мира, 55а

I

г

Введение

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

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

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

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

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

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

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

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

2.3 Анализ L-накрытий задач.

Глава 3. Разработка и анализ алгоритмов для задач максимальной и минимальной выполнимости

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

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

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

Глава 4. Результаты вычислительного эксперимента

4.1 Исследование и сравнение алгоритмов точного решения

4.2 Исследование алгоритмов локального поиска.

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

Задачам, связанным с выполнимостью логических формул, посвящено значительное число работ в области дискретной оптимизации. Основными направлениями исследований являются разработка и анализ алгоритмов их решения, изучение структуры и сложности задач, выделение полиномиально разрешимых подклассов и построение семейств "трудных" задач для определенных классов алгоритмов [8, 41 - 47, 49, 51 - 54, 56, 57, 59, 63 - 66, 68, 69, 75, 76, 79 - 83, 86, 87, 89].

Одним из подходов к решению задач выполнимости и максимальной выполнимости является использование аппарата целочисленного линейного программирования (ЦЛП). В работах [41, 49, 66] используются модели ЦЛП для этих задач.

Для анализа задач целочисленного программирования (ЦП), разработки и исследования алгоритмов, основанных на релаксации условия целочисленности, А.А. Колоколовым был предложен метод регулярных разбиений [17]. Ранее с использованием этого подхода в [11, 14 - 17, 21, 35, 55, 74] и других работах исследована сложность решения ряда задач ЦП, изучена структура релаксационных множеств, введены новые классы отсечений, построены оценки числа итераций для некоторых известных алгоритмов, исследована устойчивость задач и алгоритмов, разработаны новые алгоритмы.

С помощью этого подхода начаты исследования задачи выполнимости, которые показали перспективность его применения [25]. Поэтому актуальным является дальнейшее использование указанного подхода для анализа задач с логическими ограничениями. С помощью него в диссертации исследуются задачи максимальной и минимальной выполнимости. Основные результаты получены на основе L-разбиения, которое является наиболее изученным среди регулярных разбиений.

В настоящее время проблематика ЦП является достаточно широкой и включает исследование структуры и сложности решения задач, полиэдральный подход, методы отсечения, ветвей и границ, декомпозиции, приближенные и гибридные алгоритмы, метаэвристики, устойчивость задач и алгоритмов, многокритериальные постановки и ряд других [И, 16, 17, 21 - 23, 26 - 30, 32, 35 - 38, 55]. Во многих алгоритмах используется аппарат непрерывной оптимизации [13, 17, 31, 28, 36].

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

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

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

Кроме того, на построенных семействах задач исследовались алгоритмы перебора L-классов, ветвей и границ (метод Лэнд и Дойг) и двойственные дробные алгоритмы отсечения. Показано, что число итераций первых двух алгоритмов на некоторых семействах экспоненциально зависит от размерности задач, в то время как для первого алгоритма Го-мори число итераций растет линейно. Разработаны алгоритмы точного и приближенного решения невзвешенной задачи максимальной выполнимости, основанные на использовании метода перебора L-классов, лексикографическом переборе векторов и локальном поиске. Проведены экспериментальные исследования эффективности этих алгоритмов.

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

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

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

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

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

4. На предложенных семействах задач проведен анализ алгоритмов перебора L-классов, ветвей и границ (метод Лэнд и Дойг) и двойственных дробных алгоритмов отсечения. Показано, что число итераций алгоритмов перебора L-классов и ветвей и границ на некоторых семействах экспоненциально зависит от размерности задач, а число итераций первого алгоритма Гомори растет линейно.

Заключение

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

1. Аделыпин А.В. Задача минимальной выполнимости и некоторые алгоритмы дискретной оптимизации //Материалы конференции "Проблемы оптимизации и экономические приложения". Омск. - 2003. - С. 72.

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

3. Аделыпин А.В. Исследование задачи минимальной выполнимости с использованием L-разбиения //Информационный бюллетень Ассоциации мат. программирования. Вып. 10. - Екатеринбург: УрО РАН, 2003. - С. 19 - 20.

4. Аделыпин А.В. О сравнении некоторых алгоритмов целочисленного программирования //Материалы конференции "Дискретный анализ и исследование операций". Новосибирск, 2004. - С. 149.

5. Аделыпин А.В., Адельшина А.Г. К оценке числа итераций для двойственных алгоритмов отсечения //Вестник Омского университета. 2000. -т.- С. 14 - 16.

6. Аделыпин А.В., Колоколов А.А. Исследование задачи максимальной выполнимости с использованием L-разбиения //Материалыконференции "Дискретный анализ и исследование операций". Новосибирск, 2002. - С. 201.

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

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

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

10. Девятерикова М.В., Колоколов А.А. Анализ устойчивости некоторых алгоритмов дискретной оптимизации //Автоматика и телемеханика. 2004. - т. - С. 48 - 54.

11. Девятерикова М.В., Колоколов А.А. Об устойчивости дробных накрытий задач целочисленного программирования //Междунар. конф. "Проблемы оптимизации и экономические приложения": Тез. докладов. Омск, 1997. - С. 59 - 61.

12. Еремин И.И. Теория линейной оптимизации. Екатеринбург: Изд-во ИММ, 1998. - 247 с.

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

14. Заозерская Л.А. Исследование и решение некоторых классов задач целочисленного программирования на основе регулярных разбиений: Автореф. дис. канд. физ.-мат. наук. Омск, 1998. - 16 с.

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

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

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

18. Колоколов А.А., Адельшин А.В., Ягофарова Д.И. Решение задач выполнимости и некоторых ее обобщений с использованием метода перебора L-классов //Прикладная математика и информационные технологии. Омск, 2005. - С. 68 - 79.

19. Колоколов А.А., Адельшин А.В., Ягофарова Д.И. Алгоритмы лексикографического перебора для решения задачи выполнимости и некоторых ее обобщений //Труды XIII Байкальской международной школы-семинара. Иркутск, 2005. - Т.1. - С. 503 - 508.

20. Колоколов А.А., Девятерикова М.В. Анализ устойчивости L-разбиения множеств в конечномерном пространстве //Дискретный анализ и исследование операций, 2000. Серия 2. Т.7. - №2. - С. 47-53.

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

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

23. Колоколов А.А., Нагорная З.Е., Гуселетова О.Н., Ярош А.В. Математические модели и программный комплекс для проектирова-" ния эскизов одежды //Прикладная математика и информационные технологии. Омск, 2005. - С. 80 - 98.

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

25. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование.- М.: Наука, 1969. 368 с.

26. Корбут А.А., Сигал И.Х., Финкельштейн Ю.Ю. Гибридные методы в дискретной оптимизации //Изв. АН СССР. Техн. кибернетика. -1988. т. - С. 65 - 77.

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

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

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

30. Попов Л.Д. Об одноэтапном методе решения лексикографических вариационных неравенств //Известия вузов. Математика. 1998. -№12 (439). - С. 71 - 81.

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

32. Семенова Н.В. Решение одной задачи обобщенного целочисленного программирования //Кибернетика. 1984. - №5. - С. 25 - 31.

33. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наукова думка, 1988. - 472 с.

34. Симанчев Р.Ю. О вполне регулярных отсечениях для задач целочисленной оптимизации //Управляемые системы. Новосибирск: ИМ СО АН СССР, 1990. - Вып. 30. - С. 61 - 71.

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

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

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

38. Adelshin A.V., Kolokolov А.А. The L-partition approach to the MAX SAT problem //XXXIII International Conference on Operations Research AIR02002: Book of Abstracts. Italy, 2002. - P. 44.

39. Aspvall B. Recognizing disguised NR(1) instances of the satisfiability problem //Joutnal of algorithms. 1980. - V.l. - P. 97 - 103.

40. Aytemiz T. A probabilistic study of 3-Satisfiability. Dissertation for the degree of Doctor of Philosophy. 2001. - 119 pp.

41. Bertsimas D., Teo C., Vohra R. New randomized rounding algorithms. Preprint. 1995.

42. Blair С.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.

43. 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.

44. 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.l. - P. 21 - 32.

45. Boros E., Crama Y., Hammer P.L., Saks M. A coplexity index for satisfiability problems //SIAM Journal of Computing. 1994. - V.23.- P. 45 49.

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

47. Chandru V., Hooker J.N. Extended Horn sets in propositional logic //Journal of the ACM. 1991. - V.38. - P. 205 - 221.

48. 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.

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

50. Crescenzi P., Капп V. A compendium of NP optimization problems. -1995.

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

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

53. Dowling W.F., Gallier J.H. Linear-time algorithms for testing the satisfiability of propositional Horn formulae //Journal of Logic Programming. 1984. - V.l. - P. 267 - 284.

54. 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 Applicatios. Moscow, 1996. - P. 297 - 303.

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

56. Hansen P., Jaumard B. Algorithms for the maximum satisfiability problem //Computing. 1990. - V.44. - P. 279 - 303.

57. Hansen P., Jaumard В., Mladenovic N., Parreira A.D. Variable neighbourhood search for maximum weighted satisfiability problem //Technical Report G-2000-62. Les Cahiers du GERAD. Group for Research in Decision Analysis. 2000.

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

59. Hogg T. Refining the phase transition in combinatorial search. //Artifical Inteligence. 1996. - V.81. - P. 127 - 154.

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

61. Jaumard В., Stan M., Desrosiers J. Tabu search and quadratic relaxation for satisfiability problem //DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1996. V.26. - P." 457 - 477.

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

63. 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.

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

65. 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. P. 19 - 130.

66. 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.

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

68. Kohli R., Krishnamurti R., Mirchandani P. The minimum satisfiability problem //SIAM Journal on Discrete Mathematics. 1994. - №9. - P. 275-283.

69. Kolokolov A.A. On the L-structure of integer linear programming problems //System modelling and optimization. Proc. of the 16th IFIP" conference on the modelling and optimization. Springer Verlag, 1993. - P. 756 - 760.

70. Kolokolov A.A. Regular partitions and cuts in the integer programming //Discrete Analysis and Operations Research. Kluver Academic Publishers. Netherlands, 1996. - P. 59 - 79.

71. 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.

72. 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.

73. Kolokolov A.A., Eremeev A.V., Zaozerskaya L.A. On hybrid L-class enumeration and genetic algorithm for set covering problem //15th Conference of International Federation of Operational Research Societies (IFORS'99): Abstracts. Pekin, 1999. - P. 117.

74. Lewis H.R. Renaming a set of clauses as a Horn set //Journal of the ACM. 1978. - V.25. - P. 134 - 135.

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

76. Monien В., Speckenmeyer E. Solving satisfiability in less then 271 steps //Discrete Applied Mathematics. 1985. - V.10. - P. 287 - 295.

77. Niedermeier R., Rossmanith P. New upper bounds for maximum satisfiability //Journal of Algorithms. 2000. - V.36. - P. 63 - 88.

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

79. 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.

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

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

82. 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.

83. 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.

84. Truemper K. Alpha-balanced graphs and matrices GF(3)-representability of matroids //Journal of Combinatorial Theory.- 1982. V.32. - P. 112 - 139.

85. Truemper K. Effective logic computation. Wiley, New York, 1998.

86. Vohra R. Personal communication. 1995.

87. Yagiura M., Ibaraki Т. Analyses on the 2 and 3-flip neighbourhoods for the MAX SAT //Journal of Combinatorial Optimization. 1999. -V.3. - P. 95 - 114.

88. Yannakakis M. On the approximation of maximum satisfiability //Proc. of the 3rd ACM-SIAM Symposium on Discrete Algorithms, 1992. ¥Г 1-9.90. www.cs.ubc.ca/~hoos/SATLIB/benchmMml91. www.dimacs.rutgers.edu/