<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>8445</id>
    <completedYear/>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>52:1</pageFirst>
    <pageLast>52:17</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>210</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2021-10-15</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An Algorithm-Independent Measure of Progress for Linear Constraint Propagation</title>
    <abstract language="eng">Propagation of linear constraints has become a crucial sub-routine in modern Mixed-Integer Programming (MIP) solvers. In practice, iterative algorithms with tolerance-based stopping criteria are used to avoid problems with slow or infinite convergence. However, these heuristic stopping criteria can pose difficulties for fairly comparing the efficiency of different implementations of iterative propagation algorithms in a real-world setting. Most significantly, the presence of unbounded variable domains in the problem formulation makes it difficult to quantify the relative size of reductions performed on them. In this work, we develop a method to measure -- independently of the algorithmic design -- the progress that a given iterative propagation procedure has made at a given point in time during its execution. Our measure makes it possible to study and better compare the behavior of bounds propagation algorithms for linear constraints. We apply the new measure to answer two questions of practical relevance: (i) We investigate to what extent heuristic stopping criteria can lead to premature termination on real-world MIP instances. (ii) We compare a GPU-parallel propagation algorithm against a sequential state-of-the-art implementation and show that the parallel version is even more competitive in a real-world setting than originally reported.</abstract>
    <parentTitle language="eng">27th International Conference on Principles and Practice of Constraint Programming (CP 2021)</parentTitle>
    <identifier type="doi">10.4230/LIPIcs.CP.2021.52</identifier>
    <enrichment key="Series">Leibniz International Proceedings in Informatics (LIPIcs)</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="SubmissionStatus">epub ahead of print</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Boro Sofranac</author>
    <submitter>Boro Sofranac</submitter>
    <author>Ambros Gleixner</author>
    <author>Sebastian Pokutta</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="pokutta">Pokutta, Sebastian</collection>
    <collection role="persons" number="sofranac">Šofranac, Boro</collection>
    <collection role="institutes" number="Mathematical Algorithmic Intelligence">Mathematical Algorithmic Intelligence</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>8056</id>
    <completedYear/>
    <publishedYear>2020</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>1</pageFirst>
    <pageLast>11</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm&#13;
over Sparse Matrices</title>
    <abstract language="eng">Fast domain propagation of linear constraints has become a crucial component of today's best algorithms and solvers for mixed integer programming and pseudo-boolean optimization to achieve peak solving performance. Irregularities in the form of dynamic algorithmic behaviour, dependency structures, and sparsity patterns in the input data make efficient implementations of domain propagation on GPUs and, more generally, on parallel architectures challenging. This is one of the main reasons why domain propagation in state-of-the-art solvers is single thread only. In this paper, we present a new algorithm for domain propagation which (a) avoids these problems and allows for an efficient implementation on GPUs, and is (b) capable of running propagation rounds entirely on the GPU, without any need for synchronization or communication with the CPU. We present extensive computational results which demonstrate the effectiveness of our approach and show that ample speedups are possible on practically relevant problems: on state-of-the-art GPUs, our geometric mean speed-up for reasonably-large instances is around 10x to 20x and can be as high as 195x on favorably-large instances.</abstract>
    <parentTitle language="eng">2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3)</parentTitle>
    <identifier type="arxiv">2009.07785</identifier>
    <identifier type="doi">10.1109/IA351965.2020.00007</identifier>
    <note>URL of the Slides: https://app.box.com/s/qy0pjmhtbm7shk2ypxjxlh2sj4nudvyu</note>
    <note>URL of the Abstract: http://www.pokutta.com/blog/research/2020/09/20/gpu-prob.html</note>
    <enrichment key="opus.import.data">@article{SGP2020,	acceptnotice = {Has been accepted as a full paper for presentation to IA^3 2020: 10th Workshop on Irregular Applications: Architectures and Algorithms.},	arxiv = {https://arxiv.org/abs/2009.07785},	author = {Sofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian},	date-added = {2020-11-22 13:04:18 +0100},	date-modified = {2020-11-22 13:05:11 +0100},	journal = {{Proceedings of IA^3 at SC20}},	month = {9},	ptype = {conference},	slides = {https://app.box.com/s/qy0pjmhtbm7shk2ypxjxlh2sj4nudvyu},	summary = {http://www.pokutta.com/blog/research/2020/09/20/gpu-prob.html},	title = {{Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse Matrices}},	year = {2020}}</enrichment>
    <enrichment key="opus.import.dataHash">c8f95664ef50ec80f05ae2513866c9a4</enrichment>
    <enrichment key="opus.import.date">2020-11-24T09:22:24+00:00</enrichment>
    <enrichment key="opus.import.file">pokutta-2020.bib</enrichment>
    <enrichment key="opus.import.format">bibtex</enrichment>
    <enrichment key="opus.import.id">5fbcd0d091bac7.18675871</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <author>Boro Sofranac</author>
    <author>Ambros Gleixner</author>
    <author>Sebastian Pokutta</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="pokutta">Pokutta, Sebastian</collection>
    <collection role="persons" number="sofranac">Šofranac, Boro</collection>
    <collection role="institutes" number="Mathematical Algorithmic Intelligence">Mathematical Algorithmic Intelligence</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>8549</id>
    <completedYear/>
    <publishedYear>2022</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>102874</pageFirst>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>109</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2021-11-26</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Accelerating domain propagation: An efficient GPU-parallel algorithm over sparse matrices</title>
    <abstract language="eng">• Currently, domain propagation in state-of-the-art MIP solvers is single thread only.&#13;
• The paper presents a novel, efficient GPU algorithm to perform domain propagation.&#13;
• Challenges are dynamic algorithmic behavior, dependency structures, sparsity patterns.&#13;
• The algorithm is capable of running entirely on the GPU with no CPU involvement.&#13;
• We achieve speed-ups of around 10x to 20x, up to 180x on favorably-large instances.</abstract>
    <parentTitle language="eng">Parallel Computing</parentTitle>
    <identifier type="doi">10.1016/j.parco.2021.102874</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Boro Šofranac</author>
    <submitter>Boro Šofranac</submitter>
    <author>Ambros Gleixner</author>
    <author>Sebastian Pokutta</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="pokutta">Pokutta, Sebastian</collection>
    <collection role="persons" number="sofranac">Šofranac, Boro</collection>
    <collection role="institutes" number="Mathematical Algorithmic Intelligence">Mathematical Algorithmic Intelligence</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>7804</id>
    <completedYear/>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>443</pageFirst>
    <pageLast>490</pageLast>
    <pageNumber/>
    <edition/>
    <issue>3</issue>
    <volume>13</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library</title>
    <abstract language="eng">We report on the selection process leading to the sixth version of the Mixed Integer Programming Library. Selected from an initial pool of over 5,000 instances, the new MIPLIB 2017 collection consists of 1,065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, the compilation of these sets was done using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encoded requirements on diversity and balancedness with respect to instance features and performance data.</abstract>
    <parentTitle language="eng">Mathematical Programming Computation</parentTitle>
    <identifier type="doi">10.1007/s12532-020-00194-3</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">2020-09-10</enrichment>
    <author>Ambros Gleixner</author>
    <submitter>Ambros Gleixner</submitter>
    <author>Gregor Hendel</author>
    <author>Gerald Gamrath</author>
    <author>Tobias Achterberg</author>
    <author>Michael Bastubbe</author>
    <author>Timo Berthold</author>
    <author>Philipp M. Christophel</author>
    <author>Kati Jarck</author>
    <author>Thorsten Koch</author>
    <author>Jeff Linderoth</author>
    <author>Marco Lübbecke</author>
    <author>Hans Mittelmann</author>
    <author>Derya Ozyurt</author>
    <author>Ted Ralphs</author>
    <author>Domenico Salvagnin</author>
    <author>Yuji Shinano</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="achterberg">Achterberg, Tobias</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="gamrath">Gamrath, Gerald</collection>
    <collection role="persons" number="hendel">Hendel, Gregor</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</collection>
    <collection role="projects" number="ASTfSCM">ASTfSCM</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="Siemens">Siemens</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>8951</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>2023-01-19</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Strengthening SONC Relaxations with Constraints Derived from Variable Bounds</title>
    <abstract language="eng">Nonnegativity certificates can be used to obtain tight dual bounds for polynomial optimization problems. Hierarchies of certificate-based relaxations ensure convergence to the global optimum, but higher levels of such hierarchies can become very computationally expensive, and the well-known sums of squares hierarchies scale poorly with the degree of the polynomials. This has motivated research into alternative certificates and approaches to global optimization. We consider sums of nonnegative circuit polynomials (SONC) certificates, which are well-suited for sparse problems since the computational cost depends on the number of terms in the polynomials and does not depend on the degrees of the polynomials. We propose a method that guarantees that given finite variable domains, a SONC relaxation will yield a finite dual bound. This method opens up a new approach to utilizing variable bounds in SONC-based methods, which is particularly crucial for integrating SONC relaxations into branch-and-bound algorithms. We report on computational experiments with incorporating SONC relaxations into the spatial branch-and-bound algorithm of the mixed-integer nonlinear programming framework SCIP. Applying our strengthening method increases the number of instances where the SONC relaxation of the root node yielded a finite dual bound from 9 to 330 out of 349 instances in the test set.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-89510</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <author>Ksenia Bestuzheva</author>
    <submitter>Ksenia Bestuzheva</submitter>
    <author>Helena Völker</author>
    <author>Ambros Gleixner</author>
    <collection role="msc" number="14Q99">None of the above, but in this section</collection>
    <collection role="msc" number="68-04">Explicit machine computation and programs (not the theory of computation or programming)</collection>
    <collection role="msc" number="90C26">Nonconvex programming, global optimization</collection>
    <collection role="msc" number="90C57">Polyhedral combinatorics, branch-and-bound, branch-and-cut</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="bestuzheva">Bestuzheva, Ksenia</collection>
    <collection role="persons" number="helena.mueller">Müller, Helena</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8951/zr.pdf</file>
  </doc>
  <doc>
    <id>8830</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>2022-11-23</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Strengthening SONC Relaxations with Constraints Derived from Variable Bounds</title>
    <abstract language="eng">Certificates of polynomial nonnegativity can be used to obtain tight dual bounds for polynomial optimization problems. We consider Sums of Nonnegative Circuit (SONC) polynomials certificates, which are well suited for sparse problems since the computational cost depends only on the number of terms in the polynomials and does not depend on the degrees of the polynomials. This work is a first step to integrating SONC-based relaxations of polynomial problems into a branch-and-bound algorithm. To this end, the SONC relaxation for constrained optimization problems is extended in order to better utilize variable bounds, since this property is key for the success of a relaxation in the context of branch-and-bound. Computational experiments show that the proposed extension is crucial for making the SONC relaxations applicable to most constrained polynomial optimization problems and for integrating the two approaches.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-88306</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <author>Ksenia Bestuzheva</author>
    <submitter>Ksenia Bestuzheva</submitter>
    <author>Ambros Gleixner</author>
    <author>Helena Völker</author>
    <series>
      <title>ZIB-Report</title>
      <number>22-23</number>
    </series>
    <collection role="ccs" number="I.">Computing Methodologies</collection>
    <collection role="msc" number="14-04">Explicit machine computation and programs (not the theory of computation or programming)</collection>
    <collection role="msc" number="90-08">Computational methods</collection>
    <collection role="msc" number="90C26">Nonconvex programming, global optimization</collection>
    <collection role="msc" number="90C30">Nonlinear programming</collection>
    <collection role="msc" number="90C57">Polyhedral combinatorics, branch-and-bound, branch-and-cut</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="bestuzheva">Bestuzheva, Ksenia</collection>
    <collection role="persons" number="helena.mueller">Müller, Helena</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8830/SONC_HUGO2022.pdf</file>
  </doc>
  <doc>
    <id>7941</id>
    <completedYear/>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>751</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2020-08-26</completedDate>
    <publishedDate>2021-01-10</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Incremental design of water symbiosis networks with prior knowledge: The case of an industrial park in Kenya</title>
    <abstract language="eng">Industrial parks have a high potential for recycling and reusing resources such as water across companies by creating symbiosis networks. In this study, we introduce a mathematical optimization framework for the design of water network integration in industrial parks formulated as a large-scale standard mixed-integer non-linear programming (MINLP) problem. The novelty of our approach relies on i) developing a multi-level incremental optimization framework for water network synthesis, ii) including prior knowledge of demand growth and projected water scarcity to evaluate the significance of water-saving solutions, iii) incorporating a comprehensive formulation of water network synthesis problem including multiple pollutants and different treatment units and iv) performing a multi-objective optimization of the network including freshwater savings and relative cost of the network. The significance of the proposed optimization framework is illustrated by applying it to an existing industrial park in a water-scarce region in Kenya. Firstly, we illustrated the benefits of including prior knowledge to prevent an over-design of the network at the early stages. In the case study, we achieved a more flexible and expandable water network with 36% lower unit cost at the early stage and 15% lower unit cost at later stages for the overall maximum freshwater savings of 25%. Secondly, multi-objective analysis suggests an optimum freshwater savings of 14% to reduce the unit cost of network by half. Moreover, the significance of symbiosis networks is highlighted by showing that intra-company connections can only achieve a maximum freshwater savings of 17% with significantly higher unit cost (+45%). Finally, we showed that the values of symbiosis connectivity index in the Pareto front correspond to higher freshwater savings, indicating the significant role of the symbiosis network in the industrial park under study. This is the first study, where all the above elements have been taken into account simultaneously for the design of a water reuse network.</abstract>
    <parentTitle language="eng">Science of the Total Environment</parentTitle>
    <identifier type="doi">https://doi.org/10.1016/j.scitotenv.2020.141706</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <author>Elham Ramin</author>
    <submitter>Ksenia Bestuzheva</submitter>
    <author>Ksenia Bestuzheva</author>
    <author>Carina Gargalo</author>
    <author>Danial Ramin</author>
    <author>Carina Schneider</author>
    <author>Pedram Ramin</author>
    <author>Xavier Flores-Alsina</author>
    <author>Maj M. Andersen</author>
    <author>Krist V. Gernaey</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="bestuzheva">Bestuzheva, Ksenia</collection>
    <collection role="institutes" number="Mathematical Algorithmic Intelligence">Mathematical Algorithmic Intelligence</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>8795</id>
    <completedYear/>
    <publishedYear>2022</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>41</pageFirst>
    <pageLast>44</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Strengthening SONC Relaxations with Constraints Derived from Variable Bounds</title>
    <abstract language="eng">Certificates of polynomial nonnegativity can be used to obtain tight dual bounds for polynomial optimization problems. We consider Sums of Nonnegative Circuit (SONC) polynomials certificates, which are well suited for sparse problems since the computational cost depends only on the number of terms in the polynomials and does not depend on the degrees of the polynomials. This work is a first step to integrating SONC-based relaxations of polynomial problems into a branch-and-bound algorithm. To this end, the SONC relaxation for constrained optimization problems is extended in order to better utilize variable bounds, since this property is key for the success of a relaxation in the context of branch-and-bound. Computational experiments show that the proposed extension is crucial for making the SONC relaxations applicable to most constrained polynomial optimization problems and for integrating the two approaches.</abstract>
    <parentTitle language="eng">Proceedings of the Hungarian Global Optimization Workshop HUGO 2022</parentTitle>
    <identifier type="arxiv">2211.05518</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-88306</enrichment>
    <author>Ksenia Bestuzheva</author>
    <submitter>Ksenia Bestuzheva</submitter>
    <author>Ambros Gleixner</author>
    <author>Helena Völker</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="bestuzheva">Bestuzheva, Ksenia</collection>
    <collection role="persons" number="helena.mueller">Müller, Helena</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>8953</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>2023-01-20</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Approximating the RSRP with Predictive Maintenance</title>
    <abstract language="eng">We study the solution of the rolling stock rotation problem with predictive maintenance (RSRP-PM) by an iterative refinement approach that is based on a state-expanded event-graph. In this graph, the states are parameters of a failure distribution, and paths correspond to vehicle rotations with associated health state approximations. An optimal set of paths including maintenance can be computed by solving an integer linear program. Afterwards, the graph is refined and the procedure repeated. An associated linear program gives rise to a lower bound that can be used to determine the solution quality. Computational results for two instances derived from real world timetables of a German railway company are presented. The results show the effectiveness of the approach and the quality of the solutions.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-89531</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PeerReviewed">no</enrichment>
    <enrichment key="SubmissionStatus">accepted for publication</enrichment>
    <author>Felix Prause</author>
    <submitter>Felix Prause</submitter>
    <author>Ralf Borndörfer</author>
    <author>Boris Grimm</author>
    <author>Alexander Tesch</author>
    <series>
      <title>ZIB-Report</title>
      <number>23-04</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Rolling Stock Rotation Planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Predictive Maintenance</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Integer Linear Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Heuristic</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Lower Bound</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="tesch">Tesch, Alexander</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="prause">Prause, Felix</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="BerDiBa">BerDiBa</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8953/ZR-23-04.pdf</file>
  </doc>
  <doc>
    <id>9313</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>2023-12-20</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Multi-Swap Heuristic for Rolling Stock Rotation Planning with Predictive Maintenance</title>
    <abstract language="eng">We present a heuristic solution approach for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). The task of this problem is to assign a sequence of trips to each of the vehicles&#13;
and to schedule their maintenance such that all trips can be operated. Here, the health states of the vehicles are considered to be random variables distributed by a family of probability distribution functions, and the maintenance services should be scheduled based on the failure probability of the vehicles. The proposed algorithm first generates a solution by solving an integer linear program and then heuristically improves this solution by applying a local search procedure. For this purpose, the trips assigned to the vehicles are split up and recombined, whereby additional deadhead trips can be inserted between the partial assignments. Subse-&#13;
quently, the maintenance is scheduled by solving a shortest path problem in a state-expanded version of a space-time graph restricted to the trips of the individual vehicles. The solution approach is tested and evaluated on a set of test instances based on real-world timetables.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-93133</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="SubmissionStatus">accepted for publication</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <author>Felix Prause</author>
    <submitter>Felix Prause</submitter>
    <series>
      <title>ZIB-Report</title>
      <number>23-29</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Rolling stock rotation planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Predictive maintenance</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Heuristic</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>State-expanded graph model</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Integer linear program</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="prause">Prause, Felix</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="BerDiBa">BerDiBa</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/9313/ZR-23-29.pdf</file>
  </doc>
  <doc>
    <id>9602</id>
    <completedYear/>
    <publishedYear>2024</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An Iterative Refinement Approach for the Rolling Stock Rotation Problem with Predictive Maintenance</title>
    <abstract language="eng">The rolling stock rotation problem with predictive maintenance (RSRP-PdM) involves the assignment of trips to a fleet of vehicles with integrated maintenance scheduling based on the predicted failure probability of the vehicles. These probabilities are determined by the health states of the vehicles, which are considered to be random variables distributed by a parameterized family of probability distribution functions. During the operation of the trips, the corresponding parameters get updated. In this article, we present a dual solution approach for RSRP-PdM and generalize a linear programming based lower bound for this problem to families of probability distribution functions with more than one parameter. For this purpose, we define a rounding function that allows for a consistent underestimation of the parameters and model the problem by a state-expanded event-graph in which the possible states are restricted to a discrete set. This induces a flow problem that is solved by an integer linear program. We show that the iterative refinement of the underlying discretization leads to solutions that converge from below to an optimal solution of the original instance. Thus, the linear relaxation of the considered integer linear program results in a lower bound for RSRP-PdM. Finally, we report on the results of computational experiments conducted on a library of test instances.</abstract>
    <identifier type="arxiv">2404.08367</identifier>
    <enrichment key="SubmissionStatus">under review</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PeerReviewed">no</enrichment>
    <author>Felix Prause</author>
    <submitter>Felix Prause</submitter>
    <author>Ralf Borndörfer</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="prause">Prause, Felix</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="BerDiBa">BerDiBa</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>9603</id>
    <completedYear/>
    <publishedYear>2024</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>58</pageFirst>
    <pageLast>63</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Multi-Swap Heuristic for Rolling Stock Rotation Planning with Predictive Maintenance</title>
    <abstract language="eng">We present a heuristic solution approach for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). The task of this problem is to assign a sequence of trips to each of the vehicles and to schedule their maintenance such that all trips can be operated. Here, the health states of the vehicles are considered to be random variables distributed by a family of probability distribution functions, and the maintenance services should be scheduled based on the failure probability of the vehicles. The proposed algorithm first generates a solution by solving an integer linear program and then heuristically improves this solution by applying a local search procedure. For this purpose, the trips assigned to the vehicles are split up and recombined, whereby additional deadhead trips can be inserted between the partial assignments. Subsequently, the maintenance is scheduled by solving a shortest path problem in a state-expanded version of a space-time graph restricted to the trips of the individual vehicles. The solution approach is tested and evaluated on a set of test instances based on real-world timetables.</abstract>
    <parentTitle language="eng">Proceedings of the 11th International Network Optimization Conference (INOC), Dublin, Ireland, March 11-23, 2024</parentTitle>
    <identifier type="doi">10.48786/inoc.2024.11</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-93133</enrichment>
    <author>Felix Prause</author>
    <submitter>Felix Prause</submitter>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="prause">Prause, Felix</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="BerDiBa">BerDiBa</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>9556</id>
    <completedYear/>
    <publishedYear>2024</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>100434</pageFirst>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>30</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Approximating rolling stock rotations with integrated predictive maintenance</title>
    <abstract language="eng">We study the solution of the rolling stock rotation problem with predictive maintenance (RSRP-PdM) by an iterative refinement approach that is based on a state-expanded event-graph. In this graph, the states are parameters of a failure distribution, and paths correspond to vehicle rotations with associated health state approximations. An optimal set of paths including maintenance can be computed by solving an integer linear program. Afterwards, the graph is refined and the procedure repeated. An associated linear program gives rise to a lower bound that can be used to determine the solution quality. Computational results for six instances derived from real-world timetables of a German railway company are presented. The results show the effectiveness of the approach and the quality of the solutions.</abstract>
    <parentTitle language="eng">Journal of Rail Transport Planning &amp; Management</parentTitle>
    <identifier type="doi">10.1016/j.jrtpm.2024.100434</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">2024-02-28</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-89531</enrichment>
    <author>Felix Prause</author>
    <submitter>Felix Prause</submitter>
    <author>Ralf Borndörfer</author>
    <author>Boris Grimm</author>
    <author>Alexander Tesch</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="tesch">Tesch, Alexander</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="prause">Prause, Felix</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="BerDiBa">BerDiBa</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
</export-example>
