Francisco Santos encuentra un contraejemplo que refuta la conjetura de Hirsch

Francisco Santos

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

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

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 d de variables y un número n 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 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 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

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

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 n \le d+5 y, hace apenas dos años, el caso n=d+6 ha sido verificado por Bremner 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).

Vic Klee

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 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 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 d 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 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”. Este texto es precisamente un extracto del artículo enviado por el propio Francisco Santos a “La Gaceta de la RSME”.

Share

17 comentarios

  1. Trackback | 24 may, 2010

    Bitacoras.com

  2. Agustín Morales | 24 de mayo de 2010 | 14:55

    Vótalo Thumb up 0

    A mi me parece un descubrimiento importante pues puede ser una via para atacar el problema de la complejidad del algoritmo del simplex, y quien sabe si de otros algoritmos. La investigación operativa es muy joven aun y por tanto es lógico pensar que nos va a deparar muchas sorpresas todavía.

    ¡Enhorabuena a Francisco Santos! ¿Por qué no atacar ahora el resistente problema P=NP? ;-)

  3. Javi | 24 de mayo de 2010 | 16:07

    Vótalo Thumb up 0

    Mi enhorabuena a Fernando! Fue mi profesor de Topología en la Universidad de Cantabria.

  4. Javi | 24 de mayo de 2010 | 16:59

    Vótalo Thumb up 0

    …quiero decir Francisco…

  5. Trackback | 25 may, 2010

    Tweets that mention Francisco Santos encuentra un contraejemplo que refuta la conjetura de Hirsch | Gaussianos -- Topsy.com

  6. GonzaloOrellana | 25 de mayo de 2010 | 12:56

    Vótalo Thumb up 0

    Enhorabuena Francisco!! :)

  7. Trackback | 27 may, 2010

    Reivindicando lo nuestro « La aventura de las matemáticas

  8. Trackback | 16 jun, 2010

    El contraejemplo de Francisco Santos | Gaussianos

  9. Trackback | 23 jun, 2010

    Entrevista a Francisco Santos « La aventura de las matemáticas

  10. Trackback | 8 jul, 2010

    Francisco Santos: Les matemàtiques són una ciència molt barata « Bloc de la Biblioteca de Matemàtiques

  11. Trackback | 25 jul, 2010

    Politopos. « US Patent Appl. 12213303: Comentarios.

  12. Trackback | 4 ago, 2010

    EveryDay Science » Blog Archive » The cons-example that kills … Hirsch conjecture

  13. Trackback | 16 ago, 2010

    El contraejemplo a la conjetura de Hirsch de Francisco Santos (Universidad de Cantabria) « Francis (th)E mule Science's News

  14. Trackback | 20 ago, 2010

    El contraejemplo de Francisco Santos, en español | Gaussianos

  15. Trackback | 9 mar, 2013

    ¿Un premio Nobel de Matemáticas? | Es Ciencia Online

  16. Trackback | 13 oct, 2013

    Terminado Amazings Bilbao 2012...deseando que llegue Naukas Bilbao 2013 - Gaussianos | Gaussianos

  17. profpin | 26 de febrero de 2014 | 04:10

    Vótalo Thumb up 0

    Mis honores al gran Francisco; a por más!

Escribe un comentario

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia. Utiliza la Vista Previa antes de publicar tu comentario para asegurarte de que las fórmulas están correctamente escritas.