<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>6648</id>
    <completedYear/>
    <publishedYear>2017</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber>74</pageNumber>
    <edition/>
    <issue/>
    <volume/>
    <type>masterthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Mixed-Integer Programming for Clustering in Non-reversible Markov Processes</title>
    <abstract language="eng">The topic of this thesis is the examination of an optimization model&#13;
which stems from the clustering process of non-reversible markov processes.&#13;
We introduce the cycle clustering problem und formulate it as a mixed&#13;
integer program (MIP).&#13;
We prove that this problem is N P-hard and discuss polytopal aspects&#13;
such as facets and dimension. The focus of this thesis is the development of&#13;
solving methods for this clustering problem. We develop problem specific&#13;
primal heuristics, as well as separation methods and an approximation&#13;
algorithm. These techniques are implemented in practice as an application&#13;
for the MIP solver SCIP.&#13;
Our computational experiments show that these solving methods result&#13;
in an average speedup of ×4 compared to generic solvers and that our&#13;
application is able to solve more instances to optimality within the given&#13;
time limit of one hour.</abstract>
    <identifier type="urn">urn:nbn:de:0297-zib-66486</identifier>
    <advisor>Thorsten Koch</advisor>
    <author>Leon Eifler</author>
    <submitter>Leon Eifler</submitter>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Markov State Models</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>NESS</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Non-reversible Markov Processes</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed-Integer Programming</value>
    </subject>
    <collection role="msc" number="60-XX">PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX)</collection>
    <collection role="msc" number="82-XX">STATISTICAL MECHANICS, STRUCTURE OF MATTER</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="SparseApproxiTN">SparseApproxiTN</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
    <file>https://opus4.kobv.de/opus4-zib/files/6648/main.pdf</file>
  </doc>
  <doc>
    <id>6035</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2016-05-09</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes</title>
    <abstract language="eng">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.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-60353</identifier>
    <identifier type="doi">10.1137/16M1091162</identifier>
    <author>Jakob Witzig</author>
    <submitter>Jakob Witzig</submitter>
    <author>Isabel Beckenbach</author>
    <author>Leon Eifler</author>
    <author>Konstantin Fackeldey</author>
    <author>Ambros Gleixner</author>
    <author>Andreas Grever</author>
    <author>Marcus Weber</author>
    <series>
      <title>ZIB-Report</title>
      <number>16-39</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Non-reversible Markov Processes</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>NESS</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed-Integer Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Markov State Models</value>
    </subject>
    <collection role="msc" number="60-XX">PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX)</collection>
    <collection role="msc" number="62-XX">STATISTICS</collection>
    <collection role="msc" number="82-XX">STATISTICAL MECHANICS, STRUCTURE OF MATTER</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="num">Numerical Mathematics</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="compmol">Computational Molecular Design</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="fackeldey">Fackeldey, Konstantin</collection>
    <collection role="persons" number="weber">Weber, Marcus</collection>
    <collection role="persons" number="beckenbach">Beckenbach, Isabel</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="SparseApproxiTN">SparseApproxiTN</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6035/ZR-16-39-revised2.pdf</file>
  </doc>
  <doc>
    <id>6029</id>
    <completedYear/>
    <publishedYear>2018</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>248</pageFirst>
    <pageLast>265</pageLast>
    <pageNumber/>
    <edition/>
    <issue>1</issue>
    <volume>16</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2018-02-15</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="eng">Multiscale Modeling and Simulation</parentTitle>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="doi">10.1137/16M1091162</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-60353</enrichment>
    <enrichment key="SourceTitle">Multiscale Modeling and Simulation</enrichment>
    <enrichment key="AcceptedDate">2017-10-18</enrichment>
    <author>Jakob Witzig</author>
    <submitter>Jakob Witzig</submitter>
    <author>Isabel Beckenbach</author>
    <author>Leon Eifler</author>
    <author>Konstantin Fackeldey</author>
    <author>Ambros Gleixner</author>
    <author>Andreas Grever</author>
    <author>Marcus Weber</author>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Markov State Models</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>NESS</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Non-reversible Markov Processes</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed-Integer Programming</value>
    </subject>
    <collection role="msc" number="60-XX">PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX)</collection>
    <collection role="msc" number="82-XX">STATISTICAL MECHANICS, STRUCTURE OF MATTER</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="num">Numerical Mathematics</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="compmol">Computational Molecular Design</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="fackeldey">Fackeldey, Konstantin</collection>
    <collection role="persons" number="weber">Weber, Marcus</collection>
    <collection role="persons" number="beckenbach">Beckenbach, Isabel</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="SparseApproxiTN">SparseApproxiTN</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
</export-example>
