211service.com
La solución simplex
Mientras estaba sentado en la sala de un tribunal, esperando saber si sería elegido como jurado, Daniel Spielman tuvo una revelación: todo el trabajo que él y su colega Shanghua Teng habían construido durante los últimos tres años era un castillo de naipes. Nunca lo olvidaré, dice Spielman, profesor asociado de matemáticas. Mientras estaba sentado esperando, afortunadamente no para ser elegido, tuve esta terrible experiencia de darme cuenta de que todo lo que habíamos estado haciendo estaba mal. Pensé en tirar mi programa de investigación. Y en ese instante, las cartas colapsaron.
La pareja había estado tratando de descubrir una forma de mejorar el método simplex, uno de los algoritmos más utilizados en el mundo. Permite que muchos de los sistemas complejos que damos por sentado, como las redes de telecomunicaciones y la programación de flotas de vehículos de reparto o vuelos de aerolíneas, funcionen de la manera más eficiente y económica posible. Como nuevo profesor asistente, Spielman quería establecerse dentro del mundo de las matemáticas y ganar un puesto en el MIT trabajando en un gran desafío, a saber, hacer que el algoritmo sea más simple, más rápido y mejor. Pero después de ese día en el juzgado, cuando se dio cuenta de que aplicar conceptos de un área no relacionada al algoritmo simplex era un callejón sin salida, supo que tendría que encontrar otro gran avance para lograr sus objetivos.
Unos días después, como una persona cuya casa ha sido destruida por un huracán o un tornado, Spielman comenzó a rescatar lo que quedaba de la ruina de su investigación. Y fue entonces cuando surgió la gran idea: aunque su trabajo no pudo mejorar el método simplex, tal vez podría explícalo . El método se había desarrollado en 1947, pero después de más de 50 años de análisis, nadie había podido averiguar por qué funcionaba. La corazonada de Spielman resultó ser correcta. Después de otros tres años de trabajo colaborativo y cientos de fórmulas matemáticas, él y Teng, profesor de la Universidad de Boston, ahora pueden explicar por qué funciona el método simplex. Esto puede permitir que los llamados expertos en optimización resuelvan problemas organizativos aún más complejos. La explicación, llamada análisis suavizado, ya ha sido citada por la National Science Foundation como un avance importante en la tecnología de la información.
El camino al descubrimiento
Spielman y Teng se conocieron por primera vez en el otoño de 1990, cuando Spielman, entonces estudiante de la Universidad de Yale, visitó la Universidad Carnegie Mellon para dar un discurso. Teng, un candidato a doctorado allí, dice que él y otros en la universidad admiraban a este joven de pelo largo. Ya tenía dos trabajos de calidad de doctorado. Naturalmente, era uno de los posibles estudiantes más preciados que todas las principales universidades querían atraer a sus programas de doctorado. En 1992, Spielman eligió el MIT. Teng llegó ese mismo año como instructor en el Instituto. Su relación alumno-maestro pronto se convirtió en amistad y luego en una colaboración que ha durado 11 años.
En 1996, después de varios años de trabajar juntos en otra área, el dúo comenzó a buscar mejorar el método simplex. El proceso de investigación es muy parecido a tratar de encontrar un tesoro en una isla oscura con una pequeña linterna, dice Teng. Intentamos explorar esas muchas pistas esperanzadoras. Dan siempre lleva diarios de trabajo detallados, que marcan sistemáticamente los mapas de la exploración.
Después de tres años de tal trabajo, Spielman tuvo su realización en la corte. Los dos matemáticos cambiaron su objetivo y atacaron seriamente el nuevo problema de investigación.
Teng, quien para ese entonces era profesor asociado en la Universidad de Illinois en Urbana-Champaign, regresó a Massachusetts en un año sabático y alquiló un apartamento a cinco minutos de Spielman. Después de eso, ambos investigadores convirtieron sus salas de estar en espacios de trabajo. Teng colocó una gran pizarra en la pared de su sala. Spielman guardaba uno detrás de su sofá.
A partir de entonces, su trabajo conjunto se desarrolló a todas horas. Fue una de esas cosas en las que mi esposa se quejó de que vi a Shanghua más de lo que la vi durante algunos años, dice Spielman. Teng trabajaba a tiempo completo en Akamai en Cambridge, pero iba al apartamento de Spielman casi todas las noches después del trabajo y los fines de semana. Nos quedábamos despiertos muchas horas, probablemente hasta las dos, trabajando, señala Spielman. Teng agrega, yo era como un miembro adoptado de la familia de Dan. Incluso su gata, Chloe, se acostumbró tanto a nuestra presencia que se sentaba frente a la pizarra y miraba con atención cada vez que la instalamos. Los investigadores agradecieron a Chloe en los reconocimientos de su artículo de la revista.
Para realizar un seguimiento de su trabajo, Spielman continuó con sus diarios de trabajo, anotando cada pensamiento y ecuación que contenían las pizarras antes de borrarlos. Hoy en día, una docena de estos diarios de 200 páginas del tamaño de un cuaderno se alinean en una estantería de su oficina en el Edificio 2. Él dice que alrededor del 60 por ciento de la información que contienen las revistas es trabajo en análisis suavizado. Mientras tanto, Teng usó una cámara digital para tomar alrededor de 40 fotografías de las pizarras antes de que fueran borradas.
Finalmente respondiendo por qué
El resultado de toda esta investigación fue la respuesta a la simple pregunta ¿Por qué? Spielman y Teng finalmente descubrieron por qué el método simplex ha funcionado tan bien todo este tiempo. Lo hicieron desarrollando una nueva forma de analizar el algoritmo.
Hasta su descubrimiento, la mayoría de los matemáticos midieron los algoritmos utilizando el análisis del peor de los casos, en el que a un algoritmo se le dan los datos más difíciles y luego se juzga qué tan bien puede calcular con ellos. Sería como si alguien le presentara el peor problema de división larga posible que pueda imaginar y luego lo probara para ver si puede resolverlo y cuánto tiempo tomaría. Pero esto simplemente no funcionó con el método simplex.
Entonces Spielman y Teng encontraron un nuevo enfoque. Introdujeron cierta variabilidad en el análisis del peor de los casos. En lugar de usar números exactos como entradas para probar el algoritmo, permitieron la imprecisión. Por ejemplo, si la entrada era 1,31, permitían una entrada aleatoria entre 1,29 y 1,33. Descubrieron que al permitir la imprecisión, el algoritmo simplex siempre resolvía el problema de manera eficiente, y por eso ha tenido tanto éxito.
La idea suena simple, pero las matemáticas que la sustentan son complejas. El primer artículo de Spielman y Teng sobre el tema, ahora bajo revisión por parte de la Association for Computing Machinery Revista de la ACM , contiene 80 páginas de ecuaciones. No sé si tanta gente podría leer el periódico, dice Spielman. De hecho, escribir el artículo incluso confundió a Spielman y Teng en ocasiones. Un par de veces simplemente tiramos lo que estaba escrito y escribimos de nuevo, porque si era complicado para nosotros, lo sería aún más para [otras] personas, dice Spielman.
Spielman y Teng han presentado sus hallazgos en todo el mundo con una respuesta entusiasta. Publicaron un documento de conferencia en 2001 y, desde entonces, ambos han realizado presentaciones invitadas y discursos de apertura en los Estados Unidos y en China, Turquía, Italia, Suiza y Dinamarca.
Este análisis suavizado es un avance importante, dice Michel Goemans, PhD ‘90, profesor de matemáticas aplicadas del MIT. Y David Johnson, jefe del Departamento de Optimización y Algoritmos de AT&T Labs-Research, dice, [Análisis suavizado] proporciona un nivel adicional de confianza para quienes usan el método simplex.
Spielman dice que no ha sacado su pizarra desde el verano pasado, cuando finalmente se terminó el papel del diario, pero sin él, nunca hubiéramos logrado escribir el papel. Ahora, Spielman recomienda que los investigadores jóvenes compren pizarras blancas grandes como un buen primer paso para lograr avances. Sin embargo, Teng atribuye una gran parte de su éxito a la mente dinámica de Spielman y su gran gusto para elegir problemas de investigación. Siempre tiene el coraje de trabajar en el problema abierto más difícil en el campo, dice Teng, y ese podría ser un punto de partida aún mejor para los investigadores y personas curiosas de todo el mundo.