TY - BOOK A1 - Grötschel, Martin A1 - Lovász, Lászlo A1 - Schrijver, Alexander T1 - Geometric Algorithms and Combinatorial Optimization T3 - Algorithms and Combinatorics Y1 - 1988 SN - 3-540-13624-X, 0-387-13624-X (U.S.) VL - 2 PB - Springer ER - TY - JOUR A1 - Grötschel, Martin A1 - Jünger, Michael A1 - Reinelt, Gerhard T1 - Via Minimization with Pin Preassignments and Layer Preference JF - ZAMM – Zeitschrift für Angewandte Mathematik und Mechanik Y1 - 1989 VL - 69 IS - 11 SP - 393 EP - 399 ER - TY - JOUR A1 - Grötschel, Martin A1 - Truemper, Klaus T1 - Decomposition and Optimization over Cycles in Binary Matroids JF - Journal of Combinatorial Theory, Series B Y1 - 1989 VL - 46 IS - 3 SP - 306 EP - 337 ER - TY - JOUR A1 - Grötschel, Martin A1 - Truemper, Klaus T1 - Master Polytopes for Cycles of Binary Matroids JF - Linear Algebra and its Applications Y1 - 1989 VL - 114/115 SP - 523 EP - 540 ER - TY - JOUR A1 - Grötschel, Martin A1 - Wakabayashi, Yoshiko T1 - A cutting plane algorithm for a clustering problem JF - Mathematical Programming, Series B Y1 - 1989 VL - 45 SP - 59 EP - 96 PB - Mathematical Programming, Series B ER - TY - CHAP A1 - Ascheuer, Norbert A1 - Escudero, Laureano A1 - Grötschel, Martin A1 - Stoer, Mechthild ED - Kannan, Ravi ED - Pulleyblank, William T1 - On Identifying in Polynomial Time Violated Subtour Elimination and Precedence Forcing Constraints for the Sequential Ordering Problem T2 - Integer Programming and Combinatorial Optimization, Proceeedings of a Conference held at the University of Waterloo, May 28-30, 1990 Y1 - 1990 SP - 19 EP - 28 PB - University of Waterloo Press ER - TY - JOUR A1 - Grötschel, Martin A1 - Monma, Clyde T1 - Integer Polyhedra Arising from Certain Network Design Problems with Connectivity Constraints JF - SIAM Journal on Discrete Mathematics Y1 - 1990 VL - 3 IS - 4 SP - 502 EP - 523 ER - TY - JOUR A1 - Grötschel, Martin A1 - Wakabayashi, Yoshiko T1 - Facets of the clique partitioning polytope JF - Mathematical Programming, Series A Y1 - 1990 VL - 47 IS - 3 SP - 367 EP - 387 ER - TY - JOUR A1 - Grötschel, Martin A1 - Jünger, Michael A1 - Reinelt, Gerhard T1 - Optimal triangulation of large real world input-output matrices JF - Statistische Hefte Y1 - 1984 VL - 25 SP - 261 EP - 295 ER - TY - CHAP A1 - Grötschel, Martin A1 - Lovász, Lászlo A1 - Schrijver, Alexander ED - Pulleyblank, William T1 - Geometric Methods in Combinatorial Optimization T2 - Progress in Combinatorial Optimization, (Conference Waterloo/Ontario 1982) Y1 - 1984 SP - 167 EP - 183 PB - Academic Press ER - TY - CHAP A1 - Grötschel, Martin A1 - Lovász, Lászlo A1 - Schrijver, Alexander ED - Berge, Claude ED - Chvátal, Vašek T1 - Polynomial algorithms for perfect graphs T2 - Topics on perfect graphs Y1 - 1984 VL - 21 SP - 325 EP - 356 PB - North-Holland ER - TY - JOUR A1 - Grötschel, Martin A1 - Lovász, Lászlo A1 - Schrijver, Alexander T1 - Corrigendum to our paper “The ellipsoid method and its consequences in combinatorial optimization” JF - Combinatorica Y1 - 1984 VL - 4 IS - 4 SP - 291 EP - 295 ER - TY - JOUR A1 - Grötschel, Martin A1 - Nemhauser, George T1 - A polynomial algorithm for the max-cut problem on graphs without long odd cycles JF - Mathematical Programming Y1 - 1984 VL - 29 IS - 1 SP - 28 EP - 40 PB - North-Holland ER - TY - CHAP A1 - Grötschel, Martin A1 - Wakabayashi, Yoshiko ED - Cottle, Richard ED - Kelmanson, Milton ED - Korte, Bernhard T1 - Constructions of hypotraceable digraphs T2 - Mathematical Programming. Proceedings of the International Congress on Mathematical Programming, Rio de Janeiro, Brazil, 6-8 April 1981 Y1 - 1984 SP - 147 EP - 175 PB - North-Holland ER - TY - JOUR A1 - Barahona, Francisco A1 - Grötschel, Martin A1 - Mahjoub, Ali T1 - Facets of the Bipartite Subgraph Polytope JF - Mathematics of Operations Research Y1 - 1985 VL - 10 SP - 340 EP - 358 ER - TY - JOUR A1 - Grötschel, Martin A1 - Holland, Olaf T1 - Solving matching problems with linear programming JF - Mathematical Programming Y1 - 1985 VL - 33 IS - 3 SP - 243 EP - 259 ER - TY - CHAP A1 - Grötschel, Martin A1 - Jünger, Michael A1 - Reinelt, Gerhard ED - Rival, Ivan T1 - Acyclic subdigraphs and linear orderings T2 - Graphs and Order. The Role of Graphs in the Theory of Ordered Sets and its Applications, Proceedings of NATO ASI, Ser. C 147, Banff/Canada 1984 Y1 - 1985 SP - 217 EP - 264 PB - D. Reidel Publishing Company ER - TY - JOUR A1 - Grötschel, Martin A1 - Jünger, Michael A1 - Reinelt, Gerhard T1 - On the acyclic subgraph polytope JF - Mathematical Programming Y1 - 1985 VL - 33 IS - 1 SP - 28 EP - 42 PB - North-Holland ER - TY - JOUR A1 - Grötschel, Martin A1 - Jünger, Michael A1 - Reinelt, Gerhard T1 - Facets of the linear ordering polytope JF - Mathematical Programming Y1 - 1985 VL - 33 IS - 1 SP - 43 EP - 60 PB - North-Holland ER - TY - CHAP A1 - Grötschel, Martin A1 - Padberg, Manfred ED - Lawler, Eugene ED - Lenstra, Jan ED - Kan, Alexander ED - Shmoys, David T1 - Polyhedral theory T2 - The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization Y1 - 1985 SP - 251 EP - 306 PB - Wiley ER - TY - CHAP A1 - Padberg, Manfred A1 - Grötschel, Martin ED - Lawler, Eugene ED - Lenstra, Jan ED - Kan, Alexander ED - Shmoys, David T1 - Polyhedral computations T2 - The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization Y1 - 1985 SP - 307 EP - 360 PB - Wiley ER - TY - RPRT A1 - Barahona, Francisco A1 - Grötschel, Martin T1 - The Travelling Salesman Problem for Graphs not Contractible to K_5 - e Y1 - 1985 IS - 77 PB - Mathematisches Institut, Universität Augsburg ER - TY - JOUR A1 - Barahona, Francisco A1 - Grötschel, Martin T1 - On the Cycle Polytope of a Binary Matroid JF - Journal of Combinatorial Theory, Series B Y1 - 1986 VL - 40 SP - 40 EP - 62 ER - TY - CHAP A1 - Grötschel, Martin ED - Kerber, Adalbert T1 - Polyedrische Kombinatorik und Schnittebenenverfahren, Tagungsbericht 2. Sommerschule Diskrete Strukturen, Bayreuth 1985 T2 - Diskrete Strukturen, algebraische Methoden und Anwendungen Y1 - 1986 VL - 21 SP - 69 EP - 100 PB - Institut für Mathematik, Universität Bayreuth ER - TY - CHAP A1 - Grötschel, Martin ED - Krelle, Wilhelm T1 - Fortschritte in der polyedrischen Kombinatorik T2 - Ökonomische Prognose-, Entscheidungs- und Gleichgewichtsmodelle, Abschlußberichte des SFB 21 Y1 - 1986 SP - 341 EP - 367 PB - Verlag Chemie CY - Weinheim ER - TY - JOUR A1 - Grötschel, Martin A1 - Lovász, Lászlo A1 - Schrijver, Alexander T1 - Relaxations of Vertex Packing JF - Journal of Combinatorial Theory, Series B Y1 - 1986 VL - 40 SP - 330 EP - 343 ER - TY - JOUR A1 - Grötschel, Martin A1 - Pulleyblank, William T1 - Clique tree inequalities and the symmetric travelling salesman problem JF - Mathematics of Operations Research Y1 - 1986 VL - 11 IS - 4 SP - 537 EP - 569 ER - TY - JOUR A1 - Grötschel, Martin A1 - Holland, Olaf T1 - A Cutting Plane Algorithm for Minimum Perfect 2-Matchings JF - Computing Y1 - 1987 VL - 39 SP - 327 EP - 344 ER - TY - JOUR A1 - Grötschel, Martin A1 - Thomassen, Carsten A1 - Wakabayashi, Yoshiko T1 - Hypotraceable digraphs JF - Journal of Graph Theory Y1 - 1980 VL - 4 SP - 377 EP - 381 ER - TY - JOUR A1 - Grötschel, Martin A1 - Wakabayashi, Yoshiko T1 - Hypohamiltonian digraphs JF - Methods of Operations Research Y1 - 1980 VL - 36 SP - 99 EP - 119 ER - TY - BOOK A1 - Bachem, Achim A1 - Butz, Lothar A1 - Grötschel, Martin A1 - (Bearb.), Rainer A1 - Leitung), Bernhard T1 - Input-Output-Analyse bei unternehmensgrößenspezifischen Fragestellungen Y1 - 1981 PB - Institut für Mittelstandsforschung CY - Bonn ER - TY - JOUR A1 - Bachem, Achim A1 - Grötschel, Martin T1 - Homogenization of polyhedra JF - Methods of Operations Research Y1 - 1981 VL - 40 SP - 215 EP - 219 ER - TY - CHAP A1 - Bachem, Achim A1 - Grötschel, Martin ED - König, Heinz ED - Korte, Bernhard ED - Ritter, Klaus T1 - Characterizations of adjacency of faces of polyhedra T2 - Mathematical Programming at Oberwolfach Y1 - 1981 VL - 14 SP - 1 EP - 22 PB - North-Holland ER - TY - JOUR A1 - Grötschel, Martin A1 - Lovász, Lászlo A1 - Schrijver, Alexander T1 - The ellipsoid method and its consequences in combinatorial optimization JF - Combinatorica Y1 - 1981 VL - 1 IS - 2 SP - 169 EP - 197 ER - TY - JOUR A1 - Grötschel, Martin A1 - Lovász, Lászlo A1 - Schrijver, Alexander T1 - The ellipsoid method and its consequences in combinatorial optimization JF - IIASA Collab. Proceedings Ser. CP-81-S1 Y1 - 1981 SP - 511 EP - 546 ER - TY - JOUR A1 - Grötschel, Martin A1 - Pulleyblank, William T1 - Weakly bipartite graphs and the max-cut problem JF - Operations Research Letters Y1 - 1981 VL - 1 IS - 1 SP - 23 EP - 27 ER - TY - JOUR A1 - Grötschel, Martin A1 - Wakabayashi, Yoshiko T1 - On the structure of the monotone asymmetric travelling salesman polytope I JF - Discrete Mathematics Y1 - 1981 VL - 34 SP - 43 EP - 59 ER - TY - JOUR A1 - Grötschel, Martin A1 - Wakabayashi, Yoshiko T1 - On the structure of the monotone asymmetric travelling salesman polytope II JF - Mathematical Programming Study Y1 - 1981 VL - 14 SP - 77 EP - 97 ER - TY - CHAP A1 - Bachem, Achim A1 - Grötschel, Martin ED - Korte, Bernhard T1 - New aspects of polyhedral theory T2 - Modern Applied Mathematics Y1 - 1982 SP - 51 EP - 106 PB - North-Holland ER - TY - CHAP A1 - Grötschel, Martin ED - Korte, Bernhard T1 - Approaches to Hard Combinatorial Optimization Problems T2 - Modern Applied Mathematics, Optimization and Operations Research, Lect. Summer Sch., Bonn 1979 Y1 - 1982 SP - 437 EP - 515 PB - North-Holland ER - TY - CHAP A1 - Grötschel, Martin ED - der Universität Bonn, Der T1 - Kombinatorische Optimierung T2 - Forschungsbericht 1978-1980 der Rheinischen Friedrich-Wilhelms-Universität Y1 - 1982 SP - 45 EP - 54 PB - Bouvier CY - Bonn ER - 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 - TY - CHAP A1 - Grötschel, Martin A1 - Löbel, Andreas A1 - Völker, Manfred ED - Hoffmann, Karl-Heinz ED - Jäger, Willi ED - Lohmann, Thomas ED - Schunck (Hrsg.), Hermann T1 - Optimierung des Fahrzeugumlaufs im Öffentlichen Nahverkehr T2 - Mathematik Y1 - 1997 SP - 609 EP - 624 PB - Springer ER - TY - CHAP A1 - Grötschel, Martin ED - Kapoor, Sanjiv ED - Prasad, Sanjiva T1 - Frequency Assignment in Mobile Phone Systems T2 - FST TCS 2000 Y1 - 2000 VL - 1974 SP - 81 EP - 86 PB - Springer ER - TY - GEN A1 - Grötschel, Martin A1 - Krumke, Sven A1 - Rambau, Jörg A1 - Torres, Luis Miguel T1 - Making the Yellow Angels Fly: Online Dispatching Of Service Vehicles in Real Time N2 - 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. T3 - ZIB-Report - 02-18 KW - vehicle dispatching KW - soft time windows KW - real-time KW - column generation KW - pricing KW - branch and bound KW - real world data KW - ADAC Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6858 ER - TY - GEN A1 - Grötschel, Martin T1 - Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes N2 - A subset ${\cal C}$ of the power set of a finite set $E$ is called cardinality homogeneous if, whenever ${\cal C}$ contains some set $F$, ${\cal C}$ contains all subsets of $E$ of cardinality $|F|$. Examples of such set systems ${\cal C}$ are the sets of circuits and the sets of cycles of uniform matroids and the sets of all even or of all odd cardinality subsets of $E$. With each cardinality homogeneous set system ${\cal C}$, we associate the polytope $P({\cal C})$, the convex hull of the incidence vectors of all sets in ${\cal C}$, and provide a complete and nonredundant linear description of $P({\cal C})$. We show that a greedy algorithm optimizes any linear function over $P({\cal C})$, give an explicit optimum solution of the dual linear program, and provide a polynomial time separation algorithm for the class of polytopes of type $P({\cal C})$. T3 - ZIB-Report - 02-19 KW - Cycles in Matroids KW - cardinality homogeneous set systems KW - polytopes KW - greedy algorithm KW - polyhedral combinatorics Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6868 ER - TY - GEN A1 - Grötschel, Martin T1 - P=NP? N2 - Hinter der für den Uneingeweihten etwas kryptischen Frage "P = NP?" verbirgt sich das derzeit wichtigste Problem der Komplexitätstheorie. Dieser Artikel erläutert einige Aspekte der Theorie und erklärt informell, was "P = NP?" bedeutet. Es geht nicht nur um komplizierte algorithmische Mathematik und Informatik, sondern um grundsätzliche Fragen unserer Lebensumwelt. Kann man vielleicht beweisen, dass es für viele Probleme unseres Alltags keine effizienten Lösungsmethoden gibt? T3 - ZIB-Report - 02-26 KW - computational complexity KW - P=NP Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6939 ER - TY - GEN A1 - Grötschel, Martin A1 - Lügger, Joachim A1 - Sperber, Wolfram T1 - DMV-Vorhaben. "Verbesserung des benutzerorientierten Zugriffs auf fachspezifische Online-Datenbanken und CD-ROM für Mathematische Institute der Bundesrepublik Deutschland" N2 - Der Report analysiert die Ergebnisse des Projektes ,,Verbesserung des benutzerorientierten Zugriffs auf fachspezifische Online und CD-ROM Datenbanken für Mathematische Institute der Bundesrepublik Deutschland'' der Deutschen Mathematiker-Vereinigung. An dem Projekt, das vom ZIB geleitet und koordiniert worden ist, haben mehr als 50 mathematische Fachbereiche und Forschungsinstitute teilgenommen. Dieses vom damaligen BMFT (einem Teil des jetzigen Bundesministeriums für Bildung, Wissenschaft, Forschung und Technologie) geförderte Projekt hat wesentlich dazu beigetragen, dass fachspezifische Datenbanken heute in den mathematischen Fachbereichen in Deutschland zu den selbstverständlichen Arbeitsmitteln gehören. Darüber hinaus hat das Projekt die Grundlagen für eine moderne elektronische Informations- und Kommunikationsstruktur in den mathematischen Fachbereichen gelegt. T3 - ZIB-Report - TR-96-02 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5318 ER - TY - GEN A1 - Grötschel, Martin A1 - Lügger, Joachim T1 - Neue Produkte für die digitale Bibliothek: die Rolle der Wissenschaften N2 - Der Artikel ist die ausgearbeitete und erweiterte Fassung eines eingeladenen Vortrags der Tagung ,,Die unendliche Bibliothek - Digitale Information in Wissenschaft, Verlag und Bibliothek''. Dieses Treffen, eine Veranstaltung des Börsenvereins des Deutschen Buchhandels e.V., der Deutschen Bibliothek und der Bundesvereinigung Deutscher Bibliothkesverbände, fand im Dezember 1995 in Bonn als Beitrag zur der heute aktuellen Debatte unter Wissenschaftlern, Verlegern, Buchhändlern, Bibliothekaren und Politikern statt, wie unser Wissen und unsere Informationen digital transferiert werden können. Der Vortrag stellte das zentrale Problem des heutigen wissenschaftlichen Informationswesens dar, die gleichzeitige Existenz von Informationsflut und Informationsmangel. Nach einer knappen Bestimmung der Veränderung der Kommunikationsstrukturen in den Wissenschaften fragte er nach den essentiellen Veränderungen der Informationsarten, d.h. nach der Natur der kommenden Globalen Digitalen Bibliothek, die als ein über die ganze Welt und auf viele Institutionen verteilter globaler Speicher gesehen wird. Der Vortrag diskutierte zum Schluss die Bedürfnisse und Interessen der Wissenschaften und ihre spezifische Verantwortung beim Übergang in die elektronische Welt. Der Tagungsband ist erschienen beim Harrassowitz Verlag, Wiesbaden, 1996. T3 - ZIB-Report - TR-96-05 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5343 ER - TY - GEN A1 - Grötschel, Martin A1 - Lügger, Joachim T1 - Wissenschaftliche Information und Kommunikation im Umbruch N2 - Steht uns das Ende des traditionellen wissenschaftlichen Publizierens bevor? Neue Technologien eröffnen neue Chancen zur Bewältigung der Informationsflut und des gleichzeitigen Informationsmangels. Doch der Einsatz von Technik allein reicht nicht aus. T3 - ZIB-Report - TR-96-07 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5365 ER -