Llegamos a ustedes gracias a:



Noticias

Un nuevo algoritmo del MIT podría resolver los problemas de optimización

[10/01/2013] Un grupo de investigadores del Massachusetts Institute of Technology (MIT) han ideado una forma potencialmente más efectiva de ayudar a las computadoras a resolver algunos de los problemas más complicados de optimización que enfrentan.
Su nuevo algoritmo es más computacionalmente efectivo que otros enfoques, ya que escala de modo casi lineal, de acuerdo a Jonathan Kelner, profesor asociado de matemáticas aplicadas del MIT y miembro del Computer Science and Artificial Intelligence Laboratory del MIT, y que es coautor del nuevo algoritmo.
Los tiempos de ejecución de los algoritmos anteriormente conocidos escalaban no linealmente, escribió Kelner por correo electrónico, dando a entender que cuando un problema es más complejo, el desempeño de la computadora se reduce significativamente.
El escalamiento lineal significa que el tiempo que se requiere para resolver un problema usando una fórmula es más o menos directamente proporcional al tamaño del espacio del problema que se está estudiando.
Aunque la apariencia de un nuevo algoritmo potencialmente poderoso podría no ser tan emocionante como los más recientes gadgets del CES, podría tener repercusiones más profundas en la industria, si reduce significativamente la cantidad de trabajo que se requiere para escribir el código del programa y permite a las computadoras enfrentar eficientemente problemas complejos.
Algún día una aerolínea deseará utilizar este algoritmo de optimización para encontrar la forma más eficiente de programar los turnos de sus tripulaciones, por ejemplo. O un router podría utilizarlo para calcular el trayecto más rápido a través de una red congestionada.
Kelner y su colega Lorenzo Orecchia presentarán el algoritmo en el Symposium on Discrete Algorithms (SIAM) de la Association of Computing Machinery (ACM) que se realiza esta semana en Portland. Varios estudiantes graduados y matemáticos de la Universidad de Yale y de la Universidad del Sur de California también participaron en el trabajo.
El paper también aparecerá en la edición de enero del journal del ACM-SIAM. Obtuvo un premio de la ACM como el mejor paper del ACM-SIAM de este año.
El algoritmo no tiene aún un nombre oficial, aunque se habla de él como el algoritmo KLOS debido a las iniciales de los apellidos de los autores principales (Kelner, Yin Tat Lee, Orecchia y Aaron Sidford, todos del MIT).
En la actualidad los problemas de optimización generalmente se resuelven usando algún algoritmo de flujo máximo, a los que generalmente se llama max-flow.
Max flow modela una red mediante la construcción de un gráfico que representa todos los end points como nodos, o vértices, y todas las conexiones entre ellos como límites (edges). Luego estima la forma más eficiente de rutear el tráfico a través de la red, dada la máxima capacidad de cada nodo. Max flow estima el rendimiento en los límites al saturar un límite a la vez, trasladándose de un límite a otro para obtener más rendimiento.
Con redes muy complejas, este enfoque puede consumir demasiado tiempo y demasiados recursos para funcionar en forma efectiva. Los problemas de hoy generalmente tienen millones o incluso miles de millones de límites, indicó Kelner.
El nuevo algoritmo evalúa todos los caminos, o límites, a la vez. El enfoque se parece más a cuando la electricidad corre a través de un circuito de resistores paralelos, en donde la corriente se diseminará en todas las posibles trayectorias al mismo tiempo. Para reducir aún más el tiempo de procesamiento, el algoritmo puede identificar los cuellos de botella en la red, algo que los algoritmos max flow generalmente no hacen.
Aunque la fórmula puede representar un hito en la resolución de los problemas de optimización, aún queda por realizar mucho trabajo para que se encuentre listo para su uso en producción en las computadoras.
El trabajo que hemos publicado hasta el momento se ha enfocado en la teoría, y va a tomar mucho trabajo producir una buena implementación que sea adecuada, escribió Kelner. Los investigadores probablemente se tomen un poco más tiempo para simplificar el algoritmo antes de intentar implementarlo en una librería de software para que pueda ser utilizado por otros.
Joab Jackson, IDG News Service