Martin Grötschel—The Early Years in Bonn and Augsburg

Abstract

Martin Grötschel is one of the most influential mathematicians of our time. He has received numerous honors and serves in a number of key positions in the international mathematical community. A summary is sketched in the preceding short curriculum vitae taken from his professional homepage. Numerous scientific and popular articles recount his achievements and prominent role. These include articles in respected papers such as DIE ZEIT, Financial Times, Die Welt, and Der Tagesspiegel. His “scientific facets” will be covered in detail in the rest of this book.

When we first conceived of this chapter, we had a different perspective in mind. As his first doctoral descendants, we can tell a different story, because we were actively involved in his early career. This was the time when he developed from a scientific assistant in Bonn to a full professor in Augsburg. In the following, we recount some of our memories of this time, with no guarantee for either accuracy or completeness. Instead, these are the stories that came to mind when we sat together in Heidelberg and Cologne, preparing this chapter.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Martin Grötschel is one of the most influential mathematicians of our time. He has received numerous honors and serves in a number of key positions in the international mathematical community. A summary is sketched in the preceding short curriculum vitae taken from his professional homepage. Numerous scientific and popular articles recount his achievements and prominent role. These include articles in respected papers such as DIE ZEIT, Financial Times, Die Welt, and Der Tagesspiegel. His “scientific facets” will be covered in detail in the rest of this book.

When we first conceived of this chapter, we had a different perspective in mind. As his first doctoral descendants, we can tell a different story, because we were actively involved in his early career. This was the time when he developed from a scientific assistant in Bonn to a full professor in Augsburg. In the following, we recount some of our memories of this time, with no guarantee for either accuracy or completeness. Instead, these are the stories that came to mind when we sat together in Heidelberg and Cologne, preparing this chapter.

2 Bonn

After obtaining his diploma in Mathematics at the University of Bochum in 1973, Martin started his doctoral studies in Mathematics and Economics at the Institut für Ökonometrie und Operations Research of the Rheinische Friedrich-Wilhelms-Universität Bonn, which would prove to be an excellent choice. The Operations Research Department, under the leadership of Bernhard Korte, quickly developed into an internationally renowned center for Mathematics of Operations Research. Prominent researchers came for colloquium presentations, a visit of a couple of weeks, a few months, or even an entire sabbatical term. Bernhard Korte created a stimulating atmosphere in which young scientists could grow and bloom. He also had good taste when it came to selecting his scientific assistants, and Martin was one of them. (They first met at a summer school for members of the Deutsche Studienstiftung, where Bernhard Korte gave a series of lectures and Martin was one of the happy students to receive such a renowned stipend.)

We, the authors, were still in high school in 1973, too young to be part of what was going on in Bonn in 1973 and 1974. We entered the scene as students taking Operations Research as a minor in our studies of Computer Science in 1975, but this was early enough to know a little bit about the two preceding years.

In 1974, Manfred Padberg spent six months at the OR Department, and one day, young Martin (no beard yet) appeared at the door to his office and asked: “Was ist eigentlich Kombinatorische Optimierung?” (“What is Combinatorial Optimization anyway?”), to which Manfred replied: “Come in.” Manfred soon got Martin working on the traveling salesman problem. Everybody in Combinatorial Optimization knows what followed, but the reader may not know the first technical report on this unique and fruitful collaboration, namely Report No. 7416 of the Institut für Ökonometrie und Operations Research’s famous blue preprint series, the cover and abstract of which are shown in Fig. 1. (For the published version, see [1].)

Fig. 1

Report No. 7416, the first outcome of the collaboration of Martin Grötschel and Manfred Padberg: Cover (left) and abstract in English, German, and French (right)

Our own early experience in the Bonn OR Department was dominated by our fascination with Bernhard Korte’s unique, unusual, and entertaining teaching style. At some point, our minor subject of study interested us so much that we applied for student assistant positions (“Studentische Hilfskräfte”). The department had a data station including all the high-tech equipment that Computer Science students longed for back then. This included a punched card reader not shared by a hundred but only a dozen or so users, (comparatively) quick results from a noisy line printer, et cetera. Initially, we really had nothing to do with Martin. Our assignments, such as implementing basic computer routines like line search in nonlinear programming, came from Achim Bachem, another young scientific assistant who has also had an impressive career, but that is a different story. During this period, we tried to follow the seminars and colloquia offered by the department, sitting in the last row, without much success. What we clearly remember is that Martin was a critical member of the team, with pointed questions for those who gave presentations. This was our first encounter.

A later encounter was less enjoyable: One of our duties was to run around a table with piles of paper sheets, assemble them into scientific preprints of the blue Bonn series, and staple them. One issue we remember very clearly: Report No. 7770 (Ref. [2]) seemed to contain nothing but numbers. Later we realized that this was the distance matrix of the famous TSP instance that would later become known as “gr120.tsp,” a 120-city instance of German towns, the distances between which had been taken from the ADAC (Allgemeiner Deutscher Automobil-Club) road map. Martin’s optimum solution of the TSP for this set of cities set a new world record at the time, with the help of the aforementioned data station of the IBM mainframe at the University of Bonn. We later learned that it more or less went like this: Michael Hahmann (aka James) let IBM’s LP-solver MPSX run on a relaxation and gave the output to Martin, who plotted it at home that night (armed with only a pencil and an eraser), did the separation by hand, and handed some new cutting planes (facet defining for the TSP polytope, of course) to James the next morning. James solved the stronger relaxation during the day, gave the fractional solution to Martin in the evening, …, and, lo and behold, after 13 iterations (days) an optimum solution was found.

Then the real excitement started. In 1980, the department acquired an IBM 4331, and for the first time we could work at an IBM 3270 terminal in time sharing mode (TSO: “time sharing option” in IBM jargon). Prior to this, computing was done in batch mode. We had by now received our master/diploma degrees, and we had been promoted to “Wissenschaftliche Hilfskräfte,” which doubled our (still meager) salaries, enough to be less dependent on our parents’ support. In 1981, we had already written our first paper in graph theory, jointly with and under the supervision of Bill Pulleyblank, who was one of the department’s visiting scientists then, and whose main collaboration at the same time was with Martin. We remember when Martin said “We have found plenty of new TSP facets,” referring to the clique tree inequalities discovered in the course of this collaboration.

One day in 1981, Martin announced: “Jetzt habilitiere ich mich.” (“Now I’ll get my habilitation.”) This postdoctoral degree was a prerequisite for a professorship then. He produced a monograph within a few weeks, and he got his habilitation soon afterwards.

Also in 1981, four of the department’s scientific assistants had completed the little book [3], see Fig. 2, where the following statement is made about the triangulation problem for input-output tables: “Selbst beliebig verfeinerte Verfahrenstechniken werden vermutlich nicht dazu führen, daß man das Triangulationsproblem für wünschenswerte Größenordnungen von Input-Output-Matrizen optimal lösen kann.” (“Even arbitrarily refined procedures are not likely to lead to the solvability of the triangulation problem for input-output matrices of desirable sizes.”)

Fig. 2

A little book with an influential statement

This economics problem is equivalent to the well known linear ordering problem. Martin gave us the integer programming relaxation using 3-cycle inequalities and let us hunt for facets of the linear ordering polytope (and the related acyclic subdigraph polytope), but apparently, he didn’t expect much, stating simply: “It’s not easy.” Nevertheless, we came up with new facet classes rather quickly and he was impressed. Part of our success was, of course, due to the fact that, to us, the use of software assistance in the search came rather naturally. By chance, we had written a computer program that implemented Jack Edmonds’ all-integer version of Gaussian elimination with high-precision arithmetic (an early assignment from Achim Bachem). Therefore we were able to accurately determine the rank of a 0/1-matrix, see also [4]. We embedded this into a user-friendly software package that, given an inequality, gave one of the following replies: “Sorry, the inequality is not valid.” or “The inequality is valid and induces a face of dimension r,” or “Congratulations, you have found a facet!”.

This allowed experimentation and provided many conjectures of generalizations to facet classes. We also wrote branch&cut software that we called a “cutting plane algorithm,” avoiding any reference to the “dirty” enumeration part of the software. The technical term “branch&cut” was coined much later by Manfred Padberg and Giovanni Rinaldi.

On the IBM 4331, we used the programming language PL/I and IBM’s MPSX software to solve the linear programming relaxations. And we found we could indeed solve these triangulation instances that had seemed so hopeless just a year earlier. This became our ticket to Martin’s world.

We were confident that we had produced enough material for a scientific paper, but Martin said “One paper? No. Three!” The paper production process was just amazing for us: We would sit in Martin’s office, equipped with a notepad, a pencil, an eraser, a pair of scissors, and a bottle of glue. Days of writing, cutting and pasting (in the original sense) followed, and the result was given to Helga Grimm, the department secretary, who typed it up on an IBM Selectric “golfball” typewriter. Eventually, these three papers ended up as references [5, 6], and [7]. They were also the basis of an entire session chaired by Laurence Wolsey on August 24, 1982, at the International Symposium on Mathematical Programming ISMP 1982 in Bonn, see Fig. 3.

Fig. 3

Talks of Martin Grötschel, Michael Jünger, and Gerhard Reinelt at the ISMP 1982 in Bonn

This date was a turning point for the two of us: These were the first scientific talks we gave. Later, we produced another paper with computational studies for economists, the first of that series to appear in print [8].

Of course, for Martin, this was only one of the many findings in a period of great scientific creativity and success. Most notably, at that same ISMP 1982, he received the prestigious Fulkerson Prize, jointly with László Lovász and Alexander Schrijver, for the groundbreaking work on the Ellipsoid Method and its consequences in Combinatorial Optimization [9], see Fig. 4.

Fig. 4

Ron Graham presents the Fulkerson Prize to Martin Grötschel, László Lovász, and Alexander Schrijver at the ISMP 1982 in Bonn

In late 1982, he accepted a chair in Applied Mathematics at the University of Augsburg’s newly founded Mathematics Department.

3 Augsburg

As a result of a number of wise decisions made by an external committee, the newly founded Mathematics Department at the University of Augsburg consisted of an excellent group of active young professors and their scientific assistants. We were lucky to be among the latter almost from the very beginning. When we followed Martin to Augsburg in early 1983, the student body consisted of about 45 beginners studying mathematics in their first semester. It is hard to imagine better studying conditions. In February of 1983, there was a party in the Rosenaustraße, where four scientific assistants shared a big apartment. Almost the entire Science Faculty (math only then) from the dean to the students showed up and fitted in.

The chair of Martin consisted of four people, see the first few lines of the faculty telephone directory of April 1, 1983, in Fig. 5.

Fig. 5

Excerpt of the Telephone Directory of the Science Faculty of the University of Augsburg dated April 1, 1983

“Konnerth Theodora” is now “Ungureanu Teodora.” (Bavarians have the strange habit of listing the first name after the last name—for ordinary people, not for professors.) Teodora was the perfect addition for the one senior and the two junior scientists of the group. We worked hard in perfect harmony, and had a lot of fun. The following offers a glimpse into the atmosphere of the time: Both Martin and Teodora were unhappy with their weight: Teodora a bit too slim, Martin a bit overweight. So one day they agreed to work on this and made a contract to keep their weight sum constant.

While we were working on our doctoral dissertations, Martin’s main scientific focus was the “GLS book,” which would later become Geometric Algorithms and Combinatorial Optimization [10]. Consequently, among the many guests we had, two were regularly seen in Martin’s office: Láci Lovász and Lex Schrijver, who would often come for quiet working sessions with Martin.

The lack of decent computer equipment at the University of Augsburg presented a problem. Martin fought hard to improve the situation, but initially we had no choice but to use the computers at the University of Bonn and at the Deutsche Forschungs- und Versuchsanstalt für Luft- und Raumfahrt (DFVLR), now the Deutsches Zentrum für Luft- und Raumfahrt (DLR). The latter required frequent trips to Oberpfaffenhofen near Munich.

In addition to a computational platform, we wanted decent computer typesetting. already existed in its second (and final) generation, but there were no easy to use custom distributions. So we ordered a tape and adapted the software for the IBM mainframe in Oberpfaffenhofen, and then wrote a driver for the big vector plotter that we used as an output device. This caught the attention of Hans-Martin Wacker, the director of the computing center, who asked us to make the installation available to all users, and we did. But we became more and more tired of all the traveling and cutting pages from plotter output, so Martin ordered a CADMUS, a MUNIX workstation from Periphere Computer-Systeme (PCS) in Munich, at a price of about 50 000 German marks. (“MUNIX” instead of “UNIX” is not a typo!) It was delivered in October 1983.

We still needed a decent DIN-A4 laser printer, and there was not much choice then. The Canon LBP-10 (the first desktop laser printer in the world) was the machine of choice, but its price (roughly 35 000 marks) significantly exceeded the chair’s budget, so we talked the university computing center into buying one. We made sure it was ordered from PCS, and when it was delivered, it turned out that “unfortunately” its interface was only compatible with our CADMUS, so it ended up in our office.

The tiny CADMUS system (Motorola 68000 processor, 512 kilobytes of main memory, 60 megabytes of disk space) became our research workhorse. Again, we implemented and wrote a new output driver, now with convenient DIN-A4 output, and it soon became the typesetting machine for many more mathematicians at the Augsburg department who were tired of the then still-common typewriters.

This machinery, plus a home-made macro package for books, not only allowed our two doctoral dissertations to be typeset in , but also made possible the first Springer book to have its manuscript submitted in , namely the groundbreaking “GLS book” [10]. ( came 2 years later.)

Martin took great care in teaching optimization courses; some of his lecture notes from the first few years of his tenure in Augsburg are still in circulation today. In addition to basic mathematics courses, he covered the state of the art in linear, nonlinear, and discrete optimization. His lectures were spiced up with reports on applications and software demonstrations. As an enthusiastic teacher, he motivated many students to specialize in Combinatorial Optimization.

In 1983, Yoshiko Wakabayashi, with whom Martin had already worked in São Paulo and Bonn, came to Augsburg in order to work on her doctoral thesis concerning the aggregation of binary relations, with applications to clustering. She received her doctoral degree in 1986. In 1984, Karl-Heinz Borgwardt joined the faculty as an associate professor of Mathematical Optimization. Zaw Win came as a doctoral student from Yangon, Myanmar, and Martin got him working on the Windy Postman Problem, a core problem in vehicle routing. His doctoral degree was conferred in 1987. Martin also supervised Eberhard Zehendner, a doctoral student of Computer Science in our faculty, but outside our working group. He also received his doctoral degree in 1987.

The atmosphere in our working group was not always entirely serious. The two pictures in Fig. 6 show a legendary beer tasting party at the home of Martin and Iris Grötschel. This has been covered in print before, but here is the full truth. With the ability to triangulate input-output tables, and knowing that marketing people considered “ranking by aggregation of individual preferences,” which amounts to this very problem, we decided to determine a ranking of 10 Pilsner type beers. Pairwise comparison implied that we had to do 45 comparisons, in each of which the two glasses of each participant were (partially) filled with two different beers unknown to the drinkers. This meant 90 little portions of beer for each participant. We also had two cards each, one of which we simultaneously raised in order to indicate our preferences. See Fig. 6 for the tasting and the scoring phases.

Fig. 6

Beer tasting at the home of Martin and Iris Grötschel: Tasting phase (left) and scoring phase (right), repeated 45 times. Sitting from left to right: Michael Jünger, Martin Grötschel, Jeff Edmonds, Yoshiko Wakabayashi, Mario Sakumoto, Gerhard Reinelt

In each round, one of us acted as the waiter/waitress; in the photographed round, the second author has just served on the left picture, and he is not on the right picture because he is taking scores. Figure 7 shows scores Martin took when he was the waiter.

Fig. 7

Martin’s beer tasting scoring sheet

Part of the magic of the Augsburg years was certainly the fact that this was one of many occasions when we met at the Grötschels’ house. There were many parties with many visitors, in an atmosphere of warm hospitality.

Martin is well known as a driving force in applying state-of-the-art mathematics and computer science in industry and commerce and took on a leading position in such endeavors in the field of Combinatorial Optimization. This emerged during his time in Augsburg, where his first attempt was to become involved in the routing of the city garbage collection. Many letters were written and meetings were held, but in the end, no project was implemented due to conflicting interests among the city politicians. In retrospect, knowing that his big success in planning transport for handicapped people in Berlin started about a decade later, we are confident that the Augsburg garbage project would have been implemented and successfully completed, if Martin had been more experienced in dealing with politicians. He certainly is now, but back then, he was a beginner. This would soon change, as we shall see later.

In 1983, Martin had completed a joint paper with Francisco Barahona and Ridha Mahjoub [11], building on the two other authors’ previous related work. (Teodora has fond memories of her first assignment on her IBM Selectric.) In the mid eighties, we started serious work on the Maximum Cut Problem, together with Francisco Barahona, with whom we had established a joint German-Chilean project funded by the Volkswagen Foundation. Two applications drove us, namely ground state computations of spin glasses in solid state physics and via minimization in VLSI layout design. We still could not run branch&cut software on our university’s computers; instead we used IBM mainframes at the Kernforschungsanlage Jülich (now the Forschungszentrum Jülich) and the University of Bonn, mainly because they had the LP solver MPSX installed (and let us use it).

We can’t resist a digression on our university computer technology back in the day: We had no network connection and no email. Despite Martin’s efforts, the computing center did not see a point in having such a thing. (They considered email a passing fad that would soon be forgotten.) So data was transferred on the big reels of tape that you see spinning whenever computers are shown in old movies. Lacking space in our temporary department home in the Memminger Straße, the computing center’s tape reader was located in a nearby high school, and we had a “Studentische Hilfskraft,” one of whose jobs it was to carry reels of tape to the high school and make sure that the data eventually made its way to our CADMUS. Incidentally, the studentische Hilfskraft in charge of this was Petra Mutzel, who would later become one of Martin’s doctoral grandchildren.

Considering Martin’s achievements, then and later in Berlin, it is clear that he not only has capabilities that go far beyond the normal, but he is also a person who enjoys challenges of all kinds, takes up new duties and drives new agendas, in science, and also in scientific administration. His extraordinary gifts as a scientist had already become apparent before he came to Augsburg; the first glimpses of his organizational talents emerged in his role as co-organizer of the ISMP 1982 in Bonn. But in Augsburg, he not only kept up his high scientific productivity, but also spearheaded the successful development of the new Mathematics Department. At the age of 35, he became its director and Dean of the Science Faculty.

All this requires a competitive character, and Martin always strove to be the best. One of the few examples where we (the authors) could beat him was a TSP competition we organized for members and visitors to our working group. It simply consisted of finding a good tour for drilling 443 holes in a printed circuit board owned by Martin. (It had been our task to determine the coordinates of the holes by hand. After correction of a mistake, this resulted later in the well-known TSP instance “pcb442.tsp”.) Figure 8 shows the results of the competition, along with Martin’s tour.

Fig. 8

TSP contest: Ranking by tour length (left), Martin Grötschel’s tour (right)

A second activity in which we could soundly beat him was computer typing. Martin was then (is still?) a very slow typist. We teased him by telling him the password for his account was “Handlungsreisender,” knowing that he hated the German word for “traveling salesman.” He didn’t know that the first 8 letters were sufficient, and we grinned behind his back when we watched him slowly entering this long horrible word.

We know of no third such discipline. We are grateful that he never tried to convince us to compete with him in sports; we would have had no chance whatsoever.

Martin always made sure that we had enough money for traveling. In combination with the many visitors to the department this exposed us to the scientific community from the very beginning of our own productivity. In March 1986, he took the first author with him to a conference on “Computational Issues in Combinatorial Optimization” in Capri, Italy. After our presentation on spin glass ground state computations and VLSI via minimization, we were approached by Michel Balinski, who invited us to write an article for Operations Research, and this resulted in [12]. At this event, a young Italian approached the first author and introduced himself with the simple words: “My name is Giovanni Rinaldi, and I am the Italian version of Gerhard Reinelt.” This marked the beginning of a life-long friendship with all three of us.

Via Minimization was the entry point into our first serious industry cooperation. Martin established valuable contacts with SIEMENS in Munich, where we focused on VLSI layout design. Although working for profit, the SIEMENS team maintained high scientific standards. This was ensured by scientists like Ulrich Lauther, Michael Kolonko, and Michael Hofmeister, who made sure that the best students were hired after graduation. There were regular meetings; we would visit the team in Munich, and they would come for colloquium talks in Augsburg. In addition, there were workshops where theory met practice, so this was an ideal starting point for our first excursion from the “ivory tower” into the “real world.” We wrote a technical report on via minimization, mailed it to our scientific friends, but did not yet bother to submit it to a journal. We were surprised when we received a letter from East Germany in which we were informed that our “submission” had been accepted for publication in the Zeitschrift für Angewandte Mathematik und Mechanik! We gladly accepted, and the deal even included a complimentary Russian abstract, see [13].

In 1985, Gábor Galambos came from Szeged, Hungary, for a semester and worked on bin packing. In 1986, Klaus Truemper came from Dallas, Texas, as a Humboldt senior scientist, worked with Martin on cycles in binary matroids, and gave a lecture series on matroids. Also in 1986, Heinrich Puschmann came from Santiago de Chile and worked on transporting different kinds of oil in the same pipeline. In 1987, Leslie Trotter came as a Humboldt senior scientist from Cornell University, and Günter M. Ziegler joined us as a scientific assistant directly after receiving his Ph.D. at MIT. In 1988, Enrique Benavent came from Valencia, Spain, and worked on capacitated arc routing.

A distinctive feature of the mathematics curriculum in Augsburg was the inclusion of practical training in industry and commerce. This required close contacts between the department’s professors and local industry. One day we went with a group of students to visit the personal computer production at SIEMENS Augsburg, where we saw the POSALUX drilling machine for printed circuit boards. While it was explained to us, Martin immediately realized that minimizing production time essentially boils down to solving a sequence of instances of the traveling salesman problem. So he boldly declared “We can do better.” The answer was “No way, the machine’s control software already includes an optimization module.” But, of course, Martin insisted, and an agreement was reached that we would receive a tape with the data of various printed circuit boards, and if we managed to get improvements of at least 5 %, we’d be invited to the Eckestuben, the only Augsburg restaurant with a star rating.

Meanwhile, our dear old CADMUS had been replaced by a network of SUN workstations, and Martin had succeeded in making email available at the University of Augsburg. Needless to say, we gained much more than 5 %, see Fig. 9 for the original and the improved control of the machine, photographed from our new SUN workstations, i.e., old-fashioned screenshots.

Fig. 9

The paths the POSALUX driller would take with the original control (left) and the improved control (right)

In addition, we were equally successful in designing a better control of a plotter for the printed circuit board wiring. Our experimental study can be found in [14]. So we were not only invited for a nice dinner at the Eckestuben (where our industry partners could not help smiling when they learned about university professors’ salaries), but also to provide new software that would henceforth be used in the production at SIEMENS Augsburg.

In 1988, Giovanni Rinaldi came to work with us on maximum cut. Initially, Giovanni insisted on FORTRAN as the programming language, but eventually we convinced him that C would be a better choice. Bob Bixby was around, writing a C program, internally called BIXOPT, for the solution of linear programming problems. (BIXOPT later became LOPT, then PLEXUS, and finally CPLEX.) So the late eighties marked the starting point of our first branch&cut framework in C.

A problem with Bob’s new LP software was the lack of an implementation of the dual simplex algorithm. The package contained only a two-phase primal method. But in branch&cut, most of the time, dual feasible bases are available. So we asked Bob about this, and his response was: “Transpose the matrix.” We had no choice but do this, so the first version of this branch&cut framework contained a simulation of the dual simplex algorithm. But we kept insisting, of course, and eventually, Bob gave in. Not only could we replace our simulation with the real thing; his implementation of the dual simplex algorithm also turned out to be very successful on various LP benchmarks, and in his talks Bob was always sure to get a smile out of us when he told the story of its origin.

With third-party funds from the German Science Foundation (DFG) in the context of a priority program on applied optimization and control, along with various other sources, the group continued to grow dynamically. Our first Augsburg students had graduated and joined the various activities: Mechthild Stoer, Robert Weismantel, Alexander Martin, Doris Zepf (now Tesch) and Petra Bauer. Atef Abdel-Aziz Abdel-Hamid joined us as a doctoral student from Egypt. The pictures shown in Fig. 10 and Fig. 11 were both taken in 1989, the second after we had moved to our new building on the new campus of the University of Augsburg in September 1989.

Fig. 10

Martin Grötschel’s group in Augsburg 1989, from left to right: Michael Jünger, Atef Abdel-Aziz Abdel-Hamid, Karl-Heinz Borgwardt, Alexander Martin, Günter M. Ziegler, Doris Zepf, Robert Weismantel, Martin Grötschel, Gerhard Reinelt

Fig. 11

Martin Grötschel’s group in Augsburg with visitors 1989, from left to right: Zaw Win, Teodora Ungureanu, Michael Jünger, Jack Edmonds, Jean Fonlupt, Martin Grötschel, Günter M. Ziegler, Yoshiko Wakabayashi, Mechthild Stoer

Martin had no difficulties supervising this sizeable group of fresh doctoral students. Unlike his previous doctoral students, they had been under his influence from the beginning of their mathematical studies, and had already embraced his special mixture of mathematics and applications.

Mechthild Stoer worked on the design of reliable networks, a joint project with Clyde Monma of AT&T Bell Labs. Robert Weismantel and Alexander Martin had already worked for SIEMENS in Munich as student interns before receiving their diplomas. Consequently, their doctoral thesis subjects were in VLSI layout design: placement and routing.

In July 1989, on the occasion of the 14th IFIP Conference on System Modelling and Optimization, there was a memorable evening in Auerbachs Keller in Leipzig (immortalized in Goethe’s Faust and still behind the “iron curtain” back then), where the authors enjoyed a number of beers with their doctoral father Martin Grötschel and their (inofficial) doctoral grandfather Manfred Padberg who came as a Humboldt senior scientist, see Fig. 12. (The latter certainly claims grandfathership!)

Fig. 12

Three scientific generations in Auerbachs Keller 1989, from left to right: Gerhard Reinelt, Michael Jünger, Martin Grötschel, Marc Oliver Padberg, Manfred Padberg

In 1990, Peter Gritzmann joined the faculty as an associate professor, which strengthened the sizeable group of combinatorial optimizers in Augsburg even further. The group of doctoral students grew again, when Carlos Ferreira came from Brazil.

The last applied project we did with Martin involved robot control in cooperation with the Forschungsinstitut für Anwendungsorientierte Wissensverarbeitung (FAW) in Ulm. We modeled the task as a shortest Hamiltonian path problem with precedence constraints, and the work in this area would later turn out to be useful for various further applications. The project started in 1990, and with Norbert Ascheuer we got another original first-generation Augsburg student on board. It ended in 1991, by which time both authors had already left the University of Augsburg for professorships in Paderborn and Heidelberg.

But 1991 was also the year Martin left Augsburg for Berlin, taking all his remaining scientific assistants and doctoral students with him, including the freshly graduated students Ralf Borndörfer and Andreas Löbel. In collaboration with his colleagues Karl-Heinz Hoffmann and Hans Georg Bock, he had tried hard to establish working conditions in Augsburg that would reflect the success and growth of the application-oriented working groups of the Mathematics Department. An article in the Augsburger Allgemeine from March 2, 1991, describes the efforts to found a new institute called the “Institut für mathematische Optimierung und Steuerung (IMOS)” at the University of Augsburg. Yet this initiative (and formal application) sparked little or no interest among the authorities in the state capital, Munich. Martin is cited as having said “Noch diesen Monat oder ich gehe.” (“Either it happens this month or I’m going.”), though he still held out hope for at least a provisional start of such an institute near the university campus: “Wir könnten noch heuer anfangen.” (“We could still start this year.”) They couldn’t, so they left Augsburg, as did Peter Gritzmann in the same year.

This was the end of an exceptionally dynamic and productive period for application-oriented mathematics in Augsburg. Subsequently the old and new professors spread out, and the field took off, especially with regard to Combinatorial Optimization, where Berlin is now one of the world’s leading centers.

4 Conclusion

We were very lucky for the time we shared! Thanks, dear Martin!