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