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.
Author: | Leon EiflerORCiD |
---|---|
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 |
Page Number: | 74 |