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 formula-tion 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 con-cept 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 Re-source 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 com-putational experiments are provided to validate our framework. In particular, computational results show that two-stage column genera-tion reduces the number of generated columns and the computational time for complex instances. The transferability of the designed frame-work across applications and future research directions are further discussed. 2