Method
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.
| 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 |
|