Arc-flow formulation for capacitated clustering problems
Abstract
In this work, we present a formulation based on arc-flow models, originally designed for bin packing problems, and now applied to clustering problems. We consider the Correlation Clustering and Graph Partitioning problems with node weights and a cost associated to each cluster. We discuss the advantages of this formulation in comparison with other strategies presented in the literature.
Keywords:
Combinatorial Optimization, Integer Programming, Clustering Problems
References
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.
Published
2020-06-30
How to Cite
CHAGAS, Vítor Gomes; IORI, Manuel.
Arc-flow formulation for capacitated clustering problems. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (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.
