Si bien Papá Noel puede tener un trineo mágico y nueve valientes renos para ayudarlo a entregar regalos, para empresas como FedEx, el problema de optimización de enrutar paquetes de vacaciones de manera eficiente es tan complicado que a menudo emplean software especializado para encontrar una solución.
Este software, llamado solucionador de programación lineal entera mixta (MILP), divide un problema de optimización masivo en partes más pequeñas y utiliza algoritmos genéricos para intentar encontrar la mejor solución. Sin embargo, el solucionador podría tardar horas (o incluso días) en llegar a una solución.
El proceso es tan oneroso que una empresa a menudo debe detener el software a la mitad, aceptando una solución que no es la ideal, pero sí la mejor que podría generarse en un período de tiempo determinado.
Investigadores del MIT y ETH Zurich utilizaron el aprendizaje automático para acelerar las cosas.
Identificaron un paso intermedio clave en los solucionadores MILP que tiene tantas soluciones potenciales que lleva una enorme cantidad de tiempo desentrañarlas, lo que ralentiza todo el proceso. Los investigadores emplearon una técnica de filtrado para simplificar este paso y luego utilizaron el aprendizaje automático para encontrar la solución óptima para un tipo específico de problema.
Su enfoque basado en datos permite a una empresa utilizar sus propios datos para adaptar un solucionador MILP de uso general al problema en cuestión.
Esta nueva técnica aceleró los solucionadores MILP entre un 30 y un 70 por ciento, sin perder precisión. Se podría utilizar este método para obtener una solución óptima más rápidamente o, para problemas especialmente complejos, una mejor solución en un período de tiempo manejable.
Este enfoque podría utilizarse dondequiera que se empleen solucionadores MILP, como servicios de transporte compartido, operadores de redes eléctricas, distribuidores de vacunas o cualquier entidad que se enfrente a un problema espinoso de asignación de recursos.
“A veces, en un campo como la optimización, es muy común que la gente piense que las soluciones son puramente aprendizaje automático o puramente clásicas. Creo firmemente que queremos obtener lo mejor de ambos mundos, y esta es una instancia realmente sólida de ese enfoque híbrido”, dice la autora principal Cathy Wu, profesora asistente de desarrollo profesional Gilbert W. Winslow en Ingeniería Civil y Ambiental ( CEE), y miembro del Laboratorio de Sistemas de Información y Decisión (LIDS) y del Instituto de Datos, Sistemas y Sociedad (IDSS).
Wu escribió el artículo con los coautores principales Siriu Li, un estudiante graduado del IDSS, y Wenbin Ouyang, un estudiante graduado de CEE; así como Max Paulus, estudiante de posgrado en ETH Zurich. La investigación se presentará en la Conferencia sobre Sistemas de Procesamiento de Información Neural.
Difícil de resolver
Los problemas MILP tienen un número exponencial de soluciones potenciales. Por ejemplo, digamos que un vendedor ambulante quiere encontrar el camino más corto para visitar varias ciudades y luego regresar a su ciudad de origen. Si hay muchas ciudades que se pueden visitar en cualquier orden, el número de soluciones potenciales podría ser mayor que el número de átomos en el universo.
“Estos problemas se denominan NP-difíciles, lo que significa que es muy poco probable que exista un algoritmo eficiente para resolverlos. Cuando el problema es lo suficientemente grande, sólo podemos esperar lograr un rendimiento subóptimo”, explica Wu.
Un solucionador MILP emplea una variedad de técnicas y trucos prácticos que pueden lograr soluciones razonables en un período de tiempo manejable.
Un solucionador típico utiliza un enfoque de divide y vencerás, dividiendo primero el espacio de soluciones potenciales en partes más pequeñas con una técnica llamada ramificación. Luego, el solucionador emplea una técnica llamada corte para apretar estas piezas más pequeñas y poder buscarlas más rápido.
Cutting utiliza un conjunto de reglas que reducen el espacio de búsqueda sin eliminar ninguna solución factible. Estas reglas se generan mediante unas pocas docenas de algoritmos, conocidos como separadores, que se han creado para diferentes tipos de problemas MILP.
Wu y su equipo descubrieron que el proceso de identificar la combinación ideal de algoritmos separadores a utilizar es, en sí mismo, un problema con un número exponencial de soluciones.
“La gestión de separadores es una parte fundamental de todo solucionador, pero es un aspecto subestimado del espacio de problemas. Una de las contribuciones de este trabajo es identificar el problema de la gestión de separadores como una tarea de aprendizaje automático para empezar”, afirma.
Reducir el espacio de la solución
Ella y sus colaboradores idearon un mecanismo de filtrado que reduce este espacio de búsqueda del separador de más de 130.000 combinaciones potenciales a alrededor de 20 opciones. Este mecanismo de filtrado se basa en el principio de rendimientos marginales decrecientes, que dice que el mayor beneficio provendría de un pequeño conjunto de algoritmos, y agregar algoritmos adicionales no traerá muchas mejoras adicionales.
Luego utilizan un modelo de aprendizaje automático para elegir la mejor combinación de algoritmos entre las 20 opciones restantes.
Este modelo se entrena con un conjunto de datos específico para el problema de optimización del usuario, por lo que aprende a elegir los algoritmos que mejor se adaptan a la tarea particular del usuario. Dado que una empresa como FedEx ha resuelto problemas de enrutamiento muchas veces antes, el uso de datos reales obtenidos de experiencias pasadas debería conducir a mejores soluciones que empezar desde cero cada vez.
El proceso de aprendizaje iterativo del modelo, conocido como bandidos contextuales, una forma de aprendizaje por refuerzo, implica elegir una solución potencial, obtener retroalimentación sobre qué tan buena fue y luego intentar nuevamente encontrar una solución mejor.
Este enfoque basado en datos aceleró los solucionadores MILP entre un 30 y un 70 por ciento sin perder precisión. Además, la aceleración fue similar cuando la aplicaron a un solucionador de código abierto más simple y a un solucionador comercial más potente.
En el futuro, Wu y sus colaboradores quieren aplicar este enfoque a problemas MILP aún más complejos, donde la recopilación de datos etiquetados para entrenar el modelo podría resultar especialmente desafiante. Tal vez puedan entrenar el modelo en un conjunto de datos más pequeño y luego modificarlo para abordar un problema de optimización mucho mayor, afirma. Los investigadores también están interesados en interpretar el modelo aprendido para comprender mejor la eficacia de los diferentes algoritmos separadores.
Esta investigación cuenta con el apoyo, en parte, de Mathworks, la Fundación Nacional de Ciencias (NSF), el MIT Amazon Science Hub y el Comité de Apoyo a la Investigación del MIT.
