- La programación lineal entera (MILP) se ha consolidado como una herramienta clave en múltiples sectores industriales
- Gracias a la mejora en la eficiencia computacional de los solucionadores modernos, ahora es posible encontrar rápidamente soluciones óptimas para problemas que antes eran difíciles de resolver
- Este artículo se enfoca en los avances prácticos recientes en los métodos de resolución de MILP y en las mejoras del rendimiento computacional
- Se presentan como metodologías principales branch-and-cut, descomposición de Dantzig-Wolfe y descomposición de Benders
- También se resumen los desafíos persistentes en el campo de MILP y las oportunidades de investigación futura
Introducción
- La programación lineal entera mixta (MILP) es una herramienta esencial en investigación de operaciones y se ha utilizado con éxito en una amplia variedad de industrias
- Los solucionadores MILP modernos ya pueden encontrar soluciones óptimas para problemas de gran escala en segundos, incluso cuando antes eso era imposible
- Como resultado, el uso de MILP se ha expandido en campos como transporte, cadena de suministro, gestión de ingresos, finanzas, telecomunicaciones y manufactura
- Sin embargo, todavía quedan problemas sin resolver y nuevos retos, por lo que la investigación en MILP sigue siendo muy activa
Resumen de los puntos principales
- Este artículo analiza los avances recientes en los métodos de resolución de MILP y las mejoras prácticas de desempeño, con énfasis en cómo cada técnica ha contribuido realmente a mejorar el rendimiento computacional
- Entre la amplia literatura disponible, se priorizan los estudios basados en experimentos computacionales reales
- La discusión se organiza en torno a tres áreas clave de los métodos de resolución de MILP
- Método branch-and-cut: un enfoque representativo para resolver MILP que combina técnicas de partición de nodos y planos de corte
- Descomposición de Dantzig-Wolfe: un enfoque de descomposición que divide problemas de gran escala en subproblemas más pequeños para procesarlos de manera eficiente
- Descomposición de Benders: un método que reduce la carga computacional en estructuras complejas al separar variables y restricciones y resolverlas de forma iterativa
Cierre: desafíos y perspectivas futuras
- La parte final del artículo examina los retos que aún persisten en MILP y las oportunidades de investigación futura
- La creciente complejidad de los problemas industriales reales, la expansión de los datos y los límites del rendimiento de los solucionadores serán temas centrales de investigación en adelante
- Se espera que el campo de MILP siga creciendo junto con los avances en algoritmos, el desarrollo del hardware y la expansión hacia nuevos dominios de aplicación
1 comentarios
Opiniones en Hacker News
Alguien expresó curiosidad por si alguien podía explicar por qué los solvers comerciales de ILP como Gurobi son muchísimo mejores que los solvers gratuitos/open source; preguntó si se debe a la dificultad intrínseca del ILP, o a que el mejor solver es en realidad un enorme conjunto de heurísticas para subproblemas específicos, y por eso las estrategias generalmente “buenas” todavía no están en el dominio público
Se menciona que los solvers comerciales suelen trabajar muy de cerca con sus clientes para implementar técnicas de aceleración específicas del problema, acumulando know-how durante 10–20 años. En MILP, se enfatiza el uso de buenas heurísticas (elegir puntos de inicio para branch-and-bound, podar eficazmente el árbol) y cuts personalizados (excluir de forma eficiente soluciones parciales). También se comenta que investigadores de OR que eligen directamente sus problemas y escriben cuts y heurísticas a medida a menudo obtienen mejores resultados que los solvers comerciales, pero las empresas de solvers contratan equipos de investigadores con doctorado para implementar eso de forma consistente y seguir mejorando con datos reales de muchos clientes.
Los solvers comerciales pueden invertir enormes cantidades de tiempo y recursos en ajustar el desempeño de resolución porque tienen clientes reales interesados y que colaboran. Además de heurísticas, eso incluye reconocer subproblemas simples o problemas aproximados y retroalimentar esa información al problema completo. Los solvers open source tienen límites porque (1) la barrera de entrada para desarrollar optimizadores de punta es muy alta, tanto en matemáticas como en programación; (2) si alguien tiene ese nivel, normalmente termina en una carrera mucho mejor pagada; y (3) por la estructura del open source, casi no hay clientes que aporten casos para mejorar, datos de desempeño o profiling. Hay excepciones como SNOPT, que es comercial pero con un desarrollo comercial no tradicional, y los solvers académicos suelen enfocarse en áreas de aplicación concretas y por eso son menos generales. En otros campos, grandes empresas como Google a veces adquieren o respaldan proyectos para hacer crecer el ecosistema, pero en el mundo de los solvers la inversión necesaria para construir toda la pila desde cero es demasiado alta.
Los solvers comerciales pueden detectar qué trucos funcionarán según el problema gracias a una gran variedad de trucos y mecanismos de detección de patrones. Si conoces bien la estructura del problema, puedes hacer algo más rápido que un solver comercial, pero con un problema aleatorio casi no hay posibilidades.
Alguien planteó que “solver = conjunto de diversas heurísticas para subproblemas especializados”, y se respondió que en problemas NP-Hard casi todo tiene esa estructura. ILP es equivalente a SAT, así que aplica igual.
Se mencionó el tema de la escala comercial y la velocidad: la mayoría de las firmas de quantitative trading ejecutan problemas de optimización enormes tan seguido como pueden, y los solvers open source muchas veces ni siquiera logran resolverlos o se quedan sin memoria. La brecha es así de grande.
Se recordó la experiencia de haber construido una herramienta de asignación de recursos con la librería MILP ILOG de IBM: si ese mismo problema se hubiera resuelto hace 20 años, hoy tardaría 5 minutos mientras que entonces todavía seguiría corriendo. Las computadoras mejoraron mil veces y los algoritmos también mil veces, para una mejora total de un millón de veces. Es una buena reflexión al intentar predecir el futuro. Por cierto, en ese caso los “recursos” eran diamantes.
Alguien preguntó cómo se usa realmente esto en la práctica: si la optimización numérica no termina muchas veces desplazada por límites generales de los enfoques basados en datos (confiabilidad, problemas de datos, etc.), haciendo que una persona importante tome la decisión final “por intuición”.
Una respuesta comentó que en su empresa usan solvers a lo largo de todo el stack: optimizan la programación de baterías residenciales y EV, generan cronogramas óptimos para portafolios de cientos de miles de hogares, e incluso hacen trading de ese portafolio con solvers. También se mencionó que los precios spot de electricidad en la UE se determinan ejecutando un único solver gigante llamado Euphemia. En prácticamente cualquier área donde haya un objetivo de optimización claro conectado con dinero, los solvers se usan muchísimo.
Se dio un ejemplo real en una empresa de FMCG: (1) planificación de rutas de vendedores y entregas, (2) programación de máquinas, personal y materiales para producción, y (3) determinación de niveles adecuados de inventario en centros de distribución. No está completamente automatizado por la dificultad del pronóstico de demanda.
Se compartieron enlaces de casos de estudio útiles: Casos de estudio de Gurobi, Casos de estudio de CPLEX, Casos de estudio de Hexaly (antes LocalSolver)
Alguien comentó haber escuchado que Gurobi es bastante caro y preguntó si se podía compartir información real de precios.
Los precios concretos no son públicos, pero para practicar MIP no hace falta comprar un solver comercial como XPRESS/Gurobi/CPLEX; se recomendó usar licencias gratuitas para estudiantes o solvers MIP open source gratis para uso no comercial, por ejemplo: HiGHS, SCIP
Según lo que se ha oído, el esquema de precios es del tipo “llama y negocia”, y en la práctica ajustan el monto según cuánto dinero gana el cliente.
Se subrayó que sigue siendo mucho más barato que tomar decisiones lentas y subóptimas. Para problemas pequeños basta con solvers gratuitos como GLPK, pero en problemas grandes de negocio a menudo es casi imposible obtener una respuesta a tiempo. Por eso los solvers premium sí valen lo que cuestan.
Alguien recordó que hace unos 10 años costaba alrededor de 100 mil dólares para una licencia de varios servidores, aunque no recordaba con exactitud los límites de usuarios o de servidores. También se comentó que en la industria se considera plenamente justificable ese valor.
Gurobi también ofrece un servicio cloud con cobro por hora, y las licencias no académicas son muy caras.
Una persona contó que implementó directamente hyperplanes de cutting de Gomory en los años 90, y le sorprende cuánto avanzó el campo desde entonces. Antes podía tomar dos meses resolver un problema LP; ahora basta 1 segundo. Un trabajo de Bixby reporta que entre 1990 y 2020 CPLEX y Gurobi se volvieron casi 4 millones de veces más rápidos, independientemente de la mejora del hardware.
Entre 1988 y 2004, el hardware se volvió 1600 veces más rápido y los solvers LP 3300 veces más rápidos. Ya en ese momento la mejora acumulada superaba los 5 millones de veces. Entre 2001 y 2020, los solvers comerciales de MILP también mejoraron más de 1000 veces (50 por algoritmos y 20 por computadoras). Surgió curiosidad por recopilar este tipo de datos de mejoras de velocidad por campo, descomponiéndolos en el aporte de algoritmos y computadoras. En compiladores existe algo parecido con la “ley de Proebsting”, según la cual cada 18 años los avances de compiladores producen un efecto equivalente a duplicar la potencia de cómputo.
A alguien le pareció llamativo que enfoques basados en ML/AI no se usen tanto en este tipo de problemas. Hay papers que prueban RL/GNN en problemas pequeños, pero al final parece que lo mejor sigue siendo comprar una licencia de Gurobi. También comentó que al trabajar recientemente en optimización de scheduling vio ejemplos con RL, pero el desempeño real fue flojo; para problemas grandes parecen mejores los algoritmos evolutivos. En definitiva, si se puede formular bien el problema, un enfoque basado en OR parece el más eficiente.
Se respondió que depende del tipo de problema. Por ejemplo, decidir el ON/OFF de plantas generadoras (unit commitment) es extremadamente complejo, pero un solver MILP puede encontrar rápidamente una solución globalmente óptima. Los algoritmos genéticos no garantizan salir de mínimos locales y pueden ser lentos, y las redes neuronales siempre serán subóptimas.
También se dijo que SAT es un problema tradicional de GOFAI, y que se puede escribir un solver SAT en cualquier lenguaje de la familia ML; es decir, el enfoque “ML/AI” en realidad sí puede aplicarse bastante.
Hubo un comentario sugiriendo que estaría bien agregar la indicación de pdf en el título.
Se respondió que ese enlace no lleva a un pdf, sino al abstract.
También se compartió una referencia directa al pdf del paper: https://inria.hal.science/hal-04776866v1/document
Se expresó la opinión de que la programación lineal entera no parece tan compleja.
Se explicó que el problema de 3-coloración de vértices de un grafo (G3C) está en NP y es NP-Hard, por lo tanto es NPC, y hay resultados que muestran que si puedes resolver ILP general, también puedes resolver G3C. A su vez, SAT es NP-Complete, y si puedes resolver SAT, puedes resolver G3C; por lo tanto, si puedes resolver G3C, también puedes resolver factorización entera (FAC). FAC no es NPC, pero es extremadamente importante en el entorno computacional actual. Es decir, si pudieras resolver ILP arbitrario, podrías romper algoritmos criptográficos importantes. De ahí se infiere que ILP es un problema muy difícil. Una confusión común es que los problemas NPC suelen tener instancias aleatorias que normalmente son fáciles de resolver, y la proporción de instancias realmente difíciles incluso disminuye a medida que crece el tamaño del problema.
También se comentó que el problema del viajante (Travelling Salesperson Problem, TSP) puede codificarse como ILP, lo que sugiere una dificultad considerable.
Hay que encontrar los enteros que mejor satisfacen las restricciones; parece similar a trabajar con números reales, pero en el fondo es completamente distinto. No existe una solución general, solo heurísticas (muy buenas) para casos especiales.
Es más difícil que la programación lineal.
O también se puede ver como un problema muy realista.