Martin Grötschel: A Geometria de Problemas Difíceis

Em 1982, o Prémio Fulkerson —a honra mais exigente da matemática discreta, atribuída conjuntamente pela Sociedade Matemática Americana e pela Sociedade de Otimização Matemática— foi concedido a um trabalho sobre o método do elipsoide. O resultado subjacente, desenvolvido por Martin Grötschel com László Lovász e Alexander Schrijver, estabeleceu algo que ainda rege a forma como os teóricos pensam sobre a otimização combinatória: que, para uma classe muito vasta de problemas, ser capaz de separar —responder se um ponto se encontra dentro de um conjunto e, caso contrário, produzir um hiperplano que o prove— é computacionalmente equivalente a ser capaz de otimizar sobre esse conjunto. A otimização e a separação são a mesma dificuldade com roupas diferentes.

De Schwelm a Bona

Grötschel nasceu a 10 de setembro de 1948 em Schwelm, uma pequena cidade industrial na Renânia do Norte-Vestefália. Estudou matemática com especialização em economia na Universidade de Bochum a partir de 1969, obtendo o seu Diplom em 1973, e depois mudou-se para a Universidade de Bona como assistente de investigação, onde permaneceu durante nove anos. O seu doutoramento foi obtido em 1977 sob a orientação de Bernhard Korte, um dos fundadores da otimização discreta alemã; a sua habilitação, em investigação operacional, seguiu-se em Bona em 1981.

O trabalho de doutoramento abordou diretamente o problema mais famoso e difícil da disciplina. Grötschel fez avançar o método dos planos de corte para o Problema do Caixeiro Viajante —a abordagem na qual se relaxa um problema combinatório difícil para um contínuo, resolve-se a versão fácil e, em seguida, adicionam-se desigualdades que eliminam as respostas fracionárias que a relaxação produz, iterando até que a solução seja inteira. A técnica vive ou morre dependendo de saber quais desigualdades adicionar, e a procura por elas, a combinatória poliédrica, tornou-se o centro da sua carreira: compreender a geometria da envoltória convexa das soluções viáveis de um problema, porque é nessa geometria que reside realmente a dificuldade.

Elipsoides

O método do elipsoide chegou ao Ocidente em 1979 como a primeira prova de que a programação linear é solúvel em tempo polinomial. Era, e continua a ser, inútil na prática —muito mais lento do que o método simplex que teoricamente dominou. O que Grötschel, Lovász e Schrijver perceberam foi que o seu verdadeiro poder não era como algoritmo, mas como um dispositivo de prova.

Como o método do elipsoide necessita apenas de um oráculo de separação em vez de uma lista explícita de restrições, pode otimizar sobre poliedros com uma quantidade exponencial de facetas, desde que se consiga reconhecer uma restrição violada de forma eficiente. Essa observação converteu, de um só golpe, uma pilha de questões em aberto em questões resolvidas: famílias inteiras de problemas combinatórios mostraram ser solúveis em tempo polinomial sem que ninguém construísse um algoritmo direto para eles. O quadro foi apresentado na totalidade na monografia Geometric Algorithms and Combinatorial Optimization, que se tornou uma das referências padrão da área. O Prémio Fulkerson em 1982 reconheceu o trabalho; o Prémio George B. Dantzig seguiu-se em 1991.

Berlim

Grötschel ocupou a cátedra de matemática aplicada na Universidade de Augsburgo de 1982 a 1991, mudando-se depois para Berlim, onde passou o resto da sua vida profissional. Tornou-se professor catedrático de tecnologia da informação na Technische Universität Berlin em 1991 e vice-presidente do Zuse Institute Berlin no mesmo ano, assumindo a presidência do ZIB em 2012 e ocupando-a até 2015. Serviu como Presidente da Academia de Ciências e Humanidades de Berlim-Brandeburgo de 2015 a 2020, e tem sido Distinguished Affiliated Professor na Universidade Técnica de Munique desde 2011.

As décadas em Berlim deslocaram a sua ênfase para as aplicações, sem abandonar a teoria. Co-fundou e presidiu o Centro de Investigação DFG Matheon, uma instituição construída sobre a premissa de que os problemas industriais e de infraestruturas geram matemática genuinamente nova, em vez de apenas consumir matemática antiga. O seu trabalho aplicado estende-se ao planeamento da produção, agendamento de transportes públicos, sistemas energéticos e logística —domínios onde alguns pontos percentuais de melhoria num calendário combinatório valem muito dinheiro e uma quantidade mensurável de carbono.

Foi também um construtor de instituições invulgarmente ativo. Serviu como Presidente da Sociedade Matemática Alemã em 1993-94, como Secretário-Geral da União Matemática Internacional de 2007 a 2014 e como presidente da Einstein Foundation Berlin de 2011 a 2015. Co-editou o Handbook of Combinatorics. Os prémios acumularam-se: o Prémio Karl Heinz Beckurts em 1990, o Prémio Gottfried Wilhelm Leibniz —o galardão de investigação mais valioso da Alemanha— em 1995, a Medalha de Ouro EURO em 2004, o Prémio de Teoria John von Neumann em 2006, SIAM Fellowship e o Prémio de Serviço Distinto SIAM por volta de 2009-10. Possui doutoramentos honoris causa de quatro universidades e pertence a sete academias, incluindo a US National Academy of Engineering, a Leopoldina, a acatech, a Academia Europaea e a Academia Chinesa de Ciências.

Porque é que Martin é chamado de génio

A palavra não é uma que a sua área utiliza sobre ele, e a descrição honesta é diferente e mais útil: Grötschel é um matemático de primeiro nível cuja distinção está invulgarmente bem documentada por veredictos externos. Três dos prémios mais elevados em otimização —Fulkerson, Dantzig, von Neumann— mais o Prémio Leibniz e a adesão às academias nacionais americana, alemã e chinesa constituem um registo de excelência técnica sustentada que muito poucos matemáticos no ativo reúnem.

A qualidade específica é arquitetónica, em vez de chamativa. A intuição do método do elipsoide é o exemplo mais claro: o feito não foi inventar um novo algoritmo, mas reconhecer que um existente, praticamente inútil, codificava uma equivalência geral, e depois extrair dessa equivalência uma máquina para resolver questões através de toda uma disciplina. Esse é um tipo particular de mente —aquela que olha para uma ferramenta e vê um teorema. O mesmo instinto mostra-se no programa poliédrico, onde o movimento é converter uma pesquisa discreta numa questão sobre a forma de um corpo convexo, e novamente no Matheon, onde o movimento é tratar um problema de agendamento industrial como uma fonte de matemática, em vez de uma aplicação desta.

O contra-argumento é direto e merece ser mencionado. Os resultados centrais de Grötschel são partilhados com colaboradores, principalmente Lovász e Schrijver, e seria deturpar o registo atribuir a equivalência separação-otimização apenas a ele. A sua fama está confinada à sua especialidade; fora da otimização combinatória e da investigação operacional, ele é essencialmente desconhecido, e nenhum resultado leva o seu nome ao vocabulário matemático geral. Uma fração substancial da sua carreira posterior foi dedicada à administração, organismos de financiamento e presidências de sociedades, em vez de provas. O que o registo apoia não é um génio aclamado, mas algo mais precisamente valioso: uma carreira de resultados de primeira categoria, um quadro que a área ainda usa diariamente, e um legado institucional em Berlim que sobrevive a qualquer teorema individual.

Legado

A equivalência separação-otimização é agora equipamento padrão, ensinado a cada estudante de pós-graduação na área e invocado sempre que uma nova classe de relaxações é proposta. A abordagem poliédrica que ele ajudou a estabelecer subjaz aos solucionadores comerciais de programação inteira que encaminham aviões, agendam comboios e planeiam redes elétricas. E o ZIB, o Matheon e a escola de otimização de Berlim são factos institucionais no terreno, dotados de pessoas que aprenderam com ele que um problema prático difícil e um problema matemático profundo são frequentemente o mesmo objeto visto de dois lados.