Matemáticas en provincias (y 2)

Viene de «Matemáticas en provincias (1)»

Klee y Hirsch entran en escena

Independientemente de si se probaba o no su efectividad, el método del simplex siguió siendo utilizado, pero en 1971, Klee y Minty demostraron que era posible encontrar algunos problemas de programación lineal tal que el método del simplex, con la formulación original de Dantzig, no encuentra de forma eficiente la solución exacta (en otras palabras: un ordenador actual de gran potencia podría tardar miles de años en resolver dichos problemas usando el método del simplex original). Sin embargo, no todo estaba perdido, porque se pueden encontrar variantes a la formulación original de Dantzig y algunas de dichas variantes seguían resolviendo los ejemplos de Klee y Minty de forma eficiente. En esos momentos, los científicos que trabajaban en determinar la eficiencia del algoritmo del simplex, se encontraban ante un dilema: ¿es posible diseñar una variante de la cual se pueda demostrar que es siempre eficiente? Pues bien, en la búsqueda de dicha variante, todos miraron veinticinco años atrás, a una carta escrita por Warren M. Hirsch (1918-2007) al propio Dantzig en 1957. En dicha carta se exponía una conjetura, que pasaría a llamarse la conjetura de Hirsch, que, de ser cierta, garantizaría que se puede construir una variante eficiente (eficiente en todos los casos) del método del simplex. 

Si, a estas alturas, me queda algún lector, al margen de familiares o colegas a los cuales tengo ganados de antemano, aviso que voy a entrar, aunque sea brevemente, en solo un párrafo y de forma intuitiva, a intentar hacer ver en qué consiste la conjetura de Hirsch y su relación con el método del simplex: después prometo continuar la historia que, al menos a mí, me parece interesante.

Para entender la conjetura de Hirsch, pensemos en un polígono, escojamos dos de sus vértices y contemos cuántos lados hay entre ellos (en el camino con menos lados). Ahora hagamos lo mismo con un «polígono» en el espacio, o más bien en el equivalente a un polígono en el espacio, que es un poliedro, como el cubo, o el tetraedro, siempre escogemos dos vértices y caminamos desde uno en otro usando el menor número de lados o aristas posibles. Los matemáticos no tienen ninguna dificultad en seguir subiendo de dimensiones y así hablan de politopos (esencialmente un poliedro, pero en un espacio de dimensión d). Pues bien, la conjetura de Hirsch dice que que si escogemos dos vértices de un politopo con n puntos en un espacio de dimensión d, entonces el mínimo número de lados que nos lleva de un punto en el otro nunca es mayor que n-d (dicho en otras palabras: el diámetro de dicho politopo no es nunca mayor que n-d). La relación con el método del simple surge porque dicho método considera el dominio definido por las restricciones del problema considerado (dicho dominio es un politopo) y partiendo de un vértice, se va moviendo según ciertas reglas hasta encontrar el vértice del politopo en el que se obtiene el máximo. Por tanto la conjetura de Hirsch nos dice (si hubiera sido cierta) que el número de pasos hasta alcanzar el óptimo no son muchos si diseñamos una estrategia adecuada.

Tal y como prometimos, después del párrafo anterior, volvamos con nuestra historia:

Realmente el de Hirsch es un enunciado muy simple para lo que se gastan muchos enunciados matemáticos. Pero como otros enunciados simples en matemáticas, el último teorema de Fermat, o el teorema del mapa de los cuatro colores son dos ejemplos de ello, su sencillez oculta la gran dificultad que entraña su resolución.

Evidentemente, casi desde el primer momento, dicha conjetura atrajo la atención de un gran número de investigadores, ya que, si fuera cierta, implicaría que podemos encontrar una variante del método más utilizado (el del simplex) para resolver problemas de programación lineal que pueden permitir ahorrar a empresas u organismos millones de euros. Puede que el propio Victor Klee (1925–2007) fuera uno de los máximos «propagandistas» de la conjetura de Hirsch. Al menos, fue él quien le propuso a nuestro siguiente y definitivo protagonista que intentara atacar la demostración o la refutación de dicha conjetura.

Dantzig, Hirsch, Klee y un matemático de provincias

En Julio de 2010 se celebraba en Seattle un congreso en honor de Klee y Grünbaum (otro destacado matemático con muchos resultados en politopos o en geometría discreta en general). Normalmente los congresos suelen incluir a algunos conferenciantes «estrellas», y alrededor de sus charlas se configura el resto del congreso. Pues bien, en dicho congreso en honor de dos figuras tan destacadas, uno de dichos conferenciantes estrellas no era otro que un español, Paco Santos de la Universidad de Cantabria, uno de esos matemáticos de provincias, algo que no hubiera ocurrido jamás en un congreso equivalente cincuenta años antes. Además, nuestro matemático de provincias envió un resumen de su charla que lo convirtió en la máxima atracción de todo el congreso (iba a decir que su resumen era un tanto chulillo, pero no sé si queda bien). Lo copio aquí literalmente:

Un contraejemplo a la conjetura de Hirsch 

Solo he estado en Seattle una vez, en enero de 2002, para impartir un coloquio en la Universidad de Washington. Aunque Victor Klee ya estaba jubilado —tenía setenta y seis años— vino al Departamento de Matemáticas para charlar conmigo. Tuvimos una amena conversación en el transcurso de la cual me preguntó: ¿Por qué no intentas refutar la conjetura de Hirsch? 

Después he averiguado que él le proponía lo mismo a mucha gente, incluyendo a todos sus estudiantes, pero la cuestión y la forma en la que me la propuso me hicieron sentirme especial en ese momento. Esta charla da respuesta a esa pregunta. En ella describiré la construcción de un politopo de dimensión 43 con 86 facetas y diámetro mayor que 43. La prueba se basa en una generalización del teorema de los d pasos de Klee y Walkup. 

El mismo día en el que envió el resumen de su charla, el 10 de mayo de 2010, la noticia corrió como un reguero de de pólvora, incluso en menos de veinticuatro horas ya se había modificado la entrada de la Wikipedia en inglés correspondiente a la conjetura de Hirsch incluyendo el resultado de Paco.

El cuándo y cómo se le ocurrió a Paco Santos el contraejemplo es paradigmático del proceso de invención en matemáticas, y muy similar al relatado por el gran matemático francés Henri Poincaré (de quien se dice que fue el último matemático que conocía todas las matemáticas de su época) en su conferencia sobre la «Invención en matemáticas». Paco llevaba tiempo pensando en cómo construir dicho contraejemplo, pero la solución al enigma le vino en un vuelo Bilbao-París. Como él mismo dice, con el quehacer diario casi no se tiene tiempo de leer artículos de otros autores o de pensar relajadamente. Así que, en mitad del vuelo, mientras hojeaba una revista matemática, le llegó la inspiración: dejó la revista, cogió un cuaderno y anotó las ideas para comprobar que todo estaba correcto y asegurarse de que no se olvidaba nada. La revista se la dejó olvidada en el avión, pero la conjetura de Hirsch acababa de ser vencida. Por cierto, Poincaré lo que relata en la conferencia a la que hemos hecho mención es que el «vio» la solución del problema en el que estaba trabajando justo al poner el pie en el estribo de un tranvía.

En vista de la existencia de un contraejemplo a la conjetura de Hirsch, puede parecer que se cierra por completo la posibilidad de demostrar que existe una variante del método del simplex del cual se pueda demostrar su eficiencia. Nada más lejos de la realidad, por dos razones: en primer lugar el contraejemplo construido por Paco Santos no muestra que existen politopos cuyo diámetro es mayor que el predicho por la conjetura de Hirsch, pero no mucho mayor, con lo cual todavía queda la esperanza de demostrar que el diámetro de un politopo nunca es muy grande. Por otra parte, es posible que alguien proponga un método revolucionario que pruebe directamente que existe una variante del método del simplex eficiente o que ninguna lo es. Son todos esto problemas, no resueltos en la actualidad, más oportunidades que se presentan hoy en día para que un matemático «de provincias» pueda codearse con la élite mundial de las matemáticas, élite de la que Paco Santos, Isabel Fernández o Pablo Mira forman parte.