Martin Grötschel

Martin Grötschel: The Geometry of Hard Problems

In 1982 the Fulkerson Prize — discrete mathematics' most exacting honour, awarded jointly by the American Mathematical Society and the Mathematical Optimization Society — went to work on the ellipsoid method. The result behind it, developed by Martin Grötschel with László Lovász and Alexander Schrijver, established something that still governs how theorists think about combinatorial optimization: that for a very wide class of problems, being able to *separate* — to answer whether a point lies inside a set, and if not to produce a hyperplane proving it — is computationally equivalent to being able to *optimize* over that set. Optimization and separation are the same difficulty wearing different clothes.

Schwelm to Bonn

Grötschel was born on 10 September 1948 in Schwelm, a small industrial town in North Rhine-Westphalia. He studied mathematics with a minor in economics at the University of Bochum from 1969, taking his Diplom in 1973, and then moved to the University of Bonn as a research assistant, where he stayed for nine years. His doctorate came in 1977 under Bernhard Korte, one of the founders of German discrete optimization; his habilitation, in operations research, followed at Bonn in 1981.

The doctoral work went straight to the discipline's most famous unfriendly problem. Grötschel advanced the cutting-plane method for the Traveling Salesman Problem — the approach in which one relaxes a hard combinatorial problem into a continuous one, solves the easy version, and then adds inequalities that cut away the fractional answers the relaxation produces, iterating until the solution is integral. The technique lives or dies on knowing which inequalities to add, and the search for them, polyhedral combinatorics, became the centre of his career: understanding the geometry of the convex hull of a problem's feasible solutions, because that geometry is where the difficulty actually resides.

Ellipsoids

The ellipsoid method arrived in the West in 1979 as the first proof that linear programming is solvable in polynomial time. It was, and remains, hopeless in practice — far slower than the simplex method it theoretically dominated. What Grötschel, Lovász and Schrijver saw was that its real power was not as an algorithm but as a proof device.

Because the ellipsoid method needs only a separation oracle rather than an explicit list of constraints, it can optimize over polyhedra with exponentially many facets, provided you can recognise a violated constraint efficiently. That observation converted a stack of open questions into settled ones at a stroke: whole families of combinatorial problems were shown to be solvable in polynomial time without anyone constructing a direct algorithm for them. The framework was set out in full in the monograph *Geometric Algorithms and Combinatorial Optimization*, which became one of the standard references of the field. The Fulkerson Prize in 1982 recognised the work; the George B. Dantzig Prize followed in 1991.

Berlin

Grötschel held the chair of applied mathematics at the University of Augsburg from 1982 to 1991, then moved to Berlin, where he spent the rest of his working life. He became full professor of information technology at the Technische Universität Berlin in 1991 and Vice President of the Zuse Institute Berlin the same year, taking the presidency of ZIB in 2012 and holding it until 2015. He served as President of the Berlin-Brandenburg Academy of Sciences and Humanities from 2015 to 2020, and has been a Distinguished Affiliated Professor at the Technical University of Munich since 2011.

The Berlin decades shifted his emphasis toward applications, without abandoning the theory. He co-founded and chaired the DFG Research Center Matheon, an institution built on the premise that industrial and infrastructural problems generate genuinely new mathematics rather than merely consuming old mathematics. His applied work reaches into production planning, public transport scheduling, energy systems and logistics — domains where a few per cent of improvement in a combinatorial schedule is worth a great deal of money and a measurable amount of carbon.

He was also an unusually active institution-builder. He served as President of the German Mathematical Society in 1993–94, as General Secretary of the International Mathematical Union from 2007 to 2014, and as chair of the Einstein Foundation Berlin from 2011 to 2015. He co-edited the *Handbook of Combinatorics*. The prizes accumulated: the Karl Heinz Beckurts Prize in 1990, the Gottfried Wilhelm Leibniz Prize — Germany's most valuable research award — in 1995, the EURO Gold Medal in 2004, the John von Neumann Theory Prize in 2006, SIAM Fellowship and the SIAM Distinguished Service Prize around 2009–10. He holds honorary doctorates from four universities and belongs to seven academies, including the US National Academy of Engineering, the Leopoldina, acatech, Academia Europaea and the Chinese Academy of Sciences.

Why Martin Is Called a Genius

The word is not one his field uses about him, and the honest description is different and more useful: Grötschel is a mathematician of the first rank whose distinction is unusually well documented by external verdict. Three of the highest awards in optimization — Fulkerson, Dantzig, von Neumann — plus the Leibniz Prize and membership of the American, German and Chinese national academies constitute a paper trail of sustained technical excellence that very few working mathematicians assemble.

The specific quality is architectural rather than flashy. The ellipsoid-method insight is the clearest example: the achievement was not inventing a new algorithm but recognising that an existing, practically useless one encoded a general equivalence, and then extracting from that equivalence a machine for settling questions across an entire subject. That is a particular kind of mind — one that looks at a tool and sees a theorem. The same instinct shows in the polyhedral programme, where the move is to convert a discrete search into a question about the shape of a convex body, and again in Matheon, where the move is to treat an industrial scheduling problem as a source of mathematics rather than an application of it.

The counter-case is straightforward and worth stating. Grötschel's central results are shared with collaborators, chiefly Lovász and Schrijver, and it would misrepresent the record to attribute the separation-optimization equivalence to him alone. His fame is confined to his specialism; outside combinatorial optimization and operations research he is essentially unknown, and no result carries his name into the general mathematical vocabulary. A substantial fraction of his later career went into administration, funding bodies and society presidencies rather than proofs. What the record supports is not acclaimed genius but something more precisely valuable: a career of first-rate results, a framework the field still uses daily, and an institutional legacy in Berlin that outlasts any individual theorem.

Legacy

The separation-optimization equivalence is now standard equipment, taught to every graduate student in the area and invoked whenever a new class of relaxations is proposed. The polyhedral approach he helped establish underlies the commercial integer-programming solvers that route aircraft, schedule trains and plan power grids. And ZIB, Matheon and the Berlin optimization school are institutional facts on the ground, staffed by people who learned from him that a hard practical problem and a deep mathematical one are frequently the same object seen from two sides.

Achievements

• Fulkerson Prize — 1982
• Gottfried Wilhelm Leibniz Prize — 1995
• John von Neumann Theory Prize — 2006
• Alwin-Walther medal — 2006
• The George B. Dantzig Prize — 1991
• Held posts at Technische Universität Berlin, University of Augsburg and Technische Universität Berlin
• Fields: combinatorial optimization, mathematical model and mathematics