# Column generation

### From Glossary

This pertains to solving a
linear program whose
columns are *generated* during pricing. Typically, the number
of columns is astronomically large, possibly infinite. An example
is when solving the randomized program,
as with the Generalized Lagrange Multiplier method. In that case, column generation
consists of maximizing the Lagrangian. A similar view applies to
Dantzig-Wolfe decomposition. From the dual view, this is a cutting plane method since generating a column
in the primal corresponds to generating a constraint in the
dual.

The concept applies to any mathematical program, and the randomized program model hightlights the duality and how a completely general mathematical program can be considered with (generalized) linear programming.