TY - CHAP A1 - Grötschel, Martin ED - Bollobás, Béla T1 - On Intersections of Longest Cycles T2 - Graph Theory and Combinatorics Y1 - 1984 SP - 171 EP - 189 PB - Academic Press ER - TY - CHAP A1 - Grötschel, Martin ED - Jäger, Willi ED - Moser, J. ED - Remmert, R. T1 - Developments in combinatorial optimization T2 - Perspectives in Mathematics (Anniversary of Oberwolfach 1984) Y1 - 1984 SP - 249 EP - 294 PB - Birkhäuser CY - Basel ER - TY - CHAP A1 - Grötschel, Martin ED - O’Heigeartaigh, Michael ED - Lenstra, Jan ED - Kan, Alexander T1 - Polyhedral Combinatorics T2 - COMBINATORIAL OPTIMIZATION Y1 - 1984 SP - 1 EP - 10 PB - Wiley ER - TY - RPRT A1 - Grötschel, Martin T1 - Polyedrische Kombinatorik und Schnittebenenverfahren Y1 - 1984 IS - 231 PB - Forschungszentrum Graz, Österreich ER - TY - JOUR A1 - Grötschel, Martin A1 - Jünger, Michael A1 - Reinelt, Gerhard T1 - A Cutting Plane Algorithm for the Linear Ordering Problem JF - Operations Research Y1 - 1984 VL - 32 IS - 6 SP - 1195 EP - 1220 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Pfetsch, Marc T1 - A Column-Generation Approach to Line Planning in Public Transport JF - Transportation Science (INFORMS) Y1 - 2007 U6 - https://doi.org/10.1287/trsc.1060.0161 VL - 41 IS - 1 SP - 123 EP - 132 ER - TY - GEN A1 - Grötschel, Martin A1 - Löbel, Andreas A1 - Völker, Manfred T1 - Optimierung des Fahrzeugumlaufs im Öffentlichen Nahverkehr N2 - This paper addresses the problem of scheduling vehicles in a public mass transportation system. We show how this problem can be modelled as a special multicommodity flow problem and outline the solution methodology we have developed. Based on polyhedral investigations, we have designed and implemented a branch&cut algorithm and various heuristics with which real vehicle scheduling problems of truely large scale can be solved to optimality. We describe some implementation issues and report computational results. T3 - ZIB-Report - SC-96-08 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2195 ER - TY - GEN A1 - Ascheuer, Norbert A1 - Fischetti, Matteo A1 - Grötschel, Martin T1 - A polyhedral study of the asymmetric travelling salesman problem with time windows N2 - The asymmetric travelling salesman problem with time windows (ATSP-TW) is a basic model for scheduling and routing applications. In this paper we present a formulation of the problem involving only 0/1-variables associated with the arcs of the underlying digraph. This has the advantage of avoiding additional variables as well as the associated (typically very ineffective) linking constraints. In the formulation, time window restrictions are modelled by means of ``infeasible path elimination'' constraints. We present the basic form of these constraints along with some possible strengthenings. Several other classes of valid inequalities derived from related asymmetric travelling salesman problems are also described, along with a lifting theorem. We also study the ATSP-TW polytope, $P_{TW}$, defined as the convex hull of the integer solutions of our model. We show that determining the dimension of $P_{TW}$ is strongly {\em NP}--complete problem, even if only one time window is present. In this latter case, we provide a minimal equation system for $P_{TW}$. Computational experiments on the new formulation are reported in a companion paper [1997] where we show that it outperforms alternative formulations on some classes of problem instances. T3 - ZIB-Report - SC-97-11 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2807 ER - TY - GEN A1 - Alevras, Dimitris A1 - Grötschel, Martin A1 - Wessäly, Roland T1 - Cost-Efficient Network Synthesis from Leased Lines N2 - Given a communication demand between each pair of nodes of a network we consider the problem of deciding what capacity to install on each edge of the network in order to minimize the building cost of the network and to satisfy the demand between each pair of nodes. The feasible capacities that can be leased from a network provider are of a particular kind in our case. There are a few so-called basic capacities having the property that every basic capacity is an integral multiple of every smaller basic capacity. An edge can be equipped with a capacity only if it is an integer combination of the basic capacities. We treat, in addition, several restrictions on the routings of the demands (length restriction, diversification) and failures of single nodes or single edges. We formulate the problem as a mixed integer linear programming problem and develop a cutting plane algorithm as well as several heuristics to solve it. We report on computational results for real world data. T3 - ZIB-Report - SC-97-22 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2912 ER - TY - GEN A1 - Alevras, Dimitris A1 - Grötschel, Martin A1 - Wessäly, Roland T1 - Capacity and Survivability Models for Telecommunication Networks N2 - Designing low-cost networks that survive certain failure situations is one of the prime tasks in the telecommunication industry. In this paper we survey the development of models for network survivability used in practice in the last ten years. We show how algorithms integrating polyhedral combinatorics, linear programming, and various heuristic ideas can help solve real-world network dimensioning instances to optimality or within reasonable quality guarantees in acceptable running times. The most general problem type we address is the following. Let a communication demand between each pair of nodes of a telecommunication network be given. We consider the problem of choosing, among a discrete set of possible capacities, which capacity to install on each of the possible edges of the network in order to (i) satisfy all demands, (ii) minimize the building cost of the network. \noindent In addition to determining the network topology and the edge capacities we have to provide, for each demand, a routing such that (iii) no path can carry more than a given percentage of the demand, (iv) no path in the routing exceeds a given length. \noindent We also have to make sure that (v) for every single node or edge failure, a certain percentage of the demand is reroutable. \noindent Moreover, for all failure situations feasible routings must be computed. The model described above has been developed in cooperation with a German mobile phone provider. We present a mixed-integer programming formulation of this model and computational results with data from practice. T3 - ZIB-Report - SC-97-24 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2931 ER - TY - GEN A1 - Dalitz, Wolfgang A1 - Grötschel, Martin A1 - Lügger, Joachim T1 - Information Services for Mathematics in the Internet (Math-Net) N2 - The present paper gives a brief description of the Math-Net project which is carried out by nine mathematical institutions in Germany, supported by Deutsches Forschungsnetz (DFN) and Deutsche Telekom. The project aims at setting up the technical and organizational infrastructure for efficient, inexpensive and user-driven information services for mathematics. With the aid of active (structured retrieval mechanisms) and passive (profile services) components, electronic mathematical information in Germany will be made available to the scientist at his workplace. The emphasis is put on information about publications, software and data collections, teaching and research activities, but also on organizational and bibliographical information. Decentral organization structures, distributed search systems as well as the use of meta-information (metadata) in accordance with the Dublin Core (hopefully) guarantee a longterm, high-quality repository of data. The well-known mathematical software and data collection netlib\/ will be used as an example to illustrate how such a collection can be adapted to Math-Net. An integration of netlib into HyperWave offers additional perspectives and functionalities. T3 - ZIB-Report - SC-97-25 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2949 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Herzog, Werner A1 - Klostermeier, Fridolin A1 - Konsek, Wilhelm A1 - Küttner, Christian T1 - Kürzen muß nicht Kahlschlag heißen - das Beispiel Telebus-Behindertenfahrdienst Berlin N2 - 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. T3 - ZIB-Report - SC-96-41 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2510 ER - TY - GEN A1 - Alevras, Dimitris A1 - Grötschel, Martin A1 - Jonas, Peter A1 - Paul, Ulrich A1 - Wessäly, Roland T1 - Survivable Mobile Phone Architectures: Models and Solution Methods N2 - In the highly competitive area of telecommunications, cost, quality, and network management are among the most important aspects to be considered when designing a network. We study the problem of dimensioning a telecommunication network that is still operating in case of a failure of a network component. Given a demand between each pair of nodes of a telecommunication network and a finite set of possible capacities for each edge of the network, we consider the problem of deciding what capacity to install on each edge of the network in order to minimize the building cost of the network and to satisfy the demand between each pair of nodes, even if a network component fails. The routing of the demands must satisfy the following additional restrictions: (a) there is a maximum number of nodes allowed in each path between any pair of nodes (path length restriction), and (b) there is a maximum percentage of the demand between each pair of nodes that can be routed through any network component (diversification restriction). Moreover, the chosen capacities must be such that, for every single node or single edge failure, a certain percentage of the demand between any pair of nodes is reroutable (i.e. it ``survives'' the particular failure). We formulate the problem as a mixed integer linear programming problem and present a cutting plane algorithm as well as several heuristics for its solution. Furthermore, we discuss several ways to implement survivability into a telecommunication network. T3 - ZIB-Report - SC-96-48 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2582 ER - TY - GEN A1 - Alevras, Dimitris A1 - Grötschel, Martin A1 - Wessäly, Roland T1 - A Network Dimensioning Tool N2 - Designing low cost networks that survive certain failure situations belongs to one of the prime tasks in the telecommunications industry. In this paper we describe a mathematical model combining several aspects of survivability that are elsewhere treated in a hierarchical fashion. We present mathematical investigations of this integrated model, a cutting plane algorithm, as well as several heuristics for its solution. Moreover, we report computational results with real world data. The problem we address is the following. Suppose, between each pair of nodes in a region, a communication demand is given. We want to determine the topology of a telecommunication network connecting the given nodes and to dimension all potential physical links. For each link, the possible capacities are restricted to a given finite set. The capacities must be chosen such that the communication demands are satisfied, even if certain network components fail, and such that the network building costs are as small as possible. Moreover, for each pair of nodes and each failure situation, we want to determine the paths on which the demand between the nodes is routed. T3 - ZIB-Report - SC-96-49 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2591 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Klostermeier, Fridolin A1 - Küttner, Christian T1 - Telebus Berlin - Mobilität für Behinderte N2 - 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. T3 - ZIB-Report - SC-96-40 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2500 ER - TY - GEN A1 - Abdel-Hamid, Atef Abdel-Aziz A1 - Ascheuer, Norbert A1 - Grötschel, Martin A1 - Schorer, Herbert T1 - Simulation und Optimierung einer PC-Fertigung unter Echtzeitbedingungen N2 - Die Business Unit PC in Augsburg ist die zentrale Produktionsstätte der Siemens--Nixdorf Informationssysteme (SNI) AG für Personal Computer sowie für einige Periphärgeräte. Das Werk, entworfen nach modernen CIM/CAI--Konzepten (Computer Integrated Manufacturing/ Computer Aided Industry), wurde 1987 errichtet. Bald zeigte sich jedoch, daß es für ein zu geringes Produktionsvolumen ausgelegt war und einige Komponenten des Systems Engpässe im Produktionsbetrieb darstellen. Das Management suchte nach Möglichkeiten, den Produktionsfluß zu verbessern, ohne teure technische Änderungen am System vornehmen zu müssen. Eine Forschungsgruppe des Konrad--Zuse--Zentrums für Informationstechnik (die ehemals an der Universität Augsburg ansässig war) analysierte, unterstützt von einigen Studenten und Ingenieuren der SNI, den Produktionsfluß und lokalisierte Schwachstellen. Basierend auf diesen Erkenntnissen wurden mathematische Fragestellungen erarbeitet und auf mathematischen Optimierungsverfahren basierende Softwarepakete entwickelt, die jetzt teilweise bei SNI im Einsatz sind. Im folgenden werden einige dieser Fragestellungen, deren Modellierung und mathematische Behandlung beschrieben. Einige der Ansätze, die hier dargestellt werden sollen, sind teilweise schon in Grötschel [Grö92] angesprochen worden. T3 - ZIB-Report - SC-95-04 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1700 ER - TY - GEN A1 - Grötschel, Martin A1 - Padberg, Manfred T1 - Ulysses 2000: In Search of Optimal Solutions to Hard Combinatorial Problems. N2 - Combinatorial optimization problems pervade many areas of human problem solving especially in the fields of business, economics and engineering. Intensive mathematical research and vast increases in raw computing power have advanced the state of the art in exact and heuristic problem solving at a pace that is unprecedented in human history. We survey here in layman's terms some of the fundamental concepts and principles that have led this progress. (This article will appear -- possibly in modified form -- in a popular science magazine.) T3 - ZIB-Report - SC-93-34 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1296 ER - TY - GEN A1 - Grötschel, Martin A1 - Monma, Clyde A1 - Stoer, Mechthild T1 - Design of Survivable Networks T3 - ZIB-Report - SC-93-09 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1054 ER - TY - GEN A1 - Grötschel, Martin A1 - Lovász, Lászlo T1 - Combinatorial Optimization. N2 - This paper will appear as Chapter 28 of the forthcoming "Handbook on Combinatorics" (editors: R. Graham, M. Grötschel, L. Lovasz) to be published in 1994, by North-Holland. T3 - ZIB-Report - SC-93-13 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1098 ER - TY - GEN A1 - Godsil, C. D. A1 - Grötschel, Martin A1 - Welsh, D. J. A. T1 - Combinatorics in Statistical Physics T3 - ZIB-Report - SC-91-19 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-694 ER - TY - GEN A1 - Grötschel, Martin T1 - Discrete Mathematics in Manufacturing. N2 - Manufacturing is a topic that provides rich opportunities for important mathematical contributions to real-world problems. The purpose of this paper is to show, by means of several examples, where and how mathematical problems of a discrete nature arise in manufacturing and to demonstrate the savings and improvements that can be achieved by employing the techniques of combinatorial optimization. The topics covered range from the design phase of a product (e. g.,routing, placement and via minimization in VLSI design), the control of CNC machines (e. g., drilling and plotting), to the management of assembly lines, storage systems and whole factories. We also point out difficulties in the modelling of complex situations and outline the algorithmic methods that are used for the solution of the mathematical problems arising in manufacturing. {\bf Key words:} discrete mathematics , combinatorial optimization, applications to manufacturing. T3 - ZIB-Report - SC-92-03 KW - discrete mathematics KW - combinatorial optimization KW - applications to manufacturing Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-738 ER - TY - GEN A1 - Grötschel, Martin A1 - Monma, Clyde A1 - Stoer, Mechthild T1 - A Polyhedral Approach to Network Connectivity Problems (Extended Abstract). N2 - We present a polyhedral approach for the general problem of designing a minimum-cost network with specified connectivity requir T3 - ZIB-Report - SC-92-22 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-924 ER - TY - GEN A1 - Grötschel, Martin A1 - Monma, Clyde A1 - Stoer, Mechthild T1 - Polyhedral and Computational Investigations for Designing Communication Networks with High Survivability Requirements. N2 - We consider the important practical and theoretical problem of designing a low-cost communications network which can survive failures of certain network components. Our initial interest in this area was motivated by the need to design certain ``two-connected" survivable topologies for fiber optic communication networks of interest to the regional telephone companies. In this paper, we describe some polyhedral results for network design problems with higher connectivity requirements. We also report on some preliminary computational results for a cutting plane algorithm for various real-world and random problems with high connectivity requirements which shows promise for providing good solutions to these difficult problems. \def\NP{$\cal NP$} T3 - ZIB-Report - SC-92-24 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-944 ER - TY - GEN A1 - Ascheuer, Norbert A1 - Grötschel, Martin A1 - Krumke, Sven A1 - Rambau, Jörg T1 - Combinatorial Online Optimization N2 - In ``classical'' optimization, all data of a problem instance are considered given. The standard theory and the usual algorithmic techniques apply to such cases only. Online optimization is different. Many decisions have to be made before all data are available. In addition, decisions once made cannot be changed. How should one act ``best'' in such an environment? In this paper we survey online problems coming up in combinatorial optimization. We first outline theoretical concepts, such as competitiveness against various adversaries, to analyze online problems and algorithms. The focus, however, lies on real-world applications. We report, in particular, on theoretical investigations and our practical experience with problems arising in transportation and the automatic handling of material. T3 - ZIB-Report - SC-98-24 KW - Online Optimization KW - competitiveness KW - combinatorial optimization KW - real-world problems Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3674 ER - TY - GEN A1 - Grötschel, Martin A1 - Dalitz, Wolfgang A1 - Winczewski, Vincent T1 - Math-Net: Ein Informationssystem der Mathematik N2 - In diesem Artikel geben wir einen Überblick über das Math-Net-Projekt. Wir berichten über die organisatorischen und technischen Vorgehensweisen beim Aufbau eines verteilten Informationssystems für die Mathematik in Deutschland. T3 - ZIB-Report - SC-98-25 KW - Information System KW - Math-Net KW - Math-Net-Links KW - Dublin Core KW - Harvest Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3680 ER - TY - GEN A1 - Grötschel, Martin A1 - Lügger, Joachim T1 - Scientific Information Systems and Metadata N2 - This article begins with a short survey on the history of the classification of knowledge. It briefly discusses the traditional means of keeping track of scientific progress, i.e., collecting, classifying, abstracting, and reviewing all publications in a field. The focus of the article, however, is on modern electronic information and communication systems that try to provide high-quality information by automatic document retrieval or by using metadata, a new tool to guide search engines. We report, in particular, on efforts of this type made jointly by a number of German scientific societies. A full version of this paper including all hypertext references, links to online papers and references to the literature can be found under the URL: {\tt http://elib.zib.de/math.org.softinf.pub} . T3 - ZIB-Report - SC-98-26 KW - elektronisches Publizieren KW - Metadaten KW - Dublin Core KW - Klassifikation KW - Math-Net Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3698 ER - TY - GEN A1 - Abdel-Hamid, Atef Abdel-Aziz A1 - Ascheuer, Norbert A1 - Grötschel, Martin T1 - Order Picking in an Automatic Warehouse: Solving Online Asymmetric TSPs N2 - We report on a joint project with industry that had the aim to sequence transportation requests within an automatic storage system in such a way that the overall travel time is minimized. The manufacturing environment is such that scheduling decisions have to be made before all jobs are known. We have modeled this task as an \emph{online} Asymmetric Traveling Salesman Problem (ATSP). Several heuristics for the online ATSP are compared computationally within a simulation environment to judge which should be used in practice. Compared to the priority rule used so far, the optimization package reduced the unloaded travel time by about 40~\%. Because of these significant savings our procedure was implemented as part of the control software for the stacker cranes of the storage systems. T3 - ZIB-Report - SC-98-08 KW - Traveling Salesman Problem KW - Online-Algorithm KW - Automatic Storage System Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3519 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Löbel, Andreas T1 - Optimization of Transportation Systems N2 - 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. T3 - ZIB-Report - SC-98-09 KW - Transportation Systems KW - Optimization KW - Discrete Mathematics Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3529 ER - TY - GEN A1 - Bley, Andreas A1 - Grötschel, Martin A1 - Wessäly, Roland T1 - Design of Broadband Virtual Private Networks: Model and Heuristics for the B–WiN N2 - We investigate the problem of designing survivable broadband virtual private networks that employ the Open Shortest Path First (OSPF) routing protocol to route the packages. The capacities available for the links of the network are a minimal capacity plus multiples of a unit capacity. Given the directed communication demands between all pairs of nodes, we wish to select the capacities in a such way, that even in case of a single node or a single link failure a specified percentage of each demand can be satisfied and the costs for these capacities are minimal. We present a mixed--integer linear programming formulation of this problem and several heuristics for its solution. Furthermore, we report on computational results with real-world data. T3 - ZIB-Report - SC-98-13 KW - Telecommunication Network Design KW - Survivable Networks KW - Network Capacity Planning KW - OSPF Routing KW - Shortest Path Routing KW - Heuristics Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3565 ER - TY - CHAP A1 - Grötschel, Martin ED - der Wissenschaften, Berlin-Brandenburgische T1 - Der junge Albring und Schwelm T2 - Der Forscher und der Zweifler - Werner Albring zum 90. Geburtstag Y1 - 2005 SP - 11 EP - 35 PB - Berlin-Brandenburgische Akademie der Wissenschaften ER - TY - CHAP A1 - Grötschel, Martin A1 - Hiller, Benjamin A1 - Tuchscherer, Andreas ED - Lucas, Klaus ED - Roosen, Peter T1 - Structuring a Dynamic Environment T2 - Emergence, Analysis and Evolution of Structures. Concepts and Strategies Across Disciplines Y1 - 2009 UR - http://www.springer.com/engineering/book/978-3-642-00869-6 U6 - https://doi.org/10.1007/978-3-642-00870-2 SP - 199 EP - 214 PB - Springer ER - TY - CHAP A1 - Grötschel, Martin A1 - Koch, Thorsten A1 - Hoang, Nam-Dung ED - Biermann, Katja ED - Grötschel, Martin ED - Lutz-Westphal, Brigitte T1 - Lagenwechsel minimieren – oder das Bohren von Löchern in Leiterplatten T2 - Besser als Mathe Y1 - 2010 U6 - https://doi.org/10.1007/978-3-658-01004-1_19 SP - 161 EP - 174 PB - Vieweg+Teubner ER - TY - CHAP A1 - Grötschel, Martin ED - Hecht, Hartmut ED - Mikosch, Regina ED - Schwarz, Ingo ED - Siebert, Harald ED - Werther, Romy T1 - Tiefensuche T2 - Kosmos und Zahl - Beiträge zur Mathematik- und Astronomiegeschichte, zu Alexander von Humboldt und Leibniz Y1 - 2008 UR - http://www.steiner-verlag.de/titel/56734.html VL - 58 SP - 331 EP - 346 PB - Franz Steiner Verlag ER - TY - CHAP A1 - Grötschel, Martin A1 - Lügger, Joachim ED - Keil, Reinhard ED - Kerres, Michael ED - Schulmeister, Rolf T1 - Die Wissenschaftsgalaxis T2 - eUniversity - Update Bologna Y1 - 2007 UR - http://opus.kobv.de/zib/volltexte/2007/1014/ SP - 335 EP - 354 PB - Waxmann Verlag ER - TY - CHAP A1 - Grötschel, Martin ED - der Wissenschaften, Berlin-Brandenburgische T1 - Geistiges Eigentum – Eine Zusammenfassung der vorgetragenen Standpunkte T2 - Geistiges Eigentum – Streitgespräche in den Wissenschaftlichen Sitzungen der Versammlung der Berlin-Brandenburgischen Akademie der Wissenschaften Y1 - 2008 VL - Heft 7 SP - 89 EP - 95 PB - Berlin-Brandenburgische Akademie der Wissenschaften ER - TY - CHAP A1 - Grötschel, Martin ED - der Wissenschaften, Berlin-Brandenburgische T1 - Geistiges Eigentum – Einführung in das Thema T2 - Geistiges Eigentum – Streitgespräche in den Wissenschaftlichen Sitzungen der Versammlung der Berlin-Brandenburgischen Akademie der Wissenschaften Y1 - 2008 VL - Heft 7 SP - 9 EP - 14 PB - Berlin-Brandenburgische Akademie der Wissenschaften ER - TY - CHAP A1 - Grötschel, Martin ED - Hußmann, Stephan ED - Lutz-Westphal, Brigitte T1 - Schnelle Rundreisen T2 - Kombinatorische Optimierung erleben – In Studium und Unterricht Y1 - 2007 UR - http://www.viewegteubner.de/index.php;do=show/site=v/book_id=6158 SP - 95 EP - 128 PB - Vieweg CY - Wiesbaden ER - TY - GEN A1 - Grötschel, Martin ED - Hußmann, Stephan ED - Lutz-Westphal, Brigitte T1 - Das Problem mit der Komplexität T2 - Kombinatorische Optimierung erleben – In Studium und Unterricht Y1 - 2007 U6 - https://doi.org/10.1007/978-3-8348-9120-4_9 SP - 265 EP - 274 PB - Vieweg CY - Wiesbaden ER - TY - CHAP A1 - Grötschel, Martin ED - Grötschel, Martin T1 - Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes T2 - The Sharpest Cut Y1 - 2004 SP - 99 EP - 120 PB - MPS-SIAM ER - TY - CHAP A1 - Grötschel, Martin T1 - In der Mathematik sind sich alle einig und die Gesellschaft hat von ihr nichts zu befürchten T2 - Wissenschaft Kontrovers Y1 - 2005 VL - 2 PB - Chronos, Edition Collegium Helveticum CY - Zürich ER - TY - CHAP A1 - Grötschel, Martin ED - der Wissenschaften, Berlin-Brandenburgische T1 - Ohne x is nix T2 - Berichte und Abhandlungen Y1 - 2008 VL - 14 SP - 195 EP - 219 PB - Akademie-Verlag CY - Berlin ER - TY - GEN A1 - Grötschel, Martin T1 - Tiefensuche: Bemerkungen zur Algorithmengeschichte T1 - Depth-first search: Remarks on the history of algorithms N2 - Dieser kurze Aufsatz zur Algorithmengeschichte ist Eberhard Knobloch, meinem Lieblings-Mathematikhistoriker, zum 65. Geburtstag gewidmet. Eberhard Knobloch hat immer, wenn ich ihm eine historische Frage zur Mathematik stellte, eine Antwort gewusst – fast immer auch sofort. Erst als ich mich selbst ein wenig und dazu amateurhaft mit Mathematikgeschichte beschäftigte, wurde mir bewusst, wie schwierig dieses „Geschäft“ ist. Man muss nicht nur mehrere (alte) Sprachen beherrschen, sondern auch die wissenschaftliche Bedeutung von Begriffen und Symbolen in früheren Zeiten kennen. Man muss zusätzlich herausfinden, was zur Zeit der Entstehung der Texte „allgemeines Wissen“ war, insbesondere, was seinerzeit gültige Beweisideen und -schritte waren, und daher damals keiner präzisen Definition oder Einführung bedurfte. Es gibt aber noch eine Steigerung des historischen Schwierigkeitsgrades: Algorithmengeschichte. Dies möchte ich in diesem Artikel kurz darlegen in der Hoffnung, dass sich Wissenschaftshistoriker dieses Themas noch intensiver annehmen, als sie das bisher tun. Der Grund ist, dass heute Algorithmen viele Bereiche unserer Alltagswelt steuern und unser tägliches Leben oft von funktionierenden Algorithmen abhängt. Daher wäre eine bessere Kenntnis der Algorithmengeschichte von großem Interesse. T3 - ZIB-Report - 08-23 KW - Algorithmengeschichte KW - Algorithmus Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9628 SN - 1438-0064 ER - TY - GEN A1 - Grötschel, Martin A1 - Lutz-Westphal, Brigitte T1 - Diskrete Mathematik und ihre Anwendungen: Auf dem Weg zu authentischem Mathematikunterricht N2 - Das heutige Leben ist durchdrungen von komplexen Technologien. Ohne Kommunikationsnetze, Internet, Mobilfunk, Logistik, Verkehrstechnik, medizinische Apparate, etc. könnte die moderne Gesellschaft nicht funktionieren. Fast alle dieser Technologien haben einen hohen Mathematikanteil. Der "normale Bürger"' weiss davon nichts, der Schulunterricht könnte dem ein wenig abhelfen. Einige mathematische Aspekte dieser Technologien sind einfach und sogar spielerisch intuitiv zugänglich. Solche Anwendungen, die zusätzlich noch der Lebensumwelt der Schüler zugehören, können dazu genutzt werden, die mathematische Modellierung, also die mathematische Herangehensweise an die Lösung praktischer Fragen, anschaulich zu erläutern. Gerade in der diskreten Mathematik können hier, quasi "nebenbei" mathematische Theorien erarbeitet und Teilaspekte (Definitionen, Fragestellungen, einfache Sachverhalte) durch eigenständiges Entdecken der Schüler entwickelt werden. Wir beginnen mit einigen Beispielen. T3 - ZIB-Report - 08-21 KW - Diskrete Mathematik KW - Mathematikunterricht in Schulen KW - authentischer Mathematikunterricht Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10758 SN - 1438-0064 ER - TY - CHAP A1 - Grötschel, Martin A1 - Krumke, Sven A1 - Rambau, Jörg A1 - Winter, Thomas A1 - Zimmermann, Uwe ED - Grötschel, Martin ED - Krumke, Sven ED - Rambau, Jörg T1 - Combinatorial Online Optimization in Real Time T2 - Online Optimization of Large Scale Systems Y1 - 2001 SP - 679 EP - 704 PB - Springer ER - TY - CHAP A1 - Grötschel, Martin A1 - Krumke, Sven A1 - Rambau, Jörg ED - Grötschel, Martin ED - Krumke, Sven ED - Rambau, Jörg T1 - Online Optimization of Complex Transportation Systems T2 - Online Optimization of Large Scale Systems Y1 - 2001 SP - 705 EP - 729 PB - Springer ER - TY - GEN A1 - Grötschel, Martin A1 - Raack, Christian A1 - Werner, Axel T1 - Towards optimizing the deployment of optical access networks N2 - In this paper we study the cost-optimal deployment of optical access networks considering variants of the problem such as fiber to the home (FTTH), fiber to the building (FTTB), fiber to the curb (FTTC), or fiber to the neighborhood (FTTN). We identify the combinatorial structures of the most important sub-problems arising in this area and model these, e.g., as capacitated facility location, concentrator location, or Steiner tree problems. We discuss modeling alternatives as well. We finally construct a “unified” integer programming model that combines all sub-models and provides a global view of all these FTTx problems. We also summarize computational studies of various special cases. T3 - ZIB-Report - 13-11 KW - FTTx, FTTH, FTTB, FTTC, FTTN, telecommunications, access networks, passive optical networks, network design, routing, energy efficiency Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18627 SN - 1438-0064 ER - TY - GEN A1 - Grötschel, Martin T1 - Einblicke in die Diskrete Mathematik N2 - „Diskrete Mathematik, was ist das?“, ist eine typische Frage von Lehrern mit traditioneller Mathematikausbildung, denn dort kam und kommt diskrete Mathematik kaum vor. Die etwas Aufgeschlosseneren fragen: „Wenn (schon wieder) etwas Neues unterrichtet werden soll, was soll denn dann im Lehrplan gestrichen werden?“ Auf die zweite Frage wird hier nicht eingegangen. Das Ziel dieses Aufsatzes ist es, in diskrete Mathematik einzuführen, Interesse an diesem Fachgebiet zu wecken und dazu anzuregen, dieses auch im Schulunterricht (ein wenig) zu berücksichtigen. Die Schüler und Schülerinnen werden dafür dankbar sein – eine Erfahrung, die in vielen Unterrichtsreihen gemacht wurde. T3 - ZIB-Report - 12-01 KW - diskrete Mathematik Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14399 SN - 1438-0064 ER - TY - GEN A1 - Grötschel, Martin A1 - Hiller, Benjamin A1 - Tuchscherer, Andreas T1 - Combinatorial Online Optimization: Elevators & Yellow Angels N2 - In \emph{classical optimization} it is assumed that full information about the problem to be solved is given. This, in particular, includes that all data are at hand. The real world may not be so nice'' to optimizers. Some problem constraints may not be known, the data may be corrupted, or some data may not be available at the moments when decisions have to be made. The last issue is the subject of \emph{online optimization} which will be addressed here. We explain some theory that has been developed to cope with such situations and provide examples from practice where unavailable information is not the result of bad data handling but an inevitable phenomenon. T3 - ZIB-Report - 07-36 KW - Online-Optimierung KW - Aufzugssteuerung KW - Dispatching von Fahrzeugen KW - online optimization KW - elevator control KW - vehicle dispatching Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10360 SN - 1438-0064 ER - TY - GEN A1 - Grötschel, Martin A1 - Neumann, Gerald T1 - 10 Jahre TELOTA N2 - Das TELOTA-Projekt - zunächst nur für zwei Jahre gestartet - feierte am 15. Juni 2011 sein 10-jähriges Bestehen im Rahmen eines Workshops mit einem abschließenden Festvortrag von Richard Stallmann zum Thema „Copyright versus community in the age of computer networks“. Diese Veranstaltung zeigte, wie aktuell die TELOTA-Themen weiterhin sind und dass diese eine große Resonanz in der allgemeinen Öffentlichkeit finden. Die TELOTA-Aktivitäten haben sich als wichtiger Bestandteil der IT-Infrastruktur der BBAW erwiesen, gehen aber weit über reinen Service hinaus. Sie beeinflussen die Forschung selbst und führen zu neuen interessanten wissenschaftlichen Fragestellungen. Der Rückblick auf die ersten zehn Jahre der TELOTA-Initiative in diesem Artikel soll einen kleinen Eindruck von dem geben, was bisher geleistet wurde. T3 - ZIB-Report - 12-13 KW - BBAW KW - Telota Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14799 SN - 1438-0064 ER - TY - GEN A1 - Grötschel, Martin A1 - Nemhauser, George T1 - George Dantzig's contributions to integer programming N2 - This paper reviews George Dantzig's contribution to integer programming, especially his seminal work with Fulkerson and Johnson on the traveling salesman problem T3 - ZIB-Report - 07-39 KW - George Dantzig KW - integer programming KW - traveling salesman problem KW - TSP KW - mixed-integer programs Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10393 SN - 1438-0064 ER - TY - CHAP A1 - Grötschel, Martin A1 - Fonseca, Irene A1 - Davis, Mark ED - Casacuberta, Carles ED - Miró-Roig, Rosa ED - Ortega, Joaquín ED - Xambó-Descamps, Sebastià T1 - The Impact of Mathematical Research on Industry and Vice Versa T2 - Mathematical Glimpses into the 21st Century Y1 - 2001 SP - 35 EP - 53 PB - Societat Catalana de Matemàtiques and Centro Internacional de Métodos Numéricos en Ingeniería CY - Barcelona, Spain ET - First ER -