Column generation algorithms

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search

Author: Lorena Garcia Fernandez (lgf572)




Theory, methodology and algorithmic discussions







Column generation schematics[4]

Consider the problem in the form:



Note that, by assuming that each of the sets is bounded for the approach essentially involves solving an equivalent problem of the form:






Where there is a column for each . On the next steps of this method, we will use as the dual variables associated with the joint constraints, and as dual variables for the second set of constraints, known as convexity constraints. The idea is to solve the linear program by the primal simplex algorithm. However, the pricing step of choosing a column to enter the basis must be modified because of the enormous number of columns. Rather than pricing the columns one by one, the problem of finding a column with the largest reduced price is itself a set of K optimization problems.

Initialization: we suppose that subset of columns (at least one for each ) is available, providing a feasible Restricted Linear Programming Master Problem:



Primal feasibility: Any feasible solution of RLMP is feasible for LPM. In particular, is a feasible solution of LPM, and so

Optimality check for LPM: We need to check whether is dual feasible for LPM. This involves checking for each column, that is for each , and for each whether the reduced price . Rather than examining each point separately, we treat all points in implicitly by solving an optimization subproblem:

Stopping criteria: If for the solution is dual feasible for LPM, and so . As the value of the primal feasible solution equals that of this upper bound, is optimal for LPM.

Generating a new column: If for some , the column corresponding to the optimal solution of the subproblem has positive reduced price. Introducing the column leads to a Restricted Linear Programming Master Problem that can be easily reoptimized (e.g., by the primal simplex algorithm)

Methodology in detail

Column generation schematics[4]

To illustrate the algorithm, we will use a common example: an algorithm for one-dimensional cutting stock problem.

Problem Overview


A set of item types ,

For every item type , its length Li and the number of pieces to be produced ,

The length of the starting objects to be cut,


To find the minimum number of objects needed to satisfy the demand of all item types.


The problem can be modeled as follows:


: set of all possible cutting patterns that can be used to obtain item types in from the original objects of length  ;

 : number of pieces of type in the cutting pattern .

 : number of original objects to be cut with pattern .

The algorithm to solve this problem is built on the solution of the continuous relaxation of the above model, i.e., the model obtained by replacing constraints

with constraints...

Sometimes could be so large that enumerating all patterns would not be practical. For this purpose, the column generation below can be used:

Step 0: initialize the problem

Generate a subset of patterns for which the problem has a solution that is feasible (a typical initialization is that of starting with the single-item cutting patterns).

Step 1: formulation and solution of the master problem

Solve the master problem (restricted to the patterns (i.e: variables) with )

By solving this problem one can obtain first a primal optimal solution and then a dual optimal solution  such that and satisfy the complementary slackness condition (for example, this could be done with the simplex method).

Step 2: solution of the subproblem  

Or in other words, the next step is to find the solution of the following integer linear programming problem (called subproblem or slave problem) with |K| variables and one constraint:

For this problem, the optimal solution would be:

Step 3: optimality check 

As it was previously highlighted, it is necessary to conduct an optimality check in order to decide if the optimal solution has been reached or not. Below is the condition:

If...then STOP.

is an optimal solution of the full continuous relaxation (including all patterns in ). Otherwise, update the master problem by including in the pattern γ defined by (this means that column has to be included in the constraint matrix) and go to Step 1.

Finally, one has to go from the optimal solution of the continuous relaxation to a heuristic (i.e., not necessarily optimal but hopefully good) solution of the original problem with integrality constraints. This can be done in at least two different ways:

By rounding up the entries of (this is a good choice if these entries are large: 335.4 is not very different from 336...); Is worth noticing that rounding down is not allowed due to the fact that it would provide infeasible integer solution.

By applying an integer linear programming method (for instance the Branch-and Bound) to the last master problem that was generated; we are taking a step which is equivalent to solving the original problem (with integrality constraints)but restricted to the “good” patterns (those in S′ ) found in the above steps

Numerical example: The Cutting Stock problem

Suppose we want to solve a numerical example of the cutting stock problem that we have discussed during the theory section of this wiki, specifically a one-dimensional cutting stock problem

Problem Overview

A company produces steel bars with diameter 45 millimeters and length 33 meters. The company also takes care of cutting the bars for their different customers, who each require different lengths. At the moment, the following demand forecast is expected and must be satisfied:

Pieces needed Piece length(m) Type of item
144 6 1
105 13.5 2
72 15 3
30 16.5 4
24 22.5 5




= {1, 2, 3, 4, 5}: set of item types;



: bar length (before the cutting process)

: length of item ;

 : number of pieces of type required;

 : number of pieces of type in pattern

Decision variables

 : number of bars that should be portioned using pattern


Solving the problem







Y1 28.8
Y2 52.5
Y3 24
Y4 15
Y5 24

Next, a new possible pattern (number 6) will be consider. This pattern contains only one piece of item type number 5. So the question is if the new solution would remain optimal if this new pattern was allowed. Duality helps answer ths question. At every iteration of the simplex method, the outcome is a feasible basic solution (corresponding to some basis B) for the primal problem and a dual solution (the multipliers uT = cT BB−1 ) that satisfy the complementary slackness conditions. (Note: the dual solution will be feasible only when the last iteration is reached)

The inclusion of new pattern "6" corresponds to including a new variable in the primal problem, with objective cost 1 (as each time pattern 6 is chosen, one bar is cut) and corresponding to the following column in the constraint matrix:


The new dual constraint is:


(Note the solution for the dual problem would be:

Dual variable Variable value
D1 0.067
D2 0.167
D3 0.167
D4 0.167
D5 0.333

Since the new constraint is violated.


the norm of

To help us solve the problem, the next step is t let y6 enter the basis. To do so, we modify the problem by inserting the new variable as below:





And by so doin, it enables the conversion of the problem of finding a variable with negative reduced cost into the integer linear programming problem below:




which has the following optimal solution:

This matches the pattern called D6 earlier on in this page.

Optimality test

If :



For this example we find that the optimality test is met as so we have have found an optimal solution of the relaxed continuos problem (if this was not the case we would have had to go back to Step 1 as descrbed in the algorithm discussion of this page)

Algorithm discussion

The column generation subproblem is the critical part of the method is Step 2, i.e., generating the new columns. It is not reasonable to compute the reduced costs of all variables for , otherwise this procedure would reduce to the simplex method. In fact, n can be very large (as in the cutting-stock problem) or, for some reason, it might not be possible or convenient to enumerate all decision variables. It is then necessary to study a specific column generation algorithm for each problem; only if such an algorithm exists (and is efficient), the method can be fully developed. In the one-dimensional cutting stock problem, we transformed the column generation subproblem into an easily solvable integer linear programming problem. In other cases, the computational effort required to solve the subproblem may be so high as to make the full procedure unpractical.



  • Bandwith packing
  • Bus driver scheduling

Bandwidth packing


Bus driver scheduling


Supply Chain scheduling problem



Column generation is a way of beginning with a small, manageable parts of a problem (specifically, a few of the variables), solving that part, analyzing that partial solution to discover the next part of the problem (specifically, one or more variables) to add to the model, and then resolving the extended model. Column generation repeats the algorithm steps until it achieves an optimal solution to the entire problem.

More formally, column generation is a way of solving a linear programming problem that adds columns (corresponding to constrained variables) during the pricing phase of the simplex method of solving the problem. Generating a column in the primal simplex formulation of a linear programming problem corresponds to adding a constraint in its dual formulation.

Column generation provides an advantage to the simplex method as the solvers (when computing the solution with software) will not need to access all the variables of the problem simultaneously. In fact, a solver could begin work with only the basis (a particular subset of the constrained variables) and then use reduced cost to decide which other variables to access as needed.


  • L.A. Wolsey, Integer programming. Wiley,Column Generation Algorithms p185-p189,1998 [8]
  • L. De Giovanni M. Di Summa G. Zambelli - Methods and Models for Combinatorial Optimization
  • Dantzig-Wolfe decomposition. Encyclopedia of Mathematics. URL:[9]
  • GERARD. (2005). Personnel and Vehicle scheduling, Column Generation, slide 12. URL:[4]
  1. s
  2. Dantzig-Wolfe decomposition
  3. Methodology
  4. 4.0 4.1 4.2
  6. 6.0 6.1
  8. Methodology
  9. Dantzig-Wolfe decomposition