Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • search hit 1 of 22
Back to Result List

Branch and cut for partitioning a graph into a cycle of clusters

  • 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.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Leon Eifler, Jakob Witzig, Ambros Gleixner
Document Type:In Proceedings
Parent Title (English):Combinatorial Optimization. ISCO 2024
Volume:14594
Series:Lecture Notes in Computer Science
Year of first publication:2024
DOI:https://doi.org/10.1007/978-3-031-60924-4_8
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.