Lexicographic column generation with a tree search pricing algorithm

We present an exact and generic method for solving the pricing problem in column generation, termed the tree search pricing algorithm (TSPA). TSPA explores the space of feasible columns via a search tree and identifies all columns with a reduced-cost value below an adaptive threshold. Inspired by an approach from Krumke et al. (in: European symposium on algorithms, Springer, pp 637–648, 2002) for vehicle routing problems, we formalize and generalize this dynamic programming-based method to make it applicable across a wide range of problem classes. To improve efficiency, we derive strong completion bounds that effectively prune the search tree, significantly accelerating the generation of columns and reducing overall solution time. Additionally, we demonstrate that TSPA can be seamlessly combined with lexicographic optimization, to address problems with multiple objectives efficiently. We validate the theoretical results through an extensive computational study on two applications: the sequence-dependent cutting stock problem and the assignment of transport orders to hospital employees. Using real-world data, we demonstrate that TSPA outperforms other pricing approaches for column generation within the restricted master heuristic. For the second application, the column generation approach with TSPA surpasses both an industry-standard heuristic and a standard solver for a polynomial-size MIP formulation in a real-world setting.