Column Generation

Solve huge LPs by generating variables (columns) on demand.

Also called: Column Generation · 지연 열 생성 · 분기-가격(확장)

A method for solving linear programs with an enormous number of variables by generating them lazily: solve a restricted master, use its duals to price a subproblem (often a knapsack), add improving columns, repeat. Originated with Gilmore & Gomory's treatment of 1D Cutting Stock, and extends to branch-and-price for integer solutions.

Claims & evidence

Every relationship is a claim with an evidence grade; applicable problem-to-problem relationships also carry an equivalence level. See the evidence policy.

A–X describes evidence reliability; E0–E4 describes mathematical similarity between problems. The two axes are independent.

Relationships from this entry 1

shares method with
Column Generation to Branch and Bound
Combining column generation with branch and bound yields branch-and-price, used for exact solutions to integer cutting & packing problems.
EvidenceA · Peer-reviewed / official
Equiv.E2 · shared methodology
Sources
- Source grade: A — Peer-reviewed / officialA Linear Programming Approach to the Cutting-Stock Problem
  Citation details
  Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
- Source grade: A — Peer-reviewed / officialBranch-and-Price: Column Generation for Solving Huge Integer Programs
  Citation details
  Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W.P., Vance, P.H. (1998). Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research 46(3):316-329. Formalizes combining column generation with branch-and-bound (branch-and-price).

Relationships from this entry
Relationship	Claim	Evidence	Equiv.	Sources
shares method with Column Generation to Branch and Bound	Combining column generation with branch and bound yields branch-and-price, used for exact solutions to integer cutting & packing problems.	A · Peer-reviewed / official	E2 · shared methodology	Source grade: A — Peer-reviewed / officialA Linear Programming Approach to the Cutting-Stock Problem Citation details Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach. Source grade: A — Peer-reviewed / officialBranch-and-Price: Column Generation for Solving Huge Integer Programs Citation details Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W.P., Vance, P.H. (1998). Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research 46(3):316-329. Formalizes combining column generation with branch-and-bound (branch-and-price).

Relationships to this entry 3

uses method
1D Cutting Stock to Column Generation
Gilmore & Gomory (1961) introduced the column-generation (delayed pattern generation) LP approach for the cutting-stock problem.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialA Linear Programming Approach to the Cutting-Stock Problem
  Citation details
  Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
uses method
2D Bin Packing to Column Generation
Exact approaches to 2D bin packing have been reported with column generation / branch-and-price.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialUsing Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem
  Citation details
  Pisinger, D., Sigurd, M. (2007). Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem. INFORMS Journal on Computing 19(1):36-51. A Dantzig-Wolfe / branch-and-price-and-cut exact method for 2D bin packing.
uses method
Guillotine Cutting to Column Generation
Gilmore & Gomory extended the column-generation / pattern-generation approach to two-dimensional guillotine cutting stock.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialMultistage Cutting Stock Problems of Two and More Dimensions
  Citation details
  Gilmore, P.C., Gomory, R.E. (1965). Multistage Cutting Stock Problems of Two and More Dimensions. Operations Research 13(1):94-120. Extends column generation and the knapsack-function dynamic program to two-dimensional (guillotine) cutting.

Relationships to this entry
Relationship	Claim	Evidence	Equiv.	Sources
uses method 1D Cutting Stock to Column Generation	Gilmore & Gomory (1961) introduced the column-generation (delayed pattern generation) LP approach for the cutting-stock problem.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialA Linear Programming Approach to the Cutting-Stock Problem Citation details Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
uses method 2D Bin Packing to Column Generation	Exact approaches to 2D bin packing have been reported with column generation / branch-and-price.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialUsing Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem Citation details Pisinger, D., Sigurd, M. (2007). Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem. INFORMS Journal on Computing 19(1):36-51. A Dantzig-Wolfe / branch-and-price-and-cut exact method for 2D bin packing.
uses method Guillotine Cutting to Column Generation	Gilmore & Gomory extended the column-generation / pattern-generation approach to two-dimensional guillotine cutting stock.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialMultistage Cutting Stock Problems of Two and More Dimensions Citation details Gilmore, P.C., Gomory, R.E. (1965). Multistage Cutting Stock Problems of Two and More Dimensions. Operations Research 13(1):94-120. Extends column generation and the knapsack-function dynamic program to two-dimensional (guillotine) cutting.