TY - JOUR A1 - Borndörfer, Ralf A1 - Weismantel, Robert T1 - Discrete Relaxations of Combinatorial Programs JF - Discrete Appl. Math. Y1 - 2001 UR - http://opus.kobv.de/zib/volltexte/1997/324/ VL - 112 IS - 1–3 SP - 11 EP - 26 ER - TY - THES A1 - Borndörfer, Ralf T1 - Aspects of Set Packing, Partitioning, and Covering N2 - Diese Dissertation befaßt sich mit ganzzahligen Programmen mit 0/1 Systemen: SetPacking-, Partitioning- und Covering-Probleme. Die drei Teile der Dissertation behandeln polyedrische, algorithmische und angewandte Aspekte derartiger Modelle. Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10126 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Löbel, Andreas T1 - Der Schnellste Weg zum Ziel N2 - Wir geben eine Einführung in die Mathematik von und mit Wegen. Nicht auf dem kürzesten, aber auf einem hoffentlich kurzweiligen Weg! T3 - ZIB-Report - SC-99-32 KW - Kürzeste Wege KW - Kombinatorische Optimierung KW - Operations Research Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4209 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Klostermeier, Fridolin A1 - Küttner, Christian ED - Wilson, Nigel T1 - Telebus Berlin: Vehicle Scheduling in a Dial-a-Ride System T2 - Proceedings of the 7th International Workshop on Computer-Aided Transit Scheduling Y1 - 1999 U6 - https://doi.org/10.1007/978-3-642-85970-0_19 SP - 391 EP - 422 PB - Springer Verlag CY - Berlin ER - TY - THES A1 - Borndörfer, Ralf T1 - Aspects of Set Packing, Partitioning, and Covering Y1 - 1998 UR - http://opus.kobv.de/zib/volltexte/1998/1028/ ER - TY - GEN A1 - Borndörfer, Ralf ED - Grötschel, Martin T1 - Combinatorial Packing Problems T2 - The Sharpest Cut – The Impact of Manfred Padberg and His Work Y1 - 2004 UR - http://opus.kobv.de/zib/volltexte/2003/726/ SP - 19 EP - 32 PB - SIAM CY - Philadelphia ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Löbel, Andreas T1 - The Quickest Path to the Goal N2 - We provide an introduction into the mathematics of and with paths. Not on the shortest, but hopefully on an entertaining path! T3 - ZIB-Report - 10-21 KW - shortest paths KW - combinatorial optimization KW - operations research Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11840 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf T1 - Combinatorial Packing Problems N2 - This article investigates a certain class of combinatorial packing problems and some polyhedral relations between such problems and the set packing problem. T3 - ZIB-Report - 03-03 KW - Packing problems KW - polyhedral combinatorics Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7255 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Löbel, Andreas T1 - Alcuin's Transportation Problems and Integer Programming N2 - 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. T3 - ZIB-Report - SC-95-27 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1932 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Ferreira, Carlos E. A1 - Martin, Alexander T1 - Decomposing Matrices into Blocks N2 - 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. T3 - ZIB-Report - SC-97-15 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2849 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Klostermeier, Fridolin A1 - Küttner, Christian T1 - Telebus Berlin: Vehicle Scheduling in a Dial-a-Ride System N2 - {\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. T3 - ZIB-Report - SC-97-23 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2925 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Weismantel, Robert T1 - Set Packing Relaxations of Some Integer Programs N2 - 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. T3 - ZIB-Report - SC-97-30 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2998 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Weismantel, Robert T1 - Discrete Relaxations of Combinatorial Programs N2 - 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. T3 - ZIB-Report - SC-97-54 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3230 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Klostermeier, Fridolin A1 - Küttner, Christian T1 - Optimierung des Berliner Behindertenfahrdienstes N2 - 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. T3 - ZIB-Report - SC-97-10 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2799 ER -