Breve resumen de la materia

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.

Abstract

Many real-world optimization problems can be modeled using integer linear programming and solved with optimization packages available in several programming languages. However, for certain problems, especially in transportation logistics, the most efficient models have an exponential number of variables and cannot be solved efficiently with traditional packages. In these cases, column generation techniques are employed to handle the variables implicitly. This course offers an introduction to this technique and to VRPSolver, a modern solver that allows users to build and solve models with a large number of variables in just a few lines of code using the Julia programming language.

Objetivos del curso

• Introducir la técnica de generación de columnas
• Demostrar ejemplos de modelos que pueden resolverse de manera eficiente mediante esta técnica
• Presentar un paquete de optimización moderno que proporciona acceso transparente a la técnica para los usuarios.

Objectives of the Course

• To introduce the column generation technique
• To demonstrate examples of models that can be efficiently solved by the technique
• To present a modern optimization package that provides transparent access to the technique for users.

Programa

• 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.

Brief Index

• Mathematical modeling with integer linear programming and the branch-and-bound method.
• Revised simplex method and linear programming duality.
• Column generation and Dantzig-Wolfe decomposition for linear programming.
• Introduction to VRPSolver and VRPSolver examples

Prerrequisitos

Programación Lineal, Método Simplex, Modelado con Programación Lineal Entera

Preferred Background

Linear Programming, Simplex, Modeling with Integer Linear Programming

Bibliografía

• 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.