A faster variant of the Gilmore and Gomory technique for cutting stock problems

In 1961 Gilmore and Gomory proposed the delayed column generation technique for the resolution of cutting stock problems. Since then, it has been widely used, mainly in one-dimensional cutting problems. The application of this technique to two-dimensional cutting problems has been conditioned by the high computational effort of the auxiliary problems (knapsack problems) resolution. Gilmore and Gomory presented some algorithms that solve the auxiliary problem with different constraints. However, as the performance of these algorithms is crucial for the global efficiency of the delayed column generation technique, several other authors have developed new algorithms or even adapted or improved those proposed by Gilmore and Gomory. This paper presents a different approach, the fast delayed column generation. The idea is the reduction of the number of times the auxiliary problem is solved, instead of decreasing the resolution time of each auxiliary problem, thus improving the efficiency of the overall Gilmore and Gomory technique. The tests performed with two-dimensional rectangular problems proved that this approach is faster than the classical delayed column generation technique. Moreover, the relative efficiency of the fast delayed column generation increases with the auxiliary problems complexity.