@article{GroetschelHolland1987, author = {Gr{\"o}tschel, Martin and Holland, Olaf}, title = {A Cutting Plane Algorithm for Minimum Perfect 2-Matchings}, volume = {39}, journal = {Computing}, pages = {327 -- 344}, year = {1987}, language = {en} } @article{GroetschelThomassenWakabayashi1980, author = {Gr{\"o}tschel, Martin and Thomassen, Carsten and Wakabayashi, Yoshiko}, title = {Hypotraceable digraphs}, volume = {4}, journal = {Journal of Graph Theory}, pages = {377 -- 381}, year = {1980}, language = {en} } @article{GroetschelWakabayashi1980, author = {Gr{\"o}tschel, Martin and Wakabayashi, Yoshiko}, title = {Hypohamiltonian digraphs}, volume = {36}, journal = {Methods of Operations Research}, pages = {99 -- 119}, year = {1980}, language = {en} } @book{BachemButzGroetscheletal.1981, author = {Bachem, Achim and Butz, Lothar and Gr{\"o}tschel, Martin and (Bearb.), Rainer and Leitung), Bernhard}, title = {Input-Output-Analyse bei unternehmensgr{\"o}ßenspezifischen Fragestellungen}, publisher = {Institut f{\"u}r Mittelstandsforschung}, address = {Bonn}, year = {1981}, language = {en} } @article{BachemGroetschel1981, author = {Bachem, Achim and Gr{\"o}tschel, Martin}, title = {Homogenization of polyhedra}, volume = {40}, journal = {Methods of Operations Research}, pages = {215 -- 219}, year = {1981}, language = {en} } @inproceedings{BachemGroetschel1981, author = {Bachem, Achim and Gr{\"o}tschel, Martin}, title = {Characterizations of adjacency of faces of polyhedra}, volume = {14}, booktitle = {Mathematical Programming at Oberwolfach}, editor = {K{\"o}nig, Heinz and Korte, Bernhard and Ritter, Klaus}, publisher = {North-Holland}, pages = {1 -- 22}, year = {1981}, language = {en} } @article{GroetschelLovaszSchrijver1981, author = {Gr{\"o}tschel, Martin and Lov{\´a}sz, L{\´a}szlo and Schrijver, Alexander}, title = {The ellipsoid method and its consequences in combinatorial optimization}, volume = {1}, journal = {Combinatorica}, number = {2}, pages = {169 -- 197}, year = {1981}, language = {en} } @article{GroetschelLovaszSchrijver1981, author = {Gr{\"o}tschel, Martin and Lov{\´a}sz, L{\´a}szlo and Schrijver, Alexander}, title = {The ellipsoid method and its consequences in combinatorial optimization}, journal = {IIASA Collab. Proceedings Ser. CP-81-S1}, pages = {511 -- 546}, year = {1981}, language = {en} } @article{GroetschelPulleyblank1981, author = {Gr{\"o}tschel, Martin and Pulleyblank, William}, title = {Weakly bipartite graphs and the max-cut problem}, volume = {1}, journal = {Operations Research Letters}, number = {1}, pages = {23 -- 27}, year = {1981}, language = {en} } @article{GroetschelWakabayashi1981, author = {Gr{\"o}tschel, Martin and Wakabayashi, Yoshiko}, title = {On the structure of the monotone asymmetric travelling salesman polytope I}, volume = {34}, journal = {Discrete Mathematics}, pages = {43 -- 59}, year = {1981}, language = {en} } @article{GroetschelWakabayashi1981, author = {Gr{\"o}tschel, Martin and Wakabayashi, Yoshiko}, title = {On the structure of the monotone asymmetric travelling salesman polytope II}, volume = {14}, journal = {Mathematical Programming Study}, pages = {77 -- 97}, year = {1981}, language = {en} } @inproceedings{BachemGroetschel1982, author = {Bachem, Achim and Gr{\"o}tschel, Martin}, title = {New aspects of polyhedral theory}, booktitle = {Modern Applied Mathematics}, editor = {Korte, Bernhard}, publisher = {North-Holland}, pages = {51 -- 106}, year = {1982}, language = {en} } @inproceedings{Groetschel1982, author = {Gr{\"o}tschel, Martin}, title = {Approaches to Hard Combinatorial Optimization Problems}, booktitle = {Modern Applied Mathematics, Optimization and Operations Research, Lect. Summer Sch., Bonn 1979}, editor = {Korte, Bernhard}, publisher = {North-Holland}, pages = {437 -- 515}, year = {1982}, language = {en} } @inproceedings{Groetschel1982, author = {Gr{\"o}tschel, Martin}, title = {Kombinatorische Optimierung}, booktitle = {Forschungsbericht 1978-1980 der Rheinischen Friedrich-Wilhelms-Universit{\"a}t}, editor = {der Universit{\"a}t Bonn, Der}, publisher = {Bouvier}, address = {Bonn}, pages = {45 -- 54}, year = {1982}, language = {en} } @inproceedings{Groetschel1984, author = {Gr{\"o}tschel, Martin}, title = {On Intersections of Longest Cycles}, booktitle = {Graph Theory and Combinatorics}, editor = {Bollob{\´a}s, B{\´e}la}, publisher = {Academic Press}, pages = {171 -- 189}, year = {1984}, language = {en} } @incollection{Groetschel1984, author = {Gr{\"o}tschel, Martin}, title = {Developments in combinatorial optimization}, booktitle = {Perspectives in Mathematics (Anniversary of Oberwolfach 1984)}, editor = {J{\"a}ger, Willi and Moser, J. and Remmert, R.}, publisher = {Birkh{\"a}user}, address = {Basel}, pages = {249 -- 294}, year = {1984}, language = {en} } @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} }