Column generation algorithms

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

Introduction

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].

Formulation

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.

Examples

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.

Let $b_i$ be the demand for each piece of length $li$.

Let $x_p$ be the number of times pattern $p$ is cut. Then the column generation RMP is:

An initial set of columns must now be selected. This can be done simply by selecting “fake” columns where we know they will not end up in the solution, or by covering the basis. In this example, an identity matrix can be selected. A better basis-covering initial matrix would take $\left \lfloor L/l_i \right \rfloor$ because we can always cut at least that many bars from our raw. Thus, our initial $A$ matrix and basis, $B$ is:

Solving the dual of the RMP then yields the dual multiplier . These values are then passed to the sub-problem to see if any columns will be added to $A$. The sub-problem is as follows:

Conclusion

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.

References

[1] L. R. Ford, Jr., D. R. Fulkerson, (1958) A Suggested Computation for Maximal Multi-Commodity Network Flows. Management Science 5(1):97-101. http://dx.doi.org/10.1287/mnsc.5.1.97

[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 http://systemsbiology.ucsd.edu/sites/default/files/Attachments/Images/classes/convex_presentations/ColGen.pdf

[4] Giovanni Righini. (April 2013) Column Generation [PDF document]. Retrieved from http://homes.di.unimi.it/righini/Didattica/ComplementiRicercaOperativa/MaterialeCRO/CG.pdf

[5] Gan, H. (2008) Column Generation [PDF document]. Retrieved from http://www.more.ms.unimelb.edu.au/students/operationsresearch/lecturenotes/620362_ColGen.pdf

[6] Stein, C. (2007) Column Generation: Cutting Stock - A Very Applied Method [PDF Document]. Retrieved from http://www.columbia.edu/~cs2035/courses/ieor4600.S07/columngeneration.pdf