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.