Branch and Cut for Partitioning a Graph into a Cycle of Clusters
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909074954649600 |
|---|---|
| author | Eifler, Leon Witzig, Jakob Gleixner, Ambros |
| author_facet | Eifler, Leon Witzig, Jakob Gleixner, Ambros |
| contents | In this paper we study formulations and algorithms for the cycle clustering problem, a partitioning problem over the vertex set of a directed graph with nonnegative arc weights that is used to identify cyclic behavior in simulation data generated from nonreversible Markov state models. Here, in addition to partitioning the vertices into a set of coherent clusters, the resulting clusters must be ordered into a cycle such as to maximize the total net flow in the forward direction of the cycle. We provide a problem-specific binary programming formulation and compare it to a formulation based on the reformulation-linearization technique (RLT). We present theoretical results on the polytope associated with our custom formulation and develop primal heuristics and separation routines for both formulations. In computational experiments on simulation data from biology we find that branch and cut based on the problem-specific formulation outperforms the one based on RLT. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_08412 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Branch and Cut for Partitioning a Graph into a Cycle of Clusters Eifler, Leon Witzig, Jakob Gleixner, Ambros Optimization and Control 65K05, 90C11, 60-xx In this paper we study formulations and algorithms for the cycle clustering problem, a partitioning problem over the vertex set of a directed graph with nonnegative arc weights that is used to identify cyclic behavior in simulation data generated from nonreversible Markov state models. Here, in addition to partitioning the vertices into a set of coherent clusters, the resulting clusters must be ordered into a cycle such as to maximize the total net flow in the forward direction of the cycle. We provide a problem-specific binary programming formulation and compare it to a formulation based on the reformulation-linearization technique (RLT). We present theoretical results on the polytope associated with our custom formulation and develop primal heuristics and separation routines for both formulations. In computational experiments on simulation data from biology we find that branch and cut based on the problem-specific formulation outperforms the one based on RLT. |
| title | Branch and Cut for Partitioning a Graph into a Cycle of Clusters |
| topic | Optimization and Control 65K05, 90C11, 60-xx |
| url | https://arxiv.org/abs/2401.08412 |