• Deutsch
Login

  • Home
  • Search
  • Browse
  • Publish
  • FAQ

Refine

Author

  • Borndörfer, Ralf (263)
  • Schlechte, Thomas (74)
  • Grötschel, Martin (39)
  • Karbstein, Marika (35)
  • Reuther, Markus (35)
  • Weider, Steffen (27)
  • Pfetsch, Marc (24)
  • Löbel, Andreas (23)
  • Swarat, Elmar (22)
  • Sagnol, Guillaume (21)
+ more

Year of publication

  • 2021 (2)
  • 2020 (11)
  • 2019 (13)
  • 2018 (13)
  • 2017 (14)
  • 2016 (22)
  • 2015 (23)
  • 2014 (17)
  • 2013 (13)
  • 2012 (26)
+ more

Document Type

  • ZIB-Report (128)
  • In Proceedings (73)
  • Article (46)
  • Book chapter (5)
  • In Collection (3)
  • Other (3)
  • Doctoral Thesis (2)
  • Book (1)
  • Habilitation (1)
  • Master's Thesis (1)
+ more

Language

  • English (237)
  • German (26)

Has Fulltext

  • no (133)
  • yes (130)

Is part of the Bibliography

  • no (261)
  • yes (2)

Keywords

  • line planning (11)
  • Optimierung (9)
  • integer programming (9)
  • column generation (7)
  • combinatorial optimization (6)
  • Periodic timetabling (5)
  • Column Generation (4)
  • Integer Programming (4)
  • Linienplanung (4)
  • Mixed Integer Programming (4)
+ more

Institute

  • Mathematical Optimization (237)
  • Mathematics of Transportation and Logistics (106)
  • ZIB Allgemein (15)
  • Network Optimization (9)
  • Mathematics of Health Care (3)
  • Mathematical Algorithmic Intelligence (2)
  • Mathematics for Life and Materials Science (2)
  • Modeling and Simulation of Complex Processes (2)
  • Computational Medicine (1)
  • Mathematical Optimization Methods (1)
+ more

263 search hits

  • 1 to 10
  • BibTeX
  • CSV
  • RIS
  • XML
  • 10
  • 20
  • 50
  • 100

Sort by

  • Year
  • Year
  • Title
  • Title
  • Author
  • Author
Matrix Decomposition by Branch-and-Cut (1997)
Borndörfer, Ralf ; Ferreira, Carlos E. ; Martin, Alexander
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.
Decomposing Matrices into Blocks (1997)
Borndörfer, Ralf ; Ferreira, Carlos E. ; Martin, Alexander
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.
Optimierung des Berliner Behindertenfahrdienstes (1997)
Borndörfer, Ralf ; Grötschel, Martin ; Klostermeier, Fridolin ; Küttner, Christian
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.
Telebus Berlin: Vehicle Scheduling in a Dial-a-Ride System (1997)
Borndörfer, Ralf ; Grötschel, Martin ; Klostermeier, Fridolin ; Küttner, Christian
{\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.
Set Packing Relaxations of Some Integer Programs (1997)
Borndörfer, Ralf ; Weismantel, Robert
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.
Kürzen muß nicht Kahlschlag heißen - das Beispiel Telebus-Behindertenfahrdienst Berlin (1996)
Borndörfer, Ralf ; Grötschel, Martin ; Herzog, Werner ; Klostermeier, Fridolin ; Konsek, Wilhelm ; Küttner, Christian
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.
Telebus Berlin - Mobilität für Behinderte (1996)
Borndörfer, Ralf ; Grötschel, Martin ; Klostermeier, Fridolin ; Küttner, Christian
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.
Alcuin's Transportation Problems and Integer Programming (1995)
Borndörfer, Ralf ; Grötschel, Martin ; Löbel, Andreas
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.
On the Complexity of Storage Assignment Problems. (1994)
Abdel-Hamid, Atef Abdel-Aziz ; Borndörfer, Ralf
{\def\NP{\hbox{$\cal N\kern-.1667em\cal P$}} The {\sl storage assignment problem} asks for the cost minimal assignment of containers with different sizes to storage locations with different capacities. Such problems arise, for instance, in the optimal control of automatic storage devices in flexible manufacturing systems. This problem is known to be $\NP$-hard in the strong sense. We show that the storage assignment problem is $\NP$-hard for {\sl bounded sizes and capacities}, even if the sizes have values $1$ and~$2$ and the capacities value~$2$ only, a case we encountered in practice. Moreover, we prove that no polynomial time $\epsilon$-approximation algorithm exists. This means that almost all storage assignment problems arising in practice are indeed hard.}
Zielorientierte Dienstplanoptimierung (1998)
Borndörfer, Ralf ; Löbel, Andreas ; Strubbe, Uwe ; Völker, Manfred
Dieser Artikel behandelt einen Ansatz zur zielorientierten Optimierung der Dienstplanung im ÖPNV. Der Ansatz zielt auf die vollständige Ausnutzung aller planerischen Freiheitsgrade unter korrekter Berücksichtigung von gesetzlichen, tariflichen, technischen und betrieblichen Rahmenbedingungen. Er basiert auf mathematischen Optimierungstechniken, die wir gegenwärtig in einem vom Bundesministerium für Bildung und Forschung ({\tt bmb+f}) geförderten Verbundprojekt in einer Kooperation zwischen der HanseCom GmbH, der IVU GmbH und dem Konrad-Zuse-Zentrum für Informationstechnik Berlin entwickeln. Es ist geplant, das Verfahren in die Softwareprodukte HOT II, MICROBUS II und OPUS zu integrieren. Verhandlungen mit den Berliner Verkehrsbetrieben über eine Projektbeteiligung und Integration unserer Software in BERTA sind zur Zeit im Gang. Wir beschreiben die Methodik des Ansatzes, diskutieren Aspekte seiner praktischen Verwendung, und wir berichten über den Stand der Entwicklung.
  • 1 to 10

OPUS4 Logo

  • Contact
  • Impressum und Datenschutz
  • Sitelinks