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 -