I'm currently in the process of learning about column generation, so I apologize in advance if I show a gross lack of understanding about it.
Anyways, what I've gathered so far is that Column Generation approaches typically run faster than standard MIP formulation algorithms because you are not calculating the reduced cost of all non-basic variables every iteration of the simplex; rather, you are solving a minimization problem on a polytope to find the non-basic variable with the smallest reduced cost.
The part that is confusing me is that it seems like CG is also advertised to have a "simpler" feasible region in the reformulation which would aid in runtimes. However, aren't we simply doing all the hard work of enumerating the new variables in the beginning? For instance, when reformulating the cutting stock problem, you must enumerate all possible cutting patterns which would itself take time. Are we sure that this doesn't take more time than solving over the original formulation which also guarantees only valid patterns would be cut? In other words, are we sure that the time saved from not calculating every reduced cost, every iteration of the simplex, and solving on a "simpler" feasible region for the reformulation actually saves more time than the time spent enumerating the new variables?
I think I may be missing something here, but every example of CG I've seen so far glosses over how they create the new variables and just how much time that would take.