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.
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
Como Citar
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.
