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

КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

ОБЩИЕ СВЕДЕНИЯ

Номер проекта 23-21-00356

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

Руководитель Соколинский Леонид Борисович, Доктор физико-математических наук

Организация финансирования, регион Федеральное государственное автономное образовательное учреждение высшего образования "Южно-Уральский государственный университет (национальный исследовательский университет)" , Челябинская обл

Конкурс №78 - Конкурс 2022 года «Проведение фундаментальных научных исследований и поисковых научных исследований малыми отдельными научными группами»

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-201 - Искусственный интеллект и принятие решений

Ключевые слова линейное программирование; n-мерная визуализация; параллельный алгоритм; глубокое обучение; синтез обучающих данных; апекс-метод

Код ГРНТИ27.41.00

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

Аннотация
Задача линейного программирования (ЛП) является одной из самых важных и распространенных математических моделей для решения оптимизационных задач, возникающих в индустрии, экономике и других областях. Во многих случаях эти задачи являются нестационарными в том смысле, что их исходные данные быстро меняются во времени. Применение традиционных методов ЛП для решения таких задач зачастую оказывается неэффективным. Возможные пути решения этой проблемы - применение высокопроизводительных вычислений в совокупности с нейросетевыми технологиями. Основная идея предлагаемого подхода заключается в разработке математической модели визуального представления задачи ЛП, которая позволит использовать глубокую нейронную сеть прямого распространения для нахождения максимума линейной целевой функции. Предполагается, что допустимая область М задачи ЛП является непустым ограниченным множеством. Это означает, что M представляет собой выпуклый замкнутый многогранник в пространстве R^n. Преимущество использования нейронных сетей прямого распространения для решения нестационарных задач ЛП заключается в том, что время их работы зависит исключительно от размера входных данных и не зависит от их структуры (сложности). Общая схема решения задачи ЛП в этом случае выглядит следующим образом. Исходные данные задачи ЛП подаются на суперкомпьютер, который строит ее многомерный визуальный образ. Этот образ подается на вход нейронной сети, которая определяет оптимальный путь движения к точке максимума целевой функции по поверхности многогранника М. Научная новизна предлагаемого подхода состоит в том, что до сих пор не исследована возможность эффективного применения глубоких сетей прямого распространения к решению задач ЛП. Также в научной литературе отсутствуют работы по математическим моделям визуализации многомерных задач ЛП.

ОТЧЁТНЫЕ МАТЕРИАЛЫ

Публикации

1. Соколинский Л.Б., Соколинская И.М. Apex Method: A New Scalable Iterative Method for Linear Programming Mathematics, Vol. 11, no. 7. Article number 1654. (год публикации - 2023)
10.3390/math11071654

2. Соколинский Л.Б., Соколинская И.М. О новой версии апекс-метода для решения задач линейного программирования Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика, Т. 12, № 2. С. 5–46. (год публикации - 2023)
10.14529/cmse230201

3. Ольховский Н.А., Соколинский Л.Б. О новом методе линейного программирования Вычислительные методы и программирование, Т. 24, № 4. С. 408-429 (год публикации - 2023)
10.26089/NumMet.v24r428

4. Ольховский Н.А. Исследование нейросетевого метода решения задач линейного программирования Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика, Т. 12, № 4. С. 55-75 (год публикации - 2023)
10.14529/cmse230402

5. Ольховский Н.А., Соколинский Л.Б. AlFaMove: Scalable Implementation of Surface Movement Method for Cluster Computing Systems Supercomputing Frontiers and Innovations, Vol. 11, No. 3. P. 4-26. (год публикации - 2024)
10.14529/jsfi240301

6. Ольховский Н.А., Соколинский Л.Б. Surface Movement Method for Linear Programming Lobachevskii Journal of Mathematics, Vol. 45, No. 10. P. 5061-5079. (год публикации - 2024)
10.1134/S199508022460574545

7. Ольховский Н.А. О применении нейронных сетей прямого распространения в линейном программировании Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика, Т. 14, № 1 (год публикации - 2025)

Аннотация результатов, полученных в 2024 году
Впервые в мире разработана нейросетевая ансамблевая модель на основе нейронных сетей прямого распространения, позволяющая решать задачи линейной оптимизации в пространствах больших размерностей в режимах, близких к реальному времени. По сравнению с рекуррентными нейронными сетями с архитектурой Хопфилда, новая нейросетевая ансамблевая модель позволяет решить эталонные задачи линейного программирования в 10 раз быстрее. В основе предложенного подхода лежит новый алгоритм поверхностного движения AlFaMove, вычисляющий оптимальный путь на поверхности многогранника допустимых решений к оптимуму целевой функции. Для нахождения решения задачи на основе куба Кле-Минти алгоритму AlFaMove в пространстве размерности n требуется n итераций в то время, как классический симплекс-метод выполняет 2^n итераций. Разработанные методы, алгоритмы и подходы реализованы в виде программного комплекса, ориентированного на кластерные вычислительные системы. Информационный ресурс в сети Интернет, посвященный проекту: https://life.susu.ru.

Публикации