Lexicographic Branch-and-Bound Column Search

We present an exact generic method for solving the pricing subproblem in a column generation approach, which we call branch-and-bound column search. It searches the space of all feasible columns via a branch-and-bound tree search and simultaneously returns all columns with a reduced-cost value below a certain threshold. The approach is based on an idea from Krumke et al. (2002) for the solution of vehicle routing problems. There it was shown that it is particularly efficient when the optimal columns are sparse and that it allows to compute optimal or near-optimal solutions of the master problem already at the root node of the branch-and-bound tree. In this work, we formalize and generalize this method such that it can be applied to a large variety of different problem classes. To this end, we introduce dedicated enumeration algorithms which ensure that every column needed for an optimal solution of the LP-relaxed master problem is considered. We further derive strong bounds to effectively prune the search tree, which allows us to significantly speed up the generation of columns and thus reduces the overall solution time. In addition,we showthat our column search methods can be combined with lexicographic optimization easily and efficiently to solve problems with multiple objectives. Finally, the theoretical results are corroborated in an extensive computational study for two different applications: the sequence-dependent cutting stock problem and the optimized assignment of transport orders to employees in a hospital. On the basis of real-world data, we can show in both cases that branch-and-bound column search is superior to conventional column generation. In particular, for the second application it outperforms both an industry-standard heuristic for the problem as well as a standard solver on a polynomial-size MIP formulation within a real-world problem setting.



View Lexicographic Branch-and-Bound Column Search