Содержание к диссертации
Введение
ГЛАВА I. Дескриптивная теория локальных алгоритмов 32
1.1. О локальных алгоритмах вычисления информации . 32
1.2. Локальные алгоритмы решения задач дискретной оптимизации 37
1.3. Локальный декомпозиционный алгоритм ABT решения задач дискретной оптимизации с блочно-древовидной структурой . 45
1.4. Локальный алгоритм ABT для задач дискретной оптимизации, характеризующихся блочно-древовидной структурой с дополнительными ограничениями . 51
1.5. О связи локальных алгоритмов с другими алгоритмами дискретной оптимизации . 54
1.6. Распространение локального алгоритма на другие блочные структуры 58
Выводы по главе I 59
ГЛАВА II. Локальные элиминационные алгоритмы 61
2.1. Основные определения . 61
2.2. Локальные элиминационные алгоритмы в задачах оптимизации . 62
2.3. Локальные элиминационные алгоритмы решения дискретных задач информатики 96
Выводы по главе II 114
ГЛАВА III. Разреженные матрицы и теоретико-графовые подходы к выделению блочных структур 116
3.1. Разреженные матрицы и выделение блочной структуры 116
3.2. Свойства матриц с блочно-древовидной структурой 121
3.3. Древовидная декомпозиция и древовидная ширина 126
Выводы по главе III 150
ГЛАВА IV. Оценки эффективности и условия целесообразности применения локальных алгоритмов 152
4.1. О сложности алгоритмов решения задач дискретной оптимизации, общие понятия о сложности алгоритмов 152
4.2. Оценки сложности алгоритмов дискретной оптимизации 155
4.3. Оценки эффективности локального алгоритма решения блочно-древовидных задач дискретной оптимизации 157
4.4. О целесообразности использования локального алгоритма для решения задач дискретной оптимизации с блочно-древовидной структурой 164
4.5. Случай блочно-древовидной структуры с дополнительными ограничениями 171
Выводы по главе IV 182
ГЛАВА V. Средние значения оценки эффективности локального алгоритма 184
5.1. Средние оценки эффективности локального алгоритма для блочно-древовидных задач дискретной оптимизации 184
5.2. Асимптотическая средняя оценка эффективности локального алгоритма для задач с блочно-древовидной структурой и ограниченной связностью 199
5.3. Средняя оценка эффективности локального алгоритма для небулева случая 206
5.4. Оценка эффективности локального алгоритма в блочном случае с дополнительными ограничениями одновариантного типа 208
5.5. Средняя оценка эффективности локального алгоритма на классе блочных задач в более общем случае 212
5.6. Асимптотические средние оценки эффективности локального алгоритма для блочно-древовидной структуры с дополнительными ограничениями многовариантного типа 215
5.7. Асимптотические средние оценки эффективности локального алгоритма для блочно-древовидной структуры с дополнительными ограниченими одновариантного типа 225
5.8. Средняя оценка эффективности локального алгоритма на классе всех блочно-древовидных структур с дополнительными ограничениями одновариантного типа 231
5.9. Средние оценки эффективности локального алгоритма при решении G-блочных задач дискретной оптимизации 234
Выводы по главе V 236
ГЛАВА VI. Анализ блочных структур в случаях наилучшего и наихудшего поведения локального алгоритма 239
6.1. Оценка максимального и минимального значений оценки эффективности локального алгоритма для задач дискретной оптимизации с блочно-древовидной структурой без дополнительных ограничений 239
6.2. «Наихудшее» и «наилучшее» поведение локального алгоритма на
классе блочно-древовидных структур с дополнительными ограниче-
ниями многократного выбора 250
Выводы по главе VI 269
ГЛАВА VII. Вычислительные аспекты реализации локального алгоритма 271
7.1. «Оценочный» эксперимент для локального алгоритма 271
7.2. Эксперимент для локального алгоритма в сочетании с алгоритмами пакета «Диспро» 280
7.3. Приближенные версии локального алгоритма 286
7.4. Локальный элиминационный алгоритм и параллельные вычисления 287
Выводы по главе VII 295
Заключение 297
Литература 307
Приложение
- Локальный декомпозиционный алгоритм ABT решения задач дискретной оптимизации с блочно-древовидной структурой
- Локальные элиминационные алгоритмы решения дискретных задач информатики
- Древовидная декомпозиция и древовидная ширина
- Оценки эффективности локального алгоритма решения блочно-древовидных задач дискретной оптимизации
Введение к работе
Актуальность темы.
Методы исследования дискретных структур играют все более важную роль в современных приложениях математики.
Использование моделей и алгоритмов дискретной оптимизации (ДО) позволяет решать многие практические задачи, такие, как задачи теории расписаний, оптимизации на сетях, маршрутизации трафика в коммуникационных сетях, задачи размещения экономических объектов, задачи оптимизации автоматизированных систем планирования ресурсов (ERP), задачи логистики, в частности, оптимизацию цепочек предложения (Supply Chain Management), доказательство теорем, задачи искусственного интеллекта и робототехники и т. п. Это обусловлено тем, что дискретные оптимизационные модели адекватно отражают нелинейные зависимости, неделимость объектов, учитывают ограничения логического типа и всевозможные технологические, в том числе и имеющие качественный характер, требования. К сожалению, большинство интересных задач ДО являются NP-трудными и решение их в худшем случае может требовать построения дерева поиска решений экспоненциального размера. Многие практические задачи ДО содержат огромное число переменных и/или ограничений, что создает сложности при попытке решения этих задач с помощью современных решателей.
А. Н. Колмогоров отмечает [2, с.28]: «Весьма вероятно, что с развитием современной вычислительной техники будет понято, что в очень многих случаях разумно изучение реальных явлений вести, избегая промежуточный этап их стилизации в духе представлений математики бесконечного и непрерывного, переходя прямо к дискретным моделям. Особенно это относится к изучению сложно организованных систем, способных перерабатывать информацию».
В настоящее время среди наиболее перспективных направлений исследований в дискретной оптимизации можно выделить следующие подходы:
1) разработка эффективных вычислительных алгоритмов (как точных, так и приближенных) для решения задач ДО.
2) поиск специальных классов задач ДО, на которых хорошо работают те или иные алгоритмы;
3) теоретический анализ сложности и трудоемкости алгоритмов ДО.
4) разработка и исследование алгоритмов ДО с эффективным распараллеливанием вычислений.
Остановимся подробнее на указанных направлениях исследований. В теории дискретной оптимизации разработано большое число алгоритмов, которые можно разбить на следующие классы:
1) комбинаторные методы, в том числе:
1.1) методы ветвей и границ, методы ветвления и отсечения;
1.2) локальные алгоритмы Ю. И. Журавлева [2];
1.3) метод последовательного анализа и отсеивания вариантов, предложенный В. С. Михалевичем и Н.З. Шором [3];
1.4) последовательностные схемы В. А. Емеличева [4];
1.5) аппроксимационно-комбинаторный метод [5];
1.6) метод динамического программирования 6;
2) приближенные методы;
3) эвристические подходы (табу, генетические алгоритмы, метод отжига (simulated annealing) и др.), мета-эвристические методы (см. [11]).
4) методы глобальной оптимизации для решения задач смешанного нелинейного целочисленного программирования [8, 9].
5) декомпозиционные методы.
6) другие методы, в том числе методы отсечения; теоретико-групповые методы; гибридные методы [9].
Следует особо выделить весьма общие и эффективные при решении ряда конкретных прикладных задач дискретной оптимизации схемы, такие как метод последовательного конструирования, анализа и отсева вариантов В. С. Михалевича [3], общая схема глобального равновесного поиска (И. В. Сергиенко, В. П. Шило [10]), последовательностные схемы В. А. Емеличева [4], локальные алгоритмы Ю. И. Журавлева [2].
Хотя возможности построения полиномиальных точных алгоритмов решения задач дискретной оптимизации общего вида и представляются сомнительными [11], тем не менее, в последнее время наблюдается потребность в построении и анализе точных алгоритмов, существенно более быстрых, чем полный перебор, но пока еще не полиномиальных (так называемых супер-полиномиальных алгоритмов, с помощью которых находятся оптимальные решения NP-полных задач [12]).
Не останавливаясь подробно на приближенных методах решения задач дискретной оптимизации, заметим, тем не менее, что в основе многих приближенных методов лежит идея локального поиска. Достаточно эффективными показали себя такие приближенные алгоритмы локального поиска, как метод глобального равновесного поиска [11] – развитие метода вектора спада, разработанного И. В. Сергиенко и его учениками 13, локально-стохастические алгоритмы [14-16]. Результаты многочисленных вычислительных экспериментов для множества задач дискретной оптимизации с использованием алгоритма глобального равновесного поиска доказывают перспективность этого метода [11].
Общая теория локальных алгоритмов для решения ряда важных задач дискретной математики была развита Ю. И. Журавлевым [2]. Идея локального алгоритма основана на введении понятия «близости», на основе которого определяется окрестность элемента, т. е. множество элементов, «близких» к данному. Локальный алгоритм на каждом шаге изучает окрестности элементов (а не все элементы множества) и накапливает о них информацию, которая затем используется на последующих шагах алгоритма. Отметим, что в методе вектора спада и локально-стохастическом алгоритме используются окрестности решений задачи ДО. Алгоритмы локального поиска (называемые по-другому алгоритмами с окрестностями (neighborhood search algorithms)) [17] на каждой итерации находят улучшенное решение путем поиска в окрестности текущего решения. Эффективность подобных методов существенно зависит от способа выбора окрестности решения. К подходам, использующим локальный поиск, относятся методы отжига, табу, меметические алгоритмы. Дальнейшее развитие методы локального поиска получили в метаэвристических методах [16], [18], в которых локальный поиск используется совместно с эвристическими алгоритмами, такими как, например, алгоритм муравьиных колоний [19] и генетический алгоритм [20].
Теоретические основы для ускорения процесса решения сложных задач ДО предложены в [10], где описана РЕСТАРТ-технология, основанная на использовании РЕСТАРТ-распределения и РЕСТАРТ-критерия останова алгоритма.
В последнее время интересные результаты были получены в теории удовлетворения ограничений (Constraint Satisfaction) [21], находящейся на пересечении искусственного интеллекта и информатики.
Одним из наиболее перспективных подходов к решению задач дискретной оптимизации является построение гибридных (комбинированных) методов, основанных на сочетании и взаимодействии в рамках нового метода двух или более известных методов. Важные теоретические исследования, служащие основой для дальнейшего развития гибридных алгоритмов [9], проведены в известных работах Ю. И. Журавлева 22.
Ряд подходов из теории удовлетворения ограничений [21, 64] может быть использован при создании гибридных алгоритмов ДО и глобальной оптимизации [7].
Поскольку разработка эффективных точных алгоритмов для решения задач дискретной оптимизации общего вида, как отмечено выше, представляется сомнительной, то имеет смысл исследовать более узкие классы задач и строить более эффективные методы, основанные на изучении особенностей частных подклассов задач. Следует отметить, что успехи, достигнутые к настоящему времени в теории и практике ДО достаточно часто были связаны именно со специальной структурой задач ДО. Действительно, хорошие результаты получены при решении задач ДО, обладающих специальной структурой (так, методы отсечения успешно применялись при решении задач о покрытии, последовательностные схемы В. А. Емеличева особенно хорошо работают при решении задач о размещении, высокая эффективность метода ветвей и границ достигается при решении задач с ограничениями специального вида, например, многократного выбора [23]), градиентные алгоритмы хорошо работают на матроидах [24] и т. д.
Отметим существование некоего «принципа неопределенности» в ДО чем более общий класс задач ДО мы исследуем (и разрабатываем для таких задач вычислительные алгоритмы), тем меньше шансов получить при этом большой эффект, в то же время рассмотрение чрезмерно узких, специальных классов задач ДО позволяет разработать высокоэффективные (но и узко специализированные) вычислительные алгоритмы, однако затраченные на их разработку усилия не окупаются вполне в связи с узостью класса задач. Таким образом, при выборе объекта исследования в ДО есть смысл придерживаться «золотой середины», т. е. стремиться к выбору достаточно широкого и практически важного класса задач ДО, обладающего специальной структурой.
Понимание принципиального характера трудности решения задач дискретной оптимизации стимулировало интенсивное развитие теории сложности 25 28. Одной из наиболее важных теоретических проблем в теории сложности является известная проблема «P=NP?». В теории сложности используются в числе прочих понятия временнй и емкостной сложности алгоритма. Грубо говоря, под временнй сложностью понимается время работы алгоритма (оцениваемое числом шагов), под емкостной сложностью объем памяти, необходимый алгоритму для решения задачи.
Центральная теоретико-методологическая проблема дискретной математики решение вопроса о возможности исключения полного перебора при решении задач на дискретных структурах и, тем самым, исключения экспоненциального размера дерева поиска.
Теория сложности показала, что общность и эффективность противоречивые требования к алгоритму. Трудоемкость решения класса задач обычно снижается, если разбить этот класс на подклассы и использовать для решения задач из подклассов алгоритмы, учитывающие их специфику; это подтверждает справедливость тезиса, отмеченного выше.
Отметим работы В. А. Емеличева [29], в которых сложность решения задачи линейного программирования оценивается косвенно, путем нахождения диаметра многогранника допустимых решений.
В связи о вышесказанным приобретает особую актуальность разработка в ДО декомпозиционных подходов 30 40.
Как известно, метод декомпозиции впервые был использован для решения задач смешанного целочисленного программирования в 41, позднее были развиты и другие методы декомпозиции. Принцип декомпозиции Данцига-Вулфа для задач ЛП имеет аналог в целочисленном программировании [40]. Этот подход использует мастер-задачу целочисленного ЛП (ЦЛП), которая неявно решает задачу ЦЛП с большим числом переменных с помощью процедуры построения столбцов задачи ЦЛП, известную как алгоритм ветвей и оценок (branch-and-price) [42], использование которого позволило решить в последние годы большие задачи ДО.
Задачи ДО и, в частности, задачи ЦП с блочной структурой возникают естественным образом во многих приложениях [38], [43]. При этом блоки обычно представляют в модели отдельные объекты, либо решения в подразделениях фирмы, в техническом устройстве, либо отвечают периоду времени. Эти блоки связаны между собой ограничениями, отражающими необходимость польльзования одними и теми же ресурсами или отражающими взаимосвязь решений для всей компании, технического процесса или периода планирования. В качестве примеров можно привести составление расписаний для транспортных средств [44], задачи в области телекоммуникаций [43], [45], в том числе задачи оптимального назначения радиочастот [46], задачи стохастического целочисленного программирования [47]. Блочную структуру имеют задачи оптимизации многопродуктовых потоков [48]. Следует упомянуть также множественную задачу о ранце [49], блоки которой являются задачами о ранце, а связывающие блоки ограничения являются неравенствами упаковки и разбиения множества. Задачи ЦЛП блочного типа были получены в результате моделирования системы туризма [65].
Перспективными декомпозиционными методами, использующими разреженность матрицы ограничений задач ДО, представляются локальные элиминационные алгоритмы (ЛЭА) [66], включающие локальные алгоритмы декомпозиции [62], [67], алгоритмы несериального динамического программирования (НСДП) [50], [69], алгоритмы сегментной элиминации [51]. Для выделения специальных структур задач ДО представляются перспективными такие графовые декомпозиционные подходы, как методы древовидной декомпозиции (ДД) [52], [70]. Несмотря на обширную библиографию по этой тематике за рубежом, в отечественной литературе публикаций по ДД практически нет (можно отметить лишь близкие по тематике работы по локальным алгоритмам декомпозиции [67], а также обзор [70]). Важность и актуальность указанных подходов в ДО обусловлены результатами Courcelle [53], Arnborg et al. [54], доказавших, что ряд NP-трудных задач, поставленных в монадической логике второго порядка, могут быть решены за полиномиальное время с помощью методов динамического программирования на графах, описывающих структуру задачи ДО, имеющих ограниченную древовидную ширину. Методы ДД показали свою эффективность при решении задач ДО: задач кольцевой маршрутизации, задачи коммивояжера [55], задачи оптимального назначения радиочастот [46].
Среди блочных структур особо выделим блочно-древовидную структуру, частным случаем которой является «лестничная» или квазиблочная структура.
Одним из первых классов больших разреженных задач линейного программирования, которые начал изучать Dantzig, был класс квазиблочных задач ЛП для динамического планирования [56]. Другие примеры квазиблочных задач ЛП для многоэтапного планирования, составления расписаний, назначений и многоэтапного структурного проектирования содержатся во множестве тестовых квазиблочных задач, опубликованных Ho & Loute [57]. Квазиблочную структуру имеют задачи оптимального резервирования гостиничных номеров 82, аналогичные последним темпоральные задачи о ранце [58], получившие в последнее время применение при решении задач предварительного резервирования вычислительных ресурсов в Grid Computing, задачи линейного динамического программирования [59], некоторые задачи управления трудовыми ресурсами 60, динамические модели экономики, учитывающие в явном виде фактор времени 61, задачи управления в иерархических (обычно древовидных) структурах, сетевые задачи, задачи многоэтапного стохастического программирования.
Для решения квазиблочных задач ДО достаточно эффективен локальный алгоритм 62, 67, 71 81, использующий специфику квазиблочной матрицы ограничений и имеющий декомпозиционный характер, т.е. сводит решение исходной задачи ДО большой размерности к решению ряда задач меньших размерностей, которые уже можно решить известными методами, т.е. с помощью имеющихся решателей.
Отметим, что локальный элиминационный алгоритм долгое время оставался чисто теоретическим алгоритмом. В 71 впервые приводятся результаты вычислительного эксперимента по решению задач ДО с помощью локального алгоритма. В 72 приводятся результаты исследования эффективности локального алгоритма для квазиблочных задач ДО, причем была показана слабая зависимость асимптотической средней оценки эффективности локального алгоритма от эффективности алгоритма ДО, решающего подзадачи для блоков. Это объясняется тем, что средняя оценка эффективности рассматривалась на множестве всех квазиблочных структур, но, как отмечалось в 63, локальные алгоритмы эффективны для задач с ограниченной связностью блоков.
Следует отметить, что вопрос об эффективности локального алгоритма исследован недостаточно полно как теоретически, так и экспериментально, поэтому представляет интерес экспериментальное исследование поведения локального алгоритма в сочетании с различными решателями ДО как точными, так и приближенными.
Цель работы. В связи с вышеизложенным основными целями диссертационной работы являются:
Разработка общей алгоритмической схемы локальных элиминационных алгоритмов для решения широкого класса разреженных задач ДО и из других областей прикладной математики.
Исследование возможностей распространения локального элиминационного алгоритма на различные классы задач ДО.
Использование ЛА совместно с методами древовидной декомпозиции.
Теоретическое и экспериментальное исследование эффективности локального элиминационного алгоритма, анализ и выделение классов блочных задач ДО, достаточно эффективно решаемых локальным элиминационным алгоритмом.
Исследование возможностей снижения перебора ЛЭА на основе использования релаксаций, селектора, распараллеливания вычислительного процесса.
На защиту выносятся следующие результаты:
Разработана общая алгоритмическая схема локальных элиминационных алгоритмов для решения широкого класса разреженных дискретных задач. Эти алгоритмы используют структуру дискретной задачи и вычисляют глобальную информацию на основе локальных вычислений, используя понятие «близости переменных», основанное на использовании топологических окрестностей переменных, отражающих структуру дискретной задачи. При этом дискретные задачи могут быть как задачами дискретной оптимизации, так и носить неоптимизационный характер: дискретные задачи удовлетворения ограничений и дискретные задачи обработки запросов в реляционных базах данных. Структура разреженных дискретных задач задается с помощью графового и гиперграфового представлений.
Введены и исследованы графовые структуры локального элиминационного алгоритма: элиминационное дерево, являющееся орграфом вычислительной процедуры локального элиминационного алгоритма и задающего информационные потоки; элиминационный процесс; элиминационные графы; элиминационная игра. Показано, что использование графовых структур позволяет рационально построить вычислительную схему локального элиминационного алгоритма.
Рассмотрены и проанализированы конкретные реализации общей схемы локального элиминационного алгоритма: локальные алгоритмы элиминации переменных, использующие в качестве структурного графа граф взаимосвязей переменных задачи; блочно-элиминационные локальные алгоритмы, учитывающие подобие окрестностей отдельных переменных; локальные алгоритмы, использующие древовидную структурную декомпозицию. Предложены локальные декомпозиционные алгоритмы решения задач с блочно-древовидной структурой. Рассмотрены особенности применения локальных алгоритмов с селектором для блочно-древовидных структур с дополнительными ограничениями многократного выбора. Предложен локальный элиминационный алгоритм, использующий древовидную структурную декомпозицию, являющуюся обобщением блочно-древовидной структуры.
Предложены и проанализированы оценки вычислительной сложности (оценки эффективности) локальных алгоритмов на блочно-древовидных структурах как с дополнительными ограничениями, так и без них (с селектором и без него), на основе их анализа проведено теоретическое исследование эффективности локального элиминационного алгоритма, анализ и выделение классов блочных задач ДО, достаточно эффективно решаемых локальным элиминационным алгоритмом.
Поставлен и решен вопрос о целесообразности изучения блочно-древовидных структур на основе исследования оценок эффективности. Получены достаточные условия, позволяющие исключить полный перебор при использовании блочно-древовидных структур.
Проведен анализ оценок эффективности локального алгоритма при решении блочно-древовидных задач дискретной оптимизации с дополнительными ограничениями многократного выбора. Показана целесообразность использования локального алгоритма при решении блочно-древовидных задач дискретной оптимизации с дополнительными ограничениями многократного выбора и без них. Получены достаточные условия целесообразность использования локального алгоритма при решении блочно-древовидных задач дискретной оптимизации с дополнительными ограничениями многократного выбора одновариантного типа. Сделан вывод о сложности получения достаточных условий в случае дополнительными ограничений многократного выбора многовариантного типа.
Исследовано типичное поведение локального элиминационного алгоритма на различных блочных структурах на основе анализа среднего значения оценки эффективности локального элиминационного алгоритма. Показано, что асимптотическая средняя оценка эффективности локального алгоритма в случае блочно-древовидной структуры с переменными и блоками без дополнительных ограничений находится в пределах между и (), где степень вершины в структурном графе задачи дискретной оптимизации. Показано, что самым лучшим (в смысле минимума асимптотической средней оценки эффективности локального алгоритма) является случай квазиблочной структуры.
Найдены асимптотические средние оценки эффективности локального алгоритма на классе блочно-древовидных структур с дополнительными ограничениями многократного выбора одновариантного и многовариантного типа.
Решены задачи нахождения экстремальных значений оценок эффективности локального алгоритма при заданной структуре и параметрах , где число переменных, а число блоков. Знание экстремальных значений оценок эффективности локального алгоритма позволяет выделить наилучшие и наихудшие для локального алгоритма блочные структуры, причем наилучшие структуры соответствуютминимуму оценки эффективности, а наихудшие – максимуму.
Предложены и исследованы алгоритмы выделения древовидных структур, в том числе блочно-древовидных и древовидных декомпозиций, а именно: предложены алгоритмы выделения блочно-древовидных структур в разреженных графах взаимосвязей дискретных задач, позволяющего применение локальных элиминационных алгоритмов для решения этих задач; предложено выделение древовидных декомпозиций в разреженных графах взаимосвязей дискретных задач на основе применения элиминационной игры и различных эвристик; вскрыта связь блочных декомпозиций и древовидных декомпозиций, что дает возможность рассматривать лишь древовидные декомпозиции; построение блочных структур на основе построения фактор-графов; показана важность хордальных графов, нахождения триангуляций при нахождении древовидных декомпозиций.
Методы исследований. В работе использованы методы дискретной математики, в том числе методы теории графов, комбинаторного анализа, теории локальных алгоритмов, дискретной оптимизации, а также методы математического анализа.
Научная новизна. Все основные результаты диссертации являются новыми.
Теоретическая и практическая ценность. Работа носит теоретический и прикладной характер. Полученные результаты могут найти применение при анализе эффективности локальных алгоритмов, а также при программной реализации локальных алгоритмов решения разреженных задач дискретной оптимизации большой размерности.
Апробация работы. Основные результаты диссертации докладывались и обсуждались на семинаре отдела математических проблем распознавания и методов комбинаторного анализа Вычислительного Центра имени А. А. Дородницына РАН, на семинаре кафедры Computational Mathematics Венского университета (Австрия), семинаре кафедры Production and Operations Management Венского университета (Vienna, 24.1.2005); International Workshop "Graph and Hypergraph Decompositions Methods and Applications in Computer Science" (Vienna, 16. Dec - 18. Dec 2004); а также были представлены на Республиканской конференции «Вычислительная математика в современном научно-техническом прогрессе» (Канев, 1982); на I Республиканской школе по дискретной оптимизации (Судак, 1982 г.); Республиканском семинаре по дискретной оптимизации (Ужгород, 1983 г.), на Всесоюзных семинарах: «Методы дискретной оптимизации в АСУ» (Алушта, 1983 г.), «Дискретная оптимизация: теория и приложения» (Севастополь, 1984 г.), «Моделирование сложных систем» (Судак, 1985 г.), на заседаниях Республиканского семинара «Математическое моделирование и автоматизация обработки информации» Научного Совета АН УССР по проблеме «Кибернетика» (Симферополь, 1981-1991 гг.), на Всесоюзном семинаре по дискретной оптимизации (Алушта, 1991); Всесоюзных конференциях «Системы программного обеспечения решения задач оптимального планирования. 1982, 1986; «Декомпозиция и координация в сложных системах», Челябинск: ЧПИ, 1986; на международной конференции по математическим методам в исследовании операций. София, 1983; Российской конференции «Дискретная оптимизация и исследование операций» (Владивосток, 7-14 сентября 2007); на III и IV Всероссийских конференциях «Проблемы оптимизации и экономические приложения» (Омск, 2006, 2009 гг.) на Международных научных конференциях «Танаевские чтения» (Минск, 2007, 2010 гг.); на 11 Национальной конференции по искусственному интеллекту (Дубна, 28 сентября – 3 октября 2008 г.); Международных конференциях Х Internationaler Kongress ber Anwendungen der Mathematik in den Ingenieur Wissenschaften. Weimar. 1984; 1st International Workshop on Global Constrained Optimization and Constraint Satisfaction. Valbonne Sophia Antipolis, France, October 2-4, 2002; Int. Conference on Operations Research "Operations Research 2006" (Karlsruhe, 6-8 September, 2006); Applied Optimization and Metaheuristic Innovations (Abstracts of Int.Conference, Yalta, July 19-21, 2006); Second International Conference MCO 2008 “Modelling, Computation and Optimization in Information Systems and Management Sciences”, Metz, France Luxembourg, September 8-10, 2008; International conference "Optimization and applications" (OPTIMA2009) September 21-25, 2009 Petrovac, Montenegro.
. Публикации. По теме диссертации опубликовано 44 работы, из них 22 – в журналах из списка ВАК (список работ приводится в конце автореферата, журналы из списка ВАК выделены жирным шрифтом). В совместных работах [73, 74], [101104] В. В. Матвееву принадлежат конкретные результаты применения локального алгоритма в частном случае, а автору диссертации – принадлежит общая схема метода и руководство работой; в совместных работах [87], [9699] Канаевой Н.Н. принадлежат конкретные результаты применения локального алгоритма в частном случае наличия дополнительных ограничений, а автору диссертации – принадлежит общая схема метода и руководство работой; в совместной работе [100] Иловайской Е. И. выполнена работа по программированию и машинный эксперимент под руководством автора диссертации; в совместных работах [105107] Быстрову В. А. принадлежат конкретные результаты применения локального алгоритма в частном случае, а автору диссертации – принадлежит общая схема метода и руководство работой.
Структура и объем работы. Диссертация состоит из списка обозначений, сокращений и определений, введения, 7 глав, заключения и списка литературы, содержащего 593 названий. Общий объем диссертации 357 страниц.
Локальный декомпозиционный алгоритм ABT решения задач дискретной оптимизации с блочно-древовидной структурой
В настоящем параграфе предлагается ЛА Am [180, 185] решения блочно древовидных задач ДО, т.е. задач, в которых возможно выделить систему окрестностей различных переменных такую, что одна переменная может быть обшей самое большее лишь для двух окрестностей и граф пересечений этих окрестностей представляет собой дерево. С помощью ЛА Aвт можно решить подобную задачу ДО, двигаясь от окрестностей, соответствующих листьям дерева, к окрестности, соответствующей корню дерева.
Введем необходимые для дальнейшего изложения понятия. Пусть Q, =(5!, ), a2=(S2,U2), ..., ak=(Sk,Uk) - система окрестностей некоторых переменных х.,...,х- , где Sr, Uг - соответственно множества индексов переменных и ограничений для г -й окрестности, r = l,...,k, причем к Замечание. Отметим, что при определении понятия блочно-древовидной структуры мы пользуемся понятием окрестности, а не блока, хотя эти два понятия тесно связаны. Дело в том, что блочную структуру в матрице инциденций задачи ДО можно выделить с помощью анализа окрестностей переменных, нетрудно видеть, что если путем перестановки строк и столбцов матрицы инциденций и переменных и ограничений (1.2) задачи ДО (1.1)-(1.3) можно собрать вместе ограничения с индексами из Ur и переменные с индексами из Sr, то мы получим подматрицу - блок. Нетрудно видеть, что блочно-древовидная структура является частным случаем древовидной декомпозиции. Введем понятие графа инцидентности (или графа пересечений) Ga окрестностей {1г} аналогично понятию графа пересечений GA булевой матрицы А, введенному в [47]. Граф пересечений окрестностей Ga имеет вершины vvv2,...,vk, соответствующие выделенным окрестностям lvl2,...,lk, причем две вершины графа vr и vr , отвечающие окрестностям 1Г и 1г , соединены ребром (rvr2), если Определение 1.2. Блочно-древовидной назовем задачу ДО, для которой можно выделить систему окрестностей lvl2,...,lk, удовлетворяющую свойствам (1.4) - (1.7), причем граф пересечений окрестностей Ga является деревом. Будем говорить, что описанная задача ДО имеет блочно-древовидную (БД) структуру. Замечание. Частным случаем БД структуры является квазиблочная структура [159, 173], для которой граф пересечений окрестностей (или блоков) является линейным деревом (путем) (рис. 1). Как уже отмечалось, блочно-древовидная структура является частным случаем древовидной декомпозиции. Изложим ЛА ABT решения БД задач ЦЛП вида (1.1) - (1.3), где матрица А имеет БД структуру, содержащую к блоков, и этой структуре соответствует дерево D инцидентности блоков. Рассмотрим вершину г дерева D и дерево Dr, состоящее из вершины г и всех ее потомков. Введем необходимые обозначения: Sr - множество индексов перемен ных, принадлежащих блоку Br\ Sr/ - множество индексов переменных, принадле жащих одновременно блокам Вг и Вг,; если S то Xs = \xh,...,Xj J ; XSr/ - вектор переменных, общих для блоков Вг и Вг,. Обозначим через Z D следующую задачу: для каждого вектора Xs найти XS r и XSrr,r & Jr, такие, чтобызначение целевой функции задачи ZD , соответствующей дереву Dr. Решение задачи ZD для вершины г графа D при фиксированном векторе Xs обозначим таким образом: X (xSp г) = U [xD/ (xSr/) U xSr/1U xSr rWr Нетрудно заметить, что если зафиксировать вектор Xs то задача (1.1)-(1.3) распадается на две задачи: первая соответствует дереву Dr; а вторая - D\Dr. На этом свойстве и основано применение ЛА AВТ для решения БД задач ДО. Алгоритм Aвт вычисляет информацию, поднимаясь от листьев дерева к корневой вершине. Изложим ЛА Aвт решения БД задачи ДО, характеризующейся деревом D инцидентности блоков с k вершинами, состоящим из L слоев. Пусть в v -м слое имеется lv вершин Rv = { ,...,г }, разбитых на подмножества Jr.
Локальные элиминационные алгоритмы решения дискретных задач информатики
Как мы уже отметили, ЛА элиминации переменных исследует окрестность Nb(xj) некоторой переменной х. и находит для всех значений переменных из этой окрестности оптимальное значение Xj, что может приводить к большому объему вычислений. Однако переменные из окрестности могут обладать разными свойствами по отношению к своей окрестности: одни из них имеют связи лишь с переменными из данной окрестности, другие же связаны и с переменными извне. Поэтому имеет смысл осуществлять полный перебор значений лишь для переменных, принадлежащих границе окрестности Bo(Nb(Xj)), как в Л А A, а оптимальные значения «внутренних» переменных окрестности (т. е. переменных из Int(Nb(xj))) определять совместно с переменной Xj, образуя «блок» переменных. В ЛА элиминации переменных переменные из lnt Nb{xj)) могут рассматриваться как «блочная» переменная (или супер-переменная). Переменные в упорядочении а, принадлежащие к Int[Nb[xA), могут рассматриваться также как одна
блочная переменная, проиндексированная переменной х,. При построении блочных переменных целесообразно использовать понятие «супер-вершины» 4, объединяющей в себе так называемые «неразличимые вершины» [209], [461] (в графе G две смежные вершины и и v называются неразличимыми, если Nb[u] = Nb[v]).
Рассматривая квазиблочную задачу ДО, можно объединить все «внутренние» переменные блоков, являющиеся неразличимыми, в супер-вершины, соответствующие блокам, при этом общие переменные блоков (переменные из «перемычек») образуют другие супер-вершины. В результате решение квазиблочной задачи ДО с помощью блочной модификации НСЛА сводится к решению задачи с линейным графом вида хв -хв -хв -...-хв и реализация этого алгоритма совпадает с ЛА A.
Супер-вершина (supernode) - множество обычных вершин, которая может рассматриваться НСЛА декомпозиции как одна вершина [209], [461]. 2.2.4. Аналоги теорем единственности и мажорантности в теории локальных элиминационных алгоритмов
Ответ на вопрос, зависит ли вид элиминационного графа от порядка прохождения вершин из некоторого подмножества, дан в следующей теореме, являющейся аналогом теоремы единственности в классической теории локальных алгоритмов Ю. И. Журавлева: Теорема 2.1 (Теорема об инвариантности [255]). Любой граф, полученный из G = (X,E) с помощью поочередной элиминации всех вершин из некоторого подмножества Y а X , не зависит от порядка элиминации вершин. Определение 2.8. Граф, полученный из G с помощью элиминации всех вершин подмножества Y а X в некотором порядке, называется Y -элиминационным графом графа G и обозначается GY; эта операция называется элиминацией подмножества Y. Мажорантность локальных элиминационных алгоритмов В дальнейшем, при формулировке теоремы мажорантности локальных элиминационных алгоритмов, используются алгоритмы сравнения, которые рассматриваются для фиксированного множества переменных с фиксированными областями определения (доменами) и с фиксированным графом взаимосвязей. ЛЭА представляет собой класс алгоритмов, причем для определения конкретного алгоритма необходимо задать упорядочение переменных, граф взаимосвязей и области определения переменных. Воздействие ЛЭА на задачу ДО изоморфно некоторому алгоритму сравнения. Два присвоения \{S) и A, (S) называются сравнимыми, если для них всем переменным из граничного множества Bo(S) присвоены одни и те же наборы значений в обоих присвоениях. Два множества Sx и S2 называются частично перекрывающимися, если 1) и S2 - не вложенные; 2) некоторый член fi (х.) включен в вычисления значений целевых функций для Sl и S2. Два сравнения называются частично перекрывающимися, если их S-множества частично перекрываются. Множество сравнений (а также алгоритм сравнения или верификация) называется частично перекрывающимся, если два сравнения частично перекрываются. В противном случае множество, алгоритм или верификация называются не перекрывающимися. Формально для данного графа взаимосвязей G и области определения переменных алгоритм сравнения - это такое бинарное решающее дерево, что: i. Два ребра, спускающиеся из каждой внутренней вершины дерева, представляют два присвоения, которые сравнимы для задач ДО с графом G. Вершина решающего дерева представляет сравнение, результат которого определяет выбор ребра, идущего из вершины вниз; ii. сравнения вдоль любого пути из корня до листа дерева задают верификацию. Рассмотрим произвольную задачу ДО вида (2.1) - (2.3) с графом взаимосвязей G и доменами переменных D1,...,Dn. Пусть а - порядок элиминации переменных, минимизирующий число выполняемых сравнений (зависящее лишь от графа G, Щ,...\Оп и а). Справедлива Теорема 2.2 (о мажорантности локального алгоритма элиминации переменных) [521]. Для каждой задачи ДО вида (2.1) - (2.3) локальный алгоритм элиминации переменных с порядком элиминации а выполняет минимальное число сравнений среди всех не перекрывающихся алгоритмов сравнения. Представляет интерес следующая Теорема 2.3 (Финальная теорема) [255]. Если G = (X,E) - граф, L - полное в G подмножество вершин X , тогда существует оптимальное упорядочение, в котором вершины L по порядку являются последними. Процесс преобразования первичного графа взаимодействия переменных, соответствующий процедуре элиминации переменных с помощью локального алгоритма, известен как «элиминационная игра», которая впервые была введена Партером [494], как графовая интерпретация метода исключения Гаусса. Входом для алгоритма элиминационной игры является граф G и упорядочение а графа G (т.е. а(х) = і, если х - і -я вершина в упорядочении а).
Древовидная декомпозиция и древовидная ширина
Рассмотрим реляционную базу данных d, состоящую из множества отношений {гр...,ги} с реляционными схемами Rv...,Rn. Запрос состоит в нахождении выборки о от соединения отношений, сопровождающейся проекцией на некоторую область.
Отметим, что запросы такого вида эквивалентны так называемым конъюнктивным запросам [220], которые являются наиболее часто встречающимся типом запросов.
Рассмотрим метод поиска ответа на запрос вида (2.9), основанный на последовательной элиминации атрибутов с помощью ЛЭА, который вычисляет информацию о локальных элементах (атрибутах) задачи нахождения ответа на запрос в реляционной базе данных, задаваемой структурным графом, записывая локальную информацию об этих элементах в виде новых отношений, добавляемых к задаче, затем элиминируя просмотренные элементы и использованные отношения. При этом рассматриваются все отношения, содержащие некоторый атрибут. После нахождения соединения ( ) этих отношений [190], атрибут элиминируется с помощью проекции полученного отношения на множество оставшихся атрибутов.
Эти операции проделываются далее до тех пор, пока не останется лишь одно отношение, которое и является решением задачи - ответом на данный запрос. Если последнее отношение непусто, то ответ на запрос имеется, если же пусто -то ответа нет. Конкретизируем шаги ЛЭА решения задачи выполнения запроса, описываемого системой отношений rv...,rn с атрибутами xv...,xm, при заданном упорядочении Д. атрибутов. 1. Выбрать очередной атрибут х из схемы базы данных согласно упорядочению Ая. Найти соединение отношений, соответствующих окрестности Nb(x) элемента х в текущем структурном графе, сформировав новое отношение г с диапазоном (х, Nb(x)). 2. Спроектировать полученное отношение на множество атрибутов, соответствующих окрестности Nb(x) атрибута х. В результате получится новое отношение г = 7Гт(х)г(х) с диапазоном Nb(x), добавляемое к отношениям задачи. Если отношение с тем же набором переменных уже имеется, найти их пересечение. Если пересечение пусто, то задача выполнения запроса решения не имеет. 3. Элиминировать атрибут х вместе с соответствующими отношениями. Из элементов его окрестности Nb(x) создается клика в структурном графе (эта кли ка соответствует отношению г ). Создание клик изменяет структурный граф и ок рестности элементов. 4. Продолжать до тех пор, пока не останется нерассмотренных отношений. Обратная часть ЛЭА здесь не нужна, так как в конце вычислений находится ответ на запрос. Выводы по главе II. В главе II рассмотрен общий класс локальных элиминационных алгоритмов вычисления информации, позволяющих осуществлять вычисление глобальной информации с помощью локальных вычислений на основе анализа окрестностей элементов задачи, и относящихся к графовым декомпозиционным подходам [192], [540]. Рассмотрено применение локальных элиминационных алгоритмов при решении неоптимизационных разреженных дискретных задач информатики. В результате можно сделать следующие выводы: в главе II предложен класс локальных элиминационных алгоритмов вычисления информации для решения разреженных дискретных задач, использующих структуру дискретной задачи и вычисляющих глобальную информацию на основе локальных вычислений; предложено графовое и гиперграфовое представления структуры дискретных задач; введены и исследованы составляющие локального элиминационного алгоритма: элиминационное дерево, являющееся орграфом вычислительной процедуры локального элиминационного алгоритма и задающего информационные потоки; элиминационный процесс; элиминационные графы; элиминационная игра; рассмотрены и проанализированы конкретные реализации общей схемы локального элиминационного алгоритма: локальные алгоритмы элиминации переменных, использующие в качестве структурного графа граф взаимосвязей переменных задачи; блочно-элиминационные локальные алгоритмы, учитывающие подобие окрестностей отдельных переменных; локальные алгоритмы, использующие древовидную структурную декомпозицию; предложена несериальная модификация локального алгоритма А декомпозиции задач ДО, позволяющая решать полностью задачи ДО; выявлены аналоги двух основных теорем классической теории локальных алгоритмов: теорема о мажорантности локального элиминационного алгоритма теорема о единственности результата элиминации переменных независимо от порядка их элиминации; показано, что использование графовых структур позволяет рационально построить вычислительную схему локального элиминационного алгоритма. описаны особенности реализации вычислительной схемы локальных элимина-ционных алгоритмов при решении задач удовлетворения ограничений; рассмотрен пример решения задачи выполнимости SAT, заданной в конъюнктивной нормальной форме (КНФ); описаны особенности реализации вычислительной схемы локальных элимина-ционных алгоритмов при решении задач обработки запросов в реляционных базах данных. Материалы главы II опубликованы в работах автора [187], [190], [191-193], [199], [200], [539], [540].
Оценки эффективности локального алгоритма решения блочно-древовидных задач дискретной оптимизации
В рамках современной теории сложности сложились различные направления, одно из этих направлений связано с постановкой вопроса, существуют ли эффективные алгоритмы решения переборных (или комбинаторных) задач. В теории сложности используется понятие вычислительной сложности, дадим здесь предварительное определение этого понятия. Число шагов (или элементарных операций) алгоритма A, необходимых для нахождения решения некоторой задачи X , определяет временную вычислительную сложность алгоритма fA(X). Легкорешаемые задачи имеют полиномиальную временную сложность, а сложность трудно решаемых задач экспоненциальна. Замечание. В настоящее время помимо чисто полиномиальных и экспоненциальных алгоритмов иногда используются алгоритмы, сложность которых ни полиномиальна, ни экспоненциальна, так, согласно [10], скорости роста, такие как nlog n, которые превосходят любой полином, но меньше, чем 2nе, \/е 0, называются иногда субэкспоненциальными. Ниже будем пользоваться понятием квазиэкспоненциальных алгоритмов со скоростью роста сложности Т / nа. В настоящее время показано, что существуют универсальные переборные задачи - задачи, из полиномиальной разрешимости которых следует полиномиальная разрешимость любой переборной задачи. Таких универсальных задач сейчас известно несколько тысяч (среди них хорошо известные задача коммивояжера, задача о раскраске, задача о покрытии, многие задачи теории расписаний).
Известна гипотеза, что для универсальных задач вообще не существует эффективных методов решения переборных задач.
Можно выделить такие типы комбинаторных задач как оптимизационные задачи и задачи распознавания свойств (можно привести пример последней задачи: ответить на вопрос, существует ли допустимое решение X, такое, что значение целевой функции для него не менее L ). При этом особо выделяются классы задач: P – класс задач распознавания, которые могут быть решены некоторым полиномиальным алгоритмом, класс NP содержит индивидуальные задачи X, для которых в случае ответа «да» существовало бы удостоверение полиномиальной длины для X . Понятно, что P NP, известная проблема «P = NP » является одним из наиболее важных теоретических вопросов в теории сложности.
Мы же в дальнейшем будем интересоваться такими характеристиками сложности алгоритмов, которые позволяли бы сравнивать известные алгоритмы между собой. Остановимся на некоторых из этих характеристик.
Под вычислительной сложностью алгоритма, как отмечено выше, понимают количество условных шагов или операций, необходимых для решения задачи. Одним из наиболее распространенных методов оценки трудоемкости алгоритмов является экспериментальный метод, основанный на многократном решении задач различных размерностей и эмпирической оценке интересующих величин и зависимостей. Однако этот подход имеет существенный недостаток – он не дает достаточной уверенности в том, что результаты машинного эксперимента достигаются и на множестве данных, отличных от исследованных. В [117] отмечено: «…чтобы быть практически полезной, информация о сложности алгоритма должна быть машинно-независимой». В связи с этим широко распространен подход, использующий некоторую модель вычислительного устройства, применяемого для реализации алгоритма. В качестве вычислительных устройств обычно используются машина с производным доступом к памяти и хранимой программой или машина Тьюринга.
При введении оценок сложности алгоритмов решения комбинаторных задач обычно различаются индивидуальная задача и массовая задача (или просто задача), последняя представляет собой множество индивидуальных задач. При этом для оценки трудоемкости алгоритмов используются следующие характеристики: времення вычислительная сложность алгоритма – время, затрачиваемое алгоритмом для решения задачи, емкостная сложность алгоритма – объем памяти, необходимый для реализации алгоритма. Для сглаживания резких различий в поведении алгоритма при переходе от одной индивидуальной задачи к другой, можно рассматривать все индивидуальные задачи одной размерности n вместе и определить сложность алгоритма для этой размерности задачи как число шагов (или условных операций) алгоритма в худшем случае [305], [319], [322], [353], [396], [474], [567], т. е. находится времення вычислительная сложность T (n) в предположении, что для данного алгоритма входные данные задачи являются наихудшими из возможных, другими словами, находится верхняя оценка сложности алгоритма, говорящая о том, что данный алгоритм решает задачу не более чем за T (n) условных единиц времени. Если для некоторого алгоритма верхняя оценка сложности меньше, чем для других алгоритмов, то говорят, что этот алгоритм имеет характеристику «в худшем случае» лучше, чем другие алгоритмы.
Ориентация на худший случай иногда приводит к пессимистическим прогнозам поведения алгоритмов, так, хорошо известный симплекс-алгоритм на практике работает как полиномиальный алгоритм (это же показывает и теоретический анализ его поведения «в среднем» [152, 273, 547]), хотя оценка сложности в худшем случае для него является экспоненциальной [431].
В связи с этим с практической точки зрения часто бльший интерес представляет средняя оценка вычислительной сложности [319, 531], позволяющая судить о поведении алгоритма в среднем на некотором классе задач, однако средняя оценка вычислительной сложности тоже не дает полной характеристики эффективности алгоритма, так как возможны задачи, при решении которых сложность алгоритма превысит эту оценку.
Важной характеристикой алгоритма является асимптотическая оценка сложности – порядок скорости роста сложности алгоритма при увеличении размерности задачи. Асимптотические оценки вычислительной сложности алгоритмов позволяют судить об их поведении при решении задач большой размерности и определить границы применимости алгоритма, более того, «…именно асимптотическая сложность алгоритма определяет в итоге размер задач, которые можно решить этим алгоритмом» [10, с. 12]. Важность изучения асимптотических оценок вычислительной сложности алгоритмов обусловлена также ускоренным ростом быстродействия современной вычислительной техники и необходимостью решения задач большой размерности. Сравнивая алгоритмы по асимптотическим оценкам сложности, следует иметь в виду, что вычислительная сложность алгоритма может характеризоваться большим порядком скорости роста, но характеризоваться меньшей мультипликативной константой, чем другой алгоритм. В этом случае, алгоритм, характеризующийся большой скоростью роста сложности, может оказаться эффективнее других алгоритмов для решения задач небольшой размерности.
Оценки сложности алгоритмов дискретной оптимизации Проблема оценки сложности алгоритмов и задач оптимизации в зависимости от размерности задачи представляет большой теоретический и практический интерес и позволяет получить представление о трудоемкости решения задач дискретной оптимизации.
