Исследование полиэдральных характеристик задач комбинаторной оптимизации

В докладе рассматриваются полиэдральные структуры, возникающие из моделей линейного и целочисленного программирования для задач комбинаторной оптимизации. Во-первых, это многогранники, которые получаются при релаксации линейного программирования, т.е. снятии ограничения целочисленности переменных в модели. Исследование структуры и свойств дробных вершин и нецелочисленных граней релаксационных многогранников помогает при анализе сложности задач и разработке новых эффективных алгоритмов их решения. Во-вторых, это полиэдральные графы многогранников задач, вершинами которых являются вершины многогранников, а рёбрами – геометрические рёбра или одномерные грани. Критерии смежности вершин могут быть непосредственно применены в симплекс-подобных алгоритмах комбинаторной оптимизации, которые переходят от одного допустимого решения к другому по рёбрам полиэдрального графа. А такие характеристики полиэдрального графа задачи как диаметр и кликовое число служат оценками сложности для различных моделей вычислений и классов алгоритмов.