Martin Grötschel: La geometria dei problemi difficili

Nel 1982, il premio Fulkerson —l'onorificenza più esigente della matematica discreta, assegnata congiuntamente dall'American Mathematical Society e dalla Mathematical Optimization Society— è stato conferito a un lavoro sul metodo dell'ellissoide. Il risultato alla base, sviluppato da Martin Grötschel con László Lovász e Alexander Schrijver, ha stabilito qualcosa che ancora oggi governa il modo in cui i teorici pensano all'ottimizzazione combinatoria: che per una classe molto ampia di problemi, essere in grado di separare —rispondere se un punto si trova all'interno di un insieme e, in caso contrario, produrre un iperpiano che lo provi— è computazionalmente equivalente a essere in grado di ottimizzare su quell'insieme. L'ottimizzazione e la separazione sono la stessa difficoltà sotto spoglie diverse.

Da Schwelm a Bonn

Grötschel è nato il 10 settembre 1948 a Schwelm, una piccola città industriale nella Renania Settentrionale-Vestfalia. Ha studiato matematica con una specializzazione in economia all'Università di Bochum dal 1969, conseguendo il suo Diplom nel 1973, e poi si è trasferito all'Università di Bonn come assistente di ricerca, dove è rimasto per nove anni. Il suo dottorato è arrivato nel 1977 sotto la guida di Bernhard Korte, uno dei fondatori dell'ottimizzazione discreta tedesca; la sua abilitazione, in ricerca operativa, è seguita a Bonn nel 1981.

Il lavoro di dottorato è andato dritto al problema più famoso e ostico della disciplina. Grötschel ha fatto progredire il metodo dei piani di taglio per il problema del commesso viaggiatore —l'approccio in cui si rilassa un difficile problema combinatorio in uno continuo, si risolve la versione facile e poi si aggiungono disuguaglianze che tagliano via le risposte frazionarie che la rilassazione produce, iterando fino a quando la soluzione è intera. La tecnica vive o muore sulla base della conoscenza di quali disuguaglianze aggiungere, e la ricerca di esse, la combinatoria poliedrale, è diventata il centro della sua carriera: comprendere la geometria dell'inviluppo convesso delle soluzioni ammissibili di un problema, perché è in quella geometria che risiede realmente la difficoltà.

Elissoidi

Il metodo dell'ellissoide è arrivato in Occidente nel 1979 come prima prova che la programmazione lineare è risolvibile in tempo polinomiale. Era, e rimane, senza speranza nella pratica —molto più lento del metodo del simplesso che teoricamente dominava. Ciò che Grötschel, Lovász e Schrijver hanno visto è che il suo vero potere non era come algoritmo, ma come dispositivo di prova.

Poiché il metodo dell'ellissoide ha bisogno solo di un oracolo di separazione piuttosto che di un elenco esplicito di vincoli, può ottimizzare su poliedri con un numero esponenziale di facce, a condizione che si riesca a riconoscere un vincolo violato in modo efficiente. Quell'osservazione ha convertito una pila di domande aperte in questioni risolte in un colpo solo: intere famiglie di problemi combinatori si sono dimostrate risolvibili in tempo polinomiale senza che nessuno costruisse un algoritmo diretto per loro. Il quadro è stato esposto per intero nella monografia Geometric Algorithms and Combinatorial Optimization, che è diventata uno dei riferimenti standard del campo. Il premio Fulkerson del 1982 ha riconosciuto il lavoro; il premio George B. Dantzig è seguito nel 1991.

Berlino

Grötschel ha ricoperto la cattedra di matematica applicata all'Università di Augusta dal 1982 al 1991, poi si è trasferito a Berlino, dove ha trascorso il resto della sua vita lavorativa. È diventato professore ordinario di tecnologia dell'informazione alla Technische Universität Berlin nel 1991 e vicepresidente dello Zuse Institute Berlin lo stesso anno, assumendo la presidenza dello ZIB nel 2012 e mantenendola fino al 2015. Ha servito come presidente dell'Accademia delle scienze e delle lettere di Berlino-Brandeburgo dal 2015 al 2020, ed è Distinguished Affiliated Professor presso l'Università Tecnica di Monaco dal 2011.

I decenni berlinesi hanno spostato la sua enfasi verso le applicazioni, senza abbandonare la teoria. Ha co-fondato e presieduto il centro di ricerca DFG Matheon, un'istituzione costruita sulla premessa che i problemi industriali e infrastrutturali generano matematica genuinamente nuova piuttosto che consumare semplicemente la vecchia. Il suo lavoro applicato raggiunge la pianificazione della produzione, la programmazione dei trasporti pubblici, i sistemi energetici e la logistica —ambiti in cui un miglioramento di pochi punti percentuali in un programma combinatorio vale una grande quantità di denaro e una quantità misurabile di carbonio.

È stato anche un costruttore di istituzioni insolitamente attivo. Ha servito come presidente della Società matematica tedesca nel 1993-94, come segretario generale dell'Unione matematica internazionale dal 2007 al 2014 e come presidente dell'Einstein Foundation Berlin dal 2011 al 2015. Ha co-curato l' Handbook of Combinatorics. I premi si sono accumulati: il premio Karl Heinz Beckurts nel 1990, il premio Gottfried Wilhelm Leibniz —il premio di ricerca più prezioso della Germania— nel 1995, la medaglia d'oro EURO nel 2004, il premio John von Neumann Theory nel 2006, il SIAM Fellowship e il premio SIAM Distinguished Service intorno al 2009-10. Detiene lauree honoris causa da quattro università e appartiene a sette accademie, tra cui l'US National Academy of Engineering, la Leopoldina, l'acatech, l'Academia Europaea e l'Accademia cinese delle scienze.

Perché Martin è definito un genio

La parola non è una di quelle che il suo campo usa per lui, e la descrizione onesta è diversa e più utile: Grötschel è un matematico di primo piano la cui distinzione è insolitamente ben documentata da verdetto esterno. Tre dei massimi riconoscimenti nell'ottimizzazione —Fulkerson, Dantzig, von Neumann— più il premio Leibniz e l'adesione alle accademie nazionali americana, tedesca e cinese costituiscono una scia documentale di eccellenza tecnica sostenuta che pochissimi matematici in attività accumulano.

La qualità specifica è architettonica piuttosto che appariscente. L'intuizione del metodo dell'ellissoide ne è l'esempio più chiaro: il risultato non è stato inventare un nuovo algoritmo, ma riconoscere che uno esistente e praticamente inutile codificava un'equivalenza generale, e poi estrarre da quell'equivalenza una macchina per risolvere questioni in un'intera disciplina. È un tipo particolare di mente —quella che guarda uno strumento e vede un teorema. Lo stesso istinto si mostra nel programma poliedrale, dove la mossa è convertire una ricerca discreta in una domanda sulla forma di un corpo convesso, e ancora nel Matheon, dove la mossa è trattare un problema di programmazione industriale come fonte di matematica piuttosto che come applicazione di essa.

Il controesempio è diretto e vale la pena di essere esposto. I risultati centrali di Grötschel sono condivisi con collaboratori, principalmente Lovász e Schrijver, e sarebbe travisare il record attribuire l'equivalenza separazione-ottimizzazione solo a lui. La sua fama è confinata alla sua specializzazione; al di fuori dell'ottimizzazione combinatoria e della ricerca operativa è essenzialmente sconosciuto, e nessun risultato porta il suo nome nel vocabolario matematico generale. Una frazione sostanziale della sua carriera successiva è andata nell'amministrazione, negli organi di finanziamento e nelle presidenze di società piuttosto che nelle dimostrazioni. Ciò che il record supporta non è un genio acclamato, ma qualcosa di più precisamente prezioso: una carriera di risultati di primo livello, un quadro che il campo usa ancora quotidianamente e un'eredità istituzionale a Berlino che sopravvive a qualsiasi singolo teorema.

Eredità

L'equivalenza separazione-ottimizzazione è ora un equipaggiamento standard, insegnato a ogni studente laureato nell'area e invocato ogni volta che viene proposta una nuova classe di rilassazioni. L'approccio poliedrale che ha contribuito a stabilire è alla base dei risolutori commerciali di programmazione intera che instradano gli aerei, pianificano i treni e progettano le reti elettriche. E lo ZIB, il Matheon e la scuola di ottimizzazione di Berlino sono fatti istituzionali sul campo, dotati di personale che ha imparato da lui che un problema pratico difficile e un problema matematico profondo sono spesso lo stesso oggetto visto da due lati.