Mixed-integer programming for cycle detection in nonreversible Markov processes

DOI10.1137/16M1091162MaRDI QIDQ4643799zbMATH OpenOpenAlexFDO

Authors Jakob Witzig, Isabel Beckenbach, Leon Eifler, Konstantin Fackeldey, Ambros M. Gleixner, Andreas Grever, Marcus Weber

Publication date 29 May 2018

Published in Multiscale Modeling & Simulation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.02063

zbMATH Keywords

mixed-integer programmingMarkov state modelsnonreversible Markov processesNESS

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Combinatorial optimization (90C27) Discrete-time Markov processes on general state spaces (60J05) Mixed integer programming (90C11) Statistical thermodynamics (82B30)

Abstract: In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst.

Recommendations

• Finding dominant structures of nonreversible Markov processes
• Nonstationary cyclic behavior in Markov systems
• scientific article; zbMATH DE number 3864241
• scientific article; zbMATH DE number 7365760
• Reversible Markov Decision Processes with an Average-Reward Criterion

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 967590 (Why is no real title available?)
• A tree-search algorithm for mixed integer programming problems
• An Automatic Method of Solving Discrete Programming Problems
• An Efficient Heuristic Procedure for Partitioning Graphs
• An introduction to Markov state models and their application to long timescale molecular simulation
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computing the Minimal Rebinding Effect Included in a Given Kinetics
• Computing the nearest reversible Markov chain.
• Constraint Integer Programming: A New Approach to Integrate CP and MIP
• Finding dominant structures of nonreversible Markov processes
• Handbook of Markov Chain Monte Carlo
• Identification of almost invariant aggregates in reversible nearly uncoupled Markov chains
• Low-discrepancy and low-dispersion sequences
• L’algebre de Boole et ses applications en recherche operationnelle
• Modularity of directed networks: cycle decomposition approach
• On the Approximation of Complicated Dynamical Behavior
• On the knapsack closure of 0-1 integer linear programs
• On the solution of traveling salesman problems
• Preprocessing and Probing Techniques for Mixed Integer Programming Problems
• Robust Perron cluster analysis in conformation dynamics
• The Complexity of Multiterminal Cuts

Cited in

(1)

• Conflict Analysis for MINLP

Describes a project that uses

Uses Software

• SCIP

This page was built for publication: Mixed-integer programming for cycle detection in nonreversible Markov processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4643799)