<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>283</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1997-03-17</completedDate>
    <publishedDate>1997-03-17</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Matrix Decomposition by Branch-and-Cut</title>
    <abstract language="eng">In this paper we investigate whether matrices arising from linear or integer programming problems can be decomposed into so-called {\em bordered block diagonal form}. More precisely, given some matrix $A$, we try to assign as many rows as possible to some number of blocks of limited size such that no two rows assigned to different blocks intersect in a common column. Bordered block diagonal form is desirable because it can guide and speed up the solution process for linear and integer programming problems. We show that various matrices from the %LP- and MIP-libraries \Netlib{} and MIPLIB can indeed be decomposed into this form by computing optimal decompositions or decompositions with proven quality. These computations are done with a branch-and-cut algorithm based on polyhedral investigations of the matrix decomposition problem.</abstract>
    <identifier type="serial">SC-97-14</identifier>
    <identifier type="opus3-id">284</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-2839</identifier>
    <author>Ralf Borndörfer</author>
    <author>Carlos E. Ferreira</author>
    <author>Alexander Martin</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-97-14</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="SenWiFo-Telebus">SenWiFo-Telebus</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/283/SC-97-14.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/283/SC-97-14.pdf</file>
  </doc>
  <doc>
    <id>251</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1996-11-26</completedDate>
    <publishedDate>1996-11-26</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Kürzen muß nicht Kahlschlag heißen - das Beispiel Telebus-Behindertenfahrdienst Berlin</title>
    <abstract language="deu">Müssen Etatkürzungen bei staatlichen Dienstleistungseinrichtungen notwendig zu Leistungseinschränkungen oder Gebührenerhöhungen führen? Wir zeigen am Beispiel des Berliner Behindertenfahrdienstes {\em Telebus}, da\ss{} Sparzwang auch als Chance zur Verbesserung der eigenen Verwaltungs- und Arbeitsabläufe genutzt werden kann. Durch stärkere Dienstleistungsorientierung, Vereinfachung der Arbeitsabläufe und durch den Einsatz von moderner EDV und von mathematischen Optimierungsmethoden zur Fahrzeugeinsatzplanung werden bei Telebus heute staatliche Leistungen trotz geringeren Etats besser erbracht als vorher.</abstract>
    <identifier type="serial">SC-96-41</identifier>
    <identifier type="opus3-id">252</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-2510</identifier>
    <author>Ralf Borndörfer</author>
    <author>Martin Grötschel</author>
    <author>Werner Herzog</author>
    <author>Fridolin Klostermeier</author>
    <author>Wilhelm Konsek</author>
    <author>Christian Küttner</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-96-41</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="projects" number="SenWiFo-Telebus">SenWiFo-Telebus</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/251/SC-96-41.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/251/SC-96-41.pdf</file>
  </doc>
  <doc>
    <id>250</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1996-11-26</completedDate>
    <publishedDate>1996-11-26</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Telebus Berlin - Mobilität für Behinderte</title>
    <abstract language="deu">Steigendes Mobilitätsbedürfnis der Behinderten bei angespannter Haushaltslage --- diese Situation ergab vor drei Jahren beim Berliner Behindertenfahrdienst {\em Telebus\/} Handlungsbedarf. Gleichzeitig stie\ss{} die verwendete manuelle (Fahrzeug-)Tourenplanung mit damals etwa 1.000 Fahrtwünschen pro Tag an ihre Grenzen. Zur Lösung dieser Probleme war der effiziente Einsatz von Computern und von {\em mathematischen Optimierungsverfahren\/} erforderlich. Ergebnis des daraufhin gestarteten {\em Telebus-Projektes\/} ist die Entwicklung eines neuen, alle Arbeitsabläufe unterstützenden Computersystems, das seit über einem Jahr im Einsatz ist. Herzstück dieses Systems ist ein auf mathematischen Methoden der ganzzahligen Optimierung basierendes Verfahren zur Tourenplanung. Ziel dieses Artikels ist die Beschreibung dieses Verfahrens und seiner Verwendung bei der Behindertenbeförderung. Das Beispiel Telebus zeigt, da\ss{} der Einsatz mathematischer Optimierungstechniken neue Möglichkeiten für Kosteneinsparungen bei gleichzeitiger Serviceverbesserung auch in anderen Bereichen des ÖPNV eröffnet.</abstract>
    <identifier type="serial">SC-96-40</identifier>
    <identifier type="opus3-id">251</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-2500</identifier>
    <enrichment key="SourceTitle">Erschienen unter dem Titel: "Berliner Telebussystem bietet Mobilität für Behinderte" in: Der Nahverkehr (1-2) 20-22 (1997)</enrichment>
    <author>Ralf Borndörfer</author>
    <author>Martin Grötschel</author>
    <author>Fridolin Klostermeier</author>
    <author>Christian Küttner</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-96-40</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</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="groetschel">Grötschel, Martin</collection>
    <collection role="projects" number="SenWiFo-Telebus">SenWiFo-Telebus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/250/SC-96-40.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/250/SC-96-40.pdf</file>
  </doc>
  <doc>
    <id>352</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1998-03-11</completedDate>
    <publishedDate>1998-03-11</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Optimization of Transportation Systems</title>
    <abstract language="eng">The world has experienced two hundred years of unprecedented advances in vehicle technology, transport system development, and traffic network extension. Technical progress continues but seems to have reached some limits. Congestion, pollution, and increasing costs have created, in some parts of the world, a climate of hostility against transportation technology. Mobility, however, is still increasing. What can be done? There is no panacea. Interdisciplinary cooperation is necessary, and we are going to argue in this paper that {\em Mathematics\/} can contribute significantly to the solution of some of the problems. We propose to employ methods developed in the {\em Theory of Optimization\/} to make better use of resources and existing technology. One way of optimization is better planning. We will point out that {\em Discrete Mathematics\/} provides a suitable framework for planning decisions within transportation systems. The mathematical approach leads to a better understanding of problems. Precise and quantitative models, and advanced mathematical tools allow for provable and reproducible conclusions. Modern computing equipment is suited to put such methods into practice. At present, mathematical methods contribute, in particular, to the solution of various problems of {\em operational planning}. We report about encouraging {\em results\/} achieved so far.</abstract>
    <identifier type="serial">SC-98-09</identifier>
    <identifier type="opus3-id">353</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3529</identifier>
    <author>Ralf Borndörfer</author>
    <author>Martin Grötschel</author>
    <author>Andreas Löbel</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-98-09</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Transportation Systems</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Discrete Mathematics</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="persons" number="loebel">Löbel, Andreas</collection>
    <collection role="projects" number="BMBF-DS">BMBF-DS</collection>
    <collection role="projects" number="BMBF-VS">BMBF-VS</collection>
    <collection role="projects" number="SenWiFo-Telebus">SenWiFo-Telebus</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/352/SC-98-09.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/352/SC-98-09.pdf</file>
  </doc>
  <doc>
    <id>495</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1993-03-11</completedDate>
    <publishedDate>1993-03-11</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Telebus-Disposition: Ein Konzept zur Serviceverbesserung bei gleichzeitiger Kostensenkung.[nur hausintern]</title>
    <abstract language="deu">"`Telebus"' ist der soziale Behindertenfahrdienst im Land Berlin. Das Telebus-Forschungsprojekt des Konrad-Zuse-Zentrums für Informationstechnik (ZIB) hat das Ziel, den Fahrdienst (insbesondere die Disposition der Telebusse) zu verbessern, d.h. kundenfreundlicher zu gestalten und gleichzeitig billiger zu machen. In diesem Bericht werden die bisherigen Ergebnisse dargestellt und weitere Möglichkeiten zur Verbesserung des Service und zur Reduzierung der Kosten skizziert. \originalTeX</abstract>
    <identifier type="serial">TR-93-03</identifier>
    <identifier type="opus3-id">495</identifier>
    <note>Volltext nur Hausintern</note>
    <author>Ralf Borndörfer</author>
    <author>Martin Grötschel</author>
    <author>Fridolin Klostermeier</author>
    <author>Christian Küttner</author>
    <series>
      <title>ZIB-Report</title>
      <number>TR-93-03</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <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="groetschel">Grötschel, Martin</collection>
    <collection role="projects" number="SenWiFo-Telebus">SenWiFo-Telebus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>420</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1999-09-17</completedDate>
    <publishedDate>1999-09-17</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Der Schnellste Weg zum Ziel</title>
    <abstract language="deu">Wir geben eine Einführung in die Mathematik von und mit Wegen. Nicht auf dem kürzesten, aber auf einem hoffentlich kurzweiligen Weg!</abstract>
    <identifier type="serial">SC-99-32</identifier>
    <identifier type="opus3-id">421</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-4209</identifier>
    <identifier type="doi">10.1007/978-3-322-96366-6_5</identifier>
    <enrichment key="SourceTitle">Appeared in: Aigner u. Behrends (Eds.) (2000), Alles Mathematik, Vieweg Verlag. S. 45-76</enrichment>
    <author>Ralf Borndörfer</author>
    <author>Martin Grötschel</author>
    <author>Andreas Löbel</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-99-32</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Kürzeste Wege</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Kombinatorische Optimierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Operations Research</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <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="groetschel">Grötschel, Martin</collection>
    <collection role="persons" number="loebel">Löbel, Andreas</collection>
    <collection role="projects" number="BMBF-DS">BMBF-DS</collection>
    <collection role="projects" number="MATHEON-B1">MATHEON-B1</collection>
    <collection role="projects" number="SenWiFo-Telebus">SenWiFo-Telebus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/420/SC-99-32.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/420/SC-99-32.pdf</file>
  </doc>
  <doc>
    <id>1184</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2010-07-13</completedDate>
    <publishedDate>2010-07-13</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Quickest Path to the Goal</title>
    <abstract language="eng">We provide an introduction into the mathematics of and with paths. Not on the shortest, but hopefully on an entertaining path!</abstract>
    <identifier type="serial">10-21</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1245</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11840</identifier>
    <enrichment key="SourceTitle">Appeared in: Aigner,  Behrends (Eds.) Mathematics Everywhere, American Mathematical Society, 2010, pp. 27-51</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <author>Martin Grötschel</author>
    <author>Andreas Löbel</author>
    <series>
      <title>ZIB-Report</title>
      <number>10-21</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>shortest paths</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>combinatorial optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>operations research</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="persons" number="loebel">Löbel, Andreas</collection>
    <collection role="projects" number="BMBF-DS">BMBF-DS</collection>
    <collection role="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="projects" number="SenWiFo-Telebus">SenWiFo-Telebus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1184/ZR_10_21.pdf</file>
  </doc>
  <doc>
    <id>725</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2003-03-06</completedDate>
    <publishedDate>2003-03-06</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Combinatorial Packing Problems</title>
    <abstract language="eng">This article investigates a certain class of combinatorial packing problems and some polyhedral relations between such problems and the set packing problem.</abstract>
    <identifier type="serial">03-03</identifier>
    <identifier type="opus3-id">726</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-7255</identifier>
    <enrichment key="SourceTitle">Appeared in: The Sharpest Cut: The Impact of Manfred Padberg and his Work. Ed. By Martin Grötschel. Philadelphia: Society for Industrial and Applied Mathematics 2004. Pp. 19-32</enrichment>
    <author>Ralf Borndörfer</author>
    <series>
      <title>ZIB-Report</title>
      <number>03-03</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Packing problems</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>polyhedral combinatorics</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <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="projects" number="SenWiFo-Telebus">SenWiFo-Telebus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/725/ZR-03-03.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/725/ZR-03-03.pdf</file>
  </doc>
  <doc>
    <id>193</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1995-11-08</completedDate>
    <publishedDate>1995-11-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Alcuin's Transportation Problems and Integer Programming</title>
    <abstract language="eng">The need to solve {\it transportation problems\/} was and still is one of the driving forces behind the development of the mathematical disciplines of graph theory, optimization, and operations research. Transportation problems seem to occur for the first time in the literature in the form of the four ''River Crossing Problems'' in the book Propositiones ad acuendos iuvenes. The {\it Propositiones\/} ---the oldest collection of mathematical problems written in Latin--- date back to the $8$th century A.D. and are attributed to Alcuin of York, one of the leading scholars of his time, a royal advisor to Charlemagne at his Frankish court. Alcuin's river crossing problems had no impact on the development of mathematics. However, they already display all the characteristics of today's large-scale real transportation problems. From our point of view, they could have been the starting point of combinatorics, optimization, and operations research. We show the potential of Alcuin's problems in this respect by investigating his problem~18 about a wolf, a goat and a bunch of cabbages with current mathematical methods. This way, we also provide the reader with a leisurely introduction into the modern theory of integer programming.</abstract>
    <identifier type="serial">SC-95-27</identifier>
    <identifier type="opus3-id">193</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-1932</identifier>
    <enrichment key="SourceTitle">Appeared in: Charlemagne and his Heritage : 1200 Years of Civilization and Science in Europe. P. L. Butzer et al. (eds.) Vol. 2: The Mathematical Arts. Brepols, Turnhout, Belgium, 1998. Pp. 379-409</enrichment>
    <author>Ralf Borndörfer</author>
    <author>Martin Grötschel</author>
    <author>Andreas Löbel</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-95-27</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="persons" number="loebel">Löbel, Andreas</collection>
    <collection role="projects" number="BMBF-DS">BMBF-DS</collection>
    <collection role="projects" number="BMBF-VS">BMBF-VS</collection>
    <collection role="projects" number="SenWiFo-Telebus">SenWiFo-Telebus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/193/SC-95-27.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/193/SC-95-27.pdf</file>
  </doc>
  <doc>
    <id>284</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1997-03-17</completedDate>
    <publishedDate>1997-03-17</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Decomposing Matrices into Blocks</title>
    <abstract language="eng">In this paper we investigate whether matrices arising from linear or integer programming problems can be decomposed into so-called {\em bordered block diagonal form}. More precisely, given some matrix $A$, we try to assign as many rows as possible to some number of blocks of limited size such that no two rows assigned to different blocks intersect in a common column. Bordered block diagonal form is desirable because it can guide and speed up the solution process for linear and integer programming problems. We show that various matrices from the LP- and MIP-libraries NETLIB and MITLIB can indeed be decomposed into this form by computing optimal decompositions or decompositions with proven quality. These computations are done with a branch-and-cut algorithm based on polyhedral investigations of the matrix decomposition problem. In practice, however, one would use heuristics to find a good decomposition. We present several heuristic ideas and test their performance. Finally, we investigate the usefulness of optimal matrix decompositions into bordered block diagonal form for integer programming by using such decompositions to guide the branching process in a branch-and-cut code for general mixed integer programs.</abstract>
    <identifier type="serial">SC-97-15</identifier>
    <identifier type="opus3-id">285</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-2849</identifier>
    <enrichment key="SourceTitle">Appeared in: SIAM J. on Opt. 9 (1998), Nr 1, 236-269</enrichment>
    <author>Ralf Borndörfer</author>
    <author>Carlos E. Ferreira</author>
    <author>Alexander Martin</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-97-15</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="SenWiFo-Telebus">SenWiFo-Telebus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/284/SC-97-15.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/284/SC_97_15.orig.Vers.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/284/SC-97-15.pdf</file>
  </doc>
  <doc>
    <id>292</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1997-05-23</completedDate>
    <publishedDate>1997-05-23</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Telebus Berlin: Vehicle Scheduling in a Dial-a-Ride System</title>
    <abstract language="eng">{\em Telebus\/} is Berlin's dial-a-ride system for handicapped people that cannot use the public transportation system. The service is provided by a fleet of about 100 mini-busses and includes aid to get in and out of the vehicle. Telebus has between 1,000 and 1,500 transportation requests per day. The problem arises to schedule these requests into the vehicles such that punctual service is provided while operation costs should be minimum. Additional constraints include pre-rented vehicles, fixed bus driver shift lengths, obligatory breaks, and different vehicle capacities. We use a {\em set partitioning\/} approach for the solution of the bus scheduling problem that consists of two steps. The first {\em clustering\/} step identifies segments of possible bus tours (``orders'') such that more than one person is transported at a time; the aim in this step is to reduce the size of the problem and to make use of larger vehicle capacities. The problem to select a set of orders such that the traveling distance of the vehicles within the orders is minimal is a set partitioning problem that we can solve to optimality. In the second step the selected orders are {\em chained\/} to yield possible bus tours respecting all side constraints. The problem to select a set of such bus tours such that each order is serviced once and the total traveling distance of the vehicles is minimum is again a set partitioning problem that we solve approximately. We have developed a computer system for the solution of the bus scheduling problem that includes a branch-and-cut algorithm for the solution of the set partitioning problems. A version of this system is in operation at Telebus since July 1995. Its use made it possible that Telebus can service today about 30\% more requests per day for the same amount of money than before.</abstract>
    <identifier type="serial">SC-97-23</identifier>
    <identifier type="opus3-id">293</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-2925</identifier>
    <identifier type="doi">10.1007/978-3-642-85970-0_19</identifier>
    <enrichment key="SourceTitle">Appeared in: Lecture Notes in Economics and Mathematical Systems, Proc. of the 7th Int. Workshop on Computer-Aided Transit Scheduling (N. Wilson, Hrsg.), Springer, Berlin (1999) 391-422</enrichment>
    <author>Ralf Borndörfer</author>
    <author>Martin Grötschel</author>
    <author>Fridolin Klostermeier</author>
    <author>Christian Küttner</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-97-23</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <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="groetschel">Grötschel, Martin</collection>
    <collection role="projects" number="SenWiFo-Telebus">SenWiFo-Telebus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/292/SC-97-23.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/292/SC-97-23.pdf</file>
  </doc>
  <doc>
    <id>299</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1997-06-30</completedDate>
    <publishedDate>1997-06-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Set Packing Relaxations of Some Integer Programs</title>
    <abstract language="eng">This paper is about {\em set packing relaxations\/} of combinatorial optimization problems associated with acyclic digraphs and linear orderings, cuts and multicuts, and vertex packings themselves. Families of inequalities that are valid for such a relaxation as well as the associated separation routines carry over to the problems under investigation.</abstract>
    <identifier type="serial">SC-97-30</identifier>
    <identifier type="opus3-id">300</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-2998</identifier>
    <enrichment key="SourceTitle">Appeared in: Mathematical Programming, 88,425-450, 2000</enrichment>
    <author>Ralf Borndörfer</author>
    <author>Robert Weismantel</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-97-30</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="SenWiFo-Telebus">SenWiFo-Telebus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/299/SC-97-30.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/299/SC-97-30.pdf</file>
  </doc>
  <doc>
    <id>323</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1997-11-07</completedDate>
    <publishedDate>1997-11-07</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Discrete Relaxations of Combinatorial Programs</title>
    <abstract language="eng">This paper investigates {\em relations\/} among combinatorial optimization problems. To establish such relations we introduce a transformation technique \mbox{---{\em aggregation}---} that allows to relax an integer program by means of another integer program. We prove that various families of prominent inequalities for the acyclic subdigraph problem, the multiple knapsack problem, the max cut, graph, and the clique partitioning problem, the set covering problem, and the set packing problem can be derived and separated in polynomial time in this way. Our technique is algorithmic. It has been implemented and used in a set partitioning code.</abstract>
    <identifier type="serial">SC-97-54</identifier>
    <identifier type="opus3-id">324</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3230</identifier>
    <enrichment key="SourceTitle">Rev. vers. appeared in: Discrete Appl. Math. 112 (2001) 11-26</enrichment>
    <author>Ralf Borndörfer</author>
    <author>Robert Weismantel</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-97-54</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="SenWiFo-Telebus">SenWiFo-Telebus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/323/SC_97_54.orig.Vers.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/323/SC-97-54.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/323/SC-97-54.pdf</file>
  </doc>
  <doc>
    <id>279</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1997-03-03</completedDate>
    <publishedDate>1997-03-03</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Optimierung des Berliner Behindertenfahrdienstes</title>
    <abstract language="deu">In diesem Artikel geben wir einen Überblick über das Telebus-Projekt am Konrad-Zuse-Zentrum, Berlin, durch das der Behindertenfahrdienst in Berlin reorganisiert und optimiert wurde. Wir berichten kurz über die mathematischen Probleme und, etwas ausführlicher, über die nicht-mathematischen Schwierigkeiten, die bei der Durchführung dieses Projektes auftraten.</abstract>
    <identifier type="serial">SC-97-10</identifier>
    <identifier type="opus3-id">280</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-2799</identifier>
    <enrichment key="SourceTitle">Erschienen in: Mitteilungen der Deutschen Mathematiker-Vereinigung 2 (1997) 38-43</enrichment>
    <author>Ralf Borndörfer</author>
    <author>Martin Grötschel</author>
    <author>Fridolin Klostermeier</author>
    <author>Christian Küttner</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-97-10</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <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="groetschel">Grötschel, Martin</collection>
    <collection role="projects" number="SenWiFo-Telebus">SenWiFo-Telebus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/279/SC-97-10.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/279/SC-97-10.pdf</file>
  </doc>
</export-example>
