Formulação de fluxo em arcos para problemas de agrupamento capacitado

Resumo


Neste trabalho, apresentamos uma formulação baseada em modelos de fluxo em arcos, originalmente projetados para problemas de empacotamento, e agora aplicada a problemas de agrupamento. Consideramos os problemas de Correlation Clustering e Graph Partitioning com pesos nos vértices e custo associado a cada cluster utilizado. Discutimos as vantagens de tal formulação comparada a outras estratégias presentes na literatura.

Palavras-chave: Otimização Combinatória, Programação Linear Inteira, Problemas de Agrupamento

Referências

Becker, H. (2005). A survey of correlation clustering. Advanced Topics in Computational Learning Theory, pages 1–10.

Buluç, A., Meyerhenke, H., Safro, I., Sanders, P., e Schulz, C. (2016). Recent Advances in Graph Partitioning, pages 117–158. Springer International Publishing, Cham.

Delorme, M. e Iori, M. (2020). Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems. INFORMS Journal on Computing, 32(1): 101–119.
Publicado
30/06/2020
CHAGAS, Vítor Gomes; IORI, Manuel. Formulação de fluxo em arcos para problemas de agrupamento capacitado. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 5. , 2020, Cuiabá. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2020 . p. 97-100. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2020.11099.