Column Generation

Column generation is mathematically grounded in Dantzig-Wolfe decomposition, a reformulation technique for problems with block-angular structure. The original problem is reformulated by expressing the feasible region as a convex combination of its extreme points. This transforms a compact but tightly constrained model into a master program with fewer constraints but an enormous number of columns, each representing a feasible schedule or route. This structural separation is what makes the pricing subproblem tractable and independent.

To solve Mixed-Integer Linear Programs (MILPs) with a massive number of variables, column generation is embedded within a Branch-and-Bound tree. This hybrid is called Branch-and-Price. At each node of the search tree, column generation is executed to solve the linear relaxation to optimality. Branching decisions must be carefully designed to not destroy the structure of the pricing subproblem; standard variable branching is often incompatible, requiring specialized branching rules like Ryan-Foster branching for set partitioning formulations.

The mathematical framework for which column generation is a solution technique. A MILP model consists of a linear objective function and linear constraints, where some variables are restricted to integer values. Column generation is essential when the number of variables is too vast to enumerate explicitly, as in set partitioning formulations of routing problems.

• Solved using Branch and Price when combined with Branch and Bound
• The master problem coordinates the selection of generated columns
• Used to model complex operational constraints like time windows and capacity

The canonical application domain for column generation. The VRP seeks to determine optimal routes for a fleet of vehicles to service geographically dispersed customers. Column generation decomposes the VRP into a set partitioning master problem and a pricing subproblem that generates feasible routes.

• Each column represents a complete vehicle route with associated cost
• The pricing problem is often solved as a Resource-Constrained Shortest Path Problem
• Enables exact solutions for instances with hundreds of customers

The theoretical reformulation technique that enables column generation. It decomposes a structured linear program into a master problem and one or more independent subproblems by exploiting block-angular constraint structures. The master problem coordinates the subproblems through dual variable signals.

• Reformulates the original problem by representing extreme points of subproblem polyhedra
• The convexity constraint ensures a convex combination of generated columns
• Provides tighter linear programming relaxations than the original compact formulation

An exact algorithm that integrates column generation within a Branch and Bound tree to solve large-scale integer programs to proven optimality. At each node of the search tree, column generation solves the linear relaxation, and branching decisions are made on original variables to preserve the pricing problem structure.

• Branching on route variables destroys the pricing problem structure
• Ryan-Foster branching is commonly used for set partitioning problems
• Combines the global search of Branch and Bound with the scalability of column generation

The pivotal metric that drives column generation. The reduced cost of a non-basic variable quantifies the marginal improvement in the objective function if that variable enters the basis. The pricing subproblem seeks columns with negative reduced cost (for minimization), indicating they can improve the current solution.

• Calculated as c_j - π^T A_j, where π is the dual vector
• A zero reduced cost for all non-basic variables signals optimality
• The dual values from the restricted master problem define the pricing objective

The most common pricing subproblem in column generation for vehicle routing. It finds a path from a source to a sink that minimizes cost while respecting resource constraints such as vehicle capacity, time windows, and maximum route duration. Solved using dynamic programming with label-setting algorithms.

• Each label stores the accumulated cost and resource consumption at a node
• Dominance rules prune labels to avoid exponential state explosion
• Elementary paths (no repeated customers) require sophisticated cycle-elimination techniques