Skip to content
Back to search results

Column Generation (Dantzig-Wolfe)

Introduced by
George B. Dantzig and Philip Wolfe
Year
1960
Type
algorithm
Family
Optimization
Font size

What does it do?

Column Generation, developed by George B. Dantzig and Philip Wolfe in 1960, is a powerful optimization technique for solving large-scale linear programming problems with special structure.

Also known as Dantzig-Wolfe Decomposition, it decomposes the problem into a master problem (restricted to a subset of variables/columns) and a pricing subproblem (identifying new variables), iteratively improving the solution by introducing only relevant columns.

The intuition behind the method

The method recognizes that many large optimization problems have special structure: numerous variables but few truly important constraints, or naturally decomposable subproblems. Instead of solving the full problem with all possible variables, column generation maintains only a small subset of promising columns (variables). The pricing problem, solved using reduced costs and problem structure, identifies new columns that improve the master solution. By iteratively adding the most promising columns, the algorithm builds up a solution efficiently, avoiding the computational burden of handling all columns simultaneously.

History

Dantzig and Wolfe introduced the decomposition principle for linear programs in 1960, establishing the theoretical foundation. Gilmore and Gomory (1961) applied it to the cutting stock problem, demonstrating practical power. The method gained prominence for vehicle routing and scheduling problems in the 1980s-90s. Integration with branch-and-bound, creating branch-and-price algorithms, expanded applicability to integer programming. Modern applications include airline crew scheduling, ship routing, and large-scale logistics optimization.

When to use it

Apply column generation when solving large-scale linear programs with special structure, particularly when the number of variables is huge but a small subset dominates the optimal solution. It is ideal for cutting stock problems, vehicle routing, crew scheduling, and bin packing. Use it when problem structure allows efficient pricing problem solution. For problems without exploitable structure or moderate size, standard LP solvers are more practical.

Limitations and considerations

  • Requires problem structure enabling efficient pricing subproblem solution
  • Convergence can be slow, especially near optimality (tailing-off effect)
  • Pricing subproblem solution must be reliable and efficient, or efficiency gains are lost
  • Implementation complexity greater than standard LP methods
  • Numerical stability issues with large dual values and reduced costs

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • Solves large-scale problems intractable by standard methods due to column explosion
  • Exploits problem structure to generate only relevant columns
  • Provides bounds on solution quality during iteration
  • Naturally suited for problems with special substructure (identical subproblems, symmetry)
  • Integrable with branch-and-bound for integer programs (branch-and-price)

Applications

  • Cutting stock problem: minimizing waste when cutting material into required sizes
  • Vehicle routing: optimizing routes for delivery and transportation with time windows and capacity constraints
  • Crew scheduling: assigning crew members to flights or shifts minimizing total cost
  • Bin packing: efficiently packing items into containers to minimize waste and number of containers
  • Rostering: scheduling workers across shifts respecting availability and preference constraints
  • Airline planning: flight scheduling, crew assignments, and aircraft maintenance coordination

How it works

How it works

1

Start with a restricted master problem containing only a subset of columns necessary for an initial feasible solution.

2

Solve the dual of the current restricted master using the simplex tableau. Identify reduced costs and set up the pricing subproblem to find variables with negative reduced cost (for minimization).

3

Solve the pricing subproblem using its special structure. If a new column with negative reduced cost is found, add it to the master problem and repeat. If no improving column exists, the current solution is optimal.

Common pitfalls

  • Selecting an inefficient pricing subproblem algorithm, negating efficiency gains from column generation
  • Failing to recognize problem structure amenable to decomposition, resulting in poor performance
  • Inadequate convergence detection or too-strict tolerance, wasting iterations
  • Not implementing stabilization techniques to address the tailing-off effect

Frequently asked questions

What is the pricing problem in column generation and how does it relate to reduced costs?

The pricing problem identifies new variables (columns) with negative reduced cost that improve the master solution. Reduced cost values come from the dual of the restricted master problem and guide the search in the pricing subproblem.

Why is column generation better than solving the full problem with all columns?

In many problems, the number of potential columns is exponential or infinite, making it impossible to enumerate all. Column generation generates only the necessary columns on demand, drastically reducing computational burden.

What is the tailing-off effect and how can it be mitigated?

Tailing-off occurs when column generation makes slow progress near optimality, generating many columns with minimal improvement. Stabilization techniques (dual smoothing, trust region methods, cutoff strategies) reduce its impact.

How does branch-and-price extend column generation to integer programming?

Branch-and-price combines column generation with branch-and-bound: at each node, column generation solves the LP relaxation, and branching decisions further restrict the problem when LP solutions are fractional.

Related methods

Sources

  1. Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8(1), 101-111.

    Open DOI reference
    Copied.
  2. Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849-859.

    Open DOI reference
    Copied.