Two-stage column generation and applications

Column generation has been intensively used in the last decades to compute good quality lower bounds for combinatorial problems re-formulated through Dantzig-Wolfe decomposition. In this paper we propose a novel framework to cope with problems in which the struc-ture of the original formulation, namely the presence of a combinato-rial number of decision variables, does not allow for straightforward reformulation. The basic idea is to start from a meaningful subset of original variables, apply the DW reformulation to the subset, solve the reformulation with column generation and perform the explicit pric-ing on original variables retracing back the reformulation and using complementary-slackness conditions. The Discrete Split Delivery Ve-hicle Routing Problem with Time Windows (DSDVRPTW) is used as an illustration for the method, which provides a new exact approach to the problem. 2