Column generation

Column generation
Name	Column generation
Type	optimization algorithm
Field	Operations research
Introduced	1960s
Inventor	George Dantzig
Related	Linear programming, Integer programming, Cutting-stock problem

Column generation is an optimization technique for solving large-scale Linear programming problems by iteratively adding promising variables (columns) rather than handling the full set simultaneously. It decomposes a large model into a restricted master problem and subproblem(s), leveraging dual information to generate columns that improve the objective. The method has been central to advances in Combinatorial optimization, influenced software such as CPLEX and Gurobi, and appears in solutions to classical problems like the Cutting-stock problem and the Vehicle routing problem.

Introduction

Column generation emerged from work on the Cutting-stock problem and early developments in Linear programming theory by researchers including George Dantzig and others active in postwar operations research. It addresses instances where the number of potential decision variables is astronomically large, similar to situations encountered in formulations related to the Travelling Salesman Problem and large-scale Set partitioning problem models used in airline crew scheduling by carriers like British Airways and United Airlines. Practitioners typically embed column generation inside broader heuristics or exact methods such as Branch and bound and Branch-and-price to handle integrality constraints.

Theory and Mathematical Formulation

The mathematical foundation rests on duality theory from Linear programming and decomposition techniques akin to Dantzig–Wolfe decomposition. A linear program with matrix A, cost c and right-hand side b is restructured so columns correspond to extreme patterns or routes drawn from a possibly exponential set, as seen in formulations of the Cutting-stock problem and the Bin packing problem. The restricted master problem (RMP) contains a manageable subset of columns; solving its dual yields reduced costs used in a subproblem (pricing problem) that is often a combinatorial optimization instance such as a shortest path problem with resource constraints seen in Vehicle routing problem networks or a knapsack problem variant related to Cutting-stock problem patterns. Optimality follows when the pricing problem cannot find a column with negative reduced cost (for minimization), an argument grounded in the Strong duality theorem of Linear programming.

Algorithmic Framework

A typical algorithm alternates between solving the RMP and solving the pricing subproblem. Initialization may use artificial columns or heuristic columns inspired by solutions to related problems encountered in Crew scheduling for carriers like Air France or Delta Air Lines. The pricing step can be modeled as a shortest path instance solvable by algorithms such as Dijkstra's algorithm or as a knapsack instance solvable by dynamic programming approaches developed from work by Richard Bellman. When integrality is required, column generation is embedded within Branch-and-price frameworks that combine branching rules from Branch and bound with column generation at each node; successful industrial applications include timetabling models used by Deutsche Bahn and rostering systems used by Iberia (airline).

Applications

Column generation has been applied in a wide array of domains: airline crew scheduling pioneered by practitioners collaborating with research teams at institutions like MIT and Georgia Institute of Technology; vehicle routing and distribution problems studied at ETH Zurich and INSEAD; cutting and packing problems relevant to manufacturers such as IKEA and logistics providers like DHL; timetabling for rail operators including Network Rail and SNCF; and telecommunication network design problems examined at Bell Labs and AT&T Labs. Further applications span freight consolidation in firms like Maersk and crew rostering for Royal Dutch Airlines (KLM), with methodological cross-pollination from computational studies in venues such as the INFORMS Journal on Computing and conferences like the International Conference on Integer Programming and Combinatorial Optimization.

Computational Considerations and Implementation

Practical implementation requires careful handling of numerical stability, stabilization techniques, and warm-starting strategies used in commercial solvers like CPLEX and Gurobi. Stabilization schemes such as penalty terms or trust-region methods draw on numerical optimization research from groups at IBM Research and Microsoft Research. Efficient pricing involves specialized algorithms depending on problem structure: label-setting and label-correcting algorithms used in shortest path pricing trace lineage to work on network optimization at Bell Labs and algorithmic contributions from researchers affiliated with EPFL. Parallelization and decomposition strategies leverage high-performance computing centers, exemplified by projects at Argonne National Laboratory and Lawrence Berkeley National Laboratory, to tackle industrial-scale instances.

Variants and Extensions

Extensions include stabilized column generation, aggregated column generation, and multi-cut strategies inspired by ideas from Gomory cuts and Cutting plane method research. Integration with Lagrangian relaxation and Benders decomposition yields hybrid approaches used in stochastic settings studied at Stanford University and Columbia University. Branch-and-price-and-cut combines branching, pricing, and cutting-plane techniques; notable successful implementations were reported in collaborations between academics at Université catholique de Louvain and practitioners at major carriers. Recent trends incorporate machine learning heuristics to guide pricing or initialization, influenced by work from teams at Google DeepMind and Facebook AI Research.

Category:Optimization algorithms