Eduardo Uchoa. Universidade Federal Fluminense, Brazil
Optimizing with Column Generation
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/. Additionally, we will mention the historical discovery that CG was first employed in the late 1940s by Kantorovich and Zalgaller in their work on the Cutting Stock Problem—predating similar developments in the West by about a decade.
