Полиэдральная комбинаторика

Руководитель группы В.А. Бондаренко, д.ф.-м.н.

В состав группы также входят:

Известно, что практически любую задачу комбинаторной оптимизации можно свести к задаче линейного программирования на соответствующем многограннике. Однако, как правило, такой многогранник имеет чрезмерно сложную структуру: экспоненциальное число фасет и экспоненциально большие коэффициенты в линейных ограничениях. Более того, для большинства многогранников задач полного описания так и не было построено. Альтернативным подходом является сведение комбинаторных оптимизационных задач к задаче целочисленного линейного программирования на так называемых релаксационных многогранниках. Отличие релаксационных многогранников от классических комбинаторных многогранников состоит в том, что для их внешнего описания требуется лишь полиномиальное число линейных неравенств. При этом релаксационные многогранники частично сохраняют как структуру исходного многогранника (целочисленные вершины), так и некоторые важные свойства его граничного комплекса (например, кликовое число графа многогранника). Основным объектом для изучения при этом становятся свойства и характеристики множества нецелочисленных вершин.

В рамках исследовательской группы планируется изучение иерархии релаксаций многогранника, ассоциированного с основными NP-полными задачами, среди которых можно выделить задачу о максимальном разрезе графа. Для нее релаксацией нижнего уровня является известный корневой полуметрический многогранник, который рассматривался в работах Бондаренко, Падберга, Деза, Лоран и др. Релаксации более высоких уровней, получаемые путем наложения дополнительных линейных ограничений, изучались Бондаренко, Николаевым и Урываевым. Основное внимание в рамках исследования направлено на
• отыскание дополнительных линейных ограничений при повышении уровня релаксации;
• описание нецелочисленных вершин релаксаций и их свойств;
• построение алгоритмов для задач целочисленного программирования и распознавания целочисленности на указанных многогранниках с полиномиальной временной трудоемкостью.

Более подробно ознакомиться с исследованиями по полиэдральной комбинаторике можно по приведенной ссылке.