
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».
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Información Bitacoras.com…
Valora en Bitacoras.com: 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 propi……
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? 😉
Mi enhorabuena a Fernando! Fue mi profesor de Topología en la Universidad de Cantabria.
…quiero decir Francisco…
[…] This post was mentioned on Twitter by gaussianos, Morfismo. Morfismo said: Francisco Santos encuentra un contraejemplo que refuta la conjetura de Hirsch http://bit.ly/bBs5Ir (via @gaussianos) – Em Espanhol […]
Enhorabuena Francisco!! 🙂
[…] que nos informara gaussianos con su entrada sobre Francisco Santos y la conjetura de Hirsch, la noticia ha sido y está siendo recogida por diferentes medios de comunicación. Es […]
[…] Artículos relacionadosFrancisco Santos encuentra un contraejemplo que refuta la conjetura de Hirsch […]
[…] Francisco Santos encuentra un contraejemplo que refuta la conjetura de Hirsch, gaussianos.com […]
[…] i Topologia de la Universitat de Cantàbria, del qual s’ha parlat molt últimament en haver refutat la Conjectura de […]
[…] al teorema de Loera, Onn (2004). Atención!: La conjetura de Hirsch ha sido recientemente resuelta: https://gaussianos.com/francisco-santos-encuentra-un-contraejemplo-que-refuta-la-conjetura-de-hirsch/. Desconocía completamente la conjetura de Barnette: […]
[…] https://gaussianos.com/francisco-santos-encuentra-un-contraejemplo-que-refut… Category: Computer Technology, Material ScienceTags: article combinatorial geometry, mathematician Francisco Santos […]
[…] con el propio Francisco quien nos explicó de primera mano la noticia en ^DiAmOnD^, “Francisco Santos encuentra un contraejemplo que refuta la conjetura de Hirsch,” Gaussianos, 24 de Mayo de 2010. El texto era un extracto de un artículo que aparecería en […]
[…] que Francisco Santos, Catedrático de la Universidad de Cantabria, encontró un contraejemplo que refutaba la conjetura de Hirsch, conjetura ésta relacionada con programación lineal y que el propio Francisco me envió […]
[…] Cantabria, por su excelente trayectoria investigadora cuyo punto álgido se enmarca en su conocido contraejemplo a la conjetura de Hirsh. Además, este matemático acaba de recibir el Premio Humboldt por su labor docente e […]
[…] contento por haber podido conocer a Paco Santos, que hace un tiempo colaboró con Gaussianos con este artículo sobre su contraejemplo de la conjetura de Hirsch (a la izquierda, junto a Clara Grima y a mí, en la siguiente […]
Mis honores al gran Francisco; a por más!
[…] historia ha salido principalmente de la web de Paco Santos (sí, el del contraejemplo de la conjetura de Hirsch), uno de nuestros cracks matemáticos a nivel […]
Querría aportar el vídeo de una interesante clase de Karger Skoltek sobre el método del símplex donde se explica (en inglés) el asunto del diámetro de un politopo y la conjetura de Hirsch (hacia el minuto 50) : https://www.youtube.com/watch?v=x8rYyQjEMMs