Francisco Santos encuentra un contraejemplo que refuta la conjetura de Hirsch

Francisco Santos

Hace unos días en el blog de Gil Kalai se hacían eco de la refutación de la conjetura de Hirsch por parte del matemático español Francisco Santos. Cuando vi dicha noticia me puse en contacto con el propio Francisco para comentarle que estaba interesado en hablar sobre el tema en Gaussianos y para pedirle que nos hiciera un texto explicándonos el tema. Este fin de semana Paco me ha enviado amablemente la información que le pedí (también la ha enviado a Matemáticas y sus Fronteras) y hoy os la muestro a vosotros.

Programación Lineal y el método del simplex

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 siglo pasado. Uno de los diez elegidos fue el método del simplex en programación lineal.

L. V. Kantorovich

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).

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.

y 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.

George Dantzig

El método del simplex 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 simplex 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 de variables y un número de restricciones puede ser resuelto mediante el método del símplice en un tiempo que dependa de manera polinómica de los parámetros y .

La razón fundamental de ese desconocimiento es que no sabemos, dada una región poliédrica de dimensión y definida por desigualdades lineales, si su grafo tiene diámetro polinómico en los parámetros y . El método del simplex 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 simplex 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 simplex 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 simplex 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 del simplex 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

Warren M. 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 y definido por desigualdades no puede ser nunca mayor que .

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!!

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

Vic Klee

Y esta era la situación hasta….el 10 de Mayo de 2010. Ese día, el matemático 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:

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.

(«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 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 diametro mayor que 43. La prueba se basa en una generalización del teorema de los d-pasos de Klee y Walkup.»)

Ese mismo día, el insigne experto en combinatoria Gil Kalai publicó la noticia en su muy visitado blog y la entrada Hirsch conjecture de la Wikipedia fue actualizada para hacerse eco de ella.

Como se dice en el resumen de la charla de Paco Santos, su contraejemplo a la conjetura de Hirsch tiene dos ingredientes: una generalización del teorema de los 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 de ella ha sido también comprobada por ordenador.

¿Y ahora?

En 1987 Klee y Kleinschmidt escribieron un survey sobre las conjeturas de Hirsch y de los pasos. Dicen en él:

Finding a counterexample will be merely a small first step in the line of investigation related to the conjecture (Encontar un contrajemplo apenas constituirá un pequeño primer paso en la línea de investigación relacionada con la conjetura)

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 . Es decir, violan la conjetura, que era , 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 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». Este texto es precisamente un extracto del artículo enviado por el propio Francisco Santos a «La Gaceta de la RSME».