Determinar la ruta más económica para una nueva línea de metro en una metrópoli como Nueva York representa un desafío monumental de planificación. Este proceso implica evaluar miles de posibles trayectorias a través de cientos de bloques urbanos, cada uno con costos de construcción inciertos. La sabiduría convencional sugiere que se requieren extensos estudios de campo en diversas ubicaciones para determinar los costos asociados con la excavación bajo ciertos bloques.
Dado que estos estudios son costosos, un planificador urbano querría realizar el menor número posible mientras aún recoge los datos más útiles para tomar una decisión óptima. Con casi infinitas posibilidades, ¿cómo saber por dónde empezar?
Nueva metodología algorítmica del MIT
Un nuevo método algorítmico desarrollado por investigadores del MIT podría ofrecer la solución. Su marco matemático identifica de manera comprobable el conjunto mínimo de datos necesario para garantizar la obtención de la solución óptima a un problema, a menudo requiriendo menos mediciones que los enfoques tradicionales sugieren.
En el caso de la ruta del metro, este método considera la estructura del problema —la red de bloques urbanos, las limitaciones constructivas y los límites presupuestarios— así como la incertidumbre relacionada con los costos. El algoritmo identifica entonces el conjunto mínimo de ubicaciones donde los estudios de campo garantizarían encontrar la ruta menos costosa. Además, establece cómo utilizar estos datos recolectados estratégicamente para tomar decisiones óptimas.
Este enfoque se aplica a una amplia gama de problemas estructurados en la toma de decisiones bajo incertidumbre, como la gestión de cadenas de suministro o la optimización de redes eléctricas.
La importancia de los datos en la economía actual
“Los datos son uno de los aspectos más importantes en la economía de IA. Los modelos se entrenan con cada vez más datos, consumiendo enormes recursos computacionales”, afirma Asu Ozdaglar, profesor en Mathworks y jefe del Departamento de Ingeniería Eléctrica y Ciencias de la Computación (EECS) del MIT. Ozdaglar es también subdecano del MIT Schwarzman College of Computing y principal investigador en el Laboratorio para Sistemas de Información y Decisión (LIDS).
Ozdaglar, coautor principal de un artículo sobre esta investigación, trabaja junto a los coautores principales Omar Bennouna, estudiante graduado en EECS, y su hermano Amine Bennouna, exinvestigador postdoctoral en el MIT y actualmente profesor asistente en Northwestern University; además del coautor senior Saurabh Amin, codirector del Centro de Investigación Operativa y profesor en el Departamento de Ingeniería Civil y Ambiental del MIT.
Un enfoque innovador hacia la suficiencia de datos
Mucho del trabajo reciente en investigación operativa se centra en cómo utilizar mejor los datos para tomar decisiones, pero esto asume que esos datos ya existen. Los investigadores del MIT comenzaron planteando una pregunta diferente: ¿cuáles son los datos mínimos necesarios para resolver un problema óptimamente? Con este conocimiento, sería posible recolectar muchos menos datos para encontrar la mejor solución, ahorrando tiempo, dinero y energía al realizar experimentos y entrenar modelos de IA.
A través del desarrollo inicial, crearon una caracterización geométrica y matemática precisa sobre lo que significa que un conjunto de datos sea suficiente. Cada conjunto posible de costos (tiempos de viaje, gastos constructivos, precios energéticos) hace que una decisión particular sea óptima. Estas “regiones óptimas” dividen el espacio decisional. Un conjunto es suficiente si puede determinar qué región contiene el costo verdadero.
Esta caracterización proporciona las bases del algoritmo práctico que desarrollaron para identificar conjuntos de datos que garantizan encontrar soluciones óptimas.
Estrategias para capturar los datos correctos
A fin de utilizar esta herramienta, se introduce la estructura del objetivo y las restricciones junto con cualquier información conocida sobre el problema. Por ejemplo, en gestión logística, el objetivo podría ser reducir costos operativos a través de una red con numerosas rutas potenciales. La empresa puede tener conocimiento previo sobre algunas rutas especialmente costosas pero carecerá información completa sobre otras.
El algoritmo iterativo funciona preguntando repetidamente: “¿Hay algún escenario que cambiaría la decisión óptima que mis datos actuales no pueden detectar?” Si hay respuesta afirmativa, añade una medición que capture esa diferencia; si no, se considera que el conjunto es suficientemente válido.
Este algoritmo señala las ubicaciones específicas que deben explorarse para asegurar encontrar la solución con menor costo. Posteriormente, tras recolectar esos datos, se pueden alimentar a otro algoritmo desarrollado por los investigadores que encuentra esa solución óptima.
"El algoritmo garantiza que, ante cualquier escenario dentro tu incertidumbre, identificarás la mejor decisión,” comenta Omar Bennouna.
A través de sus evaluaciones, han demostrado que usando este método es posible garantizar una decisión óptima con un conjunto mucho más pequeño que lo habitual.
Pensando en el futuro: nuevas aplicaciones y desafíos
"Desafiamos esta idea errónea acerca de que pequeños conjuntos significan soluciones aproximadas,” resalta Amin Bennouna. “Estos son resultados exactos con pruebas matemáticas.” En el futuro próximo, desean extender su marco a otros tipos de problemas y situaciones más complejas; además quieren investigar cómo las observaciones ruidosas podrían afectar la optimalidad del conjunto.
"Me impresionó la originalidad del trabajo, su claridad y su elegante caracterización geométrica,” afirma Yao Xie, presidente Coca-Cola Foundation Chair y profesor en Georgia Tech, quien no participó directamente en esta investigación.
Si (
No(
