Delayed column generation

Delayed column generation is an efficient algorithm for solving larger integer linear programs.

The problem is split into two problems, the primary and the secondary problem. The secondary problem is a subproblem depending on the dual values of the constraints of the primary problem.

We want to find the solution with the minimum reduced cost in the secondary problem to generate new columns for the primary problem. This leads to a much smaller primary problem that can be solved with existing methods.

An example for a problem that uses this method efficiently is the cutting stock problem.