Модели и алгоритмы дискретной оптимизации для проектирования и управления сложными системами

Объект исследования – задачи дискретной оптимизации в области проектирования и управления сложными системами. Цель всего проекта и этапа 2023 г. состоит в развитии методов исследования и решения задач проектирования и управления сложными системами с использованием дискретной оптимизации: моделей и методов целочисленного программирования, эволюционных вычислений, динамического программирования, оптимизации на графах, локального поиска и машинного обучения. Используемые методы: модели и методы целочисленного программирования, эволюционных вычислений, динамического программирования и теории вероятностей. Важнейший результат за 2023 г.: Предложены алгоритмы приближенного решения NP-трудной задачи кластеризации на графах с кластерами размера, не превосходящего четырех. Доказаны гарантированные оценки точности этих алгоритмов. Кроме того, получены следующие результаты: Предложены полиномиальные алгоритмы поиска локальных экстремумов на ребрах сети с критерием максимизации суммы расстояний в метрике кратчайших путей и с критерием максимизации минимального расстояния до вершин сети в евклидовой метрике с учетом ограничения на суммарное взвешенное расстояние в метрике кратчайших путей от объекта до вершин. Для задачи составления расписаний на многоядерном процессоре с учетом взаимного замедления работ предложена модель частично целочисленного линейного программирования и жадный алгоритм приближенного решения, проведен вычислительный эксперимент, показавший перспективность разрабатываемого подхода. Для задачи проектирования линий механической обработки деталей предложен новый вариант параллельного эволюционного алгоритма для исполнения на графическом процессоре и экспериментально показано преимущество предложенной схемы по сравнению с алгоритмами из литературы. Для новой двухкритериальной постановки конкурентной задачи размещения и проектирования с гибким спросом предложены и экспериментально исследованы алгоритмы приближенного решения, основанные на локальном поиске с чередующимися окрестностями и модифицированной версии эволюционного алгоритма. Эти и другие полученные за год результаты являются новыми и соответствуют мировому уровню исследований.