Column generation algorithms

From optimization
Revision as of 14:29, 22 May 2015 by Kedricdaly (Talk | contribs)

Jump to: navigation, search

Authors: Kedric Daly[2015]
Stewards: Dajun Yue, Fengqi You



Column generation algorithms are used for MILP problems. The formulation was initially proposed by Ford and Fulkerson in 1958[1]. The main advantage of column generation is that not all possibilities need to be enumerated. Instead, the problem is first formulated as a restricted master problem (RMP). This RMP has as few variables as possible, and new variables are brought into the basis as needed, similar to the simplex method[2].


The formulation of the column generation problem depends on the type of problem. One common example is the cutting stock problem. However, all cases involve taking the original problem and formulating the RMP as well as a subproblem. The solution of the RMP determines some of the parameters in the subproblem whereas the subproblem will be used to determine if there are any columns which can enter the basis. The subproblem does this by solving for the minimum reduced cost. If the reduced cost is negative, the solution can enter the basis as a new column. If the reduced cost is greater than or equal to zero, the lower bound for the optimal solution has been found, although this may not be an integer solution.


Cutting Stock Problem (CSP)

In the cutting stock problem, the goal is to minimize the waste obtained from cutting rolls of fixed size while fulfilling customer orders.

For example, we may have steel rods of length L = 17m, with customer orders for twenty-five 3m length rods, twenty 5m length rods, and fifteen 9m length rods.

Column Generation Formulation
For the column generation formulation, the different patterns the rods can be cut into are the main focus[6].

Let P be the set of all patterns that can be cut.
Let a_ip be the number of pieces of length li cut in pattern p. L vector.png
Let b_i be the demand for each piece of length li. B vector.png
Let x_p be the number of times pattern p is cut. Then the column generation RMP is:

RMP 1 obj.png

RMP 1 constraints.PNG


Column generation algorithms are most useful when dealing with large numbers of variables. They are effective because they avoid enumerating all possible elements of a traditional MILP formulation, and instead only evaluate variables as needed.


[1] L. R. Ford, Jr., D. R. Fulkerson, (1958) A Suggested Computation for Maximal Multi-Commodity Network Flows. Management Science 5(1):97-101.

[2] Desrosiers, J., & Lübbecke, M. (2005). A Primer in Column Generation. In G. Desaulniers, J. Desrosiers & M. Solomon (Eds.), Column Generation (pp. 1-32): Springer US.

[3] Column Generation [PDF document]. Retrieved from

[4] Giovanni Righini. (April 2013) Column Generation [PDF document]. Retrieved from

[5] Gan, H. (2008) Column Generation [PDF document]. Retrieved from

[6] Stein, C. (2007) Column Generation: Cutting Stock - A Very Applied Method [PDF Document]. Retrieved from