La Conjetura de Hirsch, refutada por Francisco Santos

Nos hacemos eco en Matemáticas y sus fronteras de un importante resultado obtenido por nuestro compañero Francisco Santos, Catedrático de la Universidad de Cantabria.

La Programación Lineal y el método del símplex

En el año 2000 la revista Computing in Science and Engineering pidió a Jack Dongarra y a Francis Sullivan que eligieran los “10 algoritmos del Siglo XX”; es decir, los algoritmos más influyentes en el desarrollo de la ciencia y la ingeniería del pasado siglo. Uno de los diez elegidos fue el método del símplex en programación lineal.

La programación lineal nació hacia 1939 con los trabajos del ruso L. V. Kantorovich (1912-1986), quien en 1975 recibió el Premio Nobel de Economía por ello. Pero su desarrollo se mantuvo en secreto durante la segunda guerra mundial. No en vano se trata de la teoría de cómo organizar de la mejor manera posible una cantidad limitada de recursos (o defensas) para obtener de ellos al mayor rendimiento (o conseguir los mínimos daños).

L. V. Kantorovich

Dicho en lenguaje técnico, la programación lineal es el problema de encontrar el máximo (o mínimo) de una función lineal en un dominio definido por desigualdades también lineales. Su relevancia queda expresada en la reseña que SIAM News publicó a propósito del 80 cumpleaños de George Dantzig, mediante una cita de Eugene Lawler y otra de Laszlo Lovasz, actual presidente de la Unión Matemática Internacional. El primero dijo que la programación lineal “se usa para asignar recursos, planificar producción o carteras de inversión, organizar horarios, formular estrategias de mercado, o militares, etc. La versatilidad e impacto económico de la programación lineal en el mundo industrial de hoy es verdaderamente increíble”. El segundo: “Si hiciéramos estadísticas sobre qué problema matemático está usando más tiempo de computación en este momento en el mundo (excluyendo problemas de manejo de bases de datos, como búsqueda u ordenación) la respuesta sería probablemente programación lineal”.

G. Dantzig

El método del símplex fue publicado en 1947 por George Dantzig (1914-2005), que por entonces trabajaba en la Oficina de Control Estadístico del ejército estadounidense. Durante más de 30 años el método del símplex fue el único método practicable para resolver grandes problemas de programación lineal y, sin embargo, aún a fecha de hoy no sabemos si es un algoritmo polinómico, en el sentido de la teoría de la complejidad. Es decir, no sabemos si un problema de programación lineal con un número d de variables y un número n de restricciones puede ser resuelto mediante el método del símplex en un tiempo que dependa de manera polinómica de los parámetros n y d.

La razón fundamental de ese desconocimiento es que no sabemos, dada una región poliédrica de dimensión d y definida por n desigualdades lineales, si su grafo tiene diámetro polinómico en los parámetros n y d. El método del símplex funciona en dos etapas: primero busca un vértice arbitrario del dominio definido por las restricciones y después va moviéndose de un vértice a otro en el que el funcional a maximizar aumenta, recorriendo en cada paso una arista del politopo. Hacer esto último computacionalmente es relativamente sencillo. El método del símplex tiene cierta libertad a la hora de elegir a qué vértice vecino del actual dirigirse y el criterio utilizado para la elección de uno u otro se llama la “regla de pivote”. Pero el número de veces que hay que hacerlo será, como mínimo, la distancia del vértice original al vértice óptimo en el grafo del poliedro.  Es decir, para poder acotar la complejidad del método del símplex es necesario ser capaces primero de acotar el diámetro de los grafos de poliedros, aunque el recíproco no es cierto; incluso si supiéramos que el diámetro es pequeño, quedaría el problema de cómo hacer que el método del símplex encuentre un camino corto.

Hay que decir que, aunque se conocen otros algoritmos para programación lineal que sí son polinómicos en el modelo bit de complejidad (máquina de Turing), una “regla de pivote” polinómica para el método de símplex probaría que el mismo es fuertemente polinómico, es decir, polinómico tanto en el modelo de bit como en el modelo real. La pregunta sobre la existencia de un algoritmo polinómico para programación lineal en el modelo real fue incluida en el año 2000 por Steven Smale en su lista de Problemas matemáticos para el siglo que viene.

La conjetura de Hirsch

La conjetura de Warren M. Hirsch (1918-2007), en una carta dirigida a Dantzig en 1957, afirma que el diámetro (combinatorio) del grafo de un poliedro de dimensión d y  definido por n desigualdades no puede ser nunca mayor que n-d.

W. M. Hirsch

Dantzig la incluyó en su libro “Linear programming and extensions’‘ (1963), considerado la “Biblia” de la programación lineal. Desde entonces ha atraído la atención de matemáticos tanto puros como aplicados. Sin embargo, más de 50 años después nuestro conocimiento sobre el problema sigue siendo humillantemente escaso: no se conoce ninguna cota superior polinómica para el diámetro que se conjetura lineal!

V. Klee

En 1967, Klee y Walkup demostraron la conjetura para n ≤ d+5 y, hace apenas dos años, el caso n = d+6 ha sido verificado por Bremmer y Schewe… La demostración usa el llamado “Teorema de los d pasos”, que dice que si la conjetura de Hirsch es cierta para politopos de dimensión k con 2k caras, para un cierto valor de k, entonces también es cierta para politopos de dimensión n-k con n caras, sea quien sea n. Nótese que el teorema de los d pasos no afirma que la conjetura de Hirsch sea cierta, sólo que el caso general es equivalente al caso particular n = 2d, en cuyo caso el número de pasos conjeturado es d (de ahí el nombre).

Y esta era la situación hasta… el 10 de Mayo de 2010. Ese día, el catedrático de Geometría de la Universidad de Cantabria, Francisco Santos Leal,  envió el siguiente resumen de su próxima conferencia al congreso The Mathematics of Klee and Grünbaum: 100 years in Seattle, anunciando que había encontrado un contraejemplo a la Conjetura de Hirsch:

“He estado en Seattle sólo una vez, en enero de 2002, con motivo de una charla en la Universidad de Washington. Aunque Victor Klee ya estaba jubilado –tenía 76 años– vino al Departamento 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?

Más tarde descubrí que Klee formulaba la misma pregunta a mucha gente, incluyendo a todos sus alumnos, pero la pregunta y la forma en que me la planteó me hizo sentir especial en ese momento.  Esta charla es la respuesta a esa pregunta. Describiré la construcción de una 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.”

“I have been in Seattle only once, in January 2002, when I visited to give a colloquium talk at UW. Although Victor Klee was already retired–he was 76 years old–he came to the Department of Mathematics to talk to me. We had a nice conversation during which he asked “Why don’t you try to disprove the Hirsch Conjecture?”

I have later found out that he asked the same question to many people, including all his students, but the question and the way it was posed made me feel special at that time. This talk is the answer to that question. I will describe the construction of a 43-dimensional polytope with 86 facets and diameter bigger than 43. The proof is based on a generalization of the d-step theorem of Klee and Walkup.”

Ese mismo día, el insigne experto en combinatoria Gil Kalai publicó la noticia en su muy visitado blog ( http://gilkalai.wordpress.com ) y la entrada de “Hirsch conjecture” en la Wikipedia (http://en.wikipedia.org/wiki/Hirsch_conjecture) fue actualizada para hacerse eco de ella.

Como se dice en el resumen de la charla de F. Santos, su contraejemplo a la conjetura de Hirsch tiene dos ingredientes: una generalización del teorema de los d pasos a unos politopos en forma de huso, y la construcción explícita de cierto politopo de dimensión 5 y 48 facetas, usando en cierto modo para ello la bien conocida fibración de Hopf de la 3-esfera. La conjunción de ambas cosas demuestra la existencia de un politopo de dimensión 43, con 86 facetas y en el que el diámetro es mayor que 43!!

La corrección del contrajemplo de Santos ha sido verficada por un grupo reducido de expertos colegas que incluye al propio Kalai. Parte del contraejemplo ha sido también comprobado por ordenador.

¿Y ahora?

En 1987 Klee y Kleinschmidt escribieron un survey sobre las conjeturas de Hirsch y de los d pasos. Dicen en él: “Encontar un contrajemplo apenas constituirá un pequeño primer paso en la línea de investigación relacionada con la conjetura”. (“Finding a counterexample will be merely a small first step in the line of investigation related to the conjecture”.)

Aunque hayan sido necesarios  para dar ese “pequeño paso”, 53 años desde el enunciado de la conjetura y 23 desde que se escribió esta frase,  Santos subscribe  totalmente estas palabras. Su contraejemplo, mediante construcciones clásicas de productos y pegados, se puede convertir, señala Santos,  en una familia inifinita de contraejemplos a la conjetura de Hirsch en la que el diámetro de los poliedros construidos crece, básicamente, como 1.03 n. Es decir, violan la conjetura, que era n-d, pero sus diámetros no dejan de ser lineales y no dicen mucho sobre el problema de fondo. Quizá, por tanto, según Santos,  lo más significativo no es el contraejemplo en sí sino el Teorema generalizado de los d pasos que ha tenido que desarrollar, y que puede abrir una nueva línea de ataque al problema de encontrar cotas razonables al diámetro de un politopo y, en definitiva, a la complejidad de la programación lineal.

La versión detallada del contraejemplo de Santos está aún siendo redactada y será enviada a una de las más prestigiosas revistas de investigación matemática,  donde aparecerá, esperamos,  tras un riguroso proceso de revisión. Pero la comunidad matemática española podrá beneficiarse de un avance de ese resultado en un próximo número de  La Gaceta de la Real Sociedad Matemática Española. Ha sido, precisamente, extrayendo ideas y párrafos de un borrador inicial del  manuscrito que Santos publicará alli, lo que nos ha permitido elaborar este apunte del blog Matemáticas y sus fronteras.

¡Enhorabuena, Paco!

___________________________

Tomás Recio, Universidad de Cantabria.