О комбинаторных задачах векторной оптимизации

Исследуется класс комбинаторных задач оптимизации с несколькими критериями вида MINMAX и MINSUM в произвольном сочетании. Класс задач векторной оптимизации формулируется в терминах систем подмножеств и включает задачи на графах и задачи булевого программирования. Показано, что проблема поиска полного множества альтернатив в таких задачах может быть экспоненциально сложной (труднорешаемой). Получены новые результаты, связанные с существованием статистически эффективных алгоритмов решения указанных задач, а для двух критериев (в случае, когда хотя бы один из них MINMAX) предложены полиномиальные алгоритмы нахождения полного множества альтернатив в задачах о цепях, паросочетаниях и остовных деревьях, а также в целочисленной транспортной задаче.
Эти исследования частично финансировались фондом фундаментальных исследований Республики Беларусь.