Том 26, номер 3, 2019 г., Стр. 60-87

УДК 519.1+519.8
Симанчёв Р. Ю., Уразова И. В., Кочетов Ю. А.
Метод ветвей и отсечений для задачи разбиения на клики

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

Ключевые слова: метод ветвей и отсечений, фасетное неравенство, локальный поиск.

DOI: 10.33048/daio.2019.26.661

Симанчёв Руслан Юрьевич ^1,2
Уразова Инна Владимировна ²
Кочетов Юрий Андреевич ³
1. Омский научный центр СО РАН,
пр. Карла Маркса, 15, 644024 Омск, Россия
2. Омский гос. университет им. Ф. М. Достоевского,
пр. Мира, 55А, 644077 Омск, Россия
3. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: osiman@rambler.ru, urazovainn@mail.ru, jkochet@math.nsc.ru

Статья поступила 29 мая 2018 г.
После доработки — 4 июня 2019 г.
Принята к публикации 5 июня 2019 г.

Литература

[1] Wakabayashi Y. Aggregation of binary relations: Algorithmic and polyhedral investigations, Master Thesis. Univ. Augsburg, West Germany, 1986.

[2] Brimberg J., Janicijevic S., Mladenovic N., Urosevic D. Solving the clique partitioning problem as a maximally diverse grouping problem // Optim. Lett. 2017. Vol. 11. P. 1123–1135.

[3] Brusco M. J., Kohn H. F. Clustering qualitative data based on binary equivalence relations: neighborhood search heuristics for the clique partitioning problem // Psychometrika. 2009. Vol. 74. P. 685–703.

[4] Marcotorchino F., Michaud P. Heuristic approach to the similarity aggregation problem // Methods Oper. Res. 1981. Vol. 43. P. 395–404.

[5] Ham I., Hitomi K., Yoshida T. Group technology: applications to production management. Dordrecht: Kluwer Acad. Publ., 1988.

[6] Oosten M., Rutten J. H. G. C., Spieksma F. C. R. The clique partitioning problem: facets and patching facets // J.Netw. 2001. Vol. 38, No. 4. P. 209–226.

[7] Fortunato S. Community detection in graphs // Phys. Rep. 2010. Vol. 486, No. 3. P. 75–174.

[8] Bocker S., Briesemeister S., Klau G. W. Exact algorithms for cluster editing: evaluation and experiments // Algorithmica. 2011. Vol. 60. P. 316–334.

[9] Grotschel M., Wakabayashi Y. A cutting plane algorithm for a clustering problem // Math. Program. Ser. B. 1989. Vol. 45. P. 59–96.

[10] Grotschel M., Wakabayashi Y. Facets of the clique partitioning polytope // Math. Program. 1990. No. 47. P. 367–387.

[11] Grotschel M., Wakabayashi Y. Composition of facets of the clique partitioning polytope // Topics in Combinatorics and Graph Theory. Heidelberg: Physica-Verl., 1990. P. 271–284.

[12] Симанчёв Р. Ю., Уразова И. В. О гранях многогранника задачи аппроксимации графов // Дискрет. анализ и исслед. операций. 2015. Т. 22, № 2. С. 86–101.

[13] Simanchev R. Yu., Urazova I. V. Separation problem for $k$-parachutes // Proc. DOOR 2016 (Vladivostok, Russia, Sept. 19–23, 2016) CEUR-WS. 2016. Vol. 1623. P. 109–114.
http://ceur-ws.org/Vol-1623/paperco16.pdf

[14] Harary F. On the notion of balance of a signed graph // Mich. Math. J. 1955. Vol. 2. P. 143–146.

[15] Фридман Г. Ш. Одна задача аппроксимации графов // Управляемые системы. 1971. Вып. 8. C. 73–75.

[16] Zahn C. T. Approximating symmetric relations by equivalence relations // J. Soc. Ind. Appl. Math. 1964. Vol. 12, No. 4. P. 840–847.

[17] Krivánek M., Morávek J. NP-hard problems in hierarchical-tree clustering // Acta Inform. 1986. Vol. 23. P. 311–323.

[18] Bansal N., Blum A., Chawla S. Correlation clustering // Machine Learn. 2004. Vol. 56. P. 89–113.

[19] Ben-Dor A., Shamir R., Yakhimi Z. Clustering gene expression patterns // J. Comput. Biol. 1999. Vol. 6, No. 3–4. P. 281–297.

[20] Shamir R., Sharan R., Tsur D. Cluster graph modification problems // Discrete Appl. Math. 2004. Vol. 144, No. 1–2. P. 173–182.

[21] Агеев А. А., Ильев В. П., Кононов А. В., Талевнин А. С. Вычислительная сложность задачи аппроксимации графа // Дискрет. анализ и исслед. операций. 2006. Т. 13, № 1. С. 3–11.

[22] Charikar M., Guruswami V., Wirth A. Clustering with qualitative information // J. Comput. Syst. Sci. 2005. Vol. 71, No. 3. P. 360–383.

[23] Giotis I., Guruswami V. Correlation clustering with a fixed number of clusters // Theory Comput. 2006. Vol. 2, No. 1. P. 249–266.

[24] Ailon N., Charikar M., Newman A. Aggregating inconsistent information: ranking and clustering // J. ACM. 2008. Vol. 55, No. 5. P. 1–27.

[25] Van Zuylen A., Williamson D. P. Deterministic pivoting algorithms for constrained ranking and clustering problems // Math. Oper. Res. 2009. Vol. 34, No. 3. P. 594–620.

[26] Симанчёв Р. Ю., Уразова И. В. Многогранник расписаний обслуживания идентичных требований параллельными приборами // Дискрет. анализ и исслед. операций. 2011. Т. 18, № 11. С. 85–97.

[27] Padberg M. W., Rinaldi G. Facet identification for the symmetric traveling salesman polytope // Math. Program. 1990. Vol. 47. P. 219–257.

[28] Karp R. M., Papadimitriu C. H. On linear characterizations of combinatorial optimization problems // SIAM J. Comput. 1982. Vol. 11. P. 620–632.

[29] Alekseeva E., Kochetov Yu., Plyasunov A. Complexity of local search for the $p$-median problem // Eur. J. Oper. Res. 2008. No. 191. P. 736—752

[30] Iellamo S., Alekseeva E., Chen L., Coupechoux M., Kochetov Yu. Competitive location in cognitive radio networks // 4OR. 2015. Vol. 13, No. 1. P. 81–110.

[31] Mladenovic N., Brimberg J., Hansen P., Moreno-Pérez J. A. The $p$-median problem: a survey of metaheuristic approaches // Eur. J. Oper. Res. 2007. Vol. 179, No. 3. P. 927–939.

[32] Diakova Z., Kochetov Yu. A double VNS heuristic for the facility location and pricing problem // Electron. Notes Discrete Math. 2012. No. 39. P. 29–34.