Одной из основных парадигм при разработке алгоритмов для труднорешаемых задач является релаксация линейного программирования: задача сводится к задаче целочисленного программирования на многограннике, который возникает при снятии ограничения целочисленности с переменных, фигурирующих в задаче.
Объектом исследования в рамках проекта выступали метрический многогранник 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-раскраски графа: ребра графа разбиваются на классы эквивалентности, если они являются противоположными в некотором изометрическом цикле. На выходе программа пошагово расписывает построение всех классов эквивалентности и выделяет их различными цветами на графе.