Optimizing Connected Components Graph Partitioning With Minimum Size Constraints Using Integer Programming and Spectral Clustering Techniques
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916474349682688 |
|---|---|
| author | Cordero, Mishelle Miniguano-Trujillo, Andrés Recalde, Diego Torres, Ramiro Vaca, Polo |
| author_facet | Cordero, Mishelle Miniguano-Trujillo, Andrés Recalde, Diego Torres, Ramiro Vaca, Polo |
| contents | In this work, a graph partitioning problem in a fixed number of connected components is considered. Given an undirected graph with costs on the edges, the problem consists of partitioning the set of nodes into a fixed number of subsets with minimum size, where each subset induces a connected subgraph with minimal edge cost. The problem naturally surges in applications where connectivity is essential, such as cluster detection in social networks, political districting, sports team realignment, and energy distribution. Mixed Integer Programming formulations together with a variety of valid inequalities are demonstrated and computationally tested. An assisted column generation approach by spectral clustering is also proposed for this problem with additional valid inequalities. Finally, the methods are tested for several simulated instances, and computational results are discussed. Overall, the proposed column generation technique enhanced by spectral clustering offers a promising approach to solve clustering and partitioning problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_11254 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Optimizing Connected Components Graph Partitioning With Minimum Size Constraints Using Integer Programming and Spectral Clustering Techniques Cordero, Mishelle Miniguano-Trujillo, Andrés Recalde, Diego Torres, Ramiro Vaca, Polo Optimization and Control In this work, a graph partitioning problem in a fixed number of connected components is considered. Given an undirected graph with costs on the edges, the problem consists of partitioning the set of nodes into a fixed number of subsets with minimum size, where each subset induces a connected subgraph with minimal edge cost. The problem naturally surges in applications where connectivity is essential, such as cluster detection in social networks, political districting, sports team realignment, and energy distribution. Mixed Integer Programming formulations together with a variety of valid inequalities are demonstrated and computationally tested. An assisted column generation approach by spectral clustering is also proposed for this problem with additional valid inequalities. Finally, the methods are tested for several simulated instances, and computational results are discussed. Overall, the proposed column generation technique enhanced by spectral clustering offers a promising approach to solve clustering and partitioning problems. |
| title | Optimizing Connected Components Graph Partitioning With Minimum Size Constraints Using Integer Programming and Spectral Clustering Techniques |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2202.11254 |