Muchos problemas de optimización del mundo real pueden modelarse utilizando programación lineal entera y resolverse con paquetes de optimización disponibles en varios lenguajes de programación. Sin embargo, para ciertos problemas, especialmente en logística de transporte, los modelos más eficientes tienen un número exponencial de variables y no pueden resolverse de manera eficiente con paquetes tradicionales. En estos casos, se emplean técnicas de generación de columnas para manejar las variables de manera implícita. Este curso ofrece una introducción a esta técnica y a VRPSolver, un solver moderno que permite a los usuarios construir y resolver modelos con un gran número de variables en tan solo unas pocas líneas de código utilizando el lenguaje de programación Julia.
Modelado matemático con programación lineal entera y el método de branch and bound.
Método simplex revisado y dualidad de la programación lineal.
Generación de columnas y descomposición de Dantzig-Wolfe para problemas de programación lineal.
Introducción a VRPSolver y ejemplos de VRPSolver.
Programación Lineal, Método Simplex, Modelado con Programación Lineal Entera
Uchoa, E., Pessoa, A., Moreno, L. Optimizing with Column Generation: Advanced Branch-Cut-and-Price Algorithms (Part I). Cadernos do LOGIS-UFF, Universidade Federal Fluminense, Engenharia de Produção, Report No. L-2024-3 (2024). Available at https://optimizingwithcolumngeneration.github.io
Pessoa, A., Sadykov, R., Uchoa, Vanderbeck, F. A generic exact solver for vehicle routing and related problems. Mathematical Programming, 183, 483–523 (2020). https://doi.org/10.1007/s10107-020-01523-z
Hillier, F. S., Lieberman, G. J. Introduction to Operations Research (11th ed.). New York: McGraw-Hill Education, 2021.
Desarrollado por el Departamento de Computación, FCEyN, UBA