Martin Grötschel : La géométrie des problèmes difficiles

En 1982, le prix Fulkerson —l'honneur le plus exigeant en mathématiques discrètes, décerné conjointement par l'American Mathematical Society et la Mathematical Optimization Society— a récompensé des travaux sur la méthode de l'ellipsoïde. Le résultat sous-jacent, développé par Martin Grötschel avec László Lovász et Alexander Schrijver, a établi un principe qui régit encore la pensée des théoriciens sur l'optimisation combinatoire : pour une très large classe de problèmes, être capable de séparer —répondre si un point se trouve à l'intérieur d'un ensemble et, sinon, produire un hyperplan le prouvant— est informatiquement équivalent à être capable d' optimiser sur cet ensemble. L'optimisation et la séparation sont la même difficulté sous des formes différentes.

De Schwelm à Bonn

Grötschel est né le 10 septembre 1948 à Schwelm, une petite ville industrielle de Rhénanie-du-Nord-Westphalie. Il a étudié les mathématiques avec une mineure en économie à l'université de Bochum à partir de 1969, obtenant son Diplom en 1973, puis a rejoint l'université de Bonn en tant qu'assistant de recherche, où il est resté neuf ans. Son doctorat a été obtenu en 1977 sous la direction de Bernhard Korte, l'un des fondateurs de l'optimisation discrète allemande ; son habilitation, en recherche opérationnelle, a suivi à Bonn en 1981.

Ses travaux de doctorat se sont attaqués directement au problème le plus célèbre et difficile de la discipline. Grötschel a fait progresser la méthode des plans coupants pour le problème du voyageur de commerce —l'approche consistant à relaxer un problème combinatoire difficile en un problème continu, à résoudre la version simple, puis à ajouter des inégalités qui éliminent les réponses fractionnaires produites par la relaxation, en itérant jusqu'à ce que la solution soit entière. La technique dépend entièrement de la connaissance des inégalités à ajouter, et la recherche de celles-ci, la combinatoire polyédrale, est devenue le centre de sa carrière : comprendre la géométrie de l'enveloppe convexe des solutions réalisables d'un problème, car c'est dans cette géométrie que réside réellement la difficulté.

Ellipsoïdes

La méthode de l'ellipsoïde est arrivée en Occident en 1979 comme la première preuve que la programmation linéaire est résoluble en temps polynomial. Elle était, et reste, sans espoir en pratique —bien plus lente que la méthode du simplexe qu'elle dominait théoriquement. Ce que Grötschel, Lovász et Schrijver ont compris, c'est que sa véritable force n'était pas en tant qu'algorithme, mais en tant qu'outil de preuve.

Comme la méthode de l'ellipsoïde n'a besoin que d'un oracle de séparation plutôt que d'une liste explicite de contraintes, elle peut optimiser sur des polyèdres ayant un nombre exponentiel de facettes, à condition de pouvoir identifier efficacement une contrainte violée. Cette observation a transformé d'un coup une pile de questions ouvertes en problèmes résolus : des familles entières de problèmes combinatoires se sont révélées résolubles en temps polynomial sans qu'il soit nécessaire de construire un algorithme direct pour eux. Le cadre a été exposé en détail dans la monographie Geometric Algorithms and Combinatorial Optimization, devenue l'une des références standard du domaine. Le prix Fulkerson en 1982 a reconnu ce travail ; le prix George B. Dantzig a suivi en 1991.

Berlin

Grötschel a occupé la chaire de mathématiques appliquées à l'université d'Augsbourg de 1982 à 1991, puis a déménagé à Berlin, où il a passé le reste de sa vie professionnelle. Il est devenu professeur titulaire de technologie de l'information à la Technische Universität Berlin en 1991 et vice-président du Zuse Institute Berlin la même année, prenant la présidence du ZIB en 2012 et l'occupant jusqu'en 2015. Il a été président de l'Académie des sciences et des lettres de Berlin-Brandebourg de 2015 à 2020, et est professeur affilié distingué à l'université technique de Munich depuis 2011.

Les décennies berlinoises ont orienté son intérêt vers les applications, sans abandonner la théorie. Il a cofondé et dirigé le centre de recherche DFG Matheon, une institution fondée sur l'idée que les problèmes industriels et infrastructurels génèrent de véritables nouvelles mathématiques plutôt que de simplement consommer des mathématiques anciennes. Son travail appliqué touche à la planification de la production, à l'ordonnancement des transports publics, aux systèmes énergétiques et à la logistique —des domaines où quelques pour cent d'amélioration dans un calendrier combinatoire valent beaucoup d'argent et une quantité mesurable de carbone.

Il a également été un bâtisseur d'institutions inhabituellement actif. Il a été président de la Société mathématique allemande en 1993-94, secrétaire général de l'Union mathématique internationale de 2007 à 2014 et président de l'Einstein Foundation Berlin de 2011 à 2015. Il a coédité le Handbook of Combinatorics. Les prix se sont accumulés : le prix Karl Heinz Beckurts en 1990, le prix Gottfried Wilhelm Leibniz —le prix de recherche le plus prestigieux d'Allemagne— en 1995, la médaille d'or EURO en 2004, le prix John von Neumann Theory en 2006, le prix SIAM Fellowship et le prix SIAM Distinguished Service vers 2009-10. Il est docteur honoris causa de quatre universités et appartient à sept académies, dont l'US National Academy of Engineering, la Leopoldina, l'acatech, l'Academia Europaea et l'Académie chinoise des sciences.

Pourquoi Martin est qualifié de génie

Ce mot n'est pas utilisé à son égard par son domaine, et la description honnête est différente et plus utile : Grötschel est un mathématicien de premier rang dont la distinction est exceptionnellement bien documentée par des verdicts externes. Trois des plus hautes récompenses en optimisation —Fulkerson, Dantzig, von Neumann— plus le prix Leibniz et l'adhésion aux académies nationales américaine, allemande et chinoise constituent une trace écrite d'une excellence technique soutenue que très peu de mathématiciens en activité accumulent.

La qualité spécifique est architecturale plutôt que tape-à-l'œil. L'intuition de la méthode de l'ellipsoïde en est l'exemple le plus clair : l'exploit n'était pas d'inventer un nouvel algorithme, mais de reconnaître qu'un algorithme existant et pratiquement inutile encodait une équivalence générale, puis d'extraire de cette équivalence une machine pour régler des questions à travers toute une discipline. C'est un esprit particulier —celui qui regarde un outil et voit un théorème. Le même instinct se manifeste dans le programme polyédral, où l'idée est de convertir une recherche discrète en une question sur la forme d'un corps convexe, et à nouveau à Matheon, où l'idée est de traiter un problème d'ordonnancement industriel comme une source de mathématiques plutôt que comme une simple application.

Le contre-argument est simple et vaut la peine d'être énoncé. Les résultats centraux de Grötschel sont partagés avec des collaborateurs, principalement Lovász et Schrijver, et il serait inexact de lui attribuer seul l'équivalence séparation-optimisation. Sa renommée est confinée à sa spécialité ; en dehors de l'optimisation combinatoire et de la recherche opérationnelle, il est essentiellement inconnu, et aucun résultat ne porte son nom dans le vocabulaire mathématique général. Une fraction substantielle de sa fin de carrière a été consacrée à l'administration, aux organismes de financement et aux présidences de sociétés plutôt qu'aux preuves. Ce que le dossier soutient, ce n'est pas un génie acclamé, mais quelque chose de plus précisément précieux : une carrière de résultats de premier ordre, un cadre que le domaine utilise encore quotidiennement, et un héritage institutionnel à Berlin qui survit à tout théorème individuel.

Héritage

L'équivalence séparation-optimisation est désormais un équipement standard, enseigné à chaque étudiant diplômé dans le domaine et invoqué chaque fois qu'une nouvelle classe de relaxations est proposée. L'approche polyédrale qu'il a contribué à établir sous-tend les solveurs commerciaux de programmation entière qui dirigent les avions, ordonnancent les trains et planifient les réseaux électriques. Et le ZIB, Matheon et l'école d'optimisation de Berlin sont des faits institutionnels sur le terrain, dotés d'un personnel ayant appris de lui qu'un problème pratique difficile et un problème mathématique profond sont souvent le même objet vu sous deux angles.