Martin Grötschel: La geometría de los problemas difíciles

En 1982, el Premio Fulkerson —el honor más exigente de la matemática discreta, otorgado conjuntamente por la Sociedad Matemática Estadounidense y la Sociedad de Optimización Matemática— fue concedido a un trabajo sobre el método del elipsoide. El resultado detrás de este, desarrollado por Martin Grötschel junto a László Lovász y Alexander Schrijver, estableció algo que todavía rige cómo los teóricos piensan sobre la optimización combinatoria: que para una clase muy amplia de problemas, ser capaz de separar —responder si un punto se encuentra dentro de un conjunto y, si no, producir un hiperplano que lo demuestre— es computacionalmente equivalente a ser capaz de optimizar sobre ese conjunto. La optimización y la separación son la misma dificultad con diferente apariencia.

De Schwelm a Bonn

Grötschel nació el 10 de septiembre de 1948 en Schwelm, una pequeña ciudad industrial en Renania del Norte-Westfalia. Estudió matemáticas con una especialización en economía en la Universidad de Bochum desde 1969, obteniendo su Diplom en 1973, y luego se trasladó a la Universidad de Bonn como asistente de investigación, donde permaneció durante nueve años. Su doctorado lo obtuvo en 1977 bajo la dirección de Bernhard Korte, uno de los fundadores de la optimización discreta alemana; su habilitación, en investigación operativa, siguió en Bonn en 1981.

El trabajo doctoral abordó directamente el problema difícil más famoso de la disciplina. Grötschel avanzó el método de planos de corte para el Problema del Viajante —el enfoque en el que uno relaja un problema combinatorio difícil en uno continuo, resuelve la versión fácil y luego añade desigualdades que eliminan las respuestas fraccionarias que produce la relajación, iterando hasta que la solución es entera. La técnica vive o muere dependiendo de saber qué desigualdades añadir, y la búsqueda de estas, la combinatoria poliédrica, se convirtió en el centro de su carrera: entender la geometría de la envolvente convexa de las soluciones factibles de un problema, porque esa geometría es donde reside realmente la dificultad.

Elipsoides

El método del elipsoide llegó a Occidente en 1979 como la primera prueba de que la programación lineal es resoluble en tiempo polinómico. Era, y sigue siendo, inútil en la práctica —mucho más lento que el método símplex que teóricamente superó. Lo que Grötschel, Lovász y Schrijver vieron fue que su verdadero poder no era como algoritmo, sino como dispositivo de prueba.

Debido a que el método del elipsoide solo necesita un oráculo de separación en lugar de una lista explícita de restricciones, puede optimizar sobre poliedros con una cantidad exponencial de facetas, siempre que se pueda reconocer una restricción violada de manera eficiente. Esa observación convirtió un conjunto de preguntas abiertas en cerradas de un solo golpe: familias enteras de problemas combinatorios demostraron ser resolubles en tiempo polinómico sin que nadie construyera un algoritmo directo para ellos. El marco se estableció por completo en la monografía Geometric Algorithms and Combinatorial Optimization, que se convirtió en una de las referencias estándar del campo. El Premio Fulkerson en 1982 reconoció el trabajo; el Premio George B. Dantzig siguió en 1991.

Berlín

Grötschel ocupó la cátedra de matemáticas aplicadas en la Universidad de Augsburgo de 1982 a 1991, luego se trasladó a Berlín, donde pasó el resto de su vida laboral. Se convirtió en profesor titular de tecnología de la información en la Technische Universität Berlin en 1991 y vicepresidente del Instituto Zuse de Berlín el mismo año, asumiendo la presidencia del ZIB en 2012 y manteniéndola hasta 2015. Se desempeñó como presidente de la Academia de Ciencias y Humanidades de Berlín-Brandeburgo de 2015 a 2020, y ha sido profesor afiliado distinguido en la Universidad Técnica de Múnich desde 2011.

Las décadas de Berlín desplazaron su énfasis hacia las aplicaciones, sin abandonar la teoría. Cofundó y presidió el Centro de Investigación DFG Matheon, una institución construida sobre la premisa de que los problemas industriales y de infraestructura generan matemáticas genuinamente nuevas en lugar de simplemente consumir matemáticas antiguas. Su trabajo aplicado llega a la planificación de la producción, la programación del transporte público, los sistemas energéticos y la logística: dominios donde un par de puntos porcentuales de mejora en un programa combinatorio valen mucho dinero y una cantidad medible de carbono.

También fue un constructor de instituciones inusualmente activo. Se desempeñó como presidente de la Sociedad Matemática Alemana en 1993-94, como secretario general de la Unión Matemática Internacional de 2007 a 2014 y como presidente de la Fundación Einstein de Berlín de 2011 a 2015. Coeditó el Handbook of Combinatorics. Los premios se acumularon: el Premio Karl Heinz Beckurts en 1990, el Premio Gottfried Wilhelm Leibniz —el galardón de investigación más valioso de Alemania— en 1995, la Medalla de Oro EURO en 2004, el Premio de Teoría John von Neumann en 2006, la membresía SIAM y el Premio de Servicio Distinguido SIAM alrededor de 2009-10. Posee doctorados honoris causa de cuatro universidades y pertenece a siete academias, incluidas la Academia Nacional de Ingeniería de EE. UU., la Leopoldina, acatech, la Academia Europaea y la Academia China de las Ciencias.

Por qué Martin es llamado genio

La palabra no es una que su campo utilice sobre él, y la descripción honesta es diferente y más útil: Grötschel es un matemático de primer nivel cuya distinción está inusualmente bien documentada por el veredicto externo. Tres de los premios más altos en optimización —Fulkerson, Dantzig, von Neumann— más el Premio Leibniz y la pertenencia a las academias nacionales estadounidense, alemana y china constituyen un rastro de excelencia técnica sostenida que muy pocos matemáticos en activo reúnen.

La calidad específica es arquitectónica más que llamativa. La intuición del método del elipsoide es el ejemplo más claro: el logro no fue inventar un nuevo algoritmo, sino reconocer que uno existente, prácticamente inútil, codificaba una equivalencia general, y luego extraer de esa equivalencia una máquina para resolver preguntas en toda una disciplina. Ese es un tipo particular de mente: una que mira una herramienta y ve un teorema. El mismo instinto se muestra en el programa poliédrico, donde el movimiento es convertir una búsqueda discreta en una pregunta sobre la forma de un cuerpo convexo, y nuevamente en Matheon, donde el movimiento es tratar un problema de programación industrial como una fuente de matemáticas en lugar de una aplicación de estas.

El contraargumento es sencillo y merece ser mencionado. Los resultados centrales de Grötschel son compartidos con colaboradores, principalmente Lovász y Schrijver, y sería una tergiversación del registro atribuirle la equivalencia entre separación y optimización solo a él. Su fama se limita a su especialidad; fuera de la optimización combinatoria y la investigación operativa es esencialmente desconocido, y ningún resultado lleva su nombre al vocabulario matemático general. Una parte sustancial de su carrera posterior se dedicó a la administración, los organismos de financiación y las presidencias de sociedades en lugar de a las pruebas. Lo que el registro apoya no es un genio aclamado, sino algo más precisamente valioso: una carrera de resultados de primer orden, un marco que el campo todavía usa a diario y un legado institucional en Berlín que sobrevive a cualquier teorema individual.

Legado

La equivalencia separación-optimización es ahora un equipo estándar, enseñado a cada estudiante de posgrado en el área e invocado cada vez que se propone una nueva clase de relajaciones. El enfoque poliédrico que ayudó a establecer subyace en los solucionadores comerciales de programación entera que dirigen aviones, programan trenes y planifican redes eléctricas. Y el ZIB, Matheon y la escuela de optimización de Berlín son hechos institucionales sobre el terreno, integrados por personas que aprendieron de él que un problema práctico difícil y uno matemático profundo son frecuentemente el mismo objeto visto desde dos lados.