Version: 0.1

Author: Leon Eifler

This application can be used to solve the cycle clustering problem as described in

"Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes"
by Isabel Beckenbach, Leon Eifler, Konstantin Fackeldey, Ambros Gleixner, Andreas Grever, Marcus Weber, and Jakob Witzig,
Multiscale Modeling and Simulation , 2016 (accepted for publication, preprint available as ZIB-Report 16-39 ).

The input format is an \(n \times n\) - matrix \(Q\) of unconditional transition probabilities with a header of the form "# p nstates ncluster"; nstates is the size of the matrix, ncluster the desired number of clusters; the name of the file must end with ".spa".

The cycle clustering problem is the following:

Consider a set of states \( \mathcal B = \{1,\ldots,n\}\) and a set of clusters \(\mathcal{C}=\{1,\ldots,m\}\). Let \(Q \in \mathbb{R}^{n \times n}\) with entries \( q_{ij}\). Then the problem is given by the MINLP

    \f{align*}{
 \max \ \ \ \ \ \sum_{t \in \mathcal{K}}f_t \ + \ &\alpha \cdot \sum_{t \in \mathcal{K}} g_t  \notag\\
 \text{s.t.} \quad \sum_{t \in \mathcal{K}} x_{it} &= 1 &&  \text{ for all } i \in \mathcal{S}  \\
 \sum_{i \in \mathcal{S}} x_{it} &\ge 1 &&  \text{ for all } t \in \mathcal{K} \label{eq:setcover} \\
 g_t &=  \sum_{\substack{i,j \in \mathcal{S}\\  i < j}} (q_{ij} + q_{ji}) x_{it} x_{jt} &&  \text{ for all } t \in \mathcal{K}\\
 f_t &= {\sum_{\substack{i,j \in \mathcal{S},\\  i \neq j}} (q_{ij}-q_{ji}) x_{it} x_{j \phi(t)}} &&  \text{ for all } t \in \mathcal{K}  \\
 x_{it} &\in \{0,1\} && \text{ for all } t \in \mathcal{K},  i \in \mathcal{S} \notag \\
 f_t, g_t &\in \mathbb{R}_{\geq 0} && \text{ for all } t \in \mathcal{K}. \notag
 \f}

Further information about particular modules like heuristics and separation routines can be found in the documentation of the corresponding files.

Installation

See the Install file

SCIP

Installation