El algoritmo que recorre el mundo

Sus servicios son llamados miles de veces por segundo para asegurar que los negocios del mundo funcionan sin problemas, pero sus matemáticas

 ¿son realmente tan dignas de confianza como pensamos?

Es posible que no haya oído hablar del algoritmo que dirige el mundo.

Pocas personas lo conocen, a pesar de que puede determinar, y mucho, lo que va sucediendo en nuestro día a día: la comida que tenemos para comer, el horario del trabajo, cuando vendrá el tren que nos transporta.

 En algún lugar, en algún sótano perdido hay un servidor, y justo ahora es probable que esté trabajando en algún aspecto de su vida de mañana,

 de la semana próxima o de aquí a un año.

Tal vez la ignorancia del funcionamiento de este algoritmo sea una bendición. En la puerta de la Academia de Platón, en la antigua Atenas, colgaba una leyenda "Aquí no entra nadie que no sepa geómetría". 

Eso fue fácil de decir en aquel entonces, cuando la geometría se basaba firmemente en las tres dimensiones del espacio que construían nuestros cerebros. Sin embargo, este algoritmo opera en planos totalmente superiores. Cuatro, cinco, miles o incluso millones de dimensiones: estos son los espacios inimaginables de la serie de algoritmos matemáticos diseñados para indagar.

Quizá debamos esforzarnos un poco hasta conseguir ubicarnos mejor en su onda. Debido a que resulta tan poderoso, sin duda, el algoritmo se recorre con un punto de incomodidad. Sus fundamentos matemáticos, aunque no estructuralmente defectuosos, sí empieza a desmoronarse en su avance.

 Con tanta cosa descansando sobre él, puede no ser tan fiable como parecía.

Para entender de qué se trata todo esto, primero tenemos que ahondar en las profundas y sorprendentes formas  en las que las abstracciones de la geometría describen el mundo que nos rodea. 

Las ideas sobre este tipo de conexiones ya vienen tan de lejos como Platón, que escogió las cinco formas geométricas 3D, o poliedros, cuya perfecta regularidad, pensaba, representaban la esencia del cosmos.

 El tetraedro, cubo, octaedro y el icosaedro de 20 caras, encarnaban los "elementos" de fuego, tierra, aire y agua, y el dodecaedro de 12 caras la forma del mismo universo.

Las cosas han cambiado un poco desde entonces.
 Las teorías de la física de hoy invocan geometrías extrañamente deformadas desconocidas por Platón, o proponen la existencia de dimensiones espaciales más allá de la obvia inmediatez de tres. Los matemáticos, también han llegado a dimensiones cada vez mayores, extendiendo las ideas sobre los poliedros a alucinantes "politopos", con cuatro, cinco o cualquier número de dimensiones.

Un ejemplo de ello es una ley de poliedros propuesto en 1957 por el matemático estadounidense, Warren Hirsch, quien afirmaba que el número máximo de aristas que tiene que cruzar entre dos vértices en cualquier poliedro, nunca será mayor que el número de sus caras menos el número de dimensiones del problema, en este caso tres.

 Los dos vértices opuestos en un cubo de seis caras, por ejemplo, están separados exactamente por tres aristas, y ningún par de vértices está separado a cuatro o más.

La conjetura de Hirsch mantiene su validez para todos los poliedros 3D.
 Pero nunca se ha demostrado, de manera general, para las formas de dimensiones superiores. La expectativa de su aplicación ha venido, en gran parte, por analogía con otras reglas geométricas que han demostrado ser igualmente elásticas (ver Anexo I: "Aristas, vértices y caras").

 Cuando se trata de garantizar rutas cortas entre los puntos en una superficie de una forma 4D, 5D ó 1000D, la regla de Hirsch ha sido uno de esos irresolubles problemas de las matemáticas, una mera conjetura.

Pero, ¿es esto relevante? Porque, para los matemáticos de hoy en día, 

las dimensiones no solo hablan del espacio. Cierto, el concepto surgió cuando teníamos tres coordenadas de localización que podían variar de forma independiente: arriba-abajo, izquierda-derecha y adelante-atrás.

 Pasado el tiempo, nos encontramos con una cuarta "dimensión" que funcionaba de manera muy similar, aparte del hecho inexplicable de que debemos pasar a través de él en una sola dirección.

Pero más allá del movimiento, a menudo nos encontramos con situaciones del mundo real donde podemos variar mucho más de cuatro cosas de manera independiente. Supongamos, por ejemplo, que usted está haciéndose un bocadillo para el almuerzo. Su refrigerador contiene 10 ingredientes que puede utilizar en cantidades diversas: queso, salsa picante, atún, tomates, huevos, mantequilla, mostaza, mayonesa, lechuga y hummus. Estos ingredientes no son más que las dimensiones de un problema para hacer un bocadillo.

 Esto puede ser tratado geométricamente: combinar la elección de los ingredientes de cualquier manera particular, y completarlo se representa por un solo punto en un espacio de 10 dimensiones.

Problemas brutales

En este espacio multidimensional, es poco probable que haya una libertad ilimitada de movimiento. Habría sólo dos trozos de queso descomponiéndose en la nevera, por ejemplo, o a lo sumo, unos restos en la parte inferior del frasco de mayonesa. Nuestras preferencias personales pueden suministrar otras limitaciones más sutiles a nuestro problema de hacer el bocadillo: echar un ojo a las calorías, tal vez, o el deseo de no mezclar el atún con el hummus. Cada una de estas restricciones representa un límite a nuestro espacio multidimensional, más allá del cual no podemos movernos.

 Nuestros recursos y preferencias, en realidad van construyendo un politopo multidimensional a través del cual debemos navegar hacia nuestro 

perfecto bocata.

Realmente, los procesos de toma de decisión de nuestro bocadillo son susceptibles de ser un tanto aleatorios, con tan sólo unas pocas variables a tener en cuenta, y el resultado posible de la mera satisfacción gástrica, eso no es un problema. Pero en los negocios, el gobierno y la ciencia, con problemas de optimización similares van creciendo por todas partes, y rápidamente se transforman en bestias con muchos miles e incluso millones de variables y restricciones. Un importador de fruta podría tener un problema 1000-dimensional para hacer frente, supongamos, al envío de plátanos procedentes de cinco centros de distribución que almacenan un número variable de frutas a 200 tiendas con distintas cantidades de demanda. 

¿Cuántos paquetes de fruta deben ser enviados desde qué centros y a qué tiendas para reducir al mínimo los costos totales de transporte?

De igual manera, un gestor de fondos que desee organizar una cartera óptima que equilibre el riesgo y la expectativa dentro de un rango de acciones, la programación del ferrocarril que decide la óptima configuración del personal de plantilla y de los trenes, o de una fábrica, la gerencia de un hospital para averiguar cómo hacer malabares con los finitos recursos de maquinaria o de salas disponibles. Cada uno de estos problemas puede ser representado como una figura geométrica, cuyo número de dimensiones es el número de variables dicho problema, y ​​cuyas fronteras están delimitadas por las limitaciones de lo que hay (ver diagrama). En cada caso, necesitamos encajar nuestra salida a través de este politopo hacia su punto óptimo.

El trabajo del algoritmo

Su nombre completo es algoritmo simplex, y surgió tardíamente en la década de 1940, de la mano del matemático estadounidense, George Dantzig, que se pasó la segunda guerra mundial investigando las formas de aumentar la eficiencia logística de la fuerza aérea de EE.UU. Dantzig fue un pionero en el campo de lo que él llamó la programación lineal, que utiliza las matemáticas de politopos multidimensionales para resolver problemas de optimización. Una de las primeras ideas a las que llegó fue la del valor óptimo de la "función objetivo" (lo que se pretende maximizar o minimizar, sea ganancias, tiempo de viaje o lo que sea), se garantiza que se encuentre en uno de los vértices del politopo. Esto inmediatamente hace que las cosas sean mucho más manejables: hay una infinidad de puntos dentro de cualquier politopo, pero solamente un número finito de curvas.

Si tenemos sólo unas cuantas dimensiones y limitaciones con las que jugar, este hecho es todo lo que necesitamos.

 Podemos ver nuestro camino a lo largo de las aristas del politopo, testeando el valor de la función objetivo en cada vértice hasta encontrar su punto óptimo. Pero las cosas aumentan rápidamente.

 Aunque sólo sea un problema de 10 dimensiones con 50 restricciones —como podría ser el asignar un horario de trabajo a 10 personas con diferentes especialidades y limitaciones de tiempo—, ya nos encontraríamos con varios miles de millones de vértices para ensayar.

El algoritmo simplex busca de manera más rápida. En lugar de vagar al azar a lo largo de las aristas de un politopo, implementa una "regla pivote" en cada vértice. Existen variaciones sutilmente diferentes de esta regla pivote en diferentes implementaciones del algoritmo, pero a menudo consiste en elegir la arista a lo largo del cual la función objetivo desciende más abruptamente, eso garantiza que cada paso nos lleva más cerca del valor óptimo.

 Cuando se descubre un vértice donde ya no es posible descender más, sabemos que hemos llegado al punto óptimo.

La experiencia práctica demuestra que el método simplex es generalmente una solucionador de problemas muy hábil, que suele alcanzar una solución óptima después de un número de pivotes comparable con el número de dimensiones del problema. Esto significa un máximo probable de unos pocos cientos de pasos para resolver un problema de 50 dimensiones, en lugar de los miles de millones con el enfoque de ‘probar y comprobar’.

 Este tiempo de ejecución se dice que es "polinomial" o simplemente "P",

 el punto de referencia para los algoritmos prácticos que tienen que ejecutarse en procesadores limitados en el mundo real.

El algoritmo de Dantzig vio su primera aplicación comercial en 1952, cuando Abraham Charnes y William Cooper estaban en lo que hoy es la Universidad Carnegie Mellon en Pittsburgh, Pennsylvania, formaron equipo con Robert Mellon en la Gulf Oil Company para descubrir la mejor manera de combinar las existencias disponibles de cuatro productos de petróleo diferentes en un combustible de aviación, con un óptimo nivel de octanaje.

Desde entonces, el algoritmo simplex ha ido conquistando el mundo, integrado tanto en la optimización de paquetes comerciales como en productos de software a medida. Siempre que alguien está tratando de resolver un problema de optimización a gran escala, lo más probable es que algún chip de computador esté canturreando su melodía.

 "Es probable que se hagan decenas o cientos de miles de llamadas del método simplex cada minuto", afirma Jacek Gondzio, especialista en optimización de la Universidad de Edimburgo, Reino Unido.

Sin embargo, aunque su popularidad creció en los años de 1950 y 1960, las bases del algoritmo comienza a mostrar signos de tensión. 

Para empezar, su tiempo de ejecución es polinómica solamente de promedio. En 1972, los matemáticos Victor Klee y George Minty reforzaron este aspecto ejecutando el algoritmo en torno a algunos "hipercubos" multidimensionales ingeniosamente deformes. Al igual que un cuadrado tiene cuatro vértices, y un cubo ocho, un hipercubo de n dimensiones tiene 2n vértices. La precaria manera de Klee y Minty de poner juntos sus hipercubos significó que el algoritmo simplex tenía que recorrer a través de todos los vértices antes de aterrizar en el óptimo. Con sólo 41 dimensiones, eso deja al algoritmo con más de un billón de aristas que atravesar.

Una historia similar se mantiene para todas las variantes de la regla pivote del algoritmo, ensayado desde el diseño original de Dantzig: por muy bien que lo haga, en general, siempre es posible inventar algunos difíciles problemas de optimización en los que no da buenos resultados. La buena noticia es que estos casos patológicos tienden a no aparecer en las aplicaciones prácticas, aunque exactamente el por qué esto es así no está todavía claro.

 "Este comportamiento escapa a cualquier explicación matemática rigurosa, pero sin duda agrada a los profesionales"

Pretendientes deslumbrantes

Ese fallo fue suficiente para estimular a los investigadores a encontrar una alternativa al método simplex. El principal pretendiente apareció en los años 1970 y 1980 con el descubrimiento de los “métodos de punto interior", unos algoritmos llamativos, que en lugar de hacernos sentir su camino alrededor de la superficie de un politopo, perfora un camino a través de su núcleo. Venían con el sello de aprobación de una genuina matemática, la garantía que se ejecutan siempre en tiempo polinómico, y habitualmente llevaban un menor número de pasos para alcanzar el punto óptimo que el método simple, rara vez necesitaban más de 100 movimientos, independientemente de cuántas dimensiones tuviese el problema.

El descubrimiento generó mucho entusiasmo, y por un tiempo pareció inminente la desaparición del algoritmo de Dantzig. Sin embargo, sobrevivió e incluso prosperó. El problema con los métodos de punto interior, es que cada paso conlleva mucho más cálculo que un pivote simplex: en vez de comparar una función objetivo a lo largo de un pequeño número de aristas, debe analizar todas las direcciones posibles dentro del interior del politopo, una empresa gigantesca. Para algunos problemas industriales enormes, este inconveniente es la pena, pero de ninguna manera para todos. Gondzio estima que entre el 80 y el 90 por ciento de los problemas actuales de optimización lineal se resuelven aún con alguna variante del algoritmo simplex. Lo mismo ocurre con algunos de los más complejos problemas no-lineales (ver Anexo III: "Bajando derecho a la línea"). "Como devoto investigador del punto interior tengo un gran respeto por el método simplex", apunta Gondzio. "Y estoy haciendo mi mejor esfuerzo tratando de competir".

Me encantaría encontrar algo mejor: alguna variante nueva del algoritmo simplex que conservara todas sus ventajas, pero también que siempre se ejecutara en tiempo polinómico. Para el matemático y medallista estadounidense, Steve Smale, según escribía en 1998, el descubrimiento de un algoritmo "firmemente polinomial" es una de las 18 cuestiones matemáticas pendientes a tratar en el siglo XXI.

Sin embargo, encontrar tal algoritmo puede que ni siquiera sea posible.

Esto es debido a la existencia de que un algoritmo así de mejorado e infalible, que depende de un supuesto geométrico más fundamental, que existe una ruta lo bastante corta por la superficie del politopo entre dos vértices.

 Sí, lo tenemos: la conjetura de Hirsch.

El destino de la conjetura y el algoritmo siempre han estado entrelazados. Hirsch fue él mismo pionero en investigación operativa y un colaborador inicial de Dantzig, y fue en una carta a Dantzig en 1957, donde reflexionando acerca de la eficiencia del algoritmo que Hirsch, formuló por primera vez su conjetura.

Hasta tiempos recientes, poco había pasado para poner en duda la misma. Klee probó su certeza en todos los poliedros 3D en 1966, pero tenía el presentimiento de qie no ocurría lo mismo con los politopos de más dimensiones. En sus últimos años, se creó el hábito de sugerirlo como problema a todos los investigadores con los que se cruzaba. En 2001, uno de ellos, un joven español, Francisco Santos, ahora en la Universidad de Cantabria en Santander, asumió el reto.

Como suele pasar con este tipo de rompecabezas, le llevó su tiempo. Después de casi una década trabajando en el problema, Santos estaba listo para anunciar sus hallazgos en una conferencia en Seattle en 2010. El mes pasado, el documento resultante se publicó en la revista Annals of Mathematics (vol 176, p 383). En ella, Santos describe un politopo de 43 dimensiones con 86 caras. Según la conjetura de Hirsch, el camino más largo a través de esta forma tendría (86-43) pasos, es decir, 43 pasos. 

Pero Santos fue capaz de establecer de manera concluyente que contiene un par de vértices de al menos 44 pasos.

Aunque sólo sea como caso especial único, se había demostrado que la conjetura de Hirsch era falsa. "Se resolvió un problema que no sabíamos cómo enfocar desde hacía muchas décadas", señaló Gil Kalai, de la Universidad Hebrea de Jerusalén. "La prueba de entera es profunda, compleja y muy elegante. Es un gran resultado."

Un gran resultado, cierto, y mala noticias para el algoritmo simplex. Desde primera refutación de Santos, además los desafíantes politopos de Hirsch se han encontrado en dimensiones de tan sólo 20. Hay únicamente un límite conocido en la distancia más corta entre dos puntos de la superficie de un politopo, y se encuentra ahora en una expresión matemática obtenida por Kalai y Daniel Kleitman del Instituto de Tecnología de Massachusetts en 1992. Esta delimitación es mucho mayor que la que habría proporcionado la conjetura de Hirsch teniéndola por verdadera. Es demasiado grande, de hecho, para garantizar un tiempo de ejecución razonable para el método simplex, cualquiera que sea la regla pivote que podamos imaginar. Si esto es lo mejor que podemos hacer, es posible que el objetivo de Smale de un algoritmo idealizado quede para siempre fuera del alcance, con sus consecuencias potencialmente graves para el futuro de la optimización.

No todo está perdido, sin embargo. Una variante altamente eficiente del algoritmo simplex todavía es posible, si la denominada conjetura polinomial de Hirsch es cierto. Esto estrecha considerablemente la delimitación de Kalai y Kleitman, garantizando que no hay caminos politopos desproporcionadamente largos, en comparación con su dimensión y el número de caras. Un tema de interés ,antes de que la conjetura Hirsch se desvaneciera, es que la versión polinomial ha llamado intensamente la atención desde el anuncio de Santos, tanto como el profundo acertijo geométrico y un lugar prometedor para olisquear sobre un procedimiento de optimización óptimamente eficiente.                

Hasta el momento, no hay ninguna señal concluyente de que la conjetura polinomial se pueda probar de alguna manera.

 "No estoy seguro en absoluto", comenta Kalai.

 "Lo interesante acerca de este problema es que no sabemos la respuesta."                

Muchas cosas pueden estar superpuestas a esa respuesta. 

A medida que el algoritmo continúa canturreando por los sótanos, en su mayor parte nos dice lo que queremos saber en el momento que lo queremos saber. Sin embargo, su propio destino está ahora, más que nunca, en manos de los matemáticos.

Anexo I - Aristas, vértices y caras

Desde que Platón asentó su estilo, se ha trabajado mucho en la comprensión de las propiedades de las formas 3D, o poliedros. Quizás, el resultado más célebre fue del matemático del siglo XVIII, Leonhard Euler. Él observó que cada poliedro tiene dos aristas menos que el total de sus caras y vértices. El cubo, por ejemplo, tiene seis caras y ocho vértices, un total de 14, mientras que sus aristas suman 12. El icosaedro truncado, por su parte, tiene el patrón conocido de un balón de fútbol normal. Tiene 32 caras (12 pentagonales y 20 hexagonales), 60 vértices y 90 aristas.

El matemático francés, Adrien-Marie Legendre, demostró esta regla en 1794 para todas las formas 3D que no contiene agujeros y no se cortan a través de sí mismos de modo extraño. Como la geometría comenzó a hacerse cada ve más sofisticada y fue extendiéndose hacia dimensiones más altas en el siglo XIX, se hizo evidente que la relación de Euler no se detuvo ahí: una simple extensión de esta regla se aplica a las formas, o politopos, para cualquier número de dimensiones. Para una "hipercubo" 4D, por ejemplo, una variante de la fórmula garantiza que el número total de vértices (16) y de caras (24), será igual al número de aristas (32) añadido al número de "caras" 3D que posea la forma (8).

La regla, derivada por Warren Hirsch, en 1957, sobre la distancia máxima entre dos vértices de un poliedro, se pensaba que era similar a la del hierro fundido. Si esto es verdad resulta tener una relevancia sorprendente para el funcionamiento del mundo moderno.

Anexo II - 2000 años de algoritmos

El algoritmo simplex de George Dantzig tiene la pretensión de ser el más importante del mundo; sin embargo, los algoritmos se remontan mucho más lejos en el tiempo.

300 a.n.e. El algoritmo euclidiano .

Desde los primeros elementos matemáticos de Euclides, éste es el abuelo de todos los algoritmos, que mostraba cómo, dados dos números, se puede encontrar el número más grande que  divide a ambos. Aún no ha sido superado.

820 El algoritmo cuadrático .

La palabra algoritmo se deriva del nombre del matemático persa Al-Khwarizmi. Los profesionales experimentados de hoy utilizan su algoritmo para resolver ecuaciones de segundo grado (aquellas que contienen un término x2) en sus cabezas. Para los demás, el álgebra moderna ofrece una conocida fórmula desde la escuela.

1936 La máquina universal de Turing .

El matemático británico Alan Turing, equiparó los algoritmos con procesos mecánicos, y descubrió uno que mimetiza a todos los demás, la plantilla teorética de la computadora programable.

1946 El método de Monte Carlo .

Cuando el problema es demasiado difícil de resolver directamente, entramos en el casino del azar. John von Neumann, Stanislaw Ulam y el algoritmo de Monte Carlo de Nicholas Metropolis nos enseñó a jugar y a ganar.

1957 El compilador Fortran .

La programación era una tarea incómoda y laboriosa hasta que un equipo de IBM, liderado por John Backus, inventó el primer lenguaje de programación de alto nivel, Fortran. En el centro está el compilador: el algoritmo que convierte las instrucciones del programador en código máquina.

1962 Quicksort (ordenamiento rápido) .

La extracción de una palabra del lugar correcto en el diccionario es una tarea fácil, mas si pones todas las palabras en el orden correcto en primer lugar no lo es tanto. El matemático británico Tony Hoare proporcionó la receta, ahora existe una herramienta esencial para la gestión de bases de datos de todo tipo.

1965 La transformada rápida de Fourier .

La tecnología digital depende mucho de la ruptura de señales irregulares en sus puros componentes sinusoidales, un algoritmo creado por James Cooley y John Tukey, el más utilizado del mundo.

1994 El algoritmo de Shor .

Peter Shor, en los laboratorios de Bell, descubrió un nuevo y rápido algoritmo para dividir un número entero en sus números primos constituyentes, pero sólo podía ser realizado por un ordenador cuántico. Si alguna vez se implementara a gran escala, se anularía casi toda la moderna seguridad de Internet.

1998 Pagerank .

El vasto repositorio de información de Internet sería de poca utilidad sin una manera de buscar dicha información. Sergey Brin y Larry Page, de la Universidad de Stanford encontraron la manera de asignar un rango a cada página web, y los fundadores de Google han estado viviendo de él desde entonces.

Anexo III - Bajando directo a la línea

Cuando un joven y nervioso George Dantzig habló sobre su nuevo  algoritmo simplex en una conferencia de eminentes economistas y estadístas en Wisconsin, en 1948, una mano se levantó en objeción en la parte posterior de la sala. Era la del afamado matemático Harold Hotelling, que dijo: 

"Pero todos sabemos que el mundo no es lineal".

Aquello fue una devastadora forma de menosprecio. El éxito del algoritmo simplex para la solución de problemas de optimización depende de asumir que las variables varían en respuesta a otras variables a lo largo de las líneas rectas. Por ejemplo, una empresa de cubertería que está aumentando sus gastos en metal, producirá proporcionalmente más cuchillos y tenedores, y el beneficio será para el próximo mes.

De hecho, como Hotelling señaló, es el mundo real colmado de no linealidad. Conforme la empresa de cubertería se expande, en la economía a escala puede significar que el coste marginal de cada cuchillo o tenedor, pueda impulsar los beneficios no lineales. En términos geométricos, tales problemas están representados por formas multidimensionales, como problemas lineales que son, pero están delimitados por las caras curvadas que el algoritmo simplex tendría dificultades rastreándolas.

Sorprendentemente, las aproximaciones lineales a los procesos no lineales consiguen ser lo suficientemente buenas para los propósitos más prácticos. 

"Yo diría que el 90 ó 95 por ciento de todos los problemas de optimización resueltos en el mundo, son programas lineales", afirma Jacek Gondzio, de la Universidad de Edimburgo, Reino Unido.

 Para aquellos pocos problemas restantes que no sometidos a las artimañas lineales, hay un campo relacionado de programación no-lineal, 

y aquí también, las versiones adaptadas del algoritmo simplex han logrado desempeñar un papel importante.

Referencia: NewScientist.com ,

Autor: Richard Elwes, 13 de agosto 2012