Si hay algo crucial que mencionar es que para empresas como FedEx, el problema de optimización de enrutar eficientemente los paquetes de vacaciones es tan complicado, que frecuentemente emplean software especializado para encontrar una solución. Según se pudo conocer, este software llamado “solucionador de programación lineal entera mixta” (MILP), consigue dividir 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.
Hay que destacar que 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. Por suerte, Investigadores del MIT y ETH Zurich utilizaron el aprendizaje automático para acelerar las cosas.
La IA acelera la resolución de problemas en panoramas complicados
Según se informa, 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 poder simplificar este paso y posteriormente usaron el aprendizaje automático para encontrar la solución óptima para un tipo determinado de problema.
Vale la pena señalar que 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.
Según se conoció, esta nueva técnica aceleró los solucionadores MILP entre un 30 y un 70% sin perder precisión. Se podría usar este método para obtener una solución óptima más rápidamente o incluso, para problemas esencialmente 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, así como también operadores de redes eléctricas, distribuidores de vacunas o incluso en cualquier entidad que se enfrente a un problema dificultoso 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”, mencionó 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, así mismo, con Wenbin Ouyang, un estudiante graduado de CEE; así como Max Paulus, estudiante de posgrado en ETH Zurich. Según se ha descubierto, la investigación se presentará en la Conferencia sobre Sistemas de Procesamiento de Información Neural.
Dificil de resolver
Vale la pena recalcar que los problemas MILP tienen un número exponencial de soluciones potenciales. Por ejemplo, digamos que un vendedor ambulante desea 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.
Según Wu, “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”.
Un solucionador MILP utiliza una variedad de técnicas y trucos prácticos que tienen la capacidad de poder lograr soluciones razonables en un período de tiempo manejable.
Un solucionador típico usa 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 denominada corte para apretar estas piezas más pequeñas y poder buscarlas más rápido.
Cutting usa un conjunto de reglas que disminuyen 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 fundado para diferentes tipos de problemas MILP.
Por su parte, Wu y su equipo lograron descubrir 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.
Disminuir el espacio de la solución
Tanto ella como sus colaboradores, idearon un mecanismo de filtrado que disminuye este espacio de búsqueda del separador de más de 130.000 combinaciones potenciales a alrededor de 20 opciones. Es de señalar que este mecanismo de filtrado se basa en el principio de rendimientos marginales decrecientes, que indica que el mayor beneficio provendría de un pequeño conjunto de algoritmos, y añadir algoritmos adicionales no traerá muchas mejoras adicionales.
Posteriormente, usan un modelo de aprendizaje automático para elegir la mejor combinación de algoritmos (entre las 20 opciones restantes).
Es de acotar que este modelo se entrena con un conjunto de datos concreto 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 mucho mejor.
Ahora bien, este enfoque basado en datos aceleró los solucionadores MILP entre un 30 y un 70% 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 así mismo, a un solucionador comercial más potente.
Según se ha podido conocer, en el futuro, Wu y sus colaboradores quieren aplicar este enfoque a problemas MILP todavía más complejos, donde la recopilación de datos etiquetados para entrenar el modelo podría resultar especialmente desafiante. Los investigadores también están interesados en interpretar el modelo aprendido para comprender mejor la eficacia de los diferentes algoritmos separadores.
