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

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