Partitioning a graph into balanced connected classes: Formulations, separation and experiments

Autor(es)

Miyazawa, Flavio K. ; Moura, Phablo F. S. ; Ota, Matheus J. ; Wakabayashi, Yoshiko

• Tipo de documento: Artigo Científico
• Fonte: European Journal of Operational Research; v. 293, n. 3, p. 11-pg., 2021-04-24.

Resumo

This work addresses the balanced connected k-partition problem (BCPk), which is formally defined as follows. Given a connected graph G = (V, E) with nonnegative weights on the vertices, find a partition {V-i}(i=1)(k) of V such that each class V-i induces a connected subgraph of G, and the weight of a class with the minimum weight is as large as possible. This problem, known to be NP-hard, has been largely investigated under different approaches and perspectives: exact algorithms, approximation algorithms for some values of k or special classes of graphs, and inapproximability results. On the practical side, BCPk is used to model many applications arising in image processing, cluster analysis, operating systems and robotics. We propose three linear programming formulations for BCPk. The first one contains only binary variables and a potentially large number of constraints that can be separated in polynomial time in the corresponding linear relaxation. We introduce new valid inequalities and design polynomial-time separation algorithms for them. The other two formulations are based on flows and have a polynomial number of constraints and variables. Our computational experiments show that the exact algorithms based on the proposed formulations outperform the other exact approaches presented in the literature. (C) 2021 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 16/21250-3 - Aspectos algorítmicos e estruturais de problemas de Cobertura e Empacotamento em grafos
• Beneficiário: Phablo Fernando Soares Moura
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 17/22611-2 - Aspectos algorítmicos e estruturais de problemas de cobertura e empacotamento em grafos
• Beneficiário: Phablo Fernando Soares Moura
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado
• Processo FAPESP: 16/01860-1 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento, localização e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático