<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>5715</id>
    <completedYear/>
    <publishedYear>2016</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>3</pageFirst>
    <pageLast>9</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Exploiting Solving Phases for Mixed-Integer Programs</title>
    <abstract language="eng">Modern MIP solving software incorporates dozens of auxiliary algorithmic components for supporting the branch-and-bound search in finding and improving solutions and in strengthening the relaxation. Intuitively, a dynamic solving strategy with an appropriate emphasis on different solving components and strategies is desirable during the search process. We propose an adaptive solver behavior that dynamically reacts on transitions between the three typical phases of a MIP solving process: The first phase objective is to find a feasible solution. During the second phase, a sequence of incumbent solutions gets constructed until the incumbent is eventually optimal. Proving optimality is the central objective of the remaining third phase. Based on the MIP-solver SCIP, we demonstrate the usefulness of the phase concept both with an exact recognition of the optimality of a solution, and provide heuristic alternatives to make use of the concept in practice.</abstract>
    <parentTitle language="eng">Operations Research Proceedings 2015</parentTitle>
    <identifier type="doi">10.1007/978-3-319-42902-1_1</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-57098</enrichment>
    <author>Gregor Hendel</author>
    <submitter>Gregor Hendel</submitter>
    <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="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>1332</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber>95</pageNumber>
    <edition/>
    <issue/>
    <volume/>
    <type>bachelorthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2011-07-13</completedDate>
    <publishedDate>2011-07-13</publishedDate>
    <thesisDateAccepted>2011-05-10</thesisDateAccepted>
    <title language="eng">New Rounding and Propagation Heuristics for Mixed Integer Programming</title>
    <abstract language="deu">Die vorliegende Arbeit befasst sich mit Primalheuristiken für gemischt-ganzzahlige, lineare Optimierungsprobleme (engl.: mixed integer program MIP).&#13;
    Zahlreiche Optimierungsprobleme aus der Praxis lassen sich als MIP modellieren, Beispiele hierfür sind u. a.&#13;
    Optimierungsprobleme &#13;
    im öffentlichen Nah- und Fernverkehr, bei logistischen Fragestellungen oder im Bereich der Chip-Verifikation.&#13;
&#13;
Das Lösen von MIP ist NP-schwer und wird heutzutage meistens mit Hilfe von Branch-and-Bound-basierenden&#13;
    Algorithmen versucht. Das Branch-and-Bound-Ver\-fah\-ren profitiert unter Umständen von bereits frühzeitig&#13;
    zur Verfügung stehenden Lösungen, daher        &#13;
    sind wir sehr an heuristischen Verfahren interessiert, die in der Praxis schnell eine gute Lösung für eine große Zahl an&#13;
    MIPs  liefern und somit die Lösezeit des Branch-and-Bound-Verfahrens erheblich beschleunigen können. &#13;
     &#13;
    Primalheuristiken sind Suchverfahren zum Auffinden zulässiger Lösungen eines MIP. Verschiedene Typen von Primalheuristiken&#13;
    sollen dabei den jeweiligen Bedarf des Anwenders zu unterschiedlichen Zeiten während der Branch-and-Bound-Suche decken. Während Start- und&#13;
    Rundeheuristiken zu Beginn des Löseprozesses eine große Rolle bei der Suche nach der ersten zulässigen Lösung&#13;
    haben, arbeiten Verbesserungs-heuristiken auf schon bekannten Lösungen, um neue, bessere Lösungen zu produzieren.&#13;
    &#13;
    Diese Arbeit beschäftigt sich mit Primalheuristiken, welche Teil des MIP-Lösers SCIP sind. Im ersten Kapitel werden&#13;
    nach der Erarbeitung grundlegender Definitionen viele der durch Tobias Achterberg und Timo Berthold in SCIP integrierten&#13;
    heuristischen Verfahren vorgestellt und kategorisiert. Auf dieser Grundlage bauen dann die &#13;
    Kapitel 2-4 der Arbeit auf. In diesen werden drei zusätzliche Heuristiken vorgestellt, &#13;
    im Einzelnen sind dies ZI Round, eine Rundeheuristik, welche zuerst von Wallace beschrieben wurde, außerdem eine &#13;
    2-Opt-Heuristik für MIP und eine neue Startheuristik, Shift-And-Propagate.&#13;
    &#13;
    Großer Wert wird in jedem Kapitel auf die algorithmische Beschreibung der Heuristiken gelegt, die stets anhand von motivierenden&#13;
    Beispielen eingeführt und anhand von Pseudocode-Algorithmen begleitet werden. Zusätzlich enthält jedes Kapitel Auswertungen der&#13;
    mit den neuen Heuristiken gemessenen Ergebnisse von SCIP.&#13;
     Eine kurze Zusammenfassung in Kapitel 5 schließt diese Arbeit ab.</abstract>
    <abstract language="eng">Many practically relevant problems can be formulated in terms of a mixed integer programming (MIP) model. MIP denotes the &#13;
     optimization of a linear objective function under a certain number of linear side constraints including the need for&#13;
     some of the involved variables to take integral solution values.&#13;
     Applications of MIP based optimization can be found in the area of public transit,&#13;
     scheduling, automatic vehicle routing,&#13;
     network design, etc. &#13;
&#13;
     From a complexity point of view, MIP solving is known to be  NP-hard and most commonly tried to be solved via&#13;
     Branch-and-Bound based algorithms. Branch-and-Bound algorithms benefit from early and good feasible solutions of a MIP&#13;
     in various ways.  &#13;
              &#13;
     Primal heuristics are aimed at finding new solutions during the MIP solving process. There are different types of primal heuristics:&#13;
     while start heuristics are particularly&#13;
    valuable to find an early solution, improvement heuristics hopefully drive a given solution further towards optimality. &#13;
     &#13;
     This thesis focusses on primal heuristics which are part of the MIP-solving framework SCIP. &#13;
     The first chapter comes with basic definitions and a brief description of SCIP and the test set which we used.&#13;
     The remainder of the first chapter is an overview of the existing heuristics in SCIP which have been implemented by Achterberg&#13;
     and Berthold.&#13;
&#13;
     In the following chapters we introduce three new heuristics which apply rounding or propagation techniques for their specific purpose,&#13;
     namely the new rounding heuristic ZI Round, taken from Wallace, a 2-Opt improvement &#13;
     heuristic for MIP and the propagation heuristic Shift-and-Propagate. &#13;
     It is characteristic of all three heuristics that they mainly apply computationally inexpensive algorithms.&#13;
       &#13;
     Each of them is presented in an own chapter, starting with an algorithmic description, followed by implementational details.&#13;
     All chapters close with a discussion of the computational results obtained with the respective implementations in SCIP.</abstract>
    <identifier type="urn">urn:nbn:de:0297-zib-13322</identifier>
    <author>Gregor Hendel</author>
    <submitter>Gregor Hendel</submitter>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Primal Heuristics, MIP, mixed integer programming, ZI Round, Shift-and-Propagate, optimization</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="collections" number="">Studienabschlussarbeiten</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="hendel">Hendel, Gregor</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisPublisher>Zuse Institute Berlin (ZIB)</thesisPublisher>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
    <file>https://opus4.kobv.de/opus4-zib/files/1332/bachelor_thesis_main.pdf</file>
  </doc>
  <doc>
    <id>1325</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-07-14</completedDate>
    <publishedDate>2011-07-14</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Rounding and Propagation Heuristics for Mixed Integer Programming</title>
    <abstract language="eng">Primal heuristics are an important component of state-of-the-art codes for&#13;
mixed integer programming. In this paper, we focus on primal heuristics&#13;
that only employ computationally inexpensive procedures such as rounding&#13;
and logical deductions (propagation). We give an overview of eight&#13;
different approaches. To assess the impact of these primal  heuristics on&#13;
the ability to find feasible solutions, in particular early during search,&#13;
we introduce a new performance measure, the primal integral. Computational&#13;
experiments evaluate this and other measures on MIPLIB~2010 benchmark&#13;
instances.</abstract>
    <identifier type="serial">11-29</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-13255</identifier>
    <identifier type="doi">10.1007/978-3-642-29210-1_12</identifier>
    <enrichment key="SourceTitle">Appeared in: Operations Research Proceedings 2011. Diethard Klatte et al. (eds.) Springer 2012, pp. 71-76</enrichment>
    <author>Tobias Achterberg</author>
    <submitter>Timo Berthold</submitter>
    <author>Timo Berthold</author>
    <author>Gregor Hendel</author>
    <series>
      <title>ZIB-Report</title>
      <number>11-29</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>primal heuristic</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>mixed integer programming</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>domain propagation</value>
    </subject>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C59">Approximation methods and heuristics</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="berthold">Berthold, Timo</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="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1325/ZR-11-29.pdf</file>
  </doc>
  <doc>
    <id>6575</id>
    <completedYear>2017</completedYear>
    <publishedYear>2017</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>499</pageFirst>
    <pageLast>517</pageLast>
    <pageNumber/>
    <edition/>
    <issue>3</issue>
    <volume>33</volume>
    <type>article</type>
    <publisherName>Taylor &amp; Francis</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2017-11-03</completedDate>
    <publishedDate>2017-10-10</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">From feasibility to improvement to proof: three phases of solving mixed-integer programs</title>
    <abstract language="eng">Modern mixed-integer programming (MIP) solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound. Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three distinct phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behaviour of the non-commercial MIP solver Scip at the predicted phase transition points.</abstract>
    <parentTitle language="eng">Optimization Methods and Software</parentTitle>
    <identifier type="doi">10.1080/10556788.2017.1392519</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-61607</enrichment>
    <author>Timo Berthold</author>
    <submitter>Regine Kossick</submitter>
    <author>Gregor Hendel</author>
    <author>Thorsten Koch</author>
    <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="hendel">Hendel, Gregor</collection>
    <collection role="persons" number="koch">Koch, Thorsten</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>
  </doc>
  <doc>
    <id>5743</id>
    <completedYear/>
    <publishedYear>2014</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>73</pageFirst>
    <pageLast>106</pageLast>
    <pageNumber/>
    <edition/>
    <issue>1</issue>
    <volume>21</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Shift-and-Propagate</title>
    <abstract language="eng">In recent years, there has been a growing interest in the design of general purpose primal heuristics for use inside complete mixed integer programming solvers. Many of these heuristics rely on an optimal LP solution, which may take a significant amount of time to find. In this paper, we address this issue by introducing a pre-root primal heuristic that does not require a previously found LP solution. This heuristic, named Shift-and-Propagate , applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement to existing rounding and propagation heuristics.</abstract>
    <parentTitle language="eng">Journal of Heuristics</parentTitle>
    <identifier type="doi">10.1007/s10732-014-9271-0</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-17596</enrichment>
    <author>Timo Berthold</author>
    <author>Gregor Hendel</author>
    <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="hendel">Hendel, Gregor</collection>
    <collection role="projects" number="ASTfSCM">ASTfSCM</collection>
    <collection role="projects" number="MATHEON-B20">MATHEON-B20</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>
  </doc>
  <doc>
    <id>5709</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>--</completedDate>
    <publishedDate>2015-12-21</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Exploiting Solving Phases for Mixed-Integer Programs</title>
    <abstract language="eng">Modern MIP solving software&#13;
incorporates dozens of auxiliary algorithmic components for supporting&#13;
the branch-and-bound search in finding and improving solutions and in strengthening the relaxation.&#13;
Intuitively, a dynamic solving strategy with an appropriate emphasis on different solving components and strategies is desirable during the search process.&#13;
We propose an adaptive solver behavior that dynamically reacts &#13;
on transitions between the three typical phases of a MIP solving process:&#13;
The first phase objective is to find a feasible solution. During the second phase,&#13;
a sequence of incumbent solutions gets constructed&#13;
until the incumbent is eventually optimal. Proving&#13;
optimality is the central objective of the remaining third phase.&#13;
Based on the MIP-solver SCIP, we demonstrate &#13;
the usefulness of the phase concept both with an exact recognition of the optimality of a solution, and provide&#13;
heuristic alternatives to make use of the concept in practice.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-57098</identifier>
    <identifier type="doi">10.1007/978-3-319-42902-1_1</identifier>
    <enrichment key="SourceTitle">Appeared in: Operations Research Proceedings 2015</enrichment>
    <author>Gregor Hendel</author>
    <submitter>Gregor Hendel</submitter>
    <series>
      <title>ZIB-Report</title>
      <number>15-64</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Branch-and-Bound, 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="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="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/5709/Hendel_ExploitingSolvingPhases.pdf</file>
  </doc>
  <doc>
    <id>6160</id>
    <completedYear/>
    <publishedYear>2016</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>1</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2016-12-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Three Phases of MIP Solving</title>
    <abstract language="eng">Modern MIP solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound.&#13;
Typically, all components are tuned  to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three different phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behavior of the MIP solver SCIP at the predicted phase transition points.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-61607</identifier>
    <identifier type="doi">10.1080/10556788.2017.1392519</identifier>
    <enrichment key="SourceTitle">Optimization Methods and Software</enrichment>
    <author>Timo Berthold</author>
    <submitter>Gregor Hendel</submitter>
    <author>Gregor Hendel</author>
    <author>Thorsten Koch</author>
    <series>
      <title>ZIB-Report</title>
      <number>16-78</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>optimization software</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed-integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branch-and-bound</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>adaptive search behavior</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>optimality prediction</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="persons" number="hendel">Hendel, Gregor</collection>
    <collection role="persons" number="koch">Koch, Thorsten</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/6160/zib-paper.pdf</file>
  </doc>
</export-example>
