Семинар Добрушинской математической лаборатории ИППИ РАН
7 ноября, вторник, 16:00, ауд. 615 (очно и без трансляции).
Николаев Андрей Валерьевич (ЯрГУ): Исследование полиэдральных
характеристик задач комбинаторной оптимизации
Аннотация.
В докладе рассматриваются полиэдральные структуры, возникающие из
моделей линейного и целочисленного программирования для задач
комбинаторной оптимизации. Во-первых, это многогранники, которые
получаются при релаксации линейного программирования, т.е. снятии
ограничения целочисленности переменных в модели. Исследование
структуры и свойств дробных вершин и нецелочисленных граней
релаксационных многогранников помогает при анализе сложности задач и
разработке новых эффективных алгоритмов их решения.
Во-вторых, это полиэдральные графы многогранников задач, вершинами
которых являются вершины многогранников, а рёбрами – геометрические
рёбра или одномерные грани. Критерии смежности вершин могут быть
непосредственно применены в симплекс-подобных алгоритмах комбинаторной
оптимизации, которые переходят от одного допустимого решения к другому
по рёбрам полиэдрального графа. А такие характеристики полиэдрального
графа задачи как диаметр и кликовое число служат оценками сложности
для различных моделей вычислений и классов алгоритмов.
| 02.11.2023 | Комеч Сергей Александрович |