Mixed-Integer Programming for Clustering in Non-reversible Markov Processes

Please always quote using this URN: urn:nbn:de:0297-zib-66486
  • The topic of this thesis is the examination of an optimization model which stems from the clustering process of non-reversible markov processes. We introduce the cycle clustering problem und formulate it as a mixed integer program (MIP). We prove that this problem is N P-hard and discuss polytopal aspects such as facets and dimension. The focus of this thesis is the development of solving methods for this clustering problem. We develop problem specific primal heuristics, as well as separation methods and an approximation algorithm. These techniques are implemented in practice as an application for the MIP solver SCIP. Our computational experiments show that these solving methods result in an average speedup of ×4 compared to generic solvers and that our application is able to solve more instances to optimality within the given time limit of one hour.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Leon Eifler
Document Type:Master's Thesis
Tag:Markov State Models; Mixed-Integer Programming; NESS; Non-reversible Markov Processes
MSC-Classification:60-XX PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX)
82-XX STATISTICAL MECHANICS, STRUCTURE OF MATTER
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Granting Institution:Technische Universität Berlin
Advisor:Thorsten Koch
Year of first publication:2017
Pagenumber:74