Неразрешимость задач векторной дискретной оптимизации в классе алгоритмов линейной свертки критериев

В терминах систем подмножеств описан достаточно широкий класс задач комбинаторной векторной оптимизации, которые неразрешимы с помощью классического приема линейной свертки критериев. В этот класс, в частности, попадают хорошо известные задачи на графах (коммивояжора, о цепях между двумя вершинами и совершенных паросочетаниях, о $p$-медиане и покрытии графа цепями), а также разнообразные задачи булева программирования с векторной целевой функцией, представляющей собой любую комбинацию критериев вида $\operatorname{\textmaxsum}$, $\operatorname{\textmaxmin}$, $\operatorname{\textmaxmax}$.
Работа частично финансировалась Фондом фундаментальных исследований Республики Беларусь.