2024/01/16 by Leon Eifler, Eifler, Leon, Jakob Witzig +3
Computer Science · Decision Sciences · #60-xx #65K05 #90C11 #Bayesian Modeling and Causal Inference #FOS: Mathematics #Optimization and Control (math.OC) #Simulation Techniques and Applications
paper · pdf · doi:10.48550/arxiv.2401.08412
openalex publication_date 2024/01/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.