Комбинаторные свойства многогранников задач комбинаторной оптимизации

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