Geum.ru
Авторефераты по всем темам  >>  Авторефераты по техническим специальностям  

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

ЩЕРБИНА Олег Александрович

ОКАЛЬНЫЕ ЭЛИМИНАЦИОННЫЕ АЛГОРИТМЫ ДЛЯ

РАЗРЕЖЕННЫХ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ

05.13.17 - теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

доктора физико-математических наук

Москва - 201Е

Работа выполнена в Таврическом национальном университете

им. В.И. Вернадского (г. Симферополь, Украина)

Официальные оппоненты: доктор физико-математических наук,

профессор,        

Владимир Алексеевич Емеличев

доктор физико-математических наук,

профессор,        

Юрий Анатольевич Зуев

доктор физико-математических наук,

профессор,        

Николай Николаевич Кузюрин

Ведущая организация: Факультет вычислительной математики и

кибернетики Московского государственного

университета им. М.В. Ломоносова.

Защита диссертации состоится  Е. ЕЕЕ. 201Е г.  в Е.-00  час.

на заседании диссертационного совета Д 002.017.02 в Учреждении

Российской академии наук Вычислительный центр имени

  А.А.Дородницына РАН по адресу:

119333, г. Москва, ул. Вавилова, д.40.

С диссертацией можно ознакомиться в библиотеке В - РАН.

Автореферат разослан У У _____________ 201Е г.

Ученый секретарь диссертационного

совета Д 002.017.02, д.ф.-м.н., профессор В.В. Рязанов

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

Актуальность темы.

Методы исследования дискретных структур играют все более важную роль в современных приложениях математики.

Использование моделей и алгоритмов дискретной оптимизации (ДО) позволяет решать многие практические задачи, такие, как задачи теории расписаний, оптимизации на сетях, маршрутизации трафика в коммуникационных сетях, задачи размещения экономических объектов, задачи оптимизации автоматизированных систем планирования ресурсов (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], задачи оптимального назначения радиочастот1 [46].

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

Одним из первых классов больших разреженных задач линейного пронграммирования, которые начал изучать Dantzig, был класс квазиблочных задач ЛП для динамического планирования [56]. Другие примеры квазиблочных задач ЛП для многоэтапного планирования, составления расписаний, назначений и многоэтапного структурного проектирования содержатся во множестве тестовых квазиблочных задач, опубликованных Ho & Loute [57]. Квазинблочную структуру имеют задачи оптимального резервирования гостинничных номеров [82], аналогичные последним темпоральные заданчи о ранце [58], получившие в последнее время применение при реншении задач предварительного резервирования вычислительных ресурсов в Grid Computing, задачи линейного динамического программирования [59], некоторые задачи управления трудовыми ресурсами [60], динамические модели экономики, учитывающие в явном виде фактор времени [61], задачи управления в иерархических (обычно древовидных) структурах, сетевые задачи, задачи многоэтапного стохастического программирования.

Для решения квазиблочных задач ДО достаточно эффективен локальный алгоритм [62, 67, 71 81], использующий специфику квазиблочной матрицы ограничений и имеющий декомпозиционный характер, т.е. сводит решение исходной задачи ДО большой размерности к решению ряда задач меньших размерностей, которые уже можно решить известными методами, т.е. с помощью имеющихся решателей.

Отметим, что локальный элиминационный алгоритм долгое время оставался чисто теоретическим алгоритмом. В [71] впервые приводятся результаты вычислительного эксперимента по решению задач ДО с помощью локального алгоритма. В [72] приводятся результаты исследования эффективности локального алгоритма для квазиблочных задач ДО, причем была показана слабая зависимость асимптотической средней оценки эффективности локального алгоритма от эффективности алгоритма ДО, решающего подзадачи для блоков. Это объясняется тем, что средняя оценка эффективности рассматривалась на множестве всех квазиблочных структур, но, как отмечалось в [63], локальные алгоритмы эффективны для задач с ограниченной связностью блоков.

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

  Цель работы. В связи с вышеизложенным основными целями диссернтанционной работы являются:

  • Разработка общей алгоритмической схемы локальных элиминационных алгоритмов для решения широкого класса разреженных задач ДО и из других областей прикладной математики.
  • Исследование возможностей распространения локального элиминационного алгоритма на различные классы задач ДО.
  • Использование ЛА совместно с методами древовидной декомпозиции.
  • Теоретическое и экспериментальное исследование эффективности локального элиминационного алгоритма, анализ и выделение классов блочных задач ДО, достаточно эффективно решаемых локальным элиминационным алгоритмом.
  • Исследование возможностей снижения перебора ЛЭА на основе использования релаксаций, селектора, распараллеливания вычислительного процесса.

На защиту выносятся следующие результаты:

  1. Разработана общая алгоритмическая схема локальных элиминационных алгоритмов для решения широкого класса разреженных дискретных задач. Эти алгоритмы используют структуру дискретной задачи и вычисляют глонбальную информацию на основе локальных вычислений, используя понятие близости переменных, основанное на использовании топологических окрестностей переменных, отражающих структуру дискретной задачи. При этом дискретные задачи могут быть как задачами дискретной оптимизации, так и носить неоптимизационный характер: дискретные задачи удовлетворения ограничений и дискретные задачи обработки запросов в реляционных базах данных. Структура разреженных дискретных задач задается с помощью графового и гиперграфового представлений.
  2. Введены и исследованы графовые структуры локального элиминационнного алгоритма: элиминационное дерево, являющееся орграфом вынчиснлительной процедуры локального элиминацинонного алгоритнма и задающего информационные потоки; элиминационный процесс; элиминационные графы; элиминационная игра. Показано, что использование графовых структур позволяет рационально построить вычислительную схему локального элиминационнного алгоритма.
  3. Рассмотрены и проанализированы конкретные реализации общей схемы локального элиминационнного алгоритма: локальные алгоритмы элиминации переменных, использующие в качестве структурного графа граф взаимосвязей переменных задачи; блочно-элиминационные локальные алгоритмы, учитывающие подобие окрестностей отдельных переменных; локальные алгоритмы, использующие древовидную структурную декомпозицию. Предложены локальные декомпозиционные алгоритмы решения задач с блочно-древовидной структурой. Рассмотрены особенности применения локальных алгоритмов с селектором для блочно-древовидных структур с дополнительными ограничениями многократного выбора. Предложен локальный элиминационный алгоритм, использующий древовидную структурную декомпозицию, являющуюся обобщением блочно-древовидной структуры.
  4. Предложены и проанализированы оценки вычислительной сложности (оценки эффективности) локальных алгоритмов на блочно-древовидных структурах как с дополнительными ограничениями, так и без них (с селектором и без него), на основе их анализа проведено теоретическое исследование эффективности локального элиминационного алгоритма, анализ и выделение классов блочных задач ДО, достаточно эффективно решаемых локальным элиминационным алгоритмом.
  5. Поставлен и решен вопрос о целесообразности изучения блочно-древовидных структур на основе исследования оценок эффективности. Получены достаточные условия, позволяющие исключить полный перебор при использовании блочно-древовидных структур.
  6. Проведен анализ оценок эффективности локального алгоритма при решении блочно-древовидных задач дискретной оптимизации с дополнительными ограничениями многократного выбора. Показана целесообразность использования локального алгоритма при решении блочно-древовидных задач дискретной оптимизации с дополнительными ограничениями многократного выбора и без них. Получены достаточные условия целесообразность использования локального алгоритма при решении блочно-древовидных задач дискретной оптимизации с дополнительными ограничениями многократного выбора одновариантного типа. Сделан вывод о сложности получения достаточных условий в случае дополнительными ограничений многократного выбора многовариантного типа.
  7. Исследовано типичное поведение локального элиминационного алгоритма на различных блочных структурах на основе анализа среднего значения оценки эффективности локального элиминационного алгоритма. Показано, что асимптотическая средняя оценка эффективности локального алгоритма в случае блочно-древовидной структуры с переменными и блоками без дополнительных ограничений находится в пренделах между и (), где степень вершины в структурном графе задачи дискретной оптимизации. Показано, что самым лучшим (в смысле минимума асимптотической средней оценки эффекнтивности локального алгоритма) является случай квазиблочной структуры.
  8. Найдены асимптотические средние оценки эффективности локального алгоритма на классе блочно-древовидных структур с дополнительными ограничениями многократного выбора одновариантного и многовариантного типа.
  9. Решены задачи нахождения экстремальных значений оценок эффективности локального алгоритма при заданной структуре и параметрах , где число переменных, а число блоков. Знание экстнремальных значений оценок эффективности локального алгоритма позволяет выделить наилучшие и наинхудшие для локального алгоритма блочные структуры, причем наилучшие структуры соотнветствуютминимуму оценки эффективности, а наихудшие Ц максимуму.
  10. Предложены и исследованы алгоритмы выделения древовидных струкнтур, в том числе блочно-древовидных и древовидных декомпонзиций, а именно: предложены алгоритмы выделения блочно-древовидных структур в разреженных графах взаимосвязей дискретных задач, позволяющего применение локальных элиминационных алгоритмов для решения этих задач; предложено выделение древовидных декомпозиций в разреженных графах взаимосвязей дискретных задач на основе применения элиминационной игры и различных эвристик; вскрыта связь блочных декомпозиций и древовидных декомпозиций, что дает возможность рассматривать лишь древовидные декомпозиции; построение блочных структур на основе построения фактор-графов; показана важность хордальных графов, нахождения триангуляций при нахождении древовидных декомпозиций.

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

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

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

Апробация работы. Основные результаты диссертации докладывались и обсуждались на семинаре отдела математических проблем распознавания и методов комбинаторного анализа Вычислительного Центра имени А. А. Дородницына РАН, на семинаре кафедры 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 Innoнvations (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 страниц.

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

Во введении обосновывается актуальность темы и дается краткое содержание работы.

В главе 1 рассматривается дескриптивная теория локальных алгоритмов, в параграфе 1.1 описан локальный алгоритм вычисления информации: приведены основные определения и теоремы теории локальных алгоритмов, рассмотрены задачи дискретной математики, для которых построены мажорантные (наилучшие) локальные алгоритмы в явной форме.

В параграфе 1.2 описан локальный алгоритм А [63]. Рассмотрен иллюстративный пример решения задачи ДО с помощью кольцевого локального алгоритма А.

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

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

В параграфе 1.5 показана возможность распространения локального алгоритма на блочные структуры, описываемые произвольным графом пересечений блоков (возможно, отличным от дерева) на основе выделения остовного дерева.

В параграфе 1.6 выявлены и проанализированы связи локальных алгоритмов решения задач дискретной оптимизации с другими алгоритмами дискретной оптимизации: схемой последовательного конструирования, анализа и отсева вариантов В. С. Михалевича; несериальным динамическим программиронваннием Бертеле-Бриоши; алгоритмом сегментной элиминации Дехтер для решения задач удовлетворения ограничений; с элиминационными алгоритмами в линейной алгебре.

В главе II рассмотрен общий класс локальных элиминанционных алгоритмов вычисления информации, позволяющих на основе вычисления локальной информации получать глобальную информацию о решении всей задачи. Описана общая структура локальных алгоритмов элиминации, использующих окрестности элементов, структурный граф, описывающий структуру задачи, а также алгоритм элиминации. Представителями этого класса алгоритмов являются локальные алгоритмы декомпозиции задач дискретной оптимизации, алгоритмы несериального динамического программирования, алгоритмы сегментной элиминации, методы древовидной декомпозиции. позволяющих осущестнвлять вычисление глобальной информации с помощью локальных вычислений на основе анализа окрестностей элементов разреженной дискретной задачи. Глава начинается с основных определений в параграфе 2.1, в котором рассмотрены структура дискретной задачи и способы ее описания, причем структура может быть задана как исходными элементами (переменными) с заданием системы окрестностей этих переменных с помощью структурного элементного графа и порядка просмотра этих перенменных с помощью ЛЭА, так и различными производными структурами - блочными, блочно-древовидными, задаваемыми так называемым структурным конденсированным графом. ЛЭА вычисляет информацию о локальных элементах структуры задачи, задаваемой структурным графом, записывая локальную информацию об этих элементах в виде новых зависимостей, добавляемых к задаче, затем элиминнируя просмотренные элементы и использованные зависимости. Процедура ЛЭА состоит из двух частей: 1) прямая часть - элиминация элементов, вычисление и запоминание информации в виде локальных решений и получение в конце значения критерия; 2) обратная часть - нахождение глобального решения всей задачи по найденным в прямой части таблицам с локальными решениями, обеспечивающего достижение критерия в прямой части. Алгоритмическая схема ЛЭА представляет собой бесконтурный орграф. В параграфе 2.2 рассмотрено применение ЛЭА для решения разреженных задач дискретной оптимизации. Предложено графовое (в виде первичного графа взаимосвязей и двойственного графа) и гиперграфовое представления структуры разреженных задач дискретной оптимизации. Описаны локальные алгоритмы элиминации переменных для решения разреженных задач дискретной оптимизации. Введены и исследованы характеристики локального элиминационнного алгоритма: элиминационное дерево, являющееся орграфом вынчиснлительной процедуры локального элиминацинонного алгоритнма и задающего информационные потоки; элиминационный процесс; элиминационные графы; элиминационная игра. Описаны свойства элиминационного дерева. Рассмотрены и проанализированы конкретные реализации общей схемы локального элиминационнного алгоритма: локальные алгоритмы элиминации переменных, использующие в качестве структурного графа граф взаимосвязей переменных задачи; блочно-элиминационные локальные алгоритмы, учитывающие подобие окрестностей отдельных переменных; локальные алгоритмы, использующие древовидную структурную декомпозицию. Выявлены аналоги двух основных теорем классической теории локальных алгоритмов: теорема о мажорантности локального элиминационного алгоритма и теорема о единственности результата элиминации переменных независимо от порядка их элиминации. Предложен локальный элиминационный алгоритм, использующий древовидную структурную декомпозицию, являющийся обобщением локального декомпозиционного алгоритма, описанного в главе I. В параграфе 2.3 рассмотрено применение локальных элиминационных алгоритмов при решении неоптимизационных разреженных дискретных задач информатики. Описаны особенности реализации вычислительной схемы локальных элиминационных алгоритмов при решении задач удовлетворения ограничений, а также при решении задачи выполнимости SAT, заданной в конънюнктивной нормальной форме. Описаны особенности реализации вычислительной схемы локальных элиминационных алгоритмов при решении задач обработки запросов в реляционных базах данных.

В главе III анализируются теоретико-графовые подходы к выделению блочных структур в разреженных матрицах. В параграфе 3.1 рассмотрен алгоритм Финкельштейна выделения квазиблочной структуры в разреженной матрице. Полученная квазиблочная структура задачи ДО на двойственном графе задачи имеет вид цепи. Далее рассматривается граф, индуцируемый множеством блоков структуры в двойственном графе и выделим в нем компоненты связности. Далее каждый блок заменяется на подблоки, образованные пересечением блоков с соответствующими компонентами связности. В результате получается блочно-древовидная структура. В параграфе 3.2 для разреженных матриц получено необходимое условие выделяемости БД структуры, позволяющее по степени разреженности матрицы судить о возможности выделенния в ней БД структуры. Поскольку ЛЭА может работать на задачах ДО, в которых выделена древовидная декомпозиция (ДД), в параграфе 3.3 рассматриваются ДД и древовидная ширина (ДШ). Задача поиска ДШ (и наилучшей ДД) состоит в нахождении триангуляции с минимальным размером наибольшей клики и актуальна в связи с тем, что многие NP-полные задачи разрешимы за полиномиальное время, если они рассматриваются на графах с ограниченной ДШ. Отмечена NP-трудность как задачи поиска триангуляции с минимальным пополнением, так и задачи поиска ДШ, а также то, что для обеих задач имеются полиннонмиально вычислимые альтернативы нахождения так называемой минимальной тринангуляции. Далее рассматриваются хордальные графы (ХГ), которые в некотором смысле являютнся обобщениями деревьев. Вводится понятие триангуляции графа G, которой называется ХГ, содержащий G в качестве подграфа. Приведены результаты Courcelle, состоящие в том, что любая задача, которая может быть поставлена в монадической логике 2-го порядка, может быть решена за линейное время на графах с ограниченной ДШ. Приведены свойства хордальных графов. Рассмотрена элиминационная схема для распознавания ХГ, предложенная Fulkerson и Gross и состоящая в выделении и элиминации симплициальных вершин. Введено понятие графа и дерева клик для графа G и отмечено, что нахождение дерева клик становится простой задачей в случае хордального графа. Показано, как алгоритм элиминационной игры можно использовать для триангуляции графов. Рассмотрены методы разбиения графа. Перечислен ряд доступных пакетов программного обеспечения по разнбиению графов. Рассмотрены вопросы построения блочных структур и древовидных декомпозиций из упорядоченных разбиений путем построения фактор-графов.

Глава IV посвящена оценкам вычислительной сложности локального алгоритма и выяснению условий целесообразности его использования. В параграфе 4.1 рассматриваются некоторые вопросы теории сложности алгоритмов решения задач ДО. Вводится используемое в дальнейшем понятие вычислительной сложности алгоритма ДО, называемой оценкой эффективнноснти алгоритма, рассматриваются оценки сложности в среднем и наихудшем случае, анализируется возможность нахождения асимптотической оценки вычислительной сложности. В параграфе 4.2 вводятся оценки эффективности локального алгоритма, соответствующие различным блочным структурам, сформулированы основные цели исследования оценок эффективности локального элиминационного алгоритма на классе задач ДО. Вводя обозначения , , БД структуру описываем здесь денревом пересечения блоков и вектором , причем Вводится следующая оценка эффективности (ОЭ) локального алгоритма на БД структурах без дополнительных ограничений:

.

Рассмотрим вопрос об оценке эффективности ЛА с селектором для решения задач ДО с БД структурой и дополнительными ограничениями многократного выбора здесь в сочетании с ЛА рассматривается лишь алгоритм полного перебора, перебирающий допустимые решения дополнительных огранничений (обозначим этот алгоритм ). Введем необходимые обозначения: число переменных, входящих только в окрестность и -е дополнительное ограничение многократного выбора; число переменных, входящих в пересечение окрестностей и в -е дополнительное ограничение многократного выбора (здесь ). ОЭ ЛА в этом случае имеет вид:

.

ОЭ ЛА с селектором для решения задач ДО с БД структурой и дополнительными ограничениями многократного выбора одновариантного типа, т.е. имеет вид:

В дальнейшем используется понятие рассмотрим частично невырожденной БД структуры, когда

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

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

В главе V исследуется типичное поведение локального элиминационного алгоритма на различных блочных структурах на основе анализа среднего значения оценки эффективности локального элиминационного алгоритма. В параграфе 5.1 найдена асимптотическая средняя оценка эффективности локального элиминационного алгоритма на классе блочно-древовидных структур без дополнительных ограничений, показано, что средняя оценка эффективности является квазиэкспоненциальной функцией от числа переменных задачи ДО. Здесь найдены асимптотические оценки эффективности локального алгоритма в сочетаннии с произвольным алгоритмом ДО при решении 2-квазиблочных задач дискретной оптимизации c переменными и показано, что асимптотическая средняя оценка эффективности локального алгоритма в этом случае находится в пренделах от до для произвольного алгоритма, с помощью которого решаются задачи внутри блоков. Кроме того, показано, что асимптотическая средняя оценка эффективности локального алгоритма в случае блочно-древовидной структуры с переменными и блоками без дополнительных ограничений находится в пренделах между и (), где степень вершины в структурном графе задачи дискретной оптимизации, далее найдена наихудшая асимптотическая средняя оценка эффекнтивности локального алгоритма в случае блочно-древовидной структуры без дополнительных ограничений (при метла или звезда, где число слоев в структурном графе (дереве) задачи дискретной оптимизации), что позволяет выделить наихудшую блочно-древовидную структуру. Показано, что самым лучшим (в смысле минимума асимптотической средней оценки эффекнтивности локального алгоритма) является случай , что соответствует квазиблочной структуре. Здесь показана слабая зависимость средней оценки эффективности локального элиминационного алгоритма от эффективности алгоритма ДО, с помощью которого решаются задачи в блоках.

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

Утверждение. Асимптотическая средняя оценка эффективности ЛА в сочетании с алгоритмом ДО, имеющим оценку эффективности , при решении БД задач ДО с ограниченной связностью имеет вид:

В параграфе 5.3. анализируется средняя оценка эффективности локального алгоритма для 2-квазиблочной задачи и небулевых переменных, т. е. Справедлива асимптотическая оценка:

.

В параграфе 5.4 исследуется типичное поведение локального элиминационного алгоритма на классе блочно-диагональных задач ДО с дополнительными ограничениями многократного выбора одновариантного типа длины l, найдена асимптотическая скорость роста оценки эффективности локального элиминационного алгоритма:

В параграфе 5.5 найдена асимптотика средней оценки эфнфективности ЛА на классе всех блочных задач с дополнительными огранничениями одновариантного типа:

В параграфе 5.6 исследуется типичное поведение локального элиминационного алгоритма на классе блочно-древовидных задач ДО с дополнительными ограничениями многократного выбора многовариантного типа длины l, найдена асимптотическая скорость роста оценки эффективности локального элиминационного алгоритма:

где

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

В параграфе 5.7 исследуется типичное поведение ЛЭА на множестве частично невырожденных БД структур с блоками, дополнительными ограничениями одновариантного типа и с булевыми переменными:

В параграфе 5.8 найдена асимтотика средней оценки эффективности локального алгоритма на классе всех блочно -древовидных структур с дополнительными ограничениями одновариантного типа:

при

В параграфе 5.9 для среднего значения ОЭ для всех задач ДО с заданной графом структурой, блоками, рёбрами графа и булевыми переменными получены неравенства:

.

Кроме того, для ЛА с селектором для решения -блочных задач ДО получена следующая оценка асимптотической средней ОЭ:

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

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

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

В параграфе 6.2 находится оценка для минимума оценки эффективности ЛЭА на вышеуказанном  классе структур, приведены точные значения минимума в случае квазиблочных структур.

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

Результаты, полученные в главе VI, позволяют качественно оценивать поведение ЛЭА на тех или иных блочно-древовидных структурах, позволяют также определять, каких структур следует избегать, а к каким стремиться при использовании ЛЭА.

Глава VII посвящена вычислительным аспектам реализации ЛЭА и анализу возможностей снижения перебора при использовании ЛЭА.

В параграфе 7.1 приведены результаты машинного эксперимента для ЛЭА в сочетании с различными алгоритнмами ДО. Чрезвычайно важным для иснслендования эффективности ЛА является вопрос: Всегда ли иснпользование ЛА в сочетании с некоторым алгоритмом ДО (для решения задач в блоках) эфнфективнее использования упомянутого алгоритма самого по себе?. Наряду с проведенным теоретическим анализом ОЭ ЛА, представляет значительный интерес провенденние соответствующего сравнительного вычислительного эксперимента с друнгинми алнгоритмами ДО. Понятно, что проведение исчерпывающего вычиснлинтельного экснперимента для ЛА в сочетании со всеми существующими алгонритмами ДО (или, по крайней мере, наиболее известными из них) преднставнляется чрезвычайно трудоемким. Поэтому было принято решение о проведении вначале лоценочного экснперимента с двумя алгоритмами:

  1. одним из наименее эффективных алгоритмов ДО, в качестве которого был избран алгоритм неявного перебора (НП) без использования линейных релаксаций;
  2. одним из наиболее эффективных алгоритмов ДО, в качестве которого был принят симплекс-метод в унимодулярном случае.

Цель лоценочного эксперимента выявить разницу в поведении ЛА в сончетании с очень эффективными алгоритмами (лоценка снизу) и слабо эфнфекнтивными (лоценка сверху). Вычислительный эксперимент показал следующие возможности локального алгоритма:

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

В параграфе 7.2 исследуются возможности снижения перебора при решении задач ДО с помощью ЛЭА на основе использования релаксаций при реализации локального алгоритма.

В параграфе 7.3 предложены приближенные схемы локальных алгоритмом: с оракулом; с неполным перебором сепараторов. Здесь исследуется приближенная версия локального элиминационного алгоритма, основанная на выборе перемычек между блоками с помощью некоего лоракула, который использует либо анализ релаксированной блочно-древовидной задачи ДО, либо случайный выбор, при больших перемычках используется перебор всех значений перемычек, принадлежащих некоторой окрестности Хемминга радиуса R лугаданной описанным выше оракулом близкой к оптимальной перемычки.

Параграф 7.4 посвящен анализу возможностей распараллеливания, которые можно использовать в локальном элиминационном алгоритме решения разреженных задач ДО: параллелизм, присущий ЛЭА (параллелизация, соответствующая каждому блоку) и параллелизм, возникающий из разреженности задачи (распараллеливание на основе элиминационного дерева).

В заключении перечислены основные результаты работы (см. раздел На защиту выносятся).

ИТЕРАТУРА

  1. Колмогоров А.Н. Комбинаторные основания теории информации и исчисление вероятностей // Успехи математических наук. 1983. Т. 38, № 4. С. 27-36.
  2. Журавлев Ю.И. Избранные научные труды. М.: Магистр, 1998. 420ас.
  3. Михалевич В.С. Последовательные алгоритмы оптимизации и их применение. 1. // Кибернетика. 1965. № 1. С. 45-56; П. // Кибернетика. 1965. №2. С. 85-88.
  4. Емеличев В.А. Дискретная оптимизация: последовательностные схемы решения. 1 // Кибернетика. 1971. № 6. С. 109-121. П. // Кибернетика. 1972. № 2. С.а92-103.
  5. Хачатуров В. Р., Веселовский В. Е., Злотов А. В. и др. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности. М.: Наука, 2000. 354 с.
  6. Беллман Р. Динамическое программирование. М.: Изд-во иностр. лит., 1960. 400 с.
  7. Neumaier A. Complete Search in Continuous Global Optimization and Constraint Satisfaction // A. Iserles (ed.): Acta Numerica. Cambridge University Press. 2004. P.а271-369.
  8. Neumaier A., Shcherbina O., Huyer W., Vinko T. A comparison of complete global optimization solvers // Math. Programming B. 2005. V. 103. P.а335-356.
  9. Корбут А. А., Сигал И. Х., Финкельштейн Ю. Ю. Гибридные методы в дискретной оптимизации // Системы программного обеспечения решения задач оптимального планирования. М.: ЦЭМИ АН СССР. 1986. С. 86-87.
  10. Сергиенко И. В., Шило В. П. Задачи дискретной оптимизации: проблемы, методы решения, исследования. К.: Наукова думка. 2003. 264ас.
  11. Сергиенко И. В., Шило В. П. Проблемы дискретной оптимизации: сложные задачи, основные подходы к их решению //аКибернетика и системный анализ. 2006. № 4. С.3-25.
  12. Woeginger G.J. Exact algorithms for NP-hard problems: A survey // M. Juenger, G. Reinelt and G. Rinaldi (eds.): ФCombinatorial Optimization Eureka! You shrink!Ф. LNCS 2570. Springer. 2003. P.а185-207.
  13. Архипова Т.Т., Сергиенко И.В.. Метод возможных направлений и метод вектора спада в целочисленном программировании // Кибернетика. 1975. № 5. С.а125-128.
  14. Емеличев В.А., Комлик В.И. Метод построения последовательности планов для решения задач дискретной оптимизации. М.: Наука, 1981. 208 с.
  15. Ковалев М.М., Пирьянович В.А. Локально-стохастические алгоритмы дискретной оптимизации (эксперименты, опыт, применения) // Кибернетика. 1982. №1. С. 108-114.
  16. Aarts E., Lenstra J.K. (eds.) Local Search in Combinatorial Optimization. New York: Wiley, 1997. 512 p.
  17. Кочетов Ю.А. Вычислительные возможности локального поиска в комбинаторной оптимизации // Журнал вычислительной математики и математической физики. 2008. Т.48, C. 747Ц764.
  18. Сергиенко И. В., Шило В. П. Проблемы дискретной оптимизации: сложные задачи, основные подходы к их решению //аКибернетика и системный анализ. 2006. № 4. С. 3-25.
  19. Dorigo M., Birattari M., Sttzle T., Ant colony optimization artificial ants as a computational intelligence technique // IEEE Computational Intelligence Magazine. 2006. V. 1. P. 28-39.
  20. Holland J. H. Adaptation in Natural and Artificial Systems. University of Michigan Press, 1975. 183 p.
  21. Dechter R. Constraint Processing. Morgan Kaufmann. 2003. 481аp.
  22. Журавлев Ю. И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. Часть I // Кибернетика.а1977.аN 4.аС. 5-17. Часть II //аКибернетика.а1977.аN 6.аС. 21-27. Часть III // Кибернетика.а1978.аN 2. С.а35-43.
  23. Береснев В. Л., Гимади Э. Х., Дементьев В. Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. 333 с.
  24. Емеличев В.А., Ковалев М.М. Полиэдральные аспекты дискретной оптимизации // Кибернетика. 1982. № 6. С. 54-62.
  25. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1975. 535 с.
  26. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.
  27. Cook S.A. An overview of computational complexity // ACM Communications. 1983. V. 26. P. 400-408.
  28. Downey R.G., Fellows M.R. Parametrized complexity. Monographs in Computer Science. Springer-Verlag, 1999. 533 p.
  29. Емеличев В. А., Ковалев М. М., Кравцов М. К. Многогранники, графы, оптимизация. М.: Наука, 1981. 344 с.
  30. Бахтин А. Е., Колоколов А. А. Декомпозиционный метод решения целочисленных производственно-транспортных задач // Вопросы анализа сложных систем. Новосибирск, 1974. С. 15-36.
  31. Верина Л. Ф., Танаев В. С. Декомпозиционные подходы к решению задач математического программирования // Экономика и математические методы. 1976. № 6. С. 1160-1172.
  32. Ковалев М. Я. Декомпозиционный подход к построению Е-оптимальных приближенных алгоритмов // Математическое и прогр. обеспечение вычислит. систем. Минск. 1985. С. 3-8.
  33. Кравец В. Л., Сергиенко И. В. Декомпозиционный метод решения одного класса комбинаторных оптимизационных задач // Кибернетика. 1983. №6. С.а77-84.
  34. Рощин В. А., Семенова Н. В., Сергиенко И. В. Декомпозиционный подход к решению некоторых задач целочисленного программирования с неточными данными // Журн. вычисл. математики и матем.физики. 1990. 29. № 5. С.а786-791.
  35. Сергиенко И. В., Голодников А. Н. О применении метода вектора спада в декомпозиционных схемах решения задач целочисленного линейного программирования // Кибернетика. 1984. № 1. С. 44-47.
  36. Танаев В. С. Декомпозиция и агрегирование в задачах математического программирования. Минск: Наука и техника, 1987. 183 с.
  37. Уздемир А. П. Схема последовательной декомпозиции в задачах оптимизации // Автоматика и телемеханика. 1980. №11. С. 94-105.
  38. Авербах И. Л., Цурков В. И. Оптимизация в больших задачах с целочисленными переменными. М.: Наука, Физматлит. 1995. 288 с.
  39. Nowak I. Lagrangian decomposition of block-separable mixed-integer all-quadratic programs // Math. Programming. 2005. V. 102, N 2. P.295312.
  40. Vanderbeck F., Savelsbergh M. W. P. A generic view of Dantzig-Wolfe decomposition for integer programming // Operations Research Letters. 2006. V. 34. P.а296-306.
  41. Benders J. F. Partitioning procedures for solving mixed variables programming problems // Numerische Mathematik. 1962. V. 4, N 3. P. 238-252.
  42. Barnhart C., Johnson E. L., Nemhauser G. L., Savelsbergh M. W. P., Vance P.H. Branch and price: Column generation for solving huge integer programs // Operations Research. 1998. V. 46. P. 316Ц329.
  43. Martin A. Integer programs with block structure, Habilitations-Schrift. Berlin: Technische Universitt, 1998. 217 p.
  44. Lbel A. Optimal Vehicle Scheduling in Public Transit. PhD thesis. Berlin: Technische Universitt Berlin, 1997.
  45. Заозерская Л. А., Китриноу Е., Колоколов А. А. Задача оптимального размещения центров телекоммуникаций в регионе // Труды 13-й Байкальской международной школы-семинара Методы оптимизации и их приложения. Т.1. Иркутск, 2005. C. 469-475.
  46. Koster A. M. C. A., van Hoesel S. P. M, Kolen A. W. J. Solving frequency assignment problems via tree decomposition // Electronic Notes in Discrete Mathematics. 1999. V. 3.
  47. Stougie L., van der Vlerk M. H. (1997). Stochastic Integer Programming //а Annotated Bibliographies in Combinatorial Optimization / M. Dell'Amico, F. Maffioli, S.аMartello (eds). Chichester: John Wiley & Sons Ltd, 1997, chapter 9, pp. 127-141.
  48. Ahuja R. K., Magnanti T. L., Orlin J. B. Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs: Prentice-Hall, 1993. 846 p.
  49. Ferreira C. E. On Combinatorial Optimization Problems Arising in Computer System Design. PhD thesis. Berlin: Technische Universitt, 1994.
  50. Bertele U., Brioschi F. Nonserial Dynamic Programming. New York: Academic Press, 1972. 235 p.
  51. Dechter R. Bucket elimination: A unifying framework for reasoning // Artificial Intelligence. 1999. V. 113. P.а41-85.
  52. Hicks I. V., Koster A. M. C. A., Kolotoglu E. Branch and Tree Decomposition Techniques for Discrete Optimization // Tutorials in Operations Research. New Orleans: INFORMS. 2005. P.а1-29.
  53. Courcelle B. The monadic second-order logic of graphs I: Recognizable sets of finite graphs // Information and Computation. 1990. V. 85. P.а12-75.
  54. Arnborg S., Corneil D. G., Proskurowski A. Complexity of finding embeddings in a k-tree // SIAM J. Alg. Disc. Meth. 1987. V. 8. P.а277-284.
  55. Cook W., Seymour P. D. Tour merging via branch-decomposition //аINFORMS Journal on Computing. 2003. V. 15, N3. P.а233-248.
  56. Dantzig G. B. Programming of interdependent activities II: Mathematical model //аEconometrica. 1949. V. 17. P. 200-211.
  57. Ho J. K., Loute E. A set of staircase linear programming test problems // Mathematical Programming. 1981. 20. P. 245-250.
  58. Bartlett M., Frisch A. M., Hamadi Y., Miguel I., Tarim S. A., and Unsworth C. The Temporal Knapsack Problem and its solution // Second International Conference on the Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR, May 2005). P. 34-48.
  59. Иванилов Ю. П., Пропой А. И. О задачах линейного динамического программирования // Докл. АН СССР. 1971. 198, №5. С. 1011-1014.
  60. Мезон Р., Фламгольц Э. Управление трудовыми ресурсами // Исследование операций. М.: Мир, 1981. Т.2: Модели и применения. С. 34-50.
  61. Оптимизация развития топливно-энергетического комплекса. / Под ред. А.аС. Некрасова М.: Энергоиздат, 1981. 240 с.
  62. Финкельштейн Ю. Ю. Об одном классе задач дискретного программирования // Экономика и матем. методы. 1968. Т. 4, № 4. С.а652-655.
  63. Журавлев Ю. И., Финкельштейн Ю. Ю. Локальные алгоритмы для задач линейного целочисленного программирования // Проблемы кибернетики. М.: Наука. 1965. Вып.14. С. 289-296.

  Публикации по теме диссертации

  1. Щербина О. А. Локальные элиминационные алгоритмы для задач удовлетворения ограничений // Таврический вестник информатики и математики. 2007. №1. С. 24-39.
  2. Щербина О. А. Экономико-математические модели развития и размещения рекреационных систем // Экономика и матем. методы. 1982. Т. 18, № 2. С. 344-348.
  3. Щербина О. А. Локальные элиминационные алгоритмы решения разреженных дискретных задач // Журнал вычислительной математики и математической физики. 2008. Т. 48, N 1. С.161Ц177.
  4. Щербина О. А. О локальных алгоритмах решения квазиблочных задач дискретного программирования // Проблемы кибернетики. М.: Наука. 1983. Вып. 40. С. 171-200.
  5. Щербина О. А. О несериальной модификации локального алгонритма декомпозиции задач дискретной оптимизации // Динамические системы. 2005. Вып.а19. С.а179-190.
  6. Neumaier A., Shcherbina O. Nonserial dynamic programming and local decomposition algorithms in discrete programming.

URL:

  1. Щербина О. А. Древовидная декомпозиция и задачи дискретной оптимизации (обзор) // Кибернетика и системный анализ. 2007. № 4. С. 102-118.
  2. Щербина О. А. Об одном локальном алгоритме для задач целочисленной оптимизации // Журн. вычисл. математики и матем. физики. 1980. Т. 20, Nа3. С.а802-604.
  3. Щербина О. А. Асимптотические оценки эффективности локального алгоритма в дискретном программировании. // Журн. вычисл. математики и матем. физики. 1982. Т. 22, № 6. С. 1360-1366.
  4. Щербина О.А., Матвеев В.В. Оценки эффективности локального алгоритма для задач дискретной оптимизации // Тезисы докладов IX Межреспубликанской конференции молодых ученых. Минск: НИИЭМП. 1982. С. 141-142.
  5. Щербина О.А., Матвеев В.В. Об эффективности локальных алгоритмов решения квазиблочных задач целочисленного линейного программирования // Динамические системы. Киев: Вища школа. 1983. Вып.а2. С. 94-97.
  6. Щербина О. А. О локальных алгоритмах решения задач дискретного программирования специальной структуры // Х Internationaler Kongress ber Anwendungen der Mathematik in den Ingenieur Wissenschaften. Weimar. 1984. B. 4. S. 84-87.
  7. Щербина О. А. О решении квазиблочных задач целочисленного линейного программирования с помощью локального алгоритма // Кибернетика. 1984. №а2. С. 118-121.
  8. Щербина О. А. Локальные алгоритмы для блочно-древовидных задач дискретного программирования // Журн. вычисл. математики и матем. физики. 1985. Т. 25, N 8. С. 1143-1154.
  9. Щербина О. А. О модифицированном локальном алгоритме решения блочных задач дискретного программирования // Журн. вычисл. математики и матем.физики. 1986. Т. 26, № 9. С. 1339-1349.
  10. Щербина О. А. О квазиблочных задачах дискретного программирования с дополнительными ограничениями // Журн. вычисл. математики и матем. физики. 1987. Т. 27, N 5. С. 676-687.
  11. Щербина О. А. Применение локальных алгоритмов к решению задач целочисленного линейного программирования // Вопросы кибернетики. М.: НСК АН СССР. 1989. C.а19-34.
  12. Щербина О. А. Локальные алгоритмы и древовидная декомпозиция для задач дискретной оптимизации // Динамические системы. 2006. Вып. 20. C.а89103.
  13. Щербина О. А. Об одной унимодулярной задаче целочисленного программирования // Журн. вычисл. математики и матем. физики. 1986. Т.а26, N 7. С.а1096-1099.
  14. Щербина О. А. О локальных алгоритмах с переменными окрестностями и индикаторной информацией // Журн. вычисл. математики и матем. физики. 1986. Т. 26, N 10. С. 1588-1591.
  15. Щербина О. А. Постоптимизационный анализ в дискретном программировании (обзор) // Методы оптимизации в экономико-математическом моделировании. М.: ЦЭМИ АН СССР. 1988. С. 28-50.
  16. Щербина О. А. Элиминационные алгоритмы декомпозиции задач дискретной оптимизации // Таврический вестник информатики и математики. 2006. №2. С.а28-41.
  17. Щербина О. А. Роль графовых структур в теории локальных элиминационных алгоритмов // Динамические системы. 2008. Вып. 24. C. 8398.
  18. Щербина О. А., Канаева Н. Н. Об экстремальных свойствах сумм биномиальных коэффициентов // Динамические системы. 2000. Вып.а16. С.а192-197.
  19. Щербина О. А. Локальные элиминационные алгоритмы для решения некоторых задач искусственного интеллекта // Труды 11 Национальной конференции по искусственному интеллекту (Дубна, 28 сентября - 3 октября 2008 г.). М.: ЛЕНАНД, 2008. Т. 2. С. 244-252.
  20. Щербина О. А. Локальные элиминационные алгоритмы обработки запросов в базах данных // Таврический вестник информатики и математики. 2009. №2. С. 53-62.
  21. Shcherbina O., Neumaier A., Sam-Haroud D., Vu X.-H., Nguyen T.-V. Benchmarking global optimization and constraint satisfaction codes // Ch. Bliek, Ch. Jermann and A. Neumaier (eds.): Global Optimization and Constraint Satisfaction. - Berlin: Springer. 2003. P.а211-222.
  22. Shcherbina О. А. Nonserial dynamic programming and tree decomposition in discrete optimization // Applied Optimization and Metaheuristic Innovations (Abstracts of Int.Conference, Yalta, July 19-21, 2006). 2006. P. 45-46.
  23. Shcherbina O. Nonserial dynamic programming and tree decomposition in discrete optimization // Proceedings of Int. Conference on Operations Research УOperations Research 2006Ф (Karlsruhe, 6-8 September, 2006). Berlin: Springer Verlag, 2007. P. 155-160.
  24. Shcherbina O. Postoptimal analysis in nonserial dynamic programming / In: Proceedings of Second International Conference MCO 2008 УModelling, Computation and Optimization in Information Systems and Management SciencesФ, Metz, France Luxembourg, September 8-10, 2008. Communications in Computer and Information Science. Volume 14. Berlin Heidelberg: Springer. 2008. P. 308-317.
  25. Shcherbina O. Graph-Based Local Elimination Algorithms in Discrete Optimization // Foundations of Computational Intelligence Volume 3. Global Optimization Series: Studies in Computational Intelligence, Vol.а203 / A. Abraham; A.-E. Hassanien; P. Siarry; A. Engelbrecht (Eds.). Springer Berlin / Heidelberg. 2009, XII, 528 p. P. 235-266.
  26. Shcherbina O. Tree decomposition and postoptimality analysis in discrete optimization // arXiv:0903.4435v1 [cs.DM] (2009).
  27. Канаева Н. Н., Щербина О. А. О локальном алгоритме для задач дискретного программирования квазиблочной структуры с дополнительными ограничениями // Вычислительная математика в современном научно-техническом прогрессе. Тез.докл. респ.конф. Киев: ИК АН УССР. 1982. С. 90-91.
  28. Канаева Н. Н., Щербина О. А. О модифицированном локальном алгоритме для задач дискретного программирования // Журн. вычисл. математики и матем.физики. 1986. 26, № 2. С. 263-275.
  29. Канаева Н. Н., Щербина О. А. Об эффективности модифицированного локального алгоритма для задач дискретной оптимизации // Журн. вычисл. математики и матем.физики. 1984. 24, № 10. С. 1520-1530.
  30. Канаева Н. Н., Щербина О. А. Об эффективности модифицированного локального алгоритма // Республиканский семинар по дискретной оптимизации. Тезисы докладов. Киев: ИК АН УССР. 1985. С. 57-58.
  31. Иловайская Е. И., Щербина О. А. О вычислительных аспектах реализации локальных алгоритмов решения задач дискретной оптимизации //аДинамические системы. 1990. Вып. 9. С.а117-122.
  32. Матвеев В. В., Щербина О. А. Об одном классе локальных алгоритмов решения квазиблочных задач целочисленного линейного программирования //аКибернетика. 1984. № 6. С. 116-118.
  33. Матвеев В. В., Щербина О. А. Локальные алгоритмы решения задач дискретной оптимизации // Тезисы международной конференции по математическим методам в исследовании операций. София. 1983. С. 55-56.
  34. Матвеев В. В., Щербина О. А. Модели оптимального резервирования ресурсов, распределенных во времени // Оптимизационные задачи в автоматизированной системе плановых расчетов. Минск: НИИЭМП. 1982. С. 98-104.
  35. Матвеев В. В., Щербина О. А. Эффективность локальных алгоритмов решения квазиблочных задач целочисленного линейного программирования //аСистемы программного обеспечения решения задач оптимального планирования. М.: ЦЭМИ АН СССР. 1982. С. 85-87.
  36. Быстров В. А., Щербина О. А. О модифицированном локальном алгоритме декомпозиции блочных задач дискретного граммирования //аДекомпозиция и координация в сложных системах. Ч.1. Челябинск: ЧПИ, 1986. С. 57-58.
  37. Быстров В. А., Щербина О. А. О среднем значении оценки эффективности модифицированного локального алгоритма в квазиблочном случае // Системы программного обеспечения решения задач оптимального планирования. М.: ЦЭМИ АН СССР. 1986. С. 69.
  38. Быстров В. А., Щербина О. А. Об эффективности решения одного класса задач дискретного программирования с помощью локального алгоритма //аКибернетика. 1987. № 3. С. 96-101.

1 В системе мобильной телефонной связи коммуникация между парами телефонов достигается за счет беспроводных соединений, использующих частоты из некоторой полосы. Задача назначения частот (ЗНЧ) (Frequency Assignment Problem (FAP)) является трудной дискретной задачей, тесно связанной с задачей раскраски графа.

Авторефераты по всем темам  >>  Авторефераты по техническим специальностям