<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>7463</id>
    <completedYear>2019</completedYear>
    <publishedYear>2019</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2019-09-09</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Bounds for the final ranks during a round robin tournament</title>
    <abstract language="eng">This article answers two kinds of questions regarding the Bundesliga which is Germany's primary football (soccer) competition having the highest average stadium attendance worldwide. First "At any point of the season, what final rank will a certain team definitely reach?" and second "At any point of the season, what final rank can a certain team at most reach?". Although we focus especially on the Bundesliga, the models that we use to answer the two questions can easily be adopted to league systems that are similar to that of the Bundesliga.</abstract>
    <parentTitle language="deu">Operational Research - An International Journal (ORIJ)</parentTitle>
    <identifier type="urn">urn:nbn:de:0297-zib-74638</identifier>
    <identifier type="doi">https://doi.org/10.1007/s12351-020-00546-w</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="SubmissionStatus">accepted for publication</enrichment>
    <enrichment key="AcceptedDate">2020-01-07</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-74638</enrichment>
    <author>Uwe Gotzes</author>
    <submitter>Kai Hoppmann</submitter>
    <author>Kai Hoppmann</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-50</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="hennig">Hoppmann, Kai</collection>
    <collection role="projects" number="MODAL-GasLab">MODAL-GasLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="enernet">Energy Network Optimization</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7463/bounding_final_ranks.pdf</file>
  </doc>
  <doc>
    <id>7417</id>
    <completedYear/>
    <publishedYear>2019</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2019-08-01</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Verification of Neural Networks</title>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-74174</identifier>
    <author>Ansgar Rössig</author>
    <submitter>Milena Petkovic</submitter>
    <series>
      <title>ZIB-Report</title>
      <number>19-40</number>
    </series>
    <collection role="ddc" number="0">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="ccs" number="G.">Mathematics of Computing</collection>
    <collection role="bk" number="31">Mathematik</collection>
    <collection role="collections" number="">Studienabschlussarbeiten</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MODAL-GasLab">MODAL-GasLab</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/7417/ZR_19-40.pdf</file>
  </doc>
  <doc>
    <id>7385</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>2019-07-05</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">New Perspectives on PESP: T-Partitions and Separators</title>
    <abstract language="eng">In the planning process of public transportation companies, designing the timetable is among the core planning steps. In particular in the case of periodic (or cyclic) services, the Periodic Event Scheduling Problem (PESP) is well-established to compute high-quality periodic timetables.&#13;
&#13;
We are considering algorithms for computing good solutions for the very basic PESP with no additional extra features as add-ons. The first of these algorithms generalizes several primal heuristics that had been proposed in the past, such as single-node cuts and the modulo network simplex algorithm. We consider partitions of the graph, and identify so-called delay cuts as a structure that allows to generalize several previous heuristics. In particular, when no more improving delay cut can be found, we already know that the other heuristics could not improve either.&#13;
&#13;
The second of these algorithms turns a strategy, that had been discussed in the past, upside-down: Instead of gluing together the network line-by-line in a bottom-up way, we develop a divide-and-conquer-like top-down approach to separate the initial problem into two easier subproblems such that the information loss along their cutset edges is as small as possible.&#13;
&#13;
We are aware that there may be PESP instances that do not fit well the separator setting. Yet, on the RxLy-instances of PESPlib in our experimental computations, we come up with good primal solutions and dual bounds. In particular, on the largest instance (R4L4), this new separator approach, which applies a state-of-the-art solver as subroutine, is able to come up with better dual bounds than purely applying this state-of-the-art solver in the very same time.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-73853</identifier>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2019.2</identifier>
    <author>Niels Lindner</author>
    <submitter>Niels Lindner</submitter>
    <author>Christian Liebchen</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-35</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic Event Scheduling Problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic Timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Graph Partitioning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Graph Separators</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Balanced Cuts</value>
    </subject>
    <collection role="ccs" number="G.">Mathematics of Computing</collection>
    <collection role="ccs" number="J.">Computer Applications</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="projects" number="ECMath-MI7">ECMath-MI7</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7385/main.pdf</file>
  </doc>
  <doc>
    <id>7401</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>2019-07-20</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Visible points, the separation problem, and applications to MINLP</title>
    <abstract language="eng">In this paper we introduce a technique to produce tighter cutting planes for mixed-integer non-linear programs. Usually, a cutting plane is generated to cut off a specific infeasible point. The underlying idea is to use the infeasible point to restrict the feasible region in order to obtain a tighter domain. To ensure validity, we require that every valid cut separating the infeasible point from the restricted feasible region is still valid for the original feasible region. We translate this requirement in terms of the separation problem and the reverse polar. In particular, if the reverse polar of the restricted feasible region is the same as the reverse polar of the feasible region, then any cut valid for the restricted feasible region that \emph{separates} the infeasible point, is valid for the feasible region. We show that the reverse polar of the \emph{visible points} of the feasible region from the infeasible point coincides with the reverse polar of the feasible region. In the special where the feasible region is described by a single non-convex constraint intersected with a convex set we provide a characterization of the visible points. Furthermore, when the non-convex constraint is quadratic the characterization is particularly simple. We also provide an extended formulation for a relaxation of the visible points when the non-convex constraint is a general polynomial. Finally, we give some conditions under which for a given set there is an inclusion-wise smallest set, in some predefined family of sets, whose reverse polars coincide.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-74016</identifier>
    <author>Felipe Serrano</author>
    <submitter>Felipe Serrano</submitter>
    <series>
      <title>ZIB-Report</title>
      <number>19-38</number>
    </series>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</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="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7401/visible.pdf</file>
  </doc>
  <doc>
    <id>7397</id>
    <completedYear/>
    <publishedYear>2019</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2019-07-18</completedDate>
    <publishedDate>2019-07-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Re-optimizing ICE Rotations after a Tunnel Breakdown near Rastatt</title>
    <abstract language="eng">Planning    rolling    stock    movements    in    industrial    passenger    railway    applications    isa long-term process based on timetables which are also often valid for long periods of time. For these timetables and rotation plans, i.e., plans of railway vehicle movements are constructed as templates for these periods. During operation the rotation plans are affected by all kinds of unplanned events. An unusal example for that is the collapse of a tunnel ceiling near Rastatt in southern Germany due to construction works related to the renewal of the central station in Stuttgart. As a result the main railway connection between Stuttgart and Frankfurt am Main, located on top of the tunnel, had to be closed from August 12th to October 2nd 2017. This had a major impact on the railway network in southern Germany. Hence, all rotation plans and train schedules for both passenger and cargo traffic had to be revised. In this paper we focus on a case study for this situation and compute new rotation plans via mixed integer programming for  the  ICE  high  speed  fleet  of  DB  Fernverkehr  AG  one  of  the  largest  passenger  railway companies in Europe. In our approach we take care of some side constraints to ensure a smooth continuation of the rotation plans after the disruption has ended.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-73976</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceedings of the 8th International Conference on Railway Operations Modelling and Analysis - RailNorrköping 2019</enrichment>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <author>Boris Grimm</author>
    <submitter>Boris Grimm</submitter>
    <author>Ralf Borndörfer</author>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-02</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>case study</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>re-optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>railway rolling stock optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed integer programming</value>
    </subject>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</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/7397/ZR-19-02.pdf</file>
  </doc>
  <doc>
    <id>7386</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>2019-07-05</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Restricted Modulo Network Simplex Method for Integrated Periodic Timetabling and Passenger Routing</title>
    <abstract language="eng">The Periodic Event Scheduling Problem is a well-studied NP-hard problem with applications in public transportation to find good periodic timetables. Among the most powerful heuristics to solve the periodic timetabling problem is the modulo network simplex method. In this paper, we consider the more difficult version with integrated passenger routing and propose a refined integrated variant to solve this problem on real-world-based instances.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-73868</identifier>
    <identifier type="doi">https://doi.org/https://doi.org/10.1007/978-3-030-48439-2_92</identifier>
    <author>Fabian Löbel</author>
    <submitter>Niels Lindner</submitter>
    <author>Niels Lindner</author>
    <author>Ralf Borndörfer</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-36</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic Event Scheduling Problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic Timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Integrated Passenger Routing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Shortest Routes in Public Transport</value>
    </subject>
    <collection role="ccs" number="J.">Computer Applications</collection>
    <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="fabian.loebel">Löbel, Fabian</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="projects" number="ECMath-MI7">ECMath-MI7</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7386/paper_OR19.pdf</file>
  </doc>
  <doc>
    <id>7275</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>2019-03-13</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Using two-dimensional Projections for Stronger Separation and Propagation of Bilinear Terms</title>
    <abstract language="eng">One of the most fundamental ingredients in mixed-integer nonlinear programming solvers is the well- known McCormick relaxation for a product of two variables x and y over a box-constrained domain. The starting point of this paper is the fact that the convex hull of the graph of xy can be much tighter when computed over a strict, non-rectangular subset of the box. In order to exploit this in practice, we propose to compute valid linear inequalities for the projection of the feasible region onto the x-y-space by solving a sequence of linear programs akin to optimization-based bound tightening. These valid inequalities allow us to employ results from the literature to strengthen the classical McCormick relaxation. As a consequence, we obtain a stronger convexification procedure that exploits problem structure and can benefit from supplementary information obtained during the branch-and bound algorithm such as an objective cutoff. We complement this by a new bound tightening procedure that efficiently computes the best possible bounds for x, y, and xy over the available projections. Our computational evaluation using the academic solver SCIP exhibit that the proposed methods are applicable to a large portion of the public test library MINLPLib and help to improve performance significantly.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-72759</identifier>
    <author>Benjamin Müller</author>
    <submitter>Benjamin Müller</submitter>
    <author>Felipe Serrano</author>
    <author>Ambros Gleixner</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-15</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed-integer quadratically constrained programs</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>nonconvex</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>global optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>separation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>propagation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>projection</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>bilinear terms</value>
    </subject>
    <collection role="ccs" number="G.">Mathematics of Computing</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</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="projects" number="EnBA-M">EnBA-M</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7275/ZR-19-15.pdf</file>
  </doc>
  <doc>
    <id>7302</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>2019-04-29</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Exploiting Dual Degeneracy in Branching</title>
    <abstract language="eng">Branch-and-bound methods for mixed-integer programming (MIP) are traditionally based on solving a linear programming (LP) relaxation and branching on a variable which takes a fractional value in the (single) computed relaxation optimum. In this paper, we study branching strategies for mixed-integer programs that exploit the knowledge of multiple alternative optimal solutions (a cloud ) of the current LP relaxation. These strategies naturally extend common methods like most infeasible branching, strong branching, pseudocost branching, and their hybrids, but we also propose a novel branching rule called cloud diameter branching. We show that dual degeneracy, a requirement for alternative LP optima, is present for many instances from common MIP test sets. Computational experiments show significant improvements in the quality of branching decisions as well as reduced branching effort when using our modifications of existing branching rules. We discuss different ways to generate a cloud of solutions and present extensive computational results showing that through a careful implementation, cloud modifications can speed up full strong branching by more than 10 % on standard test sets. Additionally, by exploiting degeneracy, we are also able to improve the state-of-the-art hybrid branching rule and reduce the solving time on affected instances by almost 20 % on average.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-73028</identifier>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <author>Timo Berthold</author>
    <submitter>Gerald Gamrath</submitter>
    <author>Gerald Gamrath</author>
    <author>Domenico Salvagnin</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-17</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branching rule</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>search strategy</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>dual degeneracy</value>
    </subject>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="90C11">Mixed integer 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="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="gamrath">Gamrath, Gerald</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="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7302/ZR-19-17.pdf</file>
  </doc>
  <doc>
    <id>7280</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>2019-03-20</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An Easy Way to Build Parallel State-of-the-art Combinatorial Optimization Problem Solvers: A Computational Study on Solving Steiner Tree Problems and Mixed Integer Semidefinite Programs by using ug[SCIP-*,*]-libraries</title>
    <abstract language="eng">Branch-and-bound (B&amp;B) is an algorithmic framework for solving NP-hard combinatorial optimization problems. Although several well-designed software frameworks for parallel B&amp;B have been developed over the last two decades, there is very few literature about successfully solving previously intractable combinatorial optimization problem instances to optimality by using such frameworks.The main reason for this limited impact of parallel solvers is that the algorithmic improvements for specific problem types are significantly greater than performance gains obtained by  parallelization in general. Therefore, in order to solve hard problem instances for the first time, one needs to accelerate state-of-the-art algorithm implementations. In this paper, we present a computational study for solving Steiner tree problems and mixed integer semidefinite programs in parallel. These state-of-the-art algorithm implementations are based on SCIP and were parallelized via the ug[SCIP-*,*]-libraries---by adding less than 200 lines of glue code. Despite the ease of their parallelization, these solvers have the potential to solve previously intractable instances. In this paper, we demonstrate the convenience of such a parallelization and present results for previously unsolvable instances from the well-known PUC benchmark set, widely regarded as the most difficult Steiner tree test set in the literature.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-72804</identifier>
    <author>Yuji Shinano</author>
    <submitter>Daniel Rehfeldt</submitter>
    <author>Daniel Rehfeldt</author>
    <author>Tristan Galley</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-14</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="rehfeldt">Rehfeldt, Daniel</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="BEAM-ME">BEAM-ME</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/7280/pco2019.pdf</file>
  </doc>
  <doc>
    <id>7325</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>2019-05-20</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On the Relation between the Extended Supporting Hyperplane Algorithm and Kelley’s Cutting Plane Algorithm</title>
    <abstract language="eng">Recently, Kronqvist et al. (2016) rediscovered the supporting hyperplane algorithm of Veinott (1967) and demonstrated its computational benefits for solving convex mixed-integer nonlinear programs. In this paper we derive the algorithm from a geometric point of view. This enables us to show that the supporting hyperplane algorithm is equivalent to Kelley's cutting plane algorithm applied to a particular reformulation of the problem. As a result, we extend the applicability of the supporting hyperplane algorithm to convex problems represented by general, not necessarily convex, differentiable functions that satisfy a mild condition.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-73253</identifier>
    <author>Felipe Serrano</author>
    <submitter>Felipe Serrano</submitter>
    <author>Robert Schwarz</author>
    <author>Ambros Gleixner</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-18</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="schwarz">Schwarz, Robert</collection>
    <collection role="projects" number="EnBA-M">EnBA-M</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7325/gauge.pdf</file>
  </doc>
  <doc>
    <id>7335</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>2019-05-29</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On the Complexity of the Maximum Minimum Cost Flow Problem</title>
    <abstract language="eng">Consider a flow network, i.e., a directed graph where each arc has a nonnegative capacity and an associated length, together with nonempty supply-intervals for the sources and nonempty demand-intervals for the sinks. The goal of the Maximum Minimum Cost Flow Problem (MMCF) is to find fixed supply and demand values within these intervals, such that the optimal objective value of the induced Minimum Cost Flow Problem (MCF) is maximized. In this paper, we show that MMCF is APX-hard and remains NP-hard in the uncapacitated case.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-73359</identifier>
    <submitter>Kai Hoppmann</submitter>
    <author>Kai Hoppmann</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-19</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="hennig">Hoppmann, Kai</collection>
    <collection role="projects" number="MODAL-GasLab">MODAL-GasLab</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/7335/complexity_paper.pdf</file>
  </doc>
  <doc>
    <id>7496</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>2019-11-06</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Computational Aspects of Infeasibility Analysis in Mixed Integer Programming</title>
    <abstract language="eng">The analysis of infeasible subproblems plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications, obtained by domain propagation, that led to infeasibility. The result of this analysis is one or more sets of contradicting variable bounds from which so-called conflict constraints can be generated. This concept is called conflict graph analysis and has its origin in solving satisfiability problems and is similarly used in constraint programming. The second concept is to analyze infeasible linear programming (LP) relaxations. Every ray of the dual LP provides a set of multipliers that can be used to generate a single new globally valid linear constraint. This method is called dual proof analysis. The main contribution of this paper is twofold. Firstly, we present three enhancements of dual proof analysis: presolving via variable cancellation, strengthening by applying mixed integer rounding functions, and a filtering mechanism. Further, we provide an intense computational study evaluating the impact of every presented component regarding dual proof analysis. Secondly, this paper presents the first integrated approach to use both conflict graph and dual proof analysis simultaneously within a single MIP solution process. All experiments are carried out on general MIP instances from the standard public test set MIPLIB 2017; the presented algorithms have been implemented within the non-commercial MIP solver SCIP and the commercial MIP solver FICO Xpress.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-74962</identifier>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <author>Jakob Witzig</author>
    <submitter>Jakob Witzig</submitter>
    <author>Timo Berthold</author>
    <author>Stefan Heinz</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-54</number>
    </series>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</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="BEAM-ME">BEAM-ME</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/7496/supplement.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/7496/ZR-19-54__Witzig_Berthold_Heinz__Computational_Aspects_of_Infeasibility_Analysis_in_MIP.pdf</file>
  </doc>
  <doc>
    <id>7363</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>1</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2019-06-17</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Optimal Operation of Transient Gas Transport Networks</title>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-73639</identifier>
    <author>Kai Hoppmann</author>
    <submitter>Kai Hoppmann</submitter>
    <author>Felix Hennings</author>
    <author>Ralf Lenz</author>
    <author>Uwe Gotzes</author>
    <author>Nina Heinecke</author>
    <author>Klaus Spreckelsen</author>
    <author>Thorsten Koch</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-23</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="hennig">Hoppmann, Kai</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="persons" number="lenz">Lenz, Ralf</collection>
    <collection role="projects" number="MODAL-GasLab">MODAL-GasLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="enernet">Energy Network Optimization</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7363/Netmodel_Paper.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/7363/Netmodel_Paper_v2.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/7363/Netmodel_Paper_v3.pdf</file>
  </doc>
  <doc>
    <id>7364</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>2019-06-17</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Controlling transient gas flow in real-world pipeline intersection areas</title>
    <abstract language="eng">Compressor stations are the heart of every high-pressure gas transport network. &#13;
Located at intersection areas of the network they are contained in huge complex plants, where they are in combination with valves and regulators responsible for routing and pushing the gas through the network.&#13;
Due to their complexity and lack of data compressor stations are usually dealt with in the scientific literature in a highly simplified and idealized manner.&#13;
As part of an ongoing project with one of Germany's largest Transmission System Operators to develop a decision support system for their dispatching center, we investigated how to automatize control of compressor stations. Each station has to be in a particular configuration, leading in combination with the other nearby elements to a discrete set of up to 2000 possible feasible operation modes in the intersection area.&#13;
Since the desired performance of the station changes over time, the configuration of the station has to adapt.&#13;
Our goal is to minimize the necessary changes in the overall operation modes and related elements over time, while fulfilling a preset performance envelope or demand scenario.&#13;
This article describes the chosen model and the implemented mixed integer programming based algorithms to tackle this challenge.&#13;
By presenting extensive computational results on real world data we demonstrate the performance of our approach.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-73645</identifier>
    <enrichment key="PeerReviewed">no</enrichment>
    <author>Felix Hennings</author>
    <submitter>Felix Hennings</submitter>
    <author>Lovis Anderson</author>
    <author>Kai Hoppmann</author>
    <author>Mark Turner</author>
    <author>Thorsten Koch</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-24</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="hennig">Hoppmann, Kai</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="projects" number="MODAL-GasLab">MODAL-GasLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="enernet">Energy Network Optimization</collection>
    <collection role="persons" number="turner">Turner, Mark Ruben</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7364/ZR_19-24.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/7364/ZR_19-24_v2.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/7364/ZR_19-24_v3.pdf</file>
  </doc>
  <doc>
    <id>7367</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>2019-06-17</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Approximating Balanced Graph Partitions</title>
    <abstract language="eng">We consider the problem of partitioning a weighted graph into k&#13;
connected components of similar weight. In particular, we consider the two classical objectives to maximize the lightest part or to minimize the heaviest part. For a partitioning of the vertex set and for both objectives, we give the first known approximation results on general graphs. Specifically, we give a $\Delta$-approximation where $\Delta$ is the maximum degree of an arbitrary spanning tree of the given graph.&#13;
Concerning the edge partition case, we even obtain a 2-approximation for the min-max and the max-min problem, by using the claw-freeness of line graphs.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-73675</identifier>
    <author>Ralf Borndörfer</author>
    <submitter>Stephan Schwartz</submitter>
    <author>Ziena Elijazyfer</author>
    <author>Stephan Schwartz</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-25</number>
    </series>
    <collection role="msc" number="05-XX">COMBINATORICS (For finite fields, see 11Txx)</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schwartz">Schwartz, Stephan</collection>
    <collection role="projects" number="TOLLCONTROLOPT">TOLLCONTROLOPT</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7367/ZR-19-25.pdf</file>
  </doc>
  <doc>
    <id>7371</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>2019-06-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Prediction of Intermitted Flows in Large Gas Networks</title>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-73717</identifier>
    <author>Inken Gamrath</author>
    <submitter>Inken Gamrath</submitter>
    <author>Milena Petkovic</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-29</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MODAL-GasLab">MODAL-GasLab</collection>
    <collection role="persons" number="inken.gamrath">Gamrath, Inken</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="petkovic">Petkovic, Milena</collection>
    <collection role="institutes" number="enernet">Energy Network Optimization</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7371/Zero_Opt_Prognosis.pdf</file>
  </doc>
  <doc>
    <id>7265</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>2019-02-26</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation</title>
    <abstract language="eng">We propose a simple and general online method to measure the search progress within the Branch-and-Bound algorithm, from which we estimate the size of the remaining search tree. We then show how this information can help solvers algorithmically at runtime by designing a restart strategy for Mixed-Integer Programming (MIP) solvers that decides whether to restart the search based on the current estimate of the number of remaining nodes in the tree. We refer to this type of algorithm as clairvoyant.&#13;
Our clairvoyant restart strategy outperforms a state-of-the-art solver on a large set of publicly available MIP benchmark instances.&#13;
It is implemented in the MIP solver SCIP and will be available in future releases.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-72653</identifier>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <author>Daniel Anderson</author>
    <submitter>Gregor Hendel</submitter>
    <author>Gregor Hendel</author>
    <author>Pierre Le Bodic</author>
    <author>Jan Merlin Viernickel</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-11</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed-Integer Programming solvers</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Restart</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Progress measures</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>tree-size estimates</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="hendel">Hendel, Gregor</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="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7265/zib-report.pdf</file>
  </doc>
  <doc>
    <id>5780</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-03-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Three Enhancements for Optimization-Based Bound Tightening</title>
    <abstract language="eng">Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper is to discuss algorithmic techniques for an efficient implementation of OBBT.&#13;
Most state-of-the-art MINLP solvers apply some restricted version of OBBT and it seems to be common belief that OBBT is beneficial if only one is able to keep its computational cost under control. To this end, we introduce three techniques to increase the efficiency of OBBT: filtering strategies to reduce the number of solved LPs, ordering heuristics to exploit simplex warm starts, and the generation of Lagrangian variable bounds (LVBs). The propagation of LVBs during tree search is a fast approximation to OBBT without the need to solve auxiliary LPs.&#13;
We conduct extensive computational experiments on MINLPLib2. Our results indicate that OBBT is most beneficial on hard instances, for which we observe a speedup of 17% to 19% on average. Most importantly, more instances can be solved when using OBBT.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-57803</identifier>
    <identifier type="doi">10.1007/s10898-016-0450-4</identifier>
    <enrichment key="SourceTitle">Journal of Global Optimization</enrichment>
    <author>Ambros Gleixner</author>
    <submitter>Benjamin Müller</submitter>
    <author>Timo Berthold</author>
    <author>Benjamin Müller</author>
    <author>Stefan Weltge</author>
    <series>
      <title>ZIB-Report</title>
      <number>15-16</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>MINLP</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>optimization-based bound tightening</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>optimality-based bound tightening</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>OBBT</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>propagation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>bound tightening</value>
    </subject>
    <collection role="ccs" number="G.">Mathematics of Computing</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="berthold">Berthold, Timo</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="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/5780/ZR-15-16.pdf</file>
  </doc>
  <doc>
    <id>5937</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-08-05</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework</title>
    <abstract language="eng">This paper describes the extensions that were added to the constraint integer programming framework SCIP in order to enable it to solve convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality.&#13;
SCIP implements a spatial branch-and-bound algorithm based on a linear outer-approximation, which is computed by convex over- and underestimation of nonconvex functions. An expression graph representation of nonlinear constraints allows for bound tightening, structure analysis, and reformulation. Primal heuristics are employed throughout the solving process to find feasible solutions early. We provide insights into the performance impact of individual MINLP solver components via a detailed computational study over a large and heterogeneous test set.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-59377</identifier>
    <identifier type="doi">10.1080/10556788.2017.1335312</identifier>
    <enrichment key="SourceTitle">Optimization Methods &amp; Software</enrichment>
    <author>Stefan Vigerske</author>
    <submitter>Ambros Gleixner</submitter>
    <author>Ambros Gleixner</author>
    <series>
      <title>ZIB-Report</title>
      <number>16-24</number>
    </series>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C26">Nonconvex programming, global optimization</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="vigerske">Vigerske, Stefan</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="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/5937/ZR-16-24.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/5937/ZR-16-24-revised.pdf</file>
  </doc>
  <doc>
    <id>1463</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2012-02-06</completedDate>
    <publishedDate>2012-02-06</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Undercover: a primal MINLP heuristic exploring a largest sub-MIP</title>
    <abstract language="eng">We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programming (MINLP) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a minimal set of variables that need to be fixed in order to linearize each constraint, a so-called cover. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. We apply domain propagation and conflict analysis to try to avoid infeasibilities and learn from them, respectively. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem.&#13;
&#13;
We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and general MINLPs from MINLPLib.  It turns out that the majority of these instances allow for small covers.  Although general in nature, the heuristic appears most promising for MIQCPs, and complements nicely with existing root node heuristics in different state-of-the-art solvers.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="serial">12-07</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-14631</identifier>
    <identifier type="doi">10.1007/s10107-013-0635-2</identifier>
    <enrichment key="SourceTitle">Mathematical Programming</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-14631</enrichment>
    <author>Timo Berthold</author>
    <submitter>Timo Berthold</submitter>
    <author>Ambros Gleixner</author>
    <series>
      <title>ZIB-Report</title>
      <number>12-07</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Primal Heuristic</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed-Integer Nonlinear Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Large Neighborhood Search</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed-Integer   Quadratically Constrained Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Nonconvex Optimization</value>
    </subject>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C20">Quadratic programming</collection>
    <collection role="msc" number="90C26">Nonconvex programming, global optimization</collection>
    <collection role="msc" number="90C30">Nonlinear programming</collection>
    <collection role="msc" number="90C59">Approximation methods and heuristics</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="projects" number="MATHEON-B20">MATHEON-B20</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</collection>
    <collection role="projects" number="Siemens">Siemens</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1463/ZR-12-07.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1463/ZR-12-07_rev.pdf</file>
  </doc>
  <doc>
    <id>7432</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>2019-08-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A massively parallel interior-point solver for linear energy system models with block structure</title>
    <abstract language="eng">Linear energy system models are often a crucial component of system&#13;
design and operations, as well as energy policy consulting. Such models can lead to large-scale linear programs, which can be intractable even for state-of-the-art commercial solvers|already the available memory on a desktop machine might not be sufficient. Against this backdrop, this article introduces an interior-point solver that exploits common structures of&#13;
linear energy system models to efficiently run in parallel on distributed memory systems. The solver is designed for linear programs with doubly bordered&#13;
block-diagonal constraint matrix and makes use of a Schur complement&#13;
based decomposition. Special effort has been put into handling&#13;
large numbers of linking constraints and variables as commonly observed&#13;
in energy system models. In order to handle this strong linkage, a distributed&#13;
preconditioning of the Schur complement is used. In addition, the&#13;
solver features a number of more generic techniques such as parallel matrix&#13;
scaling and structure-preserving presolving. The implementation is&#13;
based on the existing parallel interior-point solver PIPS-IPM. We evaluate&#13;
the computational performance on energy system models with up to 700&#13;
million non-zero entries in the constraint matrix, and with more than 200&#13;
million columns and 250 million rows. This article mainly concentrates on&#13;
the energy system model ELMOD, which is a linear optimization model&#13;
representing the European electricity markets by the use of a nodal pricing&#13;
market clearing. It has been widely applied in the literature on energy&#13;
system analyses during the recent years. However, it will be demonstrated&#13;
that the new solver is also applicable to other energy system models.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-74321</identifier>
    <note>In the meantime, this report got published as a journal article: https://opus4.kobv.de/opus4-zib/frontdoor/index/index/searchtype/authorsearch/author/Hannes+Hobbie/docId/8191/start/1/rows/10&#13;
Please use this journal reference when citing this work.</note>
    <author>Daniel Rehfeldt</author>
    <submitter>Daniel Rehfeldt</submitter>
    <author>Hannes Hobbie</author>
    <author>David Schönheit</author>
    <author>Ambros Gleixner</author>
    <author>Thorsten Koch</author>
    <author>Dominik Möst</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-41</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="persons" number="rehfeldt">Rehfeldt, Daniel</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="BEAM-ME">BEAM-ME</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/7432/ip4energy3.pdf</file>
  </doc>
  <doc>
    <id>5901</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-02-04</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Towards an accurate solution of wireless network design problems</title>
    <abstract language="eng">The optimal design of wireless networks has been widely studied in the literature and many optimization models have been proposed over the years. However, most models directly include the signal-to-interference ratios representing service coverage conditions. This leads&#13;
to mixed-integer linear programs with constraint matrices containing tiny&#13;
coefficients that vary widely in their order of magnitude. These formulations are known to be challenging even for state-of-the-art solvers: the&#13;
standard numerical precision supported by these solvers is usually not sufficient to reliably guarantee feasible solutions. Service coverage errors are thus commonly present. Though these numerical issues are known&#13;
and become evident even for small-sized instances, just a very limited number of papers has tried to tackle them, by mainly investigating alternative non-compact formulations in which the sources of numerical instabilities are eliminated. In this work, we explore a new approach by investigating how recent advances in exact solution algorithms for linear&#13;
and mixed-integer programs over the rational numbers can be applied to analyze and tackle the numerical difficulties arising in wireless network design models.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-59010</identifier>
    <enrichment key="SubmissionStatus">accepted for publication</enrichment>
    <enrichment key="SourceTitle">accepted for publication in Proceedings of the 4th International Symposium on Combinatorial Optimization (ISCO)</enrichment>
    <enrichment key="AcceptedDate">2016-04-11</enrichment>
    <author>Fabio D'Andreagiovanni</author>
    <submitter>Fabio D'Andreagiovanni</submitter>
    <author>Ambros Gleixner</author>
    <series>
      <title>ZIB-Report</title>
      <number>16-12</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="institutes" number="tele">Mathematics of Telecommunication</collection>
    <collection role="projects" number="BMBF-ROBUKOM">BMBF-ROBUKOM</collection>
    <collection role="projects" number="ECMath-MI4">ECMath-MI4</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="VINO">VINO</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/5901/ZR-16-12_DAndreagiovanniGleixner_AccurateWirelessNetworkDesign.pdf</file>
  </doc>
  <doc>
    <id>7408</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>2019-07-26</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method</title>
    <abstract language="eng">In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving reductions are often mathematically simple, their implementation in a high-performance computing environment is a complex endeavor. We report results on impact, performance, and scalability of the resulting presolving routines on real-world energy system models with up to 700 million nonzero entries in the constraint matrix.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-74084</identifier>
    <identifier type="doi">10.1007/978-3-030-48439-2_13</identifier>
    <enrichment key="SourceTitle">Operations Research Proceedings 2019</enrichment>
    <author>Ambros Gleixner</author>
    <submitter>Nils-Christian Kempke</submitter>
    <author>Nils-Christian Kempke</author>
    <author>Thorsten Koch</author>
    <author>Daniel Rehfeldt</author>
    <author>Svenja Uslu</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-39</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>block structure</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>energy system models</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>interior-point method</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>high performance computing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>linear programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>parallelization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>presolving</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>preprocessing</value>
    </subject>
    <collection role="msc" number="90C05">Linear programming</collection>
    <collection role="msc" number="90C06">Large-scale problems</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="persons" number="rehfeldt">Rehfeldt, Daniel</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="BEAM-ME">BEAM-ME</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/7408/ZR-19-39-preprint_revised_pub.pdf</file>
  </doc>
  <doc>
    <id>6629</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>2017-12-21</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The SCIP Optimization Suite 5.0</title>
    <abstract language="eng">This article describes new features and enhanced algorithms made available in version 5.0 of the SCIP Optimization Suite. In its central component, the constraint integer programming solver SCIP, remarkable performance improvements have been achieved for solving mixed-integer linear and nonlinear programs. On MIPs, SCIP 5.0 is about 41 % faster than SCIP 4.0 and over twice as fast on instances that take at least 100 seconds to solve. For MINLP, SCIP 5.0 is about 17 % faster overall and 23 % faster on instances that take at least 100 seconds to solve. This boost is due to algorithmic advances in several parts of the solver such as cutting plane generation and management, a new adaptive coordination of large neighborhood search heuristics, symmetry handling, and strengthened McCormick relaxations for bilinear terms in MINLPs. Besides discussing the theoretical background and the implementational aspects of these developments, the report describes recent additions for the other software packages connected to SCIP, in particular for the LP solver SoPlex, the Steiner tree solver SCIP-Jack, the MISDP solver SCIP-SDP, and the parallelization framework UG.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-66297</identifier>
    <author>Ambros Gleixner</author>
    <submitter>Gregor Hendel</submitter>
    <author>Leon Eifler</author>
    <author>Tristan Gally</author>
    <author>Gerald Gamrath</author>
    <author>Patrick Gemander</author>
    <author>Robert Lion Gottwald</author>
    <author>Gregor Hendel</author>
    <author>Christopher Hojny</author>
    <author>Thorsten Koch</author>
    <author>Matthias Miltenberger</author>
    <author>Benjamin Müller</author>
    <author>Marc Pfetsch</author>
    <author>Christian Puchert</author>
    <author>Daniel Rehfeldt</author>
    <author>Franziska Schlösser</author>
    <author>Felipe Serrano</author>
    <author>Yuji Shinano</author>
    <author>Jan Merlin Viernickel</author>
    <author>Stefan Vigerske</author>
    <author>Dieter Weninger</author>
    <author>Jonas T. Witt</author>
    <author>Jakob Witzig</author>
    <series>
      <title>ZIB-Report</title>
      <number>17-61</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>constraint integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>linear programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed-integer linear programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed-integer nonlinear programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>optimization solver</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branch-and-cut</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branch-and-price</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>column generation framework</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>parallelization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed-integer semidefinite programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Steiner tree optimization</value>
    </subject>
    <collection role="msc" number="65-XX">NUMERICAL ANALYSIS</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="gamrath">Gamrath, Gerald</collection>
    <collection role="persons" number="robert.gottwald">Gottwald, Robert</collection>
    <collection role="persons" number="hendel">Hendel, Gregor</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="persons" number="miltenberger">Miltenberger, Matthias</collection>
    <collection role="persons" number="rehfeldt">Rehfeldt, Daniel</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</collection>
    <collection role="persons" number="vigerske">Vigerske, Stefan</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="persons" number="schloesser">Schlösser, Franziska</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6629/scipopt-50.pdf</file>
  </doc>
  <doc>
    <id>7190</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>2019-02-04</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Concurrent Approach to the Periodic Event Scheduling Problem</title>
    <abstract language="eng">We introduce a concurrent solver for the periodic event scheduling problem (PESP). It combines mixed integer programming techniques, the modulo network simplex method, satisfiability approaches, and a new heuristic based on maximum cuts. Running these components in parallel speeds up the overall solution process. This enables us to significantly improve the current upper and lower bounds for all benchmark instances of the library PESPlib.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-71907</identifier>
    <enrichment key="SubmissionStatus">accepted for publication</enrichment>
    <enrichment key="AcceptedDate">2019-03-22</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Niels Lindner</submitter>
    <author>Niels Lindner</author>
    <author>Sarah Roth</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-07</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic Event Scheduling Problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic Timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed Integer Programming</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="lindner">Lindner, Niels</collection>
    <collection role="projects" number="ECMath-MI7">ECMath-MI7</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7190/concurrent-pesp.pdf</file>
  </doc>
  <doc>
    <id>5640</id>
    <completedYear/>
    <publishedYear>2015</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2015-10-27</completedDate>
    <publishedDate>2015-10-27</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Solving Open MIP Instances with ParaSCIP on Supercomputers using up to 80,000 Cores</title>
    <abstract language="eng">This paper describes how we solved 12 previously unsolved mixed-integer program-&#13;
ming (MIP) instances from the MIPLIB benchmark sets. To achieve these results we&#13;
used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP&#13;
computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper&#13;
we describe the basic parallelization mechanism of ParaSCIP, improvements of the&#13;
dynamic load balancing and novel techniques to exploit the power of parallelization&#13;
for MIP solving. We give a detailed overview of computing times and statistics for&#13;
solving open MIPLIB instances.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-56404</identifier>
    <identifier type="doi">10.1109/IPDPS.2016.56</identifier>
    <enrichment key="SourceTitle">Appeared in: Proc. of 30th IEEE International Parallel &amp; Distributed Processing Symposium</enrichment>
    <submitter>Yuji Shinano</submitter>
    <author>Yuji Shinano</author>
    <author>Tobias Achterberg</author>
    <author>Timo Berthold</author>
    <author>Stefan Heinz</author>
    <author>Thorsten Koch</author>
    <author>Michael Winkler</author>
    <series>
      <title>ZIB-Report</title>
      <number>15-53</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed Integer Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Parallel processing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Node merging</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Racing ParaSCIP</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Ubiquity Generator Framework</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>MIPLIB</value>
    </subject>
    <collection role="ccs" number="D.">Software</collection>
    <collection role="ccs" number="I.">Computing Methodologies</collection>
    <collection role="msc" number="68-XX">COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <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="koch">Koch, Thorsten</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</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="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/5640/ZR-15-53.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/5640/ZR-15-53-rev.pdf</file>
  </doc>
  <doc>
    <id>6551</id>
    <completedYear/>
    <publishedYear>2017</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue>ZIB-Report 17-58</issue>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2017-07-11</completedDate>
    <publishedDate>2017-07-11</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Parallel PIPS-SBB: Multi-Level Parallelism For Stochastic Mixed-Integer Programs</title>
    <abstract language="eng">PIPS-SBB is a distributed-memory parallel solver with a scalable data distribution paradigm. It is designed to solve MIPs with a dual-block angular structure, which is characteristic of deterministic-equivalent Stochastic Mixed-Integer Programs (SMIPs). In this paper, we present two different parallelizations of Branch &amp; Bound (B&amp;B), implementing both as extensions of PIPS-SBB, thus adding an additional layer of parallelism. In the first of the proposed frameworks, PIPS-PSBB, the coordination and load-balancing of the different optimization workers is done in a decentralized fashion. This new framework is designed to ensure all available cores are processing the most promising parts of the B&amp;B tree. The second, ug[PIPS-SBB,MPI], is a parallel implementation using the Ubiquity Generator (UG), a universal framework for parallelizing B&amp;B tree search that has been successfully applied to other MIP solvers. We show the effects of leveraging multiple levels of parallelism in potentially improving scaling performance beyond thousands of cores.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-65517</identifier>
    <identifier type="doi">10.1007/s10589-019-00074-0</identifier>
    <enrichment key="SourceTitle">Computational Optimization and Applications</enrichment>
    <author>Lluis-Miquel Munguia</author>
    <submitter>Yuji Shinano</submitter>
    <author>Geoffrey Oxberry</author>
    <author>Deepak Rajan</author>
    <author>Yuji Shinano</author>
    <series>
      <title>ZIB-Report</title>
      <number>17-58</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>PIPS-SBB, UG, Parallel Branch and Bound</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>psyndex</type>
      <value>PIPS-SBB, UG, Parallel Branch and Bound</value>
    </subject>
    <collection role="ccs" number="G.">Mathematics of Computing</collection>
    <collection role="ccs" number="I.">Computing Methodologies</collection>
    <collection role="pacs" number="00.00.00">GENERAL</collection>
    <collection role="msc" number="68-XX">COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="BEAM-ME">BEAM-ME</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/6551/ZIB-Report-17-58.pdf</file>
  </doc>
  <doc>
    <id>6968</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>2018-07-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable</title>
    <abstract language="eng">We consider the following planning problem in public transportation: Given a&#13;
periodic timetable, how many vehicles are required to operate it?&#13;
In [9], for this sequential approach, it is proposed to first expand the periodic&#13;
timetable over time, and then answer the above question by solving a flow-based&#13;
aperiodic optimization problem.&#13;
In this contribution we propose to keep the compact periodic representation of&#13;
the timetable and simply solve a particular perfect matching problem. For practical&#13;
networks, it is very much likely that the matching problem decomposes into several&#13;
connected components. Our key observation is that there is no need to change any&#13;
turnaround decision for the vehicles of a line during the day, as long as the timetable&#13;
stays exactly the same.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-69688</identifier>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2018.16</identifier>
    <enrichment key="SourceTitle">appeared in: 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Niels Lindner</submitter>
    <author>Marika Karbstein</author>
    <author>Christian Liebchen</author>
    <author>Niels Lindner</author>
    <series>
      <title>ZIB-Report</title>
      <number>18-38</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Vehicle scheduling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Bipartite matching</value>
    </subject>
    <collection role="ccs" number="J.">Computer Applications</collection>
    <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="lindner">Lindner, Niels</collection>
    <collection role="projects" number="ECMath-MI7">ECMath-MI7</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6968/PeriodicVehicleScheduling.pdf</file>
  </doc>
  <doc>
    <id>1405</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2011-09-22</completedDate>
    <publishedDate>2011-09-22</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Hypergraph Model for Railway Vehicle Rotation Planning</title>
    <abstract language="eng">We propose a model for the integrated optimization of vehicle&#13;
  rotations and vehicle compositions in long distance railway passenger&#13;
  transport. The main contribution of the paper is a hypergraph model&#13;
  that is able to handle the challenging technical requirements as&#13;
  well as very general stipulations with respect to the ``regularity''&#13;
  of a schedule. The hypergraph model directly generalizes network&#13;
  flow models, replacing arcs with hyperarcs. Although NP-hard in&#13;
  general, the model is computationally well-behaved in practice.  High&#13;
  quality solutions can be produced in reasonable time using high&#13;
  performance Integer Programming techniques, in particular, column&#13;
  generation and rapid branching. We show that, in this way,&#13;
  large-scale real world instances of our cooperation partner DB&#13;
  Fernverkehr can be solved.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="serial">11-36</identifier>
    <identifier type="doi">/10.4230/OASIcs.ATMOS.2011.146</identifier>
    <identifier type="urn">urn:nbn:de:0030-drops-32746</identifier>
    <enrichment key="SourceTitle">Appeared in: 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Alberto Caprara and Spyros Kontogiannis (eds.) 2011, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, ISBN 978-3-939897-33-0, pp. 146-155, OpenAccess Series in Informatics (OASIcs), 20</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Thomas Schlechte</submitter>
    <author>Markus Reuther</author>
    <author>Thomas Schlechte</author>
    <author>Steffen Weider</author>
    <series>
      <title>ZIB-Report</title>
      <number>11-36</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Rolling Stock Planning, Hypergraph Modeling, Integer Programming,    Column Generation, Rapid Branching</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="schlechte">Schlechte, Thomas</collection>
    <collection role="persons" number="weider">Weider, Steffen</collection>
    <collection role="projects" number="MATHEON-B22">MATHEON-B22</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="ROTOR">ROTOR</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1405/ZR-11-36.pdf</file>
  </doc>
  <doc>
    <id>7119</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>2018-12-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Local Rapid Learning for Integer Programs</title>
    <abstract language="eng">Conflict learning algorithms are an important component of modern MIP and CP solvers. But strong conflict information is typically gained by depth-first search. While this is the natural mode for CP solving, it is not for MIP solving. Rapid Learning is a hybrid CP/MIP approach where CP search is applied at the root to learn information to support the remaining MIP solve. This has been demonstrated to be beneficial for binary programs. In this paper, we extend the idea of Rapid Learning to integer programs, where not all variables are restricted to the domain {0, 1}, and rather than just running a rapid CP search at the root, we will apply it repeatedly at local search nodes within the MIP search tree. To do so efficiently, we present six heuristic criteria to predict the chance for local Rapid Learning to be successful. Our computational experiments indicate that our extended Rapid Learning algorithm significantly speeds up MIP search and is particularly beneficial on highly dual degenerate problems.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-71190</identifier>
    <author>Timo Berthold</author>
    <submitter>Jakob Witzig</submitter>
    <author>Peter Stuckey</author>
    <author>Jakob Witzig</author>
    <series>
      <title>ZIB-Report</title>
      <number>18-56</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="berthold">Berthold, Timo</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="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7119/ZR-18-56-revised.pdf</file>
  </doc>
  <doc>
    <id>7116</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>2018-12-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Adaptive Large Neighborhood Search for Mixed Integer Programming</title>
    <abstract language="eng">Large Neighborhood Search (LNS) heuristics are among the most powerful but also most expensive heuristics for mixed integer programs (MIP). Ideally, a solver learns adaptively which LNS heuristics work best for the MIP problem at hand in order to concentrate its limited computational budget.&#13;
&#13;
To this end, this work introduces Adaptive Large Neighborhood Search (ALNS) for MIP, a primal heuristic that acts a framework for eight popular LNS heuristics such as Local Branching and Relaxation Induced Neighborhood Search (RINS). We distinguish the available LNS heuristics by their individual search domains, which we call neighborhoods. The decision which neighborhood should be executed is guided by selection strategies for the multi armed bandit problem, a related optimization problem during which suitable actions have to be chosen to maximize a reward function. In this paper, we propose an LNS-specific reward function to learn to distinguish between the available neighborhoods based on successful calls and failures. A second, algorithmic enhancement is a generic variable fixing priorization, which ALNS employs to adjust the subproblem complexity as needed. This is particularly useful for some neighborhoods which do not fix variables by themselves. The proposed primal heuristic has been implemented&#13;
within the MIP solver SCIP. An extensive computational study is conducted to compare different LNS strategies within our ALNS framework on a large set of publicly available MIP instances from the MIPLIB and Coral benchmark sets. The results of this simulation are used to calibrate the parameters of the bandit selection strategies. A second computational experiment shows the computational benefits of the proposed ALNS framework within the MIP solver SCIP.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-71167</identifier>
    <author>Gregor Hendel</author>
    <submitter>Gregor Hendel</submitter>
    <series>
      <title>ZIB-Report</title>
      <number>18-60</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>primal heuristics</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>large neighborhood search</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>multi armed bandit problem</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="hendel">Hendel, Gregor</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="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7116/adaptive-lns-master.pdf</file>
  </doc>
  <doc>
    <id>7117</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>2018-12-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Status Report on Conflict Analysis in Mixed Integer Nonlinear Programming</title>
    <abstract language="eng">Mixed integer nonlinear programs (MINLPs) are arguably among the hardest optimization problems, with a wide range of applications. MINLP solvers that are based on linear relaxations and spatial branching work similar as mixed integer programming (MIP) solvers in the sense that they are based on a branch-and-cut algorithm, enhanced by various heuristics, domain propagation, and presolving techniques. However, the analysis of infeasible subproblems, which is an important component of most major MIP solvers, has been hardly studied in the context of MINLPs. There are two main approaches for infeasibility analysis in MIP solvers: conflict graph analysis, which originates from artificial intelligence and constraint programming, and dual ray analysis.&#13;
The main contribution of this short paper is twofold. Firstly, we present the first computational study regarding the impact of dual ray analysis on convex and nonconvex MINLPs. In that context, we introduce a modified generation of infeasibility proofs that incorporates linearization cuts that are only locally valid. Secondly, we describe an extension of conflict analysis that works directly with the nonlinear relaxation of convex MINLPs instead of considering a linear relaxation. This is work-in-progress, and this short paper is meant to present first theoretical considerations without a computational study for that part.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-71170</identifier>
    <author>Jakob Witzig</author>
    <submitter>Jakob Witzig</submitter>
    <author>Timo Berthold</author>
    <author>Stefan Heinz</author>
    <series>
      <title>ZIB-Report</title>
      <number>18-57</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</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="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7117/ZR-18-57-revised.pdf</file>
  </doc>
  <doc>
    <id>7133</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>2019-01-09</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Rolling Stock Rotation Planning Problem under Revenue Considerations</title>
    <abstract language="eng">In many railway undertakings a railway timetable is offered that is valid for a longer period of time. At DB Fernverkehr AG, one of our industrial partners, this results in a summer and a winter timetable. For both of these timetables rotation plans, i.e., a detailed plan of railway vehicle movements is constructed as a template for this period.  Sometimes there are be periods where you know for sure that vehicle capacities are not sufficient to cover all trips of the timetable or to transport all passenger of the trips. Reasons for that could be a heavy increase of passenger flow, a heavy decrease of vehicle availability, impacts from nature, or even strikes of some employees. In such events the rolling stock rotations have to be adapted. Optimization methods are particularly valuable in such situations in order to maintain a best possible level of service or to maximize the expected revenue using the resources that are still available. In most cases found in the literature, a rescheduling based on a timetable update is done, followed by the construction of new rotations that reward the recovery of parts of the obsolete rotations. We consider a different, novel, and more integrated approach. The idea is to guide the cancellation of the trips or reconfiguration of the vehicle composition used to operate a trip of the timetable by the rotation planning process, which is based on the mixed integer programming approach presented in Reuther (2017). The goal is to minimize the operating costs while cancelling or operating a trip with an insufficient vehicle configuration in sense of passenger capacities inflicts opportunity costs and loss of revenue, which are based on an estimation of the expected number of passengers. The performance of the algorithms presented in two case studies, including real world scenarios from DB Fernverkehr AG and a railway operator in North America.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-71339</identifier>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <author>Boris Grimm</author>
    <submitter>Boris Grimm</submitter>
    <author>Ralf Borndörfer</author>
    <author>Christof Schulz</author>
    <author>Steffen Weider</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-01</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schulz">Schulz, Christof</collection>
    <collection role="persons" number="weider">Weider, Steffen</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</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/7133/ZR-19-01.pdf</file>
  </doc>
  <doc>
    <id>7114</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>2018-12-13</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Tight Cut Decomposition of Matching Covered Uniformable Hypergraphs</title>
    <abstract language="eng">The perfect matching polytope, i.e. the convex hull of (incidence vectors of) perfect matchings of a graph is used in many combinatorial algorithms. Kotzig, Lovász and Plummer developed a decomposition theory for graphs with perfect matchings and their corresponding polytopes known as the tight cut decomposition which breaks down every graph into a number of indecomposable graphs, so called bricks. For many properties that are of interest on graphs with perfect matchings, including the description of the perfect matching polytope, it suffices to consider these bricks. A key result by Lovász on the tight cut decomposition is that the list of bricks obtained is the same independent of the choice of tight cuts made during the tight cut decomposition procedure. This implies that finding a tight cut decomposition is polynomial time equivalent to finding a single tight cut.&#13;
		&#13;
We generalise the notions of a tight cut, a tight cut contraction and a tight cut decomposition to hypergraphs. By providing an example, we show that the outcome of the tight cut decomposition on general hypergraphs is no longer unique. However, we are able to prove that the uniqueness of the tight cut decomposition is preserved on a slight generalisation of uniform hypergraphs. Moreover, we show how the tight cut decomposition leads to a decomposition of the perfect matching polytope of uniformable hypergraphs and that the recognition problem for tight cuts in uniformable hypergraphs is polynomial time solvable.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-71149</identifier>
    <author>Isabel Beckenbach</author>
    <submitter>Isabel Beckenbach</submitter>
    <author>Meike Hatzel</author>
    <author>Sebastian Wiederrecht</author>
    <series>
      <title>ZIB-Report</title>
      <number>18-61</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>uniform hypergraphs</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>perfect matchings</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>tight cuts</value>
    </subject>
    <collection role="msc" number="05C65">Hypergraphs</collection>
    <collection role="msc" number="05C70">Factorization, matching, partitioning, covering and packing</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="beckenbach">Beckenbach, Isabel</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</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/7114/ms.pdf</file>
  </doc>
  <doc>
    <id>7095</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>2018-11-21</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Reduction-based exact solution of prize-collecting Steiner tree problems</title>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-70958</identifier>
    <author>Daniel Rehfeldt</author>
    <submitter>Daniel Rehfeldt</submitter>
    <author>Thorsten Koch</author>
    <series>
      <title>ZIB-Report</title>
      <number>18-55</number>
    </series>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="persons" number="rehfeldt">Rehfeldt, Daniel</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="BEAM-ME">BEAM-ME</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/7095/pcstpZIB.pdf</file>
  </doc>
  <doc>
    <id>7111</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>2018-12-07</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Building Optimal Steiner Trees on Supercomputers by using up to 43,000 Cores</title>
    <abstract language="eng">SCIP-JACK is a customized, branch-and-cut based solver for Steiner tree and related problems. ug [SCIP-JACK, MPI] extends SCIP-JACK to a massively par- allel solver by using the Ubiquity Generator (UG) framework. ug [SCIP-JACK, MPI] was the only solver that could run on a distributed environment at the (latest) 11th DIMACS Challenge in 2014. Furthermore, it could solve three well-known open instances and updated 14 best known solutions to instances from the bench- mark libary STEINLIB. After the DIMACS Challenge, SCIP-JACK has been con- siderably improved. However, the improvements were not reflected on ug [SCIP- JACK, MPI]. This paper describes an updated version of ug [SCIP-JACK, MPI], especially branching on constrains and a customized racing ramp-up. Furthermore, the different stages of the solution process on a supercomputer are described in detail. We also show the latest results on open instances from the STEINLIB.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-71118</identifier>
    <author>Yuji Shinano</author>
    <submitter>Yuji Shinano</submitter>
    <author>Daniel Rehfeldt</author>
    <author>Thorsten Koch</author>
    <series>
      <title>ZIB-Report</title>
      <number>18-58</number>
    </series>
    <collection role="ccs" number="I.">Computing Methodologies</collection>
    <collection role="msc" number="68-XX">COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="persons" number="rehfeldt">Rehfeldt, Daniel</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</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/7111/ZIB-Report-18-58.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/7111/ZIB-Report-18-58-rev.pdf</file>
  </doc>
  <doc>
    <id>7110</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>2018-12-07</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Intersection cuts for factorable MINLP</title>
    <abstract language="eng">Given a factorable function f, we propose a procedure that constructs a concave underestimor of f that is tight at a given point. These underestimators can be used to generate intersection cuts. A peculiarity of these underestimators is that they do not rely on a bounded domain. We propose a strengthening procedure for the intersection cuts that exploits the bounds of the domain. Finally, we propose an extension of monoidal strengthening to take advantage of the integrality of the non-basic variables.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-71105</identifier>
    <enrichment key="SourceTitle">Accepted in: A. Lodi, ed., Integer Programming and Combinatorial Optimization: 20th International Conference, IPCO 2019</enrichment>
    <author>Felipe Serrano</author>
    <submitter>Felipe Serrano</submitter>
    <series>
      <title>ZIB-Report</title>
      <number>18-59</number>
    </series>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</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="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7110/intercuts.pdf</file>
  </doc>
  <doc>
    <id>6967</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2018-07-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Kombilösung: Optimierung des Liniennetzes in Karlsruhe</title>
    <abstract language="deu">Wir beschreiben die Optimierung des Nahverkehrsnetzes der Stadt Karlsruhe im Zusammmenhang mit den Baumaßnahmen der sogenannten Kombilösung.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-69677</identifier>
    <enrichment key="SourceTitle">Der Nahverkehr 1-2, p. 33-38, 2019</enrichment>
    <enrichment key="AcceptedDate">07.11.2018</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Ralf Borndörfer</submitter>
    <author>Ascan Egerer</author>
    <author>Marika Karbstein</author>
    <author>Ralf Messerschmidt</author>
    <author>Marc Perez</author>
    <author>Steven Pfisterer</author>
    <author>Petra Strauß</author>
    <series>
      <title>ZIB-Report</title>
      <number>18-45</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>ÖPNV</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Linienplanung</value>
    </subject>
    <collection role="ccs" number="G.">Mathematics of Computing</collection>
    <collection role="pacs" number="00.00.00">GENERAL</collection>
    <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="projects" number="ECMath-MI3">ECMath-MI3</collection>
    <collection role="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</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/6967/ZR-18-45.pdf</file>
  </doc>
  <doc>
    <id>7768</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>2020-03-01</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Efficient Enumeration of Acyclic Graph Orientations with Sources or Sinks Revisited</title>
    <abstract language="eng">In a recent paper, Conte et al. [CGMR2017] presented an algorithm for enumerating all acyclic orientations of a graph G=(V,E) with a single source (and related orientations) with delay O(|V||E|). In this paper we revisit the problem by going back to an early paper by de Fraysseix et al. [FMR1995], who proposed an algorithm for enumerating all bipolar orientations of a graph based on a recursion formula. We first formalize de Fraysseix et al.'s algorithm for bipolar orientations and determine that its delay is also O(|V||E|). We then apply their recursion formula to the case of Conte et al.'s enumeration problem and show that this yields a more efficient enumeration algorithm with delay O(\sqrt(|V|)|E|). Finally, a way to further streamline the algorithm that leads to a particularly simple implementation is suggested.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-77684</identifier>
    <author>Kai-Helge Becker</author>
    <submitter>Benjamin Hiller</submitter>
    <author>Benjamin Hiller</author>
    <series>
      <title>ZIB-Report</title>
      <number>20-05</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>acyclic orientations</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>enumeration algorithm</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>multiple sources and sinks</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>bipolar orientations</value>
    </subject>
    <collection role="ccs" number="J.">Computer Applications</collection>
    <collection role="msc" number="05-XX">COMBINATORICS (For finite fields, see 11Txx)</collection>
    <collection role="msc" number="68-XX">COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MODAL-GasLab">MODAL-GasLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="projects" number="ECMATH-MI10">ECMATH-MI10</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7768/ZR-20-05-pdf</file>
  </doc>
  <doc>
    <id>7702</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>2020-02-11</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Solution Approach to the Vehicle Routing Problem with Perishable Goods</title>
    <abstract language="eng">This paper focuses on a special case of vehicle routing problem where perishable goods are considered. Deliveries have to be performed until a due date date, which may vary for different products. Storing products is prohibited.&#13;
Since late deliveries have a direct impact on the revenues for these products, a precise demand prediction is important. In our practical case the product demands and vehicle driving times for the product delivery are dependent on weather conditions, i.e., temperatures, wind, and precipitation. In this paper the definition and a solution approach to the Vehicle Routing Problem with Perishable Goods is presented. The approach includes a procedure how historical weather data is used to predict demands and driving times. Its run time and solution quality is evaluated on different data sets given by the MOPTA Competition 2018.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-77020</identifier>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <author>Boris Grimm</author>
    <submitter>Boris Grimm</submitter>
    <author>Ralf Borndörfer</author>
    <author>Mats Olthoff</author>
    <series>
      <title>ZIB-Report</title>
      <number>20-03</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</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/7702/ZR-20-03.pdf</file>
  </doc>
  <doc>
    <id>7517</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>2019-11-27</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming</title>
    <abstract language="eng">The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solver can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In this work, we exploit this fact and make use of a nonconvex relaxation obtained via aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in an MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm’s ability to generate strong dual bounds through extensive computational experiments.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-75179</identifier>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <author>Benjamin Müller</author>
    <submitter>Benjamin Müller</submitter>
    <author>Gonzalo Muñoz</author>
    <author>Maxime Gasse</author>
    <author>Ambros Gleixner</author>
    <author>Andrea Lodi</author>
    <author>Felipe Serrano</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-55</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>surrogate relaxation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>MINLP</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>nonconvex optimization</value>
    </subject>
    <collection role="ccs" number="G.">Mathematics of Computing</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <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="Siemens">Siemens</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="projects" number="EnBA-M">EnBA-M</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7517/ZR-19-55.pdf</file>
  </doc>
  <doc>
    <id>7531</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>2019-11-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Linear Programming using Limited-Precision Oracles</title>
    <abstract language="eng">Since the elimination algorithm of Fourier and Motzkin, many different methods have been developed for solving linear programs. When analyzing the time complexity of LP algorithms, it is typically either assumed that calculations are performed exactly and bounds are derived on the number of elementary arithmetic operations necessary, or the cost of all arithmetic operations is considered through a bit-complexity analysis. Yet in practice, implementations typically use limited-precision arithmetic. In this paper we introduce the idea of a limited-precision LP oracle and study how such an oracle could be used within a larger framework to compute exact precision solutions to LPs. Under mild assumptions, it is shown that a polynomial number of calls to such an oracle and a polynomial number of bit operations, is sufficient to compute an exact solution to an LP. This work provides a foundation for understanding and analyzing the behavior of the methods that are currently most effective in practice for solving LPs exactly.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="doi">10.1007/s10107-019-01444-6</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-75316</identifier>
    <enrichment key="SourceTitle">Mathematical Programming, 2019</enrichment>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <author>Ambros Gleixner</author>
    <submitter>Ambros Gleixner</submitter>
    <author>Daniel Steffy</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-57</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</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="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7531/ZR-19-57.pdf</file>
  </doc>
  <doc>
    <id>6836</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>2018-04-10</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Feature-Based Algorithm Selection for Mixed Integer Programming</title>
    <abstract language="eng">Mixed integer programming is a versatile and valuable optimization tool. However, solving specific problem instances can be computationally demanding even for cutting-edge solvers. Such long running times are often significantly reduced by an appropriate change of the solver's parameters. In this paper we investigate "algorithm selection", the task of choosing among a set of algorithms the ones that are likely to perform best for a particular instance. &#13;
&#13;
In our case, we treat different parameter settings of the MIP solver SCIP as different algorithms to choose from. Two peculiarities of the MIP solving process have our special attention. We address the well-known problem of performance variability by using multiple random seeds. Besides solving time, primal dual integrals are recorded as a second performance measure in order to distinguish solvers that timed out.&#13;
&#13;
We collected feature and performance data for a large set of publicly available MIP instances. The algorithm selection problem is addressed by several popular, feature-based methods, which have been partly extended for our purpose. Finally, an analysis of the feature space and performance results of the selected algorithms are presented.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-68362</identifier>
    <author>Alexander Georges</author>
    <submitter>Gregor Hendel</submitter>
    <author>Ambros Gleixner</author>
    <author>Gorana Gojic</author>
    <author>Robert Lion Gottwald</author>
    <author>David Haley</author>
    <author>Gregor Hendel</author>
    <author>Bartlomiej Matejczyk</author>
    <series>
      <title>ZIB-Report</title>
      <number>18-17</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>algorithm selection</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed integer programming</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="robert.gottwald">Gottwald, Robert</collection>
    <collection role="persons" number="hendel">Hendel, Gregor</collection>
    <collection role="projects" number="ASTfSCM">ASTfSCM</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="Siemens">Siemens</collection>
    <collection role="projects" number="BEAM-ME">BEAM-ME</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/6836/main.pdf</file>
  </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>8974</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-31</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Introducing TimPassLib - A library for integrated periodic timetabling and passenger routing</title>
    <abstract language="eng">Classic models to derive a timetable for public transport often face a chicken-and-egg situation: A good timetable should offer passengers routes with small travel times, but the route choice of passengers depends on the timetable. While models that fix passenger routes were frequently considered in the literature, integrated models that simultaneously optimize timetables and passenger routes have seen increasing attention lately. This creates a growing need for a set of instances that allows to test and compare new algorithmic developments for the integrated problem. Our paper addresses this requirement by presenting TimPassLib, a new benchmark library of instances for integrated periodic timetabling and passenger routing.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-89741</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <author>Philine Schiewe</author>
    <submitter>Niels Lindner</submitter>
    <author>Marc Goerigk</author>
    <author>Niels Lindner</author>
    <series>
      <title>ZIB-Report</title>
      <number>23-06</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>periodic timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>optimization in public transport</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>data sets</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>benchmarking</value>
    </subject>
    <collection role="ccs" number="J.">Computer Applications</collection>
    <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="lindner">Lindner, Niels</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="MathPlus-AA3-8">MathPlus-AA3-8</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8974/ZR-23-06.pdf</file>
  </doc>
  <doc>
    <id>6450</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>2017-07-14</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On the performance of NLP solvers within global MINLP solvers</title>
    <abstract language="eng">Solving mixed-integer nonlinear programs (MINLPs) to global optimality efficiently requires fast solvers for continuous sub-problems. These appear in, e.g., primal heuristics, convex relaxations, and bound tightening methods. Two of the best performing algorithms for these sub-problems are Sequential Quadratic Programming (SQP) and Interior Point Methods. In this paper we study the impact of different SQP and Interior Point implementations on important MINLP solver components that solve a sequence of similar NLPs. We use the constraint integer programming framework SCIP for our computational studies.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-64504</identifier>
    <identifier type="doi">10.1007/978-3-319-89920-6_84</identifier>
    <enrichment key="SourceTitle">Operations Research Proceedings 2017</enrichment>
    <author>Benjamin Müller</author>
    <submitter>Benjamin Müller</submitter>
    <author>Renke Kuhlmann</author>
    <author>Stefan Vigerske</author>
    <series>
      <title>ZIB-Report</title>
      <number>17-35</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="vigerske">Vigerske, Stefan</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="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6450/ZR-17-35.pdf</file>
  </doc>
  <doc>
    <id>8906</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-12-15</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Cutting Plane Selection with Analytic Centers and Multiregression</title>
    <abstract language="eng">Cutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation.  We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-89065</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <author>Mark Turner</author>
    <submitter>Mark Turner</submitter>
    <author>Timo Berthold</author>
    <author>Mathieu Besançon</author>
    <author>Thorsten Koch</author>
    <series>
      <title>ZIB-Report</title>
      <number>22-28</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>cut selection</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>anlalytic center</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed-integer programming</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="berthold">Berthold, Timo</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="turner">Turner, Mark Ruben</collection>
    <collection role="institutes" number="aim">Applied Algorithmic Intelligence Methods</collection>
    <collection role="projects" number="MODAL-EnergyLab">MODAL-EnergyLab</collection>
    <collection role="projects" number="UNSEEN">UNSEEN</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8906/Analytic_Center_Cut_Selection_ZIB.pdf</file>
  </doc>
  <doc>
    <id>1163</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2009-12-16</completedDate>
    <publishedDate>2009-12-16</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Undercover – a primal heuristic for MINLP based on sub-MIPs generated by set covering</title>
    <abstract language="eng">We present Undercover, a primal heuristic for mixed-integer nonlinear programming (MINLP). The heuristic constructs a mixed-integer linear subproblem (sub-MIP) of a given MINLP by fixing a subset of the variables. We solve a set covering problem to identify a minimal set of variables which need to be fixed in order to linearise each constraint. Subsequently, these variables are fixed to approximate values, e.g. obtained from a linear outer approximation. The resulting sub-MIP is solved by a mixed-integer linear programming solver. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. Although general in nature, the heuristic seems most promising for mixed-integer quadratically constrained programmes (MIQCPs). We present computational results on a general test set of MIQCPs selected from the MINLPLib.</abstract>
    <identifier type="serial">09-40</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1222</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11632</identifier>
    <enrichment key="SourceTitle">App. in: Proceedings of the EWMINLP. Pierre Bonami et al. eds. 2010, pp. 103-112</enrichment>
    <author>Timo Berthold</author>
    <submitter>unknown unknown</submitter>
    <author>Ambros Gleixner</author>
    <series>
      <title>ZIB-Report</title>
      <number>09-40</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>MINLP</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>MIQCP</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Primalheuristik</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Nachbarschaftssuche</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Mengenüberdeckung</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed-integer nonlinear programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>MIQCP</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>primal heuristic</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>large neighborhood search</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>set covering</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="ccs" number="G.1.6">Optimization</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C30">Nonlinear programming</collection>
    <collection role="msc" number="90C59">Approximation methods and heuristics</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="projects" number="MATHEON-B20">MATHEON-B20</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</collection>
    <collection role="projects" number="Siemens">Siemens</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1163/ZR_09_40_rev2.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1163/ZR_09_40.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1163/ZR_09_40_rev2.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1163/ZR_09_40.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1163/ZR_09_40_rev3.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1163/ZR_09_40_rev3.ps</file>
  </doc>
  <doc>
    <id>8851</id>
    <completedYear/>
    <publishedYear>2022</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-29</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Using Multiple Reference Vectors and Objective Scaling in the Feasibility Pump</title>
    <abstract language="deu">The Feasibility Pump (FP) is one of the best-known primal heuristics for mixed-integer programming (MIP): more than 15 papers suggested various modifications of all of its steps. So far, no variant considered information across multiple iterations, but all instead maintained the principle to optimize towards a single reference integer point. In this paper, we evaluate the usage of multiple reference vectors in all stages of the FP algorithm. In particular, we use LP-feasible vectors obtained during the main loop to tighten the variable domains before entering the computationally expensive enumeration stage. Moreover, we consider multiple integer reference vectors to explore further optimizing directions and introduce alternative objective scaling terms to balance the contributions of the distance functions and the original MIP objective. Our computational experiments demonstrate that the new method can improve performance on general MIP test sets. In detail, our modifications provide a 29.3% solution quality improvement and 4.0% running time improvement in an embedded setting, needing 16.0% fewer iterations over a large test set of MIP instances. In addition, the method’s success rate increases considerably within the first few iterations. In a standalone setting, we also observe a moderate performance improvement, which makes our version of FP suitable for the two main use-cases of the algorithm.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-88513</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <author>Timo Berthold</author>
    <submitter>Gioni Mexi</submitter>
    <author>Gioni Mexi</author>
    <author>Domenico Salvagnin</author>
    <series>
      <title>ZIB-Report</title>
      <number>22-14</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="mexi">Mexi, Gioni</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8851/ZIB-Report-22-14.pdf</file>
  </doc>
  <doc>
    <id>1763</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2013-10-01</completedDate>
    <publishedDate>2013-10-01</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Learning and Propagating Lagrangian Variable Bounds for Mixed-Integer Nonlinear Programming</title>
    <abstract language="eng">Optimization-based bound tightening (OBBT) is a domain reduction technique commonly used in nonconvex mixed-integer nonlinear programming that solves a sequence of auxiliary linear programs. Each variable is minimized and maximized to obtain the tightest bounds valid for a global linear relaxation. This paper shows how the dual solutions of the auxiliary linear programs can be used to learn what we call Lagrangian variable bound constraints.  These are linear inequalities that explain OBBT's domain reductions in terms of the bounds on other variables and the objective value of the incumbent solution. Within a spatial branch-and-bound algorithm, they can be learnt a priori (during OBBT at the root node) and propagated within the search tree at very low computational cost. Experiments with an implementation inside the MINLP solver SCIP show that this reduces the number of branch-and-bound nodes and speeds up solution times.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-17631</identifier>
    <identifier type="doi">10.1007/978-3-642-38171-3_26</identifier>
    <enrichment key="SourceTitle">Appeared in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013</enrichment>
    <author>Ambros Gleixner</author>
    <submitter>Ambros Gleixner</submitter>
    <author>Stefan Weltge</author>
    <series>
      <title>ZIB-Report</title>
      <number>13-04</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>MINLP</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>optimization-based bound tightening</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>optimality-based bound tightening</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>OBBT</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>propagation</value>
    </subject>
    <collection role="msc" number="90C26">Nonconvex programming, global optimization</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MATHEON-B20">MATHEON-B20</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</collection>
    <collection role="projects" number="Siemens">Siemens</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1763/ZR-13-04.pdf</file>
  </doc>
</export-example>
