La Conjetura de Hirsch refutada por un contrajemplo

Cuando llevamos el curso de programación lineal, nos enseñan que el problema se representa con d variables y n restricciones

Esto viéndolo del punto de vista geométrico lo tenemos para, por ejemplo, dos variables (d=2), de un area que estará acotada por lineas rectas que nos dan los lados de un polígono, luego tendremos como variables los ejes que serán dos y las restricciones (ej n=5) darán lugar a cada uno de los lados del polígono, los que finalmente nos dan el area donde se encuentran las soluciones factibles.

El óptimo lo tenemos en un vértice, donde se maximizará o minimizará una función de dos variables (la función objetivo).

Si lo vemos con tres variables nos imaginaremos el espacio, dentro del cual empiezan a actuar planos que lo cortan por uno y otro lado y finalmente nos dejan un poliedro irregular (pero convexo) con vértices, caras o facetas y aristas.

Cuando opera el método simplex, este se traslada de un vértice a otro a través de las aristas, de una esquina a otra esquina hasta llegar a una solución que siempre mejore la anterior y así hasta llegar a la solución óptima.
Recientemente gracias a la noticia que publicaran los diarios, me enteré de algo que había afirmado Warren Hirsch, vinculado al problema anterior, en el cual 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".

Pero para entender bien a que se refiere es necesario repasar un poco de teoría de grafos:

• Distancia entre dos vértices: es el número de arcos que lo conectan en la ruta mas corta posible.
• Excentricidad de un vértice: es la distancia más larga entre ese vértice y otro
• El diámetro de un grafo: es la máxima excentricidad de cualquier vértice del grafo, es decir la distancia más larga de cualquier par de vértices. Para calcularlo se debe calcular la distancia de cada par de vértices y se tomará el valor valor de los calculados.

Volviendo a lo anterior tendríamos que si tengo dos variables (dimension d=2) y con cinco restricciones (desigualdades n=5), la distancia más larga entre cualquier par de vértices nunca excederá a 3 (veamos la imagen inicial para ver si es cierto, veremos que en ningun caso, necesitamos más de 3 arcos para conectar a dos vértices).

Pero igual era solo una conjetura.

Recientemente el matemático Francisco Santos ha encontrado un caso en el cual no se cumple la regla anterior, construyó un polítopo de dimensión 43 (variables) con 86 facetas (restricciones) con forma de huso en el cual el diámetro resulta ser mayor a 43, lo cual honestamente no resulta muy alentador porque en lugar de acortar el número de pasos para llegar al óptimo indicaría que posiblemente en algunos casos necesitamos más de n-d pasos (o aristas) para conectar a los vértices más alejados.

Lo cual normalmente ocurre cuando empezamos con la peor solución (la más alejada del óptimo) y buscamos llegar al óptimo en el menor número de pasos o iteraciones como en el simplex.

Para más información:

Un profesor cántabro resuelve un problema matemático planteado ...
El Diario Montañés - ‎26/05/2010‎
«Forma parte del Método Simplex, un algoritmo que todas las empresas del mundo utilizan en la actualidad para diseñar carreteras, planificar producciones, ...
Un español resuelve la conjetura de Hirsch, enunciada hace más de ... La Vanguardia
Resuelta la conjetura de Hirsch, un problema matemático de 50 años ABC.es
Profesor resuelve uno de los grandes enigmas matemáticos Terra Perú
elmundo.es
los 42 artículos informativos »