Column Generation solves LPs with exponentially many variables by iteratively adding only the most beneficial "column" (variable) to the restricted master problem. The pricing subproblem finds the column with the most negative reduced cost — if none exists, the current solution is optimal. This technique underlies the Dantzig-Wolfe decomposition and is essential for cutting stock, crew scheduling, and vehicle routing. Each new pattern (column) represents a valid way to pack items, discovered on-demand rather than enumerated exhaustively.