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

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

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

ЛОКАЛЬНЫЕ ЭЛИМИНАЦИОННЫЕ АЛГОРИТМЫ ДЛЯ РАЗРЕЖЕННЫХ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ

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

АВТОРЕФЕРАТ

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

1 7 МАР 2011

Москва - 2011

4840883

Работа выполнена в Таврическом национальном университете им. В.И. Вернадского (г. Симферополь, Украина)

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

профессор,

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

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

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

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

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

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

кибернетики Московского государственного университета им. М.В. Ломоносова.

Защита диссертации состоится^^. 1 г. в час.

на заседании диссертационного совета Д 002.017.02 в Учреждении Российской академии наук Вычислительный центр имени А.А.Дородницына РАН по адресу:

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

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

Автореферат разослан "¿У" ^#¿#¿3^2011 г.

Ученый секретарь диссертационного совета Д 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]. Одной из наиболее важных теоретических проблем в теории сложности является известная проблема «Р^НР?». В теории сложности используются в числе прочих понятия временной и емкостной сложности алгоритма. Грубо говоря, под временной сложностью понимается время работы алгоритма (оцениваемое числом шагов), под емкостной сложностью - объем памяти, необходимый алгоритму для решения задачи.

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

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

Отметим работы В. А. Емеличева [29], в которых сложность решения задачи линейного программирования оценивается косвенно, путем нахождения диаметра многогранника допустимых решений.

В связи о вышесказанным приобретает особую актуальность разработка в ДО декомпозиционных подходов [30 - 40].

Как известно, метод декомпозиции впервые был использован для решения задач смешанного целочисленного программирования в [41], позднее были развиты и другие методы декомпозиции. Принцип декомпозиции Данцига-Вулфа для задач ЛП имеет аналог в целочисленном программировании [40]. Этот подход использует мастер-задачу целочисленного ЛП (ЦЛП), которая неявно решает задачу ЦЛП с большим числом переменных с помощью процедуры построения столбцов задачи ЦЛП, известную как алгоритм ветвей и оценок (ЬгапсЬ-апс1-рпсе) [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, был класс квазиблочных задач ЛГ1 для динамического планирования [56]. Другие примеры квазиблочных задач ЛП для многоэтапного планирования, составления расписаний, назначений и многоэтапного структурного проектирования содержатся во множестве тестовых квазиблочных задач, опубликованных Но & Loute [57]. Квазиблочную структуру имеют задачи оптимального резервирования гостиничных номеров. [82], аналогичные последним темпоральные задачи о ранце [58], получившие в последнее время применение при

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

решении задач предварительного резервирования вычислительных ресурсов в Grid Computing, задачи линейного динамического программирования [59], некоторые задачи управления трудовыми ресурсами [60], динамические модели экономики, учитывающие в явном виде фактор времени [61], задачи управления в иерархических (обычно древовидных) структурах, сетевые задачи, задачи многоэтапного стохастического программирования.

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

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

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

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

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

• Исследование возможностей распространения локального элиминационного алгоритма на различные классы задач ДО.

• Использование JIA совместно с методами древовидной декомпозиции.

• Теоретическое и экспериментальное исследование эффективности локального элиминационного алгоритма, анализ и выделение классов блочных задач ДО, достаточно эффективно решаемых локальным элиминационным алгоритмом.

• Исследование возможностей снижения перебора ЛЭА на основе использования релаксаций, селектора, распараллеливания вычислительного процесса.

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

1. Разработана общая алгоритмическая схема локальных элиминаци-оппых алгоритмов для решения широкого класса разреженных дискретных задач. Эти алгоритмы используют структуру дискретной задачи и вычисляют глобальную информацию на основе локальных вычислений, используя понятие «близости переменных», основанное на использовании топологических окрестностей переменных, отражающих структуру дискретной задачи. При этом дискретные задачи могут быть как задачами дискретной оптимизации, так и носить неоптимизационный характер: дискретные задачи удовлетворения ограничений и дискретные задачи обработки запросов в реляционных базах данных. Структура разреженных дискретных задач задается с помощью графового и гиперграфового представлений.

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

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

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

5. Поставлен и решен вопрос о целесообразности изучения блочно-древовидных структур на основе исследования оценок эффективности.

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

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

7. Исследовано типичное поведение локального элиминационного алгоритма на различных блочных структурах на основе анализа среднего значения оценки эффективности локального элиминационного алгоритма. Показано, что асимптотическая средняя оценка эффективности локального алгоритма в случае блочно-древовидной структуры с п переменными и к блоками без дополнительных ограничений находится в пределах между С'(к)-2"и С"(к)-2" /п*-2-""'' (к>2), где с1г - степень вершины г в структурном графе задачи дискретной оптимизации. Показано, что самым лучшим (в смысле минимума асимптотической средней оценки эффективности локального алгоритма) является случай квазиблочной структуры.

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

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

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

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

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

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

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

Апробация работы. Основные результаты диссертации докладывались и обсуждались на семинаре отдела математических проблем распознавания и методов комбинаторного анализа Вычислительного Центра имени А. А. Дородницына РАН, на семинаре кафедры Computational Mathcmatics Венского университета (Австрия), семинаре кафедры Production and Operations Management Венского университета (Vienna, 24.1.2005); International Workshop "Graph and Hypergraph Décompositions -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 г.); Международных конференциях X 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, 68 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], [101-104] В. В. Матвееву принадлежат конкретные результаты применения локального алгоритма в частном случае, а автору диссертации - принадлежит общая схема метода и руководство работой; в совместных работах [87], [96-99] Канаевой Н.Н. принадлежат конкретные результаты применения локального алгоритма в частном случае наличия дополнительных ограничений, а автору диссертации - принадлежит общая схема метода и руководство работой; в совместной работе [100] Иловайской Е. И. выполнена работа по программированию и машинный эксперимент под руководством автора диссертации; в совместных работах [105-107] Быстрову В. А. принадлежат конкретные результаты применения локального алгоритма в частном случае, а автору диссертации - принадлежит общая схема метода и руководство работой.

Структура и объем работы. Диссертация состоит из списка обозначений, сокращений и определений, введения, 7 глав, заключения и списка литературы, содержащего 593 названий. Общий объем диссертации 357 страниц.

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

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

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

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

В параграфе 1.3 предлагается локальный декомпозиционный алгоритм решения блочно-древовидных задач ДО: приводятся основные определения и понятия, необходимые для дальнейшего изложения; в том числе анализируется понятие окрестности переменной в задаче ДО, показано, что эта окрестность изоморфна графовым окрестностям; дается определение блочно-древовидной задачи ДО, показано, что на каждом шаге локального алгоритма осуществляется присваивание фиксирр-ванных значений некоторому множеству переменных (в отличие от локального алгоритма А, на каждом шаге которого фиксированное значение присваивается лишь одной переменной). Отмеченное различие иллюстрируется на примере. Приводится частный случаи блочно-древовидной структуры - квазиблочная (или лестничная) структура, показаны особенности реализации локального алгоритма для этой структуры, показано, что локальный алгоритм в этом случае является локальным алгоритмом с переменными окрестностями и индикаторной информацией. ЛА 2СВТ предназначен для решения блочно-древовидных задач ДО, т.е. задач, в которых возможно выделить систему окрестностей различных переменных такую, что одна переменная может быть обшей самое большее лишь для двух окрестностей и граф пересечений этих окрестностей представляет собой дерево. С помощью ЛА ЗГВТ можно решить подобную задачу ДО, двигаясь от окрестностей, соответствующих листьям дерева, к окрестности, соответствующей корню дерева. Введем необходимые понятия. Пусть О, =(^,£7,), П2 = (52,и2), ..., 0.к =(Бк,11кУ-система окрестностей некоторых переменных , где Vг - соответственно множества индексов переменных и ограничений для г-й окрестности, г = 1,...,к, причем

(}иг=М={1....,т}.(]Бг = Ы = {1.....п}, иг,(]иг1=0, г{ Фг2, П^ П^ = 0 для

любой тройки индексов гр г2, гъ.

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

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

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

Бриоши-, алгоритмом сегментной элиминации Дехтер для решения задач удовлетворения ограничений; с элиминационными алгоритмами в линейной алгебре.

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

учитывающие подобие окрестностей отдельных переменных; локальные алгоритмы, использующие древовидную структурную декомпозицию. Выявлены аналоги двух основных теорем классической теории локальных алгоритмов: теорема о мажорант-ности локального элиминационного алгоритма и теорема о единственности результата элиминации переменных независимо от порядка их элиминации. Предложен локальный элиминациомный алгоритм, использующий древовидную структурную декомпозицию, являющийся обобщением локального декомпозиционного алгоритма, описанного в главе I. В параграфе 2.3 рассмотрено применение локальных эли-минационных алгоритмов при решении неоптимизационных разреженных дискретных задач информатики. Описаны особенности реализации вычислительной схемы локальных элиминацнонных алгоритмов при решении задач удовлетворения ограничений, а также при решении задачи выполнимости SAT, заданной в конъюнктивной нормальной форме. Описаны особенности реализации вычислительной схемы локальных элиминационных алгоритмов при решении задач обработки запросов в реляционных базах данных.

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

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

Глава IV посвящена оценкам вычислительной сложности локального алгоритма и выяснению условий целесообразности его использования. В параграфе 4.1 рассматриваются некоторые вопросы теории сложности алгоритмов решения задач ДО. Вводится используемое в дальнейшем понятие вычислительной сложности алгоритма ДО, называемой оценкой эффективности алгоритма, рассматриваются оценки сложности «в среднем» и «наихудшем случае», анализируется возможность нахождения асимптотической оценки вычислительной сложности. В параграфе 4.2 вводятся оценки эффективности локального алгоритма, соответствующие различным блочным структурам, сформулированы основные цели исследования оценок эффективности локального элиминационного алгоритма на классе задач ДО. Вводя обозначения nrr, =|5r,,j, БД структуру описываем здесь деревом пересече-

ния блоков D и вектором N = 1{пг}кг Г{пгг,}, I, причем + ^ пгг, = «.

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

Г—1

Рассмотрим вопрос об оценке эффективности JTA с селектором C(v) для решения задач ДО с БД структурой и дополнительными ограничениями многократного выбора ^ х/ < vp, р= 1 ,...,N, здесь в сочетании с JIA рассматривается лишь ал-

J^p

горитм полного перебора, перебирающий допустимые решения дополнительных ограничений (обозначим этот алгоритм А^ (v))- Введем необходимые обозначения:

- число переменных, входящих только в окрестность Qr и р -е дополнительное ограничение многократного выбора; - число переменных, входящих в пересечение окрестностей fi и в р-е дополнительное ограничение многократного выбора (здесь р = ],..., N). ОЭ ЛА в этом случае имеет вид:

к N ( vr ^

ЕХвт (п, к, Z, N„ D, C(v), A,J(v)) = ХП S С%,у

г П- ргг

ОЭ ЛА 'Я яг с селектором 1 для решения задач ДО с БД структурой и дополнительными ограничениями многократного выбора одновариантного типа, т.е. ]Г х< 1, р = 1,..., Ы, имеет вид:

> м г

(„. 2, N.. О, С(I), * (I)) = ХП 1 + Р + I # + «

\

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

р=1 />=1 г'е/г у

>\,р = ],..., N.

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

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

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

2» 2"

алгоритма в этом случае находится в пределах от С, — до С, —для произвольного

п п

алгоритма, с помощью которого решаются задачи внутри блоков. Кроме того, показано, что асимптотическая средняя оценка эффективности локального алгоритма в случае блочно-древовидной структуры с п переменными и к блоками без дополнительных ограничений находится в пределах между С'(к)-2" /и2*-'-"шЫ' и С"[к)-2" / п1к~г'тах^ (к>2), где с1г - степень вершины г в структурном графе задачи дискретной оптимизации, далее найдена наихудшая асимптотическая средняя оценка эффективности локального алгоритма в случае блочно-древовидной структуры без дополнительных ограничений (при тахс1г = к-Ь + 2 - «метла» или «звезда», где Ь - число слоев в структурном графе (дереве) задачи дискретной оптимизации), что позволяет выделить наихудшую блочно-древовидную структуру. Показано, что самым лучшим (в смысле минимума асимптотической средней оценки эффективности локального алгоритма) является случай Ь = к, что соответствует квазиблочной структуре. Здесь показана слабая зависимость средней оценки эффективности локального элиминационного алгоритма от эффективности алгоритма ДО, с помощью которого решаются задачи в блоках.

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

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

Е(<р,п,к,п)

пк~1

<р(п) = 2\

-ЛГТ. <Р(п) = — п п

<р(п) = п',

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

= qj >2, у" = 1 ,...,п. Справедлива асимптотическая оценка:

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

(„. *. Z. N], вк,с{ I), л5 (!)) ~

\ЛГ+*Ч

7*"-

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

ЕЖщ (п, к, Z, N„Bk,c(I), 4 (I)) С'н - СГ1 ■ N" /п"

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

п р

п

EUm (и, к, Z, N], D, С(у), 4 (v)) ~ J, N^ со, где d' =maxdr.

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

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

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

N

Е -¿1. - - при П, N оо.

-:вт drJ п2к'г

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

С'(к)■ 2"7 пк+/-тах"' <ЕЖ> (п,кЯ) <С"{к)-2п/п'

к+/~тахс1г-\

(к> 2).

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

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

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

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

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

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

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

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

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

Е (п,к,г,М;,С,С(У),А;(У)) ^ ц£с?

/>=11^

с.с

N ( V, Л

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

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

2) одним из наиболее эффективных алгоритмов ДО, в качестве которого был принят симплекс-метод в унимодулярном случае.

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

• «Оценочный» машинный эксперимент выявил разницу в поведении ЛА в сочетании с очень эффективными алгоритмами («оценка снизу») и слабо эффективными («оценка сверху»),

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

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

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

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

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

В параграфе 7.3 предложены приближенные схемы локальных алгоритмом: с оракулом; с неполным перебором сепараторов. Здесь исследуется прибли-

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

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

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

ЛИТЕРАТУРА

1. Колмогоров А.Н. Комбинаторные основания теории информации и исчисление вероятностей // Успехи математических наук. 1983. Т. 38, № 4. С. 27-36.

2. Журавлев Ю.И. Избранные научные труды. М.: Магистр, 1998.420 с.

3. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. 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 Numérica. 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. Корбут А. А., Сигал И. X., Финкелыптейн Ю. Ю. Гибридные методы в дискретной оптимизации // Системы программного обеспечения решения задач оптимального планирования. М.: ЦЭМИ АН СССР. 1986. С. 86-87.

Ю.Сергиенко И. В., Шило В. П. Задачи дискретной оптимизации: проблемы, методы решения, исследования. К.: Наукова думка. 2003. 264 с.

П.Сергиенко И. В., Шило В. П. Проблемы дискретной оптимизации: сложные задачи, основные подходы к их решению // Кибернетика и системный анализ. 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.Архипова T.T., Сергиенко И.В.. Метод возможных направлений и метод вектора спада в целочисленном программировании // Кибернетика. 1975. № 5. С. 125-128.

14.Емеличев В.А., Комлик В.И. Метод построения последовательности планов для решения задач дискретной оптимизации. М.: Наука, 1981. 208 с.

15.Ковалев М.М., Пирьянович В.А. Локально-стохастические алгоритмы дискретной оптимизации (эксперименты, опыт, применения) // Кибернетика. 1982. №1. С. 108-114.

16.Aarts Е., Lenstra J.K. (eds.) Local Search in Combinatorial Optimization. New York: Wiley, 1997.512 р.

17.Кочетов Ю.А. Вычислительные возможности локального поиска в комбинаторной оптимизации // Журнал вычислительной математики и математической физики. 2008. Т.48, С. 747-764.

18.Сергиенко И. В., Шило В. П. Проблемы дискретной оптимизации: сложные задачи, основные подходы к их решению // Кибернетика и системный анализ. 2006. №4. С. 3-25.

19.Dorigo М., Birattari М., Stiitzle Т., Ant colony optimization - artificial ants as a computational intelligence technique // IEEE Computational Intelligence Magazine. 2006. V. l.P. 28-39.

20.Holland J. H. Adaptation in Natural and Artificial Systems. University of Michigan Press, 1975. 183 p.

21.DechterR. Constraint Processing. Morgan Kaufinann. 2003.481 p.

22.Журавлев Ю. И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. Часть I // Кибернетика. 1977. № 4. С. 5-17. Часть II // Кибернетика. 1977. № 6. С. 21-27. Часть III // Кибернетика. 1978. № 2. С. 3543.

23.Береснев В. Л., Гимади Э. X., Дементьев В. Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 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.Емеличев В. А., Ковалев M. M., Кравцов М. К. Многогранники, графы, оптимизация. М.: Наука, 1981. 344 с.

30.Бахтин А. Е., Колоколов А. А. Декомпозиционный метод решения целочисленных производственно-транспортных задач // Вопросы анализа сложных систем. Новосибирск, 1974. С. 15-36.

31 .Верина Л. Ф., Танаев В. С. Декомпозиционные подходы к решению задач математического программирования // Экономика и математические методы. 1976. №6. С. 1160-1172.

32.Ковалев М. Я. Декомпозиционный подход к построению Е-оптимальных приближенных алгоритмов // Математическое и прогр. обеспечение вычислит, систем. Минск. 1985. С. 3-8.

33.Кравец В. JL, Сергиенко И. В. Декомпозиционный метод решения одного класса комбинаторных оптимизационных задач // Кибернетика. 1983. №6. С. 77-84.

34.Рощин В. А., Семенова Н. В., Сергиенко И. В. Декомпозиционный подход к решению некоторых задач целочисленного программирования с неточными данными // Журн. вычисл. математики и матем.физики. 1990. 29. № 5. С. 786791.

35.Сергиенко И. В., Голодников А. Н. О применении метода вектора спада в декомпозиционных схемах решения задач целочисленного линейного программирования // Кибернетика. 1984, № 1. С. 44-47.

36.Танаев В. С. Декомпозиция и агрегирование в задачах математического программирования. Минск: Наука и техника, 1987. 183 с.

37.Уздемир А. П. Схема последовательной декомпозиции в задачах оптимизации // Автоматика и телемеханика. 1980. №11. С. 94-105.

ЗВ.Авербах И. JI., Цурков В. И. Оптимизация в больших задачах с целочисленными переменными. М.: Наука, Физматлит. 1995. 288 с.

39.Nowak I. Lagrangian decomposition of block-separable mixed-integer all-quadratic programs // Math. Programming. 2005. V. 102, N 2. P.295-312.

40.Vanderbeck F., Savelsbcrgh M. W. P. A generic view of Dantzig-Wolfe decomposition for integer programming // Operations Research Letters. 2006. V. 34. P. 296306.

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 Universität, 1998. 217 p.

44.Löbel A. Optimal Vehicle Scheduling in Public Transit. PhD thesis. Berlin: Technische Universität Berlin, 1997.

45.3аозерская JI. А., Китриноу E., Колоколов А. А. Задача оптимального размещения центров телекоммуникаций в регионе // Труды 13-й Байкальской международной школы-семинара «Методы оптимизации и их приложения». Т.1. Иркутск, 2005. С. 469-475.

46.Koster А. М. С. 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 С. E. On Combinatorial Optimization Problems Arising in Computer System Design. PhD thesis. Berlin: Technische Universität, 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.

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

64.Щербина О. А. Локальные элиминационные алгоритмы для задач удовлетворения ограничений // Таврический вестник информатики и математики. 2007. №1. С. 24-39.

65.Щербина О. А. Экономико-математические модели развития и размещения рекреационных систем // Экономика и матем. методы. 1982. Т. 18, № 2. С. 344348.

66.Щербина О. А. Локальные элиминационные алгоритмы решения разреженных дискретных задач // Журнал вычислительной математики и математической физики. 2008. Т. 48, N 1. С.161-177.

67. Щербина О. А. О локальных алгоритмах решения квазиблочных задач дискретного программирования // Проблемы кибернетики. М.: Наука.

1983. Вып. 40. С. 171-200.

68.Щербина О. А. О несериальной модификации локального алгоритма декомпозиции задач дискретной оптимизации // Динамические системы. 2005. Вып. 19. С. 179-190.

69.Neumaier A., Shcherbina О. Nonserial dynamic programming and local decomposition algorithms in discrete programming.

URL: http://www.optimization-online.org/DB\ HTML/2006/03/1351 .html

70.1Цербина О. А. Древовидная декомпозиция и задачи дискретной оптимизации (обзор) // Кибернетика и системный анализ. 2007. № 4. С. 102-118.

71.Щербина О. А. Об одном локальном алгоритме для задач целочисленной оптимизации // Жури, вычисл. математики и матем. физики. 1980. Т. 20, N 3. С. 802-604.

72. Щербина О. А. Асимптотические оценки эффективности локального алгоритма в дискретном программировании. // Журн. вычисл. математики и матем. физики. 1982. Т. 22, № 6. С. 1360-1366.

73.Щербина O.A., Матвеев В.В. Оценки эффективности локального алгоритма для задач дискретной оптимизации // Тезисы докладов IX Межреспубликанской конференции молодых ученых. Минск: НИИЭМП. 1982. С. 141-142.

74.Щербина O.A., Матвеев В.В. Об эффективности локальных алгоритмов решения квазиблочных задач целочисленного линейного программирования // Динамические системы. Киев: Вища школа. 1983. Вып. 2. С. 9497.

75.Щербииа О. А. О локальных алгоритмах решения задач дискретного программирования специальной структуры // X Internationaler Kongress über Anwendungen der Mathematik in den Ingenieur Wissenschaften. Weimar. 1984. B. 4. S. 84-87.

76.Щербина О. А. О решении квазиблочиых задач целочисленного линейного программирования с помощью локального алгоритма // Кибернетика.

1984. №2. С. 118-121.

77. Щербина О. А. Локальные алгоритмы для блочно-древовидиых задач дискретного программирования // Журн. вычисл. математики и матем. физики. 1985. Т. 25, N 8. С. 1143-1154.

78.Щербина О. А. О модифицированном локальном алгоритме решения блочных задач дискретного программирования // Жури, вычисл. математики и матем.физики. 1986. Т. 26, № 9. С. 1339-1349.

79.Щербина О. А. О квазиблочных задачах дискретного программирования с дополнительными ограничениями // Журн. вычисл. математики и ма-тем. физики. 1987. Т. 27, N 5. С. 676-687.

80.Щербина О. А. Применение локальных алгоритмов к решению задач целочисленного линейного программирования // Вопросы кибернетики. М.: НСК АН СССР. 1989. С. 19-34.

81. Щербина О. А. Локальные алгоритмы и древовидная декомпозиция для задач дискретной оптимизации // Динамические системы. 2006. Вып. 20. С. 89-103.

82.Щербина О. А. Об одной унимодулярной задаче целочисленного программирования // Журн. вычисл. математики и матем. физики. 1986. Т. 26, N 7. С. 1096-1099.

83.1Цербина О. А. О локальных алгоритмах с переменными окрестностями и индикаторной информацией // Журн. вычисл. математики и матем. физики. 1986. Т. 26, N 10. С. 1588-1591.

84.1Цербина О. А. Постоптимизационный анализ в дискретном программировании (обзор) // Методы оптимизации в экономико-математическом моделировании. М.: ЦЭМИ АН СССР. 1988. С. 28-50.

85.Щербина О. А. Элиминационные алгоритмы декомпозиции задач дискретной оптимизации // Таврический вестник информатики и математики. 2006. №2. С. 28-41.

86.Щербина О. А. Роль графовых структур в теории локальных элиминацион-ных алгоритмов // Динамические системы. 2008. Вып. 24. С. 83-98.

87.Щербина О. А., Канаева Н. Н. Об экстремальных свойствах сумм биномиальных коэффициентов // Динамические системы. 2000. Вып. 16. С. 192-197.

88.Щербина О. А. Локальные элиминационные алгоритмы для решения некоторых задач искусственного интеллекта // Труды 11 Национальной конференции по искусственному интеллекту (Дубна, 28 сентября — 3 октября 2008 г.). М.: ЛЕНАНД, 2008. Т. 2. С. 244-252.

89.Щербина О. А. Локальные элиминационные алгоритмы обработки запросов в базах данных // Таврический вестник информатики и математики. 2009. №2. С. 53-62.

90.Shcherbina О., Neumaier A., Sam-Haroud D., Vu Х.-Н., 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.

91. Shcherbina O. A. 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.

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

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

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

95.Shcherbina O. Tree decomposition and postoptimality analysis in discrete optimization//arXiv:0903.4435vl [cs.DM] (2009).

96.Канаева H. H., Щербина О. А. О локальном алгоритме для задач дискретного программирования квазиблочной структуры с дополнительными ограничениями // Вычислительная математика в современном научно-техническом прогрессе. Тез.докл. респ.конф. Киев: ИК АН УССР. 1982. С. 90-91.

97.Канаева Н. Н., Щербина О. А. О модифицированном локальном алгоритме для задач дискретного программирования // Журн. вычисл. математики и матем.физики. 1986. 26, № 2. С. 263-275.

98.Канаева Н. Н., Щербина О. А. Об эффективности модифицированного локального алгоритма для задач дискретной оптимизации // Журн. вычисл. математики и матем.физики. 1984. 24, № 10. С. 1520-1530.

99.Канаева Н. Н., Щербина О. А. Об эффективности модифицированного локального алгоритма // Республиканский семинар по дискретной оптимизации. Тезисы докладов. Киев: ИК АН УССР. 1985. С. 57-58.

100. Иловайская Е. И., Щербина О. А. О вычислительных аспектах реализации локальных алгоритмов решения задач дискретной оптимизации II Динамические системы. 1990. Вып. 9. С. 117-122.

101. Матвеев В. В., Щербина О. А. Об одном классе локальных алгоритмов решения квазиблочных задач целочисленного линейного программирования // Кибернетика. 1984. № 6. С. 116-118.

102. Матвеев В. В., Щербина О. А. Локальные алгоритмы решения задач дискретной оптимизации // Тезисы международной конференции по математическим методам в исследовании операций. София. 1983. С. 55-56.

103. Матвеев В. В., Щербина О. А. Модели оптимального резервирования ресурсов, распределенных во времени // Оптимизационные задачи в автоматизированной системе плановых расчетов. Минск: НИИЭМП. 1982. С. 98-104.

104. Матвеев В. В., Щербина О. А. Эффективность локальных алгоритмов решения квазиблочных задач целочисленного линейного программирования // Системы программного обеспечения решения задач оптимального планирования. М.: ЦЭМИ АН СССР. 1982. С. 85-87.

105. Быстрое В. А., Щербина О. А. О модифицированном локальном алгоритме декомпозиции блочных задач дискретного программирования //Декомпозиция и координация в сложных системах. 4.1. Челябинск: ЧПИ, 1986. С. 57-58.

106. Быстров В. А., Щербина О. А. О среднем значении оценки эффективности модифицированного локального алгоритма в квазиблочном случае // Системы программного обеспечения решения задач оптимального планирования. М.: ЦЭМИ АН СССР. 1986. С. 69.

107. Быстров В. А., Щербина О. А. Об эффективности решения одного класса задач дискретного программирования с помощью локального алгоритма // Кибернетика. 1987. № 3. С. 96-101.

Обозначения, сокращения и определения.

ВВЕДЕНИЕ.

ГЛАВА I. ДЕСКРИПТИВНАЯ ТЕОРИЯ ЛОКАЛЬНЫХ АЛГОРИТМОВ.

1.1.0 локальных алгоритмах вычисления информации.

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

1.3. Локальный декомпозиционный алгоритм 2СВТ решения задач дискретной оптимизации с блочно-древовидной структурой.

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

1.5. О связи локальных алгоритмов с другими алгоритмами дискретной оптимизации.

1.6. Распространение локального алгоритма на другие блочные структуры.

Выводы по главе 1.

ГЛАВА И. ЛОКАЛЬНЫЕ ЭЛИМИНАЦИОННЫЕ АЛГОРИТМЫ.

2.1. Основные определения.

2.2. Локальные элиминационные алгоритмы в задачах оптимизации.

2.3. Локальные элиминационные алгоритмы решения дискретных задач информатики.

Выводы по главе II.

ГЛАВА III. РАЗРЕЖЕННЫЕ МАТРИЦЫ И ТЕОРЕТИКО-ГРАФОВЫЕ

ПОДХОДЫ К ВЫДЕЛЕНИЮ БЛОЧНЫХ СТРУКТУР.

3.1. Разреженные матрицы и выделение блочной структуры.

3.2. Свойства матриц с блочно-древовидной структурой.

3.3. Древовидная декомпозиция и древовидная ширина.

Выводы по главе III.

ГЛАВА IV. ОЦЕНКИ ЭФФЕКТИВНОСТИ И УСЛОВИЯ

ЦЕЛЕСООБРАЗНОСТИ ПРИМЕНЕНИЯ ЛОКАЛЬНЫХ АЛГОРИТМОВ.

4.1. О сложности алгоритмов решения задач дискретной оптимизации, общие понятия о сложности алгоритмов.

4.2. Оценки сложности алгоритмов дискретной оптимизации.

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

4.4. О целесообразности использования локального алгоритма для решения задач дискретной оптимизации с блочно-древовидной структурой.

4.5. Случай блочно-древовидной структуры с дополнительными ограничениями.

Выводы по главе IV.

ГЛАВА V. СРЕДНИЕ ЗНАЧЕНИЯ ОЦЕНКИ ЭФФЕКТИВНОСТИ

ЛОКАЛЬНОГО АЛГОРИТМА.

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

5.2. Асимптотическая средняя оценка эффективности локального алгоритма для задач с блочно-древовидной структурой и ограниченной связностью.

5.3. Средняя оценка эффективности локального алгоритма для небулева случая.

5.4. Оценка эффективности локального алгоритма в блочном случае с дополнительными ограничениями одновариантного типа.

5.5. Средняя оценка эффективности локального алгоритма на классе блочных задач в более общем случае.

5.6. Асимптотические средние оценки эффективности локального алгоритма для блочно-древовидной структуры с дополнительными ограничениями многовариантного типа.

5.7. Асимптотические средние оценки эффективности локального алгоритма для блочно-древовидной структуры с дополнительными ограниченими одновариантного типа.

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

5.9. Средние оценки эффективности локального алгоритма при решении G -блочных задач дискретной оптимизации.

Выводы по главе V.

ГЛАВА VI. АНАЛИЗ БЛОЧНЫХ СТРУКТУР В СЛУЧАЯХ НАИЛУЧШЕГО И НАИХУДШЕГО ПОВЕДЕНИЯ ЛОКАЛЬНОГО АЛГОРИТМА.

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

6.2. «Наихудшее» и «наилучшее» поведение локального алгоритма на классе блочно-древовидных структур с дополнительными ограничениями многократного выбора.

Выводы по главе VI.

ГЛАВА VII. ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ РЕАЛИЗАЦИИ ЛОКАЛЬНОГО АЛГОРИТМА.

7.1. «Оценочный» эксперимент для локального алгоритма.

7.2. Эксперимент для локального алгоритма в сочетании с алгоритмами пакета «Диспро».

7.3. Приближенные версии локального алгоритма.

7.4. Локальный элиминационный алгоритм и параллельные вычисления.

Выводы по главе VII.

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

Использование моделей и алгоритмов дискретной оптимизации (ДО) [77], [83], [95], [96], [150], [165], [167], [226], [260], [362], [370], [421] позволяет решать многие практические задачи, такие, как задачи теории расписаний, оптимизации на сетях, маршрутизации трафика в коммуникационных сетях, задачи размещения экономических объектов, задачи оптимизации автоматизированных систем планирования ресурсов (ERP), задачи логистики, в частности, оптимизацию цепочек предложения (Supply Chain Management) [553], доказательство теорем, задачи искусственного интеллекта и робототехники и т. п. [426]. Это обусловлено тем, что дискретные оптимизационные модели адекватно отражают нелинейные зависимости, неделимость объектов, учитывают ограничения логического типа и всевозможные технологические, в том числе и имеющие качественный характер, требования. К сожалению, большинство интересных задач ДО являются NP-трудными и решение их в худшем случае может требовать построения дерева поиска решений экспоненциального размера. В настоящее время практически никто не ожидает появления полиномиального алгоритма решения NP-трудных задач [350]. Многие практические задачи ДО содержат огромное число переменных и/или ограничений, что создает сложности при попытке решения этих задач с помощью современных решателей.

А.Н. Колмогоров отмечает [79, с. 28]: «Весьма вероятно, что с развитием современной вычислительной техники будет понято, что в очень многих случаях разумно изучение реальных явлений вести, избегая промежуточный этап их стилизации в духе представлений математики бесконечного и непрерывного, переходя прямо к дискретным моделям. Особенно это относится к изучению сложно организованных систем, способных перерабатывать информацию».

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

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

2) поиск специальных классов задач ДО, на которых хорошо работают те или иные алгоритмы;

3) теоретический анализ сложности и трудоемкости алгоритмов ДО.

4) разработка и исследование алгоритмов ДО с эффективным распараллеливанием вычислений.

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

1) комбинаторные методы, в том числе:

1.1) методы ветвей и границ [82, 238, 483], методы ветвления и отсечения [443], [476];

1.2) локальные алгоритмы Ю. И. Журавлева [51-58, 60-62];

1.3) метод последовательного анализа и отсеивания вариантов, предложенный В. С. Михалевичем иН.З. Шором [113-117, 121];

1.4) последовательностные схемы В. А. Емеличева [44, 45, 47, 49];

1.5) аппроксимационно-комбинаторный метод [163, 164];

1.6) метод динамического программирования [7, 15, 188, 215, 241, 242,

287, 580];

2) приближенные методы [143-145, 162, 353, 359, 416, 434-437, 449, 531];

3) эвристические подходы [413, 480] (табу [371], генетические алгоритмы [358, 390], метод отжига (simulated annealing) [441] и др.), мета-эвристические методы [325], [489], [590];

4) методы глобальной оптимизации для решения задач смешанного нелинейного целочисленного программирования [349, 391, 484, 485, 561];

4) декомпозиционные методы [1-3, 9, 11-14, 22, 23, 30, 31, 46, 75, 78, 86, 91-93, 105, 111, 127, 134, 135, 141, 153, 155, 158, 169, 225, 283, 369, 468, 470, 488, 512, 525, 530, 533, 549, 554, 572, 573, 587];

6) другие методы, в том числе методы отсечения; теоретико-групповые методы [515], [534], [535], [586]; гибридные методы [81].

Среди методов решения задач дискретной оптимизации [318], [363] в настоящее время весьма популярен метод ветвей и границ [238, 483], представляющий собой поиск на дереве с движением от корня дерева поиска к его листьям (стратегия «up-bottom») с использованием оценок для ослабленных задач-релаксаций [360], [375], [536].

Хотя задачи ДО в общем трудны для решения, в последнее время наблюдается существенный количественный и качественный рост числа разработок в области программного обеспечения (ПО) - как коммерческого, так и некоммерческого - решения задач ДО. Хороший обзор основных алгоритмических компонентов коммерческих решателей, таких как CPLEX, LINGO, XPRESS, дан в работе Atamtiirk & Savelsbergh [223]. В работе [453] анализируются возможности некоммерческого и открытого ПО для решения задач ДО. Почти без исключений, эти новые пакеты ПО реализуют различные версии метода ветвей и границ. Метод ветвления и отсечения (branch-and-cut) [443] является обобщением метода ветвей и границ и чистого метода отсечений Гомори, при этом после решения линейной релаксации и невозможности успешного зондирования на основе решения соответствующей задачи ЛП, делается попытка нахождения нарушающегося отсечения. Если найдены нарушающиеся отсечения, они добавляются к формулировке релаксационной задачи и полученная задача ЛП решается вновь. Если же нарушающегося отсечения не было найдено, производится ветвление. Метод отсечений и ветвлений [381], [409], [490] объединяет вычислительные возможности алгоритмов ветвей и границ с теоретическими результатами комбинаторики многогранников (см. обзоры [288], [299]). В 1998 г. Applegate et al. использовали этот метод для решения задачи о коммивояжере с 13509 городами, что на порядок больше размера задач, которые решались ранее [213]. Этот результат становится более впечатляющим, если учесть, что число переменных в стандартной формулировке этой задачи примерно равно квадрату числа городов. Таким образом, здесь решалась задача с примерно 100 млн. переменных.

Пакеты ПО можно разделить на две группы: решатели, использующие алгоритмы общего назначения для решения задач СЦЛП, не использующие особенности структуры задач) и решатели, позволяющие пользователю использовать преимущества специальной структуры задачи. Наиболее часто предлагаются решатели СЦП. Среди последних следует упомянуть MINTO [482], MIPO [229], а также bc-opt [304].

Общие схемы - SYMPHONY, COIN/BCP и ABACUS [330], [420] наиболее полно отражают возможности решателей первого вида. Другие пакеты, такие как MINTO [482], могут использовать подпрограммы, учитывающие специфику задачи. CONCORDE [213], [214] - один из наиболее совершенных в настоящее время программных пакетов для решения задачи о коммивояжере. Среди коммерческих пакетов следует также выделить CPLEX (ILOG), OSL (IBM), XPRESS (Dash).

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

Теоретические основы для ускорения процесса решения сложных задач ДО предложены в [147], где описана РЕСТАРТ-технология, основанная на использовании РЕСТАРТ-распределения и РЕСТАРТ-критерия останова алгоритма.

Несмотря на описанные результаты, потребность в решении больших и более сложных задач ДО продолжает расти.

Следует особо выделить весьма общие и эффективные при решении ряда конкретных прикладных задач дискретной оптимизации схемы, такие как метод последовательного конструирования, анализа и отсева вариантов В. С. Михалевича [113-117, 121], общая схема глобального равновесного поиска {И. В. Сергиенко, В. 77. Шило [146]), последовательностные схемы В. А. Емеличееа [44, 45, 47, 49], локальные алгоритмы Ю. И. Журавлева [51-58, 60-62].

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

Тем не менее, в последнее время наблюдается потребность в построении и анализе точных алгоритмов, существенно более быстрых, чем полный перебор, но пока еще не полиномиальных (так называемых супер-полиномиальных алгоритмов, с помощью которых находятся оптимальные решения NP-полных задач - см. обзор Woeginger [583]).

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

Пападимитриу и Стайглиц [128, с. 467] пишут: «локальный поиск основан на старейшем, по-видимому, методе оптимизации - методе проб и ошибок, его идея настолько проста и естественна, что очень удивительно, насколько успешным оказывается локальный поиск для многих трудных комбинаторных задач оптимизации».

Общая теория локальных алгоритмов для решения ряда важных задач дискретной математики была развита Ю. И. Журавлевым [51-58, 60-62].

Достаточно эффективными показали себя такие приближенные алгоритмы локального поиска, как метод вектора спада, разработанный И. В. Сергиенко и его учениками [8, 138, 140, 141, 145], локально-стохастические алгоритмы [49, 76, 201].

Идея локального алгоритма основана на введении понятия «близости», на основе которого определяется окрестность элемента, т. е. множество элементов, «близких» к данному. Локальный алгоритм на каждом шаге изучает окрестности элементов (а не все элементы множества) и накапливает о них информацию, которая затем используется на последующих шагах алгоритма. Отметим, что в методе вектора спада и локально-стохастическом алгоритме используются окрестности решений задачи ДО. Алгоритмы локального поиска (называемые по-другому алгоритмами с окрестностями (neighborhood search algorithms)) [85], [201], [203],

224], [343], [392], [393] на каждой итерации находят улучшенное решение путем поиска в окрестности текущего решения. Эффективность подобных методов существенно зависит от способа выбора окрестности решения. К подходам, использующим локальный поиск, относятся методы отжига [428], табу [371], меметиче-ские алгоритмы [478]. Дальнейшее развитие методы локального поиска получили в метаэвристических методах [489], [201], [149], в которых локальный поиск используется совместно с эвристическими алгоритмами, такими как, например, алгоритм муравьиных колоний [323] и генетический алгоритм [410].

В последнее время интересные результаты были получены в теории удовлетворения ограничений (Constraint Satisfaction) [316], находящейся на пересечении искусственного интеллекта и информатики.

Одним из наиболее перспективных подходов к решению задач дискретной оптимизации является построение гибридных методов, основанных на сочетании и взаимодействии в рамках нового метода двух или более известных методов. Важные теоретические исследования, служащие основой для дальнейшего развития гибридных алгоритмов [81, 124], проведены в известных работах Ю. И. Журавлева [59].

Ряд подходов из теории удовлетворения ограничений [316, 190] может быть использован при создании гибридных алгоритмов ДО и глобальной оптимизации [484].

В работах М. М. Ковалева и его учеников [124] отдельные градиентные алгоритмы типа координатного подъема объединяются в серию и каждый из указанных алгоритмов применяется для решения конкретной задачи, причем в качестве результата работы серии алгоритмов принимается лучшее из полученных решений. Результаты машинных экспериментов [124] показывают, что поведение серии в среднем гораздо лучше, чем их теоретическое поведение в наихудшем случае, при этом эффективность серии существенно выше эффективности отдельных алгоритмов, составлявших серию. Тот факт, что погрешность серии алгоритмов оказывается во многих случаях меньше погрешности лучшего из алгоритмов серии, объясняется тем, что для различных алгоритмов серии «плохими» оказываются разные задачи. Подобные результаты были также получены в работе [474].

Поскольку разработка достаточно эффективных точных алгоритмов для решения задач дискретной оптимизации общего вида, как отмечено выше, представляется сомнительной, то имеет смысл исследовать более узкие классы задач и строить более эффективные методы, основанные на изучении особенностей частных подклассов задач. Следует отметить, что успехи, достигнутые к настоящему времени в теории и практике ДО, достаточно часто были связаны именно со специальной структурой задач ДО [576]. Действительно, хорошие результаты получены при решении задач ДО, обладающих специальной структурой (так, методы отсечения успешно применялись при решении задач о покрытии, последова-тельностные схемы В. А. Емеличева особенно хорошо работают при решении задач о размещении, высокая эффективность метода ветвей и границ достигается при решении задач с ограничениями специального вида, например, многократного выбора [397, 472]), градиентные алгоритмы хорошо работают на матроидах [48] и т. д.).

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

Понимание принципиального характера трудности решения задач дискретной оптимизации стимулировало интенсивное развитие теории сложности [10, 36, 128, 301, 395, 396, 411, 415, 451, 467, 491-493, 499, 503, 558, 578, 413, 324]. Одной из наиболее важных теоретических проблем в теории сложности является известная проблема «P=NP?».

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

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

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

Отметим работы В. А. Емеличева [47], в которых сложность решения задачи линейного программирования оценивается косвенно, путем нахождения диаметра многогранника допустимых решений.

Развитие средств вычислительной техники, появление многопроцессорных комплексов, супер-компьютеров или, иными словами, компьютеров с сильным распараллеливанием обусловило необходимость разработки и исследования алгоритмов ДО с эффективным распараллеливанием вычислений [24, 29, 38, 90, 139, 142, 166, 204, 211, 212, 237, 258, 259, 287, 291, 295, 327, 328, 337, 339, 342, 356, 377-379, 442, 443, 454, 469, 507, 508, 510, 513, 523, 543, 544, 557, 568, 588, 589].

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

В связи о вышесказанным приобретает особую актуальность разработка в ДО декомпозиционных подходов [1-3, 9, 11-14, 22, 23, 30, 31, 46, 75, 78, 86, 9193, 105, 111, 127, 134, 135, 141, 153, 155, 158, 169, 225, 283, 369, 468, 470, 488, 512, 525, 530, 533, 549, 554, 572, 573, 587], позволяющих решать задачи большой размерности [104], [309].

Как известно, метод декомпозиции впервые был использован для решения задач смешанного целочисленного программирования в работе Бендерса [244] (см. также [80]), позднее другие методы декомпозиции были развиты в работах [228, 286, 307, 433, 526, 527, 556].

Принцип декомпозиции Данцига-Вулфа для задач ЛП имеет аналог в целочисленном программировании [572]. Этот подход использует мастер-задачу целочисленного ЛП (ЦЛП), которая неявно решает задачу ЦЛП с большим числом переменных с помощью процедуры построения столбцов задачи ЦЛП, известную как алгоритм ветвей и оценок (branch-and-price) [234], использование которого позволило решить в последние годы большие задачи ДО.

Задачи ДО, возникающие на практике, обычно имеют специальную структуру, причем «. матрицы ограничений в задачах большой размерности, как правило, содержат большое количество нулевых элементов (сильно «разрежены»), а ненулевые матричные элементы в большинстве случаев группируются в блоки (чаще всего вдоль главной диагонали)» [28]. Блочность многих прикладных задач ДО обусловлена слабой связностью подсистем моделируемых реальных сложных систем. Задачи ДО и, в частности, задачи ЦП с блочной структурой возникают естественным образом во многих приложениях [4], [475]. При этом блоки обычно представляют в модели отдельные объекты, либо решения в подразделениях фирмы, в техническом устройстве, либо отвечают периоду времени. Эти блоки связаны между собой ограничениями, отражающими необходимость пользования одними и теми же ресурсами или отражающими взаимосвязь решений для всей компании, технического процесса или периода планирования. В качестве примеров можно привести составление расписаний для транспортных средств [463], задачи в области телекоммуникаций [63], [475], в том числе задачи оптимального назначения радиочастот [440], задачи стохастического целочисленного программирования [551]. Блочную структуру имеют задачи оптимизации многопродуктовых потоков ([202], [352], [464]). Следует упомянуть также множественную задачу о ранце ([335], [336]), блоки которой являются задачами о ранце, а связывающие блоки ограничения являются неравенствами упаковки и разбиения множества. Выделение блочной структуры в матрицах задач ЦЛП рассмотрено в [275]. Задачи ЦЛП блочного типа были получены в результате моделирования системы туризма [94], [175].

Перспективными декомпозиционными методами, использующими разреженность матрицы ограничений задач ДО, представляются локальные элими-национные алгоритмы [189], включающие локальные алгоритмы декомпозиции [159], [184], [195], алгоритмы несериального динамического программирования (НСДП) [255], [412], [487], [538], [539], алгоритмы сегментной элиминации [314]. Для выделения специальных структур задач ДО представляются перспективными такие графовые декомпозиционные подходы, как методы древовидной декомпозиции (ДД) [187], [405]. Несмотря на обширную библиографию по этой тематике за рубежом, в отечественной литературе публикаций по ДД практически нет (можно отметить лишь близкие по тематике работы по локальным алгоритмам декомпозиции [184], [195], а также обзор [187]). Важность и актуальность указанных подходов в ДО обусловлены результатами Courcelle [308], Arnborg et al. [218], доказавших, что ряд NP-трудных задач, поставленных в монадической логике второго порядка, могут быть решены за полиномиальное время с помощью методов динамического программирования на графах, описывающих структуру задачи ДО, имеющих ограниченную древовидную ширину. Методы ДД показали свою эффективность при решении задач ДО: задач кольцевой маршрутизации [302], задачи коммивояжера [303], задачи оптимального назначения радиочастот2 [440].

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

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

П. К К

Рис 1. Квазиблочная структура.

Одним из первых классов больших разреженных задач линейного программирования, которые начал изучать G. Dantzig, был класс квазиблочных задач ЛП для динамического планирования ([311], [312]). Другие примеры квазиблочных задач ЛП для многоэтапного планирования, составления расписаний, назначений и многоэтапного структурного проектирования содержатся во множестве тестовых квазиблочных задач, опубликованных Но & Loute ([407]). Блочные задачи ЛП изучались также в отечественных работах [18], [64], [156]. Квазиблочную структуру имеют задачи оптимального резервирования гостиничных номеров [171], аналогичные последним темпоральные задачи о ранце [236], получившие в последнее время применение при решении задач предварительного резервирования вычислительных ресурсов в Grid Computing [552], задачи линейного динамического программирования [66, 131], некоторые задачи управления трудовыми ресурсами [112], динамические модели экономики, учитывающие в явном виде фактор времени [126], задачи управления в иерархических (обычно древовидных) структурах, сетевые задачи, задачи многоэтапного стохастического программирования [579].

Для решения квазиблочных задач ДО достаточно эффективен локальный алгоритм декомпозиции [159-161, 174, 176, 178-181, 183-185, 191, 194, 197, 198], использующий специфику квазиблочной матрицы ограничений,

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

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

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

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

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

• исследование возможностей распространения локального элиминационного алгоритма на различные классы задач ДО;

• использование ЛА совместно с методами древовидной декомпозиции;

• теоретическое и экспериментальное исследование эффективности локального элиминационного алгоритма, анализ и выделение классов блочных задач ДО, достаточно эффективно решаемых локальным элиминационным алгоритмом;

• возможности снижения перебора ЛЭА;

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

Изложим структуру работы.

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

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

В параграфе 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 и отмечено, что нахождение дерева клик становится простой задачей в случае хордального графа. Показано, как алгоритм элиминационной игры можно использовать для триангуляции графов. Рассмотрены методы разбиения графа. Перечислен ряд доступных пакетов программного обеспечения по разбиению графов. Рассмотрены вопросы построения блочных структур и древовидных декомпозиций из упорядоченных разбиений путем построения фактор-графов.

Выводы по главе VII.

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

• «оценочный» машинный эксперимент выявил разницу в поведении ЛА в сочетании с очень эффективными алгоритмами («оценка снизу») и слабо эффективными («оценка сверху»);

• для практического применения ЛА в сочетании с каким-либо решателем задач ДО необходим предварительный машинный эксперимент, на основании результатов которого должны быть выявлены приемлемые параметры задач ДО, для решения которых целесообразно использовать локальный алгоритм;

• применение ЛА целесообразно при относительно небольших размерностях перемычек и достаточной разреженности матрицы условий;

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

• результаты проведенных здесь вычислительных экспериментов свидетельствуют, что применение ЛА более целесообразно на подклассе слабосвязанных задач ДО, чем использование алгоритмов ДО общего назначения;

• предложены приближенные схемы локальных алгоритмом: с оракулом, со случайным выбором значений переменных сепараторов или с неполным перебором сепараторов;

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

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

Материалы главы VII опубликованы в работах автора [68], [177], [184],

186].

ЗАКЛЮЧЕНИЕ

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

Анализ возможностей применения локальных алгоритмов для решения дискретных оптимизационных задач позволяет сделать следующие выводы:

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

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

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

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

2" ности локального алгоритма в этом случае находится в пределах от Сх— до п

2"

С2 — для произвольного алгоритма, с помощью которого решаются задачи внут-п ри блоков; показано, что асимптотическая средняя оценка эффективности локального алгоритма в случае блочно-древовидной структуры без дополнительных ограничений находится в пределах между С'(к)-2" / Пгк-Х~тах^ и С'г(к)-2п / п2к~2~тахе1г (к> 2), где с1г - степень вершины г в структурном графе задачи дискретной оптимизации;

• найдена наихудшая асимптотическая средняя оценка эффективности локального алгоритма в случае блочно-древовидной структуры без дополнительных ограничений (при тахс1г-к-Ь + 2 - «метла» или «звезда»), что позволяет выделить наихудшую блочно-древовидную структуру;

• показано, что самым лучшим (в смысле минимума асимптотической средней оценки эффективности локального алгоритма) является случай Ь = к, что соответствует квазиблочной структуре;

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

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

• найдена асимптотическая средняя оценка эффективности локального алгоритма для небулева случая в 2-квазиблочном случае;

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

Зг» ("• квс(т)- < (1)) ~ (¿-УДу».

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

Е^{пЛЛ,М],Вк,с(1)ГА1(\)) = к!- |> С; • О**-1 • М-' /пк~х, и, ТУ—»со. найдена асимптотическая средняя оценка эффективности локального алгоритма в случае блочно-диагональной структуры с дополнительными ограничениями многовариантного типа равной длины /: N п на р=1 ^0=0 найдена асимптотическая средняя оценка эффективности локального алгоритма в случае блочно-древовидной структуры с дополнительными ограничениями многовариантного типа равной длины I:

1к-2)!-Я* (1 + /)

Ы+2к-2-с!г,

Е -1---У -> СО. найдена асимптотическая средняя оценка эффективности локального алгоритма на классе всех блочно-древовидныцх структур с дополнительными ограничениями одновариантного типа: N

Е,£ ~ --— ■ —-г—-при п, N —> со. drJ п2к'2 р для среднего значения ОЭ для всех задач ДО с заданной графом G структурой, к блоками и п булевыми переменными получены неравенства:

С'(к) - Т/пк+/-тахс1' < (п,к,в) < С"(к) • 2п/пк+/-тяа'-1 (к> 2). для ЛА с селектором Ира с для решения С -блочных задач ДО получена следующая оценка асимптотической средней ОЭ:

N ( Ур > — 'в

ЕКс{п,к,2,1Г„О.С(у),4{у)) х П ЕС/' решаются задачи нахождения экстремальных значений ОЭ ЛА Е% (п, к, Z, N. Д А) при заданной структуре О и параметрах п, к. Знание экстремальных значенийОЭ ЛА 7£т позволяет выделить наилучшие и наихудшие для J1A блочные структуры, причем наилучшие структуры соответствуют minЕЖвт (п, к, Z, N, D, А), а наихудшие - тахЕЖвт (п, к, Z, N,D, А) найдена оценка максимального значения оценки эффективности локального алгоритма для задач дискретной оптимизации с блочно-древовидной структурой без дополнительных ограничений, что оценивает «наихудшее» поведение локального алгоритма на задачах с описанной структурой; найдена оценка минимального значения оценки эффективности локального алгоритма для задач дискретной оптимизации с блочно-древовидной структурой без дополнительных ограничений, что оценивает «наилучшее» поведение локального алгоритма на задачах с описанной структурой; найдена оценка максимального значения оценки эффективности локального алгоритма для задач дискретной оптимизации с блочно-древовидной структурой и дополнительными ограничениями многократного выбора, что оценивает «наихудшее» поведение локального алгоритма на задачах с описанной структурой; найдена оценка минимального значения оценки эффективности локального алгоритма для задач дискретной оптимизации с блочно-древовидной структурой и дополнительными ограничениями многократного выбора, что оценивает «наилучшее» поведение локального алгоритма на задачах с описанной структурой; поставлены и решены экстремальные задачи для сумм биномиальных коэффициентов; найдены оценки сверху оценки эффективности локального алгоритма для частично невырожденного и полностью невырожденного случаев для блочно-диагональных структур и дополнительных ограничений многократного выбора; исследованы возможности снижения перебора ЛЭА на основе использования релаксаций и селектора;

• предложены эффективные приближенные версии локального элиминационного алгоритма: с оракулом; со случайным выбором значений сепаратором и с неполным перебором сепараторов;

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

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

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

1. Авербах И. Л., Цурков В. И. Оптимизация в больших задачах с целочисленными переменными. М.: Наука, Физматлит. 1995. 288 с.

2. Авербах И. Л. К одному методу декомпозиции в блочном целочисленном программировании // Декомпозиция и координация в сложных системах. Ч. 1. Челябинск: ЧПИ. 1986. С. 50-51.

3. Авербах И. Л. Теоретико-групповой метод декомпозиции в целочисленном линейном программировании // Журн. вычисл. математики и матем.физики. 1992. Т. 32, №8. С. 1229-1243.

4. Авербах И. Л., Цурков В. И. Целочисленные оптимизационные модели блочного типа // Математическое моделирование. 1990. Т. 2, № 2. С. 39-57.

5. Акопян Г. Ц. О вхождении подмножества ребер гиперграфа в некоторое тупиковое с-покрытие // Прикладная математика. Межвузовский сб. научных трудов. Ереван: ЕРГУ, 1984. Вып.З. С. 32-35.

6. Анисимов А. В. Локальный алгоритм для задачи о кратчайшем пути из одного источника // Кибернетика. 1986. № 3. С. 57-60.

7. Арис Р. Дискретное динамическое программирование. М.: Мир, 1969. 172 с.

8. Архипова Т. Т., Сергиенко И. В. Метод возможных направлений и метод вектора спада в целочисленном программировании // Кибернетика. 1975. № 5. С. 125-128.

9. Афонин Ю. С. Блочный метод ветвей и границ // Автоматика и телемеханика. 1986. №8. С. 98-108.

10. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1975. 535 с.

11. Аюпов Р. С. Комбинаторно-непрерывный метод решения блочных задач дискретного программирования // Изв. АН СССР. Техн. кибернетика. 1984. № 3. С. 34-39.

12. Бабаев Дж. А., Мамедов К. Ш., Шихалиев Н. Ш. Решение задач булева программирования последовательным решением вспомогательных подзадач с двумя ограничениями / Рук. деп. в ВИНИТИ 8 мая 1985 г., № 3117-85 ДЕП.

13. Бахтин А. Е. Блочный способ решения задач линейного программирования // Математические методы решения экономических задач. Новосибирск: Наука, 1971. С. 63-78.

14. Бахтин А. Е., Колоколов А. А. Декомпозиционный метод решения целочисленных производственно-транспортных задач // Вопросы анализа сложных систем. Новосибирск, 1974. С. 15-36.

15. Беллман Р. Динамическое программирование. М.: Изд-во иностр. лит., 1960. 400 с.

16. Береснев В. Л., Гимади Э. X., Дементьев В. Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. 333 с.

17. Богданов А. Е. О неразрешимости задачи минимизации булевых функций в классе локальных алгоритмов // Дискретная математика и математическая кибернетика. М.: НСК АН СССР, 1982. С. 158-163.

18. Булавский В. А., Звягина Р. А., Яковлева М. А. Численные методы линейного программирования. М.: Наука, 1977. 368 с.

19. Быстров В. А., Щербина О. А. О модифицированном локальном алгоритме декомпозиции блочных задач дискретного программирования // Декомпозиция и координация в сложных системах. 4.1. Челябинск: ЧПИ, 1986. С. 57-58.

20. Быстров В. А., Щербина О. А. О среднем значении оценки эффективности модифицированного локального алгоритма в квазиблочном случае // Системы программного обеспечения решения задач оптимального планирования. М.: ЦЭМИ АН СССР. 1986. С. 69.

21. Быстров В. А., Щербина О. А. Об эффективности решения одного класса задач дискретного программирования с помощью локального алгоритма // Кибернетика. 1987. № 3. С. 96-101.

22. Верина Л. Ф., Танаев В. С. Декомпозиционные подходы к решению задач математического программирования // Экономика и математические методы. 1976. №6. С. 1160-1172.

23. Верина Л. Ф. О декомпозиции задач линейного программирования квазиблочной структуры // Весщ АН БССР. Сер. физ.-мат. наук. 1975. № 6. С. 18-21.

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

25. Волкович С. В., Волошин А. Ф. Об одной общей схеме метода последовательного анализа и отсеивания вариантов // Кибернетика. 1978. № 5. С. 98-105.

26. Вычислительные методы выбора оптимальных проектных решений / Под ред.

27. B. С. Михалевича. Киев: Наукова думка, 1977. 180 с.

28. Гловер Ф. Целочисленное программирование и комбинаторика //Исследование операций. Т.1: Методологические основы и математические методы. М.: Мир, 1981. С. 122-182.

29. Глушков В. М., Молчанов И. Н. О некоторых проблемах решения задач на ЭВМ с параллельной организацией вычислений //Кибернетика. 1981. № 4.1. C. 82-88.

30. Гольденгорин Б. И. Декомпозиция задачи размещения // Автоматика и телемеханика. 1986. № 5. С. 91-101.

31. Гольденгорин Б. И. Алгоритм декомпозиции задачи унификации и новые полиномиально разрешимые случаи // Докл. АН СССР. 1986. Т. 288, № 1. С. 1923.

32. Гришухин В. П. Потоковый алгоритм нахождения минимального разреза в гиперграфе // Системы программного обеспечения решения задач оптимального планирования. М.: ЦЭМИ АН СССР. 1986. С. 76.

33. Гришухин В. П. Оценка сложности алгоритма Балаша // Математические методы решения экономических задач. М.: Наука. 1972. Вып. 3. С. 93-105.

34. Гришухин В. П. О среднем числе итераций алгоритма Балаша // Исследования по дискретной математике. М.: Наука. 1973. С. 58-68.

35. Гришухин В. П. Алгоритмы ветвей и границ в задачах с булевыми перемен- \ ными, оценка их эффективности // Экономика и математические методы. 1976.1. Т. 12, №4. С. 757-766.

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

37. Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений. М.: Мир, 1984. 333 с.

38. Евреинов Э. Р., Косарев Ю. Г. О решении задач на универсальных системах //Вычисл. системы. 1965. Вып. 17. С. 106-164.

39. Евстигнеев В. А. Вычислительные локальные алгоритмы // Численные методы и задачи оптимизации. Томск: ТГУ. 1983. С. 96-109.

40. Евстигнеев В. А. Локальный алгоритм отыскания бикомпонент в ориентированном графе // Журн. вычисл. математики и матем. физики. 1978. Т. 18, № 5. С. 1345-1349.

41. Евстигнеев В. А. Локальный алгоритм выделений блоков в графе //Комбинаторно-алгебраические методы в прикладной математике. Горький: ГГУ. 1979. С. 35-42.

42. Евстигнеев В. А. Применение теории графов в программировании. М.: Наука, 1985.352 с.

43. Евстигнеев В. А., Касьянов В. Н. Толковый словарь по теории графов в информатике и программировании. Новосибирск: Наука, 1999. 288 с.

44. Емеличев В. А. К теории дискретной оптимизации // Докл. АН СССР. 1971. Т. 198, №2. С. 273-276.

45. Емеличев В. А. Дискретная оптимизация: последовательностные схемы решения. I // Кибернетика. 1971. № 6. С. 109-121. II // Кибернетика. 1972. № 2. С. 92-103.

46. Емеличев В. А., Буй Кат Тыонг. Декомпозиционный подход к решению квазиблочных задач дискретной оптимизации на основе метода построения последовательности планов//Кибернетика. 1988. № 1.С. 116-118.

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

48. Емеличев В. А., Ковалев М. М. Полиэдральные аспекты дискретной оптимизации // Кибернетика. 1982. № 6. С. 54-62.

49. Емеличев В. А., Комлик В. И. Метод построения последовательности планов для решения задач дискретной оптимизации. М.: Наука, 1981. 208 с.

50. Лекции по теории графов / В. А. Емеличев и др.. Изд. 2-е, испр. М.: Книжный дом «ЛИБРОКОМ», 2009. 392 с.

51. Журавлев Ю. И. Алгоритмы упрощения дизъюнктивных нормальных форм конечного индекса // Докл.АН СССР. 1961. Т. 139, № 6. С. 1329-1331.

52. Журавлев Ю. И. Теоретико-множественные методы алгебры логики // Проблемы кибернетики. М.: Физматгиз. 1962. Вып. 8. С. 5-44.

53. Журавлев Ю. И. Алгоритмы с конечной памятью над дизъюнктивными нормальными формами // Дискретный анализ. Новосибирск: ИМ СО АН СССР. 1963. Вып. 1.С. 5-12.

54. Журавлев Ю. И Об одном классе алгоритмов над конечными множествами '//Докл. АН СССР. 1963. 151, №5. С. 1025-1028.

55. Журавлев Ю. И. Оценка сложности локальных алгоритмов для некоторых экстремальных задач на конечных множествах // Докл. АН СССР. 1964. Т. 158, №5. С. 1018-1021.

56. Журавлев Ю. И. Локальные алгоритмы вычисления информации. I //Кибернетика. 1965. №1. С. 12-19; II. //Кибернетика. 1966. № 2. С. 1-11.

57. Журавлев Ю. И., Финкелыптейн Ю. Ю. Локальные алгоритмы для задач линейного целочисленного программирования // Проблемы кибернетики. М.: Наука. 1965. Вып. 14. С. 289-296.

58. Журавлев Ю. И. Алгоритмы построения минимальных дизъюнктивных нормальных форм для функций алгебры логики // Дискретная математика и математические вопросы кибернетики. М.: Наука. 1974. Т. 1, раздел 2. С. 67-98.

59. Журавлев Ю. И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. Часть I // Кибернетика. 1977. № 4. С. 5-17. Часть II //Кибернетика. 1977. № 6. С. 21-27. Часть III // Кибернетика. 1978. № 2. С. 35-43.

60. Журавлев Ю. И. О локальных алгоритмах над дизъюнктивными нормальными формами // Докл.АН СССР. 1979. Т. 245, № 2. С. 289-292.

61. Журавлев Ю. И., Лосев Г. Ф. Окрестности в задачах дискретной математики // Кибернетика и системный анализ. 1995. №2. С. 32-41.

62. Журавлев Ю. И. Избранные научные труды. М.: Магистр, 1998. 420 с.

63. Заозерская Л. А., Китриноу Е., Колоколов А. А. Задача оптимального размещения центров телекоммуникаций в регионе// Труды 13-й Байкальской международной школы-семинара «Методы оптимизации и их приложения», Т. 1. Иркутск, 2005. С. 469-475.

64. Звягина Р. А., Задачи линейного программирования о матрицами произвольной блочной структуры // Докл. АН СССР. 1971. Т. 196, № 4. С. 756-768.

65. Зуев Ю. А. Задача о покрытии: локальный подход и метод типа ветвей и границ // Журн. вычисл. математики и матем.физики. 1979. Т. 19, № 6. С. 15661578.

66. Иванилов Ю. П., Пропой А. И. О задачах линейного динамического программирования//Докл. АН СССР. 1971. Т. 198, №5. С. 1011-1014.

67. Иванов Б. Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие / Б. Н. Иванов. М.: Лаборатория Базовых Знаний, 2003. 288 с:

68. Иловайская Е. И., Щербина О. А. О вычислительных аспектах реализации локальных алгоритмов решения задач дискретной оптимизации // Динамические системы. 1990. Вып. 9. С. 117-122.

69. Кабулов А. В. Локальные алгоритмы над схемами С.В. Яблонского // Журн. вычисл. математики и матем.физики. 1977. Т. 17, № 1. С. 217-225.

70. Кабулов А. В., Лосев Г. Ф. О локальных алгоритмах упрощения дизъюнктивных нормальных форм булевых функций // Журн. вычисл. математики и ма-тем. физики. 1978. Т. 18, № 3. С. 728-734.

71. Канаева Н. Н., Щербина О. А. О модифицированном локальном алгоритмедля задач дискретного программирования // Журн. вычисл. математики и ма-тем. физики. 1986. Т. 26, № 2. С. 263-275.

72. Канаева Н. Н., Щербина О. А. Об эффективности модифицированного локального алгоритма для задач дискретной оптимизации // Журн. вычисл. математики и матем. физики. 1984. Т. 24, № 10. С. 1520-1530.

73. Канаева Н. Н., Щербина О. А. Об эффективности модифицированного локального алгоритма // Республиканский семинар по дискретной оптимизации. Тезисы докладов. Киев: ИК АН УССР. 1985. С. 57-58.

74. Канцедал С. А. Декомпозиционный подход к решению задач теории расписаний большой размерности // Автоматика и телемеханика. 1983. № 10. С. 57-58.

75. Ковалев М. М., Пирьянович В. А. Локально-стохастические алгоритмы дискретной оптимизации (эксперименты, опыт, применения) // Кибернетика. 1982. № 1. С. 108-114.

76. Ковалев М. М. Дискретная оптимизация (целочисленное программирование). Москва: Едиториал УРСС, 2003. 192 с.

77. Ковалев М. Я. Декомпозиционный подход к построению Е-оптимальных приближенных алгоритмов // Математическое и прогр. обеспечение вычислит, систем. Минск. 1985. С. 3-8.

78. Колмогоров А. Н. Комбинаторные основания теории информации // Успехи математических наук. 1983. Т. 38, № 4. С. 27-36.

79. Колоколов А. А., Леванова Т. В. Декомпозиция Бендерса для задач размещения предприятий. Учебно-методическое пособие. Омск: Изд-во Ом. гос. ун-та, 2009. 50 с.

80. Корбут А. А., Сигал И. X., Финкелыптейн Ю. Ю. Гибридные методы в дискретной оптимизации // Системы программного обеспечения решения задач оптимального планирования. М.: ЦЭМИ АН СССР. 1986. С. 86-87.

81. Корбут А.А., Сигал И.Х., Финкелыптейн Ю. Ю. Метод ветвей и границ (обзор теории алгоритмов, программ и приложений) // Math. Operationsforsch. Statist. Ser.Optimization. 1977. 8, № 2. S. 253-280.

82. Корбут А. А., Финкелыптейн Ю. Ю. Дискретное программирование. M.:1. Наука, 1969. 368 с.

83. Коробков В. К. О некоторых целочисленных задачах линейного программирования //Проблемы кибернетики. М.: Наука. 1965. Вып. 14. С. 297-299.

84. Кочетов Ю. А. Вычислительные возможности локального поиска в комбинаторной оптимизации // Журнал вычислительной математики и математической физики. 2008. Т. 48, С. 747-764.

85. Кравец В.Л., Сергиенко И.В. Декомпозиционный метод решения одного класса комбинаторных оптимизационных задач // Кибернетика. 1983. № 6. С. 7784.

86. Кузюрин Н. Н. Асимптотически точные полиномиальные алгоритмы в задачах целочисленного линейного программирования // Дискретная математика. 1989. Т. 1, 2. С. 78-85.

87. Кузюрин Н. Н. Полиномиальный в среднем алгоритм в целочисленном линейном программировании // Сибирский журнал исследования операций. 1994. Т. 1,№З.С. 38-48.

88. Кузюрин Н. Н. Вероятностные приближенные алгоритмы в дискретной оптимизации // Дискретный анализ и исследование операций, серия 2. 2002. Т. 9, №2. С. 97-114.

89. Левин Г. М., Танаев В. С. Параметрическая декомпозиция экстремальных задач // Изв. АН БССР. 1974, № 4. С. 24-29.

90. Левин Г. М., Танаев В. С. Декомпозиционные методы оптимизации проектных решений. Минск: Наука и техника, 1978. 240 с.

91. Лемешев М. Я., Щербина О. А. Оптимизация рекреационной деятельности. М.: Экономика, 1985. 160 с.

92. Леонтьев В. К. Дискретные экстремальные задачи // Итоги науки и техники ВИНИТИ. Сер. Теория вероятности, матем. статистика, теоретич. кибернетика. М.: ВИНИТИ. 1979. Вып. 16. С. 39-101.

93. Леонтьев В. К. Дискретная оптимизация // Журнал вычислительной математики и математической физики. 2007. Том 47, № 2. С. 338-352.

94. Литвак Б. Г., Найвельт А. В. Взаимно несравнимые решения в задаче о ранце с дополнительными ограничениями блочного типа //Исследования по дискретной оптимизации. М.: Наука. 1976. С. 187-203.

95. Лосев Г. Ф. Локальные алгоритмы вычисления информации с нефиксированной памятью // Докл. АН СССР. 1982. 264, № 3. С. 547-550.

96. Лосев Г. Ф. Локальные алгоритмы вычисления информации и задача о минимальном покрытии // Докл. АН СССР. 1982. Т. 267, № 3. С. 544-548.

97. Лосев Г. Ф. Наилучший локальный алгоритм для построения суммы тупиковых дизъюнктивных нормальных форм булевой функции, использующий окрестности минимального порядка // Журн. вычисл. математики и матем. физики. 1974. Т. 14, № 2. С. 470-478.

98. Лосев Г. Ф. О локальных алгоритмах вычисления информации с нефиксированной памятью // Кибернетика. 1983. № 2. С. 15-19.

99. Лосев Г. Ф. Локальные алгоритмы и многопроцессорные вычислительные машины // Республиканский семинар по дискретной оптимизации. Тезисы докладов. Киев: ИК АН УССР, 1985. С. 76-77.

100. Лосев Г. Ф. Схема построения мажорантного локального алгоритма для задач о покрытиях // Тезисы докладов 3 Всесоюзной конференции по проблемам теоретич. кибернетики. Новосибирск, 1974. С. 111-112.

101. Лэсдон Л. С. Оптимизация больших систем. М.: Наука, 1975. 432 с.

102. Малинников В. В. Метод разложения в решении задач линейного программирования с блочной структурой // Экономика и матем. методы, 1971. Т. 7, № 5. С. 733-736.

103. Маршалл А., Олкин И. Неравенства: теория мажоризации и ее приложения. М.: Мир, 1983. 576 с.

104. Матвеев В.В., Щербина O.A. Об одном классе локальных алгоритмов решения квазиблочных задач целочисленного линейного программирования // Кибернетика. 1984. № 6. С. 116-118.

105. Матвеев В. В., Щербина О. А. Локальные алгоритмы решения задач дискретной оптимизации // Тезисы международной конференции по математическим методам в исследовании операций. София. 1983. С. 55-56.

106. Матвеев В. В., Щербина О. А. Модели оптимального резервирования ресурсов, распределенных во времени // Оптимизационные задачи в автоматизированной системе плановых расчетов. Минск: НИИЭМП. 1982. С. 98-104.

107. Матвеев В. В., Щербина О. А. Эффективность локальных алгоритмов решения квазиблочных задач целочисленного линейного программирования // Системы программного обеспечения решения задач оптимального планирования. М.: ЦЭМИ АН СССР. 1982. С. 85-87.

108. Мащенко С. О. Декомпозиционный алгоритм решения частично целочисленных задач линейного программирования // Исследование задач многокритериальной оптимизации. Киев: ИК АН УССР. 1984. С. 49-63.

109. Мезон Р., Фламгольц Э. Управление трудовыми ресурсами // Исследование операций. М.: Мир, 1981. Т.2: Модели и применения. С. 34-50.

110. Михалевич В. С. Последовательные алгоритмы оптимизации и их применение. 1. // Кибернетика. 1965. № 1. С. 45-56; П. // Кибернетика. 1965. № 2. С. 85-88.

111. Михалевич В. С., Волкович В. Л., Волошин А. Ф., Позняков Ю. М. Алгоритмы последовательного анализа и отсеивания вариантов в задачах дискретной оптимизации // Кибернетика. 1980. № 3. С. 76-85.

112. Михалевич В. С., Волкович В. Л. Вычислительные методы исследования и проектирования сложных систем. М.: Наука, 1982. 286 с.

113. Михалевич В. С., Волкович В. Л., Волошин А. Ф., Мащенко С. О. Последовательный подход к решению смешанных задач линейного программирования //Кибернетика. 1983. № 1. С. 34-39.

114. Михалевич В. С., Кукса А. И. Методы последовательной оптимизации.1. ML: Наука, 1983. 205 с.

115. Михалевич В. С., Сергиенко И. В и др. Результаты экспериментального исследования эффективности методов, включенных в пакет прикладных программ ДИСПРО: Препр. / АН УССР. Ин-т кибернетики; 80-47. К., 1980. 68 с.

116. Михалевич В. С., Сергиенко И. В. и др. Пакет прикладных программ ДИСПРО, предназначенный для решения задач дискретного программирования //Кибернетика. 1981. № 3. С. 117-137.

117. Михалевич В. С., Сергиенко И. В. и др. Пакет программ ДИСПРО-3: назначение, классы решаемых задач, системное и алгоритмическое обеспечение // Кибернетика. 1985. № 1. С. 56-71.

118. Михалевич В. С., Шор Н. 3. Численные решения многовариантных задач по методу последовательного анализа вариантов //Научно-метод. материалы эконом.-матем. семинара. М.: ЛЭММ АН СССР. 1962. Вып. 1. С. 15-42.

119. Муртаф Б. Современное линейное программирование. М.: Мир, 1984. 224 с.

120. Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации. М.: Наука, 1978. 352 с.

121. Наумович Н. А. Экспериментальное исследование серий градиентных методов // Методы, алгоритмы и программы решения экстремальных задач. Минск: ИТК АН БССР. 1985. С. 98-111.

122. Нурлыбаев А. Н. О локальном алгоритме индекса 1 для построения суммы тупиковых дизъюнктивных нормальных форм для функций к-значной логики // Журн. вычисл. математики и матем. физики. 1977. Т. 17, № 6. С. 1556-1563.

123. Оптимизация развития топливно-энергетического комплекса. / Под ред. А. С. Некрасова М.: Энергоиздат, 1981. 240 с.

124. Павлов А. А. Об одном методе декомпозиции в задачах программного управления динамическими системами с постоянной и переменной структурами автоматического управления // Адаптивные системы автоматического управления. Киев. 1985. № 13. С. 37-40.

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

126. Перепелица В. А. Асимптотический подход к решению некоторых экстремальных задач на графах // Проблемы кибернетики. М.: Наука. 1973. Вып. 26. С. 291-314.

127. Писсанецки С. Технология разреженных матриц. М: Мир, 1988. 356 с.

128. Пропой А. И. Элементы теории дискретных оптимальных процессов. М.: Наука, 1973.256 с.

129. Риордан Дж. Комбинаторные тождества. М.: Наука, 1982. 255 с.

130. Романовский И. В. Алгоритмы решения экстремальных задач. М.: Наука, 1977. 352 с.

131. Росс Г. В. Декомпозиционный алгоритм решения задачи смешанного целочисленного программирования для составления расписания // Алгоритм, обеспеч. и прооектир. микропроцессорных управл. систем. М., 1982. С. 25-30.

132. Рощин В.А., Семенова Н.В., Сергиенко И.В. Декомпозиционный подход к решению некоторых задач целочисленного программирования с неточными данными // Журн. вычисл. математики и матем. физики. 1990. Т. 29. № 5. С. 786-791.

133. Сараев А. Д., Щербина О. А. Системный анализ и современные информационные технологии // Труды Крымской академии наук. Симферополь: СОНАТ. 2006. С. 47-59.

134. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984. 455 с.

135. Сергиенко И. В., Каспшицкая М. Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. Киев: Наукова думка, 1981. 288 с.

136. Сергиенко И. В., Рощин В. А. Решение задачи разбиения множества с использованием параллельных вычислений // Системы программного обеспечения решения задач оптимального планирования. М.: ЦЭМИ АН СССР. 1986. С. 104-105.

137. Сергиенко И. В. Применение вектора спада для решения задач целочисленного программирования // Управляющие системы и машины. 1975. № 3. С. 86-94.

138. Сергиенко И. В., Голодников А. Н. О применении метода вектора спада в декомпозиционных схемах решения задач целочисленного линейного программирования//Кибернетика. 1984. № 1. С. 44-47.

139. Сергиенко И. В., Гуляницкий Л. Ф. Фронтальные алгоритмы оптимизации для многопроцессорных ЭВМ // Кибернетика. 1981. № 6. С. 1-4.

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

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

142. Сергиенко И. В., Лебедева Т. Т., Рощин В. А. Приближенные методы решения дискретных задач оптимизации. Киев: Наукова думка, 1980. 276 с.

143. Сергиенко И. В., Шило В. П. Задачи дискретной оптимизации: проблемы, методы решения, исследования. К.: Наукова думка. 2003. 264 с.

144. Сергиенко И. В., Шило В. П., Рощин В. А. РЕСТАРТ-технология решения задач дискретной оптимизации // Кибернетика и систем, анализ. 2000. № 5. С. 32-40.

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

146. Сергиенко И. В., Шило В. П. Проблемы дискретной оптимизации: сложные задачи, основные подходы к их решению // Кибернетика и системный анализ. 2006. № 4. С.3-25.

147. Сигал И. X., Иванова А. П. Введение в прикладное дискретное программирование. М: Физматлит, 2007. 304 с.

148. Современное состояние теории исследования операций /Под ред. Н. Н. Моисеева. М.: Наука, 1979. 464 с.

149. Схрейвер А. Теория линейного и целочисленного программирования. М.: Мир, 1991. Т. 1. 360 е.; Т. 2. 342 с.

150. Танаев В. С. Декомпозиция и агрегирование в задачах математического программирования. Минск: Наука и техника, 1987. 183 с.

151. Танаев В. С., Шкурба В. В. Введение в теорию расписаний. М.: Наука, 1975. 256 с.

152. Тесленко Е. А. Решение задач большой размерности методом декомпозиции // Моделиров. и информат. в РАС и ОГАС. Киев. 1983. С. 86-94.

153. Тизик А. П., Цурков В. И. Декомпозиционная методика для одного класса задач блочного программирования // Журн. вычисл. математики и матем. физики. 1989. Т. 29, № 10. С. 1581-1586.

154. Тьюарсон Р. Разреженные матрицы. М.: Мир, 1977. 191 с.

155. Уздемир А. П. Схема последовательной декомпозиции в задачах оптимизации // Автоматика и телемеханика. 1980. № 11. С. 94-105.

156. Финкельштейн Ю. Ю. О решении задач дискретного программирования специального вида// Экономика и матем. методы. 1965. Т. 1, № 2. С. 262-270.

157. Финкельштейн Ю. Ю. Методы решения некоторых дискретных задач математического программирования: Дисс. . канд. физ.-матем. наук. М., 1966. 110 с.

158. Финкельштейн Ю. Ю. Об одном классе задач дискретного программирования // Экономика и матем. методы. 1968. Т. 4, № 4. С. 652-655.

159. Финкельштейн Ю. Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976. 264 с.

160. Хачатуров В. Р. Алгоритм и программа решения задачи размещения с неограниченными производствами // Экономика и матем. методы. 1967. Т. 3, №2. С. 240-251.

161. Хачатуров В. Р. Аппроксимационно-комбинаторный метод и некоторые его приложения // Журн. вычисл. математики и матем.физики. 1974. Т. 14, №6. С. 1464-1487.

162. Хачатуров В. Р., Веселовский В. Е., Злотов А. В. и др. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности. М.: Наука, 2000. 354 с.

163. Хохлюк В. И. Параллельные алгоритмы целочисленной оптимизации. М.: Радио и связь, 1987. 224 с.

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

165. Хуторянская И. В. Некоторые вопросы теории локальных алгоритмов на графах//Кибернетика. 1971. № 1. С. 29-33.

166. Цурков В. И. Декомпозиция в задачах большой размерности. М.: Наука, 1981.352 с.

167. Черенин В. П. Решение некоторых комбинаторных задач оптимального планирования методом последовательных расчетов // Материалы к конференции по опыту и перспективам применения математических методов и ЭВМ в планировании. Новосибирск: СО АН СССР, 1962.

168. Щербина О. А. О задаче оптимизации предварительного резервирования гостиничных номеров // Исследование операций и АСУ. Киев: КГУ. 1976. Вып. 7. С. 105-112.

169. Щербина О. А. Оптимальное разбиение на блоки одной квазиблочной задачи булевого программирования // Сборник работ по матем. кибернетике. М.: ВЦ АН СССР. 1976. Вып. 1. С. 81-89.

170. Щербина О. А. О квазиблочных экономико-математических моделях // Экономико-математическое моделирование развития отраслей и транспорта. Киев: ИК АН УССР, 1978. С. 32-42.

171. Щербина О. А. О модифицированном локальном алгоритме решения блочных задач дискретного программирования // Журн. вычисл. математики и матем. физики. 1986. Т. 26, № 9. С. 1339-1349.

172. Щербина О. А. Экономико-математические модели развития и размещения рекреационных систем // Экономика и матем. методы. 1982. Т. 18, № 2. С. 344-348.

173. Щербина О. А. Об одной задаче дискретного программирования // Теория оптимальных решений. Киев: ИК АН УССР. 1976. С. 49-69.

174. Щербина О. А. Об одной унимодулярной задаче целочисленного программирования // Журн. вычисл. математики и матем. физики. 1986. Т. 26, N 7. С. 1096-1099.

175. Щербина О. А. Об одном локальном алгоритме для задач целочисленной оптимизации // Журн. вычисл. математики и матем. физики. 1980. Т. 20, N 3. С. 802-604.

176. Щербина О. А. Асимптотические оценки эффективности локального алгоритма в дискретном программировании. // Журн. вычисл. математики и матем. физики. 1982. Т. 22, № 6. С. 1360-1366.

177. Щербина О. А. Локальные алгоритмы для блочно-древовидных задач дискретного программирования // Журн. вычисл. математики и матем. физики.1985. Т. 25, N8. С. 1143-1154.

178. Щербина О. А. О квазиблочных задачах дискретного программирования с дополнительными ограничениями // Журн. вычисл. математики и матем. физики. 1987. Т. 27, N 5. С. 676-687.

179. Щербина О. А. О локальных алгоритмах с переменными окрестностями и индикаторной информацией // Журн. вычисл. математики и матем. физики.1986. Т. 26, N 10. С. 1588-1591.

180. Щербина О. А. О решении квазиблочных задач целочисленного линейного программирования с помощью локального алгоритма //Кибернетика. 1984. N 2. С. 118-121.

181. Щербина О. А. О локальных алгоритмах решения квазиблочных задач дискретного программирования // Проблемы кибернетики. М.: Наука. 1983. Вып. 40. С. 171-200.

182. Щербина О. А. О локальных алгоритмах решения задач дискретного программирования специальной структуры // X Internationaler Kongress über Anwendungen der Mathematik in den Ingenieur Wissenschaften. Weimar. 1984. B. 4. S. 84-87.

183. Щербина О. А. Постоптимизационный анализ в дискретном программировании (обзор) // Методы оптимизации в экономико-математическом моделировании. M.: ЦЭМИ АН СССР. 1988. С. 28-50.

184. Щербина О. А. Древовидная декомпозиция и задачи дискретной оптимизации (обзор) // Кибернетика и системный анализ. 2007. № 4. С. 102-118.

185. Щербина О. А. Методологические аспекты динамического программирования // Динамические системы. 2007. Вып. 22. С. 21-36.

186. Щербина О. А. Элиминационные алгоритмы декомпозиции задач дискретной оптимизации // Таврический вестник информатики и математики. 2006. №2. С. 28-41.

187. Щербина О. А. Локальные элиминационные алгоритмы для задач удовлетворения ограничений // Таврический вестник информатики и математики. 2007. № 1.С. 24-39.

188. Щербина О. А. Локальные алгоритмы и древовидная декомпозиция для задач дискретной оптимизации // Динамические системы. 2006. Вып. 20. С. 89-103.

189. Щербина О. А. Локальные элиминационные алгоритмы решения разреженных дискретных задач // Журнал вычислительной математики и математической физики. 2008. Т. 48, N 1. С. 161-177.

190. Щербина О. А. Роль графовых структур в теории локальных элимина-ционных алгоритмов // Динамические системы. 2008. Вып. 24. С. 83-98.

191. Щербина О. А. Применение локальных алгоритмов к решению задач целочисленного линейного программирования // Вопросы кибернетики. M.: НСК АН СССР. 1989. С. 19-34.

192. Щербина О. А. О несериальной модификации локального алгоритма декомпозиции задач дискретной оптимизации // Динамические системы. 2005. Вып. 19. С. 179-190.

193. Щербина О. А., Канаева H. Н. Об экстремальных свойствах сумм биномиальных коэффициентов // Динамические системы. 2000. Вып. 16. С. 192197.

194. Щербина О. А., Матвеев В. В. Оценки эффективности локального алгоритма для задач дискретной оптимизации // Тезисы докладов IX Межреспубликанской конференции молодых ученых. Минск: НИИЭМП. 1982. С. 141142.

195. Щербина О. А., Матвеев В. В. Об эффективности локальных алгоритмов решения квазиблочных задач целочисленного линейного программирования // Динамические системы. Киев: Вища школа. 1983. Вып. 2. С. 94-97.

196. Щербина О. А. Локальные элиминационные алгоритмы для решения некоторых задач искусственного интеллекта // Труды 11 Национальной конференции по искусственному интеллекту (Дубна, 28 сентября — 3 октября 2008 г.). М.: ЛЕНАНД, 2008. Т. 2. С. 244-252.

197. Щербина О. А. Локальные элиминационные алгоритмы обработки запросов в базах данных // Таврический вестник информатики и математики. 2009. № 2. С.53-62.

198. Aarts Е., Lenstra J. К. (eds.) Local Search in Combinatorial Optimization. New York: Wiley, 1997. 512 c.

199. Ahuja R. K., Magnanti T. L., Orlin J. B. Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs: Prentice-Hall, 1993. 846 p.

200. Ahuja R. K., Ergun O., Orlin J. В., and Punnen A. P. A survey of very large-scale neighborhood search techniques // Discrete Appl. Math. 2002. V. 123, Issues 1-3, P. 75-102.

201. Aida K., Natsume W., Futakata Y. Distributed computing with hierarchical master-worker paradigm for parallel branch and bound algorithm // Proceedings of Third Int. Symposium on Cluster Computing and Grid CCGRID 2003. P. 156-163.

202. Aida K., Osumi T. A case study in running a parallel branch and bound application on the grid // Proc. of the The 2005 Symposium on Applications and the Internet SAINT'05, IEEE Computer Society, Washington, 2005. P. 164-173.

203. Alber J., Dorn F., and Niedermeier R. Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs // Discrete Appl. Math. 2005. V. 145. P. 219-231.

204. Alliance portal project, scientific portals, Argonne National Labs.

205. URL: http://www.extreme.indiana.edu/alliance/docandpres/SC2002PortalTalk.pdf (дата обращения 23.08.2010).

206. Alpert С. J., Yao S. Z. Spectral partitioning: the more eigenvectors, the better // 32th DAC, ACM/IEEE, 1995. P. 195-200.

207. Amestoy P. R., Davis T. A., Duff I. S. An approximate minimum degree ordering algorithm // SIAM Journal on Matrix Analysis and Applications. 1996. V. 17, N4. P. 886-905.

208. Anstreicher К. M., Brixius N. W., Goux J.-P., and Linderoth J. Solving large quadratic assignment problems on computational grids // Math. Programming. 2002. V. 91. P. 563-588.

209. Antonio J. K., Tsal W. K., and Huang G.M. A highly parallel algorithm for multistage optimization problems and shortest path problems // Journal of Parallel and Distributed Computing. 1991. V. 12. P. 213-222.

210. Applegate D, Bixby R., Chvatal V., and Cook W. On the solution of traveling salesman problems // Documenta Mathematica, Journal der Deutschen Mathematiker-Vereinigung, International Congress of Mathematicians. 1998.

211. Applegate D., Bixby R., Chvatal V., and Cook W. CONCORDE TSP Solver. URL: http://www.tsp.gatech.edu/concorde.html (дата обращения 23.08.2010).

212. Aris R., Nemhauser G. L., Wilde D. Optimization of multistage cyclic and branching system serial procedures // A. I. Ch. E. Journal. 1964. V. 10. P. 913-919.

213. Armstrong R. D. Experiments in a multiple choice mixed integer programming algorithm // Opsearch. 1977. V. 14. P. 215-228.

214. Armstrong R. D., Kung D-S., Sinha P., Zoltners A. A. A computational study of a multiple-choice knapsack algorithm // ACM Transactions on Mathematical Software. 1983. V. 9. P. 184-198.

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

216. Arnborg S., Lagergren J., Seese D. Easy problems for tree-decomposable graphs // J. Algorithms. 1991. V. 12, N2. P. 308-340.

217. Arnborg S., Proskurowski A. Characterization and recognition of partial k-trees // SIAM J. Alg. Discr. Meth. 1986. V. 7. P. 305-314.

218. Ashcraft C. Compressed graphs and the minimum degree algorithm // SIAM J. Sci. Comput. 1995. V. 16. P. 1404-1411.

219. Ashcraft C., Liu J.W.H. Robust ordering of sparse matrices using multisection // SIAM J. Matrix Anal. Appl. 1995. V. 19. P. 816-832.

220. Atamturk A., Savelsbergh M. W. P. Integer-programming software systems // Annals of Operations Research. 2005. V. 140. P. 67-124.

221. Ausiello G., Crescensi P., Gambosi G., Kann V., Marchetti-Spaccamela A., Protasi M. Complexity and Approximation (combinatorial optimization problems and their approximability properties). Berlin: Springer-Verlag, 1999. 524 p.

222. Avramita G. M. Decomposition and solving of large-scale problems in production scheduling // Economic Computation and Economic Cybernetics Studies and Research. 1978. V. 12, N 1. P. 63-76.

223. Bachem A., Euler R. Recent trends in combinatorial optimization // Operations Research Spektrum. 1984. V. 6. P. 1-22.

224. Bachoore E. and Bodlaender H. L. New upper bound heuristics for tree-width // Proc. 4th Intern. Workshop on Experimental and Efficient Algorithms WEA 2005 / S. E. Nikoletseas (ed.). LNCS 3503. Berlin: Springer-Verlag, 2005. P. 217-227.

225. Balas E., Bergthaller C. Benders' method revisited // Journal of Computational and Applied Mathematics. 1983. V. 9. P. 3-12.

226. Balas E., Ceria S., and Cornuejols G. (1996) Mixed 0-1 programming by lift-and-project in a branch-and-cut framework // Management Science. 1996. V. 42. P. 1229-1246.

227. Balintfy J. L. Menu planning by computer // The Communications of ACM. 1964. V. 7. P. 255-259.

228. Barbera R., Falzone A., Rodolico A. The Genius grid portal // Proc. of Computing in High Energy and Nuclear Physics, La Jolla, California, 2003. P. 24-28.

229. Barnes E. R., Hoffman A .J. Partitioning, spectra, and linear programming // Progress in Combinatorial Optimization / W.E. Pulleyblank, ed. Academic Press, 1984. P. 13-25.

230. Barnes E. R., Vannelli A., and Walker J. Q. A new heuristic for partitioning the nodes of a graph // SIAM J. Discr. Math. 1988. V.l. P. 299-305.

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

232. Barnier N., Brisset P. Graph coloring for air traffic flow management // Annals of Operations Research. 2004. V. 130. P. 163-178.

233. The Temporal Knapsack Problem and its solution / M. Bartlett et al. // Second International Conference on the Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR, May 2005). P. 34-48.

234. Batoukov R., Soverik T. A generic parallel branch-and-bound environment on a network of workstations // Proceedings of Hiper-99, 1999. P. 474-483.

235. Beale E. M. L. Branch and bound methods for mathematical programming systems // Ann. Discrete Math. 1979. V. 5. P. 201-219.

236. Becker A., Geiger D. A sufficiently fast algorithm for finding close to optimal clique trees //Artificial Intelligence. 2001. V. 125. P. 3-17.

237. On the desirability of acyclic database systems / C. Beeri et al. // J. ACM. 1983. V. 30. P. 479-513.

238. Beightler Ch. S., Phillips D., Wilde D. Foundations of Optimization. Eng-lewood Cliffs: Prentice-Hall. 1979. 487 p.

239. Bellman R., Dreyfus S. Applied Dynamic Programming. Princeton: Princeton University Press, 1962. 363 p.

240. Building a parallel branch and bound library / M. Benchouche et al. //Solving Combinatorial Optimization Problems in Parallel. LNCS 1054. Berlin: Springer, 1996. 221 p.

241. Benders J. F. Partitioning procedures for solving mixed variables programming problems //Numerische Mathematik. 1962. V. 4, N 3. P. 238-252.

242. Berge С. Färbung von Graphen, deren sämtliche bzw deren ungerade Kreise starr sind (Zusammenfassung) // Wiss. Z. Martin-Luther-Univ., Halle-Wittenberg, Math.-Natur. Reihe, 1961. V. 10. P. 114-115.

243. Bernstein P. A., Goodman N. Power of natural semijoins // SIAM J. Comput. 1981. V. 10, N 4. P. 751-771.

244. Berry A. A wide-range efficient algorithm for minimal triangulation // Proceedings of SODA, 1999.

245. Berry A., Blair J., Heggernes P., Peyton B. Maximum cardinality search for computing minimal triangulations of graphs // Algorithmica. 2004. V. 39. P. 287298.

246. Berry A., Heggernes P., and Villanger Y. A vertex incremental approach for maintaining chordality//Disc. Math. 2006. V. 306. P. 318-336.

247. Berry A. Graph extremities and minimal separation URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=l0.1.1.5.2872 (дата обращения 23.08.2010).

248. Bertele U., Brioschi F. A new algorithm fort he solution of the secondary optimization problem in nonserial dynamic programming // Journal of Mathematical Analysis and Applications. 1969. V. 27. P. 565-574.

249. Bertele U., Brioschi F. Contribution to nonserial dynamic programming // Journal of Mathematical Analysis and Applications. 1969. V. 28. P. 313-325.

250. Bertele U., Brioschi F. A theorem in nonserial dynamic programming // Journal of Mathematical Analysis and Applications. 1970. V. 29. P. 351-353.

251. Bertele U., Brioschi F. Parametrization in nonserial dynamic programming // Rev. Française Informat. Recherche Opérationelle. 1971. V. 2. P. 87-102.

252. Bertele U., Brioschi F. Nonserial Dynamic Programming. New York: Academic Press, 1972. 235 p.

253. Bertele U., Brioschi F. On nonserial dynamic programming // Journal of Combinatorial Theory (A). 1973. V. 14. P. 137-148.

254. Bertsekas D. P., Tsitsiklis J. N. Parallel and Distributed Computation: Numerical Methods. Englewood Cliffs: Prentice-Hall, 1989. 715 p.

255. Bixby R., Cook W., Cox A., and Lee E. K. Parallel Mixed Integer Programming. Rice University: Center for Research on Parallel Computation Research. Monograph CRPC-TR95554, 1995.

256. Bixby R., Cook W., Cox A., and Lee E.K. Computational experience with parallel mixed integer programming in a distributed environment // Annals of Operations Research. 1999. V. 90. P. 19-43.

257. Bixby R. E., Fenelon M., Gu Z., Rothberg E. E., and Wunderling R. MIP: Theory and Practice Closing the Gap. Kluwer Academic Publishers, 2000. P. 1949.

258. Blair J. R. S., Peyton B. W. An introduction to chordal graphs and clique trees // Sparse Matrix Computations: Graph Theory Issues and Algorithms / J. A.George, J. R.Gilbert, J. W. H. Liu (eds). Springer Verlag. 1993. P. 1-30.

259. Blair J. R., Heggernes P., and Telle J. A. A practical algorithm for making filled graphs minimal // Theor. Comput. Sci. 2001. V. 250. P. 125-141.

260. Blair J. R., England R. E., and Thomason M. G. Cliques and their Separators in Triangulated Graphs. Technical Report UT-CS-88-73. University of Tennessee, 1988.

261. Bodlaender H. L. Discovering treewidth // Proceedings of SOFSEM. LNCS 3381. Springer-Verlag. 2006. P. 1-16.

262. Bodlaender H. L. A tourist guide through treewidth // Acta Cybernetica. 1993. V. 11. P. 1-21.

263. Bodlaender H. L. Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees // J. Algorithms. 1990. Y. 11. P. 631-643.

264. Bodlaender H. L. A linear-time algorithm for finding tree-decompositions of small treewidth // SIAM J. Comput. 1996. V. 25. P. 1305-1317.

265. Bodlaender H. L., Koster A. M. C. A. Safe separators for treewidth // Proc. 6th Workshop on Algorithm Engineering and Experiments ALENEX04, 2004. P. 70-78.

266. Bodlaender H. L., Koster A. M. C. A., and Wolle T. Contraction and treewidth lower bounds // Proc. 12th Ann. Eur. Symp. on Algorithms, ESA2004 / S. Albers and T. Radzik (eds.). LNCS 3221. Berlin: Springer, 2004. P. 628-639.

267. Bodlaender H. L., Koster A. M. C. A. Combinatorial optimization on graphs of bounded treewidth // Computer Journal. 2008. V. 51. P. 255-269.

268. Borgwardt K.-H. The average number of steps required by the simplex method is polynomial // Z. Oper. Res. 1982. V. 26. P. 157-177.

269. Borie R. B., Parker R. G., and Tovey C. A. Deterministic decomposition of recursive graph classes // SIAM J. Discret. Math. 1991. V. 4. P. 481-501.

270. Borndorfer R., Ferreira C.E., Martin A. Decomposing matrices into blocks // SIAM J. Optim. 1998. V. 9. P. 236-269.

271. Bouchitte V., Mazoit F., and Todinca I. Chordal embeddings of planar graphs // Discrete Math. 2003. V. 273. P. 85-102.

272. Bouchitte V., Kratsch D., Muller H., Todinca I. On treewidth approximations // Discrete Appl. Math. 2004. V. 136. P. 183-196.

273. Brioschi F., Even S. Minimizing the number of operations in certain discrete variable optimization problems // Operations Research. 1970. V. 18, N 1. P. 66-81.

274. Brown G.E. Towards a vision for the NEES collaboratory, NEES Consortium Development Project.

275. URL: http://www.curee.org/projects/NEES/docs/outreach/VisionWhitePaperV3.pdfдата обращения 23.08.2010).

276. Brown R.G. Engineering a Beowulf-style Compute Cluster, 2004.

277. URL: http://www.phy.duke.edu/~rgb/Beowulf/beowulf book/beowulf book.a4.pdfдата обращения 23.08.2010).

278. Bui Т., Jones С. A heuristic for reducing fill in sparse matrix factorization // Proc. 6th SIAM Conf. Parallel Processing for Scientific Computing. SIAM, Philadelphia, 1993. P. 445-452.

279. Buneman P. A characterization of rigid circuit graphs // Discrete Math. 1974. V. 9. P. 205-212.

280. Burkard R. E., Hamacher H. W., Tind J. On general decomposition schemes in mathematical programming // Math. Program. Study. 1985. V. 24. P. 238-252.

281. Bussieck M. R., Ferris M. C., and Meeraus A. Grid-enabled optimization with GAMS // INFORMS J. on Computing. 2009. V. 21. P. 349-362.

282. Cano A. and Moral S. Heuristic algorithms for the triangulation of graphs // Advances in Intelligent Computing (LPMU94) / B. Bouchon-Meunier, R. R. Yager and I. A. Zadeh (eds.). LNCS 945. Berlin: Springer-Verlag, 1995. P. 98-107.

283. Castellani G., Giannessi F. Decomposition of mathematical programs by means of theorems of alternative for linear and nonlinear systems //A.Prekopa (Ed.): Survey of mathematical programming. Amsterdam: North Holland. 1979. V. 2. P. 423-440.

284. Casti J. Dynamic programming // Optimization Theory and Applications. 1973. N4. P. 423-438.

285. Chandru V., Rao M. R. Integer Programming // Foundations of Algorithms and Theory of Computation / M. Atallah, M. Blanton (eds.). CRC Press, 2009. P. 31.1-31.45.

286. Chandy К. M., Misra J. Distributed computation on graphs: shortest path algorithm// Communications ACM. 1982. V. 25, N 11. P. 833-837.

287. Chang E.J.H. Echo algorithms: depth parallel operations on general graphs // IEEE Trans.Software Eng. 1982. V. 8, N 4. P. 391-401.

288. Chen Q., Ferris M.C., Linderoth J.T. Fatcop 2.0: Advanced features in an opportunistic mixed integer programming solver // Annals of Operations Research. 2001. V. 103. P. 17-32.

289. Christofides N., Brooker P. The optimal partitioning of graphs // SIAM J. Appl. Math. 1976. V. 30. P. 55-69.

290. Clautiaux F., Carlier J., Moukrim A., and Negre S. New lower and upper bounds for graph treewidth // Proc. Intern. Workshop on Experimental and Efficient Algorithms, WEA 2003 / J. D. P. Rolim (ed.). LNCS 2647. Berlin: Springer-Verlag, 2003. P. 70-80.

291. Clautiaux F., Moukrim A., Negre S., and Carlier J. Heuristic and meta-heuristic methods for computing graph treewidth // RAIRO Oper. Res. 2004. V. 38. P. 13-26.

292. Clausen J. Parallel branch and bound principles and personal experiences //Parallel Computing in Optimization, Applied Optimization / A. Migdalas, P. M. Pardalos, and S. Storay, eds. Kluwer Academic Publishers, 1997.

293. Codd E. F. A relational model of data for large shared data banks // Commun. ACM. 1970. V. 13. P. 377-387.

294. Commandeur M. Solving Vertex Coloring using Tree Decompositions. Master's Thesis, Univ. Maastricht, 2004.

295. Conforti M., Cornuejols G., and Zambelli G. Polyhedral Approaches to Mixed Integer Linear Programming // 421. P. 343-386.

296. Cook S. A. The complexity of theorem-proving procedures // Proc. 3rd Ann. ACM Symp. on Theory of Computing Machinery. New York. 1971. P. 151-158.

297. Cook S. A. An overview of computational complexity // ACM Communications. 1983. V. 26. P. 400-408.

298. Cook W., Seymour P. D. An algorithm for the ring-routing problem / Bellcore technical memorandum. Bellcore, 1994.

299. Cornuejols G., Nemhauser G.L., Wolsey L.A. Worst-case and probabilistic analysis of algorithms for a location problem // Operations Research. 1980. V. 28. P. 847-858.

300. Correa R. Ferreira A. Parallel Best-first Branch and Bound in Discrete Optimization: A Framework. Technical Report 95-03. Center for Discrete Mathematics and Theoretical Computer Science, 1995.

301. Cote G., Laughton M-A. Large-scale mixed integer programming: Benderstype heuristics // European Journal of Operational Research. 1984. V. 16. P. 327333.

302. Courcelle B. Graph rewriting: An algebraic and logic approach. // Handbook of Theoretical Computer Science. Volume B / J. Van Leeuwen (ed.). Elsevier. 1990. P. 193-242.

303. Crowder H., Johnson E.L., Padberg M.W. Solving large-scale zero-one linear programming problems // Operations Research. 1983. V. 31. P. 803-834.

304. Dantzig G. B. Programming of interdependent activities II: Mathematical model // Econometrica. 1949. V. 17. P. 200-211.

305. Dantzig G. B. Time-staged methods in linear programming. Comments and early history // Large-Scale Linear Programming / G. B. Dantzig,

306. M. A. H. Dempster and M. J. Kallio, eds. Laxenburg: International Institute for Applied Systems Analysis, 1981. P. 3-16.

307. Davis T.A., Amestoy P. and Duff I.S. An approximate minimum degree ordering algorithm // SIAM J. Matrix Anal. Appl. 1996. V. 17. P. 886-905.

308. Dechter R. Bucket elimination: A unifying framework for reasoning // Artificial Intelligence. 1999. V. 113. P. 41-85.

309. Dechter R., El Fattah Y. Topological parameters for time-space tradeoff // Artificial Intelligence. 2001. V. 125, N 1-2. P. 93-118.

310. Dechter R. Constraint Processing. Morgan Kaufmann. 2003. 481 p.

311. Dechter R., Pearl J. Tree clustering for constraint networks // Artificial Intelligence. 1989. V. 38. P. 353-366.

312. Dell'Amico M., Maffioli F., Martello S. (eds). Annotated Bibliographies in Combinatorial Optimization. Chichester: John Wiley & Sons Ltd, 1997.

313. Dempe S. Worst-case and average-case analysis of an algorithm solving a generalized knapsack problem // Mathematische Operationsforschung und Statistik. 1983. V. 14. P. 551-564.

314. Deo N., Krishnamoorthy M. S., and Langston M. A. Exact and approximate solutions for the gate matrix layout problem // IEEE T-CAD. 1987. V. 6. P. 79-84.

315. Dirac G.A. On rigid circuit graphs // Anh. Math. Sem. Univ. Hamburg. 1961. V. 25. P. 71-76.

316. Dobson G. Worst-case analysis of greedy heuristics for integer programming with nonnegative data // Mathematics of Operations Research. 1982. V. 7. P. 515531.

317. Dorigo M., Birattari M., Stutzle T., Ant colony optimization artificial ants as a computational intelligence technique // IEEE Computational Intelligence Magazine. 2006. V. l.P. 28-39.

318. Downey R.G., Fellows M.R. Parametrized complexity. Monographs in Computer Science. Springer-Verlag, 1999. 533 p.

319. Dreo J., Petrowski A., Siarry P., Taillard E., Metaheuristics for Hard Optimization. Springer, 2006.

320. A Grid-enabled Distributed Branch-And-Bound Algorithm with Application on the Steiner Problem in Graph / L. M. A. Drummond et al.. Technical Report, Universidade federal Fluminense, Instituto de Computacao, 2004.

321. Eckstein J. Parallel branch-and-bound algorithms for general mixed integerprogramming on the CM-5 // SIAM J. Optimization. 1994. V. 4. P. 794-814.

322. Eckstein J., Phillips C. A., and Hart W. E. PICO: An Object-Oriented Framework for Parallel Branch and Bound, RUTCOR Research Report 40-2000, Rutgers University, Piscataway, 2000.

323. Eckstein J., Phillips C. A., Hart W. E. PEBBL 1.0 user guide, 2009. URL: https://software.sandia.gov/Acro/releases/votd/acro/packages/pebbl/doc/uguide/user -guide.pdf (дата обращения 23.08.2010).

324. Elf M., Gutwenger С., Jünger М., and Rinaldi G. Branch-and-cut algorithms for combinatorial optimization and their implementation in ABACUS // Computational Combinatorial Optimization / D. Naddef, M. Jünger (eds.). Berlin: Springer, 2001.

325. Emden-Weinert Т., Hougardy S., Kreuter В., Prömel H. J., and Steger A. Einfuhrung in Graphen und Algorithmen (URL: http://www.informatik.hu-berlin.de/alkox/lehre/skripte/ga) (дата обращения 23.08.2010).

326. Esogbue А. О., Marks В. R. Non-serial dynamic programming a survey // Operational Research Quarterly. 1974. V. 25, N 2. P. 253-265.

327. Even S. Graph Algorithms. Rockville: Computer Science Press, 1979.

328. Falkner J., Rendl E., and Wolkowicz H. A computational study of graph partitioning // Math. Progr. 1994. V. 66. P.211-240.

329. Ferreira С. E., Grötschel M., Kiefl S., Krispenz C., Martin A., Weismantel R. Some integer programs arising in the design of main frame computers // ZOR -Methods and Models of Operations Research. 1993. V. 38. P. 77-100.

330. Ferreira С. E. On Combinatorial Optimization Problems Arising in Computer System Design. PhD thesis. Berlin: Technische Universität, 1994.

331. Ferreira A., Pardalos P., eds. Solving Combinatorial Optimization Problems in Parallel: Methods and Techniques, LNCS 1054, State-of-the-Art Surveys, Springer-Verlag, 1996.

332. Ferris M. C., Pataki G., and Schmieta S. Solving the Seymour problem // Optima. 2001. V. 66. P. 1-7.

333. Ferris M. C., Maravelias C. T., and Sundaramoorthy A. Using grid computing to solve hard planning and scheduling problems // Proceedings of 18th European Symposium on Computer-Aided Process Engineering (ESCAPE 18), Lyon, France, June 1-4, 2008.

334. Fiduccia C. M., Mattheyses R. M. A linear-time heuristics for improving network partitions // Proc. 19th ACM/IEEE Design Automation Conference, 1982. P. 175-181.

335. Fiedler M. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory // Czechoslovak Math. Journal. 1975. V. 25. P. 619-633.

336. Filho J. V., Drummond L. M. A., Uchoa E., Castro M. C. S. Towards a Grid Enabled Branch-and-Bound Algorithm. Report RT-05/03, Department of Computer Science, Fluminense Federal University, 2003.

337. Fischer S. T., A note on the complexity of local search problems // Inf. Process. Lett. 1995. V. 53. P. 69-75.

338. Flake G. W., Taijan R. E., Tsioutsiouliklis K. Graph clustering and minimum cut trees // Internet Mathematics. 2003. 1, N4. P. 385-408.

339. Flores M. J. Bayesian networks inference: Advanced algorithms for triangulation and partial abduction. Ph.D. Thesis, University de Castilla, La Mancha, 2005.

340. Flores M. J., Gamez J. A. Triangulation of Bayesian networks by retriangulation // Int. J. Intelligent Systems. 2003. V. 18. P. 153-164.

341. Flores M. J., Gamez J. A. A Review on Distinct Methods and Approaches to Perform Triangulation for Bayesian Networks // Advances in Probabilistic Graphical Models, Studies in Fuzziness and Soft Computing, Vol. 214. Springer, 2007. P. 127-152

342. Floudas C. A. Nonlinear and mixed-integer optimization: fundamentals and applications. Oxford: Oxford Univ.Press, 1996. 462 p.

343. Floudas C. A. Deterministic Global Optimization. Theory, Algorithms and Applications. Kluwer Academic Publishers. 2000. 760 p.

344. Fomin F. V., Kratsch D., Todinca I. Exact (exponential) algorithms for treewidth and minimum fill-in // Proceedings of the 31st International Colloquium on Automata, Languages and Programming. LNCS 3124. Berlin: Springer Verlag, 2004. P. 568-580.

345. Foster I., Kesselman C. (eds). The Grid: Blueprint for a New Computing Infrastructure. San Francisco: Morgan Kaufmann Publishers Inc., 1998. 677 p.

346. Frank A. Packing paths, circuits, and cuts a survey // Paths, Flows, and VLSI-Layout / B. Korte, L. Lovasz, H.J. Promel, and A. Schrijver, eds. Berlin: Springer-Verlag. P. 47-100.

347. Frieze A. M., Clarke H. R. B. Approximation algorithms for the tridimensional 0-1 knapsack problem: worst-case and probabilistic analyses // European Journal of Operational Research. 1984. V. 15. P. 100-109.

348. Fulkerson D. R., Gross O. A. Incidence matrices and interval graphs // Pacific Journal of Math. 1965. V. 15. P. 835-855.

349. Gavril F. The intersection graphs of subtrees in trees are exactly the chordal graphs // J. Combinatorial Theory Ser.B. 1974. V. 16. P. 47-56.

350. Gendron B., Crainic T. G. Parallel branch and bound algorithms: Survey and synthesis // Operations Research. 1994. V. 42. P. 1042-1066.

351. Oobb: Object-oriented tools for parallel branch-and-bound /B. Gendron. Centre for Research on Transportation, Universite de Montreal, Montreal, 2005.

352. Genetic algorithms and simulated annealing / L. Davis (ed.). Los Altos: Morgan Kauffmann. 1987. 216 p.

353. Gens B. V., Levner E. V. Complexity of approximation algorithms for combinatorial problems: a survey // Sigact News. 1980. V. 12, N 3. P. 52-65.

354. Geoffrion A. M. Lagrangean relaxation for integer programming // Mathematical Programming Study. 1974. V. 2. P. 82-114.

355. Geoffrion A. M. An improved implicit enumeration approach for integer programming 11 Operations Research. 1969. V. 17, N 3. P. 437-454.

356. Geoffrion A. M. A guided tour of recent practical advances in integer linear programming // Omega. 1976. V. 4, N 1 P. 49-57.

357. Geoffrion A. M., Marsten R. E. Integer programming algorithms: a framework and state-of-the-art survey // Management Science. 1972. V. 18, N 9. P. 465491.

358. George J. A. Nested dissection of a regular finite element mesh // SIAM J. Numer. Anal. 1973. V. 10. P. 345-367.

359. George A., Poole J. W., and Voigt R. Incomplete nested dissection for solving $n$ by $n$ grid problems // SIAM J. Numer. Anal. 1978. V. 15. P. 663-673.

360. George J. A., Liu J.W.H. Computer solution of large sparse positive definite systems. 1981. Englewood Cliffs: Prentice-Hall Inc. 324 p.

361. George J. A., Liu J.W.H. The evolution of the minimum degree ordering algorithm//SIAM Rev. 1989. V. 31. P. 1-19.

362. Gilmore P. C., Hoffman A. J. A characterization of comparability graphs and of interval graphs // Can. J. Math. 1964. V. 16. V. 539-548.

363. Giulianelly S., Lucertini M. A decomposition technique in integer linear programming // Lecture Notes Comput. Sci. 1976. V. 41. P. 86-97.

364. Glover F. Future paths for integer programming and links to artificial intelligence // Comput. & Ops. Res. 1986. V. 13, N 5. P. 533-549.

365. Glover F. and Laguna M. Tabu Search. Boston: Kluwer, 1997. 382 p.

366. Gogate V., Dechter R. A complete anytime algorithm for treewidth // Proceedings of UAI, 2004. P. 201-208.

367. Golumbic M. C. Algorithmic Graph Theory and Perfect Graphs. New York: Academic Press, 1980. 284 p.

368. Gomory R. E., Hu T. C. Multi-terminal network flows // J. SIAM. 1961. V. 9. P. 551-570.

369. Gorry G. A., Shapiro J. F., Wolsey L. A. Relaxation methods for pure and mixed integer programming problems // Management Science. 1972. V. 18, N 5. P. 229-239.

370. Gottlob G., Leone N., Scarcello F. Hypertree decompositions: A survey // In Mathematical foundations of computer science. 26th international symposium, MFCS 2001. Proceedings. Berlin: Springer. LNCS 2001. 2136. P. 37-57.

371. Goux J.-P., Leyffer S. Solving large MINLPs on computational grids // Optimization and Engineering. 2002. V. 3. P. 327-354.

372. Grama A., Kumar V. Parallel search algorithms for discrete optimization problems // ORSA Journal on Computing. 1995. V. 7. P. 365-385.

373. Grama A., Kumar V. State of the art in parallel search techniques for discrete optimization problems // IEEE Transactions on Knowledge and Data Engineering. 1999. V. 11. P. 28-35.

374. Legion: An Operating System for Wide-Area Computing / A. Grimshaw et al.. Technical report, 1999.

375. Groetschel M., Jünger M., and Reinelt G. A cutting plane algorithm for the linear ordering problem // Operations Research. 1984. V. 32. P. 1195-1220.

376. Groetschel M., Lovasz L., Schrijver A. Ellipsoid method and its consequences in combinatorial optimization// Combinatorica. 1981. V. 1. P. 169-197.

377. Groetschel M., Lovasz L., Schrijver A. Polynomial algorithms for perfect graphs //Ann. Discrete Math. 1984. V. 21. P. 325-356.

378. Grótschel M., Lovász L., Schrijver A. Geometric Algorithms and Combinatorial Optimization. New York: Springer-Verlag, 1988. 362 p.

379. Gu J., Purdom P. W., Franco J., Wah B. W. Algorithms for the satisfiability (SAT) problem: A survey // Satisfiability Problem Theory and Applications. 1997. P. 19-153.

380. Gupta A. Highly scalable parallel algorithms for sparse matrix ordering // IBM J. Res. Development 1997. V. 41. P. 171-184.

381. Gupta A., Karypis G., Kumar V. Fast and effective algorithms for graph partitioning and sparse matrix ordering // IBM J. Res. Development. 1997. V. 41. P. 171184.

382. Hajnal A., Suränyi J. Über die Ausflösung von Graphen in vollständige Teilgraphen // Ann. Univ. Sei. Budapest. 1958. P. 113-121.

383. Hajos G. Über eine Art von Graphen // Internat. Math. Nachr. 1957. V. 47, Problem 65.

384. Handbook of genetic algorithms / L. Davis (ed.). New York: Van Nostrand Reinhold. 1991.385 p.

385. Hansen E., Walster G. W. Global optimization using interval analysis second edition, revised and expanded. N.Y. Basel: Marcel Dekker, Inc. 2004. 489 p.

386. Hansen P, Mladenovic N. Developments of variable neighborhood search // Essays and surveys in metaheuristics / C. Ribeiro, P. Hansen (eds.). Boston, Dordrecht, London: Kluwer Academic Publishers, 2001. P. 415-440.

387. Hansen P., Mladenovic N., and Urosevic D. Variable neighborhood search and local branching // Comput. Oper. Res. 2006. 2006. V. 33. P. 3034-3045.

388. Harary F., Norman R. Z., Cartwright D. Structural Models: An Introduction to the Theory of Directed Graphs. John Wiley & Sons, 1966. 415 p.

389. Hausmann D., Kannan R., Korte B. Exponential lower bounds on a class of knapsack algorithms // Mathematics of Operations Research. 1981. V. 6. P. 225232.

390. Hausmann D., Korte B. Lower bounds on the worst-case complexity of some oracle algorithms // Discrete Mathematics. 1978. V. 24. P. 261-276.

391. Healy W. C. Multiple choice programming // Operations Research. 1964. V. 12. P. 122-138.

392. Heggernes P. Minimal triangulations of graphs: A survey //Discrete Mathematics. 2006. V. 306, N 3. P. 297-317.

393. Heggernes P., Telle J. A., and Villanger Y. Computing minimal triangulations in time 0(nXalphaMosn) = o(n2376) // SIAM J. Discret. Math. 2005. V. 19. P. 900-913.

394. Hendrickson В., Leland R. The Chaco user's guide. Version 2.0. Technical Report SAND95-2344. Sandia National Laboratories, 1995.

395. Hendrickson В., Leland R. A multilevel algorithm for partitioning graphs // Proc. Supercomputing '95, ACM, San-Diego, 1995.

396. Hendrickson В., Rothberg E. Improving the run time and quality of nested dissection ordering // SIAM J. Sei. Comput. 1998. V. 20(2). P. 468-489.

397. Width parameters beyond tree-width and their applications / P. Hlineny et al. // The Computer Journal. 2008. V. 51. P. 326-362.

398. Ho J. K., Loute E. A set of staircase linear programming test problems // Mathematical Programming. 1981. 20. P. 245-250.

399. Ho C. W., Lee R. C. Counting clique trees and computing perfect elimination schemes in parallel // Inf. Process. Lett. 1989. V. 31. P. 61-68.

400. Hoffman K., Padberg M. LP-based combinatorial problem solving // Annals of Operations Research. 1985. V. 4. P. 145-194.

401. Holland J. H. Adaptation in Natural and Artificial Systems. University of Michigan Press, 1975. 183 p.

402. Hong J. W. On lower bounds of time complexity of some algorithms // Scien-tia Sinica. 1979. V. 22. P. 890-900.

403. Hooker J. Logic-based methods for optimization: combining optimization and constraint satisfaction. John Wiley, 2000. 495 p.

404. Hromkovic J. Algorithmics for hard problems. Berlin-Heidelberg: SpringerVerlag. 2001.494 р.

405. Hummeltenberg W., Implementations of special ordered sets in MP software // Eur. J. Operational Research. 1984. V. 17. P. 1-15.

406. Ibaraki T. On the computational efficiency of branch-and-bound algorithms // Journal of the Operations Research Society of Japan. 1977. V. 20. P. 16-35.

407. Ibaraki T. Approximate algorithms for the multiple-choice continuous knapsack problem // Journal of the Operations Research Society of Japan, 1980. V. 23. P. 28-63.

408. Jégou P., Ndiaye S. N., Terrioux C. Computing and exploiting tree-decompositions for (Max-)CSP // Proceedings of the 11th International Conference on Principles and Practice of Constraint Programming (CP-2005). 2005. P. 777-781.

409. Johnson M., Zoltners A., Sinha P. An allocation model for catalog space planning // Management Science. 1979. V. 25. P. 117-129.

410. JOSTLE graph partitioning software. URL: http://staffweb.cms.gre.ac.uk/~wc06/iostle/ (дата обращения 23.08.2010).

411. Jünger M., Thienel S. The ABACUS system for branch and cut and price algorithms in integer programming and combinatorial optimization // Software Practice and Experience. 2000. V. 30. P. 1325-1352.

412. Karypis G., Kumar V. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. TR 95-035. University of Minnesota, 1995.

413. Karypis G., Kumar V. MeTiS a software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. Version 4. University of Minnesota, 1998.

414. URL: http://www-users.cs.umn.edu/~karypis/metis (дата обращения 23.08.2010).

415. Karypis G., Aggarwal R., Kumar V., Shekhar S. Multilevel hypergraph partitioning: applications in VLSI domain // IEEE Trans. Very Large Scale Integr. Syst. 1999. V. 7. P. 69-79.

416. Kask K., Dechter R., Larrosa J., Dechter A. Unifying cluster-tree decompositions for reasoning in graphical models // Artificial Intelligence. 2005. V. 160. P.165-193.

417. Kececioglu J. D., Myers E. W. Combinatorial algorithms for DNA sequence assembly//Algorithmica. 1995. V. 13. P. 7-51.

418. Kernighan B.W., Lin S. An efficient heuristic procedure for partitioning graphs // The Bell System Techn. Journal. 1970. V. 49. P. 291-307.

419. Kirkpatrick S.; Gelatt C. D., Vecchi M. P. Optimization by simulated annealing // Science. 1983. V. 220. P. 671-680.

420. Kjaerulff U. Triangulation of graphs algorithms giving small total state space. Techn.report. Aalborg, Denmark, 1990. 35 p.

421. Kjaerulff U. Optimal decomposition of probabilistic networks by simulated annealing // Statistics and Computing. 1992. V. 2. P. 2-17.

422. Klee V., Minty G. J. How good is the simplex algorithm? // Inequalities, III / O. Shisha (ed.). New York: Academic Press, 1972. P. 159-175.

423. Kloks T. Treewidth: Computations and Approximations. New York: Springer, 1994. 209 p.

424. Kluyver C. A. Solving the multi-index transportation problem by decomposition // Economic Computation and Economic Cybernetics Studies and Research. 1979. V. 13.-P. 85-105.

425. Korte B. Approximative algorithms for discrete optimization problems // P. L. Hammer, E. L. Johnson, В. H. Korte (Eds.): Discrete Optimization I. Annals of Discrete Mathematics. Amsterdam, New York, Oxford: North Holland. 1979. V. 4. P. 85-120.

426. Korte В., Lovasz L. Mathematical structures underlying greedy algorithms // Fundamentals of Computation Theory / F. Gecseg (ed.). Lecture Notes in Computer Science 117. Berlin: Springer, 1981. P. 205-209.

427. Korte В., Schräder R. On the existence of fast approximation schemes //Nonlinear Programming 4 / O. L. Hanbasarian, R. R. Meyer, P. M. Robinson (eds.). New York: Academic Press. 1981. P. 415-438.

428. Korte В., Schräder R. Survey on oracle techniques // Mathematical Foundations of Computer Science / J.Gruska, M. Chytil (eds.). Lecture Notes in Computer Science 118. Berlin: Springer. 1981. P. 61-77.

429. Köster A. M. C. A. Frequency Assignment Models and Algorithms. PhD Thesis, Maastricht: Maastricht Univ., 1999.

430. Köster A. M. C. A., Bodlaender H. L., van Hoesel S. P. M. Treewidth: Computational experiments // Electronic Notes in Discrete Mathematics / H. Broersma, U. Faigle, J. Hurink, S. Pickl (eds). Elsevier Science Publishers. 2001. V.8.

431. Köster 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.

432. Van Laarhoven P., Aarts E. Simulated Annealing: Theory and Applications. Dordrecht: Kluwer. 1988. 187 p.

433. Ladänyi L. Parallel Branch and Cut and Its Application to the Traveling Salesman Problem, Ph.D. Dissertation, Field of Operations Research, Cornell University, 1996.

434. Ladänyi L., Ralphs Т.К., and Trotter L.E. Branch, cut, and price: Sequential and parallel // Computational Combinatorial Optimization / D. Naddef, M. Jünger (eds.). Berlin: Springer, 2001. P. 223-260.

435. Lapoire D. Treewidth and Duality for Planar Hypergraphs. Manuscript. URL: http://www.labri.fr/perso/lapoire/papers/dual planar treewidth.ps (дата обращения 23.08.2010).

436. Larranaga P., Kuijpers C. M., Poza M., and Murga R. H. Decomposing Bayesian networks: triangulation of the moral graph with genetic algorithms // Statistics and Computing. 1997. V. 7. P. 19-34.

437. Larimore S. I. An approximate minimum degree column ordering algorithm, MS Thesis, Dept. of Computer and Information Science and Engineering, University of Florida, Gainesville, FL, 1998.

438. Lasdon L. S., Teijung R. C. An efficient algorithm for multi-item scheduling //Operations Research. 1971. V. 19. P. 998-1022.

439. Lauritzen S. J., Spiegelhalter D. J. Local computations with probabilities on graphical structures and their application to expert systems // The Journal of the Royal Statistical Society. Series B. 1988. V. 50. P. 157-224.

440. Lawler E. L. Fast approximation algorithms for knapsack problems // Mathematics of Operations Research. 1979. V. 4. P. 339-356.

441. Lekkerkerker C. G., Boland J. C. Representation of a finite graph by a set of intervals on the real line // Fund. Math. 1962. V. 51. P. 45-64.

442. Lewis J. G., Peyton B. W., Pothen A. A fast algorithm for reordering sparse matrices for parallel factorization // SIAM J. Sci. Stat. Comput. 1989. V. 10. P. 1146-1173.

443. Linderoth J. T., Ralphs T. K. Noncommercial software for mixed-integer linear programming // Integer Programming: Theory and Practice / J. Karlof (ed). CRC Press Operations Research Series, 2005. P. 253-303.

444. Linderoth J. T. Topics in Parallel Integer Optimization. Ph.D. Dissertation. Georgia Institute of Technology School of Industrial and Systems Engineering, 1998.

445. Lipton R. J., Rose D. J., Taijan R. E. Generalized nested dissection // SIAM J. Numer. Anal. 1979. V. 16. P. 346-358.

446. Liu J. W. H. Modification of the minimum-degree algorithm by multiple elimination // ACM Transactions on Mathematical Software. 1985. V. 11. P. 141-153.

447. Liu J.W.H. Computational models and task scheduling for parallel sparse Cholesky factorization // Parallel Comput. 1986. V. 3. P. 327-342.

448. Liu J. W. H. The minimum degree ordering with constraints // SIAM J. Sei. Stat. Comput. 1989. V. 10. P. 1136-1145.

449. Liu J. W. H. The role of elimination trees in sparse factorization // SIAM Journal on Matrix Analysis and Applications. 1990. V. 11. P. 134-172

450. Liu J. W. H. The multifrontal method for sparse matrix solution: Theory and practice // SIAM Review. 1992. V. 34. P. 82-109.

451. Liu J. W. H., Ng E. G., and Peyton B. W. On finding supernodes for sparse matrix computations // SIAM Journal on Matrix Analysis and Applications. 1993. V. 14. P. 242-252.

452. Mechanisms for high throughput computing / M. Livny et al. // SPEEDUP. 1997. V.ll. URL: http://www.cs.wisc.edu/condor/doc/htcmech.ps (дата обращения 23.08.2010).

453. Löbel A. Optimal Vehicle Scheduling in Public Transit. PhD thesis. Berlin: Technische Universität Berlin, 1997.

454. Lomonosov M. V. Combinatorial approaches to multiflow problems // Discrete Applied Mathematics. 1985. V. 11. P. 1-94.

455. Loväsz L. Graph theory and integer programming // Annals of Discrete Mathematics. 1979. V. 4. P. 146-158.

456. Lucena B. A new lower bound for tree-width using maximum cardinality search // SIAM J. Discret. Math. 2003. V. 16. P. 345-353.

457. Maffioli F. Complexity of combinatorial optimization algorithms and the challenge of heuristics // Combinatorial Optimization / N. Christofides, A. Mingozzi, P. Toth, C. Sandi (eds.). Chichester, New York, Brisbane, Toronto: Wiley. 1979. P. 107-130.

458. Magnati T. L., Wong R. T. Accelerating Benders decomposition: algorithmic enhancement and model selection criteria // Operations Research. 1981. V. 29, N 3. P. 464-484.

459. Mancini E. P., Marcarelli S., Vasilyev I., Villano U. A grid-aware MIP solver: Implementation and case studies //Future Generation Computer Systems. 2008. V. 24. P. 133-141.

460. Mandacovic T., Sounder W. E. An interactive decomposable heuristic for project selection // Management Science. 1986. V. 31, N 10. P. 1257-1271.

461. Markowitz H. M. The elimination form of the inverse and its application to linear programming // Management Science. 1957. V. 3, N 3. P. 255-269.

462. Martin R. K., Sweeney D. J. An ideal column algorithm for integer programs with special ordered sets of variables // Mathematical Programming. 1983. V. 26. P. 48-63.

463. Martelli A., Montanari U. Nonserial dynamic programming: on the optimal strategy of variable elimination for the rectangular lattice // Journal of Mathematical Analysis and Applications. 1972. V. 40. P. 226-242.

464. Martello S., Toth P. Worst-case analysis of greedy algorithms for the subset-sum problem//Mathematical Programming. 1984. V. 28. P. 198-205.

465. Martin A. Integer Programs with Block Structure. Habilitationsschrift. Berlin: Technische Universität, 1998. 217 p.

466. Martin A. General mixed integer programming: Computation issues for branch-and-cut algorithms // Computational Combinatorial Optimization / M. Jünger, D. Naddef (eds). Springer Verlag, 2001. P. 1-25.

467. Menger K. Zur allgemeinen Kurventheorie // Fund. Math. 1927. V. 10. P. 96115.

468. Merz P., Freisleben B. Fitness landscapes, memetic algorithms and greedy operators for graph bi-partitioning // Evolutionary Computation. 2000. V. 8. P. 197213.

469. Mitra G., Hai I., and Hajian M. T. A distributed processing algorithm forsolv-ing integer programs using a cluster of workstations // Parallel Computing. 1997. V. 23. P. 733-753.

470. Modern heuristic techniques for combinatorial problems / C. R. Reeves (ed.). London: McGraw-Hill. 1995. 320 p.

471. Nauss R. M. 0-1 knapsack problem with multiple choice constraints // European Journal of Operational Research. 1978. V. 2. P. 125-131.

472. Nemhauser G. L., Savelsbergh M. W. P., and Sigismondi G. S. MINTO, a Mixed INTeger Optimizer // Operations Research Letters. 1994. V. 15. P. 47-58.

473. Nemhauser G. L., Wolsey L. A. Integer and combinatorial programming. Chichester: John Wiley & Sons. 1988. 763 p.

474. Neumaier A. Complete Search in Continuous Global Optimization and Constraint Satisfaction // Acta Numerica / A. Iserles (ed.). Cambridge University Press. 2004. P. 271-369.

475. Neumaier A., Shcherbina O., Huyer W., Vinko T. A comparison of complete global optimization solvers // Math. Programming B. 2005. V. 103. P. 335-356.

476. Neumaier A., Shcherbina O. Safe bounds in linear and mixed-integer programming // Math. Programming A. 2004. V. 99. P. 283-296.

477. Neumaier A., Shcherbina O. Nonserial dynamic programming and local decomposition algorithms in discrete programming. URL: http://www.optimization-online.org/DB HTML/2006/03/1351 .html (дата обращения 23.08.2010).

478. Nowak I. Lagrangian decomposition of block-separable mixed-integer all-quadratic programs // Math. Programming. 2005. V. 102, N 2. P.295-312.

479. Osman I. H., Laporte G. Metaheuristics: A bibliography // Ann. Operat. Res. 1996. V. 63. P. 513-628.

480. Padberg M., Rinaldi G. A branch-and-cut algorithm for the resolution of large-scale traveling salesman problems // SIAM Review. 1991. V. 33. P. 60-100.

481. Papadimitrlou С. H. On the complexity of integer programming // Journal of the ACM. 1981. V. 28. P. 765-768.

482. Parker R. G., Rardin R. L. An overview of complexity theory in discrete optimization: Part 1. Concepts // HE Transactions. 1982. V. 14. P. 3-10.

483. Parker R. G., Rardin R. L. An overview of complexity in discrete optimization: part II. Results and implications // HE Transactions. 1982. V. 14. P. 83-89.

484. Parter S. The use of linear graphs in Gauss elimination // SIAM Review. 1961. V. 3.P. 119-130.

485. PARTY partitioning library.

486. URL: http://www2.cs.uni-paderborn.de/cs/robsy/party.html (дата обращения 23.08.2010).

487. PaToH Partitioning Tools for Hypergraph.

488. URL: http://bmi.osu.edu/~umit/software.html#patoh (дата обращения 23.08.2010).

489. Pellegrini F., Roman J. Sparse matrix ordering with SCOTCH // Proceedings of HPCN'97, Vienna, LNCS 1225, 1997. P. 370-378.

490. Pellegrini F., Roman J., Amestoy P. Hybridizing nested dissection and halo approximate minimum degree for efficient sparse matrix ordering // Proceedings of Ir-regular'99, San Juan, LNCS 1586, 1999. P. 986-995.

491. Pippenger N., Fischer M.J. Relations among complexity measures // Journal ACM. 1979. V. 26. P. 361-381.

492. Pothen A., Simon H., Liou K. Partitioning sparse matrices with eigenvectors of graphs // SIAM J. on Matrix Analysis and Applications. 1990. V. 11. P. 430-452.

493. Pothen A., Sun C. A mapping algorithm for parallel sparse Cholesky factorization//SISC. 1993. V. 14. P. 1253-1257.

494. Prasanna G. N., Musicus B. R. Generalized multiprocessor scheduling and applications to matrix computations // IEEE Trans. Parallel Distrib. Syst. 1996. V. 7. P. 650-664.

495. Preparata F.P. Computational complexity // MAA Studies in Mathematics. 1982. V. 22. P. 196-228.

496. Pritsker A.A.B., Waters L.J., Wolfe P.M. Multiproject scheduling with limited resources: A zero-one programming approach // Management Science. 1969. V. 16. P. 93-108.

497. PVM: Parallel Virtual Machine, 2004. URL: http://www.csm.ornl.gov/pvm/pvm home.html (дата обращения 23.08.2010).

498. QuickBB URL: http://www.ics.uci.edu/~vgogate (дата обращения 23.08.2010).

499. Quinn M. J., Deo N. An upper bound for the speedup of parallel best branch-and-bound algorithm // BIT. 1986. V. 26, N 1. P. 35-43.

500. Ralphs Т. K. Parallel Branch and Cut for Vehicle Routing. Ph.D. Dissertation. Cornell University, Field of Operations Research, 1995.

501. Ralphs Т. K., Ladänyi L. COIN/BCP User's Guide, 2001.

502. URL: http://www.coin-or.org (дата обращения 23.08.2010).

503. Ralphs Т. К., Ladanyi L., Salzman M. J. Parallel branch, cut, and price for large-scale discrete optimization // Mathematical Programming. 2003. B98. P. 253280.

504. Ralphs Т. K., Ladanyi L., Saltzman M. J. A library hierarchy for implementing scalable parallel search algorithms // Journal of Supercomputing. 2004. V. 28 (2). P. 215-234.

505. Ralphs Т. K., Galati M. Decomposition in Integer Programming // Integer Programming: Theory and Practice / J. Karlof, ed. 2005. P. 57.

506. Ralphs Т. K. Parallel Branch and Cut // Parallel Combinatorial Optimization /Е. Talbi, ed. 2006. P. 53-101.

507. Rendl F., Wolkowicz H. A projection technique for partitioning the nodes of a graph // Annals of Operations Research. 1995. V. 58. P. 155-179.

508. Richard J.-Ph. P., Dey S. S. The Group-Theoretic Approach in Mixed Integer Programming // 421. P. 727-801.

509. Robertson N., Seymour P. Graph minors II. Algorithmic aspects of treewidth // J. Algorithms. 1986. V. 7. P. 309-322.

510. Röhrig H. Tree Decomposition: A Feasibility Study. Master's Thesis. Saarbrücken: Max-Planck-Institut für Informatik, 1998.

511. Rose D. J. A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations // Graph Theary and Computing / R.C. Read (ed.). New York: Academic Press, 1972. P. 183-217.

512. Rose D. J. On simple characterizations of A>trees // Disc. Math. 1974. V. 7. P. 317-322.

513. Rose D., Tarjan R.E., Lueker G. Algorithmic aspects of vertex elimination on graphs // SIAM J. Comput. 1976. V. 5. P. 266-283.

514. Rosenthal A. Nonserial dynamic programming is optimal for nonserial optimization problems // SIAM J. Comput. 1982. V. 11, N 1. P. 47-59.

515. Rothberg E. Robust ordering of sparse matrices: A minimum degree, nested dissection hybrid. Sylicon Graphics, Manuscript, 1995.

516. Roucairol C. Parallel processing for difficult combinatorial optimization problems // European Journal of Operational Research. 1996. V. 92. P. 573 590.

517. Samphaiboon N., Yamada T. Heuristic and exact algorithms for the precedence-constrained knapsack problem // Journal of Optimization Theory and Applications. 2000. V. 105, N 3. P. 659-676.

518. Sannomiya N., Okamoto K. A method for decomposing mixed-integer linear programs with staircase structure // Int. J. Syst. Sci. 1985. V. 16, N 1. P. 99-111.

519. Sannomiya N., Tsukabe M. A decomposition method for mixed-integer linear programming problems with angular structure // Memoirs of the Faculty of Engineering. Kyoto University. 1980. V. 42. P. 391-403.

520. Sannomiya N., Tsukabe M. A method for decomposition mixed-integer linear programming problems with angular structure // International Journal of Systems Science. 1981. V. 12. P. 1031-1044.

521. Sarkar V. Partitioning and Scheduling Programs for Multiprocessors. Technical Report CSL-TR-87-328. Ph.D Thesis. Computer Systems Lab., Stanford University, April 1987.

522. Scheffler P. Linear-Time Algorithms for NP-Complete Problems Restricted to Partial /c-Trees. Report R-MATH 03/87, Prepr. Akad. der Wissenschaften der DDR: Karl Weierstrass Institut fur Mathematik, 1987.

523. Schrage L. Using decomposition in integer programming // Naval Research Logistics Quarterly. 1973. V. 20, N 3. P. 469-476.

524. Schroter N. Average-case analysis of an approximative algorithm for the knapsack problem // G. Hammer, D. Pallaschke (eds.): Methods of Operations Research. Konigstein. 1984. V. 52. P. 455-468.

525. Shannon C. E. The zero error capacity of a noisy channel // IEEE Trans. Inform. Theory, 1956. V. 2, P. S8-S19.

526. Shanthikumar J. S., Wu Yih-Bor. Decomposition approaches in permutation sheduling problems with application to the m-machine flow shop sheduling problems // European Journal of Operational Research. 1985. V. 19, N 1. P. 125-141.

527. Shapiro J. F. Dynamic programming algorithms for the integer programming problem I: The integer programming problem viewed as a knapsack type problem // Opns. Res. 1968. Vol. 16. P. 103-121.

528. Shapiro J. F. Group theoretic algorithms for the integer programming problem ii: extension to a general algorithm // Opns. Res. 1968. Vol. 16. P. 928-947.

529. Shapiro J. F. Survey of lagrangian techniques for discrete optimization // Discrete Optimization II. Annals of Discrete Mathematics / P. L. Hammer, E. L. Johnson, B. H. Korte (eds.). Amsterdam, New York, Oxford: North Holland. 1979. P. 113-138.

530. Shcherbina O. A. 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.

531. Shcherbina О. 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.

532. E. Hassanien, P. Siarry, A. Engelbrecht (eds.). Springer Berlin / Heidelberg. 2009. P. 235-266.

533. Shcherbina O. Tree decomposition and postoptimality analysis in discrete optimization // arXiv:0903.4435vl cs.DM. (2009).

534. Shibata Y. On the tree representation of chordal graphs // J. Graph Theory. 1988. V. 12. P. 421-428.

535. Shinano Y., Fujie T. ParaLEX: A parallel extension for the CPLEX mixed integer optimizer // Recent Advances in Parallel Virtual Machine and Message Passing Interface / F. Cappello, T. Herault, J. Dongarra, eds. Springer, 2007. P. 97—106.

536. Shinano Y., Harada K., Hirabayashi R. A generalized utility for parallel branch and bound algorithms // Proceedings of the 1995 Seventh Symposium on Parallel and Distributed Processing.IEEE Computer Society Press, Los Alamitos, 1995. P. 392-^01.

537. Shinano Y., Higaki M., Hirabayashi R. Control schemas in a generalized utility for parallel branch and bound // Proc. of the 1997 Eleventh International Parallel Processing Symposium. Los Alamitos: IEEE Computer Society Press, 1997.

538. Shoikhet K., Geiger D. A practical algorithm for finding optimal triangulation //Proceedings of AAAI, 1997. P. 185-190.

539. Smale S. On the average number of steps of the simplex method of linear programming // Math. Prog. 1983. V.27. P. 241-262.

540. Snir, M., Otto, S., Huss-Lederman, S., Walker, D., and Dongarra, J. MPI: The Complete Reference. MIT Press, Inc., second edition, 1998.

541. Soumis F. Decomposition and column generation // 318., chapter 8. P. 115126.

542. SPOOLES 2.2: SParse Object Oriented Linear Equations Solver URL: http://www.netlib.Org/linalg/spooles/spooles.2.2.html (дата обращения 23.08.2010).

543. Stougie L., van der Vlerk M. H. (1997). Stochastic integer programming //318., chapter 9. P. 127-141.

544. Sulistio A. Advance Reservation and Revenue-based Resource Management for Grid Systems, Ph.D. Thesis, The University of Melbourne, Australia, 2008.

545. Supply Chain Optimisation: Product/Process Design, facilities location and flow control. Series: Applied Optimization, XVI / A. Dolgui, J. Soldek, O. Zaikin (eds.). Springer, 2005. V. 94. 289 p.

546. Sweeney D., Murphy R. A method of decomposition for integer programs // Operations Research. 1979. V. 27, N 6. P. 1128-1141.

547. Sweeney D. J., Murphy R. A. Branch and bound methods for multi-item scheduling // Operations Research. 1981. V. 29. P. 853-864.

548. Syslo M. M., Deo N., Kowalik J.S. Discrete Optimization Algorithms with Pascal Programs. Englewood Cliffs: Prentice-Hall, 1983. 542 p.

549. Talbi El-G. (Ed.) Parallel Combinatorial Optimization. John Wiley & Sons, 2006.

550. Tarjan R.E. Complexity of combinatorial algorithms // SIAM Review. 1978. V. 20. P. 457-492.

551. TarYan84. Taijan R. E., Yannakakis M. Simple linear-time algorithms to test chordality of graphs, test acyclity of hypergraphs, and selectively reduce acyclic hy-pergraphs // SIAM J. Comput. 1984. V. 13. P. 566-579.

552. Taijan R. E. Depth first search and linear graph algorithms // SIAM J. Comput. 1972. V. l.P. 146-160.

553. Tawarmalani M., Sahinidis N. V. Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer Academic Publishers. 2002. 475 p.

554. Tinney W. F., Walker J. W. Direct solutions of sparse network equations by optimally ordered triangular factorization // J. Proc. IEEE. 1967. V. 55. P. 18011809.

555. ToolBar URL: http://carlit.toulouse.inra.fr/cgi-bin/awki.cgi/ToolBarIntro (дата обращения 23.08.2010).

556. TreeD Library URL: http://www.itu.dk/people/sathi/treed/ (дата обращения 23.08.2010).

557. Treewidthlib URL: http://www.cs.uu.nl/~hansb/treewidthlib/index.php (дата обращения 23.08.2010).

558. Trienekens H. W. J. M., de Bruin A. Towards a Taxonomy of Parallel Branch and Bound Algorithms. Report EUR-CS-92-01, Department of Computer Science, Erasmus University Rotterdam, 1992.

559. Trigt C. Worst-case analysis of algorithms. Some g.c.d. algorithms // Philips Journal of Research. 1978. V. 33. P. 66-77.

560. Troya J. M., Ortega M. A study of parallel branch-and-bound algorithms with best-bound-first search//Parallel Computing. 1989. V. 11. P. 121-126.

561. Tschoke S., Polzer T. Portable parallel branch-and-bound library PPBBLib user manual. Department of computer science, Univ. of Paderborn, 1996.

562. Tschoke S., Polzer T. Portable parallel branch and bound library. URL: http://www2.cs.uni-paderborn.de/cs/ag-monien/SOFTWARE/PPBB/ppbblib.html (дата обращения 23.08.2010).

563. Ullman J. Principles of Database and Knowledge-Base Systems, 2 Volumes. New York: Computer Science Press, 1988/89. 1137 p.

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

565. Vanroy T.J. Cross decomposition for mixed integer programming // Mathematical Programming. 1983. V. 25. P. 46-63.

566. Villanger Y. Efficient Minimal Triangulation of Graphs by Using Tree Decomposition. PhD Thesis. Univ. of Bergen, 2002.

567. Walter J. R. Representations of chordal graphs as subtrees of a tree // J. Graph Theory. 1978. V. 2. P. 265-267.

568. Wedelin D. An algorithm for large scale 0-1 integer optimization with application to airline crew scheduling. // Annals of Operations Research. 1995. V. 57. P. 283-301.

569. Weigel R., Faltings B. Compiling constraint satisfaction problems // Artificial Intelligence. 1999. V. 115, N 2. P. 257-287.

570. Welsh D. J. A. Problems in computational complexity //Applications of Combinatorics / R. J. Wilson (ed.). Nantwich: Shiva, 1982. P. 75-86.

571. Wets R .J. B. Programming under uncertainty: The equivalent convex program // SIAM J. Appl. Math. 1966. V. 14. P. 89-105.

572. Wilde D., Beightler C. Foundations of Optimization. Prentice-Hall, Eng-lewood Cliffs, 1967.

573. Williams H. P. Model Building in Mathematical Programming (Third edition). New York: Wiley, 1991. 356 p.

574. Wimer T. V. Linear Algorithms on K-Terminal Graphs. Doctoral Thesis. UMI Order Number: AAI8803914. Clemson University, 1987.

575. Woeginger G. J. Exact algorithms for NP-hard problems: A survey // "Combinatorial Optimization Eureka! You shrink!" / M. Juenger, G. Reinelt and G. Rinaldi (eds.). LNCS 2570. Springer. 2003. P. 185-207.

576. Wolle T. Computational Aspects of Treewidth, Lower Bounds and Networks Reliability. Dissertation: UU Universiteit Utrecht, 2005.

577. Wolle T., Koster A. M. C. A., and Bodlaender H. L. A Note on Contraction Degeneracy. Techn. Report UU-CS -2004-042, Utrecht: Utrecht Univ., Inst, of Inform. and Comput. Sci., 2004.

578. Wolsey L. A. Extensions of the group theoretic approach in integer programming // Management Science. 1971. Vol. 18. P. 74-83.

579. Wolsey L. A. A number theoretic reformulation and decomposition method for integer programming // Discrete Programming. 1974. V.7, N 3. P. 393-403.

580. Wright S. J. Solving optimization problems on computational grids // Optima. 2001. V. 65. P. 8-13.

581. Xu Y., Ralphs T. K., Ladányi L., and Saltzman M. J. Computational experience with a software framework for parallel integer programming // The INFORMS Journal on Computing. 2009. V. 21. P. 383-397.

582. Yagiura M., Ibaraki T. On metaheuristic algorithms for combinatorial optimization problems // Systems and Computers in Japan. 2001. V. 32. P. 33-55.

583. Yannakakis M. Computing the minimum fill-in is NP-complete //SIAM J. Alg. Disc. Meth. 1981. V. 2. P.77-79.

584. Yannakakis M. Graph-theoretic methods in database theory // Proc. 9th ACM PODS. 1990. P. 230-242.

585. Zoltners A. A., Sinha P. Integer programming models for sales resource allocation //Management Science. 1980. V. 26. P. 242-260.