@misc{BorndoerferFerreiraMartin1997, author = {Bornd{\"o}rfer, Ralf and Ferreira, Carlos E. and Martin, Alexander}, title = {Matrix Decomposition by Branch-and-Cut}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2839}, number = {SC-97-14}, year = {1997}, abstract = {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.}, language = {en} } @misc{BorndoerferGroetschelHerzogetal.1996, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Herzog, Werner and Klostermeier, Fridolin and Konsek, Wilhelm and K{\"u}ttner, Christian}, title = {K{\"u}rzen muß nicht Kahlschlag heißen - das Beispiel Telebus-Behindertenfahrdienst Berlin}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2510}, number = {SC-96-41}, year = {1996}, abstract = {M{\"u}ssen Etatk{\"u}rzungen bei staatlichen Dienstleistungseinrichtungen notwendig zu Leistungseinschr{\"a}nkungen oder Geb{\"u}hrenerh{\"o}hungen f{\"u}hren? Wir zeigen am Beispiel des Berliner Behindertenfahrdienstes {\em Telebus}, da\ss{} Sparzwang auch als Chance zur Verbesserung der eigenen Verwaltungs- und Arbeitsabl{\"a}ufe genutzt werden kann. Durch st{\"a}rkere Dienstleistungsorientierung, Vereinfachung der Arbeitsabl{\"a}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.}, language = {de} } @misc{BorndoerferGroetschelKlostermeieretal.1996, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Klostermeier, Fridolin and K{\"u}ttner, Christian}, title = {Telebus Berlin - Mobilit{\"a}t f{\"u}r Behinderte}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2500}, number = {SC-96-40}, year = {1996}, abstract = {Steigendes Mobilit{\"a}tsbed{\"u}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{\"u}nschen pro Tag an ihre Grenzen. Zur L{\"o}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{\"a}ufe unterst{\"u}tzenden Computersystems, das seit {\"u}ber einem Jahr im Einsatz ist. Herzst{\"u}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{\"o}rderung. Das Beispiel Telebus zeigt, da\ss{} der Einsatz mathematischer Optimierungstechniken neue M{\"o}glichkeiten f{\"u}r Kosteneinsparungen bei gleichzeitiger Serviceverbesserung auch in anderen Bereichen des {\"O}PNV er{\"o}ffnet.}, language = {de} } @misc{BorndoerferGroetschelLoebel1998, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Optimization of Transportation Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3529}, number = {SC-98-09}, year = {1998}, abstract = {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.}, language = {en} } @misc{BorndoerferGroetschelKlostermeieretal.1993, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Klostermeier, Fridolin and K{\"u}ttner, Christian}, title = {Telebus-Disposition: Ein Konzept zur Serviceverbesserung bei gleichzeitiger Kostensenkung.[nur hausintern]}, number = {TR-93-03}, year = {1993}, abstract = {"`Telebus"' ist der soziale Behindertenfahrdienst im Land Berlin. Das Telebus-Forschungsprojekt des Konrad-Zuse-Zentrums f{\"u}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{\"o}glichkeiten zur Verbesserung des Service und zur Reduzierung der Kosten skizziert. \originalTeX}, language = {de} } @misc{BorndoerferGroetschelLoebel1999, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Der Schnellste Weg zum Ziel}, doi = {10.1007/978-3-322-96366-6_5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4209}, number = {SC-99-32}, year = {1999}, abstract = {Wir geben eine Einf{\"u}hrung in die Mathematik von und mit Wegen. Nicht auf dem k{\"u}rzesten, aber auf einem hoffentlich kurzweiligen Weg!}, language = {de} } @misc{BorndoerferGroetschelLoebel2010, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {The Quickest Path to the Goal}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11840}, number = {10-21}, year = {2010}, abstract = {We provide an introduction into the mathematics of and with paths. Not on the shortest, but hopefully on an entertaining path!}, language = {en} } @misc{Borndoerfer2003, author = {Bornd{\"o}rfer, Ralf}, title = {Combinatorial Packing Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7255}, number = {03-03}, year = {2003}, abstract = {This article investigates a certain class of combinatorial packing problems and some polyhedral relations between such problems and the set packing problem.}, language = {en} } @misc{BorndoerferGroetschelLoebel1995, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Alcuin's Transportation Problems and Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1932}, number = {SC-95-27}, year = {1995}, abstract = {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.}, language = {en} } @misc{BorndoerferFerreiraMartin1997, author = {Bornd{\"o}rfer, Ralf and Ferreira, Carlos E. and Martin, Alexander}, title = {Decomposing Matrices into Blocks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2849}, number = {SC-97-15}, year = {1997}, abstract = {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.}, language = {en} }