Method
Column Generation
Solve huge LPs by generating variables (columns) on demand.
Also called: Column Generation · 지연 열 생성 · 분기-가격(확장)
Last verified: 2026-05-27
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 equivalence level and an evidence grade. See the evidence policy.
| Relationship | Claim | Equiv. | Evidence | Sources |
|---|---|---|---|---|
| shares method withBranch and Bound | Combining column generation with branch and bound yields branch-and-price, used for exact solutions to integer cutting & packing problems. | E2 | A |
|
Neighborhood
Direct graph neighbors. Toggle depth to expand.
Click a node to open it · click an edge for its claim
See also
Not directly linked, but conceptually close — by the connections and descriptions they share.
- Integer Linear ProgrammingMethod3 connections in common
- 2D KnapsackFormal problem3 connections in common
- 0/1 Knapsack ProblemFormal problem2 connections in common
- Wäscher TypologyConcept2 connections in common
- Variable-Sized Bin PackingFormal problem2 connections in common
- Genetic AlgorithmMethod2 connections in common