Julia Wahlen

• This thesis advances combinatorial optimization by developing exact solution methods for two NP-hard problems arising in warehousing and flexible manufacturing: the order batching problem (OBP) and the set-union bin packing problem (SUBP). Both are highly relevant to real-world logistics and production systems. For the OBP, which involves grouping customer orders into capacity-constrained batches to minimize picker travel distance, two problem variants are studied: single-block and multi-block warehouse configurations. A new branch-price-and-cut (BPC) method is proposed, combining column generation (CG) with dynamic programming-based pricing using completion bounds, valid inequalities, and tailored branching rules. Additionally, heuristic approaches are derived from the exact BPC. The BPC-based methods significantly outperform existing algorithms, improving both runtime and solution quality, and solving many previously open instances. For the SUBP, a bin packing generalization with overlapping item requirements, a branch-and-price (B&P) algorithm is introduced. Several pricing strategies are proposed and evaluated, with the most effective combining a greedy heuristic and item-based labeling with completion bounds. The B&P method solves over 10,000 benchmark instances to optimality and improves many best-known solutions. Overall, the results demonstrate the effectiveness of structure-aware, CG-based methods for large-scale discrete optimization problems.