Эвристики для идентификации 1-парашютов в задаче аппроксимации графа

УДК 519.852 DOI: 10.25513/2222-8772.2018.4.35-45

ЭВРИСТИКИ ДЛЯ ИДЕНТИФИКАЦИИ 1-ПАРАШЮТОВ В ЗАДАЧЕ АППРОКСИМАЦИИ ГРАФА

Омский государственный университет им. Ф.М. Достоевского, Омск, Россия

Аннотация. Задача аппроксимации графа заключается в нахождении в полном рёберно-взвешенном графе семейства попарно вершинно-непересекающихся клик минимального веса. В общем случае задача является NP-трудной. В работе (см. [1]) был предложен класс неравенств, опорных к многограннику данной задачи. Найдены условия, при которых построенные неравенства являются фасетными. При использовании этих неравенств в алгоритмах отсечений становится актульной задача идентификации (Separation problem). В работе (см. [2]) было показано, что задача идентификации предложенных неравенств NP-трудна. В настоящей работе для идентификации отсечений разработана процедура локального поиска. Для анализа эффективности предлагаемых методов проведён вычислительный эксперимент.

Работа выполнена при поддержке РФФИ

Ключевые слова: задача идентификации, полиэдр, фасета, аппроксимация графа.

Введение

Впервые задача аппроксимации графа была сформулирована Харари в 1955 году. В 60-70-х годах прошлого столетия в ряде работ были найдены нетривиальные классы графов, на которых задача является полиномиально разрешимой. В 1986 г. Криванек и Моравек рассмотрели задачу аппроксимации графа как частный случай задачи кластеризации деревьев и доказали, что она является ЖР-трудной. Систематическое изучение задачи аппроксимации графа началось в прошлом десятилетии, когда задача была переоткрыта под разными именами (Correlation clustering, Cluster editing) различными группами авторов. В частности была установлена ЖР-трудность различных её вариантов и для их решения предложены первые приближенные алгоритмы с гарантированной оценкой точности. Лучший из известных на сегодняшний день приближенный алгоритм для задачи аппроксимации графа гарантировано находит решение не более чем в 2.5 раза хуже оптимального.

Введём следующие обозначения и понятия. Для любого графа D с Кп через VD и ED будем обозначать множества его вершин и рёбер соответственно. Для

И.В. Уразова

к.ф.-м.н., доцент, e-mail: urazovainn@mail.ru

ребра е Е Е будем также использовать запись иь, где и и V — вершины из V, инцидентные ребру е. Для О С Кп и и Е V через 8в(и) обозначим множество рёбер графа И, инцидентных вершине и. Если О = Кп, то в этой записи индекс О будем опускать. Каждое множество рёбер К С Е индуцирует в Кп некоторый подграф Т, в котором ЕТ = Я и УТ — множество вершин, инцидентных рёбрам из Я. Там, где не возникает двусмысленности, граф, индуцированный множеством рёбер Я, будем обозначать через Я. Для подграфов В,Е и Кп положим

В и ^ = ЕВ и ЕЕ, В П ^ = ЕВ П ЕЕ.

Пусть Кга = (V, Е) — полный неориентированный граф без петель и кратных рёбер. Остовный подграф Н С Кга называется М-графом, если каждая его компонента связности является кликой или одновершинным графом. Множество всех М-графов в Кга обозначим через у(У).

Пусть С С Кга — некоторый априори заданный остовный подграф. Задача аппроксимации графа С заключается в нахождении М-графа Н, минимизирующего на множестве ^(У) функционал

рс(Н) = и Н| - П Н|.

Иными словами, требуется найти такое множество попарно непересекающихся клик на V, которое как можно меньше (в рёберном смысле) отличается от графа С.

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

Множество Р С ЯЕ называется многогранником, если оно является выпуклой оболочкой конечного числа точек. Линейное неравенство атх ^ а0 (а,х Е ЯЕ,а = 0,а0 Е Я, "Т" — знак транспонирования) называется правильным к многограннику Р, оно не нарушается ни одной из точек могогранника. Правильное неравенство называется опорным к многограннику Р, если оно выполняется для любой точки из Р и существует, по крайней мере, одна точка из Р, обращающая его в равенство. Всякое опорное к Р неравенство порождает множество {х Е Р^х = а0|, которое называется гранью многогранника Р. Максимальные по включению грани многогранника называются фасетами. Ясно, что фасетой является та и только та грань, размерность которой на 1 меньше размерности самого многогранника. Опорное неравенство, порождающее фасету, назовём, соответственно, фасетным.

Полиэдром в КЕ называется множество решений конечной системы линейных уравнений и неравенств с переменными хе, е Е Е, если оно ограничено. Согласно теореме Вейля-Минковского, для всякого многогранника существует совпадающий с ним в теоретико-множественном смысле полиэдр, и наоборот.

В [1,4] было показано, что (0,1)-вектор х Е ЯЕ является вектором инци-денций М-графа, если и только если он удовлетворяет системе

+ ^ит + ^'о'ш ^ 1 ^и'ш + ^ 1

где и,у,т Е V — всевозможные тройки попарно различных вершин,

хи,€ ^ 0, для всех иу Е Е.

Полиэдр, определяемый системой (3)-(4), обозначим через Мп. Таким образом, Рп с Мп, причём включение именно строгое (в [1] приведены примеры нецелочисленных вершин полиэдра Мп) и каждая целочисленная вершина Мп является вектором инциденций некоторого М-графа. Следуя работе [3], ограничения вида (3) будем называть треугольниками.

В [1] был введён и изучен новый класс опорных к Рп неравенств. Пусть и = {и1,и2,..., ик} и Ш = {у1,у2,..., ур] — непустые подмножества множества V, и П Ш = 0, к ^ 1, р ^ 2. Через = 1, 2,... ,к, обозначим звезду в Кп с центром в вершине щ и лучами и^у^= 1, 2,... ,р (см. рис. 1).

Рис. 1. Звезда в Кп с центром в вершине и^ и лучами щю^= 1,2, ...,р

к

Через Кр обозначим клику на множестве вершин Ш. Положим Т = и Тг.

г=1

Граф Т и Кр называется ^-парашютом (см. рис. 2). С этим графом свяжем неравенство

к2 + к

х(ЕТ) - х(ЕКр) ^ .

T

K

U

p

Рис. 2. ^-парашют

В [1] было доказано, что такое неравенство, индуцированное ^-парашютом Т и Кр, является опорным к многограннику Рп тогда и только тогда, когда р ^ к, а фасетным — тогда и только тогда, когда к = 1. В этой связи особый интерес для нас будут представлять именно 1-парашюты (см. рис. 3).

Kr

T

Рис. 3. 1-парашют

В [3,4] был предложен класс опорных неравенств (2-дольных), отличающихся от fc-парашютов тем, что на множестве U = {u\,u2,... ,uu} строится клика К2 (см. рис. 4). Класс 2-дольных неравенств состоит из неравенств вида

х(ЕТ) - х(ЕКр U ЕК2) ^ min(p, к).

Кроме того, нетрудно заметить, что пересечением класса 2-дольных неравенств и класса fc-парашютов является класс 1-парашютов.

Для заданного 1-парашюта Т U Кр вершину графа Кп, образующую множество U, будем иногда называть парашютистом, а клику Кр — куполом 1-парашюта.

При разработке процедур отсечения, использующих опорные неравенства как отсекающие плоскости, на передний план выходит задача идентификации (separation problem), которая заключается в следующем. Даны некоторый класс L неравенств, опорных к многограннику Р, и точка х Е RE. Требуется найти

Т

и

к

р

Рис. 4. 2-дольное неравенство

в классе Ь неравенство, строго отделяющее точку х от многогранника Р, либо доказать, что в Ь такого неравенства нет. В 1982 году в работах Кагр 1^.М. и РараШшИгш С.Н. было показано, что при МР = со — МР для полиэдра общего вида (не обязательно целочисленного) и класса неравенств, определяющих все фасеты выпуклой оболочки его целочисленных точек, не существует полиномиального алгоритма решения задачи идентификации. В связи с этим целесообразно рассматривать задачу идентификации применительно к конкретным классам неравенств относительно конкретных задач. Например, идентификация кликовых фасет для многогранника симметричной задачи коммивояжёра полиномиально разрешима, а идентификация гребневых неравенств и неравенств деревьев клик для той же задачи ЫР-трудна (см. также [2,7]).

Очевидно, что поскольку число попарно различных троек вершин в Кп полиномиально по п, задача идентификации треугольников полиномиально разрешима. В [3] для поиска 2-дольного неравенства, отсекающего заданную точку, использовалась эвристическая процедура, поскольку сложностной статус задачи идентификации 2-дольных неравенств на тот момент был неизвестен. В 2001 году была показана ЖР-трудность задачи идентификации для этого класса. Однако важно иметь в виду следующее. Поскольку многогранник Рп целиком лежит в единичном кубе пространства КЕ, то отсекаемую точку можно полагать лежащей в единичном кубе. Это несколько усиливает постановку задачи идентификации. Возможно ещё большее усиление. Поиск неравенства, отсекающего текущий нецелочисленный оптимум, начинается, как правило, с класса неравенств с полиномиально разрешимой задачей идентификации. Поэтому постановка задачи идентификации для класса 2-дольных неравенств может быть усилена до следующей: найдётся ли 2-дольное неравенство, отсекающее точку, удовлетворяющую всем треугольникам? В [2] дано новое строгое доказательство этого факта для класса 1-парашютов и, как следствие, 2-дольных неравенств и ^-парашютов.

1. Идентификация 1-парашютов

Сформулируем задачу идентификации 1-парашютов относительно многогранника М-графов. При заданной точке х е КЕ, 0 ^ х ^ 1, среди всех 1-парашютов Т и Кр графа Кп требуется найти такой, для которого 1>2 хе — ^2 хе > 1. Эта задача может быть формализована в виде задачи

е£ЕТ

е£ЕК„

целочисленного линейного программирования. Определим булевы переменные: хи е {0,1}, и е V, — выбор парашютиста; уи е {0,1}, и е V, — выбор вершин купола; ги,и е {0,1}, и,у е V, — выбор рёбер купола; Ьа-о е {0,1}, и,у е V, — выбор рёбер между парашютистом и куполом. Требуется максимизировать функцию

^

2

при условиях:

^и'О ^ Уи + Уо — 1, и,ь е V;

^и'О ^ У и, ^ Уо , и,ь е V;

^ Хи + Уа — 1, и,ь е V;

^ Хи, Ъиу ^ Уо , и,ь е V;

Хи + Уи ^ 1, и е V;

^ ^ Хи 1 )

иеУ

х^Уи^иъ,ьа,0 е {0,1},и,ь е V.

Ограничения (6), (7) определяют рёбра внутри купола и фактически гарантируют равенство ху/и = уиуи. Ограничения (8), (9) определяют рёбра между куполом и парашютистом и гарантируют равенство = хиуъ. Ограничения (10) запрещают пересечение парашютиста с куполом. Ограничение (11) требует выбора ровно одного парашютиста. Ограничение (12) гарантирует непустой купол. В действительности для решения задачи идентификации достаточно проверить на совместность систему, образованную ограничениями (6)-(13) и неравенством ^2 хи-юЬиъ — ^2 х-и-о> 1, что в целом не облегчает задачу.

и'о^У

и/и^У

Как уже говорилось, задачу идентификации целесообразно рассматривать применительно к конкретным классам неравенств относительно конкретных задач. При такой стратегии, помимо точных процедур решения, часто используются эвристики (см., например, [3]). Так как задача идентификации 1-парашютов ЫР-трудна, мы разработали эвристическую процедуру для её решения.

Итак, рассматривается следующая задача. Дана точка х е Мп \ Рп. В графе Кп нужно найти такой 1-парашют ТииКр, где Кр, р ^ 3, — клика на множестве

вершин {VI, ь2,... ,ур] и Ти — звезда с центром в вершине и Е {у1,у2, ... ,ур} и лучами иь^, ] = 1, 2,... ,р, что выполняется неравенство

х(ЕТи) — х(ЕКр) > 1.

Полагая величины хе весами рёбер е Е Е, а величину х(ЕТи) — х(ЕКр) — весом 1-парашюта Ти и Кр, мы можем сформулировать рассматриваемую задачу идентификации как задачу поиска в полном рёберно-взвешенном графе 1-парашюта с весом больше 1.

Всякий 1-парашют Ти и Кр является кликой порядка р + 1. В связи с этим, зафиксировав какое-либо множество вершин, мы можем простым перебором найти на этом множестве самый тяжёлый 1-парашют. Формально эта процедура выглядит так.

Процедура 7(Ш). Эта процедура просматривает 1-парашюты на фиксиро-

ванном множестве вершин Ш = {и1,и2,..., щ} С V, I > 3. Положим 7(Ш) = 0, Т и К — графы с пустыми множествами вершин и рёбер.

Шаг г (г = 1, 2,... ,1). Пусть Т.\ — звезда с центром в вершине щ и лучами щиз, ] = 1,. . . ,г — 1,г + 1,.. .1, и К^ - клика на вершинах и1,..., иг-1,иг+1,.. .щ. Если х(ЕТ1) — х(ЕКг) > 7(Ш), то полагаем ^(Ш) := х(ЕТ1) — х(ЕК1), Т = % и К = Кг. Иначе оставляем всё неизменным. Переходим на шаг (г + 1).

Если в результате этой процедуры получим ^(Ш) > 1, то Т и К — искомый 1-парашют на множестве вершин Ш. В процедуре 7(Ш) не обязательно просматривать все вершины и1,и2,...,щ. Можно остановиться сразу, как только 7(Ш) > 1. Однако если размерность задачи относительно невелика, то просмотр лучше довести до конца, так как величину х(ЕТ) — х(ЕК) > 7 можно в определённом смысле считать «глубиной» отсечения.

Вообще говоря, в результате применения процедуры 7 к конкретному множеству Ш может получиться 7(Ш) ^ 1. В этой связи имеет смысл перейти к другому Ш и повторить процедуру. Мы рассматриваем три способа перехода к новому множеству вершин.

1) Множество получается из Ш удалением одной вершины и Е Ш, то есть Ш' С Ш и = | — 1. Такой переход будем обозначать Ш' = <р1(Ш,и).

2) Множество Ш' получается из Ш добавлением одной вершины и' Е ^, то есть Ш С Ш' и = | + 1. Такой переход будем обозначать Ш' = р2(Ш,и').

3) Множество получается из Ш удалением одной вершины и Е Ш и добавлением одной вершины и' Е ^, то есть = | и ^ и Ш'1 — ^ П П I = 2. Для обозначения такого перехода будем использовать запись W, = <рз(Щи,и').

К случайно выбранному множеству Ш применяется каждый из указанных способов в рандомизированном режиме. А именно переход <р1 осуществляется последовательным просмотром вершин множества Ш, вершина и Е Ш выбирается с вероятностью р1, запоминается такое Ш1, что 7^^ = шах^^]^^,^))^ Е Ш}; переход — просмотр множества V \ Ш, вершина и' выбирается с вероятностью р2, запоминается такое Ш2, что 7(^2) = шах{7(^2(Ш,и')),и' Е ^}; переход заключается в просмотре множества Ш х (V \ Ш), пара (и, и') выбирается с вероятностью р3, запоминается

для которого 7(Ш3) = шах{7(р2(Ш,и,и')),и Е Ш,и' Е ^}. В качестве нового множества вершин Ш' выбирается то из множеств Ш1, Ш2 и на котором значение функции 7(Ш) наибольшее.

Описанная процедура является одной итерацией эвристики, используемой нами для решения задачи идентификации 1-парашютов. Обозначим через ^(Ш) множество вершин, которое получается из множества Ш в результате этой итерации. При построении отсекающих 1-парашютов итерации продолжаются то тех пор, пока не прекратится заметный рост функции 7. На рисунках 4 и 5 показан пример работы описанной процедуры для задач с п = 100.

6.00 4.00

2.00

0.00 -2.00

-4.00

-6.00

-8.00

-10.00

Рис. 5. Число вершин в клике 1-парашюта \УК\ = 15, итераций 100, ) = 5

0.00 -5.00 -10.00

-15.00 -20.00 -25.00 -30.00

-35.00 -40.00 -45.00

Рис. 6. Число вершин в клике 1-парашюта \УК\ = 30, итераций 100, ) = —14

В следующем параграфе показаны результаты вычислительного эксперимента, цель которого заключалась в проверке эффективности предложенной процедуры решения задачи идентификации для 1-парашютов. Следует отметить, что анализ результатов вычислительного эксперимента существенно осложняется отсутствием на сегодняшний день тестовых задач.

2. Вычислительный эксперимент

Алгоритм локального поиска 1-парашюта был реализован на языке Java и запускался на компьютере Intel Pentium (2,4 GHz). Сам эксперимент проводился по трём направлениям и был организован следующим образом. На первом этапе исследуется эвристика для построения 1-парашютов при одинаковых значениях параметров р1, р2 и р3. Время было фиксированным и составляло 10 мин. Оценивалось значение целевой функции, полученное на заданных параметрах за 10 мин. Целью этого этапа было выделить, при каких параметрах рост значений целевой функции будет быстрее. В эксперименте рассматривались задачи размерности от 20 до 100, всего было по 10 задач на каждую размерность. Ниже представлен фрагмент таблицы 1 с результатами эксперимента. В первом столбце указано имя файла с решаемой задачей, в последнем — количество рёбер аппроксимируемого графа, в остальных столбцах стоят значения целевой функции, полученные за 10 мин при заданной вероятности.

Таблица 1. Результаты первого эксперимента

Pi = P2 = P'i

Задача 0.25 0.40 0.50 0.60 0.75 EG

f 1 - 40 216.64 216.84 216.89 218.49 218.23 385

f 2 - 40 223.81 225.28 223.54 222.70 225.35 394

f 3 - 40 227.33 225.82 225.86 228.16 226.55 400

f 4 - 40 217.30 218.20 218.27 219.05 219.42 379

f 5 - 40 227.38 225.50 225.14 225.78 227.38 400

f 1 - 50 185.78 180.30 178.89 179.01 190.46 313

f 2 - 50 177.15 175.05 174.32 177.01 177.19 306

Из таблицы 1 видно, что при выбранной вероятности 0.6 — 0.75 рост значения целевой функции за фиксированное время происходит быстрее. Часто найденных с помощью локального поиска неравенств 1-парашютов оказывается очень много, и добавление их всех в качестве отсечений может привести к быстрому росту размерности задачи и, как следствие, к увеличению времени на каждой итерации.

Целью данного эксперимента было выяснить, сколько лучше добавить найденных 1-парашютов, чтобы рост значений функции происходил быстрее. Вероятности были взяты одинаковыми и равными, а именно р\ = р2 = р3 = 0.6. Из всех найденных 1-парашютов выбирались неравенства с наибольшим значением 1атх — 1|. Здесь х — решение задачи ЛП, полученное на очередной итерации,

атх ^ 1 — неравенство 1-парашюта, найденное с помощью эвристики. Время работы программы было фиксированным и составляло 10 минут. На каждой итерации добавлялись найденные неравенства 1-парашютов в количестве 1, п/10, п/5 и п/2, где п — это число вершин исходного графа С. В эксперименте рассматривались задачи размерности от 20 до 100, всего было по 10 задач на каждую размерность. Ниже представлен фрагмент таблицы 2 с результатами эксперимента.

Таблица 2. Результаты второго эксперимента

Я =1 п/10 п/5 п/2

Задача / ах — 1 I ах — 1 I ах — 1 I ЕС

/1 — 40 210.00 2.50 216.30 2.50 217.53 2.68 222.38 385

/ 2 — 40 221.07 2.50 227.50 2.50 228.45 2.21 234.69 394

/ 3 — 40 221.75 2.50 225.81 2.50 230.39 2.00 234.15 400

/ 4 — 40 211.06 2.50 217.27 2.50 220.41 2.19 225.44 379

/ 5 — 40 218.92 2.50 220.00 2.50 229.15 2.24 232.18 400

/1 — 50 174.93 3.89 173.99 4.88 175.42 2.50 177.04 313

/ 2 — 50 171.49 4.62 172.98 4.50 172.24 4.00 173.56 306

/ 3 — 50 180.50 3.50 178.70 2.50 181.25 3.50 183.58 325

/ 4 — 50 173.84 4.58 175.96 3.47 177.81 4.79 177.72 312

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

Последний эксперимент повторяет предыдущий за исключением одного шага. Вместо значения 1атх —1| рассматривалась величина в, = |а . Результаты представлены в таблице 3.

Таблица 3. Результаты третьего эксперимента

Я =1 п/10 п/5 п/2

Задача / й I й I й I ЕС

/1 — 40 214.27 0.30 222.32 0.30 225.04 0.40 231.78 385

/ 2 — 40 225.68 0.30 229.33 0.29 240.59 0.5 244.23 394

/ 3 — 40 225.25 0.36 232.12 0.21 236.52 0.15 241.29 400

/ 4 — 40 216.18 0.32 224.61 0.26 230.36 0.21 234.73 379

/ 5 — 40 222.00 0.32 229.82 0.27 234.86 0.14 240.82 400

/1 — 50 182.18 0.45 186.14 0.37 185.23 0.43 186.43 313

Из таблицы 3 видно, что если выбирать найденные 1-парашюты по значению ^ = |а ¡а-11 при параметрах р1 = р2 = р3 = 0.6 и п/2, то значения целевой функции выше, чем при 1атх — 1|.

Заключение

В заключении автор выражает благодарность Р.Ю. Симанчеву и Ю.А. Ко-четову за ценные идеи и замечания в работе над данной статьёй.

ЛИТЕРАТУРА

1. Симанчев Р.Ю., Уразова И.В. О гранях многогранника задачи аппроксимации графов // Дискрет. анализ и исследование операций 2015. № 22(2). С. 86-101.

2. Simanchev R.Yu., Urazova I.V. Separation Problem for k-parashutes // Proc. DOOR

2016. Vladivostok, Russia, September 19-23. CEUR-WS. 2016. No. 1623. P. 109114. URL: http://ceur-ws.org/Vol-1623/paperco16.pdf (дата обращения: 10.11.2018).

3. Grotschel M., Wakabayashi Y. A cutting plane algorithm for a clustering problem // Mathematical Programming, (Series B). 1989. No. 45. P. 59-96.

4. Grotschel M., Wakabayashi Y. Facets of the clique partitioning polytope // Mathematical Programming. 1990. No. 47. P. 367-387.

5. Simanchev R.Yu., Urazova I.V. Cutting Planes Algorithm for the Connected k-factor Problem Using the Facet Inequalities. Petrovac, Montenegro, October 2-7. CEUR-WS.

2017. URL: http://ceur-ws.org/Vol-1987/paper74.pdf (дата обращения: 10.11.2018).

6. Schrijver A. Combinatorial Optimization. Polyhedra and Efficiency. Springer. 2003. Vol. A.

7. Симанчёв Р.Ю. О неравенствах, порождающих фасеты комбинаторных многогранников // Дискретный анализ и исследование операций. 2017. № 24(4). С. 95-110.

HEURISTICS FOR THE SEPARATION PROBLEM OF 1-PARACHUTES IN THE GRAPH APPROXIMATION PROBLEM

I.V. Urazova

Ph.D. (Phys.-Math.), Associate Professor, e-mail: urazovainn@mail.ru Dostoevsky Omsk State University, Omsk, Russia

Abstract. In work

Keywords: separation problem, plyhedra, facet, approximation problem.

Дата поступления в редакцию: 20.11.2018