Determinar la ruta más económica para una nueva línea de metro bajo una metrópolis como Nueva York es un desafío de planificación colosal, que implica miles de posibles trazados a través de cientos de manzanas, cada uno con costes de construcción inciertos. La opinión generalizada sugiere que se necesitarían extensos estudios de campo en numerosas ubicaciones para determinar los costes asociados a la excavación bajo ciertas manzanas.

Dado que estos estudios son costosos de realizar, un planificador urbano querría realizar la menor cantidad posible, recopilando al mismo tiempo los datos más útiles para tomar una decisión óptima.

Con un sinfín de posibilidades, ¿cómo sabrían por dónde empezar?

Un nuevo método algorítmico desarrollado por investigadores del MIT podría ser de gran ayuda. Su marco matemático identifica de forma demostrable el conjunto de datos más pequeño que garantiza encontrar la solución óptima a un problema, requiriendo a menudo menos mediciones que las que sugieren los enfoques tradicionales.

En el caso del trazado del metro, este método considera la estructura del problema (la red de manzanas, las restricciones de construcción y los límites presupuestarios) y la incertidumbre en torno a los costes. El algoritmo identifica entonces el conjunto mínimo de ubicaciones donde los estudios de campo garantizarían encontrar la ruta más económica. El método también identifica cómo utilizar estos datos recopilados estratégicamente para hallar la decisión óptima.

Este marco se aplica a una amplia gama de problemas de toma de decisiones estructuradas en condiciones de incertidumbre, como la gestión de la cadena de suministro o la optimización de la red eléctrica.

“Los datos son uno de los aspectos más importantes de la economía de la IA. Los modelos se entrenan con cada vez más datos, lo que consume enormes recursos computacionales. Sin embargo, la mayoría de los problemas del mundo real tienen una estructura que se puede aprovechar. Hemos demostrado que, con una selección cuidadosa, se pueden garantizar soluciones óptimas con un conjunto de datos pequeño, y proporcionamos un método para identificar con precisión qué datos se necesitan”, afirma Asu Ozdaglar, profesora de Mathworks y directora del Departamento de Ingeniería Eléctrica e Informática (EECS) del MIT, vicedecana del MIT Schwarzman College of Computing e investigadora principal del Laboratorio de Sistemas de Información y Decisión (LIDS).

Ozdaglar, coautor principal de un artículo sobre esta investigación, colabora con los coautores principales Omar Bennouna, estudiante de posgrado en Ingeniería Eléctrica e Informática, y su hermano Amine Bennouna, exinvestigador postdoctoral del MIT y actual profesor asistente en la Universidad Northwestern; y con el coautor principal Saurabh Amin, codirector del Centro de Investigación Operativa, profesor del Departamento de Ingeniería Civil y Ambiental del MIT e investigador principal en LIDS. La investigación se presentará en la Conferencia sobre Sistemas de Procesamiento de Información Neuronal.

Una garantía de optimalidad

Gran parte del trabajo reciente en investigación operativa se centra en cómo utilizar mejor los datos para tomar decisiones, pero esto presupone 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 de forma óptima? Con este conocimiento, se podría recopilar mucha menos información para encontrar la mejor solución, ahorrando tiempo, dinero y energía en la realización de experimentos y el entrenamiento de modelos de IA.

Los investigadores desarrollaron en primer lugar una caracterización geométrica y matemática precisa de lo que significa que un conjunto de datos sea suficiente. Cada posible conjunto de costes (tiempos de viaje, gastos de construcción, precios de la energía) hace que alguna decisión en particular sea óptima. Estas «regiones de optimalidad» dividen el espacio de decisiones. Un conjunto de datos es suficiente si permite determinar qué región contiene el coste real.

Esta caracterización constituye la base del algoritmo práctico que desarrollaron, el cual identifica conjuntos de datos que garantizan encontrar la solución óptima.

Su exploración teórica reveló que, a menudo, un conjunto de datos pequeño y cuidadosamente seleccionado es todo lo que se necesita.

“Cuando decimos que un conjunto de datos es suficiente, nos referimos a que contiene exactamente la información necesaria para resolver el problema. No es necesario estimar todos los parámetros con precisión; solo se necesitan datos que permitan discriminar entre soluciones óptimas que compiten entre sí”, afirma Amine Bennouna.

Partiendo de estos fundamentos matemáticos, los investigadores desarrollaron un algoritmo que encuentra el conjunto de datos suficiente más pequeño.

Capturar los datos correctos

Para utilizar esta herramienta, se introduce la estructura de la tarea, como el objetivo y las restricciones, junto con la información que se tiene sobre el problema.

Por ejemplo, en la gestión de la cadena de suministro, la tarea podría consistir en reducir los costes operativos en una red de decenas de rutas potenciales. La empresa puede saber ya que algunas rutas de envío son especialmente costosas, pero carecer de información completa sobre otras.

El algoritmo iterativo de los investigadores funciona preguntando repetidamente: "¿Existe algún escenario que altere la decisión óptima de una forma que mis datos actuales no puedan detectar?". Si la respuesta es afirmativa, añade una medición que capture esa diferencia. Si la respuesta es negativa, se puede demostrar que el conjunto de datos es suficiente.

Este algoritmo identifica el subconjunto de ubicaciones que deben explorarse para garantizar encontrar la solución de coste mínimo.

Luego, tras recopilar esos datos, el usuario puede introducirlos en otro algoritmo desarrollado por los investigadores que encuentra la solución óptima. En este caso, se trataría de las rutas de envío que deben incluirse en una cadena de suministro con un coste óptimo.

“El algoritmo garantiza que, para cualquier escenario que pueda ocurrir dentro de su incertidumbre, usted identificará la mejor decisión”, dice Omar Bennouna.

Las evaluaciones de los investigadores revelaron que, utilizando este método, es posible garantizar una decisión óptima con un conjunto de datos mucho más pequeño que el que se suele recopilar.

“Desafiamos la idea errónea de que pocos datos implican soluciones aproximadas. Se trata de resultados de suficiencia exactos con demostraciones matemáticas. Hemos identificado cuándo se garantiza la obtención de la solución óptima con muy pocos datos; no probablemente, sino con certeza”, afirma Amin.

En el futuro, los investigadores quieren extender su marco teórico a otros tipos de problemas y situaciones más complejas. También quieren estudiar cómo las observaciones con ruido podrían afectar la optimalidad del conjunto de datos.

“Me impresionó la originalidad, la claridad y la elegante caracterización geométrica del trabajo. Su marco ofrece una perspectiva de optimización novedosa sobre la eficiencia de los datos en la toma de decisiones”, dice Yao Xie, titular de la Cátedra de la Fundación Coca-Cola y profesor en Georgia Tech, quien no participó en este trabajo.

​Autor​