2451. Optimizing with Column Generation
Invited abstract in session TE-5: Semi-plenary talk Uchoa, stream PC Stream.
Thursday, 16:30-17:15Room: H7
Authors (first author is the speaker)
| 1. | Eduardo Uchoa
|
| Engenharia de Producao, UFF |
Abstract
Column Generation (CG) is a technique to solve Linear Programs with a very large number of variables. Instead of explicitly evaluating reduced costs, variables are dynamically generated by solving auxiliary optimization problems known as pricing subproblems. CG is one of the major optimization techniques, being also effective in integer programming, in algorithms like Branch-and-Price and Branch-Cut-and-Price. It has been successfully applied to many types of vehicle routing, cutting and packing, airline planning, timetabling, crew scheduling, graph coloring, clustering, lot sizing, and machine scheduling, among other problems. The talk provides an overview of the CG. The central question explored is: under what circumstances are CG-based algorithms likely to outperform other existing methods? The discussion draws on material from the recent book “Optimizing with Column Generation: advanced Branch-Cut-and-Price Algorithms (Part I)” available at https://optimizingwithcolumngeneration.github.io.
Keywords
- Linear Programming
- Integer Programming
Status: accepted
Back to the list of papers