Введение
1 Детерминированные методы решения задач глобальной оптимизации с одним критерием 19
1.1 Постановка задачи и обзор известных результатов 19
1.2 Случай множеств простой структуры 22
1.3 Поиск глобального минимума в задаче НЛП 26
1.4 Миноранты 30
1.5 Обработка подмножеств в алгоритмах COVER и COVERNLP . 33
1.6 Результаты вычислительных экспериментов 36
1.7 Основные результаты главы 41
2 Детерминированные методы решения задач многокритериальной оптимизации 43
2.1 Постановка задачи и обзор существующих результатов 43
2.2 Случай ограничений параллелепипедного типа 47
2.3 Решение задач многокритериальной оптимизации при наличии функциональных ограничений 66
2.4 Основные результаты главы 75
3 Эффективная оболочка невыпуклых множеств и метод ее аппроксимации 76
3.1 Эффективная граница и эффективная оболочка 76
3.2 Аппроксимация эффективной оболочки 81
3.3 Применение эффективной оболочки для описания рабочей области робота-манипулятора 87
3.4 Основные результаты главы 91
Оценки сложности метода ветвей и границ 92
4.1 Постановка задачи и обзор существующих результатов 92
4.2 Сложность метода бисекций 94
4.3 Общие сведения о сложности метода ветвей и границ для задачи о ранце 97
4.4 Асимптотическая оценка сложности наихудшего случая в методе ветвей и границ с ветвлением по дробной переменной для задачи о ранце 105
4.4.1 Нахождение дробной переменной 106
4.4.2 Рекуррентные соотношения для сложности метода ветвей и границ 107
4.5 Общие оценки сложности метода ветвей и границ для задачи о ранце 125
4.6 Верхняя оценка сложности мажоритарного алгоритма для задачио ранце 134
4.7 Основные результаты главы 151
Параллельная вычислительная сложность метода ветвей и границ 153
5.1 Постановка задачи и обзор существующих результатов 153
5.2 Фронтальный параллельный вариант реализации метода ветвей и границ 154
5.3 Проблемно-независимая оценка сложности фронтального алгоритма 156
5.4 Оценка параллельной сложности ярусного фронтального алгоритма для задачи о сумме подмножеств 158
5.5 Основные результаты главы 169
6 Программные комплекс для решения задач оптимизации на последовательных и параллельных вычислительных системах 170
6.1 Постановка задачи и обзор существующих результатов 170
6.2 Общие сведения об архитектурах современных параллельных и распределенных систем 176
6.2.1 Последовательные архитектуры 176
6.2.2 Многопроцессорные системы с общей памятью 176
6.2.3 Многопроцессорные системы с распределенной памятью . 177
6.3 Реализация метода ветвей и границ для многопроцессорных систем с распределенной памятью 178
6.3.1 Общие принципы реализации 178
6.3.2 Формализация описания управления процессом вычислений180
6.3.3 Основные компоненты библиотеки BNB-Solver и их взаимосвязь 186
6.4 Способы повышения эффективности параллельной реализации метода ветвей и границ на примере задачи о ранце 195
6.4.1 Использование специфики решаемой задачи для эффективной реализации ветвлений 195
6.4.2 Использование эвристик для ускорения поиска экстремума 200
6.5 Программный комплекс для решения задач оптимизации большой размерности в распределенной вычислительной среде . 208
6.5.1 Архитектура программного комплекса 208
6.5.2 Применение программного комплекса BNB-Grid для нахождения минимума энергии молекулярного кластера 213
6.6 Основные результаты главы 222
Заключение
