@inproceedings{Groetschel1984, author = {Gr{\"o}tschel, Martin}, title = {Polyhedral Combinatorics}, booktitle = {COMBINATORIAL OPTIMIZATION}, editor = {O'Heigeartaigh, Michael and Lenstra, Jan and Kan, Alexander}, publisher = {Wiley}, pages = {1 -- 10}, year = {1984}, language = {en} } @techreport{Groetschel1984, author = {Gr{\"o}tschel, Martin}, title = {Polyedrische Kombinatorik und Schnittebenenverfahren}, number = {231}, publisher = {Forschungszentrum Graz, {\"O}sterreich}, year = {1984}, language = {en} } @article{GroetschelJuengerReinelt1984, author = {Gr{\"o}tschel, Martin and J{\"u}nger, Michael and Reinelt, Gerhard}, title = {A Cutting Plane Algorithm for the Linear Ordering Problem}, volume = {32}, journal = {Operations Research}, number = {6}, pages = {1195 -- 1220}, year = {1984}, language = {en} } @article{BorndoerferGroetschelPfetsch2007, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Pfetsch, Marc}, title = {A Column-Generation Approach to Line Planning in Public Transport}, volume = {41}, journal = {Transportation Science (INFORMS)}, number = {1}, doi = {10.1287/trsc.1060.0161}, pages = {123 -- 132}, year = {2007}, language = {en} } @misc{GroetschelLoebelVoelker1996, author = {Gr{\"o}tschel, Martin and L{\"o}bel, Andreas and V{\"o}lker, Manfred}, title = {Optimierung des Fahrzeugumlaufs im {\"O}ffentlichen Nahverkehr}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2195}, number = {SC-96-08}, year = {1996}, abstract = {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.}, language = {de} } @misc{AscheuerFischettiGroetschel1997, author = {Ascheuer, Norbert and Fischetti, Matteo and Gr{\"o}tschel, Martin}, title = {A polyhedral study of the asymmetric travelling salesman problem with time windows}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2807}, number = {SC-97-11}, year = {1997}, abstract = {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.}, language = {en} } @misc{AlevrasGroetschelWessaely1997, author = {Alevras, Dimitris and Gr{\"o}tschel, Martin and Wess{\"a}ly, Roland}, title = {Cost-Efficient Network Synthesis from Leased Lines}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2912}, number = {SC-97-22}, year = {1997}, abstract = {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.}, language = {en} } @misc{AlevrasGroetschelWessaely1997, author = {Alevras, Dimitris and Gr{\"o}tschel, Martin and Wess{\"a}ly, Roland}, title = {Capacity and Survivability Models for Telecommunication Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2931}, number = {SC-97-24}, year = {1997}, abstract = {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.}, language = {en} } @misc{DalitzGroetschelLuegger1997, author = {Dalitz, Wolfgang and Gr{\"o}tschel, Martin and L{\"u}gger, Joachim}, title = {Information Services for Mathematics in the Internet (Math-Net)}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2949}, number = {SC-97-25}, year = {1997}, abstract = {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.}, 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{AlevrasGroetschelJonasetal.1996, author = {Alevras, Dimitris and Gr{\"o}tschel, Martin and Jonas, Peter and Paul, Ulrich and Wess{\"a}ly, Roland}, title = {Survivable Mobile Phone Architectures: Models and Solution Methods}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2582}, number = {SC-96-48}, year = {1996}, abstract = {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.}, language = {en} } @misc{AlevrasGroetschelWessaely1996, author = {Alevras, Dimitris and Gr{\"o}tschel, Martin and Wess{\"a}ly, Roland}, title = {A Network Dimensioning Tool}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2591}, number = {SC-96-49}, year = {1996}, abstract = {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.}, language = {en} } @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{AbdelHamidAscheuerGroetscheletal.1995, author = {Abdel-Hamid, Atef Abdel-Aziz and Ascheuer, Norbert and Gr{\"o}tschel, Martin and Schorer, Herbert}, title = {Simulation und Optimierung einer PC-Fertigung unter Echtzeitbedingungen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1700}, number = {SC-95-04}, year = {1995}, abstract = {Die Business Unit PC in Augsburg ist die zentrale Produktionsst{\"a}tte der Siemens--Nixdorf Informationssysteme (SNI) AG f{\"u}r Personal Computer sowie f{\"u}r einige Periph{\"a}rger{\"a}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{\"u}r ein zu geringes Produktionsvolumen ausgelegt war und einige Komponenten des Systems Engp{\"a}sse im Produktionsbetrieb darstellen. Das Management suchte nach M{\"o}glichkeiten, den Produktionsfluß zu verbessern, ohne teure technische {\"A}nderungen am System vornehmen zu m{\"u}ssen. Eine Forschungsgruppe des Konrad--Zuse--Zentrums f{\"u}r Informationstechnik (die ehemals an der Universit{\"a}t Augsburg ans{\"a}ssig war) analysierte, unterst{\"u}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{\"a}tze, die hier dargestellt werden sollen, sind teilweise schon in Gr{\"o}tschel [Gr{\"o}92] angesprochen worden.}, language = {de} } @misc{GroetschelPadberg1994, author = {Gr{\"o}tschel, Martin and Padberg, Manfred}, title = {Ulysses 2000: In Search of Optimal Solutions to Hard Combinatorial Problems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1296}, number = {SC-93-34}, year = {1994}, abstract = {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.)}, language = {en} } @misc{GroetschelMonmaStoer1993, author = {Gr{\"o}tschel, Martin and Monma, Clyde and Stoer, Mechthild}, title = {Design of Survivable Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1054}, number = {SC-93-09}, year = {1993}, language = {en} } @misc{GroetschelLovasz1993, author = {Gr{\"o}tschel, Martin and Lov{\´a}sz, L{\´a}szlo}, title = {Combinatorial Optimization.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1098}, number = {SC-93-13}, year = {1993}, abstract = {This paper will appear as Chapter 28 of the forthcoming "Handbook on Combinatorics" (editors: R. Graham, M. Gr{\"o}tschel, L. Lovasz) to be published in 1994, by North-Holland.}, language = {en} } @misc{GodsilGroetschelWelsh1992, author = {Godsil, C. D. and Gr{\"o}tschel, Martin and Welsh, D. J. A.}, title = {Combinatorics in Statistical Physics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-694}, number = {SC-91-19}, year = {1992}, language = {en} } @misc{Groetschel1992, author = {Gr{\"o}tschel, Martin}, title = {Discrete Mathematics in Manufacturing.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-738}, number = {SC-92-03}, year = {1992}, abstract = {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.}, language = {en} } @misc{GroetschelMonmaStoer1992, author = {Gr{\"o}tschel, Martin and Monma, Clyde and Stoer, Mechthild}, title = {A Polyhedral Approach to Network Connectivity Problems (Extended Abstract).}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-924}, number = {SC-92-22}, year = {1992}, abstract = {We present a polyhedral approach for the general problem of designing a minimum-cost network with specified connectivity requir}, language = {en} } @misc{GroetschelMonmaStoer1993, author = {Gr{\"o}tschel, Martin and Monma, Clyde and Stoer, Mechthild}, title = {Polyhedral and Computational Investigations for Designing Communication Networks with High Survivability Requirements.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-944}, number = {SC-92-24}, year = {1993}, abstract = {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\$}}, language = {en} } @misc{AscheuerGroetschelKrumkeetal.1998, author = {Ascheuer, Norbert and Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Combinatorial Online Optimization}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3674}, number = {SC-98-24}, year = {1998}, abstract = {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.}, language = {en} } @misc{GroetschelDalitzWinczewski1998, author = {Gr{\"o}tschel, Martin and Dalitz, Wolfgang and Winczewski, Vincent}, title = {Math-Net: Ein Informationssystem der Mathematik}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3680}, number = {SC-98-25}, year = {1998}, abstract = {In diesem Artikel geben wir einen {\"U}berblick {\"u}ber das Math-Net-Projekt. Wir berichten {\"u}ber die organisatorischen und technischen Vorgehensweisen beim Aufbau eines verteilten Informationssystems f{\"u}r die Mathematik in Deutschland.}, language = {de} } @misc{GroetschelLuegger1998, author = {Gr{\"o}tschel, Martin and L{\"u}gger, Joachim}, title = {Scientific Information Systems and Metadata}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3698}, number = {SC-98-26}, year = {1998}, abstract = {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} .}, language = {en} } @misc{AbdelHamidAscheuerGroetschel1998, author = {Abdel-Hamid, Atef Abdel-Aziz and Ascheuer, Norbert and Gr{\"o}tschel, Martin}, title = {Order Picking in an Automatic Warehouse: Solving Online Asymmetric TSPs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3519}, number = {SC-98-08}, year = {1998}, abstract = {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.}, language = {en} } @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{BleyGroetschelWessaely1998, author = {Bley, Andreas and Gr{\"o}tschel, Martin and Wess{\"a}ly, Roland}, title = {Design of Broadband Virtual Private Networks: Model and Heuristics for the B-WiN}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3565}, number = {SC-98-13}, year = {1998}, abstract = {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.}, language = {en} } @incollection{Groetschel2005, author = {Gr{\"o}tschel, Martin}, title = {Der junge Albring und Schwelm}, booktitle = {Der Forscher und der Zweifler - Werner Albring zum 90. Geburtstag}, editor = {der Wissenschaften, Berlin-Brandenburgische}, publisher = {Berlin-Brandenburgische Akademie der Wissenschaften}, pages = {11 -- 35}, year = {2005}, language = {en} } @incollection{GroetschelHillerTuchscherer2009, author = {Gr{\"o}tschel, Martin and Hiller, Benjamin and Tuchscherer, Andreas}, title = {Structuring a Dynamic Environment}, booktitle = {Emergence, Analysis and Evolution of Structures. Concepts and Strategies Across Disciplines}, editor = {Lucas, Klaus and Roosen, Peter}, publisher = {Springer}, doi = {10.1007/978-3-642-00870-2}, pages = {199 -- 214}, year = {2009}, language = {en} } @incollection{GroetschelKochHoang2010, author = {Gr{\"o}tschel, Martin and Koch, Thorsten and Hoang, Nam-Dung}, title = {Lagenwechsel minimieren - oder das Bohren von L{\"o}chern in Leiterplatten}, booktitle = {Besser als Mathe}, editor = {Biermann, Katja and Gr{\"o}tschel, Martin and Lutz-Westphal, Brigitte}, publisher = {Vieweg+Teubner}, doi = {10.1007/978-3-658-01004-1_19}, pages = {161 -- 174}, year = {2010}, language = {en} } @incollection{Groetschel2008, author = {Gr{\"o}tschel, Martin}, title = {Tiefensuche}, volume = {58}, booktitle = {Kosmos und Zahl - Beitr{\"a}ge zur Mathematik- und Astronomiegeschichte, zu Alexander von Humboldt und Leibniz}, editor = {Hecht, Hartmut and Mikosch, Regina and Schwarz, Ingo and Siebert, Harald and Werther, Romy}, publisher = {Franz Steiner Verlag}, pages = {331 -- 346}, year = {2008}, language = {en} } @incollection{GroetschelLuegger2007, author = {Gr{\"o}tschel, Martin and L{\"u}gger, Joachim}, title = {Die Wissenschaftsgalaxis}, booktitle = {eUniversity - Update Bologna}, editor = {Keil, Reinhard and Kerres, Michael and Schulmeister, Rolf}, publisher = {Waxmann Verlag}, pages = {335 -- 354}, year = {2007}, language = {en} } @incollection{Groetschel2008, author = {Gr{\"o}tschel, Martin}, title = {Geistiges Eigentum - Eine Zusammenfassung der vorgetragenen Standpunkte}, volume = {Heft 7}, booktitle = {Geistiges Eigentum - Streitgespr{\"a}che in den Wissenschaftlichen Sitzungen der Versammlung der Berlin-Brandenburgischen Akademie der Wissenschaften}, editor = {der Wissenschaften, Berlin-Brandenburgische}, publisher = {Berlin-Brandenburgische Akademie der Wissenschaften}, pages = {89 -- 95}, year = {2008}, language = {en} } @incollection{Groetschel2008, author = {Gr{\"o}tschel, Martin}, title = {Geistiges Eigentum - Einf{\"u}hrung in das Thema}, volume = {Heft 7}, booktitle = {Geistiges Eigentum - Streitgespr{\"a}che in den Wissenschaftlichen Sitzungen der Versammlung der Berlin-Brandenburgischen Akademie der Wissenschaften}, editor = {der Wissenschaften, Berlin-Brandenburgische}, publisher = {Berlin-Brandenburgische Akademie der Wissenschaften}, pages = {9 -- 14}, year = {2008}, language = {en} } @incollection{Groetschel2007, author = {Gr{\"o}tschel, Martin}, title = {Schnelle Rundreisen}, booktitle = {Kombinatorische Optimierung erleben - In Studium und Unterricht}, editor = {Hußmann, Stephan and Lutz-Westphal, Brigitte}, publisher = {Vieweg}, address = {Wiesbaden}, pages = {95 -- 128}, year = {2007}, language = {en} } @misc{Groetschel2007, author = {Gr{\"o}tschel, Martin}, title = {Das Problem mit der Komplexit{\"a}t}, journal = {Kombinatorische Optimierung erleben - In Studium und Unterricht}, editor = {Hußmann, Stephan and Lutz-Westphal, Brigitte}, publisher = {Vieweg}, address = {Wiesbaden}, doi = {10.1007/978-3-8348-9120-4_9}, pages = {265 -- 274}, year = {2007}, language = {en} } @incollection{Groetschel2004, author = {Gr{\"o}tschel, Martin}, title = {Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes}, booktitle = {The Sharpest Cut}, editor = {Gr{\"o}tschel, Martin}, publisher = {MPS-SIAM}, pages = {99 -- 120}, year = {2004}, language = {en} } @incollection{Groetschel2005, author = {Gr{\"o}tschel, Martin}, title = {In der Mathematik sind sich alle einig und die Gesellschaft hat von ihr nichts zu bef{\"u}rchten}, volume = {2}, booktitle = {Wissenschaft Kontrovers}, publisher = {Chronos, Edition Collegium Helveticum}, address = {Z{\"u}rich}, year = {2005}, language = {en} } @incollection{Groetschel2008, author = {Gr{\"o}tschel, Martin}, title = {Ohne x is nix}, volume = {14}, booktitle = {Berichte und Abhandlungen}, editor = {der Wissenschaften, Berlin-Brandenburgische}, publisher = {Akademie-Verlag}, address = {Berlin}, pages = {195 -- 219}, year = {2008}, language = {en} } @misc{Groetschel2008, author = {Gr{\"o}tschel, Martin}, title = {Tiefensuche: Bemerkungen zur Algorithmengeschichte}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9628}, number = {08-23}, year = {2008}, abstract = {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{\"a}ftigte, wurde mir bewusst, wie schwierig dieses „Gesch{\"a}ft" ist. Man muss nicht nur mehrere (alte) Sprachen beherrschen, sondern auch die wissenschaftliche Bedeutung von Begriffen und Symbolen in fr{\"u}heren Zeiten kennen. Man muss zus{\"a}tzlich herausfinden, was zur Zeit der Entstehung der Texte „allgemeines Wissen" war, insbesondere, was seinerzeit g{\"u}ltige Beweisideen und -schritte waren, und daher damals keiner pr{\"a}zisen Definition oder Einf{\"u}hrung bedurfte. Es gibt aber noch eine Steigerung des historischen Schwierigkeitsgrades: Algorithmengeschichte. Dies m{\"o}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{\"a}gliches Leben oft von funktionierenden Algorithmen abh{\"a}ngt. Daher w{\"a}re eine bessere Kenntnis der Algorithmengeschichte von großem Interesse.}, language = {de} } @misc{GroetschelLutzWestphal2008, author = {Gr{\"o}tschel, Martin and Lutz-Westphal, Brigitte}, title = {Diskrete Mathematik und ihre Anwendungen: Auf dem Weg zu authentischem Mathematikunterricht}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10758}, number = {08-21}, year = {2008}, abstract = {Das heutige Leben ist durchdrungen von komplexen Technologien. Ohne Kommunikationsnetze, Internet, Mobilfunk, Logistik, Verkehrstechnik, medizinische Apparate, etc. k{\"o}nnte die moderne Gesellschaft nicht funktionieren. Fast alle dieser Technologien haben einen hohen Mathematikanteil. Der "normale B{\"u}rger"' weiss davon nichts, der Schulunterricht k{\"o}nnte dem ein wenig abhelfen. Einige mathematische Aspekte dieser Technologien sind einfach und sogar spielerisch intuitiv zug{\"a}nglich. Solche Anwendungen, die zus{\"a}tzlich noch der Lebensumwelt der Sch{\"u}ler zugeh{\"o}ren, k{\"o}nnen dazu genutzt werden, die mathematische Modellierung, also die mathematische Herangehensweise an die L{\"o}sung praktischer Fragen, anschaulich zu erl{\"a}utern. Gerade in der diskreten Mathematik k{\"o}nnen hier, quasi "nebenbei" mathematische Theorien erarbeitet und Teilaspekte (Definitionen, Fragestellungen, einfache Sachverhalte) durch eigenst{\"a}ndiges Entdecken der Sch{\"u}ler entwickelt werden. Wir beginnen mit einigen Beispielen.}, language = {de} } @incollection{GroetschelKrumkeRambauetal.2001, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg and Winter, Thomas and Zimmermann, Uwe}, title = {Combinatorial Online Optimization in Real Time}, booktitle = {Online Optimization of Large Scale Systems}, editor = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, publisher = {Springer}, pages = {679 -- 704}, year = {2001}, language = {en} } @incollection{GroetschelKrumkeRambau2001, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Online Optimization of Complex Transportation Systems}, booktitle = {Online Optimization of Large Scale Systems}, editor = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, publisher = {Springer}, pages = {705 -- 729}, year = {2001}, language = {en} } @misc{GroetschelRaackWerner2013, author = {Gr{\"o}tschel, Martin and Raack, Christian and Werner, Axel}, title = {Towards optimizing the deployment of optical access networks}, issn = {1438-0064}, doi = {10.1007/s13675-013-0016-x}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-18627}, year = {2013}, abstract = {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.}, language = {en} } @misc{Groetschel2012, author = {Gr{\"o}tschel, Martin}, title = {Einblicke in die Diskrete Mathematik}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14399}, number = {12-01}, year = {2012}, abstract = {„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{\"u}hren, Interesse an diesem Fachgebiet zu wecken und dazu anzuregen, dieses auch im Schulunterricht (ein wenig) zu ber{\"u}cksichtigen. Die Sch{\"u}ler und Sch{\"u}lerinnen werden daf{\"u}r dankbar sein - eine Erfahrung, die in vielen Unterrichtsreihen gemacht wurde.}, language = {de} } @misc{GroetschelHillerTuchscherer2007, author = {Gr{\"o}tschel, Martin and Hiller, Benjamin and Tuchscherer, Andreas}, title = {Combinatorial Online Optimization: Elevators \& Yellow Angels}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10360}, number = {07-36}, year = {2007}, abstract = {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.}, language = {en} } @misc{GroetschelNeumann2012, author = {Gr{\"o}tschel, Martin and Neumann, Gerald}, title = {10 Jahre TELOTA}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14799}, number = {12-13}, year = {2012}, abstract = {Das TELOTA-Projekt - zun{\"a}chst nur f{\"u}r zwei Jahre gestartet - feierte am 15. Juni 2011 sein 10-j{\"a}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 {\"O}ffentlichkeit finden. Die TELOTA-Aktivit{\"a}ten haben sich als wichtiger Bestandteil der IT-Infrastruktur der BBAW erwiesen, gehen aber weit {\"u}ber reinen Service hinaus. Sie beeinflussen die Forschung selbst und f{\"u}hren zu neuen interessanten wissenschaftlichen Fragestellungen. Der R{\"u}ckblick auf die ersten zehn Jahre der TELOTA-Initiative in diesem Artikel soll einen kleinen Eindruck von dem geben, was bisher geleistet wurde.}, language = {de} } @misc{GroetschelNemhauser2007, author = {Gr{\"o}tschel, Martin and Nemhauser, George}, title = {George Dantzig's contributions to integer programming}, issn = {1438-0064}, doi = {10.1016/j.disopt.2007.08.003}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10393}, number = {07-39}, year = {2007}, abstract = {This paper reviews George Dantzig's contribution to integer programming, especially his seminal work with Fulkerson and Johnson on the traveling salesman problem}, language = {en} } @incollection{GroetschelFonsecaDavis2001, author = {Gr{\"o}tschel, Martin and Fonseca, Irene and Davis, Mark}, title = {The Impact of Mathematical Research on Industry and Vice Versa}, booktitle = {Mathematical Glimpses into the 21st Century}, editor = {Casacuberta, Carles and Mir{\´o}-Roig, Rosa and Ortega, Joaqu{\´i}n and Xamb{\´o}-Descamps, Sebasti{\`a}}, edition = {First}, publisher = {Societat Catalana de Matem{\`a}tiques and Centro Internacional de M{\´e}todos Num{\´e}ricos en Ingenier{\´i}a}, address = {Barcelona, Spain}, pages = {35 -- 53}, year = {2001}, language = {en} } @incollection{GroetschelLoebelVoelker1997, author = {Gr{\"o}tschel, Martin and L{\"o}bel, Andreas and V{\"o}lker, Manfred}, title = {Optimierung des Fahrzeugumlaufs im {\"O}ffentlichen Nahverkehr}, booktitle = {Mathematik}, editor = {Hoffmann, Karl-Heinz and J{\"a}ger, Willi and Lohmann, Thomas and Schunck (Hrsg.), Hermann}, publisher = {Springer}, pages = {609 -- 624}, year = {1997}, language = {en} } @inproceedings{Groetschel2000, author = {Gr{\"o}tschel, Martin}, title = {Frequency Assignment in Mobile Phone Systems}, volume = {1974}, booktitle = {FST TCS 2000}, editor = {Kapoor, Sanjiv and Prasad, Sanjiva}, publisher = {Springer}, pages = {81 -- 86}, year = {2000}, language = {en} } @misc{GroetschelKrumkeRambauetal.2002, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg and Torres, Luis Miguel}, title = {Making the Yellow Angels Fly: Online Dispatching Of Service Vehicles in Real Time}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6858}, number = {02-18}, year = {2002}, abstract = {Combinatorial online optimization is an area with lots of applications and potential for significant progress, both in theory and practice. In this short note we sketch the ADACproblem, a typical large-scale online optimization problem, discuss some theoretical and pratical issues coming up, and explain, very briefly, how we approach this problem mathematically. Online problems are a battlefield of heuristics with many strong claims about their solution quality. We indicate that a stronger problem orientation and the use of a little more mathematics may yield.}, language = {en} }