Column generation #

Column generation is an algorithm for solving large linear programs by exploiting the fact that in most interesting problems, almost all variables will be zero in the optimal solution.

The cutting stock problem is the classic example for this, and it was initially used as a technique specifically for solving that problem.

Links and resources #

• These introductory slides introducing column generation by using it to solve the cutting stock problem.
• Some more slides that are slightly terser but also get the point across.
• The original paper by Gilmore and Gomory.
• A decent video introduction to column generation.