| Texto completo | |
| Autor(es): |
Miyazawa, Flavio K.
;
Moura, Phablo F. S.
;
Ota, Matheus J.
;
Wakabayashi, Yoshiko
Número total de Autores: 4
|
| Tipo de documento: | Artigo Científico |
| Fonte: | COMBINATORIAL OPTIMIZATION, ISCO 2020; v. 12176, p. 12-pg., 2020-01-01. |
| Resumo | |
For a fixed integer k >= 2, the balanced connected k-partition problem (BCPk) consists in partitioning a graph into k mutually vertex-disjoint connected subgraphs of similar weight. More formally, given a connected graph G with nonnegative weights on the vertices, find a partition {V-i}(i=1)(k) of V (G) such that each class Vi 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, is used to model many applications arising in image processing, cluster analysis, operating systems and robotics. We propose an ILP and a MILP formulation for BCPk. The first one contains only binary variables and a potentially large number of constraints that can be separated in polynomial time. We also present polyhedral results on the polytope associated with this formulation, introduce new valid inequalities and design separation algorithms. The other formulation is based on flows and has a polynomial number of constraints and variables. Computational experiments show that our formulations achieve better results than the other formulations presented in the literature. (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: | 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 |
| 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 |