Релаксационные многогранники труднорешаемых задач

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


грант Президента РФ для молодых кандидатов наук
Руководитель проекта: Николаев Андрей Валерьевич
Период выполнения проекта: 27.02.2015 - 27.02.2016
Одной из основных парадигм при разработке алгоритмов для труднорешаемых задач является релаксация линейного программирования: задача сводится к задаче целочисленного программирования на многограннике, который возникает при снятии ограничения целочисленности с переменных, фигурирующих в задаче.
Объектом исследования в рамках проекта выступали метрический многогранник MET(n), который является релаксацией многогранника CUT(n) задачи о разрезе в графе, а также многогранник SATP(m,n) и его релаксация SATP_LP(m,n).

Рассматриваемый многогранник SATP(m,n) представляет особый интерес для изучения, так как различные постановки задачи 3-выполнимость, в том числе максимальная 3-выполнимость, 3-выполнимость при различных литералах и 3-выполнимость при одном истинном литерале, сводятся к задаче целочисленного программирования или распознавания целочисленности на SATP(m,n). Задача распознавания целочисленности отвечает на вопрос: верно ли, что максимум линейной целевой функции достигается в целой вершине многогранника.

В качестве основного результата описан полиномиальный алгоритм решения задачи распознавания целочисленности на многограннике SATP_LP(m,n) для целевых функций специального вида. Алгоритм основан на двойном применении линейного программирования и дополнительных O(mn(m+n)) шагах для восстановления искомой целой точки. С помощью сведения к задаче распознавания целочисленности на SATP_LP(m,n) построен полиномиальный алгоритм для частного случая задачи о раскраске двудольного графа с ограничениями по ребрам на комбинации цветов.

Метрический многогранник MET(n) определяется наиболее простыми гипергранями разрезного многогранника CUT(n) вида «неравенств треугольника». Известно, что он является плотной релаксацией разрезного многогранника: все вершины, ребра и двумерные грани, а также большинство d-мерных граней CUT(n) являются гранями MET(n).

Большое число работ посвящено исследованию нецелочисленных вершин метрического многогранника. Однако, полного описания множества нецелочисленных вершин до сих пор не построено. Наиболее подробно изученным является класс графических вершин метрического многогранника, порождаемых метрикой на графах.

В рамках проекта описаны новые классы графов, порождающих графические вершины метрического многогранника, и разработана научно-исследовательская программа для построения графических вершин метрического многогранника «GraphicVerticesMaker». Программа на основе метрики на графе находит координаты соответствующей точки метрического многогранника. Проверка является ли построенная точка вершиной осуществляется с помощью алгоритма ic-раскраски графа: ребра графа разбиваются на классы эквивалентности, если они являются противоположными в некотором изометрическом цикле. На выходе программа пошагово расписывает построение всех классов эквивалентности и выделяет их различными цветами на графе.




  • 30
    лет факультету
  • Более 2000
    выпускников
Подавать сертификаты ЕГЭ вместе с другими документами не нужно, ваши баллы будут проверяться в федеральной базе.