Recent Advances in Column Generation

In a recent paper, a class of linear programming problems referred to as problems with column-dependent-rows has been introduced. In these problems, the structural linking constraints are dependent on the set of variables, and when the restricted master problem is formed with a subset of variables, only the linking constraints induced by these variables exist in this problem. The main difficulty in solving these problems is to price columns that induce new rows as the dual variables associated with these rows are unknown.

These problems grow both horizontally and vertically through the iterations of the column generation algorithm, leading to simultaneous column-and-row generation. We discuss the general characteristics of problems with column-dependent-rows and exemplify simultaneous column-and-row generation on

the multi-stage cutting stock problem, an extension of the one-dimensional cutting stock problem in which the stock roll is cut into the finished rolls in more than one stage due to technical restrictions. This problem also possesses a two-level decomposable structure. We then handle the problems that allow Dantzig-Wolfe decomposition in two levels and discuss generic solution methodologies for these problems.