Column Generation (Dantzig-Wolfe)
Also known as: Dantzig-Wolfe decomposition, column generation method
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.
Key highlights
- 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)
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
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.
Strengths & limitations
- 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)
- 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
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
Frequently asked
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.
Sources
- 1.Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8(1), 101-111.
- 2.Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849-859.
You have read it. What now?
Cite this page
ScholarGate. (2026, June 3). Column Generation (Dantzig-Wolfe). ScholarGate. https://scholargate.app/operations-research/column-generation