  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.
