Содержание к диссертации
Введение
Глава 1. Задачи дискретной оптимизации и выполнимость логических формул 9
1.1 Постановки задач и их сложность 9
1.2 Связь с другими задачами и некоторые приложения . 11
1.3 L-структура задач целочисленного программирования . 15
1.4 Методы решения 21
Глава 2. Исследование задач с использованием L-разбиения 25
2.1 L-структура многогранников задач максимальной и минимальной выполнимости 25
2.2 Построение специальных семейств логических формул . 32
2.3 Анализ L-накрытий задач 36
Глава 3. Разработка и анализ алгоритмов для задач максимальной и минимальной выполнимости 45
3.1 Анализ некоторых алгоритмов целочисленного программирования на основе L-разбиения 45
3.2 Алгоритмы точного решения для задачи максимальной выполнимости 62
3.3 Алгоритмы локального поиска для задачи максимальной выполнимости 69
Глава 4. Результаты вычислительного эксперимента 72
4.1 Исследование и сравнение алгоритмов точного решения . 72
4.2 Исследование алгоритмов локального поиска 84
Заключение 90
Список литературы
- Постановки задач и их сложность
- Связь с другими задачами и некоторые приложения
- L-структура многогранников задач максимальной и минимальной выполнимости
- Анализ некоторых алгоритмов целочисленного программирования на основе L-разбиения
Введение к работе
Во многих задачах управления, планирования, проектирования и других областях возникают логические ограничения, которые необходимо учитывать в процессе принятия решений. В связи со сложностью этих задач для их решения применяются модели и методы системного анализа, исследования операций и оптимизации. Указанные ограничения часто описываются с помощью логических формул и приводят к задачам максимальной или минимальной выполнимости, представляющих собой обобщения известной задачи выполнимости, одной из центральных в теории сложности. Задача выполнимости является первой, для которой была доказана 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-классов, лексикографическом переборе векторов и локальном поиске. Проведены экспериментальные исследования эффективности этих алгоритмов.
Диссертация состоит из введения, четырех глав и заключения.
В первой главе приводятся постановки задач выполнимости, максимальной и минимальной выполнимости, рассмотрен ряд связанных с ними задач дискретной оптимизации. Указаны некоторые полиномиально разрешимые подклассы задач выполнимости. Приведен краткий обзор существующих алгоритмов решения данных задач, включая точные, эвристические-и приближенные алгоритмы с гарантированной оценкой точности. Изложен метод регулярных разбиений, который является достаточно продуктивным при исследовании задач ЦП и анализе алгоритмов их решения.
Во второй главе проводится анализ задач выполнимости, максимальной и минимальной выполнимости на основе целочисленного программирования и L-разбиения. Показано, что многогранник задачи максимальной выполнимости имеет альтернирующую L-структуру, а мощность любого дробного комплекса многогранника задачи минимальной выполнимости не превосходит величины т + 1, где т - число скобок данной логической формулы, причем полученная оценка является достижимой. Построены семейства логических формул, для которых исследована L-структура задач выполнимости, максимальной и минимальной выполнимости. В частности, выделены семейства, для которых все указанные задачи имеют мощности L-накрытий, растущие экспоненциально с увеличением числа переменных в формуле. Задачи из построенных семейств могут быть использованы в качестве тестовых примеров для различных алгоритмов.
Третья глава посвящена разработке алгоритмов точного и приближенного решения задачи максимальной выполнимости, анализу ряда алгоритмов ЦП, основанных на использовании релаксационных множеств, при решении предложенных нами семейств задач максимальной и минимальной выполнимости. Выделены семейства задач, на которых число
итераций алгоритмов перебора L-классов и ветвей и границ (метод Лэнд и Дойг) растут экспоненциально с увеличением числа переменных. Показано, что при решении некоторых задач из этих семейств первым алгоритмом Гомори используется линейное число отсечений. Предложены схемы точного решения невзвешенной задачи максимальной выполнимости и алгоритмы локального поиска, основанные на сведении задачи к конечной последовательности задач выполнимости и переборе L-классов.
В четвертой главе содержатся результаты вычислительного эксперимента для разработанных нами алгоритмов. Проведено сравнение точного алгоритма с пакетом OPL Studio и с точным алгоритмом, предложенным B.Borchers и J.Furman [44], на сериях случайных задач, семействах из электронных библиотек DIM ACS и SATLIB, а также на семействах задач, построенных во второй главе. Кроме того, исследованы алгоритмы локального поиска при решении некоторых задач из библиотеки DIM ACS. Выполнено сравнение этих алгоритмов относительно времени работы и точности получаемых решений. В целом полученные результаты экспериментального исследования указывают на эффективность использования предложенных алгоритмов при точном или приближенном решении задач максимальной выполнимости.
Основные результаты диссертации опубликованы в работах [1 - 5, 7, 18, 19, 39, 72, 73] и докладывались на следующих конференциях и семинарах: Международной школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 2001 и 2005), Международной конференции по исследованию операций OR'2001 (Дуйсбург, Германия, 2001), Международном семинаре "Алгебра и линейная оптимизация", посвященном 90-летию со дня рождения С.Н. Черникова (Екатеринбург, 2002), Российской конференции "Дискретный анализ и исследование операций"(Новосибирск, 2002 и 2004), XXIV цикле научно-исследовательского семинара по дискретной математике (Одесса, 2002), Всероссийской конференции "Мате-
матическое программирование и приложения"(Екатеринбург, 2003), Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, 2003), Mini Euro Conference on VNS (Тенерифе, Испания, 2005), XXXVII Региональной молодежной школе-конференции "Проблемы теоретической и прикладной математики"(Екатеринбург, 2006), а также на научном семинаре "Математическое моделирование и дискретная оптимизация "в Омском филиале Института математики им. С.Л. Соболева СО РАН (2000-2006).
Автор благодарит научного руководителя Колоколова А.А. за внимание и поддержку при выполнении данной работы, а также Ягофарову Д.И. и Тюрюмова А.Н. за сотрудничество.
Постановки задач и их сложность
Приведем постановку задачи выполнимости логической формулы. Пусть даны логические переменные xi,x2,...,xn, которые могут принимать только два значения: истина или лооюъ. Литералом называется либо переменная Xj (позитивный литерал), либо ее отрицание Xj (негативный литерал). Литерал Xj принимает значение истина в том и только в том случае, если переменная Xj принимает значение лооюъ.
Рассмотрим логическую формулу F в конъюктивной нормальной форме (КНФ), т. е. представляющую собой конъюнкцию скобок (формул) Сі, С 2,..., Ст, каждая из которых является дизъюнкцией литералов. Задача выполнимости состоит в том, чтобы установить, является ли данная формула истинной при каком-нибудь наборе значений переменных. Данная задача является первой, для которой была доказана АГР-полнота [50]. В дальнейшем, будем говорить, что формула F выполнима, если существует такой набор значений переменных. В противном случае формулу называют невыполнимой.
Обобщениями задачи выполнимости являются задачи максимальной и минимальной выполнимости. Пусть скобки Сі,..., Ст имеют неотрицательные веса С\,..., ст. Задача максимальной (минимальной) выполнимости состоит в том, чтобы найти такой набор значений переменных, при котором суммарный вес всех выполненных скобок будет наибольшим (наименьшим). Отметим, что при переходе от задачи выполнимости к задаче максимальной или минимальной выполнимости, сложность задачи возрастает.
Поскольку исследуемые в работе задачи являются iVP-трудными, то наряду с разработкой полиномиальных приближенных алгоритмов решения одним из направлений исследования задач является выявление полиномиально разрешимых подклассов [56, 66]. Приведем наиболее известные из них.
Если в рассмотренных задачах каждая скобка содержит не более к литералов, то они называются задачами -выполнимости и максимальной (минимальной) fc-выполнимости соответственно. Известно, что задача 2-выполнимости является полиномиально разрешимой [50], а задачи максимальной и минимальной / -выполнимости - iVP-трудными даже в случае к = 2.
Если каждая скобка логической формулы содержит не более одного позитивного литерала, то такая формула называется хорновской. Задача выполнимости с хорновской формулой является полиномиально разрешимой [54, 83], а задачи максимальной и минимальной выполнимости -iVP-трудными. В работах [40, 45 - 48, 75, 85, 86] описываются различные классы формул, для которых задача выполнимости также полиномиально разрешима. В диссертации установлены свойства L-структуры многогранников задач максимальной и минимальной выполнимости. Доказано, что многогранник задачи максимальной выполнимости имеет альтернирующую L-структуру, а верхняя оценка мощности дробных комплексов многогранника задачи минимальной выполнимости является линейной функцией от числа скобок данной логической формулы. Рассмотрены лексикографические постановки задач максимальной и минимальной выполнимости в расширенном пространстве и лексикографическая задача выполнимости. Исследована L-структура этих задач для построенных семейств логических формул. Выделены семейства задач, мощности L-накрытий которых растут экспоненциально с увеличением числа переменных в формулах.
Кроме того, на построенных семействах задач исследовались алгоритмы перебора L-классов, ветвей и границ (метод Лэнд и Дойг) и двойственные дробные алгоритмы отсечения. Показано, что число итераций первых двух алгоритмов на некоторых семействах экспоненциально зависит от размерности задач, в то время как для первого алгоритма Го-мори число итераций растет линейно. Разработаны алгоритмы точного и приближенного решения невзвешенной задачи максимальной выполнимости, основанные на использовании метода перебора L-классов, лексикографическом переборе векторов и локальном поиске. Проведены экспериментальные исследования эффективности этих алгоритмов.
Связь с другими задачами и некоторые приложения
Задачи выполнимости, максимальной и минимальной выполнимости находят применение в логике, теории графов, задачах теории расписания, планировании, проектировании и во многих других областях. Большое число приложений приведено в работе [66]. В данном разделе будут описаны некоторые задачи, связанные с выполнением логических условий.
Задача построения производственного расписания. В задачах теории расписаний обычно требуется составить расписание выполнения заданных работ (операций) при некоторых ограничениях на их выполнение и имеющиеся ресурсы.
В задаче построения производственного расписания (ПР) имеется некоторый набор операций, которые необходимо выполнить при наличии следующих ограничений. Для каждой операции і, і = 1,...,q, задано время, необходимое для ее выполнения - Pi, ранний момент времени начала операции i-r\, т. е. момент, раньше которого операция г не может начаться и поздний момент окончания г -й операции, т. е. момент, позже которого операция і не должна заканчиваться.
На множестве операций задан частичный порядок их выполнения, т. е. возможна ситуация, когда некоторая операция не может начать выполняться пока не закончится другая. Кроме того, какие-то операции не могут выполняться параллельно, например из-за ограничений по ресурсам. Требуется составить расписание выполнения всех операций, удовлетворяющее данным ограничениям. Через Si обозначим время начала выполнения операции і, г = 1,..., q. Введем булевы переменные Xi,t = 1, если Si t, О, если Si t, где значения t = 1,..., d соответствуют дискретным моментам времени в течение выполнения операций, причем в момент d все операции должны быть выполнены. Согласно этому определению Xitt = 1 означает, что операция і начинает выполняться в момент t или позже; Xitt = О, если операция і начинается до момента времени t.
Сформулируем задачу построения ПР как задачу выполнимости. Для этого нужно построить некоторую логическую формулу F, выполнимость которой требуется проверить. Первое множество скобок формулы F определяется из условий Хц =Ф Хц-1 = Хц V Xitt-i для любых і = 1,... ,q и t = 1,... ,d. Условие Xitt = Xitt i означает, что если операция і начинается не раньше момента t, то она начинается не раньше t — 1. Количество скобок первого типа равно d q. Второе множество состоит из q единичных скобок вида ХІ ГІ, г = 1,... ,q, которые соответствуют требованиям о ранних моментах времени начала каждой операции. Аналогично определим q единичных скобок вида хца{-Р1+1) г = 1,..., q, соответствующих требованиям о поздних моментах времени окончания каждой операции. Следующее множество скобок определяет частичный порядок, заданный на множестве операций. Пусть операция j не может начать выполняться пока не выполнена операция г, тогда этому ограничению соответствует скобка %i,t %j,t+pi = xi,t V Xjj+Pi для всех t = 0,...,d —Pi.
Наконец, последнее множество скобок получается следующим образом. Пусть операции і и j не могут выполняться одновременно. Это условие может возникать при ограниченности ресурсов, требуемых для выполнения этих операций. Для каждой такой пары операций имеем множество скобок {хц =Ф- xjtt+Pi) V (xjtt =» Xi,t+Pj) = xitt V xu V Xjj+pt V Xitt+Pj при t = 0,...,d —Pi.
Рассмотрим формулу F, являющуюся конъюнкцией всех перечисленных скобок. Легко показать, что допустимое расписание задачи существует тогда и только тогда, когда существует набор значений логических переменных, при котором формула F выполнена.
Задача о наименьшем вершинном покрытии. Рассмотрим невзвешенную задачу минимальной выполнимости и задачу о наименьшем вершинном покрытии в следующей постановке. Дан неориентированный граф G = ІУ,Е). Требуется найти минимальное по мощности подмножество V множества V, такое что для каждого ребра (и, v) Є Е выполняется и Є V либо v Є V.
В работе [76] установлена связь этой задачи с задачей минимальной выполнимости. Пусть / - некоторая индивидуальная задача минимальной выполнимости, Сі = {Сі,..., Ст} - множество скобок данной формулы, Xi = {х\,..., хп} - множество логических переменных. Построим вспомогательный граф Gi = (V/, Е{) для задачи I следующим образом. Каждой скобке из С/ соответствует одна вершина графа. Пара вершин Vi, Vj Є Vi смежна тогда и только тогда, когда для соответствующих скобок СІ и Cj существует переменная х Є Xj, входящая в Q без отрицания, а в Cj - с отрицанием или наоборот.
Очевидно, что для пары скобок Ci,Cj, i,j = 1,...,т, которым соответствуют смежные вершины во вспомогательном графе, не существует набора значений логических переменных, при котором обе скобки будут невыполненными. Это простое свойство графа позволило доказать [76], что для любого набора значений переменных, выполняющего к скобок, можно построить вершинное покрытие мощности к во вспомогательном графе. И наоборот, для любого вершинного покрытия мощности к можно найти набор значений переменных, выполняющий к скобок. Из этого следует, что оптимальные значения целевой функции задачи минимальной выполнимости и задачи наименьшего вершинного покрытия для вспомогательного графа совпадают.
Более того, каждому графу G = (V, Е) можно поставить в соответствие формулу F в КНФ. Для этого вершине vi Є V сопоставляем скобку Cj, ребру (vi,Vj) Є Е - переменную хц, причем скобка СІ содержит эту переменную без отрицания, a Cj - с отрицанием, i,j = 1,...,m. При таком сведении длина скобки СІ (число входящих литералов) равна степени вершины Vi.
Легко заметить, что граф G является вспомогательным для задачи минимальной выполнимости с формулой F. Следовательно, оптимальные значения целевых функций соответствующих индивидуальных задач о наименьшем покрытии и минимальной выполнимости совпадают.
Задачи проектирования. При проектировании различных изделий некоторые ограничения, могут описываться с помощью логических условий. Следовательно, требование об их непротиворечивости равносильно выполнимости соответствующей логической формулы. Если данные ограничения несовместны, перед проектировщиком может ставиться задача проектирования изделия, максимально удовлетворяющего некоторым параметрам. Такая задача является аналогом задачи максимальной выполнимости.
L-структура многогранников задач максимальной и минимальной выполнимости
В некоторых работах задачи выполнимости и максимальной выполнимости формулируются как задачи целочисленного линейного программирования (ЦЛП) [1, 4, 7, 18, 25, 39, 49, 64, 65, 66, 72]. Рассмотрим сначала постановку задачи выполнимости.
Таким образом, задача выполнимости сводится к отысканию некоторой целочисленной точки многогранника М или доказательству того, что ее не существует. При этом можно сформулировать задачу выполнимости как задачу поиска лексикографически максимального допустимого решения множества (2.4)-(2.6): найти lexmax(МП Zn). (2.7)
В такой постановке в любом допустимом целочисленном решении Zi = 1 только в том случае, когда формула С; выполнена. Таким образом, оптимальное значение целевой функции равно наибольшему суммарному весу выполненных скобок. Iі
В некоторых работах, например в [64], рассматривают задачу минимизации суммарного веса невыполненных скобок, которая эквивалентна задаче максимальной выполнимости. При этом получается похожая модель ЦЛП.
Здесь &г- - длина скобки СІ, т. е. число входящих в нее литералов. Легко показать, что z\ = 0 только в том случае, когда формула СІ не выполнена. Таким образом, оптимальное значение целевой функции равно наименьшему суммарному весу выполненных скобок. Через Q обозначим многогранник, задаваемый системой ограничений (2.19)-(2.21). Далее будет проведен анализ L-структуры многогранников задач максимальной и минимальности выполнимости. Такие исследования задач ЦЛП интересны как в теоретическом плане, так и могут оказаться полезными при разработке алгоритмов их решения. Ранее было доказано, что альтернирующей Ігструктурой обладают многогранники задач об упаковке и покрытии множеств, задачи стандартизации и др. [17]. Оказалось, что этот же факт имеет место и для многогранников Р и Р задачи максимальной выполнимости. Пусть в задачах (2.8)-(2.12) и (2.18)-(2.22) переменные упорядочены следующим образом: 2/11 ) Уп, z\, ) zm. При этом предположении нами доказаны следующие утверждения об L-структуре соответствующих многогранников.
Теорема 2.1 Многогранник Р задачи максимальной выполнимости (2.8)-(2.12) имеет альтернирующую L-структуру.
Доказательство. Легко показать, что система линейных ограничений (2.9)-(2.11) обладает следующими свойствами:
a) Если Z{ = 0 для любого і = 1,..., т, то любое присвоение переменным уі,..., уп булевых значений дает допустимую точку многогранника Р.
b) Пусть х = (у[,..., у п; z[,..., z m) некоторая точка многогранника Р, у которой все координаты y j целые и значение некоторой переменной z\ - дробное. Тогда можно округлить значение z[ произвольно (вверх или вниз) и в обоих случаях получится допустимая точка. В случае нескольких дробных значений переменных Zi процедуру округления можно применить для каждой из них, в результате чего получится целая допустимая точка многогранника.
Таким образом, лексикографически максимальная и минимальная точки являются целочисленными. Теорема доказана. Из альтернируемости следует, что любой дробный І класс многогранника Р содержит точку с координатами из множества {0,,1}. Легко показать, что этим же свойством обладает и многогранник М задачи выполнимости, что использовалось при разработке алгоритма перебора L-классов [25].
Заметим, что L-структура множества зависит от упорядочения пе ременных. Существуют примеры, когда изменение порядка переменных приводит либо к увеличению, либо к уменьшению мощностей комплексов дробных L-классов многогранников задач. Далее приводится соответствующий пример задачи максимальной выполнимости.
Пусть в установленном порядке переменных среди Zj, г = 1,...,т, сначала идут переменные, соответствующие какой-либо невыполнимой формуле, тогда если их значения равны 1, то все такие допустимые точки многогранника будут дробными. После этого нетрудно посчитать число дробных L-классов, их число растет экспоненциально с увеличением числа переменных.
Таким образом, при разработке алгоритмов, основанных на использовании релаксационных множеств, одним из важных вопросов является определение порядка переменных, что может существенно влиять на их эффективность. В дальнейшем при разработке алгоритмов решения задачи максимальной выполнимости нами использовались процедуры упорядочения логических переменных.
Далее рассмотрим задачу минимальной выполнимости. Легко построить пример логической формулы, для которой многогранник Q за-, дачи, определяемый системой (2.19)-(2.21) не имеет альтернирующей L-структуры. Однако, удалось получить верхнюю оценку мощности любого его комплекса, представляющую собой линейную функцию от числа скобок логической формулы.
Таким образом, можно посчитать наибольшее возможное число классов, составляющих L-комплекс: т классов с рангами от п + 1 до п + т и один класс ранга не больше п. Значит, в любом L-комплексе содержится не более т + 1 элемента. Теорема доказана. Замечание 2. Данная оценка является достижимой. Можно показать, что многогранник задачи минимальной выполнимости с формулой вида F = (xi V х2)(х3 V хА)... (жп_і V хп) содержит L-комплекс мощности тп + 1. Таким образом, L-структура многогранника Q задачи минимальной выполнимости "хуже", чем у многогранника Р задачи максимальной выполнимости, т.к. Q содержит более мощные -L-комплексы, которые могут оказывать влияние на работу алгоритмов.
В п. 1.3 отмечалась актуальность исследования задач ЦЛП с точки зрения мощности их L-накрытия, которая существенно влияет на работу многих алгоритмов целочисленного программирования. В данном разделе строятся семейства логических формул специального вида, записанные в конъюнктивной нормальной форме. В дальнейшем на основе этих семейств исследуются задачи выполнимости, максимальной и минимальной выполнимости. Выделены семейства задач, у которых мощности дробных накрытий растут экспоненциально с увеличением числа переменных в формуле.
При построении семейств для краткости через C(i,j) будем обозначать формулу (ХІ V Xj)(Xi V Xj)(Xi V Xj)(Xi V Xj). Семейство SI. Пусть г - натуральное число. Рассмотрим Fi = Сі Л ... Л Сг Л С, ГДЄ Q = (ХЗІ-2 V Жзі_і)(3і-2 V хзї)(х3і-і V хЗІ) для і = 1,...,г и C = C(3r + l,3r + 2). Семейство S2. Пусть F2 = Сі Л ... Л Сг Л С, где d = (ж3»-2 v ЕЗ -І)(ЕЗІ-2 V хЗІ) Л Л (ЯЗІ-І V ЇЗІ) для г = 1,... ,г и С = С(3г + 1,3г + 2) . Семейство S3. Рассмотрим F3 = Сі Л.. .ЛСГЛС, где Сг- = (:&3 -2V:r3i-i)(33i-2Va;3,-)A Л (ж3г_1 V 3) для г = 1,..., г и С = С(3г + 1, Зг + 2). Для наглядности можно выписать матрицы ограничений задачи выполнимости с формулами из данных семейств. Матрицы семейств S1 - S3 имеют блочно-диагональную структуру. Ниже выписана матрица задачи для семейства S1:
Анализ некоторых алгоритмов целочисленного программирования на основе L-разбиения
В данном разделе проводится анализ алгоритмов перебора L-классов, ветвей и границ (метод Лэнд и Дойг) и двойственного дробного алгоритма отсечения Гомори при решении специально построенных семейств задач максимальной и минимальной выполнимости.
Алгоритм перебора L-классов [17] был предложен для решения общей задачи целочисленного программирования в следующей постановке: f{x)- max,xe{QnZn), (3.1) где О - замкнутое, ограниченное множество в Rn и f(x) - непрерывная функция. Данный метод основан на L-разбиении пространства Лп, которое было определено в главе 1.
Рассмотрим идею метода перебора L-классов для задачи (3.1). Основной шаг базового алгоритма (далее он обозначается LC) заключается в переходе от одного L-класса релаксационного множества задачи Г2 к следующему за ним в порядке лексикографического убывания с учетом рекордного значения целевой функции f(x). В процессе перебора алгоритм порождает последовательность S точек х Є Q, обладающую свойствами: 2) все точки х принадлежат различным L-классам; 3) если множество Q Г) Zn непусто, то последовательность S содержит подпоследовательность целых точек Q = {z tk\k = 1,..., } такую, что f(z{tk+i)} /(г( )), к = 1,..., q - 1 (в случае q 2).
Процесс перебора L-классов начинается с лексикографически максимальной точки а 1) Є SX Текущие точки х строятся посредством нахождения лексикографического максимума вспомогательных подзадач непрерывной оптимизации. Поиск лексикографического максимума этих подзадач может быть осуществлен с помощью последовательной оптимизации [13]. В случае, когда Q является выпуклым многогранным множеством, это можно выполнить, например, с помощью лексикографического двойственного симплекс-метода. Алгоритм завершает работу, когда не удается найти представителя очередного L-класса. В случае, если задача разрешима, лучшее из найденных целочисленных решений является оптимальным. Так как множество О. ограничено, то за конечное число шагов либо находится оптимальное решение, либо устанавливается, что его не существует.
Процесс перебора L-классов можно проиллюстрировать с помощью ленты, разделенной на ячейки (рис. 3.1). Пусть Q./L = {Vi,...,V\},_ А = 0,/L \,Vi - Vi+i,i = 1,..., A — 1. Первой ячейке соответствует L-класс Vi, второй - V2 и т.д. Алгоритм LC можно рассматривать как процедуру просмотра ячеек ленты справа налево. Будем считать, что на итерации t ячейка с номером к просмотрена, если х Є Vfc. При этом каждая ячейка ленты просматривается не более одного раза (многие ячейки могут пропускаться из-за ограничения по рекорду). z zl Vi КУ У Рис. 3.1: Процесс перебора L-классов Прежде чем описывать алгоритм LC определим & = inf{\ f(z ) - f(z") : z, z Є(ПП Zn) и /( ) ф /(/)}. Так как О, ограничено, то 5 0. Выберем 0 5 6. Алгоритм LC
Шаг 0. Решить задачу непрерывной оптимизации, получающуюся из (3.1) путем исключения условия целочисленности. Если она не имеет допустимых решений, или ее решение целочисленное, процесс завершается. Иначе за начальное значение рекорда взять гее = -оо и перейти на шаг 1. Шаг 1. Найти х = lexmax Q. Возможны два случая. 1.1 Если х Є Z", вычислить новый рекорд rec = f{x ), положить р — п + 1,х = х и перейти на шаг 3. 1.2 В случае х . Zn перейти на шаг 2. Шаг 2. Поиск следующего L-класса ("ход вниз"). Пусть х" = х . Найти р = min{j : x j Ф [x j\,j = 1,...,n}. Решить подзадачу: найти х = Іехтах{х Є Q : f(x) rec + 5, %i = Я і) Яр—і = %p—1 т — L pJj Возможны следующие случаи. 2.1 Если эта подзадача не имеет решений ир=1, то на шаг 4. 2.2 Если подзадача не имеет решений и р 1, то на шаг 3. 2.3 Если подзадача имеет решение х Є Zn, обновить рекорд rec = f(x ), положить р = п + 1, х" — х , перейти на шаг 3. 2.4 Если х Z", то на шаг 2. Шаг 3. Поиск следующего L-класса ("ход вверх"). Положить р = р — 1. Решить подзадачу: найти х = Іехтах{х Є Q : /(#). rec + , Шаг 4. Процесс решения завершается. Лучшее найденное целочисленное решение является оптимальным. Если такого нет, исходная задача не имеет решений. Шаг 0 и шаг 1 в алгоритме являются предварительными и выполняются один раз. Основные итерации алгоритма осуществляются на шагах 2иЗ. Заметим, что в силу непрерывности функции f(x) множество О Г) {х : f{x) гее + 6} является замкнутым. В силу ограниченности множества О, данный алгоритм является конечным. Кроме того, для задачи ЦЛП с целочисленными исходными данными параметр 5 можно полагать равным 1. Отметим, что ряд результатов данной главы получен для логических формул, описанных в формулировках теорем 2.3 и 2.4. Напомним, что в теореме 2.3 рассматриваются формулы F = С\ А ... Л Ст Л С", где С - некоторая невыполнимая формула, причем множества переменных, входящих в Ci,..., Сг, С, попарно не пересекаются, г = г(п) - полином степени не меньше 1 от п, г(п) — +оо при п — +оо. Кроме того, каждая формула Сі может быть выполнена не менее, чем двумя различными наборами значений переменных. В теореме 2.4 рассматриваются формулы F = С\ Л ... Л Сг, где все СІ не выполнимы и оптимальное решение любой задачи максимальной выполнимости формулы СІ достигается более, чем на одном наборе значений переменных. В результате исследования алгоритма перебора L-классов LC для задачи максимальной выполнимости была получена следующая Теорема 3.1 Если семейство логических формул удовлетворяет условиям теорем 2.3 или 2.4, то число итераций алгоритма LC при решении задач максимальной выполнимости для данного семейства растет экспоненциально с увеличением числа переменных в формуле. Доказательство. 1) Пусть F = С\ А ... Л Сг Л С удовлетворяет условиям теоремы 2.3. Обозначим через р текущее рекордное значение целевой функции задачи максимальной выполнимости с формулой F. Предположим, что в некоторый момент работы алгоритма было найдено решение, для которого р = т— 1. Покажем, что на доказательство того, что данное решение является оптимальным, требуется экспоненциальное от размерности задачи число итераций алгоритма LC.
При решении задачи максимальной выполнимости алгоритмом LC на шагах 2 и 3 будут получаться оптимальные решения задач линейного программирования (ЛП) следующего вида: х = (a , ...,xN, 1/2,..., 1/2; 1,...,1), (3.26) v v \с\ т где XI,...,XN - переменные, соответствующие формулам Сі Л ... Л Сг. Никакая из точек такого вида не является целочисленной и все являются представителями различных дробных L-классов, при этом значение целевой функции равно га. Так как N(Ci) 2 для любого і, то существует не менее 2Г таких векторов, а значит по крайней мере 2Г задач ЛП будет решено алгоритмом LC с рекордным значением целевой функции равным т—1. 2) Если F = С\ А ... Л Сг удовлетворяет условиям теоремы 2.4, то, проводя рассуждения, аналогичные пункту 1), можно построить оценку числа итераций для алгоритма LC, которая растет экспоненциально с увеличением числа переменных. Теорема доказана. Кроме того, алгоритм LC исследовался для задачи минимальной выполнимости. Показано, что для задач семейства S7 имеет место аналогичный теореме 3.1 результат. Утверждение 3.1 Число итераций алгоритма LC для задачи минимальной выполнимости формул семейства S7 растет экспоненциально с увеличением числа переменных. Подсчет числа итераций указанного алгоритма для данного семейства проводится непосредственно путем построения последовательности L-классов, получаемых в процессе решения задачи.
Метод ветвей и границ относится к группе комбинаторных методов дискретного программирования. Центральную идею комбинаторных методов составляет замена полного перебора всех допустимых решений их частичным направленным перебором. Впервые метод ветвей и границ был предложен в работе Лэнд и Дойг для решения задачи целочисленного линейного программирования [26].
