Salani, M., Vacca, I., and Bierlaire, M. (2010)

Two-stage column generation

We introduce a new concept in column generation for handling complex large scale optimization problems, called two-stage column generation, where columns for the compact and extensive formulation are simultaneously generated. The new framework is specifically conceived for tackling complex problems that cannot be efficiently solved by standard column generation and exploits the Relationship between compact and extensive formulation. In particular, the concept of extensive reduced cost is introduced in order to estimate the contribution of compact formulation variables to the master problem. A formal description of the proposed framework is provided and major theoretical issues are discussed. An example based on the Resource Constrained Shortest Path Problem illustrates how two-stage column generation works when the pricing subproblem satisfies or not the integrality property. The two-stage scheme is applied to the Discrete Split Delivery Vehicle Routing Problem and extensive computational experiments are provided to validate our framework. In particular, computational results show that two-stage column generation reduces the number of generated columns and the computational time for complex instances. The transferability of the designed framework across applications and future research directions are further discussed.