Численные методы решения оптимизационных задач презентация

программирование
Эффективная реализация МНП на современных архитектурах

- безусловная оптимизация
- дискретная оптимизация
математическое программирование
Линейное программирование
Нелинейное программирование
частично-целочисленное программирование (оптимизация)

решения)
Детерминированные методы (гарантируют оптимальность с заданной точностью)

Оптимум

Приближенное решение

задачи)
поиск конфигурации молекул с минимальной энергией взаимодействия
докинг протеинов
оптимизация размещения элементов микросхем и их верификация

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

метод поиска глобального экстремума функций (перебор на неравномерной сетке)”, Ж. вычисл. матем. и матем. физ., 11:6 (1971), 1390–1403
Расширен на случай многих критериев в 1986 Евтушенко Ю. Г., Потапов М. А. «Методы численного решения многокритериальных задач.» ДАН СССР, Т. 291, N 1, 1986, С. 25-39.
Расширен на задачи математического программирования в 1992 Yu. G. Evtushenko, M. A. Potapov, V. V. Korotkikh. Numerical methods for global optimization. In "Recent advances in global optimization”, Princeton University Press, pp. 274-297. 1992.
Первая параллельная реализация 2007 Ю. Г. Евтушенко, В. У. Малкова, А. А. Станевичюс. Распараллеливание процесса поиска глобального экстремума. Автоматика и телемеханика, № 5. С. 46-58, 2007.

Новая техника для задач математического программирования 2011 Ю. Г. Евтушенко, М. А. Посыпкин. Варианты метода неравномерных покрытий для глобальной оптимизации частично-целочисленных нелинейных задач. Доклады Академии наук. Т: 437. № 2. С. 168–172.

найти -оптимальное решение

то

- совокупность допустимых точек

точке .

в точке

Этот шар может быть исключен из дальнейшего рассмотрения.

и может существенно ускорить процесс нахождения минимума

-решение

миноранта для j-го ограничения на множестве :

то множество

можно отбросить как не содержащее допустимых точек.

то

- совокупность -допустимых точек

ограничений g1-g4.

РАНЕЕ НАЙДЕННОГО (РЕКОРДА)

до начала решения задачи и формируется динамически;

ГРАФ АЛГОРИТМА

вычислений

ПРОБЛЕМНО-ЗАВИСИМЫЕ

Способ ветвления
Правила отсева

памятью

архитектуры

методы

МВГ для
ранца

МВГ для коммивояжера

МВГ для непрерывной оптимизации

КАРКАСЫ

ПАМЯТИ

КАРКАС
ДЛЯ РАСПРЕДЕЛЕННОЙ ПАМЯТИ

МЕТОД НЕРАВНОМЕРНЫХ ПОКРЫТИЙ

МВГ
ДЛЯ РАНЦА

КАРКАС
ДЛЯ ПОСЛЕД. АРХИТЕКТУР

МВГ ДЛЯ ЗАДАЧИ КОММИВОЯЖЕРА

Солвер НЛП для общей памяти

СОЛВЕРЫ

ПОДСИСТЕМА УПРАВЛЕНИЯ ПАМЯТЬЮ

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

(не более) Ts вершин.
РП процесс, завершивший обработку назначенной вершины, посылает запрос УП. В ответ УП посылает рабочему процессу одну вершину. РП получает ее и начинает выполнять итерации МНП.
Если на УП скапливается более Um вершин, УП посылает сообщение всем РП чтобы они прекратили посылку вершин.
Если на УП меньше Lm вершин, то УП посылает сообщение всем РП, чтобы они возобновили посылку вершин.

УП

РП

РП

РП

РП

УП – управляющий процесс, РП – рабочий процесс;
Tb – пороговое значение числа ветвлений на рабочем процессе;
Ts – пороговое значение числа пересылаемых вершин на управляющий процесс;
Um(Lm) – максимальное (минимальное) число вершин на управляющем процессе

память + общая память + GPU)
Реализация в распределенной среде (BOINC-проекты: OPTIMA@home)