Faltan dos días para que se inicie el Congreso Internacional de Matemáticos (ICM 2010) en la India. Un buen momento para recordar el resultado matemático más importante de este año, hasta hoy, protagonizado por un español. Francisco Santos Leal encontró un contraejemplo a la conjetura de Hirsch en programación lineal propuesta en 1957. Hay muchas fuentes en la web para esta noticia. Gaussianos contactó 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 la “La Gaceta de la Real Sociedad Matemática Española.” Francisco tuvo la gran idea de publicar dicho artículo, en español, también en ArXiv, gratis para todos. Francisco Santos, «Sobre un contraejemplo a la conjetura de Hirsch,» ArXiv, 19 Jul 2010 [La Gaceta de la RSME 13: 525-538, 2010]. No sé, di por hecho que en Gaussianos dedicarían una entrada a dicha publicación. Sin embargo, parece que se les ha pasado. Solo se hicieron eco de la publicación del artículo técnico en inglés, Francisco Santos, «A counterexample to the Hirsch conjecture,» ArXiv, 14 Jun 2010, en su entrada ^DiAmOnD^, «El contraejemplo de Francisco Santos,»  Gaussianos, 16 de Junio de 2010. Permitidme unas líneas sobre el contraejemplo. Más información obviamente en el artículo de La Gaceta.

Un problema de programación lineal es un problema de optimización del tipo Maximizar/minimizar

,

 

sujeto a las restricciones

 

El método más famoso y más utilizado para resolver este problema es el método del símplice (también conocido como método del simplex) popularizado/redescubierto por George Dantzig (en realidad el método era ya conocido desde la época de Fourier a principios del s. XIX para resolver sistemas de desigualdades y ha sido redescubierto muchas veces, siendo el ruso L. V. Kantorovitch quien recibió en 1975 el Premio Nobel de Economía por su redescubrimiento alrededor de 1939, cosas de la historia). Este problema de optimización puede parecer una menudencia, casi una trivialidad, pero su resolución gracias al método del símplice es, sin lugar a dudas, el problema matemático que más dinero ha generado en toda la historia. Durante la II Guerra Mundial se utilizó para planificar operaciones militares (por eso se llama investigación de operaciones al campo de estudio de la optimización de funciones y problemas). Hoy en día, no solo todo matemático, sino también todo ingeniero y todo economista estudia investigación operativa.

¿Cuál es la idea del método del símplice? La región de puntos del espacio de n dimensiones que cumple con las restricciones es un politopo (la versión en n dimensiones de un poliedro en 3 dimensiones o de un polígono en 2 dimensiones). La solución del problema es un vértice de este politopo (en 2 dimensiones un vértice del polígono y en 3 dimensiones un vértice del poliedro). El problema no tiene solución si el politopo es el conjunto vacío, puede haber infinitas soluciones, si la solución es una arista o una cara del politopo, y la solución puede ser no acotada, si el politopo no es un conjunto acotado. La idea del método del símplice es determinar un vértice del politopo; si el origen es un vértice (cumple las restricciones), se toma el origen y se habla del método del símplice de una sola fase; si el origen no es un vértice, se habla del método del símplice de las dos fases, donde la primera fase es otro problema del mismo tipo pero con una función objetivo diferente, cuya solución es un vértice del politopo). El método del símplice consiste en ir saltando de vértice a vértice, solo entre vértices adyacentes (unidos por una arista en el politopo), mientras se pueda ir mejorando el valor de la función objetivo. Un símplice es el politopo formado por un vértice y todos n vértices adyacentes, en n dimensiones (en 2 dimesiones un símplice es un triángulo y en 3 dimensiones es un tetraedro). El salto de un vértice a otro adyacente se puede interpretar como el salto de un símplice a otro símplice adyacente. El algoritmo del símplice acaba cuando no podemos saltar a ningún vértice (o símplice) que mejore el valor de la función objetivo. El salto de un vértice a otro se obtiene aplicando el método de Gauss para la resolución de sistemas lineales. Omitiré más detalles matemáticos (bien conocidos por matemáticos, ingenieros, economistas, …).

Como el algoritmo del símplice se basa en saltar de un vértice a otro, el número de pasos del algoritmo depende del número mínimo de pasos que hay dar para conectar dos vértices cualesquiera del politopo. A este número se le llama diámetro (combinatorio) del grafo del politopo. Dados dos vértices cualesquiera es el número mínimo de aristas por las que hay que pasar para conectar ambos vértices considerando el politopo como si fuera un grafo. La Conjetura de Hirsch (1957) afirma que el diámetro (combinatorio) del grafo de un politopo de dimensión n definido por m desigualdades no puede ser nunca mayor que m – n. Parece una tontería, pero es un resultado cuya demostración ha escapado de las manos de los matemáticos durante los últimos 50 años. Francisco Santos ha encontrado un politopo de dimensión 43 con 86 caras y un diámetro mayor que 43. Para construir este contraejemplo de la conjetura ha utilizado una generalización del Teorema de los n pasos de Klee y Walkup. Francisco ha demostrado la existencia de su contraejemplo aplicando 38 veces un resultado matemático llamado Lema del Huso aplicado a un politopo en 5 dimensiones y 48 caras que viola cierta el Teorema de Klee y Walkup. Este politopo aparece explícitamente en su demostración, sin embargo, Francisco aún no ha sido capaz de construir y verificar explícitamente que su politopo de dimensión 43 realmente viola la Conjetura de Hirsch. Su demostración no es constructiva. Los interesados en saber qué es el teorema de los n pasos y el lema del huso pueden recurrir al artículo en La Gaceta de Francisco. Los interesados en los detalles de la demostración tendrán que pelearse con el artículo técnico en inglés en ArXiv (la demostración ocupa unas 20 páginas del artículo, que tiene 27).

¿Para qué sirve todo esto? Para estudiar la complejidad computacional (el número máximo de pasos) del método del símplice. El método del símplice es un método muy utilizado y es bastante eficiente en la práctica pero el análisis de su complejidad presenta muchas dificultades matemáticas. Hay varias variantes del método del símplice en las que se ha demostrado que su complejidad en el peor caso es exponencial (no polinómica). Estas variantes dependen de cómo se elige el nuevo vértice al que saltar a partir del vértice actual (regla de la selección del pivote). Sin embargo, no se sabe si existe alguna regla de elección de pivotes que garantice que dicha variante del método tiene una complejidad en el peor caso polinómica. En la práctica, los experimentos por ordenador con problemas aleatorios, han demostrado que la complejidad (número de pasos) del método está entre 2 (m-n) y 3  (m-n), donde m es el número de restricciones (desigualdades, incluyendo las de positividad de las variables de decisión) y n la dimensión del vector solución (nótese que m>n por el teorema de Rouché-Frobenius para sistemas lineales).

Todo parece indicar que las técnicas del teorema generalizado de los n pasos utilizado por Francisco Santos permitirán abrir nuevas vías de ataque al problema del estudio de la complejidad computacional del método del símplice. Esperemos que así sea. En cualquier caso, enhorabuena Francisco y deseamos volver a tener noticias tuyas en un futuro cercano.