Scippy

    SCIP

    Solving Constraint Integer Programs

    xternal_cycleclustering.c
    Go to the documentation of this file.
    1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
    2/* */
    3/* This file is part of the program and library */
    4/* SCIP --- Solving Constraint Integer Programs */
    5/* */
    6/* Copyright (c) 2002-2026 Zuse Institute Berlin (ZIB) */
    7/* */
    8/* Licensed under the Apache License, Version 2.0 (the "License"); */
    9/* you may not use this file except in compliance with the License. */
    10/* You may obtain a copy of the License at */
    11/* */
    12/* http://www.apache.org/licenses/LICENSE-2.0 */
    13/* */
    14/* Unless required by applicable law or agreed to in writing, software */
    15/* distributed under the License is distributed on an "AS IS" BASIS, */
    16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
    17/* See the License for the specific language governing permissions and */
    18/* limitations under the License. */
    19/* */
    20/* You should have received a copy of the Apache-2.0 license */
    21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
    22/* */
    23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
    24
    25/**@file xternal_cycleclustering.c
    26 * @brief main document page
    27 * @author Leon Eifler
    28 */
    29
    30/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
    31
    32/**@page CYCLECLUSTERING_MAIN CycleClustering
    33 * @version 0.1
    34 * @author Leon Eifler
    35 *
    36 * This application can be used to solve the cycle clustering problem as described in
    37 *
    38 * "Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes"@n
    39 * by Isabel Beckenbach, Leon Eifler, Konstantin Fackeldey, Ambros Gleixner, Andreas Grever, Marcus Weber, and Jakob Witzig, @n
    40 * <em> Multiscale Modeling and Simulation </em> , 2016 (accepted for publication, preprint available as <a href="https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6035">ZIB-Report 16-39</a> ).
    41 *
    42 * The input format is an \f$n \times n\f$ - matrix \f$Q\f$ of unconditional transition probabilities with a header of the form
    43 * "# 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".
    44 *
    45 * The cycle clustering problem is the following:
    46 *
    47 * Consider a set of states \f$ \mathcal B = \{1,\ldots,n\}\f$ and a set of clusters \f$\mathcal{C}=\{1,\ldots,m\}\f$.
    48 * Let \f$Q \in \mathbb{R}^{n \times n}\f$ with entries \f$ q_{ij}\f$. Then the problem is given by the MINLP
    49 *
    50 * \f{align*}{
    51 * \max \ \ \ \ \ \sum_{t \in \mathcal{K}}f_t \ + \ &\alpha \cdot \sum_{t \in \mathcal{K}} g_t \notag\\
    52 * \text{s.t.} \quad \sum_{t \in \mathcal{K}} x_{it} &= 1 && \text{ for all } i \in \mathcal{S} \\
    53 * \sum_{i \in \mathcal{S}} x_{it} &\ge 1 && \text{ for all } t \in \mathcal{K} \label{eq:setcover} \\
    54 * 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}\\
    55 * 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} \\
    56 * x_{it} &\in \{0,1\} && \text{ for all } t \in \mathcal{K}, i \in \mathcal{S} \notag \\
    57 * f_t, g_t &\in \mathbb{R}_{\geq 0} && \text{ for all } t \in \mathcal{K}. \notag
    58 * \f}
    59 *
    60 * Further information about particular modules like heuristics and separation routines
    61 * can be found in the documentation of the corresponding files.
    62 *
    63 * Installation
    64 * ------------
    65 *
    66 * See the @ref INSTALL_APPLICATIONS_EXAMPLES "Install file"
    67 *
    68 *
    69 */