Column generation or delayed column generation is an efficient algorithm for solving large linear programs. The overarching idea is that many linear programs are too large to consider all the variables explicitly. The idea is thus to start by solving the considered program with only a subset of its variables. Then iteratively, variables that have the potential to improve the objective function are added to the program. Once it is possible to demonstrate that adding new variables would no longer improve the value of the objective function, the procedure stops. The hope when applying a column generation algorithm is that only a very small fraction of the variables will be generated. This hope is supported by the fact that in the optimal solution, most variables will be non-basic and assume a value of zero, so the optimal solution can be found without them. In many cases, this method allows to solve large linear programs that would otherwise be intractable. The classical example of a problem where it is successfully used is the cutting stock problem. One particular technique in linear programming which uses this kind of approach is the Dantzig–Wolfe decomposition algorithm. Additionally, column generation has been applied to many problems such as crew scheduling, vehicle routing, and the capacitated p-median problem. Algorithm The algorithm considers two problems: the master problem and the subproblem. The master problem is the original problem with only a subset of variables being considered. The subproblem is a new problem created to identify an improving variable (i.e. which can improve the objective function of the master problem). The algorithm then proceeds as follow: Initialise the master problem and the subproblem Solve the master problem Search for an improving variable with the subproblem If an improving variable is found: add it to the master problem then go to step 2 Else: The solution of the master problem is optimal. Stop. Finding an improving variable The most difficult part of this procedure is how to find a variable that can improve the objective function of the master problem. This can be done by finding the variable with the most negative reduced cost (assuming without loss of generality that the problem is a minimization problem). If no variable has a negative reduced cost, then the current solution of the master problem is optimal. When the number of variables is very large, it is not possible to find an