Метод ветвей и отсечений для задачи разбиения на клики

Проводится численное исследование метода ветвей и отсечений, адаптированного для решения задачи разбиения на клики (CPP). Эта задача заключается в нахождении в полном рёберно-взвешенном графе семейства попарно не пересекающихся клик минимального общего веса. Рассматриваются два частных случая задачи CPP. Первый известен как задача агрегации бинарных отношений (ABRP), а второй — как задача аппроксимации графа (GAP). Для известного ранее класса фасетных неравенств многогранника задачи разработан алгоритм отсечения, включающий два новых основных элемента: поиск решения с заданной гарантированной точностью и процедуру локального поиска для решения задачи идентификации неравенств. Предложенный алгоритм отсечения используется для построения нижних оценок в методе ветвей и отсечений. Для поиска верхних оценок точного решения используются специальные эвристики. Проведён вычислительный эксперимент на случайно сгенерированных графах. Наш метод позволил найти оптимальное решение для ранее изученных экземпляров ABRP и новых задач большой размерности. Задача GAP оказалась более сложным в вычислительном отношении частным случаем задачи CPP. Кроме того, для нашего алгоритма выделены простые и сложные классы GAP. Табл. 5, рис. 1, библиогр. 32.